39 //------------------------------split_thru_phi---------------------------------
40 // Split Node 'n' through merge point if there is enough win.
41 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
42 if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
43 // ConvI2L may have type information on it which is unsafe to push up
44 // so disable this for now
45 return NULL;
46 }
47
48 int wins = 0;
49 assert(!n->is_CFG(), "");
50 assert(region->is_Region(), "");
51
52 const Type* type = n->bottom_type();
53 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
54 Node *phi;
55 if (t_oop != NULL && t_oop->is_known_instance_field()) {
56 int iid = t_oop->instance_id();
57 int index = C->get_alias_index(t_oop);
58 int offset = t_oop->offset();
59 phi = new (C) PhiNode(region, type, NULL, iid, index, offset);
60 } else {
61 phi = PhiNode::make_blank(region, n);
62 }
63 uint old_unique = C->unique();
64 for (uint i = 1; i < region->req(); i++) {
65 Node *x;
66 Node* the_clone = NULL;
67 if (region->in(i) == C->top()) {
68 x = C->top(); // Dead path? Use a dead data op
69 } else {
70 x = n->clone(); // Else clone up the data op
71 the_clone = x; // Remember for possible deletion.
72 // Alter data node to use pre-phi inputs
73 if (n->in(0) == region)
74 x->set_req( 0, region->in(i) );
75 for (uint j = 1; j < n->req(); j++) {
76 Node *in = n->in(j);
77 if (in->is_Phi() && in->in(0) == region)
78 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone
79 }
346 Node *scale = n->in(2);
347 Node *scale_ctrl = get_ctrl(scale);
348 IdealLoopTree *scale_loop = get_loop(scale_ctrl );
349 if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) )
350 return NULL;
351 const TypeInt *scale_t = scale->bottom_type()->isa_int();
352 if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 )
353 return NULL; // Dont bother with byte/short masking
354 // Add must vary with loop (else shift would be loop-invariant)
355 Node *add = n->in(1);
356 Node *add_ctrl = get_ctrl(add);
357 IdealLoopTree *add_loop = get_loop(add_ctrl);
358 //assert( n_loop == add_loop, "" );
359 if( n_loop != add_loop ) return NULL; // happens w/ evil ZKM loops
360
361 // Convert I-V into I+ (0-V); same for V-I
362 if( add->Opcode() == Op_SubI &&
363 _igvn.type( add->in(1) ) != TypeInt::ZERO ) {
364 Node *zero = _igvn.intcon(0);
365 set_ctrl(zero, C->root());
366 Node *neg = new (C) SubINode( _igvn.intcon(0), add->in(2) );
367 register_new_node( neg, get_ctrl(add->in(2) ) );
368 add = new (C) AddINode( add->in(1), neg );
369 register_new_node( add, add_ctrl );
370 }
371 if( add->Opcode() != Op_AddI ) return NULL;
372 // See if one add input is loop invariant
373 Node *add_var = add->in(1);
374 Node *add_var_ctrl = get_ctrl(add_var);
375 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
376 Node *add_invar = add->in(2);
377 Node *add_invar_ctrl = get_ctrl(add_invar);
378 IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl );
379 if( add_var_loop == n_loop ) {
380 } else if( add_invar_loop == n_loop ) {
381 // Swap to find the invariant part
382 add_invar = add_var;
383 add_invar_ctrl = add_var_ctrl;
384 add_invar_loop = add_var_loop;
385 add_var = add->in(2);
386 Node *add_var_ctrl = get_ctrl(add_var);
387 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
388 } else // Else neither input is loop invariant
389 return NULL;
390 if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) )
391 return NULL; // No invariant part of the add?
392
393 // Yes! Reshape address expression!
394 Node *inv_scale = new (C) LShiftINode( add_invar, scale );
395 Node *inv_scale_ctrl =
396 dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ?
397 add_invar_ctrl : scale_ctrl;
398 register_new_node( inv_scale, inv_scale_ctrl );
399 Node *var_scale = new (C) LShiftINode( add_var, scale );
400 register_new_node( var_scale, n_ctrl );
401 Node *var_add = new (C) AddINode( var_scale, inv_scale );
402 register_new_node( var_add, n_ctrl );
403 _igvn.replace_node( n, var_add );
404 return var_add;
405 }
406
407 // Replace (I+V) with (V+I)
408 if( n_op == Op_AddI ||
409 n_op == Op_AddL ||
410 n_op == Op_AddF ||
411 n_op == Op_AddD ||
412 n_op == Op_MulI ||
413 n_op == Op_MulL ||
414 n_op == Op_MulF ||
415 n_op == Op_MulD ) {
416 if( n2_loop == n_loop ) {
417 assert( n1_loop != n_loop, "" );
418 n->swap_edges(1, 2);
419 }
420 }
421
422 // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V),
423 // but not if I2 is a constant.
424 if( n_op == Op_AddP ) {
425 if( n2_loop == n_loop && n3_loop != n_loop ) {
426 if( n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con() ) {
427 Node *n22_ctrl = get_ctrl(n->in(2)->in(2));
428 Node *n23_ctrl = get_ctrl(n->in(2)->in(3));
429 IdealLoopTree *n22loop = get_loop( n22_ctrl );
430 IdealLoopTree *n23_loop = get_loop( n23_ctrl );
431 if( n22loop != n_loop && n22loop->is_member(n_loop) &&
432 n23_loop == n_loop ) {
433 Node *add1 = new (C) AddPNode( n->in(1), n->in(2)->in(2), n->in(3) );
434 // Stuff new AddP in the loop preheader
435 register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
436 Node *add2 = new (C) AddPNode( n->in(1), add1, n->in(2)->in(3) );
437 register_new_node( add2, n_ctrl );
438 _igvn.replace_node( n, add2 );
439 return add2;
440 }
441 }
442 }
443
444 // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V)
445 if( n2_loop != n_loop && n3_loop == n_loop ) {
446 if( n->in(3)->Opcode() == Op_AddI ) {
447 Node *V = n->in(3)->in(1);
448 Node *I = n->in(3)->in(2);
449 if( is_member(n_loop,get_ctrl(V)) ) {
450 } else {
451 Node *tmp = V; V = I; I = tmp;
452 }
453 if( !is_member(n_loop,get_ctrl(I)) ) {
454 Node *add1 = new (C) AddPNode( n->in(1), n->in(2), I );
455 // Stuff new AddP in the loop preheader
456 register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
457 Node *add2 = new (C) AddPNode( n->in(1), add1, V );
458 register_new_node( add2, n_ctrl );
459 _igvn.replace_node( n, add2 );
460 return add2;
461 }
462 }
463 }
464 }
465
466 return NULL;
467 }
468
469 //------------------------------conditional_move-------------------------------
470 // Attempt to replace a Phi with a conditional move. We have some pretty
471 // strict profitability requirements. All Phis at the merge point must
472 // be converted, so we can remove the control flow. We need to limit the
473 // number of c-moves to a small handful. All code that was in the side-arms
474 // of the CFG diamond is now speculatively executed. This code has to be
475 // "cheap enough". We are pretty much limited to CFG diamonds that merge
476 // 1 or 2 items with a total of 1 or 2 ops executed speculatively.
477 Node *PhaseIdealLoop::conditional_move( Node *region ) {
1087 // "Nearly" because all Nodes have been cloned from the original in the loop,
1088 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1089 // through the Phi recursively, and return a Bool.
1090 BoolNode *PhaseIdealLoop::clone_iff( PhiNode *phi, IdealLoopTree *loop ) {
1091
1092 // Convert this Phi into a Phi merging Bools
1093 uint i;
1094 for( i = 1; i < phi->req(); i++ ) {
1095 Node *b = phi->in(i);
1096 if( b->is_Phi() ) {
1097 _igvn.replace_input_of(phi, i, clone_iff( b->as_Phi(), loop ));
1098 } else {
1099 assert( b->is_Bool(), "" );
1100 }
1101 }
1102
1103 Node *sample_bool = phi->in(1);
1104 Node *sample_cmp = sample_bool->in(1);
1105
1106 // Make Phis to merge the Cmp's inputs.
1107 PhiNode *phi1 = new (C) PhiNode( phi->in(0), Type::TOP );
1108 PhiNode *phi2 = new (C) PhiNode( phi->in(0), Type::TOP );
1109 for( i = 1; i < phi->req(); i++ ) {
1110 Node *n1 = phi->in(i)->in(1)->in(1);
1111 Node *n2 = phi->in(i)->in(1)->in(2);
1112 phi1->set_req( i, n1 );
1113 phi2->set_req( i, n2 );
1114 phi1->set_type( phi1->type()->meet_speculative(n1->bottom_type()));
1115 phi2->set_type( phi2->type()->meet_speculative(n2->bottom_type()));
1116 }
1117 // See if these Phis have been made before.
1118 // Register with optimizer
1119 Node *hit1 = _igvn.hash_find_insert(phi1);
1120 if( hit1 ) { // Hit, toss just made Phi
1121 _igvn.remove_dead_node(phi1); // Remove new phi
1122 assert( hit1->is_Phi(), "" );
1123 phi1 = (PhiNode*)hit1; // Use existing phi
1124 } else { // Miss
1125 _igvn.register_new_node_with_optimizer(phi1);
1126 }
1127 Node *hit2 = _igvn.hash_find_insert(phi2);
1128 if( hit2 ) { // Hit, toss just made Phi
1155 //------------------------------clone_bool-------------------------------------
1156 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1157 // "Nearly" because all Nodes have been cloned from the original in the loop,
1158 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1159 // through the Phi recursively, and return a Bool.
1160 CmpNode *PhaseIdealLoop::clone_bool( PhiNode *phi, IdealLoopTree *loop ) {
1161 uint i;
1162 // Convert this Phi into a Phi merging Bools
1163 for( i = 1; i < phi->req(); i++ ) {
1164 Node *b = phi->in(i);
1165 if( b->is_Phi() ) {
1166 _igvn.replace_input_of(phi, i, clone_bool( b->as_Phi(), loop ));
1167 } else {
1168 assert( b->is_Cmp() || b->is_top(), "inputs are all Cmp or TOP" );
1169 }
1170 }
1171
1172 Node *sample_cmp = phi->in(1);
1173
1174 // Make Phis to merge the Cmp's inputs.
1175 PhiNode *phi1 = new (C) PhiNode( phi->in(0), Type::TOP );
1176 PhiNode *phi2 = new (C) PhiNode( phi->in(0), Type::TOP );
1177 for( uint j = 1; j < phi->req(); j++ ) {
1178 Node *cmp_top = phi->in(j); // Inputs are all Cmp or TOP
1179 Node *n1, *n2;
1180 if( cmp_top->is_Cmp() ) {
1181 n1 = cmp_top->in(1);
1182 n2 = cmp_top->in(2);
1183 } else {
1184 n1 = n2 = cmp_top;
1185 }
1186 phi1->set_req( j, n1 );
1187 phi2->set_req( j, n2 );
1188 phi1->set_type(phi1->type()->meet_speculative(n1->bottom_type()));
1189 phi2->set_type(phi2->type()->meet_speculative(n2->bottom_type()));
1190 }
1191
1192 // See if these Phis have been made before.
1193 // Register with optimizer
1194 Node *hit1 = _igvn.hash_find_insert(phi1);
1195 if( hit1 ) { // Hit, toss just made Phi
1196 _igvn.remove_dead_node(phi1); // Remove new phi
1320 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
1321 worklist.push(old->fast_out(j));
1322
1323 while( worklist.size() ) { // Visit all uses
1324 Node *use = worklist.pop();
1325 if (!has_node(use)) continue; // Ignore dead nodes
1326 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
1327 if( !loop->is_member( use_loop ) && use->is_CFG() ) {
1328 // Both OLD and USE are CFG nodes here.
1329 assert( use->is_Proj(), "" );
1330
1331 // Clone the loop exit control projection
1332 Node *newuse = use->clone();
1333 newuse->set_req(0,nnn);
1334 _igvn.register_new_node_with_optimizer(newuse);
1335 set_loop(newuse, use_loop);
1336 set_idom(newuse, nnn, dom_depth(nnn) + 1 );
1337
1338 // We need a Region to merge the exit from the peeled body and the
1339 // exit from the old loop body.
1340 RegionNode *r = new (C) RegionNode(3);
1341 // Map the old use to the new merge point
1342 old_new.map( use->_idx, r );
1343 uint dd_r = MIN2(dom_depth(newuse),dom_depth(use));
1344 assert( dd_r >= dom_depth(dom_lca(newuse,use)), "" );
1345
1346 // The original user of 'use' uses 'r' instead.
1347 for (DUIterator_Last lmin, l = use->last_outs(lmin); l >= lmin;) {
1348 Node* useuse = use->last_out(l);
1349 _igvn.rehash_node_delayed(useuse);
1350 uint uses_found = 0;
1351 if( useuse->in(0) == use ) {
1352 useuse->set_req(0, r);
1353 uses_found++;
1354 if( useuse->is_CFG() ) {
1355 assert( dom_depth(useuse) > dd_r, "" );
1356 set_idom(useuse, r, dom_depth(useuse));
1357 }
1358 }
1359 for( uint k = 1; k < useuse->req(); k++ ) {
1360 if( useuse->in(k) == use ) {
1667 // other-proj v
1668 // * new_if(relop(cmp[IU](left,right)))
1669 // / \
1670 // v v
1671 // * new-proj proj
1672 // (returned)
1673 //
1674 ProjNode* PhaseIdealLoop::insert_if_before_proj(Node* left, bool Signed, BoolTest::mask relop, Node* right, ProjNode* proj) {
1675 IfNode* iff = proj->in(0)->as_If();
1676 IdealLoopTree *loop = get_loop(proj);
1677 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
1678 int ddepth = dom_depth(proj);
1679
1680 _igvn.rehash_node_delayed(iff);
1681 _igvn.rehash_node_delayed(proj);
1682
1683 proj->set_req(0, NULL); // temporary disconnect
1684 ProjNode* proj2 = proj_clone(proj, iff);
1685 register_node(proj2, loop, iff, ddepth);
1686
1687 Node* cmp = Signed ? (Node*) new (C)CmpINode(left, right) : (Node*) new (C)CmpUNode(left, right);
1688 register_node(cmp, loop, proj2, ddepth);
1689
1690 BoolNode* bol = new (C)BoolNode(cmp, relop);
1691 register_node(bol, loop, proj2, ddepth);
1692
1693 IfNode* new_if = new (C)IfNode(proj2, bol, iff->_prob, iff->_fcnt);
1694 register_node(new_if, loop, proj2, ddepth);
1695
1696 proj->set_req(0, new_if); // reattach
1697 set_idom(proj, new_if, ddepth);
1698
1699 ProjNode* new_exit = proj_clone(other_proj, new_if)->as_Proj();
1700 guarantee(new_exit != NULL, "null exit node");
1701 register_node(new_exit, get_loop(other_proj), new_if, ddepth);
1702
1703 return new_exit;
1704 }
1705
1706 //------------------------------ insert_region_before_proj -------------------------------------
1707 // Insert a region before an if projection (* - new node)
1708 //
1709 // before
1710 // if(test)
1711 // / |
1712 // v |
1713 // proj v
1725 // v
1726 // * dum_if
1727 // / \
1728 // v \
1729 // * dum-proj v
1730 // proj
1731 //
1732 RegionNode* PhaseIdealLoop::insert_region_before_proj(ProjNode* proj) {
1733 IfNode* iff = proj->in(0)->as_If();
1734 IdealLoopTree *loop = get_loop(proj);
1735 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
1736 int ddepth = dom_depth(proj);
1737
1738 _igvn.rehash_node_delayed(iff);
1739 _igvn.rehash_node_delayed(proj);
1740
1741 proj->set_req(0, NULL); // temporary disconnect
1742 ProjNode* proj2 = proj_clone(proj, iff);
1743 register_node(proj2, loop, iff, ddepth);
1744
1745 RegionNode* reg = new (C)RegionNode(2);
1746 reg->set_req(1, proj2);
1747 register_node(reg, loop, iff, ddepth);
1748
1749 IfNode* dum_if = new (C)IfNode(reg, short_circuit_if(NULL, proj), iff->_prob, iff->_fcnt);
1750 register_node(dum_if, loop, reg, ddepth);
1751
1752 proj->set_req(0, dum_if); // reattach
1753 set_idom(proj, dum_if, ddepth);
1754
1755 ProjNode* dum_proj = proj_clone(other_proj, dum_if);
1756 register_node(dum_proj, loop, dum_if, ddepth);
1757
1758 return reg;
1759 }
1760
1761 //------------------------------ insert_cmpi_loop_exit -------------------------------------
1762 // Clone a signed compare loop exit from an unsigned compare and
1763 // insert it before the unsigned cmp on the stay-in-loop path.
1764 // All new nodes inserted in the dominator tree between the original
1765 // if and it's projections. The original if test is replaced with
1766 // a constant to force the stay-in-loop path.
1767 //
1768 // This is done to make sure that the original if and it's projections
1769 // still dominate the same set of control nodes, that the ctrl() relation
2552 #endif
2553 if (new_peel_if != NULL) {
2554 remove_cmpi_loop_exit(new_peel_if, loop);
2555 }
2556 // Inhibit more partial peeling on this loop
2557 assert(!head->is_partial_peel_loop(), "not partial peeled");
2558 head->mark_partial_peel_failed();
2559 if (cloned_for_outside_use > 0) {
2560 // Terminate this round of loop opts because
2561 // the graph outside this loop was changed.
2562 C->set_major_progress();
2563 return true;
2564 }
2565 return false;
2566 }
2567
2568 // Step 3: clone loop, retarget control, and insert new phis
2569
2570 // Create new loop head for new phis and to hang
2571 // the nodes being moved (sinked) from the peel region.
2572 LoopNode* new_head = new (C) LoopNode(last_peel, last_peel);
2573 new_head->set_unswitch_count(head->unswitch_count()); // Preserve
2574 _igvn.register_new_node_with_optimizer(new_head);
2575 assert(first_not_peeled->in(0) == last_peel, "last_peel <- first_not_peeled");
2576 first_not_peeled->set_req(0, new_head);
2577 set_loop(new_head, loop);
2578 loop->_body.push(new_head);
2579 not_peel.set(new_head->_idx);
2580 set_idom(new_head, last_peel, dom_depth(first_not_peeled));
2581 set_idom(first_not_peeled, new_head, dom_depth(first_not_peeled));
2582
2583 while (sink_list.size() > 0) {
2584 Node* n = sink_list.pop();
2585 set_ctrl(n, new_head);
2586 }
2587
2588 assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
2589
2590 clone_loop( loop, old_new, dd );
2591
2592 const uint clone_exit_idx = 1;
2752 progress = false;
2753 for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) {
2754 Node* use = phi->fast_out(i); // User of trip-counter
2755 if (!has_ctrl(use)) continue;
2756 Node *u_ctrl = get_ctrl(use);
2757 if (use->is_Phi()) {
2758 u_ctrl = NULL;
2759 for (uint j = 1; j < use->req(); j++)
2760 if (use->in(j) == phi)
2761 u_ctrl = dom_lca(u_ctrl, use->in(0)->in(j));
2762 }
2763 IdealLoopTree *u_loop = get_loop(u_ctrl);
2764 // Look for loop-invariant use
2765 if (u_loop == loop) continue;
2766 if (loop->is_member(u_loop)) continue;
2767 // Check that use is live out the bottom. Assuming the trip-counter
2768 // update is right at the bottom, uses of of the loop middle are ok.
2769 if (dom_lca(exit, u_ctrl) != exit) continue;
2770 // Hit! Refactor use to use the post-incremented tripcounter.
2771 // Compute a post-increment tripcounter.
2772 Node *opaq = new (C) Opaque2Node( C, cle->incr() );
2773 register_new_node( opaq, u_ctrl );
2774 Node *neg_stride = _igvn.intcon(-cle->stride_con());
2775 set_ctrl(neg_stride, C->root());
2776 Node *post = new (C) AddINode( opaq, neg_stride);
2777 register_new_node( post, u_ctrl );
2778 _igvn.rehash_node_delayed(use);
2779 for (uint j = 1; j < use->req(); j++) {
2780 if (use->in(j) == phi)
2781 use->set_req(j, post);
2782 }
2783 // Since DU info changed, rerun loop
2784 progress = true;
2785 break;
2786 }
2787 }
2788
2789 }
|
39 //------------------------------split_thru_phi---------------------------------
40 // Split Node 'n' through merge point if there is enough win.
41 Node *PhaseIdealLoop::split_thru_phi( Node *n, Node *region, int policy ) {
42 if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) {
43 // ConvI2L may have type information on it which is unsafe to push up
44 // so disable this for now
45 return NULL;
46 }
47
48 int wins = 0;
49 assert(!n->is_CFG(), "");
50 assert(region->is_Region(), "");
51
52 const Type* type = n->bottom_type();
53 const TypeOopPtr *t_oop = _igvn.type(n)->isa_oopptr();
54 Node *phi;
55 if (t_oop != NULL && t_oop->is_known_instance_field()) {
56 int iid = t_oop->instance_id();
57 int index = C->get_alias_index(t_oop);
58 int offset = t_oop->offset();
59 phi = new PhiNode(region, type, NULL, iid, index, offset);
60 } else {
61 phi = PhiNode::make_blank(region, n);
62 }
63 uint old_unique = C->unique();
64 for (uint i = 1; i < region->req(); i++) {
65 Node *x;
66 Node* the_clone = NULL;
67 if (region->in(i) == C->top()) {
68 x = C->top(); // Dead path? Use a dead data op
69 } else {
70 x = n->clone(); // Else clone up the data op
71 the_clone = x; // Remember for possible deletion.
72 // Alter data node to use pre-phi inputs
73 if (n->in(0) == region)
74 x->set_req( 0, region->in(i) );
75 for (uint j = 1; j < n->req(); j++) {
76 Node *in = n->in(j);
77 if (in->is_Phi() && in->in(0) == region)
78 x->set_req( j, in->in(i) ); // Use pre-Phi input for the clone
79 }
346 Node *scale = n->in(2);
347 Node *scale_ctrl = get_ctrl(scale);
348 IdealLoopTree *scale_loop = get_loop(scale_ctrl );
349 if( n_loop == scale_loop || !scale_loop->is_member( n_loop ) )
350 return NULL;
351 const TypeInt *scale_t = scale->bottom_type()->isa_int();
352 if( scale_t && scale_t->is_con() && scale_t->get_con() >= 16 )
353 return NULL; // Dont bother with byte/short masking
354 // Add must vary with loop (else shift would be loop-invariant)
355 Node *add = n->in(1);
356 Node *add_ctrl = get_ctrl(add);
357 IdealLoopTree *add_loop = get_loop(add_ctrl);
358 //assert( n_loop == add_loop, "" );
359 if( n_loop != add_loop ) return NULL; // happens w/ evil ZKM loops
360
361 // Convert I-V into I+ (0-V); same for V-I
362 if( add->Opcode() == Op_SubI &&
363 _igvn.type( add->in(1) ) != TypeInt::ZERO ) {
364 Node *zero = _igvn.intcon(0);
365 set_ctrl(zero, C->root());
366 Node *neg = new SubINode( _igvn.intcon(0), add->in(2) );
367 register_new_node( neg, get_ctrl(add->in(2) ) );
368 add = new AddINode( add->in(1), neg );
369 register_new_node( add, add_ctrl );
370 }
371 if( add->Opcode() != Op_AddI ) return NULL;
372 // See if one add input is loop invariant
373 Node *add_var = add->in(1);
374 Node *add_var_ctrl = get_ctrl(add_var);
375 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
376 Node *add_invar = add->in(2);
377 Node *add_invar_ctrl = get_ctrl(add_invar);
378 IdealLoopTree *add_invar_loop = get_loop(add_invar_ctrl );
379 if( add_var_loop == n_loop ) {
380 } else if( add_invar_loop == n_loop ) {
381 // Swap to find the invariant part
382 add_invar = add_var;
383 add_invar_ctrl = add_var_ctrl;
384 add_invar_loop = add_var_loop;
385 add_var = add->in(2);
386 Node *add_var_ctrl = get_ctrl(add_var);
387 IdealLoopTree *add_var_loop = get_loop(add_var_ctrl );
388 } else // Else neither input is loop invariant
389 return NULL;
390 if( n_loop == add_invar_loop || !add_invar_loop->is_member( n_loop ) )
391 return NULL; // No invariant part of the add?
392
393 // Yes! Reshape address expression!
394 Node *inv_scale = new LShiftINode( add_invar, scale );
395 Node *inv_scale_ctrl =
396 dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ?
397 add_invar_ctrl : scale_ctrl;
398 register_new_node( inv_scale, inv_scale_ctrl );
399 Node *var_scale = new LShiftINode( add_var, scale );
400 register_new_node( var_scale, n_ctrl );
401 Node *var_add = new AddINode( var_scale, inv_scale );
402 register_new_node( var_add, n_ctrl );
403 _igvn.replace_node( n, var_add );
404 return var_add;
405 }
406
407 // Replace (I+V) with (V+I)
408 if( n_op == Op_AddI ||
409 n_op == Op_AddL ||
410 n_op == Op_AddF ||
411 n_op == Op_AddD ||
412 n_op == Op_MulI ||
413 n_op == Op_MulL ||
414 n_op == Op_MulF ||
415 n_op == Op_MulD ) {
416 if( n2_loop == n_loop ) {
417 assert( n1_loop != n_loop, "" );
418 n->swap_edges(1, 2);
419 }
420 }
421
422 // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V),
423 // but not if I2 is a constant.
424 if( n_op == Op_AddP ) {
425 if( n2_loop == n_loop && n3_loop != n_loop ) {
426 if( n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con() ) {
427 Node *n22_ctrl = get_ctrl(n->in(2)->in(2));
428 Node *n23_ctrl = get_ctrl(n->in(2)->in(3));
429 IdealLoopTree *n22loop = get_loop( n22_ctrl );
430 IdealLoopTree *n23_loop = get_loop( n23_ctrl );
431 if( n22loop != n_loop && n22loop->is_member(n_loop) &&
432 n23_loop == n_loop ) {
433 Node *add1 = new AddPNode( n->in(1), n->in(2)->in(2), n->in(3) );
434 // Stuff new AddP in the loop preheader
435 register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
436 Node *add2 = new AddPNode( n->in(1), add1, n->in(2)->in(3) );
437 register_new_node( add2, n_ctrl );
438 _igvn.replace_node( n, add2 );
439 return add2;
440 }
441 }
442 }
443
444 // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V)
445 if( n2_loop != n_loop && n3_loop == n_loop ) {
446 if( n->in(3)->Opcode() == Op_AddI ) {
447 Node *V = n->in(3)->in(1);
448 Node *I = n->in(3)->in(2);
449 if( is_member(n_loop,get_ctrl(V)) ) {
450 } else {
451 Node *tmp = V; V = I; I = tmp;
452 }
453 if( !is_member(n_loop,get_ctrl(I)) ) {
454 Node *add1 = new AddPNode( n->in(1), n->in(2), I );
455 // Stuff new AddP in the loop preheader
456 register_new_node( add1, n_loop->_head->in(LoopNode::EntryControl) );
457 Node *add2 = new AddPNode( n->in(1), add1, V );
458 register_new_node( add2, n_ctrl );
459 _igvn.replace_node( n, add2 );
460 return add2;
461 }
462 }
463 }
464 }
465
466 return NULL;
467 }
468
469 //------------------------------conditional_move-------------------------------
470 // Attempt to replace a Phi with a conditional move. We have some pretty
471 // strict profitability requirements. All Phis at the merge point must
472 // be converted, so we can remove the control flow. We need to limit the
473 // number of c-moves to a small handful. All code that was in the side-arms
474 // of the CFG diamond is now speculatively executed. This code has to be
475 // "cheap enough". We are pretty much limited to CFG diamonds that merge
476 // 1 or 2 items with a total of 1 or 2 ops executed speculatively.
477 Node *PhaseIdealLoop::conditional_move( Node *region ) {
1087 // "Nearly" because all Nodes have been cloned from the original in the loop,
1088 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1089 // through the Phi recursively, and return a Bool.
1090 BoolNode *PhaseIdealLoop::clone_iff( PhiNode *phi, IdealLoopTree *loop ) {
1091
1092 // Convert this Phi into a Phi merging Bools
1093 uint i;
1094 for( i = 1; i < phi->req(); i++ ) {
1095 Node *b = phi->in(i);
1096 if( b->is_Phi() ) {
1097 _igvn.replace_input_of(phi, i, clone_iff( b->as_Phi(), loop ));
1098 } else {
1099 assert( b->is_Bool(), "" );
1100 }
1101 }
1102
1103 Node *sample_bool = phi->in(1);
1104 Node *sample_cmp = sample_bool->in(1);
1105
1106 // Make Phis to merge the Cmp's inputs.
1107 PhiNode *phi1 = new PhiNode( phi->in(0), Type::TOP );
1108 PhiNode *phi2 = new PhiNode( phi->in(0), Type::TOP );
1109 for( i = 1; i < phi->req(); i++ ) {
1110 Node *n1 = phi->in(i)->in(1)->in(1);
1111 Node *n2 = phi->in(i)->in(1)->in(2);
1112 phi1->set_req( i, n1 );
1113 phi2->set_req( i, n2 );
1114 phi1->set_type( phi1->type()->meet_speculative(n1->bottom_type()));
1115 phi2->set_type( phi2->type()->meet_speculative(n2->bottom_type()));
1116 }
1117 // See if these Phis have been made before.
1118 // Register with optimizer
1119 Node *hit1 = _igvn.hash_find_insert(phi1);
1120 if( hit1 ) { // Hit, toss just made Phi
1121 _igvn.remove_dead_node(phi1); // Remove new phi
1122 assert( hit1->is_Phi(), "" );
1123 phi1 = (PhiNode*)hit1; // Use existing phi
1124 } else { // Miss
1125 _igvn.register_new_node_with_optimizer(phi1);
1126 }
1127 Node *hit2 = _igvn.hash_find_insert(phi2);
1128 if( hit2 ) { // Hit, toss just made Phi
1155 //------------------------------clone_bool-------------------------------------
1156 // Passed in a Phi merging (recursively) some nearly equivalent Bool/Cmps.
1157 // "Nearly" because all Nodes have been cloned from the original in the loop,
1158 // but the fall-in edges to the Cmp are different. Clone bool/Cmp pairs
1159 // through the Phi recursively, and return a Bool.
1160 CmpNode *PhaseIdealLoop::clone_bool( PhiNode *phi, IdealLoopTree *loop ) {
1161 uint i;
1162 // Convert this Phi into a Phi merging Bools
1163 for( i = 1; i < phi->req(); i++ ) {
1164 Node *b = phi->in(i);
1165 if( b->is_Phi() ) {
1166 _igvn.replace_input_of(phi, i, clone_bool( b->as_Phi(), loop ));
1167 } else {
1168 assert( b->is_Cmp() || b->is_top(), "inputs are all Cmp or TOP" );
1169 }
1170 }
1171
1172 Node *sample_cmp = phi->in(1);
1173
1174 // Make Phis to merge the Cmp's inputs.
1175 PhiNode *phi1 = new PhiNode( phi->in(0), Type::TOP );
1176 PhiNode *phi2 = new PhiNode( phi->in(0), Type::TOP );
1177 for( uint j = 1; j < phi->req(); j++ ) {
1178 Node *cmp_top = phi->in(j); // Inputs are all Cmp or TOP
1179 Node *n1, *n2;
1180 if( cmp_top->is_Cmp() ) {
1181 n1 = cmp_top->in(1);
1182 n2 = cmp_top->in(2);
1183 } else {
1184 n1 = n2 = cmp_top;
1185 }
1186 phi1->set_req( j, n1 );
1187 phi2->set_req( j, n2 );
1188 phi1->set_type(phi1->type()->meet_speculative(n1->bottom_type()));
1189 phi2->set_type(phi2->type()->meet_speculative(n2->bottom_type()));
1190 }
1191
1192 // See if these Phis have been made before.
1193 // Register with optimizer
1194 Node *hit1 = _igvn.hash_find_insert(phi1);
1195 if( hit1 ) { // Hit, toss just made Phi
1196 _igvn.remove_dead_node(phi1); // Remove new phi
1320 for (DUIterator_Fast jmax, j = old->fast_outs(jmax); j < jmax; j++)
1321 worklist.push(old->fast_out(j));
1322
1323 while( worklist.size() ) { // Visit all uses
1324 Node *use = worklist.pop();
1325 if (!has_node(use)) continue; // Ignore dead nodes
1326 IdealLoopTree *use_loop = get_loop( has_ctrl(use) ? get_ctrl(use) : use );
1327 if( !loop->is_member( use_loop ) && use->is_CFG() ) {
1328 // Both OLD and USE are CFG nodes here.
1329 assert( use->is_Proj(), "" );
1330
1331 // Clone the loop exit control projection
1332 Node *newuse = use->clone();
1333 newuse->set_req(0,nnn);
1334 _igvn.register_new_node_with_optimizer(newuse);
1335 set_loop(newuse, use_loop);
1336 set_idom(newuse, nnn, dom_depth(nnn) + 1 );
1337
1338 // We need a Region to merge the exit from the peeled body and the
1339 // exit from the old loop body.
1340 RegionNode *r = new RegionNode(3);
1341 // Map the old use to the new merge point
1342 old_new.map( use->_idx, r );
1343 uint dd_r = MIN2(dom_depth(newuse),dom_depth(use));
1344 assert( dd_r >= dom_depth(dom_lca(newuse,use)), "" );
1345
1346 // The original user of 'use' uses 'r' instead.
1347 for (DUIterator_Last lmin, l = use->last_outs(lmin); l >= lmin;) {
1348 Node* useuse = use->last_out(l);
1349 _igvn.rehash_node_delayed(useuse);
1350 uint uses_found = 0;
1351 if( useuse->in(0) == use ) {
1352 useuse->set_req(0, r);
1353 uses_found++;
1354 if( useuse->is_CFG() ) {
1355 assert( dom_depth(useuse) > dd_r, "" );
1356 set_idom(useuse, r, dom_depth(useuse));
1357 }
1358 }
1359 for( uint k = 1; k < useuse->req(); k++ ) {
1360 if( useuse->in(k) == use ) {
1667 // other-proj v
1668 // * new_if(relop(cmp[IU](left,right)))
1669 // / \
1670 // v v
1671 // * new-proj proj
1672 // (returned)
1673 //
1674 ProjNode* PhaseIdealLoop::insert_if_before_proj(Node* left, bool Signed, BoolTest::mask relop, Node* right, ProjNode* proj) {
1675 IfNode* iff = proj->in(0)->as_If();
1676 IdealLoopTree *loop = get_loop(proj);
1677 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
1678 int ddepth = dom_depth(proj);
1679
1680 _igvn.rehash_node_delayed(iff);
1681 _igvn.rehash_node_delayed(proj);
1682
1683 proj->set_req(0, NULL); // temporary disconnect
1684 ProjNode* proj2 = proj_clone(proj, iff);
1685 register_node(proj2, loop, iff, ddepth);
1686
1687 Node* cmp = Signed ? (Node*) new CmpINode(left, right) : (Node*) new CmpUNode(left, right);
1688 register_node(cmp, loop, proj2, ddepth);
1689
1690 BoolNode* bol = new BoolNode(cmp, relop);
1691 register_node(bol, loop, proj2, ddepth);
1692
1693 IfNode* new_if = new IfNode(proj2, bol, iff->_prob, iff->_fcnt);
1694 register_node(new_if, loop, proj2, ddepth);
1695
1696 proj->set_req(0, new_if); // reattach
1697 set_idom(proj, new_if, ddepth);
1698
1699 ProjNode* new_exit = proj_clone(other_proj, new_if)->as_Proj();
1700 guarantee(new_exit != NULL, "null exit node");
1701 register_node(new_exit, get_loop(other_proj), new_if, ddepth);
1702
1703 return new_exit;
1704 }
1705
1706 //------------------------------ insert_region_before_proj -------------------------------------
1707 // Insert a region before an if projection (* - new node)
1708 //
1709 // before
1710 // if(test)
1711 // / |
1712 // v |
1713 // proj v
1725 // v
1726 // * dum_if
1727 // / \
1728 // v \
1729 // * dum-proj v
1730 // proj
1731 //
1732 RegionNode* PhaseIdealLoop::insert_region_before_proj(ProjNode* proj) {
1733 IfNode* iff = proj->in(0)->as_If();
1734 IdealLoopTree *loop = get_loop(proj);
1735 ProjNode *other_proj = iff->proj_out(!proj->is_IfTrue())->as_Proj();
1736 int ddepth = dom_depth(proj);
1737
1738 _igvn.rehash_node_delayed(iff);
1739 _igvn.rehash_node_delayed(proj);
1740
1741 proj->set_req(0, NULL); // temporary disconnect
1742 ProjNode* proj2 = proj_clone(proj, iff);
1743 register_node(proj2, loop, iff, ddepth);
1744
1745 RegionNode* reg = new RegionNode(2);
1746 reg->set_req(1, proj2);
1747 register_node(reg, loop, iff, ddepth);
1748
1749 IfNode* dum_if = new IfNode(reg, short_circuit_if(NULL, proj), iff->_prob, iff->_fcnt);
1750 register_node(dum_if, loop, reg, ddepth);
1751
1752 proj->set_req(0, dum_if); // reattach
1753 set_idom(proj, dum_if, ddepth);
1754
1755 ProjNode* dum_proj = proj_clone(other_proj, dum_if);
1756 register_node(dum_proj, loop, dum_if, ddepth);
1757
1758 return reg;
1759 }
1760
1761 //------------------------------ insert_cmpi_loop_exit -------------------------------------
1762 // Clone a signed compare loop exit from an unsigned compare and
1763 // insert it before the unsigned cmp on the stay-in-loop path.
1764 // All new nodes inserted in the dominator tree between the original
1765 // if and it's projections. The original if test is replaced with
1766 // a constant to force the stay-in-loop path.
1767 //
1768 // This is done to make sure that the original if and it's projections
1769 // still dominate the same set of control nodes, that the ctrl() relation
2552 #endif
2553 if (new_peel_if != NULL) {
2554 remove_cmpi_loop_exit(new_peel_if, loop);
2555 }
2556 // Inhibit more partial peeling on this loop
2557 assert(!head->is_partial_peel_loop(), "not partial peeled");
2558 head->mark_partial_peel_failed();
2559 if (cloned_for_outside_use > 0) {
2560 // Terminate this round of loop opts because
2561 // the graph outside this loop was changed.
2562 C->set_major_progress();
2563 return true;
2564 }
2565 return false;
2566 }
2567
2568 // Step 3: clone loop, retarget control, and insert new phis
2569
2570 // Create new loop head for new phis and to hang
2571 // the nodes being moved (sinked) from the peel region.
2572 LoopNode* new_head = new LoopNode(last_peel, last_peel);
2573 new_head->set_unswitch_count(head->unswitch_count()); // Preserve
2574 _igvn.register_new_node_with_optimizer(new_head);
2575 assert(first_not_peeled->in(0) == last_peel, "last_peel <- first_not_peeled");
2576 first_not_peeled->set_req(0, new_head);
2577 set_loop(new_head, loop);
2578 loop->_body.push(new_head);
2579 not_peel.set(new_head->_idx);
2580 set_idom(new_head, last_peel, dom_depth(first_not_peeled));
2581 set_idom(first_not_peeled, new_head, dom_depth(first_not_peeled));
2582
2583 while (sink_list.size() > 0) {
2584 Node* n = sink_list.pop();
2585 set_ctrl(n, new_head);
2586 }
2587
2588 assert(is_valid_loop_partition(loop, peel, peel_list, not_peel), "bad partition");
2589
2590 clone_loop( loop, old_new, dd );
2591
2592 const uint clone_exit_idx = 1;
2752 progress = false;
2753 for (DUIterator_Fast imax, i = phi->fast_outs(imax); i < imax; i++) {
2754 Node* use = phi->fast_out(i); // User of trip-counter
2755 if (!has_ctrl(use)) continue;
2756 Node *u_ctrl = get_ctrl(use);
2757 if (use->is_Phi()) {
2758 u_ctrl = NULL;
2759 for (uint j = 1; j < use->req(); j++)
2760 if (use->in(j) == phi)
2761 u_ctrl = dom_lca(u_ctrl, use->in(0)->in(j));
2762 }
2763 IdealLoopTree *u_loop = get_loop(u_ctrl);
2764 // Look for loop-invariant use
2765 if (u_loop == loop) continue;
2766 if (loop->is_member(u_loop)) continue;
2767 // Check that use is live out the bottom. Assuming the trip-counter
2768 // update is right at the bottom, uses of of the loop middle are ok.
2769 if (dom_lca(exit, u_ctrl) != exit) continue;
2770 // Hit! Refactor use to use the post-incremented tripcounter.
2771 // Compute a post-increment tripcounter.
2772 Node *opaq = new Opaque2Node( C, cle->incr() );
2773 register_new_node( opaq, u_ctrl );
2774 Node *neg_stride = _igvn.intcon(-cle->stride_con());
2775 set_ctrl(neg_stride, C->root());
2776 Node *post = new AddINode( opaq, neg_stride);
2777 register_new_node( post, u_ctrl );
2778 _igvn.rehash_node_delayed(use);
2779 for (uint j = 1; j < use->req(); j++) {
2780 if (use->in(j) == phi)
2781 use->set_req(j, post);
2782 }
2783 // Since DU info changed, rerun loop
2784 progress = true;
2785 break;
2786 }
2787 }
2788
2789 }
|