1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/src/share/vm/opto/ifnode.cpp Sat Dec 01 00:00:00 2007 +0000
1.3 @@ -0,0 +1,922 @@
1.4 +/*
1.5 + * Copyright 2000-2006 Sun Microsystems, Inc. All Rights Reserved.
1.6 + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
1.7 + *
1.8 + * This code is free software; you can redistribute it and/or modify it
1.9 + * under the terms of the GNU General Public License version 2 only, as
1.10 + * published by the Free Software Foundation.
1.11 + *
1.12 + * This code is distributed in the hope that it will be useful, but WITHOUT
1.13 + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
1.14 + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
1.15 + * version 2 for more details (a copy is included in the LICENSE file that
1.16 + * accompanied this code).
1.17 + *
1.18 + * You should have received a copy of the GNU General Public License version
1.19 + * 2 along with this work; if not, write to the Free Software Foundation,
1.20 + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
1.21 + *
1.22 + * Please contact Sun Microsystems, Inc., 4150 Network Circle, Santa Clara,
1.23 + * CA 95054 USA or visit www.sun.com if you need additional information or
1.24 + * have any questions.
1.25 + *
1.26 + */
1.27 +
1.28 +// Portions of code courtesy of Clifford Click
1.29 +
1.30 +// Optimization - Graph Style
1.31 +
1.32 +#include "incls/_precompiled.incl"
1.33 +#include "incls/_ifnode.cpp.incl"
1.34 +
1.35 +
1.36 +extern int explicit_null_checks_elided;
1.37 +
1.38 +//=============================================================================
1.39 +//------------------------------Value------------------------------------------
1.40 +// Return a tuple for whichever arm of the IF is reachable
1.41 +const Type *IfNode::Value( PhaseTransform *phase ) const {
1.42 + if( !in(0) ) return Type::TOP;
1.43 + if( phase->type(in(0)) == Type::TOP )
1.44 + return Type::TOP;
1.45 + const Type *t = phase->type(in(1));
1.46 + if( t == Type::TOP ) // data is undefined
1.47 + return TypeTuple::IFNEITHER; // unreachable altogether
1.48 + if( t == TypeInt::ZERO ) // zero, or false
1.49 + return TypeTuple::IFFALSE; // only false branch is reachable
1.50 + if( t == TypeInt::ONE ) // 1, or true
1.51 + return TypeTuple::IFTRUE; // only true branch is reachable
1.52 + assert( t == TypeInt::BOOL, "expected boolean type" );
1.53 +
1.54 + return TypeTuple::IFBOTH; // No progress
1.55 +}
1.56 +
1.57 +const RegMask &IfNode::out_RegMask() const {
1.58 + return RegMask::Empty;
1.59 +}
1.60 +
1.61 +//------------------------------split_if---------------------------------------
1.62 +// Look for places where we merge constants, then test on the merged value.
1.63 +// If the IF test will be constant folded on the path with the constant, we
1.64 +// win by splitting the IF to before the merge point.
1.65 +static Node* split_if(IfNode *iff, PhaseIterGVN *igvn) {
1.66 + // I could be a lot more general here, but I'm trying to squeeze this
1.67 + // in before the Christmas '98 break so I'm gonna be kinda restrictive
1.68 + // on the patterns I accept. CNC
1.69 +
1.70 + // Look for a compare of a constant and a merged value
1.71 + Node *i1 = iff->in(1);
1.72 + if( !i1->is_Bool() ) return NULL;
1.73 + BoolNode *b = i1->as_Bool();
1.74 + Node *cmp = b->in(1);
1.75 + if( !cmp->is_Cmp() ) return NULL;
1.76 + i1 = cmp->in(1);
1.77 + if( i1 == NULL || !i1->is_Phi() ) return NULL;
1.78 + PhiNode *phi = i1->as_Phi();
1.79 + if( phi->is_copy() ) return NULL;
1.80 + Node *con2 = cmp->in(2);
1.81 + if( !con2->is_Con() ) return NULL;
1.82 + // See that the merge point contains some constants
1.83 + Node *con1=NULL;
1.84 + uint i4;
1.85 + for( i4 = 1; i4 < phi->req(); i4++ ) {
1.86 + con1 = phi->in(i4);
1.87 + if( !con1 ) return NULL; // Do not optimize partially collaped merges
1.88 + if( con1->is_Con() ) break; // Found a constant
1.89 + // Also allow null-vs-not-null checks
1.90 + const TypePtr *tp = igvn->type(con1)->isa_ptr();
1.91 + if( tp && tp->_ptr == TypePtr::NotNull )
1.92 + break;
1.93 + }
1.94 + if( i4 >= phi->req() ) return NULL; // Found no constants
1.95 +
1.96 + igvn->C->set_has_split_ifs(true); // Has chance for split-if
1.97 +
1.98 + // Make sure that the compare can be constant folded away
1.99 + Node *cmp2 = cmp->clone();
1.100 + cmp2->set_req(1,con1);
1.101 + cmp2->set_req(2,con2);
1.102 + const Type *t = cmp2->Value(igvn);
1.103 + // This compare is dead, so whack it!
1.104 + igvn->remove_dead_node(cmp2);
1.105 + if( !t->singleton() ) return NULL;
1.106 +
1.107 + // No intervening control, like a simple Call
1.108 + Node *r = iff->in(0);
1.109 + if( !r->is_Region() ) return NULL;
1.110 + if( phi->region() != r ) return NULL;
1.111 + // No other users of the cmp/bool
1.112 + if (b->outcnt() != 1 || cmp->outcnt() != 1) {
1.113 + //tty->print_cr("many users of cmp/bool");
1.114 + return NULL;
1.115 + }
1.116 +
1.117 + // Make sure we can determine where all the uses of merged values go
1.118 + for (DUIterator_Fast jmax, j = r->fast_outs(jmax); j < jmax; j++) {
1.119 + Node* u = r->fast_out(j);
1.120 + if( u == r ) continue;
1.121 + if( u == iff ) continue;
1.122 + if( u->outcnt() == 0 ) continue; // use is dead & ignorable
1.123 + if( !u->is_Phi() ) {
1.124 + /*
1.125 + if( u->is_Start() ) {
1.126 + tty->print_cr("Region has inlined start use");
1.127 + } else {
1.128 + tty->print_cr("Region has odd use");
1.129 + u->dump(2);
1.130 + }*/
1.131 + return NULL;
1.132 + }
1.133 + if( u != phi ) {
1.134 + // CNC - do not allow any other merged value
1.135 + //tty->print_cr("Merging another value");
1.136 + //u->dump(2);
1.137 + return NULL;
1.138 + }
1.139 + // Make sure we can account for all Phi uses
1.140 + for (DUIterator_Fast kmax, k = u->fast_outs(kmax); k < kmax; k++) {
1.141 + Node* v = u->fast_out(k); // User of the phi
1.142 + // CNC - Allow only really simple patterns.
1.143 + // In particular I disallow AddP of the Phi, a fairly common pattern
1.144 + if( v == cmp ) continue; // The compare is OK
1.145 + if( (v->is_ConstraintCast()) &&
1.146 + v->in(0)->in(0) == iff )
1.147 + continue; // CastPP/II of the IfNode is OK
1.148 + // Disabled following code because I cannot tell if exactly one
1.149 + // path dominates without a real dominator check. CNC 9/9/1999
1.150 + //uint vop = v->Opcode();
1.151 + //if( vop == Op_Phi ) { // Phi from another merge point might be OK
1.152 + // Node *r = v->in(0); // Get controlling point
1.153 + // if( !r ) return NULL; // Degraded to a copy
1.154 + // // Find exactly one path in (either True or False doms, but not IFF)
1.155 + // int cnt = 0;
1.156 + // for( uint i = 1; i < r->req(); i++ )
1.157 + // if( r->in(i) && r->in(i)->in(0) == iff )
1.158 + // cnt++;
1.159 + // if( cnt == 1 ) continue; // Exactly one of True or False guards Phi
1.160 + //}
1.161 + if( !v->is_Call() ) {
1.162 + /*
1.163 + if( v->Opcode() == Op_AddP ) {
1.164 + tty->print_cr("Phi has AddP use");
1.165 + } else if( v->Opcode() == Op_CastPP ) {
1.166 + tty->print_cr("Phi has CastPP use");
1.167 + } else if( v->Opcode() == Op_CastII ) {
1.168 + tty->print_cr("Phi has CastII use");
1.169 + } else {
1.170 + tty->print_cr("Phi has use I cant be bothered with");
1.171 + }
1.172 + */
1.173 + }
1.174 + return NULL;
1.175 +
1.176 + /* CNC - Cut out all the fancy acceptance tests
1.177 + // Can we clone this use when doing the transformation?
1.178 + // If all uses are from Phis at this merge or constants, then YES.
1.179 + if( !v->in(0) && v != cmp ) {
1.180 + tty->print_cr("Phi has free-floating use");
1.181 + v->dump(2);
1.182 + return NULL;
1.183 + }
1.184 + for( uint l = 1; l < v->req(); l++ ) {
1.185 + if( (!v->in(l)->is_Phi() || v->in(l)->in(0) != r) &&
1.186 + !v->in(l)->is_Con() ) {
1.187 + tty->print_cr("Phi has use");
1.188 + v->dump(2);
1.189 + return NULL;
1.190 + } // End of if Phi-use input is neither Phi nor Constant
1.191 + } // End of for all inputs to Phi-use
1.192 + */
1.193 + } // End of for all uses of Phi
1.194 + } // End of for all uses of Region
1.195 +
1.196 + // Only do this if the IF node is in a sane state
1.197 + if (iff->outcnt() != 2)
1.198 + return NULL;
1.199 +
1.200 + // Got a hit! Do the Mondo Hack!
1.201 + //
1.202 + //ABC a1c def ghi B 1 e h A C a c d f g i
1.203 + // R - Phi - Phi - Phi Rc - Phi - Phi - Phi Rx - Phi - Phi - Phi
1.204 + // cmp - 2 cmp - 2 cmp - 2
1.205 + // bool bool_c bool_x
1.206 + // if if_c if_x
1.207 + // T F T F T F
1.208 + // ..s.. ..t .. ..s.. ..t.. ..s.. ..t..
1.209 + //
1.210 + // Split the paths coming into the merge point into 2 seperate groups of
1.211 + // merges. On the left will be all the paths feeding constants into the
1.212 + // Cmp's Phi. On the right will be the remaining paths. The Cmp's Phi
1.213 + // will fold up into a constant; this will let the Cmp fold up as well as
1.214 + // all the control flow. Below the original IF we have 2 control
1.215 + // dependent regions, 's' and 't'. Now we will merge the two paths
1.216 + // just prior to 's' and 't' from the two IFs. At least 1 path (and quite
1.217 + // likely 2 or more) will promptly constant fold away.
1.218 + PhaseGVN *phase = igvn;
1.219 +
1.220 + // Make a region merging constants and a region merging the rest
1.221 + uint req_c = 0;
1.222 + for (uint ii = 1; ii < r->req(); ii++) {
1.223 + if( phi->in(ii) == con1 ) {
1.224 + req_c++;
1.225 + }
1.226 + }
1.227 + Node *region_c = new (igvn->C, req_c + 1) RegionNode(req_c + 1);
1.228 + Node *phi_c = con1;
1.229 + uint len = r->req();
1.230 + Node *region_x = new (igvn->C, len - req_c + 1) RegionNode(len - req_c + 1);
1.231 + Node *phi_x = PhiNode::make_blank(region_x, phi);
1.232 + for (uint i = 1, i_c = 1, i_x = 1; i < len; i++) {
1.233 + if( phi->in(i) == con1 ) {
1.234 + region_c->init_req( i_c++, r ->in(i) );
1.235 + } else {
1.236 + region_x->init_req( i_x, r ->in(i) );
1.237 + phi_x ->init_req( i_x++, phi->in(i) );
1.238 + }
1.239 + }
1.240 +
1.241 + // Register the new RegionNodes but do not transform them. Cannot
1.242 + // transform until the entire Region/Phi conglerate has been hacked
1.243 + // as a single huge transform.
1.244 + igvn->register_new_node_with_optimizer( region_c );
1.245 + igvn->register_new_node_with_optimizer( region_x );
1.246 + phi_x = phase->transform( phi_x );
1.247 + // Prevent the untimely death of phi_x. Currently he has no uses. He is
1.248 + // about to get one. If this only use goes away, then phi_x will look dead.
1.249 + // However, he will be picking up some more uses down below.
1.250 + Node *hook = new (igvn->C, 4) Node(4);
1.251 + hook->init_req(0, phi_x);
1.252 + hook->init_req(1, phi_c);
1.253 +
1.254 + // Make the compare
1.255 + Node *cmp_c = phase->makecon(t);
1.256 + Node *cmp_x = cmp->clone();
1.257 + cmp_x->set_req(1,phi_x);
1.258 + cmp_x->set_req(2,con2);
1.259 + cmp_x = phase->transform(cmp_x);
1.260 + // Make the bool
1.261 + Node *b_c = phase->transform(new (igvn->C, 2) BoolNode(cmp_c,b->_test._test));
1.262 + Node *b_x = phase->transform(new (igvn->C, 2) BoolNode(cmp_x,b->_test._test));
1.263 + // Make the IfNode
1.264 + IfNode *iff_c = new (igvn->C, 2) IfNode(region_c,b_c,iff->_prob,iff->_fcnt);
1.265 + igvn->set_type_bottom(iff_c);
1.266 + igvn->_worklist.push(iff_c);
1.267 + hook->init_req(2, iff_c);
1.268 +
1.269 + IfNode *iff_x = new (igvn->C, 2) IfNode(region_x,b_x,iff->_prob, iff->_fcnt);
1.270 + igvn->set_type_bottom(iff_x);
1.271 + igvn->_worklist.push(iff_x);
1.272 + hook->init_req(3, iff_x);
1.273 +
1.274 + // Make the true/false arms
1.275 + Node *iff_c_t = phase->transform(new (igvn->C, 1) IfTrueNode (iff_c));
1.276 + Node *iff_c_f = phase->transform(new (igvn->C, 1) IfFalseNode(iff_c));
1.277 + Node *iff_x_t = phase->transform(new (igvn->C, 1) IfTrueNode (iff_x));
1.278 + Node *iff_x_f = phase->transform(new (igvn->C, 1) IfFalseNode(iff_x));
1.279 +
1.280 + // Merge the TRUE paths
1.281 + Node *region_s = new (igvn->C, 3) RegionNode(3);
1.282 + igvn->_worklist.push(region_s);
1.283 + region_s->init_req(1, iff_c_t);
1.284 + region_s->init_req(2, iff_x_t);
1.285 + igvn->register_new_node_with_optimizer( region_s );
1.286 +
1.287 + // Merge the FALSE paths
1.288 + Node *region_f = new (igvn->C, 3) RegionNode(3);
1.289 + igvn->_worklist.push(region_f);
1.290 + region_f->init_req(1, iff_c_f);
1.291 + region_f->init_req(2, iff_x_f);
1.292 + igvn->register_new_node_with_optimizer( region_f );
1.293 +
1.294 + igvn->hash_delete(cmp);// Remove soon-to-be-dead node from hash table.
1.295 + cmp->set_req(1,NULL); // Whack the inputs to cmp because it will be dead
1.296 + cmp->set_req(2,NULL);
1.297 + // Check for all uses of the Phi and give them a new home.
1.298 + // The 'cmp' got cloned, but CastPP/IIs need to be moved.
1.299 + Node *phi_s = NULL; // do not construct unless needed
1.300 + Node *phi_f = NULL; // do not construct unless needed
1.301 + for (DUIterator_Last i2min, i2 = phi->last_outs(i2min); i2 >= i2min; --i2) {
1.302 + Node* v = phi->last_out(i2);// User of the phi
1.303 + igvn->hash_delete(v); // Have to fixup other Phi users
1.304 + igvn->_worklist.push(v);
1.305 + uint vop = v->Opcode();
1.306 + Node *proj = NULL;
1.307 + if( vop == Op_Phi ) { // Remote merge point
1.308 + Node *r = v->in(0);
1.309 + for (uint i3 = 1; i3 < r->req(); i3++)
1.310 + if (r->in(i3) && r->in(i3)->in(0) == iff) {
1.311 + proj = r->in(i3);
1.312 + break;
1.313 + }
1.314 + } else if( v->is_ConstraintCast() ) {
1.315 + proj = v->in(0); // Controlling projection
1.316 + } else {
1.317 + assert( 0, "do not know how to handle this guy" );
1.318 + }
1.319 +
1.320 + Node *proj_path_data, *proj_path_ctrl;
1.321 + if( proj->Opcode() == Op_IfTrue ) {
1.322 + if( phi_s == NULL ) {
1.323 + // Only construct phi_s if needed, otherwise provides
1.324 + // interfering use.
1.325 + phi_s = PhiNode::make_blank(region_s,phi);
1.326 + phi_s->init_req( 1, phi_c );
1.327 + phi_s->init_req( 2, phi_x );
1.328 + phi_s = phase->transform(phi_s);
1.329 + }
1.330 + proj_path_data = phi_s;
1.331 + proj_path_ctrl = region_s;
1.332 + } else {
1.333 + if( phi_f == NULL ) {
1.334 + // Only construct phi_f if needed, otherwise provides
1.335 + // interfering use.
1.336 + phi_f = PhiNode::make_blank(region_f,phi);
1.337 + phi_f->init_req( 1, phi_c );
1.338 + phi_f->init_req( 2, phi_x );
1.339 + phi_f = phase->transform(phi_f);
1.340 + }
1.341 + proj_path_data = phi_f;
1.342 + proj_path_ctrl = region_f;
1.343 + }
1.344 +
1.345 + // Fixup 'v' for for the split
1.346 + if( vop == Op_Phi ) { // Remote merge point
1.347 + uint i;
1.348 + for( i = 1; i < v->req(); i++ )
1.349 + if( v->in(i) == phi )
1.350 + break;
1.351 + v->set_req(i, proj_path_data );
1.352 + } else if( v->is_ConstraintCast() ) {
1.353 + v->set_req(0, proj_path_ctrl );
1.354 + v->set_req(1, proj_path_data );
1.355 + } else
1.356 + ShouldNotReachHere();
1.357 + }
1.358 +
1.359 + // Now replace the original iff's True/False with region_s/region_t.
1.360 + // This makes the original iff go dead.
1.361 + for (DUIterator_Last i3min, i3 = iff->last_outs(i3min); i3 >= i3min; --i3) {
1.362 + Node* p = iff->last_out(i3);
1.363 + assert( p->Opcode() == Op_IfTrue || p->Opcode() == Op_IfFalse, "" );
1.364 + Node *u = (p->Opcode() == Op_IfTrue) ? region_s : region_f;
1.365 + // Replace p with u
1.366 + igvn->add_users_to_worklist(p);
1.367 + for (DUIterator_Last lmin, l = p->last_outs(lmin); l >= lmin;) {
1.368 + Node* x = p->last_out(l);
1.369 + igvn->hash_delete(x);
1.370 + uint uses_found = 0;
1.371 + for( uint j = 0; j < x->req(); j++ ) {
1.372 + if( x->in(j) == p ) {
1.373 + x->set_req(j, u);
1.374 + uses_found++;
1.375 + }
1.376 + }
1.377 + l -= uses_found; // we deleted 1 or more copies of this edge
1.378 + }
1.379 + igvn->remove_dead_node(p);
1.380 + }
1.381 +
1.382 + // Force the original merge dead
1.383 + igvn->hash_delete(r);
1.384 + r->set_req_X(0,NULL,igvn);
1.385 +
1.386 + // Now remove the bogus extra edges used to keep things alive
1.387 + igvn->remove_dead_node( hook );
1.388 +
1.389 + // Must return either the original node (now dead) or a new node
1.390 + // (Do not return a top here, since that would break the uniqueness of top.)
1.391 + return new (igvn->C, 1) ConINode(TypeInt::ZERO);
1.392 +}
1.393 +
1.394 +//------------------------------is_range_check---------------------------------
1.395 +// Return 0 if not a range check. Return 1 if a range check and set index and
1.396 +// offset. Return 2 if we had to negate the test. Index is NULL if the check
1.397 +// is versus a constant.
1.398 +int IfNode::is_range_check(Node* &range, Node* &index, jint &offset) {
1.399 + Node* b = in(1);
1.400 + if (b == NULL || !b->is_Bool()) return 0;
1.401 + BoolNode* bn = b->as_Bool();
1.402 + Node* cmp = bn->in(1);
1.403 + if (cmp == NULL) return 0;
1.404 + if (cmp->Opcode() != Op_CmpU) return 0;
1.405 +
1.406 + Node* l = cmp->in(1);
1.407 + Node* r = cmp->in(2);
1.408 + int flip_test = 1;
1.409 + if (bn->_test._test == BoolTest::le) {
1.410 + l = cmp->in(2);
1.411 + r = cmp->in(1);
1.412 + flip_test = 2;
1.413 + } else if (bn->_test._test != BoolTest::lt) {
1.414 + return 0;
1.415 + }
1.416 + if (l->is_top()) return 0; // Top input means dead test
1.417 + if (r->Opcode() != Op_LoadRange) return 0;
1.418 +
1.419 + // We have recognized one of these forms:
1.420 + // Flip 1: If (Bool[<] CmpU(l, LoadRange)) ...
1.421 + // Flip 2: If (Bool[<=] CmpU(LoadRange, l)) ...
1.422 +
1.423 + // Make sure it's a real range check by requiring an uncommon trap
1.424 + // along the OOB path. Otherwise, it's possible that the user wrote
1.425 + // something which optimized to look like a range check but behaves
1.426 + // in some other way.
1.427 + Node* iftrap = proj_out(flip_test == 2 ? true : false);
1.428 + bool found_trap = false;
1.429 + if (iftrap != NULL) {
1.430 + Node* u = iftrap->unique_ctrl_out();
1.431 + if (u != NULL) {
1.432 + // It could be a merge point (Region) for uncommon trap.
1.433 + if (u->is_Region()) {
1.434 + Node* c = u->unique_ctrl_out();
1.435 + if (c != NULL) {
1.436 + iftrap = u;
1.437 + u = c;
1.438 + }
1.439 + }
1.440 + if (u->in(0) == iftrap && u->is_CallStaticJava()) {
1.441 + int req = u->as_CallStaticJava()->uncommon_trap_request();
1.442 + if (Deoptimization::trap_request_reason(req) ==
1.443 + Deoptimization::Reason_range_check) {
1.444 + found_trap = true;
1.445 + }
1.446 + }
1.447 + }
1.448 + }
1.449 + if (!found_trap) return 0; // sorry, no cigar
1.450 +
1.451 + // Look for index+offset form
1.452 + Node* ind = l;
1.453 + jint off = 0;
1.454 + if (l->is_top()) {
1.455 + return 0;
1.456 + } else if (l->is_Add()) {
1.457 + if ((off = l->in(1)->find_int_con(0)) != 0) {
1.458 + ind = l->in(2);
1.459 + } else if ((off = l->in(2)->find_int_con(0)) != 0) {
1.460 + ind = l->in(1);
1.461 + }
1.462 + } else if ((off = l->find_int_con(-1)) >= 0) {
1.463 + // constant offset with no variable index
1.464 + ind = NULL;
1.465 + } else {
1.466 + // variable index with no constant offset (or dead negative index)
1.467 + off = 0;
1.468 + }
1.469 +
1.470 + // Return all the values:
1.471 + index = ind;
1.472 + offset = off;
1.473 + range = r;
1.474 + return flip_test;
1.475 +}
1.476 +
1.477 +//------------------------------adjust_check-----------------------------------
1.478 +// Adjust (widen) a prior range check
1.479 +static void adjust_check(Node* proj, Node* range, Node* index,
1.480 + int flip, jint off_lo, PhaseIterGVN* igvn) {
1.481 + PhaseGVN *gvn = igvn;
1.482 + // Break apart the old check
1.483 + Node *iff = proj->in(0);
1.484 + Node *bol = iff->in(1);
1.485 + if( bol->is_top() ) return; // In case a partially dead range check appears
1.486 + // bail (or bomb[ASSERT/DEBUG]) if NOT projection-->IfNode-->BoolNode
1.487 + DEBUG_ONLY( if( !bol->is_Bool() ) { proj->dump(3); fatal("Expect projection-->IfNode-->BoolNode"); } )
1.488 + if( !bol->is_Bool() ) return;
1.489 +
1.490 + Node *cmp = bol->in(1);
1.491 + // Compute a new check
1.492 + Node *new_add = gvn->intcon(off_lo);
1.493 + if( index ) {
1.494 + new_add = off_lo ? gvn->transform(new (gvn->C, 3) AddINode( index, new_add )) : index;
1.495 + }
1.496 + Node *new_cmp = (flip == 1)
1.497 + ? new (gvn->C, 3) CmpUNode( new_add, range )
1.498 + : new (gvn->C, 3) CmpUNode( range, new_add );
1.499 + new_cmp = gvn->transform(new_cmp);
1.500 + // See if no need to adjust the existing check
1.501 + if( new_cmp == cmp ) return;
1.502 + // Else, adjust existing check
1.503 + Node *new_bol = gvn->transform( new (gvn->C, 2) BoolNode( new_cmp, bol->as_Bool()->_test._test ) );
1.504 + igvn->hash_delete( iff );
1.505 + iff->set_req_X( 1, new_bol, igvn );
1.506 +}
1.507 +
1.508 +//------------------------------up_one_dom-------------------------------------
1.509 +// Walk up the dominator tree one step. Return NULL at root or true
1.510 +// complex merges. Skips through small diamonds.
1.511 +Node* IfNode::up_one_dom(Node *curr, bool linear_only) {
1.512 + Node *dom = curr->in(0);
1.513 + if( !dom ) // Found a Region degraded to a copy?
1.514 + return curr->nonnull_req(); // Skip thru it
1.515 +
1.516 + if( curr != dom ) // Normal walk up one step?
1.517 + return dom;
1.518 +
1.519 + // Use linear_only if we are still parsing, since we cannot
1.520 + // trust the regions to be fully filled in.
1.521 + if (linear_only)
1.522 + return NULL;
1.523 +
1.524 + // Else hit a Region. Check for a loop header
1.525 + if( dom->is_Loop() )
1.526 + return dom->in(1); // Skip up thru loops
1.527 +
1.528 + // Check for small diamonds
1.529 + Node *din1, *din2, *din3, *din4;
1.530 + if( dom->req() == 3 && // 2-path merge point
1.531 + (din1 = dom ->in(1)) && // Left path exists
1.532 + (din2 = dom ->in(2)) && // Right path exists
1.533 + (din3 = din1->in(0)) && // Left path up one
1.534 + (din4 = din2->in(0)) ) { // Right path up one
1.535 + if( din3->is_Call() && // Handle a slow-path call on either arm
1.536 + (din3 = din3->in(0)) )
1.537 + din3 = din3->in(0);
1.538 + if( din4->is_Call() && // Handle a slow-path call on either arm
1.539 + (din4 = din4->in(0)) )
1.540 + din4 = din4->in(0);
1.541 + if( din3 == din4 && din3->is_If() )
1.542 + return din3; // Skip around diamonds
1.543 + }
1.544 +
1.545 + // Give up the search at true merges
1.546 + return NULL; // Dead loop? Or hit root?
1.547 +}
1.548 +
1.549 +//------------------------------remove_useless_bool----------------------------
1.550 +// Check for people making a useless boolean: things like
1.551 +// if( (x < y ? true : false) ) { ... }
1.552 +// Replace with if( x < y ) { ... }
1.553 +static Node *remove_useless_bool(IfNode *iff, PhaseGVN *phase) {
1.554 + Node *i1 = iff->in(1);
1.555 + if( !i1->is_Bool() ) return NULL;
1.556 + BoolNode *bol = i1->as_Bool();
1.557 +
1.558 + Node *cmp = bol->in(1);
1.559 + if( cmp->Opcode() != Op_CmpI ) return NULL;
1.560 +
1.561 + // Must be comparing against a bool
1.562 + const Type *cmp2_t = phase->type( cmp->in(2) );
1.563 + if( cmp2_t != TypeInt::ZERO &&
1.564 + cmp2_t != TypeInt::ONE )
1.565 + return NULL;
1.566 +
1.567 + // Find a prior merge point merging the boolean
1.568 + i1 = cmp->in(1);
1.569 + if( !i1->is_Phi() ) return NULL;
1.570 + PhiNode *phi = i1->as_Phi();
1.571 + if( phase->type( phi ) != TypeInt::BOOL )
1.572 + return NULL;
1.573 +
1.574 + // Check for diamond pattern
1.575 + int true_path = phi->is_diamond_phi();
1.576 + if( true_path == 0 ) return NULL;
1.577 +
1.578 + // phi->region->if_proj->ifnode->bool->cmp
1.579 + BoolNode *bol2 = phi->in(0)->in(1)->in(0)->in(1)->as_Bool();
1.580 +
1.581 + // Now get the 'sense' of the test correct so we can plug in
1.582 + // either iff2->in(1) or its complement.
1.583 + int flip = 0;
1.584 + if( bol->_test._test == BoolTest::ne ) flip = 1-flip;
1.585 + else if( bol->_test._test != BoolTest::eq ) return NULL;
1.586 + if( cmp2_t == TypeInt::ZERO ) flip = 1-flip;
1.587 +
1.588 + const Type *phi1_t = phase->type( phi->in(1) );
1.589 + const Type *phi2_t = phase->type( phi->in(2) );
1.590 + // Check for Phi(0,1) and flip
1.591 + if( phi1_t == TypeInt::ZERO ) {
1.592 + if( phi2_t != TypeInt::ONE ) return NULL;
1.593 + flip = 1-flip;
1.594 + } else {
1.595 + // Check for Phi(1,0)
1.596 + if( phi1_t != TypeInt::ONE ) return NULL;
1.597 + if( phi2_t != TypeInt::ZERO ) return NULL;
1.598 + }
1.599 + if( true_path == 2 ) {
1.600 + flip = 1-flip;
1.601 + }
1.602 +
1.603 + Node* new_bol = (flip ? phase->transform( bol2->negate(phase) ) : bol2);
1.604 + iff->set_req(1, new_bol);
1.605 + // Intervening diamond probably goes dead
1.606 + phase->C->set_major_progress();
1.607 + return iff;
1.608 +}
1.609 +
1.610 +static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff);
1.611 +
1.612 +//------------------------------Ideal------------------------------------------
1.613 +// Return a node which is more "ideal" than the current node. Strip out
1.614 +// control copies
1.615 +Node *IfNode::Ideal(PhaseGVN *phase, bool can_reshape) {
1.616 + if (remove_dead_region(phase, can_reshape)) return this;
1.617 + // No Def-Use info?
1.618 + if (!can_reshape) return NULL;
1.619 + PhaseIterGVN *igvn = phase->is_IterGVN();
1.620 +
1.621 + // Don't bother trying to transform a dead if
1.622 + if (in(0)->is_top()) return NULL;
1.623 + // Don't bother trying to transform an if with a dead test
1.624 + if (in(1)->is_top()) return NULL;
1.625 + // Another variation of a dead test
1.626 + if (in(1)->is_Con()) return NULL;
1.627 + // Another variation of a dead if
1.628 + if (outcnt() < 2) return NULL;
1.629 +
1.630 + // Canonicalize the test.
1.631 + Node* idt_if = idealize_test(phase, this);
1.632 + if (idt_if != NULL) return idt_if;
1.633 +
1.634 + // Try to split the IF
1.635 + Node *s = split_if(this, igvn);
1.636 + if (s != NULL) return s;
1.637 +
1.638 + // Check for people making a useless boolean: things like
1.639 + // if( (x < y ? true : false) ) { ... }
1.640 + // Replace with if( x < y ) { ... }
1.641 + Node *bol2 = remove_useless_bool(this, phase);
1.642 + if( bol2 ) return bol2;
1.643 +
1.644 + // Setup to scan up the CFG looking for a dominating test
1.645 + Node *dom = in(0);
1.646 + Node *prev_dom = this;
1.647 +
1.648 + // Check for range-check vs other kinds of tests
1.649 + Node *index1, *range1;
1.650 + jint offset1;
1.651 + int flip1 = is_range_check(range1, index1, offset1);
1.652 + if( flip1 ) {
1.653 + Node *first_prev_dom = NULL;
1.654 +
1.655 + // Try to remove extra range checks. All 'up_one_dom' gives up at merges
1.656 + // so all checks we inspect post-dominate the top-most check we find.
1.657 + // If we are going to fail the current check and we reach the top check
1.658 + // then we are guarenteed to fail, so just start interpreting there.
1.659 + // We 'expand' the top 2 range checks to include all post-dominating
1.660 + // checks.
1.661 +
1.662 + // The top 2 range checks seen
1.663 + Node *prev_chk1 = NULL;
1.664 + Node *prev_chk2 = NULL;
1.665 + // Low and high offsets seen so far
1.666 + jint off_lo = offset1;
1.667 + jint off_hi = offset1;
1.668 +
1.669 + // Scan for the top 2 checks and collect range of offsets
1.670 + for( int dist = 0; dist < 999; dist++ ) { // Range-Check scan limit
1.671 + if( dom->Opcode() == Op_If && // Not same opcode?
1.672 + prev_dom->in(0) == dom ) { // One path of test does dominate?
1.673 + if( dom == this ) return NULL; // dead loop
1.674 + // See if this is a range check
1.675 + Node *index2, *range2;
1.676 + jint offset2;
1.677 + int flip2 = dom->as_If()->is_range_check(range2, index2, offset2);
1.678 + // See if this is a _matching_ range check, checking against
1.679 + // the same array bounds.
1.680 + if( flip2 == flip1 && range2 == range1 && index2 == index1 &&
1.681 + dom->outcnt() == 2 ) {
1.682 + // Gather expanded bounds
1.683 + off_lo = MIN2(off_lo,offset2);
1.684 + off_hi = MAX2(off_hi,offset2);
1.685 + // Record top 2 range checks
1.686 + prev_chk2 = prev_chk1;
1.687 + prev_chk1 = prev_dom;
1.688 + // If we match the test exactly, then the top test covers
1.689 + // both our lower and upper bounds.
1.690 + if( dom->in(1) == in(1) )
1.691 + prev_chk2 = prev_chk1;
1.692 + }
1.693 + }
1.694 + prev_dom = dom;
1.695 + dom = up_one_dom( dom );
1.696 + if( !dom ) break;
1.697 + }
1.698 +
1.699 +
1.700 + // Attempt to widen the dominating range check to cover some later
1.701 + // ones. Since range checks "fail" by uncommon-trapping to the
1.702 + // interpreter, widening a check can make us speculative enter the
1.703 + // interpreter. If we see range-check deopt's, do not widen!
1.704 + if (!phase->C->allow_range_check_smearing()) return NULL;
1.705 +
1.706 + // Constant indices only need to check the upper bound.
1.707 + // Non-constance indices must check both low and high.
1.708 + if( index1 ) {
1.709 + // Didn't find 2 prior covering checks, so cannot remove anything.
1.710 + if( !prev_chk2 ) return NULL;
1.711 + // 'Widen' the offsets of the 1st and 2nd covering check
1.712 + adjust_check( prev_chk1, range1, index1, flip1, off_lo, igvn );
1.713 + // Do not call adjust_check twice on the same projection
1.714 + // as the first call may have transformed the BoolNode to a ConI
1.715 + if( prev_chk1 != prev_chk2 ) {
1.716 + adjust_check( prev_chk2, range1, index1, flip1, off_hi, igvn );
1.717 + }
1.718 + // Test is now covered by prior checks, dominate it out
1.719 + prev_dom = prev_chk2;
1.720 + } else {
1.721 + // Didn't find prior covering check, so cannot remove anything.
1.722 + if( !prev_chk1 ) return NULL;
1.723 + // 'Widen' the offset of the 1st and only covering check
1.724 + adjust_check( prev_chk1, range1, index1, flip1, off_hi, igvn );
1.725 + // Test is now covered by prior checks, dominate it out
1.726 + prev_dom = prev_chk1;
1.727 + }
1.728 +
1.729 +
1.730 + } else { // Scan for an equivalent test
1.731 +
1.732 + Node *cmp;
1.733 + int dist = 0; // Cutoff limit for search
1.734 + int op = Opcode();
1.735 + if( op == Op_If &&
1.736 + (cmp=in(1)->in(1))->Opcode() == Op_CmpP ) {
1.737 + if( cmp->in(2) != NULL && // make sure cmp is not already dead
1.738 + cmp->in(2)->bottom_type() == TypePtr::NULL_PTR ) {
1.739 + dist = 64; // Limit for null-pointer scans
1.740 + } else {
1.741 + dist = 4; // Do not bother for random pointer tests
1.742 + }
1.743 + } else {
1.744 + dist = 4; // Limit for random junky scans
1.745 + }
1.746 +
1.747 + // Normal equivalent-test check.
1.748 + if( !dom ) return NULL; // Dead loop?
1.749 +
1.750 + // Search up the dominator tree for an If with an identical test
1.751 + while( dom->Opcode() != op || // Not same opcode?
1.752 + dom->in(1) != in(1) || // Not same input 1?
1.753 + (req() == 3 && dom->in(2) != in(2)) || // Not same input 2?
1.754 + prev_dom->in(0) != dom ) { // One path of test does not dominate?
1.755 + if( dist < 0 ) return NULL;
1.756 +
1.757 + dist--;
1.758 + prev_dom = dom;
1.759 + dom = up_one_dom( dom );
1.760 + if( !dom ) return NULL;
1.761 + }
1.762 +
1.763 + // Check that we did not follow a loop back to ourselves
1.764 + if( this == dom )
1.765 + return NULL;
1.766 +
1.767 + if( dist > 2 ) // Add to count of NULL checks elided
1.768 + explicit_null_checks_elided++;
1.769 +
1.770 + } // End of Else scan for an equivalent test
1.771 +
1.772 + // Hit! Remove this IF
1.773 +#ifndef PRODUCT
1.774 + if( TraceIterativeGVN ) {
1.775 + tty->print(" Removing IfNode: "); this->dump();
1.776 + }
1.777 + if( VerifyOpto && !phase->allow_progress() ) {
1.778 + // Found an equivalent dominating test,
1.779 + // we can not guarantee reaching a fix-point for these during iterativeGVN
1.780 + // since intervening nodes may not change.
1.781 + return NULL;
1.782 + }
1.783 +#endif
1.784 +
1.785 + // Replace dominated IfNode
1.786 + dominated_by( prev_dom, igvn );
1.787 +
1.788 + // Must return either the original node (now dead) or a new node
1.789 + // (Do not return a top here, since that would break the uniqueness of top.)
1.790 + return new (phase->C, 1) ConINode(TypeInt::ZERO);
1.791 +}
1.792 +
1.793 +//------------------------------dominated_by-----------------------------------
1.794 +void IfNode::dominated_by( Node *prev_dom, PhaseIterGVN *igvn ) {
1.795 + igvn->hash_delete(this); // Remove self to prevent spurious V-N
1.796 + Node *idom = in(0);
1.797 + // Need opcode to decide which way 'this' test goes
1.798 + int prev_op = prev_dom->Opcode();
1.799 + Node *top = igvn->C->top(); // Shortcut to top
1.800 +
1.801 + // Now walk the current IfNode's projections.
1.802 + // Loop ends when 'this' has no more uses.
1.803 + for (DUIterator_Last imin, i = last_outs(imin); i >= imin; --i) {
1.804 + Node *ifp = last_out(i); // Get IfTrue/IfFalse
1.805 + igvn->add_users_to_worklist(ifp);
1.806 + // Check which projection it is and set target.
1.807 + // Data-target is either the dominating projection of the same type
1.808 + // or TOP if the dominating projection is of opposite type.
1.809 + // Data-target will be used as the new control edge for the non-CFG
1.810 + // nodes like Casts and Loads.
1.811 + Node *data_target = (ifp->Opcode() == prev_op ) ? prev_dom : top;
1.812 + // Control-target is just the If's immediate dominator or TOP.
1.813 + Node *ctrl_target = (ifp->Opcode() == prev_op ) ? idom : top;
1.814 +
1.815 + // For each child of an IfTrue/IfFalse projection, reroute.
1.816 + // Loop ends when projection has no more uses.
1.817 + for (DUIterator_Last jmin, j = ifp->last_outs(jmin); j >= jmin; --j) {
1.818 + Node* s = ifp->last_out(j); // Get child of IfTrue/IfFalse
1.819 + igvn->hash_delete(s); // Yank from hash table before edge hacking
1.820 + if( !s->depends_only_on_test() ) {
1.821 + // Find the control input matching this def-use edge.
1.822 + // For Regions it may not be in slot 0.
1.823 + uint l;
1.824 + for( l = 0; s->in(l) != ifp; l++ ) { }
1.825 + s->set_req(l, ctrl_target);
1.826 + } else { // Else, for control producers,
1.827 + s->set_req(0, data_target); // Move child to data-target
1.828 + }
1.829 + igvn->_worklist.push(s); // Revisit collapsed Phis
1.830 + } // End for each child of a projection
1.831 +
1.832 + igvn->remove_dead_node(ifp);
1.833 + } // End for each IfTrue/IfFalse child of If
1.834 +
1.835 + // Kill the IfNode
1.836 + igvn->remove_dead_node(this);
1.837 +}
1.838 +
1.839 +//------------------------------Identity---------------------------------------
1.840 +// If the test is constant & we match, then we are the input Control
1.841 +Node *IfTrueNode::Identity( PhaseTransform *phase ) {
1.842 + // Can only optimize if cannot go the other way
1.843 + const TypeTuple *t = phase->type(in(0))->is_tuple();
1.844 + return ( t == TypeTuple::IFNEITHER || t == TypeTuple::IFTRUE )
1.845 + ? in(0)->in(0) // IfNode control
1.846 + : this; // no progress
1.847 +}
1.848 +
1.849 +//------------------------------dump_spec--------------------------------------
1.850 +#ifndef PRODUCT
1.851 +void IfNode::dump_spec(outputStream *st) const {
1.852 + st->print("P=%f, C=%f",_prob,_fcnt);
1.853 +}
1.854 +#endif
1.855 +
1.856 +//------------------------------idealize_test----------------------------------
1.857 +// Try to canonicalize tests better. Peek at the Cmp/Bool/If sequence and
1.858 +// come up with a canonical sequence. Bools getting 'eq', 'gt' and 'ge' forms
1.859 +// converted to 'ne', 'le' and 'lt' forms. IfTrue/IfFalse get swapped as
1.860 +// needed.
1.861 +static IfNode* idealize_test(PhaseGVN* phase, IfNode* iff) {
1.862 + assert(iff->in(0) != NULL, "If must be live");
1.863 +
1.864 + if (iff->outcnt() != 2) return NULL; // Malformed projections.
1.865 + Node* old_if_f = iff->proj_out(false);
1.866 + Node* old_if_t = iff->proj_out(true);
1.867 +
1.868 + // CountedLoopEnds want the back-control test to be TRUE, irregardless of
1.869 + // whether they are testing a 'gt' or 'lt' condition. The 'gt' condition
1.870 + // happens in count-down loops
1.871 + if (iff->is_CountedLoopEnd()) return NULL;
1.872 + if (!iff->in(1)->is_Bool()) return NULL; // Happens for partially optimized IF tests
1.873 + BoolNode *b = iff->in(1)->as_Bool();
1.874 + BoolTest bt = b->_test;
1.875 + // Test already in good order?
1.876 + if( bt.is_canonical() )
1.877 + return NULL;
1.878 +
1.879 + // Flip test to be canonical. Requires flipping the IfFalse/IfTrue and
1.880 + // cloning the IfNode.
1.881 + Node* new_b = phase->transform( new (phase->C, 2) BoolNode(b->in(1), bt.negate()) );
1.882 + if( !new_b->is_Bool() ) return NULL;
1.883 + b = new_b->as_Bool();
1.884 +
1.885 + PhaseIterGVN *igvn = phase->is_IterGVN();
1.886 + assert( igvn, "Test is not canonical in parser?" );
1.887 +
1.888 + // The IF node never really changes, but it needs to be cloned
1.889 + iff = new (phase->C, 2) IfNode( iff->in(0), b, 1.0-iff->_prob, iff->_fcnt);
1.890 +
1.891 + Node *prior = igvn->hash_find_insert(iff);
1.892 + if( prior ) {
1.893 + igvn->remove_dead_node(iff);
1.894 + iff = (IfNode*)prior;
1.895 + } else {
1.896 + // Cannot call transform on it just yet
1.897 + igvn->set_type_bottom(iff);
1.898 + }
1.899 + igvn->_worklist.push(iff);
1.900 +
1.901 + // Now handle projections. Cloning not required.
1.902 + Node* new_if_f = (Node*)(new (phase->C, 1) IfFalseNode( iff ));
1.903 + Node* new_if_t = (Node*)(new (phase->C, 1) IfTrueNode ( iff ));
1.904 +
1.905 + igvn->register_new_node_with_optimizer(new_if_f);
1.906 + igvn->register_new_node_with_optimizer(new_if_t);
1.907 + igvn->hash_delete(old_if_f);
1.908 + igvn->hash_delete(old_if_t);
1.909 + // Flip test, so flip trailing control
1.910 + igvn->subsume_node(old_if_f, new_if_t);
1.911 + igvn->subsume_node(old_if_t, new_if_f);
1.912 +
1.913 + // Progress
1.914 + return iff;
1.915 +}
1.916 +
1.917 +//------------------------------Identity---------------------------------------
1.918 +// If the test is constant & we match, then we are the input Control
1.919 +Node *IfFalseNode::Identity( PhaseTransform *phase ) {
1.920 + // Can only optimize if cannot go the other way
1.921 + const TypeTuple *t = phase->type(in(0))->is_tuple();
1.922 + return ( t == TypeTuple::IFNEITHER || t == TypeTuple::IFFALSE )
1.923 + ? in(0)->in(0) // IfNode control
1.924 + : this; // no progress
1.925 +}
