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