1.1 --- a/src/share/vm/opto/loopTransform.cpp Mon Apr 04 18:48:49 2011 -0700
1.2 +++ b/src/share/vm/opto/loopTransform.cpp Mon Apr 04 19:02:36 2011 -0700
1.3 @@ -522,34 +522,40 @@
1.4 loop->record_for_igvn();
1.5 }
1.6
1.7 +#define EMPTY_LOOP_SIZE 7 // number of nodes in an empty loop
1.8 +
1.9 //------------------------------policy_maximally_unroll------------------------
1.10 -// Return exact loop trip count, or 0 if not maximally unrolling
1.11 +// Calculate exact loop trip count and return true if loop can be maximally
1.12 +// unrolled.
1.13 bool IdealLoopTree::policy_maximally_unroll( PhaseIdealLoop *phase ) const {
1.14 CountedLoopNode *cl = _head->as_CountedLoop();
1.15 assert(cl->is_normal_loop(), "");
1.16 + if (!cl->is_valid_counted_loop())
1.17 + return false; // Malformed counted loop
1.18
1.19 Node *init_n = cl->init_trip();
1.20 Node *limit_n = cl->limit();
1.21
1.22 // Non-constant bounds
1.23 if (init_n == NULL || !init_n->is_Con() ||
1.24 - limit_n == NULL || !limit_n->is_Con() ||
1.25 - // protect against stride not being a constant
1.26 - !cl->stride_is_con()) {
1.27 + limit_n == NULL || !limit_n->is_Con()) {
1.28 return false;
1.29 }
1.30 - int init = init_n->get_int();
1.31 - int limit = limit_n->get_int();
1.32 - int span = limit - init;
1.33 - int stride = cl->stride_con();
1.34 + // Use longs to avoid integer overflow.
1.35 + int stride_con = cl->stride_con();
1.36 + long init_con = cl->init_trip()->get_int();
1.37 + long limit_con = cl->limit()->get_int();
1.38 + int stride_m = stride_con - (stride_con > 0 ? 1 : -1);
1.39 + long trip_cnt = (limit_con - init_con + stride_m)/stride_con;
1.40
1.41 - if (init >= limit || stride > span) {
1.42 + // Note, max_jint is used to indicate unknown trip count.
1.43 + if (trip_cnt <= 0 || trip_cnt >= (long)max_jint) {
1.44 // return a false (no maximally unroll) and the regular unroll/peel
1.45 // route will make a small mess which CCP will fold away.
1.46 return false;
1.47 }
1.48 - uint trip_count = span/stride; // trip_count can be greater than 2 Gig.
1.49 - assert( (int)trip_count*stride == span, "must divide evenly" );
1.50 + uint trip_count = (uint)trip_cnt;
1.51 + cl->set_trip_count(trip_count);
1.52
1.53 // Real policy: if we maximally unroll, does it get too big?
1.54 // Allow the unrolled mess to get larger than standard loop
1.55 @@ -557,15 +563,29 @@
1.56 uint body_size = _body.size();
1.57 uint unroll_limit = (uint)LoopUnrollLimit * 4;
1.58 assert( (intx)unroll_limit == LoopUnrollLimit * 4, "LoopUnrollLimit must fit in 32bits");
1.59 - cl->set_trip_count(trip_count);
1.60 if (trip_count > unroll_limit || body_size > unroll_limit) {
1.61 return false;
1.62 }
1.63
1.64 + // Take into account that after unroll conjoined heads and tails will fold,
1.65 + // otherwise policy_unroll() may allow more unrolling than max unrolling.
1.66 + uint new_body_size = EMPTY_LOOP_SIZE + (body_size - EMPTY_LOOP_SIZE) * trip_count;
1.67 + uint tst_body_size = (new_body_size - EMPTY_LOOP_SIZE) / trip_count + EMPTY_LOOP_SIZE;
1.68 + if (body_size != tst_body_size) // Check for int overflow
1.69 + return false;
1.70 + if (new_body_size > unroll_limit ||
1.71 + // Unrolling can result in a large amount of node construction
1.72 + new_body_size >= MaxNodeLimit - phase->C->unique()) {
1.73 + return false;
1.74 + }
1.75 +
1.76 // Currently we don't have policy to optimize one iteration loops.
1.77 // Maximally unrolling transformation is used for that:
1.78 // it is peeled and the original loop become non reachable (dead).
1.79 - if (trip_count == 1)
1.80 + // Also fully unroll a loop with few iterations regardless next
1.81 + // conditions since following loop optimizations will split
1.82 + // such loop anyway (pre-main-post).
1.83 + if (trip_count <= 3)
1.84 return true;
1.85
1.86 // Do not unroll a loop with String intrinsics code.
1.87 @@ -582,17 +602,7 @@
1.88 } // switch
1.89 }
1.90
1.91 - if (body_size <= unroll_limit) {
1.92 - uint new_body_size = body_size * trip_count;
1.93 - if (new_body_size <= unroll_limit &&
1.94 - body_size == new_body_size / trip_count &&
1.95 - // Unrolling can result in a large amount of node construction
1.96 - new_body_size < MaxNodeLimit - phase->C->unique()) {
1.97 - return true; // maximally unroll
1.98 - }
1.99 - }
1.100 -
1.101 - return false; // Do not maximally unroll
1.102 + return true; // Do maximally unroll
1.103 }
1.104
1.105
1.106 @@ -604,12 +614,15 @@
1.107 CountedLoopNode *cl = _head->as_CountedLoop();
1.108 assert(cl->is_normal_loop() || cl->is_main_loop(), "");
1.109
1.110 - // protect against stride not being a constant
1.111 - if (!cl->stride_is_con()) return false;
1.112 + if (!cl->is_valid_counted_loop())
1.113 + return false; // Malformed counted loop
1.114
1.115 // protect against over-unrolling
1.116 if (cl->trip_count() <= 1) return false;
1.117
1.118 + // Check for stride being a small enough constant
1.119 + if (abs(cl->stride_con()) > (1<<3)) return false;
1.120 +
1.121 int future_unroll_ct = cl->unrolled_count() * 2;
1.122
1.123 // Don't unroll if the next round of unrolling would push us
1.124 @@ -690,9 +703,6 @@
1.125 return false;
1.126 }
1.127
1.128 - // Check for stride being a small enough constant
1.129 - if (abs(cl->stride_con()) > (1<<3)) return false;
1.130 -
1.131 // Unroll once! (Each trip will soon do double iterations)
1.132 return true;
1.133 }
1.134 @@ -1086,7 +1096,11 @@
1.135 tty->print("Unrolling ");
1.136 loop->dump_head();
1.137 } else if (TraceLoopOpts) {
1.138 - tty->print("Unroll %d ", loop_head->unrolled_count()*2);
1.139 + if (loop_head->trip_count() < LoopUnrollLimit) {
1.140 + tty->print("Unroll %d(%2d) ", loop_head->unrolled_count()*2, loop_head->trip_count());
1.141 + } else {
1.142 + tty->print("Unroll %d ", loop_head->unrolled_count()*2);
1.143 + }
1.144 loop->dump_head();
1.145 }
1.146 #endif
1.147 @@ -1761,7 +1775,7 @@
1.148 // have on the last iteration. This will break the loop.
1.149 bool IdealLoopTree::policy_do_remove_empty_loop( PhaseIdealLoop *phase ) {
1.150 // Minimum size must be empty loop
1.151 - if (_body.size() > 7/*number of nodes in an empty loop*/)
1.152 + if (_body.size() > EMPTY_LOOP_SIZE)
1.153 return false;
1.154
1.155 if (!_head->is_CountedLoop())
1.156 @@ -1887,6 +1901,12 @@
1.157 }
1.158 }
1.159
1.160 + // Skip next optimizations if running low on nodes. Note that
1.161 + // policy_unswitching and policy_maximally_unroll have this check.
1.162 + uint nodes_left = MaxNodeLimit - phase->C->unique();
1.163 + if ((2 * _body.size()) > nodes_left) {
1.164 + return true;
1.165 + }
1.166
1.167 // Counted loops may be peeled, may need some iterations run up
1.168 // front for RCE, and may want to align loop refs to a cache
