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 
IsPhiOf(HInstruction * instruction,HBasicBlock * block)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  */
InputsAreDefinedBeforeLoop(HInstruction * instruction)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  */
UpdateLoopPhisIn(HEnvironment * environment,HLoopInformation * info)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 
Run()81 bool LICM::Run() {
82   bool didLICM = false;
83   DCHECK(side_effects_.HasRun());
84 
85   // Only used during debug.
86   ArenaBitVector* visited = nullptr;
87   if (kIsDebugBuild) {
88     visited = new (graph_->GetAllocator()) ArenaBitVector(graph_->GetAllocator(),
89                                                           graph_->GetBlocks().size(),
90                                                           false,
91                                                           kArenaAllocLICM);
92   }
93 
94   // Post order visit to visit inner loops before outer loops.
95   for (HBasicBlock* block : graph_->GetPostOrder()) {
96     if (!block->IsLoopHeader()) {
97       // Only visit the loop when we reach the header.
98       continue;
99     }
100 
101     HLoopInformation* loop_info = block->GetLoopInformation();
102     SideEffects loop_effects = side_effects_.GetLoopEffects(block);
103     HBasicBlock* pre_header = loop_info->GetPreHeader();
104 
105     for (HBlocksInLoopIterator it_loop(*loop_info); !it_loop.Done(); it_loop.Advance()) {
106       HBasicBlock* inner = it_loop.Current();
107       DCHECK(inner->IsInLoop());
108       if (inner->GetLoopInformation() != loop_info) {
109         // Thanks to post order visit, inner loops were already visited.
110         DCHECK(visited->IsBitSet(inner->GetBlockId()));
111         continue;
112       }
113       if (kIsDebugBuild) {
114         visited->SetBit(inner->GetBlockId());
115       }
116 
117       if (loop_info->ContainsIrreducibleLoop()) {
118         // We cannot licm in an irreducible loop, or in a natural loop containing an
119         // irreducible loop.
120         continue;
121       }
122       DCHECK(!loop_info->IsIrreducible());
123 
124       // We can move an instruction that can throw only as long as it is the first visible
125       // instruction (throw or write) in the loop. Note that the first potentially visible
126       // instruction that is not hoisted stops this optimization. Non-throwing instructions,
127       // on the other hand, can still be hoisted.
128       bool found_first_non_hoisted_visible_instruction_in_loop = !inner->IsLoopHeader();
129       for (HInstructionIterator inst_it(inner->GetInstructions());
130            !inst_it.Done();
131            inst_it.Advance()) {
132         HInstruction* instruction = inst_it.Current();
133         bool can_move = false;
134         if (instruction->CanBeMoved() && InputsAreDefinedBeforeLoop(instruction)) {
135           if (instruction->CanThrow()) {
136             if (!found_first_non_hoisted_visible_instruction_in_loop) {
137               DCHECK(instruction->GetBlock()->IsLoopHeader());
138               if (instruction->IsClinitCheck()) {
139                 // clinit is only done once, and since all visible instructions
140                 // in the loop header so far have been hoisted out, we can hoist
141                 // the clinit check out also.
142                 can_move = true;
143               } else if (!instruction->GetSideEffects().MayDependOn(loop_effects)) {
144                 can_move = true;
145               }
146             }
147           } else if (!instruction->GetSideEffects().MayDependOn(loop_effects)) {
148             can_move = true;
149           }
150         }
151         if (can_move) {
152           // We need to update the environment if the instruction has a loop header
153           // phi in it.
154           if (instruction->NeedsEnvironment()) {
155             UpdateLoopPhisIn(instruction->GetEnvironment(), loop_info);
156           } else {
157             DCHECK(!instruction->HasEnvironment());
158           }
159           instruction->MoveBefore(pre_header->GetLastInstruction());
160           MaybeRecordStat(stats_, MethodCompilationStat::kLoopInvariantMoved);
161           didLICM = true;
162         }
163 
164         if (!can_move && (instruction->CanThrow() || instruction->DoesAnyWrite())) {
165           // If `instruction` can do something visible (throw or write),
166           // we cannot move further instructions that can throw.
167           found_first_non_hoisted_visible_instruction_in_loop = true;
168         }
169       }
170     }
171   }
172   return didLICM;
173 }
174 
175 }  // namespace art
176