1 files changed, 36 insertions, 5 deletions

diff --git a/compiler/optimizing/nodes.cc b/compiler/optimizing/nodes.cc
index 2cfe5b3ae2..e6cb3a2379 100644
--- a/compiler/optimizing/nodes.cc
+++ b/compiler/optimizing/nodes.cc
@@ -1575,14 +1575,46 @@ void HInstruction::ReplaceWith(HInstruction* other) {
 void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
                                           HInstruction* replacement,
                                           bool strictly_dominated) {
+  // Get the dominated blocks first to faster calculation of domination afterwards.
+  HGraph* graph = GetBlock()->GetGraph();
+  ArenaBitVector visited_blocks(graph->GetAllocator(),
+                                graph->GetBlocks().size(),
+                                /* expandable= */ false,
+                                kArenaAllocMisc);
+  visited_blocks.ClearAllBits();
+  ScopedArenaAllocator allocator(graph->GetArenaStack());
+  ScopedArenaQueue<const HBasicBlock*> worklist(allocator.Adapter(kArenaAllocMisc));
+  HBasicBlock* dominator_block = dominator->GetBlock();
+  worklist.push(dominator_block);
+
+  while (!worklist.empty()) {
+    const HBasicBlock* current = worklist.front();
+    worklist.pop();
+    visited_blocks.SetBit(current->GetBlockId());
+    for (HBasicBlock* dominated : current->GetDominatedBlocks()) {
+      if (visited_blocks.IsBitSet(dominated->GetBlockId())) {
+        continue;
+      }
+      worklist.push(dominated);
+    }
+  }
+
   const HUseList<HInstruction*>& uses = GetUses();
   for (auto it = uses.begin(), end = uses.end(); it != end; /* ++it below */) {
     HInstruction* user = it->GetUser();
+    HBasicBlock* block = user->GetBlock();
     size_t index = it->GetIndex();
     // Increment `it` now because `*it` may disappear thanks to user->ReplaceInput().
     ++it;
-    const bool dominated =
-        strictly_dominated ? dominator->StrictlyDominates(user) : dominator->Dominates(user);
+    bool dominated = false;
+    if (dominator_block == block) {
+      // Trickier case, call the other methods.
+      dominated =
+          strictly_dominated ? dominator->StrictlyDominates(user) : dominator->Dominates(user);
+    } else {
+      // Block domination.
+      dominated = visited_blocks.IsBitSet(block->GetBlockId());
+    }
 
     if (dominated) {
       user->ReplaceInput(replacement, index);
@@ -1590,9 +1622,8 @@ void HInstruction::ReplaceUsesDominatedBy(HInstruction* dominator,
       // If the input flows from a block dominated by `dominator`, we can replace it.
       // We do not perform this for catch phis as we don't have control flow support
       // for their inputs.
-      const ArenaVector<HBasicBlock*>& predecessors = user->GetBlock()->GetPredecessors();
-      HBasicBlock* predecessor = predecessors[index];
-      if (dominator->GetBlock()->Dominates(predecessor)) {
+      HBasicBlock* predecessor = block->GetPredecessors()[index];
+      if (visited_blocks.IsBitSet(predecessor->GetBlockId())) {
         user->ReplaceInput(replacement, index);
       }
     }