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 <sstream>
20
21 #include "android-base/logging.h"
22 #include "base/arena_bit_vector.h"
23 #include "base/array_ref.h"
24 #include "base/bit_vector-inl.h"
25 #include "base/globals.h"
26 #include "base/logging.h"
27 #include "base/scoped_arena_allocator.h"
28 #include "base/scoped_arena_containers.h"
29 #include "common_dominator.h"
30 #include "nodes.h"
31
32 namespace art HIDDEN {
33
Run()34 bool CodeSinking::Run() {
35 if (graph_->GetExitBlock() == nullptr) {
36 // Infinite loop, just bail.
37 return false;
38 }
39
40 UncommonBranchSinking();
41 ReturnSinking();
42 return true;
43 }
44
UncommonBranchSinking()45 void CodeSinking::UncommonBranchSinking() {
46 HBasicBlock* exit = graph_->GetExitBlock();
47 DCHECK(exit != nullptr);
48 // TODO(ngeoffray): we do not profile branches yet, so use throw instructions
49 // as an indicator of an uncommon branch.
50 for (HBasicBlock* exit_predecessor : exit->GetPredecessors()) {
51 HInstruction* last = exit_predecessor->GetLastInstruction();
52
53 // TryBoundary instructions are sometimes inserted between the last instruction (e.g. Throw,
54 // Return) and Exit. We don't want to use that instruction for our "uncommon branch" heuristic
55 // because they are not as good an indicator as throwing branches, so we skip them and fetch the
56 // actual last instruction.
57 if (last->IsTryBoundary()) {
58 // We have an exit try boundary. Fetch the previous instruction.
59 DCHECK(!last->AsTryBoundary()->IsEntry());
60 if (last->GetPrevious() == nullptr) {
61 DCHECK(exit_predecessor->IsSingleTryBoundary());
62 exit_predecessor = exit_predecessor->GetSinglePredecessor();
63 last = exit_predecessor->GetLastInstruction();
64 } else {
65 last = last->GetPrevious();
66 }
67 }
68
69 // Any predecessor of the exit that does not return, throws an exception.
70 if (!last->IsReturn() && !last->IsReturnVoid()) {
71 SinkCodeToUncommonBranch(exit_predecessor);
72 }
73 }
74 }
75
IsInterestingInstruction(HInstruction * instruction)76 static bool IsInterestingInstruction(HInstruction* instruction) {
77 // Instructions from the entry graph (for example constants) are never interesting to move.
78 if (instruction->GetBlock() == instruction->GetBlock()->GetGraph()->GetEntryBlock()) {
79 return false;
80 }
81 // We want to move moveable instructions that cannot throw, as well as
82 // heap stores and allocations.
83
84 // Volatile stores cannot be moved.
85 if (instruction->IsInstanceFieldSet()) {
86 if (instruction->AsInstanceFieldSet()->IsVolatile()) {
87 return false;
88 }
89 }
90
91 // Check allocations and strings first, as they can throw, but it is safe to move them.
92 if (instruction->IsNewInstance() || instruction->IsNewArray() || instruction->IsLoadString()) {
93 return true;
94 }
95
96 // Check it is safe to move ConstructorFence.
97 // (Safe to move ConstructorFence for only protecting the new-instance but not for finals.)
98 if (instruction->IsConstructorFence()) {
99 HConstructorFence* ctor_fence = instruction->AsConstructorFence();
100
101 // A fence with "0" inputs is dead and should've been removed in a prior pass.
102 DCHECK_NE(0u, ctor_fence->InputCount());
103
104 // TODO: this should be simplified to 'return true' since it's
105 // potentially pessimizing any code sinking for inlined constructors with final fields.
106 // TODO: double check that if the final field assignments are not moved,
107 // then the fence is not moved either.
108
109 return ctor_fence->GetAssociatedAllocation() != nullptr;
110 }
111
112 // All other instructions that can throw cannot be moved.
113 if (instruction->CanThrow()) {
114 return false;
115 }
116
117 // We can only store on local allocations. Other heap references can
118 // be escaping. Note that allocations can escape too, but we only move
119 // allocations if their users can move too, or are in the list of
120 // post dominated blocks.
121 if (instruction->IsInstanceFieldSet()) {
122 if (!instruction->InputAt(0)->IsNewInstance()) {
123 return false;
124 }
125 }
126
127 if (instruction->IsArraySet()) {
128 if (!instruction->InputAt(0)->IsNewArray()) {
129 return false;
130 }
131 }
132
133 // Heap accesses cannot go past instructions that have memory side effects, which
134 // we are not tracking here. Note that the load/store elimination optimization
135 // runs before this optimization, and should have removed interesting ones.
136 // In theory, we could handle loads of local allocations, but this is currently
137 // hard to test, as LSE removes them.
138 if (instruction->IsStaticFieldGet() ||
139 instruction->IsInstanceFieldGet() ||
140 instruction->IsArrayGet()) {
141 return false;
142 }
143
144 if (instruction->IsInstanceFieldSet() ||
145 instruction->IsArraySet() ||
146 instruction->CanBeMoved()) {
147 return true;
148 }
149 return false;
150 }
151
AddInstruction(HInstruction * instruction,const ArenaBitVector & processed_instructions,const ArenaBitVector & discard_blocks,ScopedArenaVector<HInstruction * > * worklist)152 static void AddInstruction(HInstruction* instruction,
153 const ArenaBitVector& processed_instructions,
154 const ArenaBitVector& discard_blocks,
155 ScopedArenaVector<HInstruction*>* worklist) {
156 // Add to the work list if the instruction is not in the list of blocks
157 // to discard, hasn't been already processed and is of interest.
158 if (!discard_blocks.IsBitSet(instruction->GetBlock()->GetBlockId()) &&
159 !processed_instructions.IsBitSet(instruction->GetId()) &&
160 IsInterestingInstruction(instruction)) {
161 worklist->push_back(instruction);
162 }
163 }
164
AddInputs(HInstruction * instruction,const ArenaBitVector & processed_instructions,const ArenaBitVector & discard_blocks,ScopedArenaVector<HInstruction * > * worklist)165 static void AddInputs(HInstruction* instruction,
166 const ArenaBitVector& processed_instructions,
167 const ArenaBitVector& discard_blocks,
168 ScopedArenaVector<HInstruction*>* worklist) {
169 for (HInstruction* input : instruction->GetInputs()) {
170 AddInstruction(input, processed_instructions, discard_blocks, worklist);
171 }
172 }
173
AddInputs(HBasicBlock * block,const ArenaBitVector & processed_instructions,const ArenaBitVector & discard_blocks,ScopedArenaVector<HInstruction * > * worklist)174 static void AddInputs(HBasicBlock* block,
175 const ArenaBitVector& processed_instructions,
176 const ArenaBitVector& discard_blocks,
177 ScopedArenaVector<HInstruction*>* worklist) {
178 for (HInstructionIterator it(block->GetPhis()); !it.Done(); it.Advance()) {
179 AddInputs(it.Current(), processed_instructions, discard_blocks, worklist);
180 }
181 for (HInstructionIterator it(block->GetInstructions()); !it.Done(); it.Advance()) {
182 AddInputs(it.Current(), processed_instructions, discard_blocks, worklist);
183 }
184 }
185
ShouldFilterUse(HInstruction * instruction,HInstruction * user,const ArenaBitVector & post_dominated)186 static bool ShouldFilterUse(HInstruction* instruction,
187 HInstruction* user,
188 const ArenaBitVector& post_dominated) {
189 if (instruction->IsNewInstance()) {
190 return (user->IsInstanceFieldSet() || user->IsConstructorFence()) &&
191 (user->InputAt(0) == instruction) &&
192 !post_dominated.IsBitSet(user->GetBlock()->GetBlockId());
193 } else if (instruction->IsNewArray()) {
194 return (user->IsArraySet() || user->IsConstructorFence()) &&
195 (user->InputAt(0) == instruction) &&
196 !post_dominated.IsBitSet(user->GetBlock()->GetBlockId());
197 }
198 return false;
199 }
200
201 // Find the ideal position for moving `instruction`. If `filter` is true,
202 // we filter out store instructions to that instruction, which are processed
203 // first in the step (3) of the sinking algorithm.
204 // This method is tailored to the sinking algorithm, unlike
205 // the generic HInstruction::MoveBeforeFirstUserAndOutOfLoops.
FindIdealPosition(HInstruction * instruction,const ArenaBitVector & post_dominated,bool filter=false)206 static HInstruction* FindIdealPosition(HInstruction* instruction,
207 const ArenaBitVector& post_dominated,
208 bool filter = false) {
209 DCHECK(!instruction->IsPhi()); // Makes no sense for Phi.
210
211 // Find the target block.
212 CommonDominator finder(/* block= */ nullptr);
213 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
214 HInstruction* user = use.GetUser();
215 if (!(filter && ShouldFilterUse(instruction, user, post_dominated))) {
216 HBasicBlock* block = user->GetBlock();
217 if (user->IsPhi()) {
218 // Special case phis by taking the incoming block for regular ones,
219 // or the dominator for catch phis.
220 block = user->AsPhi()->IsCatchPhi()
221 ? block->GetDominator()
222 : block->GetPredecessors()[use.GetIndex()];
223 }
224 finder.Update(block);
225 }
226 }
227 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
228 DCHECK(!use.GetUser()->GetHolder()->IsPhi());
229 DCHECK_IMPLIES(filter,
230 !ShouldFilterUse(instruction, use.GetUser()->GetHolder(), post_dominated));
231 finder.Update(use.GetUser()->GetHolder()->GetBlock());
232 }
233 HBasicBlock* target_block = finder.Get();
234 if (target_block == nullptr) {
235 // No user we can go next to? Likely a LSE or DCE limitation.
236 return nullptr;
237 }
238
239 // Move to the first dominator not in a loop, if we can. We only do this if we are trying to hoist
240 // `instruction` out of a loop it wasn't a part of.
241 const HLoopInformation* loop_info = instruction->GetBlock()->GetLoopInformation();
242 while (target_block->IsInLoop() && target_block->GetLoopInformation() != loop_info) {
243 if (!post_dominated.IsBitSet(target_block->GetDominator()->GetBlockId())) {
244 break;
245 }
246 target_block = target_block->GetDominator();
247 DCHECK(target_block != nullptr);
248 }
249
250 if (instruction->CanThrow()) {
251 // Consistency check: We shouldn't land in a loop if we weren't in one before traversing up the
252 // dominator tree regarding try catches.
253 const bool was_in_loop = target_block->IsInLoop();
254
255 // We cannot move an instruction that can throw into a try that said instruction is not a part
256 // of already, as that would mean it will throw into a different catch block. In short, for
257 // throwing instructions:
258 // * If the throwing instruction is part of a try, they should only be sunk into that same try.
259 // * If the throwing instruction is not part of any try, they shouldn't be sunk to any try.
260 if (instruction->GetBlock()->IsTryBlock()) {
261 const HTryBoundary& try_entry =
262 instruction->GetBlock()->GetTryCatchInformation()->GetTryEntry();
263 while (!(target_block->IsTryBlock() &&
264 try_entry.HasSameExceptionHandlersAs(
265 target_block->GetTryCatchInformation()->GetTryEntry()))) {
266 target_block = target_block->GetDominator();
267 if (!post_dominated.IsBitSet(target_block->GetBlockId())) {
268 // We couldn't find a suitable block.
269 return nullptr;
270 }
271 }
272 } else {
273 // Search for the first block also not in a try block
274 while (target_block->IsTryBlock()) {
275 target_block = target_block->GetDominator();
276 if (!post_dominated.IsBitSet(target_block->GetBlockId())) {
277 // We couldn't find a suitable block.
278 return nullptr;
279 }
280 }
281 }
282
283 DCHECK_IMPLIES(target_block->IsInLoop(), was_in_loop);
284 }
285
286 // Find insertion position. No need to filter anymore, as we have found a
287 // target block.
288 HInstruction* insert_pos = nullptr;
289 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
290 if (use.GetUser()->GetBlock() == target_block &&
291 (insert_pos == nullptr || use.GetUser()->StrictlyDominates(insert_pos))) {
292 insert_pos = use.GetUser();
293 }
294 }
295 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
296 HEnvironment* env = use.GetUser();
297 HInstruction* user = env->GetHolder();
298 if (user->GetBlock() == target_block &&
299 (insert_pos == nullptr || user->StrictlyDominates(insert_pos))) {
300 if (target_block->IsCatchBlock() && target_block->GetFirstInstruction() == user) {
301 // We can sink the instructions past the environment setting Nop. If we do that, we have to
302 // remove said instruction from the environment. Since we know that we will be sinking the
303 // instruction to this block and there are no more instructions to consider, we can safely
304 // remove it from the environment now.
305 DCHECK(target_block->GetFirstInstruction()->IsNop());
306 env->RemoveAsUserOfInput(use.GetIndex());
307 env->SetRawEnvAt(use.GetIndex(), /*instruction=*/ nullptr);
308 } else {
309 insert_pos = user;
310 }
311 }
312 }
313 if (insert_pos == nullptr) {
314 // No user in `target_block`, insert before the control flow instruction.
315 insert_pos = target_block->GetLastInstruction();
316 DCHECK(insert_pos->IsControlFlow());
317 // Avoid splitting HCondition from HIf to prevent unnecessary materialization.
318 if (insert_pos->IsIf()) {
319 HInstruction* if_input = insert_pos->AsIf()->InputAt(0);
320 if (if_input == insert_pos->GetPrevious()) {
321 insert_pos = if_input;
322 }
323 }
324 }
325 DCHECK(!insert_pos->IsPhi());
326 return insert_pos;
327 }
328
329
SinkCodeToUncommonBranch(HBasicBlock * end_block)330 void CodeSinking::SinkCodeToUncommonBranch(HBasicBlock* end_block) {
331 // Local allocator to discard data structures created below at the end of this optimization.
332 ScopedArenaAllocator allocator(graph_->GetArenaStack());
333
334 size_t number_of_instructions = graph_->GetCurrentInstructionId();
335 ScopedArenaVector<HInstruction*> worklist(allocator.Adapter(kArenaAllocMisc));
336 ArenaBitVector processed_instructions(
337 &allocator, number_of_instructions, /* expandable= */ false);
338 ArenaBitVector post_dominated(&allocator, graph_->GetBlocks().size(), /* expandable= */ false);
339
340 // Step (1): Visit post order to get a subset of blocks post dominated by `end_block`.
341 // TODO(ngeoffray): Getting the full set of post-dominated should be done by
342 // computing the post dominator tree, but that could be too time consuming. Also,
343 // we should start the analysis from blocks dominated by an uncommon branch, but we
344 // don't profile branches yet.
345 bool found_block = false;
346 for (HBasicBlock* block : graph_->GetPostOrder()) {
347 if (block == end_block) {
348 found_block = true;
349 post_dominated.SetBit(block->GetBlockId());
350 } else if (found_block) {
351 bool is_post_dominated = true;
352 DCHECK_NE(block, graph_->GetExitBlock())
353 << "We shouldn't encounter the exit block after `end_block`.";
354
355 // BasicBlock that are try entries look like this:
356 // BasicBlock i:
357 // instr 1
358 // ...
359 // instr N
360 // TryBoundary kind:entry ---Try begins here---
361 //
362 // Due to how our BasicBlocks are structured, BasicBlock i will have an xhandler successor
363 // since we are starting a try. If we use `GetSuccessors` for this case, we will check if
364 // the catch block is post_dominated.
365 //
366 // However, this catch block doesn't matter: when we sink the instruction into that
367 // BasicBlock i, we do it before the TryBoundary (i.e. outside of the try and outside the
368 // catch's domain). We can ignore catch blocks using `GetNormalSuccessors` to sink code
369 // right before the start of a try block.
370 //
371 // On the other side of the coin, BasicBlock that are try exits look like this:
372 // BasicBlock j:
373 // instr 1
374 // ...
375 // instr N
376 // TryBoundary kind:exit ---Try ends here---
377 //
378 // If we sink to these basic blocks we would be sinking inside of the try so we would like
379 // to check the catch block for post dominance.
380 const bool ends_with_try_boundary_entry =
381 block->EndsWithTryBoundary() && block->GetLastInstruction()->AsTryBoundary()->IsEntry();
382 ArrayRef<HBasicBlock* const> successors =
383 ends_with_try_boundary_entry ? block->GetNormalSuccessors() :
384 ArrayRef<HBasicBlock* const>(block->GetSuccessors());
385 for (HBasicBlock* successor : successors) {
386 if (!post_dominated.IsBitSet(successor->GetBlockId())) {
387 is_post_dominated = false;
388 break;
389 }
390 }
391 if (is_post_dominated) {
392 post_dominated.SetBit(block->GetBlockId());
393 }
394 }
395 }
396
397 // Now that we have found a subset of post-dominated blocks, add to the worklist all inputs
398 // of instructions in these blocks that are not themselves in these blocks.
399 // Also find the common dominator of the found post dominated blocks, to help filtering
400 // out un-movable uses in step (2).
401 CommonDominator finder(end_block);
402 for (size_t i = 0, e = graph_->GetBlocks().size(); i < e; ++i) {
403 if (post_dominated.IsBitSet(i)) {
404 finder.Update(graph_->GetBlocks()[i]);
405 AddInputs(graph_->GetBlocks()[i], processed_instructions, post_dominated, &worklist);
406 }
407 }
408 HBasicBlock* common_dominator = finder.Get();
409
410 // Step (2): iterate over the worklist to find sinking candidates.
411 ArenaBitVector instructions_that_can_move(
412 &allocator, number_of_instructions, /* expandable= */ false);
413 ScopedArenaVector<ScopedArenaVector<HInstruction*>> instructions_to_move(
414 graph_->GetBlocks().size(),
415 ScopedArenaVector<HInstruction*>(allocator.Adapter(kArenaAllocMisc)),
416 allocator.Adapter(kArenaAllocMisc));
417 while (!worklist.empty()) {
418 HInstruction* instruction = worklist.back();
419 if (processed_instructions.IsBitSet(instruction->GetId())) {
420 // The instruction has already been processed, continue. This happens
421 // when the instruction is the input/user of multiple instructions.
422 worklist.pop_back();
423 continue;
424 }
425 bool all_users_in_post_dominated_blocks = true;
426 bool can_move = true;
427 // Check users of the instruction.
428 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
429 HInstruction* user = use.GetUser();
430 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId()) &&
431 !instructions_that_can_move.IsBitSet(user->GetId())) {
432 all_users_in_post_dominated_blocks = false;
433 // If we've already processed this user, or the user cannot be moved, or
434 // is not dominating the post dominated blocks, bail.
435 // TODO(ngeoffray): The domination check is an approximation. We should
436 // instead check if the dominated blocks post dominate the user's block,
437 // but we do not have post dominance information here.
438 if (processed_instructions.IsBitSet(user->GetId()) ||
439 !IsInterestingInstruction(user) ||
440 !user->GetBlock()->Dominates(common_dominator)) {
441 can_move = false;
442 break;
443 }
444 }
445 }
446
447 // Check environment users of the instruction. Some of these users require
448 // the instruction not to move.
449 if (all_users_in_post_dominated_blocks) {
450 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
451 HEnvironment* environment = use.GetUser();
452 HInstruction* user = environment->GetHolder();
453 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId())) {
454 if (graph_->IsDebuggable() ||
455 user->IsDeoptimize() ||
456 user->CanThrowIntoCatchBlock() ||
457 (user->IsSuspendCheck() && graph_->IsCompilingOsr())) {
458 can_move = false;
459 break;
460 }
461 }
462 }
463 }
464 if (!can_move) {
465 // Instruction cannot be moved, mark it as processed and remove it from the work
466 // list.
467 processed_instructions.SetBit(instruction->GetId());
468 worklist.pop_back();
469 } else if (all_users_in_post_dominated_blocks) {
470 // Instruction is a candidate for being sunk. Mark it as such, remove it from the
471 // work list, and add its inputs to the work list.
472 instructions_that_can_move.SetBit(instruction->GetId());
473 instructions_to_move[instruction->GetBlock()->GetBlockId()].push_back(instruction);
474 processed_instructions.SetBit(instruction->GetId());
475 worklist.pop_back();
476 AddInputs(instruction, processed_instructions, post_dominated, &worklist);
477 // Drop the environment use not in the list of post-dominated block. This is
478 // to help step (3) of this optimization, when we start moving instructions
479 // closer to their use.
480 for (const HUseListNode<HEnvironment*>& use : instruction->GetEnvUses()) {
481 HEnvironment* environment = use.GetUser();
482 HInstruction* user = environment->GetHolder();
483 if (!post_dominated.IsBitSet(user->GetBlock()->GetBlockId())) {
484 environment->RemoveAsUserOfInput(use.GetIndex());
485 environment->SetRawEnvAt(use.GetIndex(), nullptr);
486 }
487 }
488 } else {
489 // The information we have on the users was not enough to decide whether the
490 // instruction could be moved.
491 // Add the users to the work list, and keep the instruction in the work list
492 // to process it again once all users have been processed.
493 for (const HUseListNode<HInstruction*>& use : instruction->GetUses()) {
494 AddInstruction(use.GetUser(), processed_instructions, post_dominated, &worklist);
495 }
496 }
497 }
498
499 // We want to process the instructions in reverse dominated order. This is required for heap
500 // stores. To guarantee this (including the transitivity of incomparability) we have some extra
501 // bookkeeping.
502 ScopedArenaVector<HInstruction*> instructions_to_move_sorted(allocator.Adapter(kArenaAllocMisc));
503 for (HBasicBlock* block : graph_->GetPostOrder()) {
504 const int block_id = block->GetBlockId();
505
506 // Order the block itself first.
507 std::sort(instructions_to_move[block_id].begin(),
508 instructions_to_move[block_id].end(),
509 [&block](HInstruction* a, HInstruction* b) {
510 return block->GetInstructions().FoundBefore(b, a);
511 });
512
513 for (HInstruction* instruction : instructions_to_move[block_id]) {
514 instructions_to_move_sorted.push_back(instruction);
515 }
516 }
517
518 if (kIsDebugBuild) {
519 // We should have ordered the instructions in reverse dominated order. This means that
520 // instructions shouldn't dominate instructions that come after it in the vector.
521 for (size_t i = 0; i < instructions_to_move_sorted.size(); ++i) {
522 for (size_t j = i + 1; j < instructions_to_move_sorted.size(); ++j) {
523 if (instructions_to_move_sorted[i]->StrictlyDominates(instructions_to_move_sorted[j])) {
524 std::stringstream ss;
525 graph_->Dump(ss, nullptr);
526 ss << "\n"
527 << "{";
528 for (HInstruction* instr : instructions_to_move_sorted) {
529 ss << *instr << " in block: " << instr->GetBlock() << ", ";
530 }
531 ss << "}\n";
532 ss << "i = " << i << " which is " << *instructions_to_move_sorted[i]
533 << "strictly dominates j = " << j << " which is " << *instructions_to_move_sorted[j]
534 << "\n";
535 LOG(FATAL) << "Unexpected ordering of code sinking instructions: " << ss.str();
536 }
537 }
538 }
539 }
540
541 // Step (3): Try to move sinking candidates.
542 for (HInstruction* instruction : instructions_to_move_sorted) {
543 HInstruction* position = nullptr;
544 if (instruction->IsArraySet()
545 || instruction->IsInstanceFieldSet()
546 || instruction->IsConstructorFence()) {
547 if (!instructions_that_can_move.IsBitSet(instruction->InputAt(0)->GetId())) {
548 // A store can trivially move, but it can safely do so only if the heap
549 // location it stores to can also move.
550 // TODO(ngeoffray): Handle allocation/store cycles by pruning these instructions
551 // from the set and all their inputs.
552 continue;
553 }
554 // Find the position of the instruction we're storing into, filtering out this
555 // store and all other stores to that instruction.
556 position = FindIdealPosition(instruction->InputAt(0), post_dominated, /* filter= */ true);
557
558 // The position needs to be dominated by the store, in order for the store to move there.
559 if (position == nullptr || !instruction->GetBlock()->Dominates(position->GetBlock())) {
560 continue;
561 }
562 } else {
563 // Find the ideal position within the post dominated blocks.
564 position = FindIdealPosition(instruction, post_dominated);
565 if (position == nullptr) {
566 continue;
567 }
568 }
569 // Bail if we could not find a position in the post dominated blocks (for example,
570 // if there are multiple users whose common dominator is not in the list of
571 // post dominated blocks).
572 if (!post_dominated.IsBitSet(position->GetBlock()->GetBlockId())) {
573 continue;
574 }
575 MaybeRecordStat(stats_, MethodCompilationStat::kInstructionSunk);
576 instruction->MoveBefore(position, /* do_checks= */ false);
577 }
578 }
579
ReturnSinking()580 void CodeSinking::ReturnSinking() {
581 HBasicBlock* exit = graph_->GetExitBlock();
582 DCHECK(exit != nullptr);
583
584 int number_of_returns = 0;
585 bool saw_return = false;
586 for (HBasicBlock* pred : exit->GetPredecessors()) {
587 // TODO(solanes): We might have Return/ReturnVoid->TryBoundary->Exit. We can theoretically
588 // handle them and move them out of the TryBoundary. However, it is a border case and it adds
589 // codebase complexity.
590 if (pred->GetLastInstruction()->IsReturn() || pred->GetLastInstruction()->IsReturnVoid()) {
591 saw_return |= pred->GetLastInstruction()->IsReturn();
592 ++number_of_returns;
593 }
594 }
595
596 if (number_of_returns < 2) {
597 // Nothing to do.
598 return;
599 }
600
601 // `new_block` will coalesce the Return instructions into Phi+Return, or the ReturnVoid
602 // instructions into a ReturnVoid.
603 HBasicBlock* new_block = new (graph_->GetAllocator()) HBasicBlock(graph_, exit->GetDexPc());
604 if (saw_return) {
605 HPhi* new_phi = nullptr;
606 for (size_t i = 0; i < exit->GetPredecessors().size(); /*++i in loop*/) {
607 HBasicBlock* pred = exit->GetPredecessors()[i];
608 if (!pred->GetLastInstruction()->IsReturn()) {
609 ++i;
610 continue;
611 }
612
613 HReturn* ret = pred->GetLastInstruction()->AsReturn();
614 if (new_phi == nullptr) {
615 // Create the new_phi, if we haven't done so yet. We do it here since we need to know the
616 // type to assign to it.
617 new_phi = new (graph_->GetAllocator()) HPhi(graph_->GetAllocator(),
618 kNoRegNumber,
619 /*number_of_inputs=*/0,
620 ret->InputAt(0)->GetType());
621 new_block->AddPhi(new_phi);
622 }
623 new_phi->AddInput(ret->InputAt(0));
624 pred->ReplaceAndRemoveInstructionWith(ret,
625 new (graph_->GetAllocator()) HGoto(ret->GetDexPc()));
626 pred->ReplaceSuccessor(exit, new_block);
627 // Since we are removing a predecessor, there's no need to increment `i`.
628 }
629 new_block->AddInstruction(new (graph_->GetAllocator()) HReturn(new_phi, exit->GetDexPc()));
630 } else {
631 for (size_t i = 0; i < exit->GetPredecessors().size(); /*++i in loop*/) {
632 HBasicBlock* pred = exit->GetPredecessors()[i];
633 if (!pred->GetLastInstruction()->IsReturnVoid()) {
634 ++i;
635 continue;
636 }
637
638 HReturnVoid* ret = pred->GetLastInstruction()->AsReturnVoid();
639 pred->ReplaceAndRemoveInstructionWith(ret,
640 new (graph_->GetAllocator()) HGoto(ret->GetDexPc()));
641 pred->ReplaceSuccessor(exit, new_block);
642 // Since we are removing a predecessor, there's no need to increment `i`.
643 }
644 new_block->AddInstruction(new (graph_->GetAllocator()) HReturnVoid(exit->GetDexPc()));
645 }
646
647 new_block->AddSuccessor(exit);
648 graph_->AddBlock(new_block);
649
650 // Recompute dominance since we added a new block.
651 graph_->ClearDominanceInformation();
652 graph_->ComputeDominanceInformation();
653 }
654
655 } // namespace art
656