Home | History | Annotate | Download | only in optimizing 
      1 /*
      2  * Copyright (C) 2015 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 #include "licm.h"
     18 
     19 #include "side_effects_analysis.h"
     20 
     21 namespace art {
     22 
     23 static bool IsPhiOf(HInstruction* instruction, HBasicBlock* block) {
     24   return instruction->IsPhi() && instruction->GetBlock() == block;
     25 }
     26 
     27 /**
     28  * Returns whether `instruction` has all its inputs and environment defined
     29  * before the loop it is in.
     30  */
     31 static bool InputsAreDefinedBeforeLoop(HInstruction* instruction) {
     32   DCHECK(instruction->IsInLoop());
     33   HLoopInformation* info = instruction->GetBlock()->GetLoopInformation();
     34   for (const HInstruction* input : instruction->GetInputs()) {
     35     HLoopInformation* input_loop = input->GetBlock()->GetLoopInformation();
     36     // We only need to check whether the input is defined in the loop. If it is not
     37     // it is defined before the loop.
     38     if (input_loop != nullptr && input_loop->IsIn(*info)) {
     39       return false;
     40     }
     41   }
     42 
     43   for (HEnvironment* environment = instruction->GetEnvironment();
     44        environment != nullptr;
     45        environment = environment->GetParent()) {
     46     for (size_t i = 0, e = environment->Size(); i < e; ++i) {
     47       HInstruction* input = environment->GetInstructionAt(i);
     48       if (input != nullptr) {
     49         HLoopInformation* input_loop = input->GetBlock()->GetLoopInformation();
     50         if (input_loop != nullptr && input_loop->IsIn(*info)) {
     51           // We can move an instruction that takes a loop header phi in the environment:
     52           // we will just replace that phi with its first input later in `UpdateLoopPhisIn`.
     53           bool is_loop_header_phi = IsPhiOf(input, info->GetHeader());
     54           if (!is_loop_header_phi) {
     55             return false;
     56           }
     57         }
     58       }
     59     }
     60   }
     61   return true;
     62 }
     63 
     64 /**
     65  * If `environment` has a loop header phi, we replace it with its first input.
     66  */
     67 static void UpdateLoopPhisIn(HEnvironment* environment, HLoopInformation* info) {
     68   for (; environment != nullptr; environment = environment->GetParent()) {
     69     for (size_t i = 0, e = environment->Size(); i < e; ++i) {
     70       HInstruction* input = environment->GetInstructionAt(i);
     71       if (input != nullptr && IsPhiOf(input, info->GetHeader())) {
     72         environment->RemoveAsUserOfInput(i);
     73         HInstruction* incoming = input->InputAt(0);
     74         environment->SetRawEnvAt(i, incoming);
     75         incoming->AddEnvUseAt(environment, i);
     76       }
     77     }
     78   }
     79 }
     80 
     81 void LICM::Run() {
     82   DCHECK(side_effects_.HasRun());
     83 
     84   // Only used during debug.
     85   ArenaBitVector* visited = nullptr;
     86   if (kIsDebugBuild) {
     87     visited = new (graph_->GetAllocator()) ArenaBitVector(graph_->GetAllocator(),
     88                                                           graph_->GetBlocks().size(),
     89                                                           false,
     90                                                           kArenaAllocLICM);
     91   }
     92 
     93   // Post order visit to visit inner loops before outer loops.
     94   for (HBasicBlock* block : graph_->GetPostOrder()) {
     95     if (!block->IsLoopHeader()) {
     96       // Only visit the loop when we reach the header.
     97       continue;
     98     }
     99 
    100     HLoopInformation* loop_info = block->GetLoopInformation();
    101     SideEffects loop_effects = side_effects_.GetLoopEffects(block);
    102     HBasicBlock* pre_header = loop_info->GetPreHeader();
    103 
    104     for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
    105       HBasicBlock* inner = it_loop.Current();
    106       DCHECK(inner->IsInLoop());
    107       if (inner->GetLoopInformation() != loop_info) {
    108         // Thanks to post order visit, inner loops were already visited.
    109         DCHECK(visited->IsBitSet(inner->GetBlockId()));
    110         continue;
    111       }
    112       if (kIsDebugBuild) {
    113         visited->SetBit(inner->GetBlockId());
    114       }
    115 
    116       if (loop_info->ContainsIrreducibleLoop()) {
    117         // We cannot licm in an irreducible loop, or in a natural loop containing an
    118         // irreducible loop.
    119         continue;
    120       }
    121       DCHECK(!loop_info->IsIrreducible());
    122 
    123       // We can move an instruction that can throw only as long as it is the first visible
    124       // instruction (throw or write) in the loop. Note that the first potentially visible
    125       // instruction that is not hoisted stops this optimization. Non-throwing instructions,
    126       // on the other hand, can still be hoisted.
    127       bool found_first_non_hoisted_visible_instruction_in_loop = !inner->IsLoopHeader();
    128       for (HInstructionIterator inst_it(inner->GetInstructions());
    129            !inst_it.Done();
    130            inst_it.Advance()) {
    131         HInstruction* instruction = inst_it.Current();
    132         bool can_move = false;
    133         if (instruction->CanBeMoved() && InputsAreDefinedBeforeLoop(instruction)) {
    134           if (instruction->CanThrow()) {
    135             if (!found_first_non_hoisted_visible_instruction_in_loop) {
    136               DCHECK(instruction->GetBlock()->IsLoopHeader());
    137               if (instruction->IsClinitCheck()) {
    138                 // clinit is only done once, and since all visible instructions
    139                 // in the loop header so far have been hoisted out, we can hoist
    140                 // the clinit check out also.
    141                 can_move = true;
    142               } else if (!instruction->GetSideEffects().MayDependOn(loop_effects)) {
    143                 can_move = true;
    144               }
    145             }
    146           } else if (!instruction->GetSideEffects().MayDependOn(loop_effects)) {
    147             can_move = true;
    148           }
    149         }
    150         if (can_move) {
    151           // We need to update the environment if the instruction has a loop header
    152           // phi in it.
    153           if (instruction->NeedsEnvironment()) {
    154             UpdateLoopPhisIn(instruction->GetEnvironment(), loop_info);
    155           } else {
    156             DCHECK(!instruction->HasEnvironment());
    157           }
    158           instruction->MoveBefore(pre_header->GetLastInstruction());
    159           MaybeRecordStat(stats_, MethodCompilationStat::kLoopInvariantMoved);
    160         }
    161 
    162         if (!can_move && (instruction->CanThrow() || instruction->DoesAnyWrite())) {
    163           // If `instruction` can do something visible (throw or write),
    164           // we cannot move further instructions that can throw.
    165           found_first_non_hoisted_visible_instruction_in_loop = true;
    166         }
    167       }
    168     }
    169   }
    170 }
    171 
    172 }  // namespace art
    173