Mercurial > hg > graal-jvmci-8
comparison src/share/vm/opto/block.cpp @ 14456:abec000618bf
Merge
author | kvn |
---|---|
date | Tue, 28 Jan 2014 12:25:34 -0800 |
parents | de6a9e811145 c3efa8868779 |
children | 4ca6dc0799b6 78bbf4d43a14 |
comparison
equal
deleted
inserted
replaced
14269:2a8891e0a082 | 14456:abec000618bf |
---|---|
140 } | 140 } |
141 | 141 |
142 // Find and remove n from block list | 142 // Find and remove n from block list |
143 void Block::find_remove( const Node *n ) { | 143 void Block::find_remove( const Node *n ) { |
144 remove_node(find_node(n)); | 144 remove_node(find_node(n)); |
145 } | |
146 | |
147 bool Block::contains(const Node *n) const { | |
148 return _nodes.contains(n); | |
145 } | 149 } |
146 | 150 |
147 // Return empty status of a block. Empty blocks contain only the head, other | 151 // Return empty status of a block. Empty blocks contain only the head, other |
148 // ideal nodes, and an optional trailing goto. | 152 // ideal nodes, and an optional trailing goto. |
149 int Block::is_Empty() const { | 153 int Block::is_Empty() const { |
524 add_block_at(block_no + 1, block); | 528 add_block_at(block_no + 1, block); |
525 } | 529 } |
526 | 530 |
527 // Does this block end in a multiway branch that cannot have the default case | 531 // Does this block end in a multiway branch that cannot have the default case |
528 // flipped for another case? | 532 // flipped for another case? |
529 static bool no_flip_branch( Block *b ) { | 533 static bool no_flip_branch(Block *b) { |
530 int branch_idx = b->number_of_nodes() - b->_num_succs-1; | 534 int branch_idx = b->number_of_nodes() - b->_num_succs-1; |
531 if( branch_idx < 1 ) return false; | 535 if (branch_idx < 1) { |
532 Node *bra = b->get_node(branch_idx); | 536 return false; |
533 if( bra->is_Catch() ) | 537 } |
538 Node *branch = b->get_node(branch_idx); | |
539 if (branch->is_Catch()) { | |
534 return true; | 540 return true; |
535 if( bra->is_Mach() ) { | 541 } |
536 if( bra->is_MachNullCheck() ) | 542 if (branch->is_Mach()) { |
543 if (branch->is_MachNullCheck()) { | |
537 return true; | 544 return true; |
538 int iop = bra->as_Mach()->ideal_Opcode(); | 545 } |
539 if( iop == Op_FastLock || iop == Op_FastUnlock ) | 546 int iop = branch->as_Mach()->ideal_Opcode(); |
547 if (iop == Op_FastLock || iop == Op_FastUnlock) { | |
540 return true; | 548 return true; |
549 } | |
550 // Don't flip if branch has an implicit check. | |
551 if (branch->as_Mach()->is_TrapBasedCheckNode()) { | |
552 return true; | |
553 } | |
541 } | 554 } |
542 return false; | 555 return false; |
543 } | 556 } |
544 | 557 |
545 // Check for NeverBranch at block end. This needs to become a GOTO to the | 558 // Check for NeverBranch at block end. This needs to become a GOTO to the |
694 i--; | 707 i--; |
695 } | 708 } |
696 } // End of for all blocks | 709 } // End of for all blocks |
697 } | 710 } |
698 | 711 |
712 Block *PhaseCFG::fixup_trap_based_check(Node *branch, Block *block, int block_pos, Block *bnext) { | |
713 // Trap based checks must fall through to the successor with | |
714 // PROB_ALWAYS. | |
715 // They should be an If with 2 successors. | |
716 assert(branch->is_MachIf(), "must be If"); | |
717 assert(block->_num_succs == 2, "must have 2 successors"); | |
718 | |
719 // Get the If node and the projection for the first successor. | |
720 MachIfNode *iff = block->get_node(block->number_of_nodes()-3)->as_MachIf(); | |
721 ProjNode *proj0 = block->get_node(block->number_of_nodes()-2)->as_Proj(); | |
722 ProjNode *proj1 = block->get_node(block->number_of_nodes()-1)->as_Proj(); | |
723 ProjNode *projt = (proj0->Opcode() == Op_IfTrue) ? proj0 : proj1; | |
724 ProjNode *projf = (proj0->Opcode() == Op_IfFalse) ? proj0 : proj1; | |
725 | |
726 // Assert that proj0 and succs[0] match up. Similarly for proj1 and succs[1]. | |
727 assert(proj0->raw_out(0) == block->_succs[0]->head(), "Mismatch successor 0"); | |
728 assert(proj1->raw_out(0) == block->_succs[1]->head(), "Mismatch successor 1"); | |
729 | |
730 ProjNode *proj_always; | |
731 ProjNode *proj_never; | |
732 // We must negate the branch if the implicit check doesn't follow | |
733 // the branch's TRUE path. Then, the new TRUE branch target will | |
734 // be the old FALSE branch target. | |
735 if (iff->_prob <= 2*PROB_NEVER) { // There are small rounding errors. | |
736 proj_never = projt; | |
737 proj_always = projf; | |
738 } else { | |
739 // We must negate the branch if the trap doesn't follow the | |
740 // branch's TRUE path. Then, the new TRUE branch target will | |
741 // be the old FALSE branch target. | |
742 proj_never = projf; | |
743 proj_always = projt; | |
744 iff->negate(); | |
745 } | |
746 assert(iff->_prob <= 2*PROB_NEVER, "Trap based checks are expected to trap never!"); | |
747 // Map the successors properly | |
748 block->_succs.map(0, get_block_for_node(proj_never ->raw_out(0))); // The target of the trap. | |
749 block->_succs.map(1, get_block_for_node(proj_always->raw_out(0))); // The fall through target. | |
750 | |
751 if (block->get_node(block->number_of_nodes() - block->_num_succs + 1) != proj_always) { | |
752 block->map_node(proj_never, block->number_of_nodes() - block->_num_succs + 0); | |
753 block->map_node(proj_always, block->number_of_nodes() - block->_num_succs + 1); | |
754 } | |
755 | |
756 // Place the fall through block after this block. | |
757 Block *bs1 = block->non_connector_successor(1); | |
758 if (bs1 != bnext && move_to_next(bs1, block_pos)) { | |
759 bnext = bs1; | |
760 } | |
761 // If the fall through block still is not the next block, insert a goto. | |
762 if (bs1 != bnext) { | |
763 insert_goto_at(block_pos, 1); | |
764 } | |
765 return bnext; | |
766 } | |
767 | |
699 // Fix up the final control flow for basic blocks. | 768 // Fix up the final control flow for basic blocks. |
700 void PhaseCFG::fixup_flow() { | 769 void PhaseCFG::fixup_flow() { |
701 // Fixup final control flow for the blocks. Remove jump-to-next | 770 // Fixup final control flow for the blocks. Remove jump-to-next |
702 // block. If neither arm of a IF follows the conditional branch, we | 771 // block. If neither arm of an IF follows the conditional branch, we |
703 // have to add a second jump after the conditional. We place the | 772 // have to add a second jump after the conditional. We place the |
704 // TRUE branch target in succs[0] for both GOTOs and IFs. | 773 // TRUE branch target in succs[0] for both GOTOs and IFs. |
705 for (uint i = 0; i < number_of_blocks(); i++) { | 774 for (uint i = 0; i < number_of_blocks(); i++) { |
706 Block* block = get_block(i); | 775 Block* block = get_block(i); |
707 block->_pre_order = i; // turn pre-order into block-index | 776 block->_pre_order = i; // turn pre-order into block-index |
717 Block* bs0 = block->non_connector_successor(0); | 786 Block* bs0 = block->non_connector_successor(0); |
718 | 787 |
719 // Check for multi-way branches where I cannot negate the test to | 788 // Check for multi-way branches where I cannot negate the test to |
720 // exchange the true and false targets. | 789 // exchange the true and false targets. |
721 if (no_flip_branch(block)) { | 790 if (no_flip_branch(block)) { |
722 // Find fall through case - if must fall into its target | 791 // Find fall through case - if must fall into its target. |
792 // Get the index of the branch's first successor. | |
723 int branch_idx = block->number_of_nodes() - block->_num_succs; | 793 int branch_idx = block->number_of_nodes() - block->_num_succs; |
724 for (uint j2 = 0; j2 < block->_num_succs; j2++) { | 794 |
725 const ProjNode* p = block->get_node(branch_idx + j2)->as_Proj(); | 795 // The branch is 1 before the branch's first successor. |
726 if (p->_con == 0) { | 796 Node *branch = block->get_node(branch_idx-1); |
727 // successor j2 is fall through case | 797 |
728 if (block->non_connector_successor(j2) != bnext) { | 798 // Handle no-flip branches which have implicit checks and which require |
729 // but it is not the next block => insert a goto | 799 // special block ordering and individual semantics of the 'fall through |
730 insert_goto_at(i, j2); | 800 // case'. |
801 if ((TrapBasedNullChecks || TrapBasedRangeChecks) && | |
802 branch->is_Mach() && branch->as_Mach()->is_TrapBasedCheckNode()) { | |
803 bnext = fixup_trap_based_check(branch, block, i, bnext); | |
804 } else { | |
805 // Else, default handling for no-flip branches | |
806 for (uint j2 = 0; j2 < block->_num_succs; j2++) { | |
807 const ProjNode* p = block->get_node(branch_idx + j2)->as_Proj(); | |
808 if (p->_con == 0) { | |
809 // successor j2 is fall through case | |
810 if (block->non_connector_successor(j2) != bnext) { | |
811 // but it is not the next block => insert a goto | |
812 insert_goto_at(i, j2); | |
813 } | |
814 // Put taken branch in slot 0 | |
815 if (j2 == 0 && block->_num_succs == 2) { | |
816 // Flip targets in succs map | |
817 Block *tbs0 = block->_succs[0]; | |
818 Block *tbs1 = block->_succs[1]; | |
819 block->_succs.map(0, tbs1); | |
820 block->_succs.map(1, tbs0); | |
821 } | |
822 break; | |
731 } | 823 } |
732 // Put taken branch in slot 0 | |
733 if (j2 == 0 && block->_num_succs == 2) { | |
734 // Flip targets in succs map | |
735 Block *tbs0 = block->_succs[0]; | |
736 Block *tbs1 = block->_succs[1]; | |
737 block->_succs.map(0, tbs1); | |
738 block->_succs.map(1, tbs0); | |
739 } | |
740 break; | |
741 } | 824 } |
742 } | 825 } |
743 | 826 |
744 // Remove all CatchProjs | 827 // Remove all CatchProjs |
745 for (uint j = 0; j < block->_num_succs; j++) { | 828 for (uint j = 0; j < block->_num_succs; j++) { |
842 } | 925 } |
843 } // End of for all blocks | 926 } // End of for all blocks |
844 } | 927 } |
845 | 928 |
846 | 929 |
930 // postalloc_expand: Expand nodes after register allocation. | |
931 // | |
932 // postalloc_expand has to be called after register allocation, just | |
933 // before output (i.e. scheduling). It only gets called if | |
934 // Matcher::require_postalloc_expand is true. | |
935 // | |
936 // Background: | |
937 // | |
938 // Nodes that are expandend (one compound node requiring several | |
939 // assembler instructions to be implemented split into two or more | |
940 // non-compound nodes) after register allocation are not as nice as | |
941 // the ones expanded before register allocation - they don't | |
942 // participate in optimizations as global code motion. But after | |
943 // register allocation we can expand nodes that use registers which | |
944 // are not spillable or registers that are not allocated, because the | |
945 // old compound node is simply replaced (in its location in the basic | |
946 // block) by a new subgraph which does not contain compound nodes any | |
947 // more. The scheduler called during output can later on process these | |
948 // non-compound nodes. | |
949 // | |
950 // Implementation: | |
951 // | |
952 // Nodes requiring postalloc expand are specified in the ad file by using | |
953 // a postalloc_expand statement instead of ins_encode. A postalloc_expand | |
954 // contains a single call to an encoding, as does an ins_encode | |
955 // statement. Instead of an emit() function a postalloc_expand() function | |
956 // is generated that doesn't emit assembler but creates a new | |
957 // subgraph. The code below calls this postalloc_expand function for each | |
958 // node with the appropriate attribute. This function returns the new | |
959 // nodes generated in an array passed in the call. The old node, | |
960 // potential MachTemps before and potential Projs after it then get | |
961 // disconnected and replaced by the new nodes. The instruction | |
962 // generating the result has to be the last one in the array. In | |
963 // general it is assumed that Projs after the node expanded are | |
964 // kills. These kills are not required any more after expanding as | |
965 // there are now explicitly visible def-use chains and the Projs are | |
966 // removed. This does not hold for calls: They do not only have | |
967 // kill-Projs but also Projs defining values. Therefore Projs after | |
968 // the node expanded are removed for all but for calls. If a node is | |
969 // to be reused, it must be added to the nodes list returned, and it | |
970 // will be added again. | |
971 // | |
972 // Implementing the postalloc_expand function for a node in an enc_class | |
973 // is rather tedious. It requires knowledge about many node details, as | |
974 // the nodes and the subgraph must be hand crafted. To simplify this, | |
975 // adlc generates some utility variables into the postalloc_expand function, | |
976 // e.g., holding the operands as specified by the postalloc_expand encoding | |
977 // specification, e.g.: | |
978 // * unsigned idx_<par_name> holding the index of the node in the ins | |
979 // * Node *n_<par_name> holding the node loaded from the ins | |
980 // * MachOpnd *op_<par_name> holding the corresponding operand | |
981 // | |
982 // The ordering of operands can not be determined by looking at a | |
983 // rule. Especially if a match rule matches several different trees, | |
984 // several nodes are generated from one instruct specification with | |
985 // different operand orderings. In this case the adlc generated | |
986 // variables are the only way to access the ins and operands | |
987 // deterministically. | |
988 // | |
989 // If assigning a register to a node that contains an oop, don't | |
990 // forget to call ra_->set_oop() for the node. | |
991 void PhaseCFG::postalloc_expand(PhaseRegAlloc* _ra) { | |
992 GrowableArray <Node *> new_nodes(32); // Array with new nodes filled by postalloc_expand function of node. | |
993 GrowableArray <Node *> remove(32); | |
994 GrowableArray <Node *> succs(32); | |
995 unsigned int max_idx = C->unique(); // Remember to distinguish new from old nodes. | |
996 DEBUG_ONLY(bool foundNode = false); | |
997 | |
998 // for all blocks | |
999 for (uint i = 0; i < number_of_blocks(); i++) { | |
1000 Block *b = _blocks[i]; | |
1001 // For all instructions in the current block. | |
1002 for (uint j = 0; j < b->number_of_nodes(); j++) { | |
1003 Node *n = b->get_node(j); | |
1004 if (n->is_Mach() && n->as_Mach()->requires_postalloc_expand()) { | |
1005 #ifdef ASSERT | |
1006 if (TracePostallocExpand) { | |
1007 if (!foundNode) { | |
1008 foundNode = true; | |
1009 tty->print("POSTALLOC EXPANDING %d %s\n", C->compile_id(), | |
1010 C->method() ? C->method()->name()->as_utf8() : C->stub_name()); | |
1011 } | |
1012 tty->print(" postalloc expanding "); n->dump(); | |
1013 if (Verbose) { | |
1014 tty->print(" with ins:\n"); | |
1015 for (uint k = 0; k < n->len(); ++k) { | |
1016 if (n->in(k)) { tty->print(" "); n->in(k)->dump(); } | |
1017 } | |
1018 } | |
1019 } | |
1020 #endif | |
1021 new_nodes.clear(); | |
1022 // Collect nodes that have to be removed from the block later on. | |
1023 uint req = n->req(); | |
1024 remove.clear(); | |
1025 for (uint k = 0; k < req; ++k) { | |
1026 if (n->in(k) && n->in(k)->is_MachTemp()) { | |
1027 remove.push(n->in(k)); // MachTemps which are inputs to the old node have to be removed. | |
1028 n->in(k)->del_req(0); | |
1029 j--; | |
1030 } | |
1031 } | |
1032 | |
1033 // Check whether we can allocate enough nodes. We set a fix limit for | |
1034 // the size of postalloc expands with this. | |
1035 uint unique_limit = C->unique() + 40; | |
1036 if (unique_limit >= _ra->node_regs_max_index()) { | |
1037 Compile::current()->record_failure("out of nodes in postalloc expand"); | |
1038 return; | |
1039 } | |
1040 | |
1041 // Emit (i.e. generate new nodes). | |
1042 n->as_Mach()->postalloc_expand(&new_nodes, _ra); | |
1043 | |
1044 assert(C->unique() < unique_limit, "You allocated too many nodes in your postalloc expand."); | |
1045 | |
1046 // Disconnect the inputs of the old node. | |
1047 // | |
1048 // We reuse MachSpillCopy nodes. If we need to expand them, there | |
1049 // are many, so reusing pays off. If reused, the node already | |
1050 // has the new ins. n must be the last node on new_nodes list. | |
1051 if (!n->is_MachSpillCopy()) { | |
1052 for (int k = req - 1; k >= 0; --k) { | |
1053 n->del_req(k); | |
1054 } | |
1055 } | |
1056 | |
1057 #ifdef ASSERT | |
1058 // Check that all nodes have proper operands. | |
1059 for (int k = 0; k < new_nodes.length(); ++k) { | |
1060 if (new_nodes.at(k)->_idx < max_idx || !new_nodes.at(k)->is_Mach()) continue; // old node, Proj ... | |
1061 MachNode *m = new_nodes.at(k)->as_Mach(); | |
1062 for (unsigned int l = 0; l < m->num_opnds(); ++l) { | |
1063 if (MachOper::notAnOper(m->_opnds[l])) { | |
1064 outputStream *os = tty; | |
1065 os->print("Node %s ", m->Name()); | |
1066 os->print("has invalid opnd %d: %p\n", l, m->_opnds[l]); | |
1067 assert(0, "Invalid operands, see inline trace in hs_err_pid file."); | |
1068 } | |
1069 } | |
1070 } | |
1071 #endif | |
1072 | |
1073 // Collect succs of old node in remove (for projections) and in succs (for | |
1074 // all other nodes) do _not_ collect projections in remove (but in succs) | |
1075 // in case the node is a call. We need the projections for calls as they are | |
1076 // associated with registes (i.e. they are defs). | |
1077 succs.clear(); | |
1078 for (DUIterator k = n->outs(); n->has_out(k); k++) { | |
1079 if (n->out(k)->is_Proj() && !n->is_MachCall() && !n->is_MachBranch()) { | |
1080 remove.push(n->out(k)); | |
1081 } else { | |
1082 succs.push(n->out(k)); | |
1083 } | |
1084 } | |
1085 // Replace old node n as input of its succs by last of the new nodes. | |
1086 for (int k = 0; k < succs.length(); ++k) { | |
1087 Node *succ = succs.at(k); | |
1088 for (uint l = 0; l < succ->req(); ++l) { | |
1089 if (succ->in(l) == n) { | |
1090 succ->set_req(l, new_nodes.at(new_nodes.length() - 1)); | |
1091 } | |
1092 } | |
1093 for (uint l = succ->req(); l < succ->len(); ++l) { | |
1094 if (succ->in(l) == n) { | |
1095 succ->set_prec(l, new_nodes.at(new_nodes.length() - 1)); | |
1096 } | |
1097 } | |
1098 } | |
1099 | |
1100 // Index of old node in block. | |
1101 uint index = b->find_node(n); | |
1102 // Insert new nodes into block and map them in nodes->blocks array | |
1103 // and remember last node in n2. | |
1104 Node *n2 = NULL; | |
1105 for (int k = 0; k < new_nodes.length(); ++k) { | |
1106 n2 = new_nodes.at(k); | |
1107 b->insert_node(n2, ++index); | |
1108 map_node_to_block(n2, b); | |
1109 } | |
1110 | |
1111 // Add old node n to remove and remove them all from block. | |
1112 remove.push(n); | |
1113 j--; | |
1114 #ifdef ASSERT | |
1115 if (TracePostallocExpand && Verbose) { | |
1116 tty->print(" removing:\n"); | |
1117 for (int k = 0; k < remove.length(); ++k) { | |
1118 tty->print(" "); remove.at(k)->dump(); | |
1119 } | |
1120 tty->print(" inserting:\n"); | |
1121 for (int k = 0; k < new_nodes.length(); ++k) { | |
1122 tty->print(" "); new_nodes.at(k)->dump(); | |
1123 } | |
1124 } | |
1125 #endif | |
1126 for (int k = 0; k < remove.length(); ++k) { | |
1127 if (b->contains(remove.at(k))) { | |
1128 b->find_remove(remove.at(k)); | |
1129 } else { | |
1130 assert(remove.at(k)->is_Proj() && (remove.at(k)->in(0)->is_MachBranch()), ""); | |
1131 } | |
1132 } | |
1133 // If anything has been inserted (n2 != NULL), continue after last node inserted. | |
1134 // This does not always work. Some postalloc expands don't insert any nodes, if they | |
1135 // do optimizations (e.g., max(x,x)). In this case we decrement j accordingly. | |
1136 j = n2 ? b->find_node(n2) : j; | |
1137 } | |
1138 } | |
1139 } | |
1140 | |
1141 #ifdef ASSERT | |
1142 if (foundNode) { | |
1143 tty->print("FINISHED %d %s\n", C->compile_id(), | |
1144 C->method() ? C->method()->name()->as_utf8() : C->stub_name()); | |
1145 tty->flush(); | |
1146 } | |
1147 #endif | |
1148 } | |
1149 | |
1150 | |
1151 //------------------------------dump------------------------------------------- | |
847 #ifndef PRODUCT | 1152 #ifndef PRODUCT |
848 void PhaseCFG::_dump_cfg( const Node *end, VectorSet &visited ) const { | 1153 void PhaseCFG::_dump_cfg( const Node *end, VectorSet &visited ) const { |
849 const Node *x = end->is_block_proj(); | 1154 const Node *x = end->is_block_proj(); |
850 assert( x, "not a CFG" ); | 1155 assert( x, "not a CFG" ); |
851 | 1156 |