Second step for computing SSA: renaming.

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 17 matching lines @@
 DECLARE_FLAG(bool, enable_type_checks);
 
 
 FlowGraphBuilder::FlowGraphBuilder(const ParsedFunction& parsed_function)
   : parsed_function_(parsed_function),
     preorder_block_entries_(),
     postorder_block_entries_(),
     context_level_(0),
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
-    graph_entry_(NULL) { }
+    graph_entry_(NULL),
+    current_ssa_temp_index_(0) { }
 
 
 void FlowGraphBuilder::AddCatchEntry(TargetEntryInstr* entry) {
   graph_entry_->AddCatchEntry(entry);
 }
 
 
 void EffectGraphVisitor::Append(const EffectGraphVisitor& other_fragment) {
   ASSERT(is_open());
   if (other_fragment.is_empty()) return;
@@ skipping 2292 matching lines @@
   for (intptr_t i = 0; i < block_count; ++i) {
     postorder_block_entries_[i]->set_block_id(block_count - i - 1);
   }
   if (for_optimized && FLAG_use_ssa) {
     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.
+    Rename(variable_count);
   }
   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 185 matching lines @@
             work[index] = var_index;
             worklist.Add(block);
           }
         }
       }
     }
   }
 }
 
 
+void FlowGraphBuilder::Rename(intptr_t var_count) {
+  // Initialize start environment:
+  // All locals are initialized with #null.
+  // TODO(fschneider): Support paramters. All parameters are initially located

[srdjan, 2012/06/18 18:04:38]

parameters

[Florian Schneider, 2012/06/19 11:26:40]

Done.

+  // on the stack.
+  ZoneGrowableArray<Value*>* start_env =
+      new ZoneGrowableArray<Value*>(var_count);
+  if (parsed_function().function().num_fixed_parameters() > 0) {
+    Bailout("Fixed parameter support in SSA");
+  }
+  if (parsed_function().copied_parameter_count()) {
+    Bailout("Copied parameter support in SSA");
+  }
+  Value* null_value = new ConstantVal(Object::ZoneHandle());
+  ASSERT(var_count == parsed_function().stack_local_count());

[srdjan, 2012/06/18 18:04:38]

Why don't you use stack_local_count instead of passing in var_count? If it is
temporary to check sanity, please add a TODO to remove var_count.

[Florian Schneider, 2012/06/19 11:26:40]

Yes, in one of the next CLs it will change to:

var_count = local + fixed_params + copied_params

Maybe we should store this value in the builder class instead of passing it
around in all functions?

+  for (intptr_t i = 0; i < var_count; i++) {
+    start_env->Add(null_value);
+  }
+  graph_entry_->set_start_env(start_env);
+
+  BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0);
+  ASSERT(normal_entry != NULL);  // Graph entry is empty.

[srdjan, 2012/06/18 18:04:38]

Maybe change comment to: "Must have entry" or similar.

[Florian Schneider, 2012/06/19 11:26:40]

Done.

