| products/Sources/formale Sprachen/Java/openjdk-20-36_src/src/hotspot/share/opto/ |
|
Quellcode-Bibliothek© Kompilation durch diese Firma[Weder Korrektheit noch Funktionsfähigkeit der Software werden zugesichert.]Datei: so.xml Sprache: C |
|
||||||
|
/*
* Copyright (c) 1999, 2022, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it * under the terms of the GNU General Public License version 2 only, as * published by the Free Software Foundation. * * This code is distributed in the hope that it will be useful, but WITHOUT * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License * version 2 for more details (a copy is included in the LICENSE file that * accompanied this code). * * You should have received a copy of the GNU General Public License version * 2 along with this work; if not, write to the Free Software Foundation, * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. * * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA * or visit www.oracle.com if you need additional information or have any * questions. * */ #include "precompiled.hpp" #include "gc/shared/barrierSet.hpp" #include "gc/shared/c2/barrierSetC2.hpp" #include "memory/allocation.inline.hpp" #include "memory/resourceArea.hpp" #include "opto/addnode.hpp" #include "opto/callnode.hpp" #include "opto/castnode.hpp" #include "opto/connode.hpp" #include "opto/castnode.hpp" #include "opto/divnode.hpp" #include "opto/loopnode.hpp" #include "opto/matcher.hpp" #include "opto/mulnode.hpp" #include "opto/movenode.hpp" #include "opto/opaquenode.hpp" #include "opto/rootnode.hpp" #include "opto/subnode.hpp" #include "opto/subtypenode.hpp" #include "utilities/macros.hpp" //============================================================================= //------------------------------split_thru_phi--------------------------------- // Split Node 'n' through merge point if there is enough win. Node* PhaseIdealLoop::split_thru_phi(Node* n, Node* region, int policy) { if (n->Opcode() == Op_ConvI2L && n->bottom_type() != TypeLong::LONG) { // ConvI2L may have type information on it which is unsafe to push up // so disable this for now return NULL; } // Splitting range check CastIIs through a loop induction Phi can // cause new Phis to be created that are left unrelated to the loop // induction Phi and prevent optimizations (vectorization) if (n->Opcode() == Op_CastII && region->is_CountedLoop() && n->in(1) == region->as_CountedLoop()->phi()) { return NULL; } // Bail out if 'n' is a Div or Mod node whose zero check was removed earlier (i.e. control is NULL) a // phi p of a trip-counted (integer) loop whose inputs could be zero (include zero in their type r // range that does not necessarily include all values of its inputs. Since each of these inputs w // of 'n', we need to bail out of one of these divisors could be zero (zero in its type range). if ((n->Opcode() == Op_DivI || n->Opcode() == Op_ModI) && n->in(0) == NULL && region->is_CountedLoop() && n->in(2) == region->as_CountedLoop()->phi()) { Node* phi = region->as_CountedLoop()->phi(); for (uint i = 1; i < phi->req(); i++) { if (_igvn.type(phi->in(i))->filter_speculative(TypeInt::ZERO) != Type::TOP) { // Zero could be a possible value but we already removed the zero check. Bail out to avoid a possib return NULL; } } } int wins = 0; assert(!n->is_CFG(), ""); assert(region->is_Region(), ""); const Type* type = n->bottom_type(); const TypeOopPtr* t_oop = _igvn.type(n)->isa_oopptr(); Node* phi; if (t_oop != NULL && t_oop->is_known_instance_field()) { int iid = t_oop->instance_id(); int index = C->get_alias_index(t_oop); int offset = t_oop->offset(); phi = new PhiNode(region, type, NULL, iid, index, offset); } else { phi = PhiNode::make_blank(region, n); } uint old_unique = C->unique(); for (uint i = 1; i < region->req(); i++) { Node* x; Node* the_clone = NULL; if (region->in(i) == C->top()) { x = C->top(); // Dead path? Use a dead data op } else { x = n->clone(); // Else clone up the data op the_clone = x; // Remember for possible deletion. // Alter data node to use pre-phi inputs if (n->in(0) == region) x->set_req( 0, region->in(i) ); for (uint j = 1; j < n->req(); j++) { Node* in = n->in(j); if (in->is_Phi() && in->in(0) == region) x->set_req(j, in->in(i)); // Use pre-Phi input for the clone } } // Check for a 'win' on some paths const Type* t = x->Value(&_igvn); bool singleton = t->singleton(); // A TOP singleton indicates that there are no possible values incoming // along a particular edge. In most cases, this is OK, and the Phi will // be eliminated later in an Ideal call. However, we can't allow this to // happen if the singleton occurs on loop entry, as the elimination of // the PhiNode may cause the resulting node to migrate back to a previous // loop iteration. if (singleton && t == Type::TOP) { // Is_Loop() == false does not confirm the absence of a loop (e.g., an // irreducible loop may not be indicated by an affirmative is_Loop()); // therefore, the only top we can split thru a phi is on a backedge of // a loop. singleton &= region->is_Loop() && (i != LoopNode::EntryControl); } if (singleton) { wins++; x = ((PhaseGVN&)_igvn).makecon(t); } else { // We now call Identity to try to simplify the cloned node. // Note that some Identity methods call phase->type(this). // Make sure that the type array is big enough for // our new node, even though we may throw the node away. // (Note: This tweaking with igvn only works because x is a new node.) _igvn.set_type(x, t); // If x is a TypeNode, capture any more-precise type permanently into Node // otherwise it will be not updated during igvn->transform since // igvn->type(x) is set to x->Value() already. x->raise_bottom_type(t); Node* y = x->Identity(&_igvn); if (y != x) { wins++; x = y; } else { y = _igvn.hash_find(x); if (y) { wins++; x = y; } else { // Else x is a new node we are keeping // We do not need register_new_node_with_optimizer // because set_type has already been called. _igvn._worklist.push(x); } } } if (x != the_clone && the_clone != NULL) _igvn.remove_dead_node(the_clone); phi->set_req( i, x ); } // Too few wins? if (wins <= policy) { _igvn.remove_dead_node(phi); return NULL; } // Record Phi register_new_node( phi, region ); for (uint i2 = 1; i2 < phi->req(); i2++) { Node *x = phi->in(i2); // If we commoned up the cloned 'x' with another existing Node, // the existing Node picks up a new use. We need to make the // existing Node occur higher up so it dominates its uses. Node *old_ctrl; IdealLoopTree *old_loop; if (x->is_Con()) { // Constant's control is always root. set_ctrl(x, C->root()); continue; } // The occasional new node if (x->_idx >= old_unique) { // Found a new, unplaced node? old_ctrl = NULL; old_loop = NULL; // Not in any prior loop } else { old_ctrl = get_ctrl(x); old_loop = get_loop(old_ctrl); // Get prior loop } // New late point must dominate new use Node *new_ctrl = dom_lca(old_ctrl, region->in(i2)); if (new_ctrl == old_ctrl) // Nothing is changed continue; IdealLoopTree *new_loop = get_loop(new_ctrl); // Don't move x into a loop if its uses are // outside of loop. Otherwise x will be cloned // for each use outside of this loop. IdealLoopTree *use_loop = get_loop(region); if (!new_loop->is_member(use_loop) && (old_loop == NULL || !new_loop->is_member(old_loop))) { // Take early control, later control will be recalculated // during next iteration of loop optimizations. new_ctrl = get_early_ctrl(x); new_loop = get_loop(new_ctrl); } // Set new location set_ctrl(x, new_ctrl); // If changing loop bodies, see if we need to collect into new body if (old_loop != new_loop) { if (old_loop && !old_loop->_child) old_loop->_body.yank(x); if (!new_loop->_child) new_loop->_body.push(x); // Collect body info } } return phi; } //------------------------------dominated_by------------------------------------ // Replace the dominated test with an obvious true or false. Place it on the // IGVN worklist for later cleanup. Move control-dependent data Nodes on the // live path up to the dominating control. void PhaseIdealLoop::dominated_by(IfProjNode* prevdom, IfNode* iff, bool flip, bool excl if (VerifyLoopOptimizations && PrintOpto) { tty->print_cr("dominating test"); } // prevdom is the dominating projection of the dominating test. assert(iff->Opcode() == Op_If || iff->Opcode() == Op_CountedLoopEnd || iff->Opcode() == Op_LongCountedLoopEnd || iff->Opcode() == Op_RangeCheck, "Check this code when new subtype is added"); int pop = prevdom->Opcode(); assert( pop == Op_IfFalse || pop == Op_IfTrue, "" ); if (flip) { if (pop == Op_IfTrue) pop = Op_IfFalse; else pop = Op_IfTrue; } // 'con' is set to true or false to kill the dominated test. Node *con = _igvn.makecon(pop == Op_IfTrue ? TypeInt::ONE : TypeInt::ZERO); set_ctrl(con, C->root()); // Constant gets a new use // Hack the dominated test _igvn.replace_input_of(iff, 1, con); // If I dont have a reachable TRUE and FALSE path following the IfNode then // I can assume this path reaches an infinite loop. In this case it's not // important to optimize the data Nodes - either the whole compilation will // be tossed or this path (and all data Nodes) will go dead. if (iff->outcnt() != 2) return; // Make control-dependent data Nodes on the live path (path that will remain // once the dominated IF is removed) become control-dependent on the // dominating projection. Node* dp = iff->proj_out_or_null(pop == Op_IfTrue); // Loop predicates may have depending checks which should not // be skipped. For example, range check predicate has two checks // for lower and upper bounds. if (dp == NULL) return; ProjNode* dp_proj = dp->as_Proj(); ProjNode* unc_proj = iff->proj_out(1 - dp_proj->_con)->as_Proj(); if (exclude_loop_predicate && (unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_predicate) != NULL || unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_profile_predicate) != NULL || unc_proj->is_uncommon_trap_proj(Deoptimization::Reason_range_check) != NULL)) { // If this is a range check (IfNode::is_range_check), do not // reorder because Compile::allow_range_check_smearing might have // changed the check. return; // Let IGVN transformation change control dependence. } IdealLoopTree* old_loop = get_loop(dp); for (DUIterator_Fast imax, i = dp->fast_outs(imax); i < imax; i++) { Node* cd = dp->fast_out(i); // Control-dependent node // Do not rewire Div and Mod nodes which could have a zero divisor to avoid skipping their zero che if (cd->depends_only_on_test() && _igvn.no_dependent_zero_check(cd)) { assert(cd->in(0) == dp, ""); _igvn.replace_input_of(cd, 0, prevdom); set_early_ctrl(cd, false); IdealLoopTree* new_loop = get_loop(get_ctrl(cd)); if (old_loop != new_loop) { if (!old_loop->_child) { old_loop->_body.yank(cd); } if (!new_loop->_child) { new_loop->_body.push(cd); } } --i; --imax; } } } //------------------------------has_local_phi_input---------------------------- // Return TRUE if 'n' has Phi inputs from its local block and no other // block-local inputs (all non-local-phi inputs come from earlier blocks) Node *PhaseIdealLoop::has_local_phi_input( Node *n ) { Node *n_ctrl = get_ctrl(n); // See if some inputs come from a Phi in this block, or from before // this block. uint i; for( i = 1; i < n->req(); i++ ) { Node *phi = n->in(i); if( phi->is_Phi() && phi->in(0) == n_ctrl ) break; } if( i >= n->req() ) return NULL; // No Phi inputs; nowhere to clone thru // Check for inputs created between 'n' and the Phi input. These // must split as well; they have already been given the chance // (courtesy of a post-order visit) and since they did not we must // recover the 'cost' of splitting them by being very profitable // when splitting 'n'. Since this is unlikely we simply give up. for( i = 1; i < n->req(); i++ ) { Node *m = n->in(i); if( get_ctrl(m) == n_ctrl && !m->is_Phi() ) { // We allow the special case of AddP's with no local inputs. // This allows us to split-up address expressions. if (m->is_AddP() && get_ctrl(m->in(AddPNode::Base)) != n_ctrl && get_ctrl(m->in(AddPNode::Address)) != n_ctrl && get_ctrl(m->in(AddPNode::Offset)) != n_ctrl) { // Move the AddP up to the dominating point. That's fine because control of m's inputs // must dominate get_ctrl(m) == n_ctrl and we just checked that the input controls are != n_ctrl Node* c = find_non_split_ctrl(idom(n_ctrl)); if (c->is_OuterStripMinedLoop()) { c->as_Loop()->verify_strip_mined(1); c = c->in(LoopNode::EntryControl); } set_ctrl_and_loop(m, c); continue; } return NULL; } assert(n->is_Phi() || m->is_Phi() || is_dominator(get_ctrl(m), n_ctrl), "m has strange c } return n_ctrl; } // Replace expressions like ((V+I) << 2) with (V<<2 + I<<2). Node* PhaseIdealLoop::remix_address_expressions_add_left_shift(Node* n, IdealLoopTr assert(bt == T_INT || bt == T_LONG, "only for integers"); int n_op = n->Opcode(); if (n_op == Op_LShift(bt)) { // Scale is loop invariant Node* scale = n->in(2); Node* scale_ctrl = get_ctrl(scale); IdealLoopTree* scale_loop = get_loop(scale_ctrl); if (n_loop == scale_loop || !scale_loop->is_member(n_loop)) { return NULL; } const TypeInt* scale_t = scale->bottom_type()->isa_int(); if (scale_t != NULL && scale_t->is_con() && scale_t->get_con() >= 16) { return NULL; // Dont bother with byte/short masking } // Add must vary with loop (else shift would be loop-invariant) Node* add = n->in(1); Node* add_ctrl = get_ctrl(add); IdealLoopTree* add_loop = get_loop(add_ctrl); if (n_loop != add_loop) { return NULL; // happens w/ evil ZKM loops } // Convert I-V into I+ (0-V); same for V-I if (add->Opcode() == Op_Sub(bt) && _igvn.type(add->in(1)) != TypeInteger::zero(bt)) { assert(add->Opcode() == Op_SubI || add->Opcode() == Op_SubL, ""); Node* zero = _igvn.integercon(0, bt); set_ctrl(zero, C->root()); Node* neg = SubNode::make(zero, add->in(2), bt); register_new_node(neg, get_ctrl(add->in(2))); add = AddNode::make(add->in(1), neg, bt); register_new_node(add, add_ctrl); } if (add->Opcode() != Op_Add(bt)) return NULL; assert(add->Opcode() == Op_AddI || add->Opcode() == Op_AddL, ""); // See if one add input is loop invariant Node* add_var = add->in(1); Node* add_var_ctrl = get_ctrl(add_var); IdealLoopTree* add_var_loop = get_loop(add_var_ctrl); Node* add_invar = add->in(2); Node* add_invar_ctrl = get_ctrl(add_invar); IdealLoopTree* add_invar_loop = get_loop(add_invar_ctrl); if (add_invar_loop == n_loop) { // Swap to find the invariant part add_invar = add_var; add_invar_ctrl = add_var_ctrl; add_invar_loop = add_var_loop; add_var = add->in(2); } else if (add_var_loop != n_loop) { // Else neither input is loop invariant return NULL; } if (n_loop == add_invar_loop || !add_invar_loop->is_member(n_loop)) { return NULL; // No invariant part of the add? } // Yes! Reshape address expression! Node* inv_scale = LShiftNode::make(add_invar, scale, bt); Node* inv_scale_ctrl = dom_depth(add_invar_ctrl) > dom_depth(scale_ctrl) ? add_invar_ctrl : scale_ctrl; register_new_node(inv_scale, inv_scale_ctrl); Node* var_scale = LShiftNode::make(add_var, scale, bt); register_new_node(var_scale, n_ctrl); Node* var_add = AddNode::make(var_scale, inv_scale, bt); register_new_node(var_add, n_ctrl); _igvn.replace_node(n, var_add); return var_add; } return NULL; } //------------------------------remix_address_expressions---------------------- // Rework addressing expressions to get the most loop-invariant stuff // moved out. We'd like to do all associative operators, but it's especially // important (common) to do address expressions. Node* PhaseIdealLoop::remix_address_expressions(Node* n) { if (!has_ctrl(n)) return NULL; Node* n_ctrl = get_ctrl(n); IdealLoopTree* n_loop = get_loop(n_ctrl); // See if 'n' mixes loop-varying and loop-invariant inputs and // itself is loop-varying. // Only interested in binary ops (and AddP) if (n->req() < 3 || n->req() > 4) return NULL; Node* n1_ctrl = get_ctrl(n->in( 1)); Node* n2_ctrl = get_ctrl(n->in( 2)); Node* n3_ctrl = get_ctrl(n->in(n->req() == 3 ? 2 : 3)); IdealLoopTree* n1_loop = get_loop(n1_ctrl); IdealLoopTree* n2_loop = get_loop(n2_ctrl); IdealLoopTree* n3_loop = get_loop(n3_ctrl); // Does one of my inputs spin in a tighter loop than self? if ((n_loop->is_member(n1_loop) && n_loop != n1_loop) || (n_loop->is_member(n2_loop) && n_loop != n2_loop) || (n_loop->is_member(n3_loop) && n_loop != n3_loop)) { return NULL; // Leave well enough alone } // Is at least one of my inputs loop-invariant? if (n1_loop == n_loop && n2_loop == n_loop && n3_loop == n_loop) { return NULL; // No loop-invariant inputs } Node* res = remix_address_expressions_add_left_shift(n, n_loop, n_ctrl, T_INT); if (res != NULL) { return res; } res = remix_address_expressions_add_left_shift(n, n_loop, n_ctrl, T_LONG); if (res != NULL) { return res; } int n_op = n->Opcode(); // Replace (I+V) with (V+I) if (n_op == Op_AddI || n_op == Op_AddL || n_op == Op_AddF || n_op == Op_AddD || n_op == Op_MulI || n_op == Op_MulL || n_op == Op_MulF || n_op == Op_MulD) { if (n2_loop == n_loop) { assert(n1_loop != n_loop, ""); n->swap_edges(1, 2); } } // Replace ((I1 +p V) +p I2) with ((I1 +p I2) +p V), // but not if I2 is a constant. if (n_op == Op_AddP) { if (n2_loop == n_loop && n3_loop != n_loop) { if (n->in(2)->Opcode() == Op_AddP && !n->in(3)->is_Con()) { Node* n22_ctrl = get_ctrl(n->in(2)->in(2)); Node* n23_ctrl = get_ctrl(n->in(2)->in(3)); IdealLoopTree* n22loop = get_loop(n22_ctrl); IdealLoopTree* n23_loop = get_loop(n23_ctrl); if (n22loop != n_loop && n22loop->is_member(n_loop) && n23_loop == n_loop) { Node* add1 = new AddPNode(n->in(1), n->in(2)->in(2), n->in(3)); // Stuff new AddP in the loop preheader register_new_node(add1, n_loop->_head->in(LoopNode::EntryControl)); Node* add2 = new AddPNode(n->in(1), add1, n->in(2)->in(3)); register_new_node(add2, n_ctrl); _igvn.replace_node(n, add2); return add2; } } } // Replace (I1 +p (I2 + V)) with ((I1 +p I2) +p V) if (n2_loop != n_loop && n3_loop == n_loop) { if (n->in(3)->Opcode() == Op_AddX) { Node* V = n->in(3)->in(1); Node* I = n->in(3)->in(2); if (is_member(n_loop,get_ctrl(V))) { } else { Node *tmp = V; V = I; I = tmp; } if (!is_member(n_loop,get_ctrl(I))) { Node* add1 = new AddPNode(n->in(1), n->in(2), I); // Stuff new AddP in the loop preheader register_new_node(add1, n_loop->_head->in(LoopNode::EntryControl)); Node* add2 = new AddPNode(n->in(1), add1, V); register_new_node(add2, n_ctrl); _igvn.replace_node(n, add2); return add2; } } } } return NULL; } // Optimize ((in1[2*i] * in2[2*i]) + (in1[2*i+1] * in2[2*i+1])) Node *PhaseIdealLoop::convert_add_to_muladd(Node* n) { assert(n->Opcode() == Op_AddI, "sanity"); Node * nn = NULL; Node * in1 = n->in(1); Node * in2 = n->in(2); if (in1->Opcode() == Op_MulI && in2->Opcode() == Op_MulI) { IdealLoopTree* loop_n = get_loop(get_ctrl(n)); if (loop_n->is_counted() && loop_n->_head->as_Loop()->is_valid_counted_loop(T_INT) && Matcher::match_rule_supported(Op_MulAddVS2VI) && Matcher::match_rule_supported(Op_MulAddS2I)) { Node* mul_in1 = in1->in(1); Node* mul_in2 = in1->in(2); Node* mul_in3 = in2->in(1); Node* mul_in4 = in2->in(2); if (mul_in1->Opcode() == Op_LoadS && mul_in2->Opcode() == Op_LoadS && mul_in3->Opcode() == Op_LoadS && mul_in4->Opcode() == Op_LoadS) { IdealLoopTree* loop1 = get_loop(get_ctrl(mul_in1)); IdealLoopTree* loop2 = get_loop(get_ctrl(mul_in2)); IdealLoopTree* loop3 = get_loop(get_ctrl(mul_in3)); IdealLoopTree* loop4 = get_loop(get_ctrl(mul_in4)); IdealLoopTree* loop5 = get_loop(get_ctrl(in1)); IdealLoopTree* loop6 = get_loop(get_ctrl(in2)); // All nodes should be in the same counted loop. if (loop_n == loop1 && loop_n == loop2 && loop_n == loop3 && loop_n == loop4 && loop_n == loop5 && loop_n == loop6) { Node* adr1 = mul_in1->in(MemNode::Address); Node* adr2 = mul_in2->in(MemNode::Address); Node* adr3 = mul_in3->in(MemNode::Address); Node* adr4 = mul_in4->in(MemNode::Address); if (adr1->is_AddP() && adr2->is_AddP() && adr3->is_AddP() && adr4->is_AddP()) { if ((adr1->in(AddPNode::Base) == adr3->in(AddPNode::Base)) && (adr2->in(AddPNode::Base) == adr4->in(AddPNode::Base))) { nn = new MulAddS2INode(mul_in1, mul_in2, mul_in3, mul_in4); register_new_node(nn, get_ctrl(n)); _igvn.replace_node(n, nn); return nn; } else if ((adr1->in(AddPNode::Base) == adr4->in(AddPNode::Base)) && (adr2->in(AddPNode::Base) == adr3->in(AddPNode::Base))) { nn = new MulAddS2INode(mul_in1, mul_in2, mul_in4, mul_in3); register_new_node(nn, get_ctrl(n)); _igvn.replace_node(n, nn); return nn; } } } } } } return nn; } //------------------------------conditional_move------------------------------- // Attempt to replace a Phi with a conditional move. We have some pretty // strict profitability requirements. All Phis at the merge point must // be converted, so we can remove the control flow. We need to limit the // number of c-moves to a small handful. All code that was in the side-arms // of the CFG diamond is now speculatively executed. This code has to be // "cheap enough". We are pretty much limited to CFG diamonds that merge // 1 or 2 items with a total of 1 or 2 ops executed speculatively. Node *PhaseIdealLoop::conditional_move( Node *region ) { assert(region->is_Region(), "sanity check"); if (region->req() != 3) return NULL; // Check for CFG diamond Node *lp = region->in(1); Node *rp = region->in(2); if (!lp || !rp) return NULL; Node *lp_c = lp->in(0); if (lp_c == NULL || lp_c != rp->in(0) || !lp_c->is_If()) return NULL; IfNode *iff = lp_c->as_If(); // Check for ops pinned in an arm of the diamond. // Can't remove the control flow in this case if (lp->outcnt() > 1) return NULL; if (rp->outcnt() > 1) return NULL; IdealLoopTree* r_loop = get_loop(region); assert(r_loop == get_loop(iff), "sanity"); // Always convert to CMOVE if all results are used only outside this loop. bool used_inside_loop = (r_loop == _ltree_root); // Check profitability int cost = 0; int phis = 0; for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { Node *out = region->fast_out(i); if (!out->is_Phi()) continue; // Ignore other control edges, etc phis++; PhiNode* phi = out->as_Phi(); BasicType bt = phi->type()->basic_type(); switch (bt) { case T_DOUBLE: case T_FLOAT: if (C->use_cmove()) { continue; //TODO: maybe we want to add some cost } cost += Matcher::float_cmove_cost(); // Could be very expensive break; case T_LONG: { cost += Matcher::long_cmove_cost(); // May encodes as 2 CMOV's } case T_INT: // These all CMOV fine case T_ADDRESS: { // (RawPtr) cost++; break; } case T_NARROWOOP: // Fall through case T_OBJECT: { // Base oops are OK, but not derived oops const TypeOopPtr *tp = phi->type()->make_ptr()->isa_oopptr(); // Derived pointers are Bad (tm): what's the Base (for GC purposes) of a // CMOVE'd derived pointer? It's a CMOVE'd derived base. Thus // CMOVE'ing a derived pointer requires we also CMOVE the base. If we // have a Phi for the base here that we convert to a CMOVE all is well // and good. But if the base is dead, we'll not make a CMOVE. Later // the allocator will have to produce a base by creating a CMOVE of the // relevant bases. This puts the allocator in the business of // manufacturing expensive instructions, generally a bad plan. // Just Say No to Conditionally-Moved Derived Pointers. if (tp && tp->offset() != 0) return NULL; cost++; break; } default: return NULL; // In particular, can't do memory or I/O } // Add in cost any speculative ops for (uint j = 1; j < region->req(); j++) { Node *proj = region->in(j); Node *inp = phi->in(j); if (get_ctrl(inp) == proj) { // Found local op cost++; // Check for a chain of dependent ops; these will all become // speculative in a CMOV. for (uint k = 1; k < inp->req(); k++) if (get_ctrl(inp->in(k)) == proj) cost += ConditionalMoveLimit; // Too much speculative goo } } // See if the Phi is used by a Cmp or Narrow oop Decode/Encode. // This will likely Split-If, a higher-payoff operation. for (DUIterator_Fast kmax, k = phi->fast_outs(kmax); k < kmax; k++) { Node* use = phi->fast_out(k); if (use->is_Cmp() || use->is_DecodeNarrowPtr() || use->is_EncodeNarrowPtr()) cost += ConditionalMoveLimit; // Is there a use inside the loop? // Note: check only basic types since CMoveP is pinned. if (!used_inside_loop && is_java_primitive(bt)) { IdealLoopTree* u_loop = get_loop(has_ctrl(use) ? get_ctrl(use) : use); if (r_loop == u_loop || r_loop->is_member(u_loop)) { used_inside_loop = true; } } } }//for Node* bol = iff->in(1); if (bol->Opcode() == Op_Opaque4) { return NULL; // Ignore loop predicate checks (the Opaque4 ensures they will go away) } assert(bol->Opcode() == Op_Bool, "Unexpected node"); int cmp_op = bol->in(1)->Opcode(); if (cmp_op == Op_SubTypeCheck) { // SubTypeCheck expansion expects an IfNode return NULL; } // It is expensive to generate flags from a float compare. // Avoid duplicated float compare. if (phis > 1 && (cmp_op == Op_CmpF || cmp_op == Op_CmpD)) return NULL; float infrequent_prob = PROB_UNLIKELY_MAG(3); // Ignore cost and blocks frequency if CMOVE can be moved outside the loop. if (used_inside_loop) { if (cost >= ConditionalMoveLimit) return NULL; // Too much goo // BlockLayoutByFrequency optimization moves infrequent branch // from hot path. No point in CMOV'ing in such case (110 is used // instead of 100 to take into account not exactness of float value). if (BlockLayoutByFrequency) { infrequent_prob = MAX2(infrequent_prob, (float)BlockLayoutMinDiamondPercentage/110. } } // Check for highly predictable branch. No point in CMOV'ing if // we are going to predict accurately all the time. if (C->use_cmove() && (cmp_op == Op_CmpF || cmp_op == Op_CmpD)) { //keep going } else if (iff->_prob < infrequent_prob || iff->_prob > (1.0f - infrequent_prob)) return NULL; // -------------- // Now replace all Phis with CMOV's Node *cmov_ctrl = iff->in(0); uint flip = (lp->Opcode() == Op_IfTrue); Node_List wq; while (1) { PhiNode* phi = NULL; for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { Node *out = region->fast_out(i); if (out->is_Phi()) { phi = out->as_Phi(); break; } } if (phi == NULL || _igvn.type(phi) == Type::TOP) { break; } if (PrintOpto && VerifyLoopOptimizations) { tty->print_cr("CMOV"); } // Move speculative ops wq.push(phi); while (wq.size() > 0) { Node *n = wq.pop(); for (uint j = 1; j < n->req(); j++) { Node* m = n->in(j); if (m != NULL && !is_dominator(get_ctrl(m), cmov_ctrl)) { #ifndef PRODUCT if (PrintOpto && VerifyLoopOptimizations) { tty->print(" speculate: "); m->dump(); } #endif set_ctrl(m, cmov_ctrl); wq.push(m); } } } Node *cmov = CMoveNode::make(cmov_ctrl, iff->in(1), phi->in(1+flip), phi->in(2-flip), _igv register_new_node( cmov, cmov_ctrl ); _igvn.replace_node( phi, cmov ); #ifndef PRODUCT if (TraceLoopOpts) { tty->print("CMOV "); r_loop->dump_head(); if (Verbose) { bol->in(1)->dump(1); cmov->dump(1); } } if (VerifyLoopOptimizations) verify(); #endif } // The useless CFG diamond will fold up later; see the optimization in // RegionNode::Ideal. _igvn._worklist.push(region); return iff->in(1); } static void enqueue_cfg_uses(Node* m, Unique_Node_List& wq) { for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax; i++) { Node* u = m->fast_out(i); if (u->is_CFG()) { if (u->Opcode() == Op_NeverBranch) { u = ((NeverBranchNode*)u)->proj_out(0); enqueue_cfg_uses(u, wq); } else { wq.push(u); } } } } // Try moving a store out of a loop, right before the loop Node* PhaseIdealLoop::try_move_store_before_loop(Node* n, Node *n_ctrl) { // Store has to be first in the loop body IdealLoopTree *n_loop = get_loop(n_ctrl); if (n->is_Store() && n_loop != _ltree_root && n_loop->is_loop() && n_loop->_head->is_Loop() && n->in(0) != NULL) { Node* address = n->in(MemNode::Address); Node* value = n->in(MemNode::ValueIn); Node* mem = n->in(MemNode::Memory); IdealLoopTree* address_loop = get_loop(get_ctrl(address)); IdealLoopTree* value_loop = get_loop(get_ctrl(value)); // - address and value must be loop invariant // - memory must be a memory Phi for the loop // - Store must be the only store on this memory slice in the // loop: if there's another store following this one then value // written at iteration i by the second store could be overwritten // at iteration i+n by the first store: it's not safe to move the // first store out of the loop // - nothing must observe the memory Phi: it guarantees no read // before the store, we are also guaranteed the store post // dominates the loop head (ignoring a possible early // exit). Otherwise there would be extra Phi involved between the // loop's Phi and the store. // - there must be no early exit from the loop before the Store // (such an exit most of the time would be an extra use of the // memory Phi but sometimes is a bottom memory Phi that takes the // store as input). if (!n_loop->is_member(address_loop) && !n_loop->is_member(value_loop) && mem->is_Phi() && mem->in(0) == n_loop->_head && mem->outcnt() == 1 && mem->in(LoopNode::LoopBackControl) == n) { assert(n_loop->_tail != NULL, "need a tail"); assert(is_dominator(n_ctrl, n_loop->_tail), "store control must not be in a branch // Verify that there's no early exit of the loop before the store. bool ctrl_ok = false; { // Follow control from loop head until n, we exit the loop or // we reach the tail ResourceMark rm; Unique_Node_List wq; wq.push(n_loop->_head); for (uint next = 0; next < wq.size(); ++next) { Node *m = wq.at(next); if (m == n->in(0)) { ctrl_ok = true; continue; } assert(!has_ctrl(m), "should be CFG"); if (!n_loop->is_member(get_loop(m)) || m == n_loop->_tail) { ctrl_ok = false; break; } enqueue_cfg_uses(m, wq); if (wq.size() > 10) { ctrl_ok = false; break; } } } if (ctrl_ok) { // move the Store _igvn.replace_input_of(mem, LoopNode::LoopBackControl, mem); _igvn.replace_input_of(n, 0, n_loop->_head->as_Loop()->skip_strip_mined()->in(LoopNode _igvn.replace_input_of(n, MemNode::Memory, mem->in(LoopNode::EntryControl)); // Disconnect the phi now. An empty phi can confuse other // optimizations in this pass of loop opts. _igvn.replace_node(mem, mem->in(LoopNode::EntryControl)); n_loop->_body.yank(mem); set_ctrl_and_loop(n, n->in(0)); return n; } } } return NULL; } // Try moving a store out of a loop, right after the loop void PhaseIdealLoop::try_move_store_after_loop(Node* n) { if (n->is_Store() && n->in(0) != NULL) { Node *n_ctrl = get_ctrl(n); IdealLoopTree *n_loop = get_loop(n_ctrl); // Store must be in a loop if (n_loop != _ltree_root && !n_loop->_irreducible) { Node* address = n->in(MemNode::Address); Node* value = n->in(MemNode::ValueIn); IdealLoopTree* address_loop = get_loop(get_ctrl(address)); // address must be loop invariant if (!n_loop->is_member(address_loop)) { // Store must be last on this memory slice in the loop and // nothing in the loop must observe it Node* phi = NULL; for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { Node* u = n->fast_out(i); if (has_ctrl(u)) { // control use? IdealLoopTree *u_loop = get_loop(get_ctrl(u)); if (!n_loop->is_member(u_loop)) { continue; } if (u->is_Phi() && u->in(0) == n_loop->_head) { assert(_igvn.type(u) == Type::MEMORY, "bad phi"); // multiple phis on the same slice are possible if (phi != NULL) { return; } phi = u; continue; } } return; } if (phi != NULL) { // Nothing in the loop before the store (next iteration) // must observe the stored value bool mem_ok = true; { ResourceMark rm; Unique_Node_List wq; wq.push(phi); for (uint next = 0; next < wq.size() && mem_ok; ++next) { Node *m = wq.at(next); for (DUIterator_Fast imax, i = m->fast_outs(imax); i < imax && mem_ok; i++) { Node* u = m->fast_out(i); if (u->is_Store() || u->is_Phi()) { if (u != n) { wq.push(u); mem_ok = (wq.size() <= 10); } } else { mem_ok = false; break; } } } } if (mem_ok) { // Move the store out of the loop if the LCA of all // users (except for the phi) is outside the loop. Node* hook = new Node(1); hook->init_req(0, n_ctrl); // Add an input to prevent hook from being dead _igvn.rehash_node_delayed(phi); int count = phi->replace_edge(n, hook, &_igvn); assert(count > 0, "inconsistent phi"); // Compute latest point this store can go Node* lca = get_late_ctrl(n, get_ctrl(n)); if (lca->is_OuterStripMinedLoop()) { lca = lca->in(LoopNode::EntryControl); } if (n_loop->is_member(get_loop(lca))) { // LCA is in the loop - bail out _igvn.replace_node(hook, n); return; } #ifdef ASSERT if (n_loop->_head->is_Loop() && n_loop->_head->as_Loop()->is_strip_mined()) { assert(n_loop->_head->Opcode() == Op_CountedLoop, "outer loop is a strip mined"); n_loop->_head->as_Loop()->verify_strip_mined(1); Node* outer = n_loop->_head->as_CountedLoop()->outer_loop(); IdealLoopTree* outer_loop = get_loop(outer); assert(n_loop->_parent == outer_loop, "broken loop tree"); assert(get_loop(lca) == outer_loop, "safepoint in outer loop consume all memory sta } #endif lca = place_outside_loop(lca, n_loop); assert(!n_loop->is_member(get_loop(lca)), "control must not be back in the loop"); assert(get_loop(lca)->_nest < n_loop->_nest || lca->in(0)->Opcode() == Op_NeverBranch, "must // Move store out of the loop _igvn.replace_node(hook, n->in(MemNode::Memory)); _igvn.replace_input_of(n, 0, lca); set_ctrl_and_loop(n, lca); // Disconnect the phi now. An empty phi can confuse other // optimizations in this pass of loop opts.. if (phi->in(LoopNode::LoopBackControl) == phi) { _igvn.replace_node(phi, phi->in(LoopNode::EntryControl)); n_loop->_body.yank(phi); } } } } } } } //------------------------------split_if_with_blocks_pre----------------------- // Do the real work in a non-recursive function. Data nodes want to be // cloned in the pre-order so they can feed each other nicely. Node *PhaseIdealLoop::split_if_with_blocks_pre( Node *n ) { // Cloning these guys is unlikely to win int n_op = n->Opcode(); if (n_op == Op_MergeMem) { return n; } if (n->is_Proj()) { return n; } // Do not clone-up CmpFXXX variations, as these are always // followed by a CmpI if (n->is_Cmp()) { return n; } // Attempt to use a conditional move instead of a phi/branch if (ConditionalMoveLimit > 0 && n_op == Op_Region) { Node *cmov = conditional_move( n ); if (cmov) { return cmov; } } if (n->is_CFG() || n->is_LoadStore()) { return n; } if (n->is_Opaque1()) { // Opaque nodes cannot be mod'd if (!C->major_progress()) { // If chance of no more loop opts... _igvn._worklist.push(n); // maybe we'll remove them } return n; } if (n->is_Con()) { return n; // No cloning for Con nodes } Node *n_ctrl = get_ctrl(n); if (!n_ctrl) { return n; // Dead node } Node* res = try_move_store_before_loop(n, n_ctrl); if (res != NULL) { return n; } // Attempt to remix address expressions for loop invariants Node *m = remix_address_expressions( n ); if( m ) return m; if (n_op == Op_AddI) { Node *nn = convert_add_to_muladd( n ); if ( nn ) return nn; } if (n->is_ConstraintCast()) { Node* dom_cast = n->as_ConstraintCast()->dominating_cast(&_igvn, this); // ConstraintCastNode::dominating_cast() uses node control input to determine domination // Node control inputs don't necessarily agree with loop control info (due to // transformations happened in between), thus additional dominance check is needed // to keep loop info valid. if (dom_cast != NULL && is_dominator(get_ctrl(dom_cast), get_ctrl(n))) { _igvn.replace_node(n, dom_cast); return dom_cast; } } // Determine if the Node has inputs from some local Phi. // Returns the block to clone thru. Node *n_blk = has_local_phi_input( n ); if( !n_blk ) return n; // Do not clone the trip counter through on a CountedLoop // (messes up the canonical shape). if (((n_blk->is_CountedLoop() || (n_blk->is_Loop() && n_blk->as_Loop()->is_loop_nest_inner_ (n_blk->is_LongCountedLoop() && n->Opcode() == Op_AddL)) { return n; } // Pushing a shift through the iv Phi can get in the way of addressing optimizations or range chec if (n_blk->is_BaseCountedLoop() && n->Opcode() == Op_LShift(n_blk->as_BaseCountedLoop()->bt n->in(1) == n_blk->as_BaseCountedLoop()->phi()) { return n; } // Check for having no control input; not pinned. Allow // dominating control. if (n->in(0)) { Node *dom = idom(n_blk); if (dom_lca(n->in(0), dom) != n->in(0)) { return n; } } // Policy: when is it profitable. You must get more wins than // policy before it is considered profitable. Policy is usually 0, // so 1 win is considered profitable. Big merges will require big // cloning, so get a larger policy. int policy = n_blk->req() >> 2; // If the loop is a candidate for range check elimination, // delay splitting through it's phi until a later loop optimization if (n_blk->is_BaseCountedLoop()) { IdealLoopTree *lp = get_loop(n_blk); if (lp && lp->_rce_candidate) { return n; } } if (must_throttle_split_if()) return n; // Split 'n' through the merge point if it is profitable Node *phi = split_thru_phi( n, n_blk, policy ); if (!phi) return n; // Found a Phi to split thru! // Replace 'n' with the new phi _igvn.replace_node( n, phi ); // Moved a load around the loop, 'en-registering' something. if (n_blk->is_Loop() && n->is_Load() && !phi->in(LoopNode::LoopBackControl)->is_Load()) C->set_major_progress(); return phi; } static bool merge_point_too_heavy(Compile* C, Node* region) { // Bail out if the region and its phis have too many users. int weight = 0; for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { weight += region->fast_out(i)->outcnt(); } int nodes_left = C->max_node_limit() - C->live_nodes(); if (weight * 8 > nodes_left) { if (PrintOpto) { tty->print_cr("*** Split-if bails out: %d nodes, region weight %d", C->unique(), we } return true; } else { return false; } } static bool merge_point_safe(Node* region) { // 4799512: Stop split_if_with_blocks from splitting a block with a ConvI2LNode // having a PhiNode input. This sidesteps the dangerous case where the split // ConvI2LNode may become TOP if the input Value() does not // overlap the ConvI2L range, leaving a node which may not dominate its // uses. // A better fix for this problem can be found in the BugTraq entry, but // expediency for Mantis demands this hack. #ifdef _LP64 for (DUIterator_Fast imax, i = region->fast_outs(imax); i < imax; i++) { Node* n = region->fast_out(i); if (n->is_Phi()) { for (DUIterator_Fast jmax, j = n->fast_outs(jmax); j < jmax; j++) { Node* m = n->fast_out(j); if (m->Opcode() == Op_ConvI2L) return false; if (m->is_CastII()) { return false; } } } } #endif return true; } //------------------------------place_outside_loop------------------------------ // Place some computation outside of this loop on the path to the use passed as argument Node* PhaseIdealLoop::place_outside_loop(Node* useblock, IdealLoopTree* loop) const { Node* head = loop->_head; assert(!loop->is_member(get_loop(useblock)), "must be outside loop"); if (head->is_Loop() && head->as_Loop()->is_strip_mined()) { loop = loop->_parent; assert(loop->_head->is_OuterStripMinedLoop(), "malformed strip mined loop"); } // Pick control right outside the loop for (;;) { Node* dom = idom(useblock); if (loop->is_member(get_loop(dom)) || // NeverBranch nodes are not assigned to the loop when constructed (dom->Opcode() == Op_NeverBranch && loop->is_member(get_loop(dom->in(0))))) { break; } useblock = dom; } assert(find_non_split_ctrl(useblock) == useblock, "should be non split control"); return useblock; } bool PhaseIdealLoop::identical_backtoback_ifs(Node *n) { if (!n->is_If() || n->is_BaseCountedLoopEnd()) { return false; } if (!n->in(0)->is_Region()) { return false; } Node* region = n->in(0); Node* dom = idom(region); if (!dom->is_If() || dom->in(1) != n->in(1)) { return false; } IfNode* dom_if = dom->as_If(); Node* proj_true = dom_if->proj_out(1); Node* proj_false = dom_if->proj_out(0); for (uint i = 1; i < region->req(); i++) { if (is_dominator(proj_true, region->in(i))) { continue; } if (is_dominator(proj_false, region->in(i))) { continue; } return false; } return true; } bool PhaseIdealLoop::can_split_if(Node* n_ctrl) { if (must_throttle_split_if()) { return false; } // Do not do 'split-if' if irreducible loops are present. if (_has_irreducible_loops) { return false; } if (merge_point_too_heavy(C, n_ctrl)) { return false; } // Do not do 'split-if' if some paths are dead. First do dead code // elimination and then see if its still profitable. for (uint i = 1; i < n_ctrl->req(); i++) { if (n_ctrl->in(i) == C->top()) { return false; } } // If trying to do a 'Split-If' at the loop head, it is only // profitable if the cmp folds up on BOTH paths. Otherwise we // risk peeling a loop forever. // CNC - Disabled for now. Requires careful handling of loop // body selection for the cloned code. Also, make sure we check // for any input path not being in the same loop as n_ctrl. For // irreducible loops we cannot check for 'n_ctrl->is_Loop()' // because the alternative loop entry points won't be converted // into LoopNodes. IdealLoopTree *n_loop = get_loop(n_ctrl); for (uint j = 1; j < n_ctrl->req(); j++) { if (get_loop(n_ctrl->in(j)) != n_loop) { return false; } } // Check for safety of the merge point. if (!merge_point_safe(n_ctrl)) { return false; } return true; } // Detect if the node is the inner strip-mined loop // Return: NULL if it's not the case, or the exit of outer strip-mined loop static Node* is_inner_of_stripmined_loop(const Node* out) { Node* out_le = NULL; if (out->is_CountedLoopEnd()) { const CountedLoopNode* loop = out->as_CountedLoopEnd()->loopnode(); if (loop != NULL && loop->is_strip_mined()) { out_le = loop->in(LoopNode::EntryControl)->as_OuterStripMinedLoop()->outer_loop_exit( } } return out_le; } //------------------------------split_if_with_blocks_post---------------------- // Do the real work in a non-recursive function. CFG hackery wants to be // in the post-order, so it can dirty the I-DOM info and not use the dirtied // info. void PhaseIdealLoop::split_if_with_blocks_post(Node *n) { // Cloning Cmp through Phi's involves the split-if transform. // FastLock is not used by an If if (n->is_Cmp() && !n->is_FastLock()) { Node *n_ctrl = get_ctrl(n); // Determine if the Node has inputs from some local Phi. // Returns the block to clone thru. Node *n_blk = has_local_phi_input(n); if (n_blk != n_ctrl) { return; } if (!can_split_if(n_ctrl)) { return; } if (n->outcnt() != 1) { return; // Multiple bool's from 1 compare? } Node *bol = n->unique_out(); assert(bol->is_Bool(), "expect a bool here"); if (bol->outcnt() != 1) { return;// Multiple branches from 1 compare? } Node *iff = bol->unique_out(); // Check some safety conditions if (iff->is_If()) { // Classic split-if? if (iff->in(0) != n_ctrl) { return; // Compare must be in same blk as if } } else if (iff->is_CMove()) { // Trying to split-up a CMOVE // Can't split CMove with different control edge. if (iff->in(0) != NULL && iff->in(0) != n_ctrl ) { return; } if (get_ctrl(iff->in(2)) == n_ctrl || get_ctrl(iff->in(3)) == n_ctrl) { return; // Inputs not yet split-up } if (get_loop(n_ctrl) != get_loop(get_ctrl(iff))) { return; // Loop-invar test gates loop-varying CMOVE } } else { return; // some other kind of node, such as an Allocate } // When is split-if profitable? Every 'win' on means some control flow // goes dead, so it's almost always a win. int policy = 0; // Split compare 'n' through the merge point if it is profitable Node *phi = split_thru_phi( n, n_ctrl, policy); if (!phi) { return; } // Found a Phi to split thru! // Replace 'n' with the new phi _igvn.replace_node(n, phi); // Now split the bool up thru the phi Node *bolphi = split_thru_phi(bol, n_ctrl, -1); guarantee(bolphi != NULL, "null boolean phi node"); _igvn.replace_node(bol, bolphi); assert(iff->in(1) == bolphi, ""); if (bolphi->Value(&_igvn)->singleton()) { return; } // Conditional-move? Must split up now if (!iff->is_If()) { Node *cmovphi = split_thru_phi(iff, n_ctrl, -1); _igvn.replace_node(iff, cmovphi); return; } // Now split the IF do_split_if(iff); return; } // Two identical ifs back to back can be merged if (try_merge_identical_ifs(n)) { return; } // Check for an IF ready to split; one that has its // condition codes input coming from a Phi at the block start. int n_op = n->Opcode(); // Check for an IF being dominated by another IF same test if (n_op == Op_If || n_op == Op_RangeCheck) { Node *bol = n->in(1); uint max = bol->outcnt(); // Check for same test used more than once? if (max > 1 && bol->is_Bool()) { // Search up IDOMs to see if this IF is dominated. Node *cutoff = get_ctrl(bol); // Now search up IDOMs till cutoff, looking for a dominating test Node *prevdom = n; Node *dom = idom(prevdom); while (dom != cutoff) { if (dom->req() > 1 && dom->in(1) == bol && prevdom->in(0) == dom && safe_for_if_replacement(dom)) { // It's invalid to move control dependent data nodes in the inner // strip-mined loop, because: // 1) break validation of LoopNode::verify_strip_mined() // 2) move code with side-effect in strip-mined loop // Move to the exit of outer strip-mined loop in that case. Node* out_le = is_inner_of_stripmined_loop(dom); if (out_le != NULL) { prevdom = out_le; } // Replace the dominated test with an obvious true or false. // Place it on the IGVN worklist for later cleanup. C->set_major_progress(); dominated_by(prevdom->as_IfProj(), n->as_If(), false, true); #ifndef PRODUCT if( VerifyLoopOptimizations ) verify(); #endif return; } prevdom = dom; dom = idom(prevdom); } } } try_sink_out_of_loop(n); try_move_store_after_loop(n); } // Transform: // // if (some_condition) { // // body 1 // } else { // // body 2 // } // if (some_condition) { // // body 3 // } else { // // body 4 // } // // into: // // // if (some_condition) { // // body 1 // // body 3 // } else { // // body 2 // // body 4 // } bool PhaseIdealLoop::try_merge_identical_ifs(Node* n) { if (identical_backtoback_ifs(n) && can_split_if(n->in(0))) { Node *n_ctrl = n->in(0); IfNode* dom_if = idom(n_ctrl)->as_If(); ProjNode* dom_proj_true = dom_if->proj_out(1); ProjNode* dom_proj_false = dom_if->proj_out(0); // Now split the IF RegionNode* new_false_region; RegionNode* new_true_region; do_split_if(n, &new_false_region, &new_true_region); assert(new_false_region->req() == new_true_region->req(), ""); #ifdef ASSERT for (uint i = 1; i < new_false_region->req(); ++i) { assert(new_false_region->in(i)->in(0) == new_true_region->in(i)->in(0), "unexpected sha assert(i == new_false_region->req() - 1 || new_false_region->in(i)->in(0)->in(1) == new_fals } #endif assert(new_false_region->in(1)->in(0)->in(1) == dom_if->in(1), "dominating if and domin // We now have: // if (some_condition) { // // body 1 // if (some_condition) { // body3: // new_true_region // // body3 // } else { // goto body4; // } // } else { // // body 2 // if (some_condition) { // goto body3; // } else { // body4: // new_false_region // // body4; // } // } // // clone pinned nodes thru the resulting regions push_pinned_nodes_thru_region(dom_if, new_true_region); push_pinned_nodes_thru_region(dom_if, new_false_region); // Optimize out the cloned ifs. Because pinned nodes were cloned, this also allows a CastPP that // on a projection of n to have the dom_if as a control dependency. We don't want the CastPP to end u // unrelated control dependency. for (uint i = 1; i < new_false_region->req(); i++) { if (is_dominator(dom_proj_true, new_false_region->in(i))) { dominated_by(dom_proj_true->as_IfProj(), new_false_region->in(i)->in(0)->as_If(), fals } else { assert(is_dominator(dom_proj_false, new_false_region->in(i)), "bad if"); dominated_by(dom_proj_false->as_IfProj(), new_false_region->in(i)->in(0)->as_If(), fal } } return true; } return false; } void PhaseIdealLoop::push_pinned_nodes_thru_region(IfNode* dom_if, Node* region) { for (DUIterator i = region->outs(); region->has_out(i); i++) { Node* u = region->out(i); if (!has_ctrl(u) || u->is_Phi() || !u->depends_only_on_test() || !_igvn.no_dependent_zero continue; } assert(u->in(0) == region, "not a control dependent node?"); uint j = 1; for (; j < u->req(); ++j) { Node* in = u->in(j); if (!is_dominator(ctrl_or_self(in), dom_if)) { break; } } if (j == u->req()) { Node *phi = PhiNode::make_blank(region, u); for (uint k = 1; k < region->req(); ++k) { Node* clone = u->clone(); clone->set_req(0, region->in(k)); register_new_node(clone, region->in(k)); phi->init_req(k, clone); } register_new_node(phi, region); _igvn.replace_node(u, phi); --i; } } } bool PhaseIdealLoop::safe_for_if_replacement(const Node* dom) const { if (!dom->is_CountedLoopEnd()) { return true; } CountedLoopEndNode* le = dom->as_CountedLoopEnd(); CountedLoopNode* cl = le->loopnode(); if (cl == NULL) { return true; } if (!cl->is_main_loop()) { return true; } if (cl->is_canonical_loop_entry() == NULL) { return true; } // Further unrolling is possible so loop exit condition might change return false; } // See if a shared loop-varying computation has no loop-varying uses. // Happens if something is only used for JVM state in uncommon trap exits, // like various versions of induction variable+offset. Clone the // computation per usage to allow it to sink out of the loop. void PhaseIdealLoop::try_sink_out_of_loop(Node* n) { if (has_ctrl(n) && !n->is_Phi() && !n->is_Bool() && !n->is_Proj() && !n->is_MergeMem() && !n->is_CMove() && n->Opcode() != Op_Opaque4 && !n->is_Type()) { Node *n_ctrl = get_ctrl(n); IdealLoopTree *n_loop = get_loop(n_ctrl); if (n->in(0) != NULL) { IdealLoopTree* loop_ctrl = get_loop(n->in(0)); if (n_loop != loop_ctrl && n_loop->is_member(loop_ctrl)) { // n has a control input inside a loop but get_ctrl() is member of an outer loop. This could happen // for Div nodes inside a loop (control input inside loop) without a use except for an UCT (outsid // Rewire control of n to right outside of the loop, regardless if its input(s) are later sunk or n _igvn.replace_input_of(n, 0, place_outside_loop(n_ctrl, loop_ctrl)); } } if (n_loop != _ltree_root && n->outcnt() > 1) { // Compute early control: needed for anti-dependence analysis. It's also possible that as a re // previous transformations in this loop opts round, the node can be hoisted now: early control Node* early_ctrl = compute_early_ctrl(n, n_ctrl); if (n_loop->is_member(get_loop(early_ctrl)) && // check that this one can't be hoisted now ctrl_of_all_uses_out_of_loop(n, early_ctrl, n_loop)) { // All uses in outer loops! assert(!n->is_Store() && !n->is_LoadStore(), "no node with a side effect"); Node* outer_loop_clone = NULL; for (DUIterator_Last jmin, j = n->last_outs(jmin); j >= jmin;) { Node* u = n->last_out(j); // Clone private computation per use _igvn.rehash_node_delayed(u); Node* x = n->clone(); // Clone computation Node* x_ctrl = NULL; if (u->is_Phi()) { // Replace all uses of normal nodes. Replace Phi uses // individually, so the separate Nodes can sink down // different paths. uint k = 1; while (u->in(k) != n) k++; u->set_req(k, x); // x goes next to Phi input path x_ctrl = u->in(0)->in(k); // Find control for 'x' next to use but not inside inner loops. x_ctrl = place_outside_loop(x_ctrl, n_loop); --j; } else { // Normal use if (has_ctrl(u)) { x_ctrl = get_ctrl(u); } else { x_ctrl = u->in(0); } // Find control for 'x' next to use but not inside inner loops. x_ctrl = place_outside_loop(x_ctrl, n_loop); // Replace all uses if (u->is_ConstraintCast() && u->bottom_type()->higher_equal(_igvn.type(n)) && u->in(0) == x_ct // If we're sinking a chain of data nodes, we might have inserted a cast to pin the use which is not n // anymore now that we're going to pin n as well _igvn.replace_node(u, x); --j; } else { int nb = u->replace_edge(n, x, &_igvn); j -= nb; } } if (n->is_Load()) { // For loads, add a control edge to a CFG node outside of the loop // to force them to not combine and return back inside the loop // during GVN optimization (4641526). assert(x_ctrl == get_late_ctrl_with_anti_dep(x->as_Load(), early_ctrl, x_ctrl), "anti- IdealLoopTree* x_loop = get_loop(x_ctrl); Node* x_head = x_loop->_head; if (x_head->is_Loop() && x_head->is_OuterStripMinedLoop()) { // Do not add duplicate LoadNodes to the outer strip mined loop if (outer_loop_clone != NULL) { _igvn.replace_node(x, outer_loop_clone); continue; } outer_loop_clone = x; } x->set_req(0, x_ctrl); } else if (n->in(0) != NULL){ x->set_req(0, x_ctrl); } assert(dom_depth(n_ctrl) <= dom_depth(x_ctrl), "n is later than its clone"); assert(!n_loop->is_member(get_loop(x_ctrl)), "should have moved out of loop"); register_new_node(x, x_ctrl); // Chain of AddP: (AddP base (AddP base )) must keep the same base after sinking so: // 1- We don't add a CastPP here when the first one is sunk so if the second one is not, their bases re // the same. // (see 2- below) assert(!x->is_AddP() || !x->in(AddPNode::Address)->is_AddP() || x->in(AddPNode::Address)->in(AddPNode::Base) == x->in(AddPNode::Base) || !x->in(AddPNode::Address)->in(AddPNode::Base)->eqv_uncast(x->in(AddPNode::Base)), "un if (x->in(0) == NULL && !x->is_DecodeNarrowPtr() && !(x->is_AddP() && x->in(AddPNode::Address)->is_AddP() && x->in(AddPNode::Address)->in(AddPNod assert(!x->is_Load(), "load should be pinned"); // Use a cast node to pin clone out of loop Node* cast = NULL; for (uint k = 0; k < x->req(); k++) { Node* in = x->in(k); if (in != NULL && n_loop->is_member(get_loop(get_ctrl(in)))) { const Type* in_t = _igvn.type(in); cast = ConstraintCastNode::make_cast_for_type(x_ctrl, in, in_t, ConstraintCastNode::U } if (cast != NULL) { register_new_node(cast, x_ctrl); x->replace_edge(in, cast); // Chain of AddP: // 2- A CastPP of the base is only added now that both AddP nodes are sunk if (x->is_AddP() && k == AddPNode::Base) { for (DUIterator_Fast imax, i = x->fast_outs(imax); i < imax; i++) { Node* u = x->fast_out(i); if (u->is_AddP() && u->in(AddPNode::Base) == n->in(AddPNode::Base)) { _igvn.replace_input_of(u, AddPNode::Base, cast); assert(u->find_out_with(Op_AddP) == NULL, "more than 2 chained AddP nodes?"); } } } break; } } assert(cast != NULL, "must have added a cast to pin the node"); } } _igvn.remove_dead_node(n); } _dom_lca_tags_round = 0; } } } // Compute the early control of a node by following its inputs until we reach // nodes that are pinned. Then compute the LCA of the control of all pinned nodes. Node* PhaseIdealLoop::compute_early_ctrl(Node* n, Node* n_ctrl) { Node* early_ctrl = NULL; ResourceMark rm; Unique_Node_List wq; wq.push(n); for (uint i = 0; i < wq.size(); i++) { Node* m = wq.at(i); Node* c = NULL; if (m->is_CFG()) { c = m; } else if (m->pinned()) { c = m->in(0); } else { for (uint j = 0; j < m->req(); j++) { Node* in = m->in(j); if (in != NULL) { wq.push(in); } } } if (c != NULL) { assert(is_dominator(c, n_ctrl), "control input must dominate current control"); if (early_ctrl == NULL || is_dominator(early_ctrl, c)) { early_ctrl = c; } } } assert(is_dominator(early_ctrl, n_ctrl), "early control must dominate current cont return early_ctrl; } bool PhaseIdealLoop::ctrl_of_all_uses_out_of_loop(const Node* n, Node* n_ctrl, IdealLo for (DUIterator_Fast imax, i = n->fast_outs(imax); i < imax; i++) { Node* u = n->fast_out(i); if (u->is_Opaque1()) { return false; // Found loop limit, bugfix for 4677003 } // We can't reuse tags in PhaseIdealLoop::dom_lca_for_get_late_ctrl_internal() so make su // get_late_ctrl_with_anti_dep() use their own tag _dom_lca_tags_round++; assert(_dom_lca_tags_round != 0, "shouldn't wrap around"); if (u->is_Phi()) { for (uint j = 1; j < u->req(); ++j) { if (u->in(j) == n && !ctrl_of_use_out_of_loop(n, n_ctrl, n_loop, u->in(0)->in(j))) { return false; } } } else { Node* ctrl = has_ctrl(u) ? get_ctrl(u) : u->in(0); if (!ctrl_of_use_out_of_loop(n, n_ctrl, n_loop, ctrl)) { return false; } } } return true; } bool PhaseIdealLoop::ctrl_of_use_out_of_loop(const Node* n, Node* n_ctrl, IdealLoopTre if (n->is_Load()) { ctrl = get_late_ctrl_with_anti_dep(n->as_Load(), n_ctrl, ctrl); } IdealLoopTree *u_loop = get_loop(ctrl); if (u_loop == n_loop) { return false; // Found loop-varying use } --> -------------------- --> maximum size reached --> -------------------- ¤ Diese beiden folgenden Angebotsgruppen bietet das Unternehmen0.74Angebot Wie Sie bei der Firma Beratungs- und Dienstleistungen beauftragen können ¤ |
Lebenszyklus
Die hierunter aufgelisteten Ziele sind für diese Firma wichtig
ZieleEntwicklung einer Software für die statische QuellcodeanalyseBot Zugriff |
