1 /*
2 * Copyright (C) 2017 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 "code_sinking.h"
18
19 #include "base/arena_bit_vector.h"
20 #include "base/bit_vector-inl.h"
21 #include "base/scoped_arena_allocator.h"
22 #include "base/scoped_arena_containers.h"
23 #include "common_dominator.h"
24 #include "nodes.h"
25
26 namespace art {
27
Run()28 bool CodeSinking::Run() {
29 HBasicBlock* exit = graph_->GetExitBlock();
30 if (exit == nullptr) {
31 // Infinite loop, just bail.
32 return false;
33 }
34 // TODO(ngeoffray): we do not profile branches yet, so use throw instructions
35 // as an indicator of an uncommon branch.
36 for (HBasicBlock* exit_predecessor : exit->GetPredecessors()) {
37 HInstruction* last = exit_predecessor->GetLastInstruction();
38 // Any predecessor of the exit that does not return, throws an exception.
39 if (!last->IsReturn() && !last->IsReturnVoid()) {
40 SinkCodeToUncommonBranch(exit_predecessor);
41 }
42 }
43 return true;
44 }
45
IsInterestingInstruction(HInstruction * instruction)46 static bool IsInterestingInstruction(HInstruction* instruction) {
47 // Instructions from the entry graph (for example constants) are never interesting to move.
48 if (instruction->GetBlock() == instruction->GetBlock()->GetGraph()->GetEntryBlock()) {
49 return false;
50 }
51 // We want to move moveable instructions that cannot throw, as well as
52 // heap stores and allocations.
53
54 // Volatile stores cannot be moved.
55 if (instruction->IsInstanceFieldSet()) {
56 if (instruction->AsInstanceFieldSet()->IsVolatile()) {
57 return false;
58 }
59 }
60
61 // Check allocations and strings first, as they can throw, but it is safe to move them.
62 if (instruction->IsNewInstance() || instruction->IsNewArray() || instruction->IsLoadString()) {
63 return true;
64 }
65
66 // Check it is safe to move ConstructorFence.
67 // (Safe to move ConstructorFence for only protecting the new-instance but not for finals.)
68 if (instruction->IsConstructorFence()) {
69 HConstructorFence* ctor_fence = instruction->AsConstructorFence();
70
71 // A fence with "0" inputs is dead and should've been removed in a prior pass.
72 DCHECK_NE(0u, ctor_fence->InputCount());
73
74 // TODO: this should be simplified to 'return true' since it's
75 // potentially pessimizing any code sinking for inlined constructors with final fields.
76 // TODO: double check that if the final field assignments are not moved,
77 // then the fence is not moved either.
78
79 return ctor_fence->GetAssociatedAllocation() != nullptr;
80 }
81
82 // All other instructions that can throw cannot be moved.
83 if (instruction->CanThrow()) {
84 return false;
85 }
86
87 // We can only store on local allocations. Other heap references can
88 // be escaping. Note that allocations can escape too, but we only move
89 // allocations if their users can move to, or are in the list of
90 // post dominated blocks.
91 if (instruction->IsInstanceFieldSet()) {
92 if (!instruction->InputAt(0)->IsNewInstance()) {
93 return false;
94 }
95 }
96
97 if (instruction->IsArraySet()) {
98 if (!instruction->InputAt(0)->IsNewArray()) {
99 return false;
100 }
101 }
102
103 // Heap accesses cannot go pass instructions that have memory side effects, which
104 // we are not tracking here. Note that the load/store elimination optimization
105 // runs before this optimization, and should have removed interesting ones.
106 // In theory, we could handle loads of local allocations, but this is currently
107 // hard to test, as LSE removes them.
108 if (instruction->IsStaticFieldGet() ||
109 instruction->IsInstanceFieldGet() ||
110 instruction->IsPredicatedInstanceFieldGet() ||
111 instruction->IsArrayGet()) {
112 return false;
113 }
114
115 if (instruction->IsInstanceFieldSet() ||
116 instruction->IsArraySet() ||
117 instruction->CanBeMoved()) {
118 return true;
119 }
120 return false;
121 }
122
AddInstruction(HInstruction * instruction,const ArenaBitVector & processed_instructions,const ArenaBitVector & discard_blocks,ScopedArenaVector<HInstruction * > * worklist)123 static void AddInstruction(HInstruction* instruction,
124 const ArenaBitVector& processed_instructions,
125 const ArenaBitVector& discard_blocks,
126 ScopedArenaVector<HInstruction*>* worklist) {
127 // Add to the work list if the instruction is not in the list of blocks
128 // to discard, hasn't been already processed and is of interest.
129 if (!discard_blocks.IsBitSet(instruction->GetBlock()->GetBlockId()) &&
130 !processed_instructions.IsBitSet(instruction->GetId()) &&
131 IsInterestingInstruction(instruction)) {
132 worklist->push_back(instruction);
133 }
134 }
135
AddInputs(HInstruction * instruction,const ArenaBitVector & processed_instructions,const ArenaBitVector & discard_blocks,ScopedArenaVector<HInstruction * > * worklist)136 static void AddInputs(HInstruction* instruction,
137 const ArenaBitVector& processed_instructions,
138 const ArenaBitVector& discard_blocks,
139 ScopedArenaVector<HInstruction*>* worklist) {
140 for (HInstruction* input : instruction->GetInputs()) {
141 AddInstruction(input, processed_instructions, discard_blocks, worklist);
142 }
143 }
144
AddInputs(HBasicBlock * block,const ArenaBitVector & processed_instructions,const ArenaBitVector & discard_blocks,ScopedArenaVector<HInstruction * > * worklist)145 static void AddInputs(HBasicBlock* block,
146 const ArenaBitVector& processed_instructions,
147 const ArenaBitVector& discard_blocks,
148 ScopedArenaVector<HInstruction*>* worklist) {
149 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
150 AddInputs(it.Current(), processed_instructions, discard_blocks, worklist);
151 }
152 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
153 AddInputs(it.Current(), processed_instructions, discard_blocks, worklist);
154 }
155 }
156
ShouldFilterUse(HInstruction * instruction,HInstruction * user,const ArenaBitVector & post_dominated)157 static bool ShouldFilterUse(HInstruction* instruction,
158 HInstruction* user,
159 const ArenaBitVector& post_dominated) {
160 if (instruction->IsNewInstance()) {
161 return (user->IsInstanceFieldSet() || user->IsConstructorFence()) &&
162 (user->InputAt(0) == instruction) &&
163 !post_dominated.IsBitSet(user->GetBlock()->GetBlockId());
164 } else if (instruction->IsNewArray()) {
165 return (user->IsArraySet() || user->IsConstructorFence()) &&
166 (user->InputAt(0) == instruction) &&
167 !post_dominated.IsBitSet(user->GetBlock()->GetBlockId());
168 }
169 return false;
170 }
171
172
173 // Find the ideal position for moving `instruction`. If `filter` is true,
174 // we filter out store instructions to that instruction, which are processed
175 // first in the step (3) of the sinking algorithm.
176 // This method is tailored to the sinking algorithm, unlike
177 // the generic HInstruction::MoveBeforeFirstUserAndOutOfLoops.
FindIdealPosition(HInstruction * instruction,const ArenaBitVector & post_dominated,bool filter=false)178 static HInstruction* FindIdealPosition(HInstruction* instruction,
179 const ArenaBitVector& post_dominated,
180 bool filter = false) {
181 DCHECK(!instruction->IsPhi()); // Makes no sense for Phi.
182
183 // Find the target block.
184 CommonDominator finder(/* block= */ nullptr);
185 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
186 HInstruction* user = use.GetUser();
187 if (!(filter && ShouldFilterUse(instruction, user, post_dominated))) {
188 HBasicBlock* block = user->GetBlock();
189 if (user->IsPhi()) {
190 // Special case phis by taking the incoming block for regular ones,
191 // or the dominator for catch phis.
192 block = user->AsPhi()->IsCatchPhi()
193 ? block->GetDominator()
194 : block->GetPredecessors()[use.GetIndex()];
195 }
196 finder.Update(block);
197 }
198 }
199 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
200 DCHECK(!use.GetUser()->GetHolder()->IsPhi());
201 DCHECK(!filter || !ShouldFilterUse(instruction, use.GetUser()->GetHolder(), post_dominated));
202 finder.Update(use.GetUser()->GetHolder()->GetBlock());
203 }
204 HBasicBlock* target_block = finder.Get();
205 if (target_block == nullptr) {
206 // No user we can go next to? Likely a LSE or DCE limitation.
207 return nullptr;
208 }
209
210 // Move to the first dominator not in a loop, if we can.
211 while (target_block->IsInLoop()) {
212 if (!post_dominated.IsBitSet(target_block->GetDominator()->GetBlockId())) {
213 break;
214 }
215 target_block = target_block->GetDominator();
216 DCHECK(target_block != nullptr);
217 }
218
219 // Bail if the instruction can throw and we are about to move into a catch block.
220 if (instruction->CanThrow() && target_block->GetTryCatchInformation() != nullptr) {
221 return nullptr;
222 }
223
224 // Find insertion position. No need to filter anymore, as we have found a
225 // target block.
226 HInstruction* insert_pos = nullptr;
227 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
228 if (use.GetUser()->GetBlock() == target_block &&
229 (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) {
230 insert_pos = use.GetUser();
231 }
232 }
233 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
234 HInstruction* user = use.GetUser()->GetHolder();
235 if (user->GetBlock() == target_block &&
236 (insert_pos == nullptr || user->StrictlyDominates(insert_pos))) {
237 insert_pos = user;
238 }
239 }
240 if (insert_pos == nullptr) {
241 // No user in `target_block`, insert before the control flow instruction.
242 insert_pos = target_block->GetLastInstruction();
243 DCHECK(insert_pos->IsControlFlow());
244 // Avoid splitting HCondition from HIf to prevent unnecessary materialization.
245 if (insert_pos->IsIf()) {
246 HInstruction* if_input = insert_pos->AsIf()->InputAt(0);
247 if (if_input == insert_pos->GetPrevious()) {
248 insert_pos = if_input;
249 }
250 }
251 }
252 DCHECK(!insert_pos->IsPhi());
253 return insert_pos;
254 }
255
256
SinkCodeToUncommonBranch(HBasicBlock * end_block)257 void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) {
258 // Local allocator to discard data structures created below at the end of this optimization.
259 ScopedArenaAllocator allocator(graph_->GetArenaStack());
260
261 size_t number_of_instructions = graph_->GetCurrentInstructionId();
262 ScopedArenaVector<HInstruction*> worklist(allocator.Adapter(kArenaAllocMisc));
263 ArenaBitVector processed_instructions(&allocator, number_of_instructions, /* expandable= */ false);
264 processed_instructions.ClearAllBits();
265 ArenaBitVector post_dominated(&allocator, graph_->GetBlocks().size(), /* expandable= */ false);
266 post_dominated.ClearAllBits();
267 ArenaBitVector instructions_that_can_move(
268 &allocator, number_of_instructions, /* expandable= */ false);
269 instructions_that_can_move.ClearAllBits();
270 ScopedArenaVector<HInstruction*> move_in_order(allocator.Adapter(kArenaAllocMisc));
271
272 // Step (1): Visit post order to get a subset of blocks post dominated by `end_block`.
273 // TODO(ngeoffray): Getting the full set of post-dominated shoud be done by
274 // computint the post dominator tree, but that could be too time consuming. Also,
275 // we should start the analysis from blocks dominated by an uncommon branch, but we
276 // don't profile branches yet.
277 bool found_block = false;
278 for (HBasicBlock* block : graph_->GetPostOrder()) {
279 if (block == end_block) {
280 found_block = true;
281 post_dominated.SetBit(block->GetBlockId());
282 } else if (found_block) {
283 bool is_post_dominated = true;
284 if (block->GetSuccessors().empty()) {
285 // We currently bail for loops.
286 is_post_dominated = false;
287 } else {
288 for (HBasicBlock* successor : block->GetSuccessors()) {
289 if (!post_dominated.IsBitSet(successor->GetBlockId())) {
290 is_post_dominated = false;
291 break;
292 }
293 }
294 }
295 if (is_post_dominated) {
296 post_dominated.SetBit(block->GetBlockId());
297 }
298 }
299 }
300
301 // Now that we have found a subset of post-dominated blocks, add to the worklist all inputs
302 // of instructions in these blocks that are not themselves in these blocks.
303 // Also find the common dominator of the found post dominated blocks, to help filtering
304 // out un-movable uses in step (2).
305 CommonDominator finder(end_block);
306 for (size_t i = 0, e = graph_->GetBlocks().size(); i < e; ++i) {
307 if (post_dominated.IsBitSet(i)) {
308 finder.Update(graph_->GetBlocks()[i]);
309 AddInputs(graph_->GetBlocks()[i], processed_instructions, post_dominated, &worklist);
310 }
311 }
312 HBasicBlock* common_dominator = finder.Get();
313
314 // Step (2): iterate over the worklist to find sinking candidates.
315 while (!worklist.empty()) {
316 HInstruction* instruction = worklist.back();
317 if (processed_instructions.IsBitSet(instruction->GetId())) {
318 // The instruction has already been processed, continue. This happens
319 // when the instruction is the input/user of multiple instructions.
320 worklist.pop_back();
321 continue;
322 }
323 bool all_users_in_post_dominated_blocks = true;
324 bool can_move = true;
325 // Check users of the instruction.
326 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
327 HInstruction* user = use.GetUser();
328 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId()) &&
329 !instructions_that_can_move.IsBitSet(user->GetId())) {
330 all_users_in_post_dominated_blocks = false;
331 // If we've already processed this user, or the user cannot be moved, or
332 // is not dominating the post dominated blocks, bail.
333 // TODO(ngeoffray): The domination check is an approximation. We should
334 // instead check if the dominated blocks post dominate the user's block,
335 // but we do not have post dominance information here.
336 if (processed_instructions.IsBitSet(user->GetId()) ||
337 !IsInterestingInstruction(user) ||
338 !user->GetBlock()->Dominates(common_dominator)) {
339 can_move = false;
340 break;
341 }
342 }
343 }
344
345 // Check environment users of the instruction. Some of these users require
346 // the instruction not to move.
347 if (all_users_in_post_dominated_blocks) {
348 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
349 HEnvironment* environment = use.GetUser();
350 HInstruction* user = environment->GetHolder();
351 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId())) {
352 if (graph_->IsDebuggable() ||
353 user->IsDeoptimize() ||
354 user->CanThrowIntoCatchBlock() ||
355 (user->IsSuspendCheck() && graph_->IsCompilingOsr())) {
356 can_move = false;
357 break;
358 }
359 }
360 }
361 }
362 if (!can_move) {
363 // Instruction cannot be moved, mark it as processed and remove it from the work
364 // list.
365 processed_instructions.SetBit(instruction->GetId());
366 worklist.pop_back();
367 } else if (all_users_in_post_dominated_blocks) {
368 // Instruction is a candidate for being sunk. Mark it as such, remove it from the
369 // work list, and add its inputs to the work list.
370 instructions_that_can_move.SetBit(instruction->GetId());
371 move_in_order.push_back(instruction);
372 processed_instructions.SetBit(instruction->GetId());
373 worklist.pop_back();
374 AddInputs(instruction, processed_instructions, post_dominated, &worklist);
375 // Drop the environment use not in the list of post-dominated block. This is
376 // to help step (3) of this optimization, when we start moving instructions
377 // closer to their use.
378 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
379 HEnvironment* environment = use.GetUser();
380 HInstruction* user = environment->GetHolder();
381 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId())) {
382 environment->RemoveAsUserOfInput(use.GetIndex());
383 environment->SetRawEnvAt(use.GetIndex(), nullptr);
384 }
385 }
386 } else {
387 // The information we have on the users was not enough to decide whether the
388 // instruction could be moved.
389 // Add the users to the work list, and keep the instruction in the work list
390 // to process it again once all users have been processed.
391 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
392 AddInstruction(use.GetUser(), processed_instructions, post_dominated, &worklist);
393 }
394 }
395 }
396
397 // Make sure we process instructions in dominated order. This is required for heap
398 // stores.
399 std::sort(move_in_order.begin(), move_in_order.end(), [](HInstruction* a, HInstruction* b) {
400 return b->StrictlyDominates(a);
401 });
402
403 // Step (3): Try to move sinking candidates.
404 for (HInstruction* instruction : move_in_order) {
405 HInstruction* position = nullptr;
406 if (instruction->IsArraySet()
407 || instruction->IsInstanceFieldSet()
408 || instruction->IsConstructorFence()) {
409 if (!instructions_that_can_move.IsBitSet(instruction->InputAt(0)->GetId())) {
410 // A store can trivially move, but it can safely do so only if the heap
411 // location it stores to can also move.
412 // TODO(ngeoffray): Handle allocation/store cycles by pruning these instructions
413 // from the set and all their inputs.
414 continue;
415 }
416 // Find the position of the instruction we're storing into, filtering out this
417 // store and all other stores to that instruction.
418 position = FindIdealPosition(instruction->InputAt(0), post_dominated, /* filter= */ true);
419
420 // The position needs to be dominated by the store, in order for the store to move there.
421 if (position == nullptr || !instruction->GetBlock()->Dominates(position->GetBlock())) {
422 continue;
423 }
424 } else {
425 // Find the ideal position within the post dominated blocks.
426 position = FindIdealPosition(instruction, post_dominated);
427 if (position == nullptr) {
428 continue;
429 }
430 }
431 // Bail if we could not find a position in the post dominated blocks (for example,
432 // if there are multiple users whose common dominator is not in the list of
433 // post dominated blocks).
434 if (!post_dominated.IsBitSet(position->GetBlock()->GetBlockId())) {
435 continue;
436 }
437 MaybeRecordStat(stats_, MethodCompilationStat::kInstructionSunk);
438 instruction->MoveBefore(position, /* do_checks= */ false);
439 }
440 }
441
442 } // namespace art
443