851 // If we unrolled with no intention of doing RCE and we later
852 // changed our minds, we got no pre-loop. Either we need to
853 // make a new pre-loop, or we gotta disallow RCE.
854 if (cl->is_main_no_pre_loop()) return false; // Disallowed for now.
855 Node *trip_counter = cl->phi();
856
857 // check for vectorized loops, some opts are no longer needed
858 if (cl->do_unroll_only()) return false;
859
860 // Check loop body for tests of trip-counter plus loop-invariant vs
861 // loop-invariant.
862 for (uint i = 0; i < _body.size(); i++) {
863 Node *iff = _body[i];
864 if (iff->Opcode() == Op_If ||
865 iff->Opcode() == Op_RangeCheck) { // Test?
866
867 // Comparing trip+off vs limit
868 Node *bol = iff->in(1);
869 if (bol->req() != 2) continue; // dead constant test
870 if (!bol->is_Bool()) {
871 assert(UseLoopPredicate && bol->Opcode() == Op_Conv2B, "predicate check only");
872 continue;
873 }
874 if (bol->as_Bool()->_test._test == BoolTest::ne)
875 continue; // not RC
876
877 Node *cmp = bol->in(1);
878 Node *rc_exp = cmp->in(1);
879 Node *limit = cmp->in(2);
880
881 Node *limit_c = phase->get_ctrl(limit);
882 if( limit_c == phase->C->top() )
883 return false; // Found dead test on live IF? No RCE!
884 if( is_member(phase->get_loop(limit_c) ) ) {
885 // Compare might have operands swapped; commute them
886 rc_exp = cmp->in(2);
887 limit = cmp->in(1);
888 limit_c = phase->get_ctrl(limit);
889 if( is_member(phase->get_loop(limit_c) ) )
890 continue; // Both inputs are loop varying; cannot RCE
891 }
1743 }
1744 if (u == phi) {
1745 continue;
1746 }
1747 ok = false;
1748 }
1749
1750 // iff the uses conform
1751 if (ok) {
1752 def_node->add_flag(Node::Flag_is_reduction);
1753 loop_head->mark_has_reductions();
1754 }
1755 }
1756 }
1757 }
1758 }
1759 }
1760 }
1761 }
1762
1763 //------------------------------dominates_backedge---------------------------------
1764 // Returns true if ctrl is executed on every complete iteration
1765 bool IdealLoopTree::dominates_backedge(Node* ctrl) {
1766 assert(ctrl->is_CFG(), "must be control");
1767 Node* backedge = _head->as_Loop()->in(LoopNode::LoopBackControl);
1768 return _phase->dom_lca_internal(ctrl, backedge) == ctrl;
1769 }
1770
1771 //------------------------------adjust_limit-----------------------------------
1772 // Helper function for add_constraint().
1773 Node* PhaseIdealLoop::adjust_limit(int stride_con, Node * scale, Node *offset, Node *rc_limit, Node *loop_limit, Node *pre_ctrl) {
1774 // Compute "I :: (limit-offset)/scale"
1775 Node *con = new SubINode(rc_limit, offset);
1776 register_new_node(con, pre_ctrl);
1777 Node *X = new DivINode(0, con, scale);
1778 register_new_node(X, pre_ctrl);
1779
1780 // Adjust loop limit
1781 loop_limit = (stride_con > 0)
1782 ? (Node*)(new MinINode(loop_limit, X))
1783 : (Node*)(new MaxINode(loop_limit, X));
1784 register_new_node(loop_limit, pre_ctrl);
1785 return loop_limit;
1786 }
1787
1788 //------------------------------add_constraint---------------------------------
1789 // Constrain the main loop iterations so the conditions:
1790 // low_limit <= scale_con * I + offset < upper_limit
2170 continue; // Don't rce this check but continue looking for other candidates.
2171 }
2172 #ifdef ASSERT
2173 if (TraceRangeLimitCheck) {
2174 tty->print_cr("RC bool node%s", flip ? " flipped:" : ":");
2175 bol->dump(2);
2176 }
2177 #endif
2178 // At this point we have the expression as:
2179 // scale_con * trip_counter + offset :: limit
2180 // where scale_con, offset and limit are loop invariant. Trip_counter
2181 // monotonically increases by stride_con, a constant. Both (or either)
2182 // stride_con and scale_con can be negative which will flip about the
2183 // sense of the test.
2184
2185 // Adjust pre and main loop limits to guard the correct iteration set
2186 if( cmp->Opcode() == Op_CmpU ) {// Unsigned compare is really 2 tests
2187 if( b_test._test == BoolTest::lt ) { // Range checks always use lt
2188 // The underflow and overflow limits: 0 <= scale*I+offset < limit
2189 add_constraint( stride_con, scale_con, offset, zero, limit, pre_ctrl, &pre_limit, &main_limit );
2190 if (!conditional_rc) {
2191 // (0-offset)/scale could be outside of loop iterations range.
2192 conditional_rc = !loop->dominates_backedge(iff);
2193 }
2194 } else {
2195 if (PrintOpto) {
2196 tty->print_cr("missed RCE opportunity");
2197 }
2198 continue; // In release mode, ignore it
2199 }
2200 } else { // Otherwise work on normal compares
2201 switch( b_test._test ) {
2202 case BoolTest::gt:
2203 // Fall into GE case
2204 case BoolTest::ge:
2205 // Convert (I*scale+offset) >= Limit to (I*(-scale)+(-offset)) <= -Limit
2206 scale_con = -scale_con;
2207 offset = new SubINode( zero, offset );
2208 register_new_node( offset, pre_ctrl );
2209 limit = new SubINode( zero, limit );
2210 register_new_node( limit, pre_ctrl );
2211 // Fall into LE case
2212 case BoolTest::le:
2213 if (b_test._test != BoolTest::gt) {
2214 // Convert X <= Y to X < Y+1
2215 limit = new AddINode( limit, one );
2216 register_new_node( limit, pre_ctrl );
2217 }
2218 // Fall into LT case
2219 case BoolTest::lt:
2220 // The underflow and overflow limits: MIN_INT <= scale*I+offset < limit
2221 // Note: (MIN_INT+1 == -MAX_INT) is used instead of MIN_INT here
2222 // to avoid problem with scale == -1: MIN_INT/(-1) == MIN_INT.
2223 add_constraint( stride_con, scale_con, offset, mini, limit, pre_ctrl, &pre_limit, &main_limit );
2224 if (!conditional_rc) {
2225 // ((MIN_INT+1)-offset)/scale could be outside of loop iterations range.
2226 // Note: negative offset is replaced with 0 but (MIN_INT+1)/scale could
2227 // still be outside of loop range.
2228 conditional_rc = !loop->dominates_backedge(iff);
2229 }
2230 break;
2231 default:
2232 if (PrintOpto) {
2233 tty->print_cr("missed RCE opportunity");
2234 }
2235 continue; // Unhandled case
2236 }
2237 }
2238
2239 // Kill the eliminated test
2240 C->set_major_progress();
2241 Node *kill_con = _igvn.intcon( 1-flip );
2242 set_ctrl(kill_con, C->root());
2243 _igvn.replace_input_of(iff, 1, kill_con);
2244 // Find surviving projection
2245 assert(iff->is_If(), "");
2246 ProjNode* dp = ((IfNode*)iff)->proj_out(1-flip);
2247 // Find loads off the surviving projection; remove their control edge
2248 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
2249 Node* cd = dp->fast_out(i); // Control-dependent node
|
851 // If we unrolled with no intention of doing RCE and we later
852 // changed our minds, we got no pre-loop. Either we need to
853 // make a new pre-loop, or we gotta disallow RCE.
854 if (cl->is_main_no_pre_loop()) return false; // Disallowed for now.
855 Node *trip_counter = cl->phi();
856
857 // check for vectorized loops, some opts are no longer needed
858 if (cl->do_unroll_only()) return false;
859
860 // Check loop body for tests of trip-counter plus loop-invariant vs
861 // loop-invariant.
862 for (uint i = 0; i < _body.size(); i++) {
863 Node *iff = _body[i];
864 if (iff->Opcode() == Op_If ||
865 iff->Opcode() == Op_RangeCheck) { // Test?
866
867 // Comparing trip+off vs limit
868 Node *bol = iff->in(1);
869 if (bol->req() != 2) continue; // dead constant test
870 if (!bol->is_Bool()) {
871 assert(bol->Opcode() == Op_Conv2B, "predicate check only");
872 continue;
873 }
874 if (bol->as_Bool()->_test._test == BoolTest::ne)
875 continue; // not RC
876
877 Node *cmp = bol->in(1);
878 Node *rc_exp = cmp->in(1);
879 Node *limit = cmp->in(2);
880
881 Node *limit_c = phase->get_ctrl(limit);
882 if( limit_c == phase->C->top() )
883 return false; // Found dead test on live IF? No RCE!
884 if( is_member(phase->get_loop(limit_c) ) ) {
885 // Compare might have operands swapped; commute them
886 rc_exp = cmp->in(2);
887 limit = cmp->in(1);
888 limit_c = phase->get_ctrl(limit);
889 if( is_member(phase->get_loop(limit_c) ) )
890 continue; // Both inputs are loop varying; cannot RCE
891 }
1743 }
1744 if (u == phi) {
1745 continue;
1746 }
1747 ok = false;
1748 }
1749
1750 // iff the uses conform
1751 if (ok) {
1752 def_node->add_flag(Node::Flag_is_reduction);
1753 loop_head->mark_has_reductions();
1754 }
1755 }
1756 }
1757 }
1758 }
1759 }
1760 }
1761 }
1762
1763 //------------------------------adjust_limit-----------------------------------
1764 // Helper function for add_constraint().
1765 Node* PhaseIdealLoop::adjust_limit(int stride_con, Node * scale, Node *offset, Node *rc_limit, Node *loop_limit, Node *pre_ctrl) {
1766 // Compute "I :: (limit-offset)/scale"
1767 Node *con = new SubINode(rc_limit, offset);
1768 register_new_node(con, pre_ctrl);
1769 Node *X = new DivINode(0, con, scale);
1770 register_new_node(X, pre_ctrl);
1771
1772 // Adjust loop limit
1773 loop_limit = (stride_con > 0)
1774 ? (Node*)(new MinINode(loop_limit, X))
1775 : (Node*)(new MaxINode(loop_limit, X));
1776 register_new_node(loop_limit, pre_ctrl);
1777 return loop_limit;
1778 }
1779
1780 //------------------------------add_constraint---------------------------------
1781 // Constrain the main loop iterations so the conditions:
1782 // low_limit <= scale_con * I + offset < upper_limit
2162 continue; // Don't rce this check but continue looking for other candidates.
2163 }
2164 #ifdef ASSERT
2165 if (TraceRangeLimitCheck) {
2166 tty->print_cr("RC bool node%s", flip ? " flipped:" : ":");
2167 bol->dump(2);
2168 }
2169 #endif
2170 // At this point we have the expression as:
2171 // scale_con * trip_counter + offset :: limit
2172 // where scale_con, offset and limit are loop invariant. Trip_counter
2173 // monotonically increases by stride_con, a constant. Both (or either)
2174 // stride_con and scale_con can be negative which will flip about the
2175 // sense of the test.
2176
2177 // Adjust pre and main loop limits to guard the correct iteration set
2178 if( cmp->Opcode() == Op_CmpU ) {// Unsigned compare is really 2 tests
2179 if( b_test._test == BoolTest::lt ) { // Range checks always use lt
2180 // The underflow and overflow limits: 0 <= scale*I+offset < limit
2181 add_constraint( stride_con, scale_con, offset, zero, limit, pre_ctrl, &pre_limit, &main_limit );
2182 // (0-offset)/scale could be outside of loop iterations range.
2183 conditional_rc = true;
2184 } else {
2185 if (PrintOpto) {
2186 tty->print_cr("missed RCE opportunity");
2187 }
2188 continue; // In release mode, ignore it
2189 }
2190 } else { // Otherwise work on normal compares
2191 switch( b_test._test ) {
2192 case BoolTest::gt:
2193 // Fall into GE case
2194 case BoolTest::ge:
2195 // Convert (I*scale+offset) >= Limit to (I*(-scale)+(-offset)) <= -Limit
2196 scale_con = -scale_con;
2197 offset = new SubINode( zero, offset );
2198 register_new_node( offset, pre_ctrl );
2199 limit = new SubINode( zero, limit );
2200 register_new_node( limit, pre_ctrl );
2201 // Fall into LE case
2202 case BoolTest::le:
2203 if (b_test._test != BoolTest::gt) {
2204 // Convert X <= Y to X < Y+1
2205 limit = new AddINode( limit, one );
2206 register_new_node( limit, pre_ctrl );
2207 }
2208 // Fall into LT case
2209 case BoolTest::lt:
2210 // The underflow and overflow limits: MIN_INT <= scale*I+offset < limit
2211 // Note: (MIN_INT+1 == -MAX_INT) is used instead of MIN_INT here
2212 // to avoid problem with scale == -1: MIN_INT/(-1) == MIN_INT.
2213 add_constraint( stride_con, scale_con, offset, mini, limit, pre_ctrl, &pre_limit, &main_limit );
2214 // ((MIN_INT+1)-offset)/scale could be outside of loop iterations range.
2215 // Note: negative offset is replaced with 0 but (MIN_INT+1)/scale could
2216 // still be outside of loop range.
2217 conditional_rc = true;
2218 break;
2219 default:
2220 if (PrintOpto) {
2221 tty->print_cr("missed RCE opportunity");
2222 }
2223 continue; // Unhandled case
2224 }
2225 }
2226
2227 // Kill the eliminated test
2228 C->set_major_progress();
2229 Node *kill_con = _igvn.intcon( 1-flip );
2230 set_ctrl(kill_con, C->root());
2231 _igvn.replace_input_of(iff, 1, kill_con);
2232 // Find surviving projection
2233 assert(iff->is_If(), "");
2234 ProjNode* dp = ((IfNode*)iff)->proj_out(1-flip);
2235 // Find loads off the surviving projection; remove their control edge
2236 for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) {
2237 Node* cd = dp->fast_out(i); // Control-dependent node
|