286  * of an existing value range, NewArray or a loop phi corresponding to an
487   const int32_t increment_;         // Increment for each loop iteration.
505   // Added blocks for loop body entry test.
563     // Clear the loop data structures.
615       // Make sure the comparison is in the loop header so each increment is
635       // Comparison needs to be in loop header to make sure it's done after each
711           // if it's not defined in the loop header.
906       // Try loop-based dynamic elimination.
907       HLoopInformation* loop = bounds_check->GetBlock()->GetLoopInformation();
910       if (DynamicBCESeemsProfitable(loop, bounds_check->GetBlock()) &&
913           CanHandleInfiniteLoop(loop, index, needs_finite_test) &&
915           CanHandleLength(loop, array_length, needs_taken_test)) {
916         TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
917         TransformLoopForDynamicBCE(loop, bounds_check);
1032     // such as the inner loop 'for (int j=0; j<array.length-i; j++)' where i
1033     // is the index for outer loop. In this case, we know j is bounded by array.length-1.
1230     * may be exposed underneath which can be hoisted out of the loop to the
1241     * unsafe to hoist array references across their deoptimization instruction inside a loop.
1245       HLoopInformation* loop = array_get->GetBlock()->GetLoopInformation();
1246       if (loop->IsDefinedOutOfTheLoop(array_get->InputAt(0)) &&
1247           loop->IsDefinedOutOfTheLoop(array_get->InputAt(1))) {
1248         SideEffects loop_effects = side_effects_.GetLoopEffects(loop->GetHeader());
1252           if (loop->DominatesAllBackEdges(array_get->GetBlock())) {
1253             HoistToPreHeaderOrDeoptBlock(loop, array_get);
1404         // use analysis for static bce only if loop is finite.
1417    * Performs loop-based dynamic elimination on a bounds check. In order to minimize the
1421   void TransformLoopForDynamicBCE(HLoopInformation* loop, HBoundsCheck* bounds_check) {
1424     DCHECK(loop->IsDefinedOutOfTheLoop(array_length));  // pre-checked
1425     DCHECK(loop->DominatesAllBackEdges(bounds_check->GetBlock()));
1426     // Collect all bounds checks in the same loop that are related as "a[base + constant]"
1438       if (user->IsBoundsCheck() && loop == user->GetBlock()->GetLoopInformation()) {
1452           if (!loop->DominatesAllBackEdges(user->GetBlock())) {
1470     // Perform loop-based deoptimization if it seems profitable, where we eliminate bounds
1476       HBasicBlock* block = GetPreHeader(loop, bounds_check);
1490           // It handles either loop invariants (lower is not set) or unit strides.
1522               loop, block, new (GetGraph()->GetAllocator()) HAbove(min_upper, max_upper));
1533               loop, block, new (GetGraph()->GetAllocator()) HAbove(min_lower, max_lower));
1539             loop, block, new (GetGraph()->GetAllocator()) HAbove(max_lower, max_upper));
1542           loop, block, new (GetGraph()->GetAllocator()) HAboveOrEqual(max_upper, array_length));
1551   bool DynamicBCESeemsProfitable(HLoopInformation* loop, HBasicBlock* block) {
1552     if (loop != nullptr) {
1553       // The loop preheader of an irreducible loop does not dominate all the blocks in
1554       // the loop. We would need to find the common dominator of all blocks in the loop.
1555       if (loop->IsIrreducible()) {
1565       if (loop->GetPreHeader()->GetLastInstruction()->IsTryBoundary()) {
1568       // Does loop have early-exits? If so, the full range may not be covered by the loop
1570       if (IsEarlyExitLoop(loop)) {
1575       return loop->DominatesAllBackEdges(block);
1581    * Returns true if the loop has early exits, which implies it may not cover
1584   bool IsEarlyExitLoop(HLoopInformation* loop) {
1585     const uint32_t loop_id = loop->GetHeader()->GetBlockId();
1586     // If loop has been analyzed earlier for early-exit, don't repeat the analysis.
1591     // First time early-exit analysis for this loop. Since analysis requires scanning
1592     // the full loop-body, results of the analysis is stored for subsequent queries.
1593     HBlocksInLoopReversePostOrderIterator it_loop(*loop);
1596         if (!loop->Contains(*successor)) {
1607    * Returns true if the array length is already loop invariant, or can be made so
1610   bool CanHandleLength(HLoopInformation* loop, HInstruction* length, bool needs_taken_test) {
1611     if (loop->IsDefinedOutOfTheLoop(length)) {
1613     } else if (length->IsArrayLength() && length->GetBlock()->GetLoopInformation() == loop) {
1614       if (CanHandleNullCheck(loop, length->InputAt(0), needs_taken_test)) {
1615         HoistToPreHeaderOrDeoptBlock(loop, length);
1623    * Returns true if the null check is already loop invariant, or can be made so
1626   bool CanHandleNullCheck(HLoopInformation* loop, HInstruction* check, bool needs_taken_test) {
1627     if (loop->IsDefinedOutOfTheLoop(check)) {
1629     } else if (check->IsNullCheck() && check->GetBlock()->GetLoopInformation() == loop) {
1631       if (loop->IsDefinedOutOfTheLoop(array)) {
1633         TransformLoopForDeoptimizationIfNeeded(loop, needs_taken_test);
1634         HBasicBlock* block = GetPreHeader(loop, check);
1637         InsertDeoptInLoop(loop, block, cond, /* is_null_check */ true);
1650    * of the loop to use, dynamic bce in such cases is only allowed if other tests
1651    * ensure the loop is finite.
1653   bool CanHandleInfiniteLoop(HLoopInformation* loop, HInstruction* index, bool needs_infinite_test) {
1655       // If we already forced the loop to be finite, allow directly.
1656       const uint32_t loop_id = loop->GetHeader()->GetBlockId();
1661       // this point) is the direct loop index (viz. a[i]), since then the runtime tests
1662       // ensure upper bound cannot cause an infinite loop.
1663       HInstruction* control = loop->GetHeader()->GetLastInstruction();
1681    * Returns appropriate preheader for the loop, depending on whether the
1682    * instruction appears in the loop header or proper loop-body.
1684   HBasicBlock* GetPreHeader(HLoopInformation* loop, HInstruction* instruction) {
1687     HBasicBlock* header = loop->GetHeader();
1699     return loop->GetPreHeader();
1702   /** Inserts a deoptimization test in a loop preheader. */
1703   void InsertDeoptInLoop(HLoopInformation* loop,
1707     HInstruction* suspend = loop->GetSuspendCheck();
1716           suspend->GetEnvironment(), loop->GetHeader());
1733   /** Hoists instruction out of the loop to preheader or deoptimization block. */
1734   void HoistToPreHeaderOrDeoptBlock(HLoopInformation* loop, HInstruction* instruction) {
1735     HBasicBlock* block = GetPreHeader(loop, instruction);
1741    * Adds a new taken-test structure to a loop if needed and not already done.
1755    * For example, this loop:
1776   void TransformLoopForDeoptimizationIfNeeded(HLoopInformation* loop, bool needs_taken_test) {
1778     const uint32_t loop_id = loop->GetHeader()->GetBlockId();
1784     HBasicBlock* header = loop->GetHeader();
1786     HBasicBlock* new_preheader = loop->GetPreHeader();
1796     // Insert the taken-test to see if the loop body is entered. If the
1797     // loop isn't entered at all, it jumps around the deoptimization block.
1810    * All uses of instructions in the deoptimization block that reach the loop need
1811    * a phi node in the new loop preheader to fix the dominance relation.
1914   // Early-exit loop bookkeeping.
1917   // Taken-test loop bookkeeping.
1920   // Finite loop bookkeeping.

Indexes created Sun Aug 12 02:23:12 CEST 2018