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