55 if( !n ) continue; // Missing inputs are TOP
56 if( phase->type(n) == Type::CONTROL )
57 return Type::CONTROL;
58 }
59 return Type::TOP; // All paths dead? Then so are we
60 }
61
62 //------------------------------Identity---------------------------------------
63 // Check for Region being Identity.
64 Node* RegionNode::Identity(PhaseGVN* phase) {
65 // Cannot have Region be an identity, even if it has only 1 input.
66 // Phi users cannot have their Region input folded away for them,
67 // since they need to select the proper data input
68 return this;
69 }
70
71 //------------------------------merge_region-----------------------------------
72 // If a Region flows into a Region, merge into one big happy merge. This is
73 // hard to do if there is stuff that has to happen
74 static Node *merge_region(RegionNode *region, PhaseGVN *phase) {
75 if( region->Opcode() != Op_Region ) // Do not do to LoopNodes
76 return NULL;
77 Node *progress = NULL; // Progress flag
78 PhaseIterGVN *igvn = phase->is_IterGVN();
79
80 uint rreq = region->req();
81 for( uint i = 1; i < rreq; i++ ) {
82 Node *r = region->in(i);
83 if( r && r->Opcode() == Op_Region && // Found a region?
84 r->in(0) == r && // Not already collapsed?
85 r != region && // Avoid stupid situations
86 r->outcnt() == 2 ) { // Self user and 'region' user only?
87 assert(!r->as_Region()->has_phi(), "no phi users");
88 if( !progress ) { // No progress
89 if (region->has_phi()) {
90 return NULL; // Only flatten if no Phi users
91 // igvn->hash_delete( phi );
92 }
93 igvn->hash_delete( region );
94 progress = region; // Making progress
95 }
96 igvn->hash_delete( r );
97
98 // Append inputs to 'r' onto 'region'
99 for( uint j = 1; j < r->req(); j++ ) {
100 // Move an input from 'r' to 'region'
101 region->add_req(r->in(j));
102 r->set_req(j, phase->C->top());
103 // Update phis of 'region'
154 }
155
156 return only_phi;
157 }
158
159
160 //------------------------------check_phi_clipping-----------------------------
161 // Helper function for RegionNode's identification of FP clipping
162 // Check inputs to the Phi
163 static bool check_phi_clipping( PhiNode *phi, ConNode * &min, uint &min_idx, ConNode * &max, uint &max_idx, Node * &val, uint &val_idx ) {
164 min = NULL;
165 max = NULL;
166 val = NULL;
167 min_idx = 0;
168 max_idx = 0;
169 val_idx = 0;
170 uint phi_max = phi->req();
171 if( phi_max == 4 ) {
172 for( uint j = 1; j < phi_max; ++j ) {
173 Node *n = phi->in(j);
174 int opcode = n->Opcode();
175 switch( opcode ) {
176 case Op_ConI:
177 {
178 if( min == NULL ) {
179 min = n->Opcode() == Op_ConI ? (ConNode*)n : NULL;
180 min_idx = j;
181 } else {
182 max = n->Opcode() == Op_ConI ? (ConNode*)n : NULL;
183 max_idx = j;
184 if( min->get_int() > max->get_int() ) {
185 // Swap min and max
186 ConNode *temp;
187 uint temp_idx;
188 temp = min; min = max; max = temp;
189 temp_idx = min_idx; min_idx = max_idx; max_idx = temp_idx;
190 }
191 }
192 }
193 break;
194 default:
195 {
196 val = n;
197 val_idx = j;
198 }
199 break;
200 }
201 }
202 }
241 // Control pattern checks
242 top_if = (IfNode*)in1000;
243 bot_if = (IfNode*)in10;
244 }
245 }
246 }
247
248 return (top_if != NULL);
249 }
250
251
252 //------------------------------check_convf2i_clipping-------------------------
253 // Helper function for RegionNode's identification of FP clipping
254 // Verify that the value input to the phi comes from "ConvF2I; LShift; RShift"
255 static bool check_convf2i_clipping( PhiNode *phi, uint idx, ConvF2INode * &convf2i, Node *min, Node *max) {
256 convf2i = NULL;
257
258 // Check for the RShiftNode
259 Node *rshift = phi->in(idx);
260 assert( rshift, "Previous checks ensure phi input is present");
261 if( rshift->Opcode() != Op_RShiftI ) { return false; }
262
263 // Check for the LShiftNode
264 Node *lshift = rshift->in(1);
265 assert( lshift, "Previous checks ensure phi input is present");
266 if( lshift->Opcode() != Op_LShiftI ) { return false; }
267
268 // Check for the ConvF2INode
269 Node *conv = lshift->in(1);
270 if( conv->Opcode() != Op_ConvF2I ) { return false; }
271
272 // Check that shift amounts are only to get sign bits set after F2I
273 jint max_cutoff = max->get_int();
274 jint min_cutoff = min->get_int();
275 jint left_shift = lshift->in(2)->get_int();
276 jint right_shift = rshift->in(2)->get_int();
277 jint max_post_shift = nth_bit(BitsPerJavaInteger - left_shift - 1);
278 if( left_shift != right_shift ||
279 0 > left_shift || left_shift >= BitsPerJavaInteger ||
280 max_post_shift < max_cutoff ||
281 max_post_shift < -min_cutoff ) {
282 // Shifts are necessary but current transformation eliminates them
283 return false;
284 }
285
286 // OK to return the result of ConvF2I without shifting
287 convf2i = (ConvF2INode*)conv;
288 return true;
289 }
290
291
292 //------------------------------check_compare_clipping-------------------------
293 // Helper function for RegionNode's identification of FP clipping
294 static bool check_compare_clipping( bool less_than, IfNode *iff, ConNode *limit, Node * & input ) {
295 Node *i1 = iff->in(1);
296 if ( !i1->is_Bool() ) { return false; }
297 BoolNode *bool1 = i1->as_Bool();
298 if( less_than && bool1->_test._test != BoolTest::le ) { return false; }
299 else if( !less_than && bool1->_test._test != BoolTest::lt ) { return false; }
300 const Node *cmpF = bool1->in(1);
301 if( cmpF->Opcode() != Op_CmpF ) { return false; }
302 // Test that the float value being compared against
303 // is equivalent to the int value used as a limit
304 Node *nodef = cmpF->in(2);
305 if( nodef->Opcode() != Op_ConF ) { return false; }
306 jfloat conf = nodef->getf();
307 jint coni = limit->get_int();
308 if( ((int)conf) != coni ) { return false; }
309 input = cmpF->in(1);
310 return true;
311 }
312
313 //------------------------------is_unreachable_region--------------------------
314 // Find if the Region node is reachable from the root.
315 bool RegionNode::is_unreachable_region(PhaseGVN *phase) const {
316 assert(req() == 2, "");
317
318 // First, cut the simple case of fallthrough region when NONE of
319 // region's phis references itself directly or through a data node.
320 uint max = outcnt();
321 uint i;
322 for (i = 0; i < max; i++) {
323 Node* phi = raw_out(i);
324 if (phi != NULL && phi->is_Phi()) {
325 assert(phase->eqv(phi->in(0), this) && phi->req() == 2, "");
1088 // Check for a 2-path merge
1089 Node *region = in(0);
1090 if( !region ) return 0;
1091 if( region->req() != 3 ) return 0;
1092 if( req() != 3 ) return 0;
1093 // Check that both paths come from the same If
1094 Node *ifp1 = region->in(1);
1095 Node *ifp2 = region->in(2);
1096 if( !ifp1 || !ifp2 ) return 0;
1097 Node *iff = ifp1->in(0);
1098 if( !iff || !iff->is_If() ) return 0;
1099 if( iff != ifp2->in(0) ) return 0;
1100 if (check_control_only) return -1;
1101 // Check for a proper bool/cmp
1102 const Node *b = iff->in(1);
1103 if( !b->is_Bool() ) return 0;
1104 const Node *cmp = b->in(1);
1105 if( !cmp->is_Cmp() ) return 0;
1106
1107 // Check for branching opposite expected
1108 if( ifp2->Opcode() == Op_IfTrue ) {
1109 assert( ifp1->Opcode() == Op_IfFalse, "" );
1110 return 2;
1111 } else {
1112 assert( ifp1->Opcode() == Op_IfTrue, "" );
1113 return 1;
1114 }
1115 }
1116
1117 //----------------------------check_cmove_id-----------------------------------
1118 // Check for CMove'ing a constant after comparing against the constant.
1119 // Happens all the time now, since if we compare equality vs a constant in
1120 // the parser, we "know" the variable is constant on one path and we force
1121 // it. Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a
1122 // conditional move: "x = (x==0)?0:x;". Yucko. This fix is slightly more
1123 // general in that we don't need constants. Since CMove's are only inserted
1124 // in very special circumstances, we do it here on generic Phi's.
1125 Node* PhiNode::is_cmove_id(PhaseTransform* phase, int true_path) {
1126 assert(true_path !=0, "only diamond shape graph expected");
1127
1128 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1129 // phi->region->if_proj->ifnode->bool->cmp
1130 Node* region = in(0);
1131 Node* iff = region->in(1)->in(0);
1132 BoolNode* b = iff->in(1)->as_Bool();
1304 static Node* is_cond_add(PhaseGVN *phase, PhiNode *phi, int true_path) {
1305 assert(true_path !=0, "only diamond shape graph expected");
1306
1307 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1308 // phi->region->if_proj->ifnode->bool->cmp
1309 RegionNode *region = (RegionNode*)phi->in(0);
1310 Node *iff = region->in(1)->in(0);
1311 BoolNode* b = iff->in(1)->as_Bool();
1312 const CmpNode *cmp = (CmpNode*)b->in(1);
1313
1314 // Make sure only merging this one phi here
1315 if (region->has_unique_phi() != phi) return NULL;
1316
1317 // Make sure each arm of the diamond has exactly one output, which we assume
1318 // is the region. Otherwise, the control flow won't disappear.
1319 if (region->in(1)->outcnt() != 1) return NULL;
1320 if (region->in(2)->outcnt() != 1) return NULL;
1321
1322 // Check for "(P < Q)" of type signed int
1323 if (b->_test._test != BoolTest::lt) return NULL;
1324 if (cmp->Opcode() != Op_CmpI) return NULL;
1325
1326 Node *p = cmp->in(1);
1327 Node *q = cmp->in(2);
1328 Node *n1 = phi->in( true_path);
1329 Node *n2 = phi->in(3-true_path);
1330
1331 int op = n1->Opcode();
1332 if( op != Op_AddI // Need zero as additive identity
1333 /*&&op != Op_SubI &&
1334 op != Op_AddP &&
1335 op != Op_XorI &&
1336 op != Op_OrI*/ )
1337 return NULL;
1338
1339 Node *x = n2;
1340 Node *y = NULL;
1341 if( x == n1->in(1) ) {
1342 y = n1->in(2);
1343 } else if( x == n1->in(2) ) {
1344 y = n1->in(1);
1345 } else return NULL;
1346
1347 // Not so profitable if compare and add are constants
1348 if( q->is_Con() && phase->type(q) != TypeInt::ZERO && y->is_Con() )
1349 return NULL;
1350
1351 Node *cmplt = phase->transform( new CmpLTMaskNode(p,q) );
1352 Node *j_and = phase->transform( new AndINode(cmplt,y) );
1365 // Find the false path from the true path. With only 2 inputs, 3 - x works nicely.
1366 int false_path = 3 - true_path;
1367
1368 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1369 // phi->region->if_proj->ifnode->bool->cmp
1370 BoolNode *bol = phi_root->in(0)->in(1)->in(0)->in(1)->as_Bool();
1371
1372 // Check bool sense
1373 switch( bol->_test._test ) {
1374 case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = true_path; break;
1375 case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = false_path; break;
1376 case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = true_path; break;
1377 case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = false_path; break;
1378 default: return NULL; break;
1379 }
1380
1381 // Test is next
1382 Node *cmp = bol->in(1);
1383 const Type *tzero = NULL;
1384 switch( cmp->Opcode() ) {
1385 case Op_CmpF: tzero = TypeF::ZERO; break; // Float ABS
1386 case Op_CmpD: tzero = TypeD::ZERO; break; // Double ABS
1387 default: return NULL;
1388 }
1389
1390 // Find zero input of compare; the other input is being abs'd
1391 Node *x = NULL;
1392 bool flip = false;
1393 if( phase->type(cmp->in(cmp_zero_idx)) == tzero ) {
1394 x = cmp->in(3 - cmp_zero_idx);
1395 } else if( phase->type(cmp->in(3 - cmp_zero_idx)) == tzero ) {
1396 // The test is inverted, we should invert the result...
1397 x = cmp->in(cmp_zero_idx);
1398 flip = true;
1399 } else {
1400 return NULL;
1401 }
1402
1403 // Next get the 2 pieces being selected, one is the original value
1404 // and the other is the negated value.
1405 if( phi_root->in(phi_x_idx) != x ) return NULL;
1406
1407 // Check other phi input for subtract node
1408 Node *sub = phi_root->in(3 - phi_x_idx);
1409
1410 // Allow only Sub(0,X) and fail out for all others; Neg is not OK
1411 if( tzero == TypeF::ZERO ) {
1412 if( sub->Opcode() != Op_SubF ||
1413 sub->in(2) != x ||
1414 phase->type(sub->in(1)) != tzero ) return NULL;
1415 x = new AbsFNode(x);
1416 if (flip) {
1417 x = new SubFNode(sub->in(1), phase->transform(x));
1418 }
1419 } else {
1420 if( sub->Opcode() != Op_SubD ||
1421 sub->in(2) != x ||
1422 phase->type(sub->in(1)) != tzero ) return NULL;
1423 x = new AbsDNode(x);
1424 if (flip) {
1425 x = new SubDNode(sub->in(1), phase->transform(x));
1426 }
1427 }
1428
1429 return x;
1430 }
1431
1432 //------------------------------split_once-------------------------------------
1433 // Helper for split_flow_path
1434 static void split_once(PhaseIterGVN *igvn, Node *phi, Node *val, Node *n, Node *newn) {
1435 igvn->hash_delete(n); // Remove from hash before hacking edges
1436
1437 uint j = 1;
1438 for (uint i = phi->req()-1; i > 0; i--) {
1439 if (phi->in(i) == val) { // Found a path with val?
1440 // Add to NEW Region/Phi, no DU info
1451 // Now I can point to the new node.
1452 n->add_req(newn);
1453 igvn->_worklist.push(n);
1454 }
1455
1456 //------------------------------split_flow_path--------------------------------
1457 // Check for merging identical values and split flow paths
1458 static Node* split_flow_path(PhaseGVN *phase, PhiNode *phi) {
1459 BasicType bt = phi->type()->basic_type();
1460 if( bt == T_ILLEGAL || type2size[bt] <= 0 )
1461 return NULL; // Bail out on funny non-value stuff
1462 if( phi->req() <= 3 ) // Need at least 2 matched inputs and a
1463 return NULL; // third unequal input to be worth doing
1464
1465 // Scan for a constant
1466 uint i;
1467 for( i = 1; i < phi->req()-1; i++ ) {
1468 Node *n = phi->in(i);
1469 if( !n ) return NULL;
1470 if( phase->type(n) == Type::TOP ) return NULL;
1471 if( n->Opcode() == Op_ConP || n->Opcode() == Op_ConN || n->Opcode() == Op_ConNKlass )
1472 break;
1473 }
1474 if( i >= phi->req() ) // Only split for constants
1475 return NULL;
1476
1477 Node *val = phi->in(i); // Constant to split for
1478 uint hit = 0; // Number of times it occurs
1479 Node *r = phi->region();
1480
1481 for( ; i < phi->req(); i++ ){ // Count occurrences of constant
1482 Node *n = phi->in(i);
1483 if( !n ) return NULL;
1484 if( phase->type(n) == Type::TOP ) return NULL;
1485 if( phi->in(i) == val ) {
1486 hit++;
1487 if (PhaseIdealLoop::find_predicate(r->in(i)) != NULL) {
1488 return NULL; // don't split loop entry path
1489 }
1490 }
1491 }
1691 if (is_loop && !uin->eqv_uncast(in(LoopNode::EntryControl)) ||
1692 !is_loop && is_unsafe_data_reference(uin)) {
1693 // Break this data loop to avoid creation of a dead loop.
1694 if (can_reshape) {
1695 return top;
1696 } else {
1697 // We can't return top if we are in Parse phase - cut inputs only
1698 // let Identity to handle the case.
1699 replace_edge(uin, top);
1700 return NULL;
1701 }
1702 }
1703 }
1704
1705 if (uncasted) {
1706 // Add a cast node between the phi to be removed and its unique input.
1707 // Wait until after parsing for the type information to propagate from the casts.
1708 assert(can_reshape, "Invalid during parsing");
1709 const Type* phi_type = bottom_type();
1710 assert(phi_type->isa_int() || phi_type->isa_ptr(), "bad phi type");
1711 int opcode;
1712 // Determine the type of cast to be added.
1713 if (phi_type->isa_int()) {
1714 opcode = Op_CastII;
1715 } else {
1716 const Type* uin_type = phase->type(uin);
1717 if ((phi_type->join(TypePtr::NOTNULL) == uin_type->join(TypePtr::NOTNULL)) ||
1718 (!phi_type->isa_oopptr() && !uin_type->isa_oopptr())) {
1719 opcode = Op_CastPP;
1720 } else {
1721 opcode = Op_CheckCastPP;
1722 }
1723 }
1724 // Add a cast to carry the control dependency of the Phi that is
1725 // going away
1726 Node* cast = ConstraintCastNode::make_cast(opcode, r, uin, phi_type, true);
1727 cast = phase->transform(cast);
1728 // set all inputs to the new cast so the Phi is removed by Identity
1729 PhaseIterGVN* igvn = phase->is_IterGVN();
1730 for (uint i = 1; i < req(); i++) {
1731 set_req_X(i, cast, igvn);
1732 }
1733 uin = cast;
1734 }
1735
1736 // One unique input.
1737 debug_only(Node* ident = Identity(phase));
1738 // The unique input must eventually be detected by the Identity call.
1739 #ifdef ASSERT
1740 if (ident != uin && !ident->is_top()) {
1741 // print this output before failing assert
1780 // We can't return top if we are in Parse phase - cut inputs only
1781 // to stop further optimizations for this phi. Identity will return TOP.
1782 assert(req() == 3, "only diamond merge phi here");
1783 set_req(1, top);
1784 set_req(2, top);
1785 return NULL;
1786 } else {
1787 return opt;
1788 }
1789 }
1790 }
1791
1792 // Check for merging identical values and split flow paths
1793 if (can_reshape) {
1794 opt = split_flow_path(phase, this);
1795 // This optimization only modifies phi - don't need to check for dead loop.
1796 assert(opt == NULL || phase->eqv(opt, this), "do not elide phi");
1797 if (opt != NULL) return opt;
1798 }
1799
1800 if (in(1) != NULL && in(1)->Opcode() == Op_AddP && can_reshape) {
1801 // Try to undo Phi of AddP:
1802 // (Phi (AddP base base y) (AddP base2 base2 y))
1803 // becomes:
1804 // newbase := (Phi base base2)
1805 // (AddP newbase newbase y)
1806 //
1807 // This occurs as a result of unsuccessful split_thru_phi and
1808 // interferes with taking advantage of addressing modes. See the
1809 // clone_shift_expressions code in matcher.cpp
1810 Node* addp = in(1);
1811 const Type* type = addp->in(AddPNode::Base)->bottom_type();
1812 Node* y = addp->in(AddPNode::Offset);
1813 if (y != NULL && addp->in(AddPNode::Base) == addp->in(AddPNode::Address)) {
1814 // make sure that all the inputs are similar to the first one,
1815 // i.e. AddP with base == address and same offset as first AddP
1816 bool doit = true;
1817 for (uint i = 2; i < req(); i++) {
1818 if (in(i) == NULL ||
1819 in(i)->Opcode() != Op_AddP ||
1820 in(i)->in(AddPNode::Base) != in(i)->in(AddPNode::Address) ||
1821 in(i)->in(AddPNode::Offset) != y) {
1822 doit = false;
1823 break;
1824 }
1825 // Accumulate type for resulting Phi
1826 type = type->meet_speculative(in(i)->in(AddPNode::Base)->bottom_type());
1827 }
1828 Node* base = NULL;
1829 if (doit) {
1830 // Check for neighboring AddP nodes in a tree.
1831 // If they have a base, use that it.
1832 for (DUIterator_Fast kmax, k = this->fast_outs(kmax); k < kmax; k++) {
1833 Node* u = this->fast_out(k);
1834 if (u->is_AddP()) {
1835 Node* base2 = u->in(AddPNode::Base);
1836 if (base2 != NULL && !base2->is_top()) {
1837 if (base == NULL)
1838 base = base2;
1839 else if (base != base2)
2055 }
2056 }
2057 }
2058 #endif
2059
2060 return progress; // Return any progress
2061 }
2062
2063 //------------------------------is_tripcount-----------------------------------
2064 bool PhiNode::is_tripcount() const {
2065 return (in(0) != NULL && in(0)->is_CountedLoop() &&
2066 in(0)->as_CountedLoop()->phi() == this);
2067 }
2068
2069 //------------------------------out_RegMask------------------------------------
2070 const RegMask &PhiNode::in_RegMask(uint i) const {
2071 return i ? out_RegMask() : RegMask::Empty;
2072 }
2073
2074 const RegMask &PhiNode::out_RegMask() const {
2075 uint ideal_reg = _type->ideal_reg();
2076 assert( ideal_reg != Node::NotAMachineReg, "invalid type at Phi" );
2077 if( ideal_reg == 0 ) return RegMask::Empty;
2078 return *(Compile::current()->matcher()->idealreg2spillmask[ideal_reg]);
2079 }
2080
2081 #ifndef PRODUCT
2082 void PhiNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const {
2083 // For a PhiNode, the set of related nodes includes all inputs till level 2,
2084 // and all outputs till level 1. In compact mode, inputs till level 1 are
2085 // collected.
2086 this->collect_nodes(in_rel, compact ? 1 : 2, false, false);
2087 this->collect_nodes(out_rel, -1, false, false);
2088 }
2089
2090 void PhiNode::dump_spec(outputStream *st) const {
2091 TypeNode::dump_spec(st);
2092 if (is_tripcount()) {
2093 st->print(" #tripcount");
2094 }
2095 }
2096 #endif
2097
2098
|
55 if( !n ) continue; // Missing inputs are TOP
56 if( phase->type(n) == Type::CONTROL )
57 return Type::CONTROL;
58 }
59 return Type::TOP; // All paths dead? Then so are we
60 }
61
62 //------------------------------Identity---------------------------------------
63 // Check for Region being Identity.
64 Node* RegionNode::Identity(PhaseGVN* phase) {
65 // Cannot have Region be an identity, even if it has only 1 input.
66 // Phi users cannot have their Region input folded away for them,
67 // since they need to select the proper data input
68 return this;
69 }
70
71 //------------------------------merge_region-----------------------------------
72 // If a Region flows into a Region, merge into one big happy merge. This is
73 // hard to do if there is stuff that has to happen
74 static Node *merge_region(RegionNode *region, PhaseGVN *phase) {
75 if( region->Opcode() != Opcodes::Op_Region ) // Do not do to LoopNodes
76 return NULL;
77 Node *progress = NULL; // Progress flag
78 PhaseIterGVN *igvn = phase->is_IterGVN();
79
80 uint rreq = region->req();
81 for( uint i = 1; i < rreq; i++ ) {
82 Node *r = region->in(i);
83 if( r && r->Opcode() == Opcodes::Op_Region && // Found a region?
84 r->in(0) == r && // Not already collapsed?
85 r != region && // Avoid stupid situations
86 r->outcnt() == 2 ) { // Self user and 'region' user only?
87 assert(!r->as_Region()->has_phi(), "no phi users");
88 if( !progress ) { // No progress
89 if (region->has_phi()) {
90 return NULL; // Only flatten if no Phi users
91 // igvn->hash_delete( phi );
92 }
93 igvn->hash_delete( region );
94 progress = region; // Making progress
95 }
96 igvn->hash_delete( r );
97
98 // Append inputs to 'r' onto 'region'
99 for( uint j = 1; j < r->req(); j++ ) {
100 // Move an input from 'r' to 'region'
101 region->add_req(r->in(j));
102 r->set_req(j, phase->C->top());
103 // Update phis of 'region'
154 }
155
156 return only_phi;
157 }
158
159
160 //------------------------------check_phi_clipping-----------------------------
161 // Helper function for RegionNode's identification of FP clipping
162 // Check inputs to the Phi
163 static bool check_phi_clipping( PhiNode *phi, ConNode * &min, uint &min_idx, ConNode * &max, uint &max_idx, Node * &val, uint &val_idx ) {
164 min = NULL;
165 max = NULL;
166 val = NULL;
167 min_idx = 0;
168 max_idx = 0;
169 val_idx = 0;
170 uint phi_max = phi->req();
171 if( phi_max == 4 ) {
172 for( uint j = 1; j < phi_max; ++j ) {
173 Node *n = phi->in(j);
174 Opcodes opcode = n->Opcode();
175 switch( opcode ) {
176 case Opcodes::Op_ConI:
177 {
178 if( min == NULL ) {
179 min = n->Opcode() == Opcodes::Op_ConI ? (ConNode*)n : NULL;
180 min_idx = j;
181 } else {
182 max = n->Opcode() == Opcodes::Op_ConI ? (ConNode*)n : NULL;
183 max_idx = j;
184 if( min->get_int() > max->get_int() ) {
185 // Swap min and max
186 ConNode *temp;
187 uint temp_idx;
188 temp = min; min = max; max = temp;
189 temp_idx = min_idx; min_idx = max_idx; max_idx = temp_idx;
190 }
191 }
192 }
193 break;
194 default:
195 {
196 val = n;
197 val_idx = j;
198 }
199 break;
200 }
201 }
202 }
241 // Control pattern checks
242 top_if = (IfNode*)in1000;
243 bot_if = (IfNode*)in10;
244 }
245 }
246 }
247
248 return (top_if != NULL);
249 }
250
251
252 //------------------------------check_convf2i_clipping-------------------------
253 // Helper function for RegionNode's identification of FP clipping
254 // Verify that the value input to the phi comes from "ConvF2I; LShift; RShift"
255 static bool check_convf2i_clipping( PhiNode *phi, uint idx, ConvF2INode * &convf2i, Node *min, Node *max) {
256 convf2i = NULL;
257
258 // Check for the RShiftNode
259 Node *rshift = phi->in(idx);
260 assert( rshift, "Previous checks ensure phi input is present");
261 if( rshift->Opcode() != Opcodes::Op_RShiftI ) { return false; }
262
263 // Check for the LShiftNode
264 Node *lshift = rshift->in(1);
265 assert( lshift, "Previous checks ensure phi input is present");
266 if( lshift->Opcode() != Opcodes::Op_LShiftI ) { return false; }
267
268 // Check for the ConvF2INode
269 Node *conv = lshift->in(1);
270 if( conv->Opcode() != Opcodes::Op_ConvF2I ) { return false; }
271
272 // Check that shift amounts are only to get sign bits set after F2I
273 jint max_cutoff = max->get_int();
274 jint min_cutoff = min->get_int();
275 jint left_shift = lshift->in(2)->get_int();
276 jint right_shift = rshift->in(2)->get_int();
277 jint max_post_shift = nth_bit(BitsPerJavaInteger - left_shift - 1);
278 if( left_shift != right_shift ||
279 0 > left_shift || left_shift >= BitsPerJavaInteger ||
280 max_post_shift < max_cutoff ||
281 max_post_shift < -min_cutoff ) {
282 // Shifts are necessary but current transformation eliminates them
283 return false;
284 }
285
286 // OK to return the result of ConvF2I without shifting
287 convf2i = (ConvF2INode*)conv;
288 return true;
289 }
290
291
292 //------------------------------check_compare_clipping-------------------------
293 // Helper function for RegionNode's identification of FP clipping
294 static bool check_compare_clipping( bool less_than, IfNode *iff, ConNode *limit, Node * & input ) {
295 Node *i1 = iff->in(1);
296 if ( !i1->is_Bool() ) { return false; }
297 BoolNode *bool1 = i1->as_Bool();
298 if( less_than && bool1->_test._test != BoolTest::le ) { return false; }
299 else if( !less_than && bool1->_test._test != BoolTest::lt ) { return false; }
300 const Node *cmpF = bool1->in(1);
301 if( cmpF->Opcode() != Opcodes::Op_CmpF ) { return false; }
302 // Test that the float value being compared against
303 // is equivalent to the int value used as a limit
304 Node *nodef = cmpF->in(2);
305 if( nodef->Opcode() != Opcodes::Op_ConF ) { return false; }
306 jfloat conf = nodef->getf();
307 jint coni = limit->get_int();
308 if( ((int)conf) != coni ) { return false; }
309 input = cmpF->in(1);
310 return true;
311 }
312
313 //------------------------------is_unreachable_region--------------------------
314 // Find if the Region node is reachable from the root.
315 bool RegionNode::is_unreachable_region(PhaseGVN *phase) const {
316 assert(req() == 2, "");
317
318 // First, cut the simple case of fallthrough region when NONE of
319 // region's phis references itself directly or through a data node.
320 uint max = outcnt();
321 uint i;
322 for (i = 0; i < max; i++) {
323 Node* phi = raw_out(i);
324 if (phi != NULL && phi->is_Phi()) {
325 assert(phase->eqv(phi->in(0), this) && phi->req() == 2, "");
1088 // Check for a 2-path merge
1089 Node *region = in(0);
1090 if( !region ) return 0;
1091 if( region->req() != 3 ) return 0;
1092 if( req() != 3 ) return 0;
1093 // Check that both paths come from the same If
1094 Node *ifp1 = region->in(1);
1095 Node *ifp2 = region->in(2);
1096 if( !ifp1 || !ifp2 ) return 0;
1097 Node *iff = ifp1->in(0);
1098 if( !iff || !iff->is_If() ) return 0;
1099 if( iff != ifp2->in(0) ) return 0;
1100 if (check_control_only) return -1;
1101 // Check for a proper bool/cmp
1102 const Node *b = iff->in(1);
1103 if( !b->is_Bool() ) return 0;
1104 const Node *cmp = b->in(1);
1105 if( !cmp->is_Cmp() ) return 0;
1106
1107 // Check for branching opposite expected
1108 if( ifp2->Opcode() == Opcodes::Op_IfTrue ) {
1109 assert( ifp1->Opcode() == Opcodes::Op_IfFalse, "" );
1110 return 2;
1111 } else {
1112 assert( ifp1->Opcode() == Opcodes::Op_IfTrue, "" );
1113 return 1;
1114 }
1115 }
1116
1117 //----------------------------check_cmove_id-----------------------------------
1118 // Check for CMove'ing a constant after comparing against the constant.
1119 // Happens all the time now, since if we compare equality vs a constant in
1120 // the parser, we "know" the variable is constant on one path and we force
1121 // it. Thus code like "if( x==0 ) {/*EMPTY*/}" ends up inserting a
1122 // conditional move: "x = (x==0)?0:x;". Yucko. This fix is slightly more
1123 // general in that we don't need constants. Since CMove's are only inserted
1124 // in very special circumstances, we do it here on generic Phi's.
1125 Node* PhiNode::is_cmove_id(PhaseTransform* phase, int true_path) {
1126 assert(true_path !=0, "only diamond shape graph expected");
1127
1128 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1129 // phi->region->if_proj->ifnode->bool->cmp
1130 Node* region = in(0);
1131 Node* iff = region->in(1)->in(0);
1132 BoolNode* b = iff->in(1)->as_Bool();
1304 static Node* is_cond_add(PhaseGVN *phase, PhiNode *phi, int true_path) {
1305 assert(true_path !=0, "only diamond shape graph expected");
1306
1307 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1308 // phi->region->if_proj->ifnode->bool->cmp
1309 RegionNode *region = (RegionNode*)phi->in(0);
1310 Node *iff = region->in(1)->in(0);
1311 BoolNode* b = iff->in(1)->as_Bool();
1312 const CmpNode *cmp = (CmpNode*)b->in(1);
1313
1314 // Make sure only merging this one phi here
1315 if (region->has_unique_phi() != phi) return NULL;
1316
1317 // Make sure each arm of the diamond has exactly one output, which we assume
1318 // is the region. Otherwise, the control flow won't disappear.
1319 if (region->in(1)->outcnt() != 1) return NULL;
1320 if (region->in(2)->outcnt() != 1) return NULL;
1321
1322 // Check for "(P < Q)" of type signed int
1323 if (b->_test._test != BoolTest::lt) return NULL;
1324 if (cmp->Opcode() != Opcodes::Op_CmpI) return NULL;
1325
1326 Node *p = cmp->in(1);
1327 Node *q = cmp->in(2);
1328 Node *n1 = phi->in( true_path);
1329 Node *n2 = phi->in(3-true_path);
1330
1331 Opcodes op = n1->Opcode();
1332 if( op != Opcodes::Op_AddI // Need zero as additive identity
1333 /*&&op != Op_SubI &&
1334 op != Op_AddP &&
1335 op != Op_XorI &&
1336 op != Op_OrI*/ )
1337 return NULL;
1338
1339 Node *x = n2;
1340 Node *y = NULL;
1341 if( x == n1->in(1) ) {
1342 y = n1->in(2);
1343 } else if( x == n1->in(2) ) {
1344 y = n1->in(1);
1345 } else return NULL;
1346
1347 // Not so profitable if compare and add are constants
1348 if( q->is_Con() && phase->type(q) != TypeInt::ZERO && y->is_Con() )
1349 return NULL;
1350
1351 Node *cmplt = phase->transform( new CmpLTMaskNode(p,q) );
1352 Node *j_and = phase->transform( new AndINode(cmplt,y) );
1365 // Find the false path from the true path. With only 2 inputs, 3 - x works nicely.
1366 int false_path = 3 - true_path;
1367
1368 // is_diamond_phi() has guaranteed the correctness of the nodes sequence:
1369 // phi->region->if_proj->ifnode->bool->cmp
1370 BoolNode *bol = phi_root->in(0)->in(1)->in(0)->in(1)->as_Bool();
1371
1372 // Check bool sense
1373 switch( bol->_test._test ) {
1374 case BoolTest::lt: cmp_zero_idx = 1; phi_x_idx = true_path; break;
1375 case BoolTest::le: cmp_zero_idx = 2; phi_x_idx = false_path; break;
1376 case BoolTest::gt: cmp_zero_idx = 2; phi_x_idx = true_path; break;
1377 case BoolTest::ge: cmp_zero_idx = 1; phi_x_idx = false_path; break;
1378 default: return NULL; break;
1379 }
1380
1381 // Test is next
1382 Node *cmp = bol->in(1);
1383 const Type *tzero = NULL;
1384 switch( cmp->Opcode() ) {
1385 case Opcodes::Op_CmpF: tzero = TypeF::ZERO; break; // Float ABS
1386 case Opcodes::Op_CmpD: tzero = TypeD::ZERO; break; // Double ABS
1387 default: return NULL;
1388 }
1389
1390 // Find zero input of compare; the other input is being abs'd
1391 Node *x = NULL;
1392 bool flip = false;
1393 if( phase->type(cmp->in(cmp_zero_idx)) == tzero ) {
1394 x = cmp->in(3 - cmp_zero_idx);
1395 } else if( phase->type(cmp->in(3 - cmp_zero_idx)) == tzero ) {
1396 // The test is inverted, we should invert the result...
1397 x = cmp->in(cmp_zero_idx);
1398 flip = true;
1399 } else {
1400 return NULL;
1401 }
1402
1403 // Next get the 2 pieces being selected, one is the original value
1404 // and the other is the negated value.
1405 if( phi_root->in(phi_x_idx) != x ) return NULL;
1406
1407 // Check other phi input for subtract node
1408 Node *sub = phi_root->in(3 - phi_x_idx);
1409
1410 // Allow only Sub(0,X) and fail out for all others; Neg is not OK
1411 if( tzero == TypeF::ZERO ) {
1412 if( sub->Opcode() != Opcodes::Op_SubF ||
1413 sub->in(2) != x ||
1414 phase->type(sub->in(1)) != tzero ) return NULL;
1415 x = new AbsFNode(x);
1416 if (flip) {
1417 x = new SubFNode(sub->in(1), phase->transform(x));
1418 }
1419 } else {
1420 if( sub->Opcode() != Opcodes::Op_SubD ||
1421 sub->in(2) != x ||
1422 phase->type(sub->in(1)) != tzero ) return NULL;
1423 x = new AbsDNode(x);
1424 if (flip) {
1425 x = new SubDNode(sub->in(1), phase->transform(x));
1426 }
1427 }
1428
1429 return x;
1430 }
1431
1432 //------------------------------split_once-------------------------------------
1433 // Helper for split_flow_path
1434 static void split_once(PhaseIterGVN *igvn, Node *phi, Node *val, Node *n, Node *newn) {
1435 igvn->hash_delete(n); // Remove from hash before hacking edges
1436
1437 uint j = 1;
1438 for (uint i = phi->req()-1; i > 0; i--) {
1439 if (phi->in(i) == val) { // Found a path with val?
1440 // Add to NEW Region/Phi, no DU info
1451 // Now I can point to the new node.
1452 n->add_req(newn);
1453 igvn->_worklist.push(n);
1454 }
1455
1456 //------------------------------split_flow_path--------------------------------
1457 // Check for merging identical values and split flow paths
1458 static Node* split_flow_path(PhaseGVN *phase, PhiNode *phi) {
1459 BasicType bt = phi->type()->basic_type();
1460 if( bt == T_ILLEGAL || type2size[bt] <= 0 )
1461 return NULL; // Bail out on funny non-value stuff
1462 if( phi->req() <= 3 ) // Need at least 2 matched inputs and a
1463 return NULL; // third unequal input to be worth doing
1464
1465 // Scan for a constant
1466 uint i;
1467 for( i = 1; i < phi->req()-1; i++ ) {
1468 Node *n = phi->in(i);
1469 if( !n ) return NULL;
1470 if( phase->type(n) == Type::TOP ) return NULL;
1471 if( n->Opcode() == Opcodes::Op_ConP || n->Opcode() == Opcodes::Op_ConN || n->Opcode() == Opcodes::Op_ConNKlass )
1472 break;
1473 }
1474 if( i >= phi->req() ) // Only split for constants
1475 return NULL;
1476
1477 Node *val = phi->in(i); // Constant to split for
1478 uint hit = 0; // Number of times it occurs
1479 Node *r = phi->region();
1480
1481 for( ; i < phi->req(); i++ ){ // Count occurrences of constant
1482 Node *n = phi->in(i);
1483 if( !n ) return NULL;
1484 if( phase->type(n) == Type::TOP ) return NULL;
1485 if( phi->in(i) == val ) {
1486 hit++;
1487 if (PhaseIdealLoop::find_predicate(r->in(i)) != NULL) {
1488 return NULL; // don't split loop entry path
1489 }
1490 }
1491 }
1691 if (is_loop && !uin->eqv_uncast(in(LoopNode::EntryControl)) ||
1692 !is_loop && is_unsafe_data_reference(uin)) {
1693 // Break this data loop to avoid creation of a dead loop.
1694 if (can_reshape) {
1695 return top;
1696 } else {
1697 // We can't return top if we are in Parse phase - cut inputs only
1698 // let Identity to handle the case.
1699 replace_edge(uin, top);
1700 return NULL;
1701 }
1702 }
1703 }
1704
1705 if (uncasted) {
1706 // Add a cast node between the phi to be removed and its unique input.
1707 // Wait until after parsing for the type information to propagate from the casts.
1708 assert(can_reshape, "Invalid during parsing");
1709 const Type* phi_type = bottom_type();
1710 assert(phi_type->isa_int() || phi_type->isa_ptr(), "bad phi type");
1711 Opcodes opcode;
1712 // Determine the type of cast to be added.
1713 if (phi_type->isa_int()) {
1714 opcode = Opcodes::Op_CastII;
1715 } else {
1716 const Type* uin_type = phase->type(uin);
1717 if ((phi_type->join(TypePtr::NOTNULL) == uin_type->join(TypePtr::NOTNULL)) ||
1718 (!phi_type->isa_oopptr() && !uin_type->isa_oopptr())) {
1719 opcode = Opcodes::Op_CastPP;
1720 } else {
1721 opcode = Opcodes::Op_CheckCastPP;
1722 }
1723 }
1724 // Add a cast to carry the control dependency of the Phi that is
1725 // going away
1726 Node* cast = ConstraintCastNode::make_cast(opcode, r, uin, phi_type, true);
1727 cast = phase->transform(cast);
1728 // set all inputs to the new cast so the Phi is removed by Identity
1729 PhaseIterGVN* igvn = phase->is_IterGVN();
1730 for (uint i = 1; i < req(); i++) {
1731 set_req_X(i, cast, igvn);
1732 }
1733 uin = cast;
1734 }
1735
1736 // One unique input.
1737 debug_only(Node* ident = Identity(phase));
1738 // The unique input must eventually be detected by the Identity call.
1739 #ifdef ASSERT
1740 if (ident != uin && !ident->is_top()) {
1741 // print this output before failing assert
1780 // We can't return top if we are in Parse phase - cut inputs only
1781 // to stop further optimizations for this phi. Identity will return TOP.
1782 assert(req() == 3, "only diamond merge phi here");
1783 set_req(1, top);
1784 set_req(2, top);
1785 return NULL;
1786 } else {
1787 return opt;
1788 }
1789 }
1790 }
1791
1792 // Check for merging identical values and split flow paths
1793 if (can_reshape) {
1794 opt = split_flow_path(phase, this);
1795 // This optimization only modifies phi - don't need to check for dead loop.
1796 assert(opt == NULL || phase->eqv(opt, this), "do not elide phi");
1797 if (opt != NULL) return opt;
1798 }
1799
1800 if (in(1) != NULL && in(1)->Opcode() == Opcodes::Op_AddP && can_reshape) {
1801 // Try to undo Phi of AddP:
1802 // (Phi (AddP base base y) (AddP base2 base2 y))
1803 // becomes:
1804 // newbase := (Phi base base2)
1805 // (AddP newbase newbase y)
1806 //
1807 // This occurs as a result of unsuccessful split_thru_phi and
1808 // interferes with taking advantage of addressing modes. See the
1809 // clone_shift_expressions code in matcher.cpp
1810 Node* addp = in(1);
1811 const Type* type = addp->in(AddPNode::Base)->bottom_type();
1812 Node* y = addp->in(AddPNode::Offset);
1813 if (y != NULL && addp->in(AddPNode::Base) == addp->in(AddPNode::Address)) {
1814 // make sure that all the inputs are similar to the first one,
1815 // i.e. AddP with base == address and same offset as first AddP
1816 bool doit = true;
1817 for (uint i = 2; i < req(); i++) {
1818 if (in(i) == NULL ||
1819 in(i)->Opcode() != Opcodes::Op_AddP ||
1820 in(i)->in(AddPNode::Base) != in(i)->in(AddPNode::Address) ||
1821 in(i)->in(AddPNode::Offset) != y) {
1822 doit = false;
1823 break;
1824 }
1825 // Accumulate type for resulting Phi
1826 type = type->meet_speculative(in(i)->in(AddPNode::Base)->bottom_type());
1827 }
1828 Node* base = NULL;
1829 if (doit) {
1830 // Check for neighboring AddP nodes in a tree.
1831 // If they have a base, use that it.
1832 for (DUIterator_Fast kmax, k = this->fast_outs(kmax); k < kmax; k++) {
1833 Node* u = this->fast_out(k);
1834 if (u->is_AddP()) {
1835 Node* base2 = u->in(AddPNode::Base);
1836 if (base2 != NULL && !base2->is_top()) {
1837 if (base == NULL)
1838 base = base2;
1839 else if (base != base2)
2055 }
2056 }
2057 }
2058 #endif
2059
2060 return progress; // Return any progress
2061 }
2062
2063 //------------------------------is_tripcount-----------------------------------
2064 bool PhiNode::is_tripcount() const {
2065 return (in(0) != NULL && in(0)->is_CountedLoop() &&
2066 in(0)->as_CountedLoop()->phi() == this);
2067 }
2068
2069 //------------------------------out_RegMask------------------------------------
2070 const RegMask &PhiNode::in_RegMask(uint i) const {
2071 return i ? out_RegMask() : RegMask::Empty;
2072 }
2073
2074 const RegMask &PhiNode::out_RegMask() const {
2075 Opcodes ideal_reg = _type->ideal_reg();
2076 assert( ideal_reg != Opcodes::NotAMachineReg, "invalid type at Phi" );
2077 if( ideal_reg == Opcodes::Op_Node ) return RegMask::Empty;
2078 return *(Compile::current()->matcher()->idealreg2spillmask[static_cast<uint>(ideal_reg)]);
2079 }
2080
2081 #ifndef PRODUCT
2082 void PhiNode::related(GrowableArray<Node*> *in_rel, GrowableArray<Node*> *out_rel, bool compact) const {
2083 // For a PhiNode, the set of related nodes includes all inputs till level 2,
2084 // and all outputs till level 1. In compact mode, inputs till level 1 are
2085 // collected.
2086 this->collect_nodes(in_rel, compact ? 1 : 2, false, false);
2087 this->collect_nodes(out_rel, -1, false, false);
2088 }
2089
2090 void PhiNode::dump_spec(outputStream *st) const {
2091 TypeNode::dump_spec(st);
2092 if (is_tripcount()) {
2093 st->print(" #tripcount");
2094 }
2095 }
2096 #endif
2097
2098
|