First step to SSA construction: Phi insertion.

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 "vm/ast_printer.h"
 #include "vm/bit_vector.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 41 matching lines @@
     exit()->SetSuccessor(other_fragment.entry());
     exit_ = other_fragment.exit();
   }
   temp_index_ = other_fragment.temp_index();
 }
 
 
 void EffectGraphVisitor::AddInstruction(Instruction* instruction) {
   ASSERT(is_open());
   DeallocateTempIndex(instruction->InputCount());
-  if (instruction->IsBindInstr()) {
-    instruction->AsBindInstr()->set_temp_index(AllocateTempIndex());
+  if (instruction->IsDefinition()) {
+    instruction->AsDefinition()->set_temp_index(AllocateTempIndex());
   }
   if (is_empty()) {
     entry_ = exit_ = instruction;
   } else {
     exit()->SetSuccessor(instruction);
     exit_ = instruction;
   }
 }
 
 
@@ skipping 2256 matching lines @@
                                &assigned_vars,
                                variable_count);
   // Number blocks in reverse postorder.
   intptr_t block_count = postorder_block_entries_.length();
   for (intptr_t i = 0; i < block_count; ++i) {
     postorder_block_entries_[i]->set_block_id(block_count - i - 1);
   }
   if (for_optimized) {
     GrowableArray<BitVector*> dominance_frontier;
     ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
+    InsertPhis(&preorder_block_entries_,
+               &assigned_vars,
+               variable_count,
+               &dominance_frontier);
+    // TODO(fschneider): Perform SSA renaming.
   }
   if (FLAG_print_flow_graph || (Dart::flow_graph_writer() != NULL)) {
     intptr_t length = postorder_block_entries_.length();
     GrowableArray<BlockEntryInstr*> reverse_postorder(length);
     for (intptr_t i = length - 1; i >= 0; --i) {
       reverse_postorder.Add(postorder_block_entries_[i]);
     }
     if (FLAG_print_flow_graph) {
       // Print flow graph to stdout.
       FlowGraphPrinter printer(function, reverse_postorder);
@@ skipping 88 matching lines @@
 
   // 2. Compute the immediate dominators as the nearest common ancestor of
   // spanning tree parent and semidominator, for all blocks except the entry.
   for (intptr_t block_index = 1; block_index < size; ++block_index) {
     intptr_t dom_index = idom[block_index];
     while (dom_index > semi[block_index]) {
       dom_index = idom[dom_index];
     }
     idom[block_index] = dom_index;
     (*preorder)[block_index]->set_dominator((*preorder)[dom_index]);
+    (*preorder)[dom_index]->dominated_blocks()->Add((*preorder)[block_index]);
   }
 
   // 3. Now compute the dominance frontier for all blocks.  This is
   // algorithm in "A Simple, Fast Dominance Algorithm" (Figure 5), which is
   // attributed to a paper by Ferrante et al.  There is no bookkeeping
   // required to avoid adding a block twice to the same block's dominance
   // frontier because we use a set to represent the dominance frontier.
   for (intptr_t block_index = 0; block_index < size; ++block_index) {
     BlockEntryInstr* block = (*preorder)[block_index];
     intptr_t count = block->PredecessorCount();
@@ skipping 16 matching lines @@
   intptr_t next_index = (*parent)[current_index];
   if (next_index > start_index) {
     CompressPath(start_index, next_index, parent, label);
     (*label)[current_index] =
         Utils::Minimum((*label)[current_index], (*label)[next_index]);
     (*parent)[current_index] = (*parent)[next_index];
   }
 }
 
 
+void FlowGraphBuilder::InsertPhis(GrowableArray<BlockEntryInstr*>* preorder,

[srdjan, 2012/06/12 17:34:37]

const GrowableArray<BlockEntryInstr>&

[Florian Schneider, 2012/06/13 10:53:40]

Done.

+                                  GrowableArray<BitVector*>* assigned_vars,

[srdjan, 2012/06/12 17:34:37]

const GrowableArray<BitVector>&

[Florian Schneider, 2012/06/13 10:53:40]

Done.

+                                  intptr_t var_count,
+                                  GrowableArray<BitVector*>* dom_frontier) {

[srdjan, 2012/06/12 17:34:37]

ditto

[Florian Schneider, 2012/06/13 10:53:40]

Done.

+  int block_count = preorder->length();

[srdjan, 2012/06/12 17:34:37]

const intptr_t

[Florian Schneider, 2012/06/13 10:53:40]

Done.

[Florian Schneider, 2012/06/13 10:53:40]

Done.

+  // Map preorder block number to the highest variable index that has a phi
+  // in that block.  Use it to avoid inserting multiple phis for the same
+  // variable.
+  int* has_already = new int[block_count];

[srdjan, 2012/06/12 17:34:37]

Allocation in C++ heap should be avoided (memory leaks, slow). Use Zone
allocated arrays. In fact I would use GrowableArrays<intptr_t> allocated to
capacity block_count and cleared with the loop below. (both for has_already and
work).

[Florian Schneider, 2012/06/13 10:53:40]

Done.

+  // Map preorder block number to the highest variable index for which the
+  // block went on the worklist.  Use it to avoid adding the same block to
+  // the worklist more than once for the same variable.
+  int* work = new int[block_count];
+
+  // Initialize has_already and work.
+  for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
+    has_already[block_index] = -1;
+    work[block_index] = -1;
+  }
+
+  // Insert phis for each variable in turn.
+  GrowableArray<BlockEntryInstr*> worklist;
+  for (intptr_t var_index = 0; var_index < var_count; ++var_index) {
+    // Add to the worklist each block containing an assignment.
+    for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
+      if ((*assigned_vars)[block_index]->Contains(var_index)) {
+        work[block_index] = var_index;
+        worklist.Add((*preorder)[block_index]);
+      }
+    }
+
+    while (!worklist.is_empty()) {
+      BlockEntryInstr* current = worklist.Last();
+      worklist.RemoveLast();
+      // Ensure a phi for each block in the dominance frontier of current.
+      for (BitVector::Iterator it((*dom_frontier)[current->preorder_number()]);
+           !it.Done();
+           it.Advance()) {
+        int index = it.Current();
+        if (has_already[index] < var_index) {
+          BlockEntryInstr* block = (*preorder)[index];
+          ASSERT(block->IsJoinEntry());
+          block->AsJoinEntry()->InsertPhi(var_index, var_count);
+          has_already[index] = var_index;
+          if (work[index] < var_index) {
+            work[index] = var_index;
+            worklist.Add(block);
+          }
+        }
+      }
+    }
+  }
+
+  delete[] work;
+  delete[] has_already;
+}
+
+
 void FlowGraphBuilder::Bailout(const char* reason) {
   const char* kFormat = "FlowGraphBuilder Bailout: %s %s";
   const char* function_name = parsed_function_.function().ToCString();
   intptr_t len = OS::SNPrint(NULL, 0, kFormat, function_name, reason) + 1;
   char* chars = reinterpret_cast<char*>(
       Isolate::Current()->current_zone()->Allocate(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