+  ZoneGrowableArray<Value*>* env = new ZoneGrowableArray<Value*>(var_count);
+  env->AddArray(*start_env);
+  RenameRecursive(normal_entry, env, var_count);
+}
+
+
+static intptr_t WhichPred(BlockEntryInstr* predecessor,
+                          JoinEntryInstr* join_block) {
+  for (intptr_t i = 0; i < join_block->PredecessorCount(); ++i) {
+    if (join_block->PredecessorAt(i) == predecessor) return i;
+  }
+  UNREACHABLE();
+  return -1;
+}
+
+
+void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
+                                       ZoneGrowableArray<Value*>* env,
+                                       intptr_t var_count) {
+  // Iterate over instructions.
+  // 1. Handle phis first.
+  if (block_entry->IsJoinEntry()) {
+    JoinEntryInstr* join = block_entry->AsJoinEntry();
+    if (join->phis() != NULL) {

[srdjan, 2012/06/18 18:04:38]

ASSERT(join->phis() != NULL) ? 

[Florian Schneider, 2012/06/19 11:26:40]

Right now I lazily allocate the phis() array when there are phis present: The
non-optimizing compiler will never add any phi-instructions, so the JoinEntry
would always have an empty GrowableArray in this case.

+      for (intptr_t i = 0; i < join->phis()->length(); ++i) {
+        PhiInstr* phi = (*join->phis())[i];
+        if (phi != NULL) {
+          (*env)[i] = new UseVal(phi);
+          phi->set_ssa_temp_index(current_ssa_temp_index_++);  // New SSA temp.
+        }
+      }
+    }
+  }
+
+  // 2. Handle normal instructions.
+  Instruction* current = block_entry->StraightLineSuccessor();
+  Instruction* prev = block_entry;
+  while (current != NULL && !current->IsBlockEntry()) {

[srdjan, 2012/06/18 18:04:38]

add parenthesis

[Florian Schneider, 2012/06/19 11:26:40]

Done.

+    // 2a. Handle LoadLocal and StoreLocal.
+    LoadLocalComp* load = NULL;
+    if (current->IsDo() &&
+        current->AsDo()->computation()->IsLoadLocal()) {
+      load = current->AsDo()->computation()->AsLoadLocal();

[srdjan, 2012/06/18 18:04:38]

A LoadLocal in a Do has no side effect and can be thrown (optimized) away. Why
not get rid of it?

[Florian Schneider, 2012/06/19 11:26:40]

Yes. I remove it from the graph below, but better if we already not generate
such a LoadLocal in the first place. I'll add an ASSERT instead.

+    } else if (current->IsBind() &&
+               current->AsBind()->computation()->IsLoadLocal()) {
+      load = current->AsBind()->computation()->AsLoadLocal();
+    }
+    StoreLocalComp* store = NULL;
+    if (current->IsDo() &&
+        current->AsDo()->computation()->IsStoreLocal()) {
+      store = current->AsDo()->computation()->AsStoreLocal();
+    } else if (current->IsBind() &&
+               current->AsBind()->computation()->IsStoreLocal()) {
+      store = current->AsBind()->computation()->AsStoreLocal();
+    }
+
+    if (load != NULL || store != NULL) {

[srdjan, 2012/06/18 18:04:38]

Add parenthesis

[Florian Schneider, 2012/06/19 11:26:40]

Done.

+      // Remove instruction with LoadLocal or StoreLocal.
+      prev->SetSuccessor(current->StraightLineSuccessor());
+      // Update renaming environment for StoreLocal.
+      if (store != NULL) {
+        (*env)[store->local().BitIndexIn(var_count)] = store->value();
+      }
+    } else {
+      // Assign new SSA temporary.
+      if (current->IsBind()) {
+        current->AsDefinition()->set_ssa_temp_index(current_ssa_temp_index_++);
+      }
+    }
+
+    // 2b. Handle uses of LoadLocal / StoreLocal
+    for (intptr_t i = 0; i < current->InputCount(); ++i) {
+      // For each use of a LoadLocal/StoreLocal: Replace it with the definition
+      // from the enviroment.

[srdjan, 2012/06/18 18:04:38]

environment

[Florian Schneider, 2012/06/19 11:26:40]

Done.

+      Value* v = current->InputAt(i);
+      if (v->IsUse() &&
+          v->AsUse()->definition()->IsBind() &&
+          v->AsUse()->definition()->AsBind()->computation()->IsLoadLocal()) {
+        Computation* comp = v->AsUse()->definition()->AsBind()->computation();
+        intptr_t index = comp->AsLoadLocal()->local().BitIndexIn(var_count);
+        Value* new_value = (*env)[index];
+        // Make a copy if it is a UseVal.
+        if (new_value->IsUse()) {
+          new_value = new UseVal(new_value->AsUse()->definition());
+        }
+        current->SetInputAt(i, new_value);
+      }
+      if (v->IsUse() &&
+          v->AsUse()->definition()->IsBind() &&
+          v->AsUse()->definition()->AsBind()->computation()->IsStoreLocal()) {
+        // For each use of a LoadLocal: Replace LoadLocal with the definition
+        // from the enviroment.
+        Computation* comp = v->AsUse()->definition()->AsBind()->computation();
+        intptr_t index = comp->AsStoreLocal()->local().BitIndexIn(var_count);
+        Value* new_value = (*env)[index];
+        // Make a copy if it is a UseVal.
+        if (new_value->IsUse()) {
+          new_value = new UseVal(new_value->AsUse()->definition());
+        }
+        current->SetInputAt(i, new_value);
+      }
+    }
+
+    // Update previous only if no instruction was removed from the graph.
+    if (load == NULL && store == NULL) {

[srdjan, 2012/06/18 18:04:38]

parenthesis

[Florian Schneider, 2012/06/19 11:26:40]

Done.

+      prev = current;
+    }
+    current = current->StraightLineSuccessor();
+  }
+
+  // 3. Process dominated blocks.
+  for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) {
+    BlockEntryInstr* block = block_entry->dominated_blocks()[i];
+    ZoneGrowableArray<Value*>* new_env =
+        new ZoneGrowableArray<Value*>(var_count);
+    new_env->AddArray(*env);
+    RenameRecursive(block, new_env, var_count);
+  }
+
+  // 4. Process successor block. We have edge-split form, so that only blocks
+  // with one successor can have a join block as successor.
+  if (block_entry->last_instruction()->SuccessorCount() == 1 &&

[srdjan, 2012/06/18 18:04:38]

ditto

[Florian Schneider, 2012/06/19 11:26:40]

Done.

+      block_entry->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
+    JoinEntryInstr* successor =
+        block_entry->last_instruction()->SuccessorAt(0)->AsJoinEntry();
+    intptr_t pred_index = WhichPred(block_entry, successor);
+    if (successor->phis() != NULL) {
+      for (intptr_t i = 0; i < successor->phis()->length(); ++i) {
+        PhiInstr* phi = (*successor->phis())[i];
+        if (phi != NULL) phi->SetInputAt(pred_index, (*env)[i]);
+      }
+    }
+  }
+}
+
+
 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