loopPredicate.cpp revision 2433
1008N/A * Copyright (c) 2011, Oracle and/or its affiliates. All rights reserved. 1008N/A * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 1008N/A * This code is free software; you can redistribute it and/or modify it 1008N/A * under the terms of the GNU General Public License version 2 only, as 1008N/A * published by the Free Software Foundation. 1008N/A * This code is distributed in the hope that it will be useful, but WITHOUT 1008N/A * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 1008N/A * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1008N/A * version 2 for more details (a copy is included in the LICENSE file that 1008N/A * You should have received a copy of the GNU General Public License version 1008N/A * 2 along with this work; if not, write to the Free Software Foundation, 1008N/A * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 1008N/A * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 1008N/A * The general idea of Loop Predication is to insert a predicate on the entry 1008N/A * path to a loop, and raise a uncommon trap if the check of the condition fails. 1008N/A * The condition checks are promoted from inside the loop body, and thus 1008N/A * the checks inside the loop could be eliminated. Currently, loop predication 1008N/A * optimization has been applied to remove array range check and loop invariant 1008N/A * checks (such as null checks). 1008N/A//-------------------------------is_uncommon_trap_proj---------------------------- 1008N/A// Return true if proj is the form of "proj->[region->..]call_uct" 1008N/A return false;
// don't do further after call 1008N/A//-------------------------------is_uncommon_trap_if_pattern------------------------- 1008N/A// Return true for "if(test)-> proj -> ... 1008N/A// other_proj->[region->..]call_uct" 1008N/A// "must_reason_predicate" means the uct reason must be Reason_predicate 1008N/A // Variation of a dead If node. 1008N/A // we need "If(Conv2B(Opaque1(...)))" pattern for reason_predicate 1008N/A//-------------------------------register_control------------------------- 1008N/A // When called from beautify_loops() idom is not constructed yet. 1008N/A//------------------------------create_new_if_for_predicate------------------------ 1008N/A// create a new if above the uct_if_pattern for the predicate to be promoted. 1008N/A// uncommon_proj cont_proj if_uct if_cont 1008N/A// uncommon_trap | uncommon_proj cont_proj 1008N/A// We will create a region to guard the uct call if there is no one there. 1008N/A// The true projecttion (if_cont) of the new_iff is returned. 1008N/A// This code is also used to clone predicates to clonned loops. if (!
rgn->
is_Region()) {
// create a region to guard the call // When called from beautify_loops() idom is not constructed yet. // Find region's edge corresponding to uncommon_proj // Clonning the predicate to new location. // When called from beautify_loops() idom is not constructed yet. // If rgn has phis add new edges which has the same // value as on original uncommon_proj pass. //------------------------------create_new_if_for_predicate------------------------ // Create a new if below new_entry for the predicate to be cloned (IGVN optimization) if (!
rgn->
is_Region()) {
// create a region to guard the call // Find region's edge corresponding to uncommon_proj // Create new_iff in new location. // If rgn has phis add corresponding new edges which has the same // value as on original uncommon_proj pass. //--------------------------clone_predicate----------------------- // Match original condition since predicate's projections could be swapped. //--------------------------move_predicate----------------------- // Cut predicate from old place and move it to new. // Cut predicate from old place. // When called from beautify_loops() idom is not constructed yet. i -=
uses_found;
// we deleted 1 or more copies of this edge // When called from beautify_loops() idom is not constructed yet. //--------------------------clone_loop_predicates----------------------- // Interface from PhaseIdealLoop // Clone loop predicates to cloned loops (peeled, unswitched, split_if). assert(
false,
"not IfTrue, IfFalse, Region or SafePoint");
// Search original predicates //--------------------------eliminate_loop_predicates----------------------- // Remove Opaque1 node from predicates list. // IGVN will remove this predicate check. //--------------------------skip_loop_predicates------------------------------ // Skip related predicates. if (
predicate !=
NULL) {
// right pattern that can be used by loop predication //--------------------------find_predicate_insertion_point------------------- // Find a good location to insert a predicate //--------------------------find_predicate------------------------------------ if (
predicate !=
NULL) {
// right pattern that can be used by loop predication //------------------------------Invariance----------------------------------- // Helper class for loop_predication_impl to compute invariance on the fly and // Helper function to set up the invariance for invariance computation // If n is a known invariant, set up directly. Otherwise, look up the // the possibility to push n onto the stack for further processing. // Compute invariance for "the_node" and (possibly) all its inputs recursively if (
idx == n->
req()) {
// all inputs are processed // n is invariant if it's inputs are all invariant for (
uint i = 0; i < n->
req(); i++) {
}
else {
// process next input // Helper function to set up _old_new map for clone_nodes. // If n is a known invariant, set up directly ("clone" of n == n). // Otherwise, push n onto the stack for real cloning. // Clone "n" and (possibly) all its inputs recursively if (
idx == n->
req()) {
// all inputs processed, clone n! for (
uint i = 0; i < n->
req(); i++) {
}
else {
// process next input // Map old to n for invariance computation and clone // Driver function to compute invariance // Driver function to clone invariant //------------------------------is_range_check_if ----------------------------------- // Returns true if the predicate of iff is in "scale*iv + offset u< load_range(ptr)" format // Note: this function is particularly designed for loop predication. We require load_range // and offset to be loop invariant computed on the fly by "invar" // Allow predication on positive values that aren't LoadRanges. // This allows optimization of loops where the length of the // array is a known value and doesn't need to be loaded back //------------------------------rc_predicate----------------------------------- // Create a range check predicate // for (i = init; i < limit; i += stride) { // Compute max(scale*i + offset) for init <= i < limit and build the predicate // as "max(scale*i + offset) u< a.length". // There are two cases for max(scale*i + offset): // max(scale*i + offset) = scale*(limit-stride) + offset // max(scale*i + offset) = scale*init + offset //------------------------------ loop_predication_impl-------------------------- // Insert loop predicates for null checks and range checks // Could be a simple region when irreducible loops are present. // do nothing for infinite loops // do nothing for iteration-splitted loops // Create list of if-projs such that a newer proj dominates all older // projs in the list, and they all dominate loop->tail() bool hoisted =
false;
// true if at least one proj is promoted // Following are changed to nonnull when a predicate can be hoisted // stop processing the remaining projs in the list because the execution of them // depends on the condition of "iff" (iff->in(1)). // Both arms are inside the loop. There are two cases: // (1) there is one backward branch. In this case, any remaining proj // in the if_proj list post-dominates "iff". So, the condition of "iff" // does not determine the execution the remining projs directly, and we // (2) both arms are forwarded, i.e. a diamond shape. In this case, "proj" // does not dominate loop->tail(), so it can not be in the if_proj list. // Negate test if necessary // Range check for counted loops // Build if's for the upper and lower bound tests. The // lower_bound test will dominate the upper bound test and all // cloned or created nodes will use the lower bound test as // their declared control. // Perform cloning to keep Invariance state correct since the // late schedule will place invariant things in the loop. // Fall through into rest of the clean up code which will move // any dependent nodes onto the upper bound test. // Loop variant check (for example, range check in non-counted loop) // Success - attach condition (new_predicate_bol) to predicate if // Eliminate the old If in the loop body // report that the loop predication has been actually performed tty->
print(
"Loop Predication Performed:");
//------------------------------loop_predication-------------------------------- // driver routine for loop predication optimization // Recursively promote predicates