Incrementally recompute dominators when inlining.

runtime/vm/flow_graph_builder.cc

 // Copyright (c) 2012, the Dart project authors.  Please see the AUTHORS file
 // for details. All rights reserved. Use of this source code is governed by a
 // BSD-style license that can be found in the LICENSE file.
 
 #include "vm/flow_graph_builder.h"
 
 #include "lib/invocation_mirror.h"
 #include "vm/ast_printer.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 44 matching lines @@
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
     graph_entry_(NULL) { }
 
 
 void FlowGraphBuilder::AddCatchEntry(CatchBlockEntryInstr* entry) {
   graph_entry_->AddCatchEntry(entry);
 }
 
 
-void InliningContext::PrepareGraphs(FlowGraph* caller_graph,
-                                    Definition* call,
-                                    FlowGraph* callee_graph) {
+void InliningContext::PrepareGraphs(FlowGraph* callee_graph) {
   ASSERT(callee_graph->graph_entry()->SuccessorCount() == 1);
-  ASSERT(callee_graph->max_block_id() > caller_graph->max_block_id());
+  ASSERT(callee_graph->max_block_id() > caller_graph_->max_block_id());
   ASSERT(callee_graph->max_virtual_register_number() >
-         caller_graph->max_virtual_register_number());
+         caller_graph_->max_virtual_register_number());
 
   // Adjust the caller's maximum block id and current SSA temp index.
-  caller_graph->set_max_block_id(callee_graph->max_block_id());
-  caller_graph->set_current_ssa_temp_index(
+  caller_graph_->set_max_block_id(callee_graph->max_block_id());
+  caller_graph_->set_current_ssa_temp_index(
       callee_graph->max_virtual_register_number());
 
   // Attach the outer environment on each instruction in the callee graph.
   for (BlockIterator block_it = callee_graph->postorder_iterator();
        !block_it.Done();
        block_it.Advance()) {
     for (ForwardInstructionIterator it(block_it.Current());
          !it.Done();
          it.Advance()) {
       Instruction* instr = it.Current();
       // TODO(zerny): Avoid creating unnecessary environments. Note that some
       // optimizations need deoptimization info for non-deoptable instructions,
       // eg, LICM on GOTOs.
-      if (instr->env() != NULL) call->env()->DeepCopyToOuter(instr);
+      if (instr->env() != NULL) call_->env()->DeepCopyToOuter(instr);
     }
   }
 }
 
 
 void InliningContext::AddExit(ReturnInstr* exit) {
   Data data = { NULL, exit };
   exits_.Add(data);
 }
 
 
 int InliningContext::LowestBlockIdFirst(const Data* a, const Data* b) {
   return (a->exit_block->block_id() - b->exit_block->block_id());
 }
 
 
 void InliningContext::SortExits() {
   // Assign block entries here because we did not necessarily know them when
   // the return exit was added to the array.
   for (int i = 0; i < exits_.length(); ++i) {
     exits_[i].exit_block = exits_[i].exit_return->GetBlock();
   }
   exits_.Sort(LowestBlockIdFirst);
 }
 
 
-void InliningContext::ReplaceCall(FlowGraph* caller_graph,
-                                  Definition* call,
-                                  FlowGraph* callee_graph) {
-  ASSERT(call->previous() != NULL);
-  ASSERT(call->next() != NULL);
-  PrepareGraphs(caller_graph, call, callee_graph);
-
-  BlockEntryInstr* caller_entry = call->GetBlock();
-  TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry();
-
-  // Insert the callee graph into the caller graph.  First sort the list of
-  // exits by block id (recording block entries as a side effect).
+Definition* InliningContext::JoinReturns(BlockEntryInstr** exit_block,
+                                         Instruction** last_instruction) {
+  // First sort the list of exits by block id (caching return instruction
+  // block entries as a side effect).
   SortExits();
   intptr_t num_exits = exits_.length();
   if (num_exits == 0) {
     // TODO(zerny): Add support for non-local exits, such as throw.
     UNREACHABLE();
+    return NULL;
   } else if (num_exits == 1) {
-    // For just one exit, replace the uses and remove the call from the graph.
-    call->ReplaceUsesWith(ValueAt(0)->definition());
     ValueAt(0)->RemoveFromUseList();
-    call->previous()->LinkTo(callee_entry->next());
-    LastInstructionAt(0)->LinkTo(call->next());
-    // In case of control flow, locally update the predecessors, phis and
-    // dominator tree.
-    // TODO(zerny): should we leave the dominator tree since we recompute it
-    // after a full inlining pass?
-    if (callee_graph->preorder().length() > 2) {
-      BlockEntryInstr* exit_block = ExitBlockAt(0);
-      // Pictorially, the graph structure is:
-      //
-      //   Bc : caller_entry    Bi : callee_entry
-      //     before_call          inlined_head
-      //     call               ... other blocks ...
-      //     after_call         Be : exit_block
-      //                          inlined_foot
-      // And becomes:
-      //
-      //   Bc : caller_entry
-      //     before_call
-      //     inlined_head
-      //   ... other blocks ...
-      //   Be : exit_block
-      //    inlined_foot
-      //    after_call
-      //
-      // For 'after_call', caller entry (Bc) is replaced by callee exit (Be).
-      caller_entry->ReplaceAsPredecessorWith(exit_block);
-      // For 'inlined_head', callee entry (Bi) is replaced by caller entry (Bc).
-      callee_entry->ReplaceAsPredecessorWith(caller_entry);
-      // The callee exit is now the immediate dominator of blocks whose
-      // immediate dominator was the caller entry.
-      ASSERT(exit_block->dominated_blocks().is_empty());
-      for (intptr_t i = 0; i < caller_entry->dominated_blocks().length(); ++i) {
-        BlockEntryInstr* block = caller_entry->dominated_blocks()[i];
-        block->set_dominator(exit_block);
-        exit_block->AddDominatedBlock(block);
+    *exit_block = ExitBlockAt(0);
+    *last_instruction = LastInstructionAt(0);
+    return call_->HasUses() ? ValueAt(0)->definition() : NULL;
+  } else {
+    // Create a join of the returns.
+    intptr_t join_id = caller_graph_->max_block_id() + 1;
+    caller_graph_->set_max_block_id(join_id);
+    JoinEntryInstr* join =
+        new JoinEntryInstr(join_id, CatchClauseNode::kInvalidTryIndex);
+
+    // The dominator set of the join is the intersection of the dominator
+    // sets of all the predecessors.  If we keep the dominator sets ordered
+    // by height in the dominator tree, we can also get the immediate
+    // dominator of the join node from the intersection.
+    //
+    // block_dominators is the dominator set for each block, ordered from
+    // the immediate dominator to the root of the dominator tree.  This is
+    // the order we collect them in (adding at the end).
+    //
+    // join_dominators is the join's dominators ordered from the root of the
+    // dominator tree to the immediate dominator.  This order supports
+    // removing during intersection by truncating the list.
+    GrowableArray<BlockEntryInstr*> block_dominators;
+    GrowableArray<BlockEntryInstr*> join_dominators;
+    for (intptr_t i = 0; i < num_exits; ++i) {
+      // Add the control-flow edge.
+      LastInstructionAt(i)->Goto(join);
+      ExitBlockAt(i)->set_last_instruction(LastInstructionAt(i)->next());
+      join->predecessors_.Add(ExitBlockAt(i));
+
+      // Collect the block's dominators.
+      block_dominators.Clear();
+      BlockEntryInstr* dominator = ExitBlockAt(i)->dominator();
+      while (dominator != NULL) {
+        block_dominators.Add(dominator);
+        dominator = dominator->dominator();
       }
-      // The caller entry is now the immediate dominator of blocks whose
-      // immediate dominator was the callee entry.
-      caller_entry->ClearDominatedBlocks();
-      for (intptr_t i = 0; i < callee_entry->dominated_blocks().length(); ++i) {
-        BlockEntryInstr* block = callee_entry->dominated_blocks()[i];
-        block->set_dominator(caller_entry);
-        caller_entry->AddDominatedBlock(block);
+
+      if (i == 0) {
+        // The initial dominator set is the first predecessor's dominator
+        // set.  Reverse it.
+        for (intptr_t j = block_dominators.length() - 1; j >= 0; --j) {
+          join_dominators.Add(block_dominators[j]);
+        }
+      } else {
+        // Intersect the block's dominators with the join's dominators so far.
+        intptr_t last = block_dominators.length() - 1;
+        for (intptr_t j = 0; j < join_dominators.length(); ++j) {
+          intptr_t k = last - j;  // Corresponding index in block_dominators.
+          if ((k < 0) || (join_dominators[j] != block_dominators[k])) {
+            // We either exhausted the dominators for this block before
+            // exhausting the current intersection, or else we found a block
+            // on the path from the root of the tree that is not in common.
+            ASSERT(j >= 1);

[Florian Schneider, 2013/04/11 11:30:18]

I think you can even assert that there are always at least 1 block (graph entry)
in the join_dominators:

ASSERT(j > 1)

+            join_dominators.TruncateTo(j - 1);
+            break;
+          }
+        }
       }
     }
-  } else {
-    // Create a join of the returns.
-    intptr_t join_id = caller_graph->max_block_id() + 1;
-    caller_graph->set_max_block_id(join_id);
-    JoinEntryInstr* join =
-        new JoinEntryInstr(join_id, CatchClauseNode::kInvalidTryIndex);
-    for (intptr_t i = 0; i < num_exits; ++i) {
-      LastInstructionAt(i)->Goto(join);
-      // Directly add the predecessors of the join in ascending block id order.
-      join->predecessors_.Add(ExitBlockAt(i));
-    }
+    // The immediate dominator of the join is the last one in the ordered
+    // intersection.
+    join->set_dominator(join_dominators.Last());
+    join_dominators.Last()->AddDominatedBlock(join);
+    *exit_block = join;
+    *last_instruction = join;
+
     // If the call has uses, create a phi of the returns.
-    if (call->HasUses()) {
+    if (call_->HasUses()) {
       // Add a phi of the return values.
       PhiInstr* phi = new PhiInstr(join, num_exits);
-      phi->set_ssa_temp_index(caller_graph->alloc_ssa_temp_index());
+      phi->set_ssa_temp_index(caller_graph_->alloc_ssa_temp_index());
       phi->mark_alive();
       for (intptr_t i = 0; i < num_exits; ++i) {
         phi->SetInputAt(i, ValueAt(i));
       }
       join->InsertPhi(phi);
-      // Replace uses of the call with the phi.
-      call->ReplaceUsesWith(phi);
+      return phi;
     } else {
       // In the case that the result is unused, remove the return value uses
       // from their definition's use list.
       for (intptr_t i = 0; i < num_exits; ++i) {
         ValueAt(i)->RemoveFromUseList();
       }
+      return NULL;
     }
-    // Remove the call from the graph.
-    call->previous()->LinkTo(callee_entry->next());
-    join->LinkTo(call->next());
-    // Replace the blocks after splitting (see comment in the len=1 case above).
-    caller_entry->ReplaceAsPredecessorWith(join);
-    callee_entry->ReplaceAsPredecessorWith(caller_entry);
-    // Update the last instruction pointers on each exit block to the new goto.
-    for (intptr_t i = 0; i < num_exits; ++i) {
-      ExitBlockAt(i)->set_last_instruction(LastInstructionAt(i)->next());
-    }
-    // Mark that the dominator tree is invalid.
-    // TODO(zerny): Compute the dominator frontier locally.
-    caller_graph->InvalidateDominatorTree();
   }
 }
 
+
+void InliningContext::ReplaceCall(FlowGraph* callee_graph) {
+  ASSERT(call_->previous() != NULL);
+  ASSERT(call_->next() != NULL);
+  PrepareGraphs(callee_graph);
+
+  BlockEntryInstr* call_block = call_->GetBlock();
+  TargetEntryInstr* callee_entry = callee_graph->graph_entry()->normal_entry();
+
+  // Insert the callee graph into the caller graph.
+  BlockEntryInstr* callee_exit = NULL;
+  Instruction* callee_last_instruction = NULL;
+  Definition* callee_result = JoinReturns(&callee_exit,
+                                          &callee_last_instruction);
+  if (callee_result != NULL) {
+    call_->ReplaceUsesWith(callee_result);
+  }
+  if (callee_last_instruction == callee_entry) {
+    // There are no instructions in the inlined function (e.g., it might be
+    // a return of a parameter or a return of a constant defined in the
+    // initial definitions).
+    call_->previous()->LinkTo(call_->next());
+  } else {
+    call_->previous()->LinkTo(callee_entry->next());
+    callee_last_instruction->LinkTo(call_->next());
+  }
+  if (callee_exit != callee_entry) {
+    // In case of control flow, locally update the predecessors, phis and
+    // dominator tree.
+    //
+    // Pictorially, the graph structure is:
+    //
+    //   Bc : call_block      Bi : callee_entry
+    //     before_call          inlined_head
+    //     call               ... other blocks ...
+    //     after_call         Be : callee_exit
+    //                          inlined_foot
+    // And becomes:
+    //
+    //   Bc : call_block
+    //     before_call
+    //     inlined_head
+    //   ... other blocks ...
+    //   Be : callee_exit
+    //    inlined_foot
+    //    after_call
+    //
+    // For successors of 'after_call', the call block (Bc) is replaced as a
+    // predecessor by the callee exit (Be).
+    call_block->ReplaceAsPredecessorWith(callee_exit);
+    // For successors of 'inlined_head', the callee entry (Bi) is replaced
+    // as a predecessor by the call block (Bc).
+    callee_entry->ReplaceAsPredecessorWith(call_block);
+
+    // The callee exit is now the immediate dominator of blocks whose
+    // immediate dominator was the call block.
+    ASSERT(callee_exit->dominated_blocks().is_empty());
+    for (intptr_t i = 0; i < call_block->dominated_blocks().length(); ++i) {
+      BlockEntryInstr* block = call_block->dominated_blocks()[i];
+      block->set_dominator(callee_exit);
+      callee_exit->AddDominatedBlock(block);
+    }
+    // The call block is now the immediate dominator of blocks whose
+    // immediate dominator was the callee entry.
+    call_block->ClearDominatedBlocks();
+    for (intptr_t i = 0; i < callee_entry->dominated_blocks().length(); ++i) {
+      BlockEntryInstr* block = callee_entry->dominated_blocks()[i];
+      block->set_dominator(call_block);
+      call_block->AddDominatedBlock(block);
+    }
+  }
+}
+
 
 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) {
   ASSERT(is_open());
   if (other_fragment.is_empty()) return;
   if (is_empty()) {
     entry_ = other_fragment.entry();
     exit_ = other_fragment.exit();
   } else {
     exit()->LinkTo(other_fragment.entry());
     exit_ = other_fragment.exit();
@@ skipping 3105 matching lines @@
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = Isolate::Current()->current_zone()->Alloc<char>(len);
   OS::SNPrint(chars, len, kFormat, function_name, reason);
   const Error& error = Error::Handle(
       LanguageError::New(String::Handle(String::New(chars))));
   Isolate::Current()->long_jump_base()->Jump(1, error);
 }
 
 
 }  // namespace dart