458 // | | |
459 // | stmt2 |
460 // | | |
461 // | v |
462 // v if ^
463 // | / \ |
464 // | / \ |
465 // | v v |
466 // | false true |
467 // | | \ |
468 // v v --+
469 // region
470 // |
471 // v
472 // exit
473 //
474 void PhaseIdealLoop::do_peeling( IdealLoopTree *loop, Node_List &old_new ) {
475
476 C->set_major_progress();
477 // Peeling a 'main' loop in a pre/main/post situation obfuscates the
478 // 'pre' loop from the main and the 'pre' can no longer have it's
479 // iterations adjusted. Therefore, we need to declare this loop as
480 // no longer a 'main' loop; it will need new pre and post loops before
481 // we can do further RCE.
482 #ifndef PRODUCT
483 if (TraceLoopOpts) {
484 tty->print("Peel ");
485 loop->dump_head();
486 }
487 #endif
488 Node* head = loop->_head;
489 bool counted_loop = head->is_CountedLoop();
490 if (counted_loop) {
491 CountedLoopNode *cl = head->as_CountedLoop();
492 assert(cl->trip_count() > 0, "peeling a fully unrolled loop");
493 cl->set_trip_count(cl->trip_count() - 1);
494 if (cl->is_main_loop()) {
495 cl->set_normal_loop();
496 #ifndef PRODUCT
497 if (PrintOpto && VerifyLoopOptimizations) {
498 tty->print("Peeling a 'main' loop; resetting to 'normal' ");
1894 // Find the main loop limit; we will trim it's iterations
1895 // to not ever trip end tests
1896 Node *main_limit = cl->limit();
1897
1898 // Need to find the main-loop zero-trip guard
1899 Node *ctrl = cl->in(LoopNode::EntryControl);
1900 assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
1901 Node *iffm = ctrl->in(0);
1902 assert(iffm->Opcode() == Op_If, "");
1903 Node *bolzm = iffm->in(1);
1904 assert(bolzm->Opcode() == Op_Bool, "");
1905 Node *cmpzm = bolzm->in(1);
1906 assert(cmpzm->is_Cmp(), "");
1907 Node *opqzm = cmpzm->in(2);
1908 // Can not optimize a loop if zero-trip Opaque1 node is optimized
1909 // away and then another round of loop opts attempted.
1910 if (opqzm->Opcode() != Op_Opaque1)
1911 return;
1912 assert(opqzm->in(1) == main_limit, "do not understand situation");
1913
1914 // Find the pre-loop limit; we will expand it's iterations to
1915 // not ever trip low tests.
1916 Node *p_f = iffm->in(0);
1917 assert(p_f->Opcode() == Op_IfFalse, "");
1918 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
1919 assert(pre_end->loopnode()->is_pre_loop(), "");
1920 Node *pre_opaq1 = pre_end->limit();
1921 // Occasionally it's possible for a pre-loop Opaque1 node to be
1922 // optimized away and then another round of loop opts attempted.
1923 // We can not optimize this particular loop in that case.
1924 if (pre_opaq1->Opcode() != Op_Opaque1)
1925 return;
1926 Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1;
1927 Node *pre_limit = pre_opaq->in(1);
1928
1929 // Where do we put new limit calculations
1930 Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl);
1931
1932 // Ensure the original loop limit is available from the
1933 // pre-loop Opaque1 node.
1934 Node *orig_limit = pre_opaq->original_loop_limit();
2198 // Find the OTHER exit path from the IF
2199 Node* ex = iff->proj_out(1-test_con);
2200 float p = iff->_prob;
2201 if( !phase->is_member( this, ex ) && iff->_fcnt == COUNT_UNKNOWN ) {
2202 if( top == Op_IfTrue ) {
2203 if( p < (PROB_FAIR + PROB_UNLIKELY_MAG(3))) {
2204 iff->_prob = PROB_STATIC_FREQUENT;
2205 }
2206 } else {
2207 if( p > (PROB_FAIR - PROB_UNLIKELY_MAG(3))) {
2208 iff->_prob = PROB_STATIC_INFREQUENT;
2209 }
2210 }
2211 }
2212 }
2213 }
2214 test = phase->idom(test);
2215 }
2216 }
2217
2218
2219 //------------------------------policy_do_remove_empty_loop--------------------
2220 // Micro-benchmark spamming. Policy is to always remove empty loops.
2221 // The 'DO' part is to replace the trip counter with the value it will
2222 // have on the last iteration. This will break the loop.
2223 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) {
2224 // Minimum size must be empty loop
2225 if (_body.size() > EMPTY_LOOP_SIZE)
2226 return false;
2227
2228 if (!_head->is_CountedLoop())
2229 return false; // Dead loop
2230 CountedLoopNode *cl = _head->as_CountedLoop();
2231 if (!cl->is_valid_counted_loop())
2232 return false; // Malformed loop
2233 if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
2234 return false; // Infinite loop
2235
2236 #ifdef ASSERT
2237 // Ensure only one phi which is the iv.
2238 Node* iv = NULL;
2239 for (DUIterator_Fast imax, i = cl->fast_outs(imax); i < imax; i++) {
2240 Node* n = cl->fast_out(i);
2241 if (n->Opcode() == Op_Phi) {
2242 assert(iv == NULL, "Too many phis" );
2243 iv = n;
2244 }
2245 }
2246 assert(iv == cl->phi(), "Wrong phi" );
2247 #endif
2248
2249 // main and post loops have explicitly created zero trip guard
2250 bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
2251 if (needs_guard) {
2252 // Skip guard if values not overlap.
2253 const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
2254 const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
|
458 // | | |
459 // | stmt2 |
460 // | | |
461 // | v |
462 // v if ^
463 // | / \ |
464 // | / \ |
465 // | v v |
466 // | false true |
467 // | | \ |
468 // v v --+
469 // region
470 // |
471 // v
472 // exit
473 //
474 void PhaseIdealLoop::do_peeling( IdealLoopTree *loop, Node_List &old_new ) {
475
476 C->set_major_progress();
477 // Peeling a 'main' loop in a pre/main/post situation obfuscates the
478 // 'pre' loop from the main and the 'pre' can no longer have its
479 // iterations adjusted. Therefore, we need to declare this loop as
480 // no longer a 'main' loop; it will need new pre and post loops before
481 // we can do further RCE.
482 #ifndef PRODUCT
483 if (TraceLoopOpts) {
484 tty->print("Peel ");
485 loop->dump_head();
486 }
487 #endif
488 Node* head = loop->_head;
489 bool counted_loop = head->is_CountedLoop();
490 if (counted_loop) {
491 CountedLoopNode *cl = head->as_CountedLoop();
492 assert(cl->trip_count() > 0, "peeling a fully unrolled loop");
493 cl->set_trip_count(cl->trip_count() - 1);
494 if (cl->is_main_loop()) {
495 cl->set_normal_loop();
496 #ifndef PRODUCT
497 if (PrintOpto && VerifyLoopOptimizations) {
498 tty->print("Peeling a 'main' loop; resetting to 'normal' ");
1894 // Find the main loop limit; we will trim it's iterations
1895 // to not ever trip end tests
1896 Node *main_limit = cl->limit();
1897
1898 // Need to find the main-loop zero-trip guard
1899 Node *ctrl = cl->in(LoopNode::EntryControl);
1900 assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
1901 Node *iffm = ctrl->in(0);
1902 assert(iffm->Opcode() == Op_If, "");
1903 Node *bolzm = iffm->in(1);
1904 assert(bolzm->Opcode() == Op_Bool, "");
1905 Node *cmpzm = bolzm->in(1);
1906 assert(cmpzm->is_Cmp(), "");
1907 Node *opqzm = cmpzm->in(2);
1908 // Can not optimize a loop if zero-trip Opaque1 node is optimized
1909 // away and then another round of loop opts attempted.
1910 if (opqzm->Opcode() != Op_Opaque1)
1911 return;
1912 assert(opqzm->in(1) == main_limit, "do not understand situation");
1913
1914 // Find the pre-loop limit; we will expand its iterations to
1915 // not ever trip low tests.
1916 Node *p_f = iffm->in(0);
1917 assert(p_f->Opcode() == Op_IfFalse, "");
1918 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
1919 assert(pre_end->loopnode()->is_pre_loop(), "");
1920 Node *pre_opaq1 = pre_end->limit();
1921 // Occasionally it's possible for a pre-loop Opaque1 node to be
1922 // optimized away and then another round of loop opts attempted.
1923 // We can not optimize this particular loop in that case.
1924 if (pre_opaq1->Opcode() != Op_Opaque1)
1925 return;
1926 Opaque1Node *pre_opaq = (Opaque1Node*)pre_opaq1;
1927 Node *pre_limit = pre_opaq->in(1);
1928
1929 // Where do we put new limit calculations
1930 Node *pre_ctrl = pre_end->loopnode()->in(LoopNode::EntryControl);
1931
1932 // Ensure the original loop limit is available from the
1933 // pre-loop Opaque1 node.
1934 Node *orig_limit = pre_opaq->original_loop_limit();
2198 // Find the OTHER exit path from the IF
2199 Node* ex = iff->proj_out(1-test_con);
2200 float p = iff->_prob;
2201 if( !phase->is_member( this, ex ) && iff->_fcnt == COUNT_UNKNOWN ) {
2202 if( top == Op_IfTrue ) {
2203 if( p < (PROB_FAIR + PROB_UNLIKELY_MAG(3))) {
2204 iff->_prob = PROB_STATIC_FREQUENT;
2205 }
2206 } else {
2207 if( p > (PROB_FAIR - PROB_UNLIKELY_MAG(3))) {
2208 iff->_prob = PROB_STATIC_INFREQUENT;
2209 }
2210 }
2211 }
2212 }
2213 }
2214 test = phase->idom(test);
2215 }
2216 }
2217
2218 #ifdef ASSERT
2219 static CountedLoopNode* locate_pre_from_main(CountedLoopNode *cl) {
2220 Node *ctrl = cl->in(LoopNode::EntryControl);
2221 assert(ctrl->Opcode() == Op_IfTrue || ctrl->Opcode() == Op_IfFalse, "");
2222 Node *iffm = ctrl->in(0);
2223 assert(iffm->Opcode() == Op_If, "");
2224 Node *p_f = iffm->in(0);
2225 assert(p_f->Opcode() == Op_IfFalse, "");
2226 CountedLoopEndNode *pre_end = p_f->in(0)->as_CountedLoopEnd();
2227 assert(pre_end->loopnode()->is_pre_loop(), "");
2228 return pre_end->loopnode();
2229 }
2230 #endif
2231
2232 // Remove the main and post loops and make the pre loop execute all
2233 // iterations. Useful when the pre loop is found empty.
2234 void IdealLoopTree::remove_main_post_loops(CountedLoopNode *cl, PhaseIdealLoop *phase) {
2235 CountedLoopEndNode* pre_end = cl->loopexit();
2236 Node* pre_cmp = pre_end->cmp_node();
2237 if (pre_cmp->in(2)->Opcode() != Op_Opaque1) {
2238 // Only safe to remove the main loop if the compiler optimized it
2239 // out based on an unknown number of iterations
2240 return;
2241 }
2242
2243 if (_next == NULL || !_next->_head->is_CountedLoop() || !_next->_head->as_CountedLoop()->is_main_loop()) {
2244 // Can't find the main loop
2245 return;
2246 }
2247
2248 CountedLoopNode* main_head = _next->_head->as_CountedLoop();;
2249 assert(locate_pre_from_main(main_head) == cl, "bad main loop");
2250 Node* main_iff = main_head->in(LoopNode::EntryControl)->in(0);
2251
2252 // Remove the Opaque1Node of the pre loop and make it execute all iterations
2253 phase->_igvn.replace_input_of(pre_cmp, 2, pre_cmp->in(2)->in(2));
2254 // Remove the Opaque1Node of the main loop so it can be optimized out
2255 Node* main_cmp = main_iff->in(1)->in(1);
2256 assert(main_cmp->in(2)->Opcode() == Op_Opaque1, "main loop has no opaque node?");
2257 phase->_igvn.replace_input_of(main_cmp, 2, main_cmp->in(2)->in(1));
2258 }
2259
2260 //------------------------------policy_do_remove_empty_loop--------------------
2261 // Micro-benchmark spamming. Policy is to always remove empty loops.
2262 // The 'DO' part is to replace the trip counter with the value it will
2263 // have on the last iteration. This will break the loop.
2264 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) {
2265 // Minimum size must be empty loop
2266 if (_body.size() > EMPTY_LOOP_SIZE)
2267 return false;
2268
2269 if (!_head->is_CountedLoop())
2270 return false; // Dead loop
2271 CountedLoopNode *cl = _head->as_CountedLoop();
2272 if (!cl->is_valid_counted_loop())
2273 return false; // Malformed loop
2274 if (!phase->is_member(this, phase->get_ctrl(cl->loopexit()->in(CountedLoopEndNode::TestValue))))
2275 return false; // Infinite loop
2276
2277 if (cl->is_pre_loop()) {
2278 // If the loop we are removing is a pre-loop then the main and
2279 // post loop can be removed as well
2280 remove_main_post_loops(cl, phase);
2281 }
2282
2283 #ifdef ASSERT
2284 // Ensure only one phi which is the iv.
2285 Node* iv = NULL;
2286 for (DUIterator_Fast imax, i = cl->fast_outs(imax); i < imax; i++) {
2287 Node* n = cl->fast_out(i);
2288 if (n->Opcode() == Op_Phi) {
2289 assert(iv == NULL, "Too many phis" );
2290 iv = n;
2291 }
2292 }
2293 assert(iv == cl->phi(), "Wrong phi" );
2294 #endif
2295
2296 // main and post loops have explicitly created zero trip guard
2297 bool needs_guard = !cl->is_main_loop() && !cl->is_post_loop();
2298 if (needs_guard) {
2299 // Skip guard if values not overlap.
2300 const TypeInt* init_t = phase->_igvn.type(cl->init_trip())->is_int();
2301 const TypeInt* limit_t = phase->_igvn.type(cl->limit())->is_int();
|