1 /*
2 * Copyright (c) 2000, 2016, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
191 return 0;
192 }
193
194 //---------------------reassociate_add_sub-----------------------------
195 // Reassociate invariant add and subtract expressions:
196 //
197 // inv1 + (x + inv2) => ( inv1 + inv2) + x
198 // (x + inv2) + inv1 => ( inv1 + inv2) + x
199 // inv1 + (x - inv2) => ( inv1 - inv2) + x
200 // inv1 - (inv2 - x) => ( inv1 - inv2) + x
201 // (x + inv2) - inv1 => (-inv1 + inv2) + x
202 // (x - inv2) + inv1 => ( inv1 - inv2) + x
203 // (x - inv2) - inv1 => (-inv1 - inv2) + x
204 // inv1 + (inv2 - x) => ( inv1 + inv2) - x
205 // inv1 - (x - inv2) => ( inv1 + inv2) - x
206 // (inv2 - x) + inv1 => ( inv1 + inv2) - x
207 // (inv2 - x) - inv1 => (-inv1 + inv2) - x
208 // inv1 - (x + inv2) => ( inv1 - inv2) - x
209 //
210 Node* IdealLoopTree::reassociate_add_sub(Node* n1, PhaseIdealLoop *phase) {
211 if (!n1->is_Add() && !n1->is_Sub() || n1->outcnt() == 0) return NULL;
212 if (is_invariant(n1)) return NULL;
213 int inv1_idx = is_invariant_addition(n1, phase);
214 if (!inv1_idx) return NULL;
215 // Don't mess with add of constant (igvn moves them to expression tree root.)
216 if (n1->is_Add() && n1->in(2)->is_Con()) return NULL;
217 Node* inv1 = n1->in(inv1_idx);
218 Node* n2 = n1->in(3 - inv1_idx);
219 int inv2_idx = is_invariant_addition(n2, phase);
220 if (!inv2_idx) return NULL;
221 Node* x = n2->in(3 - inv2_idx);
222 Node* inv2 = n2->in(inv2_idx);
223
224 bool neg_x = n2->is_Sub() && inv2_idx == 1;
225 bool neg_inv2 = n2->is_Sub() && inv2_idx == 2;
226 bool neg_inv1 = n1->is_Sub() && inv1_idx == 2;
227 if (n1->is_Sub() && inv1_idx == 1) {
228 neg_x = !neg_x;
229 neg_inv2 = !neg_inv2;
230 }
231 Node* inv1_c = phase->get_ctrl(inv1);
712 assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");
713 const TypeInt* iv_type = phase->_igvn.type(phi)->is_int();
714 int next_stride = stride_con * 2; // stride after this unroll
715 if (next_stride > 0) {
716 if (iv_type->_lo + next_stride <= iv_type->_lo || // overflow
717 iv_type->_lo + next_stride > iv_type->_hi) {
718 return false; // over-unrolling
719 }
720 } else if (next_stride < 0) {
721 if (iv_type->_hi + next_stride >= iv_type->_hi || // overflow
722 iv_type->_hi + next_stride < iv_type->_lo) {
723 return false; // over-unrolling
724 }
725 }
726 }
727 }
728
729 // After unroll limit will be adjusted: new_limit = limit-stride.
730 // Bailout if adjustment overflow.
731 const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int();
732 if (stride_con > 0 && ((limit_type->_hi - stride_con) >= limit_type->_hi) ||
733 stride_con < 0 && ((limit_type->_lo - stride_con) <= limit_type->_lo))
734 return false; // overflow
735
736 // Adjust body_size to determine if we unroll or not
737 uint body_size = _body.size();
738 // Key test to unroll loop in CRC32 java code
739 int xors_in_loop = 0;
740 // Also count ModL, DivL and MulL which expand mightly
741 for (uint k = 0; k < _body.size(); k++) {
742 Node* n = _body.at(k);
743 switch (n->Opcode()) {
744 case Op_XorI: xors_in_loop++; break; // CRC32 java code
745 case Op_ModL: body_size += 30; break;
746 case Op_DivL: body_size += 30; break;
747 case Op_MulL: body_size += 10; break;
748 case Op_StrComp:
749 case Op_StrEquals:
750 case Op_StrIndexOf:
751 case Op_StrIndexOfChar:
752 case Op_EncodeISOArray:
753 case Op_AryEq:
1499
1500 if (limit->is_Con()) {
1501 // The check in policy_unroll and the assert above guarantee
1502 // no underflow if limit is constant.
1503 new_limit = _igvn.intcon(limit->get_int() - stride_con);
1504 set_ctrl(new_limit, C->root());
1505 } else {
1506 // Limit is not constant.
1507 if (loop_head->unrolled_count() == 1) { // only for first unroll
1508 // Separate limit by Opaque node in case it is an incremented
1509 // variable from previous loop to avoid using pre-incremented
1510 // value which could increase register pressure.
1511 // Otherwise reorg_offsets() optimization will create a separate
1512 // Opaque node for each use of trip-counter and as result
1513 // zero trip guard limit will be different from loop limit.
1514 assert(has_ctrl(opaq), "should have it");
1515 Node* opaq_ctrl = get_ctrl(opaq);
1516 limit = new Opaque2Node( C, limit );
1517 register_new_node( limit, opaq_ctrl );
1518 }
1519 if (stride_con > 0 && (java_subtract(limit_type->_lo, stride_con) < limit_type->_lo) ||
1520 stride_con < 0 && (java_subtract(limit_type->_hi, stride_con) > limit_type->_hi)) {
1521 // No underflow.
1522 new_limit = new SubINode(limit, stride);
1523 } else {
1524 // (limit - stride) may underflow.
1525 // Clamp the adjustment value with MININT or MAXINT:
1526 //
1527 // new_limit = limit-stride
1528 // if (stride > 0)
1529 // new_limit = (limit < new_limit) ? MININT : new_limit;
1530 // else
1531 // new_limit = (limit > new_limit) ? MAXINT : new_limit;
1532 //
1533 BoolTest::mask bt = loop_end->test_trip();
1534 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
1535 Node* adj_max = _igvn.intcon((stride_con > 0) ? min_jint : max_jint);
1536 set_ctrl(adj_max, C->root());
1537 Node* old_limit = NULL;
1538 Node* adj_limit = NULL;
1539 Node* bol = limit->is_CMove() ? limit->in(CMoveNode::Condition) : NULL;
1540 if (loop_head->unrolled_count() > 1 &&
|
1 /*
2 * Copyright (c) 2000, 2017, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 *
191 return 0;
192 }
193
194 //---------------------reassociate_add_sub-----------------------------
195 // Reassociate invariant add and subtract expressions:
196 //
197 // inv1 + (x + inv2) => ( inv1 + inv2) + x
198 // (x + inv2) + inv1 => ( inv1 + inv2) + x
199 // inv1 + (x - inv2) => ( inv1 - inv2) + x
200 // inv1 - (inv2 - x) => ( inv1 - inv2) + x
201 // (x + inv2) - inv1 => (-inv1 + inv2) + x
202 // (x - inv2) + inv1 => ( inv1 - inv2) + x
203 // (x - inv2) - inv1 => (-inv1 - inv2) + x
204 // inv1 + (inv2 - x) => ( inv1 + inv2) - x
205 // inv1 - (x - inv2) => ( inv1 + inv2) - x
206 // (inv2 - x) + inv1 => ( inv1 + inv2) - x
207 // (inv2 - x) - inv1 => (-inv1 + inv2) - x
208 // inv1 - (x + inv2) => ( inv1 - inv2) - x
209 //
210 Node* IdealLoopTree::reassociate_add_sub(Node* n1, PhaseIdealLoop *phase) {
211 if ((!n1->is_Add() && !n1->is_Sub()) || n1->outcnt() == 0) return NULL;
212 if (is_invariant(n1)) return NULL;
213 int inv1_idx = is_invariant_addition(n1, phase);
214 if (!inv1_idx) return NULL;
215 // Don't mess with add of constant (igvn moves them to expression tree root.)
216 if (n1->is_Add() && n1->in(2)->is_Con()) return NULL;
217 Node* inv1 = n1->in(inv1_idx);
218 Node* n2 = n1->in(3 - inv1_idx);
219 int inv2_idx = is_invariant_addition(n2, phase);
220 if (!inv2_idx) return NULL;
221 Node* x = n2->in(3 - inv2_idx);
222 Node* inv2 = n2->in(inv2_idx);
223
224 bool neg_x = n2->is_Sub() && inv2_idx == 1;
225 bool neg_inv2 = n2->is_Sub() && inv2_idx == 2;
226 bool neg_inv1 = n1->is_Sub() && inv1_idx == 2;
227 if (n1->is_Sub() && inv1_idx == 1) {
228 neg_x = !neg_x;
229 neg_inv2 = !neg_inv2;
230 }
231 Node* inv1_c = phase->get_ctrl(inv1);
712 assert(phi->is_Phi() && phi->in(0) == _head, "Counted loop should have iv phi.");
713 const TypeInt* iv_type = phase->_igvn.type(phi)->is_int();
714 int next_stride = stride_con * 2; // stride after this unroll
715 if (next_stride > 0) {
716 if (iv_type->_lo + next_stride <= iv_type->_lo || // overflow
717 iv_type->_lo + next_stride > iv_type->_hi) {
718 return false; // over-unrolling
719 }
720 } else if (next_stride < 0) {
721 if (iv_type->_hi + next_stride >= iv_type->_hi || // overflow
722 iv_type->_hi + next_stride < iv_type->_lo) {
723 return false; // over-unrolling
724 }
725 }
726 }
727 }
728
729 // After unroll limit will be adjusted: new_limit = limit-stride.
730 // Bailout if adjustment overflow.
731 const TypeInt* limit_type = phase->_igvn.type(limit_n)->is_int();
732 if ((stride_con > 0 && ((limit_type->_hi - stride_con) >= limit_type->_hi)) ||
733 (stride_con < 0 && ((limit_type->_lo - stride_con) <= limit_type->_lo)))
734 return false; // overflow
735
736 // Adjust body_size to determine if we unroll or not
737 uint body_size = _body.size();
738 // Key test to unroll loop in CRC32 java code
739 int xors_in_loop = 0;
740 // Also count ModL, DivL and MulL which expand mightly
741 for (uint k = 0; k < _body.size(); k++) {
742 Node* n = _body.at(k);
743 switch (n->Opcode()) {
744 case Op_XorI: xors_in_loop++; break; // CRC32 java code
745 case Op_ModL: body_size += 30; break;
746 case Op_DivL: body_size += 30; break;
747 case Op_MulL: body_size += 10; break;
748 case Op_StrComp:
749 case Op_StrEquals:
750 case Op_StrIndexOf:
751 case Op_StrIndexOfChar:
752 case Op_EncodeISOArray:
753 case Op_AryEq:
1499
1500 if (limit->is_Con()) {
1501 // The check in policy_unroll and the assert above guarantee
1502 // no underflow if limit is constant.
1503 new_limit = _igvn.intcon(limit->get_int() - stride_con);
1504 set_ctrl(new_limit, C->root());
1505 } else {
1506 // Limit is not constant.
1507 if (loop_head->unrolled_count() == 1) { // only for first unroll
1508 // Separate limit by Opaque node in case it is an incremented
1509 // variable from previous loop to avoid using pre-incremented
1510 // value which could increase register pressure.
1511 // Otherwise reorg_offsets() optimization will create a separate
1512 // Opaque node for each use of trip-counter and as result
1513 // zero trip guard limit will be different from loop limit.
1514 assert(has_ctrl(opaq), "should have it");
1515 Node* opaq_ctrl = get_ctrl(opaq);
1516 limit = new Opaque2Node( C, limit );
1517 register_new_node( limit, opaq_ctrl );
1518 }
1519 if ((stride_con > 0 && (java_subtract(limit_type->_lo, stride_con) < limit_type->_lo)) ||
1520 (stride_con < 0 && (java_subtract(limit_type->_hi, stride_con) > limit_type->_hi))) {
1521 // No underflow.
1522 new_limit = new SubINode(limit, stride);
1523 } else {
1524 // (limit - stride) may underflow.
1525 // Clamp the adjustment value with MININT or MAXINT:
1526 //
1527 // new_limit = limit-stride
1528 // if (stride > 0)
1529 // new_limit = (limit < new_limit) ? MININT : new_limit;
1530 // else
1531 // new_limit = (limit > new_limit) ? MAXINT : new_limit;
1532 //
1533 BoolTest::mask bt = loop_end->test_trip();
1534 assert(bt == BoolTest::lt || bt == BoolTest::gt, "canonical test is expected");
1535 Node* adj_max = _igvn.intcon((stride_con > 0) ? min_jint : max_jint);
1536 set_ctrl(adj_max, C->root());
1537 Node* old_limit = NULL;
1538 Node* adj_limit = NULL;
1539 Node* bol = limit->is_CMove() ? limit->in(CMoveNode::Condition) : NULL;
1540 if (loop_head->unrolled_count() > 1 &&
|