Store variable counts in the flow graph builder.

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 "vm/ast_printer.h"
 #include "vm/bit_vector.h"
 #include "vm/code_descriptors.h"
 #include "vm/dart_entry.h"
@@ skipping 14 matching lines @@
             "Eliminate type checks when allowed by static type analysis.");
 DEFINE_FLAG(bool, print_ast, false, "Print abstract syntax tree.");
 DEFINE_FLAG(bool, print_flow_graph, false, "Print the IR flow graph.");
 DEFINE_FLAG(bool, trace_type_check_elimination, false,
             "Trace type check elimination at compile time.");
 DECLARE_FLAG(bool, enable_type_checks);
 
 
 FlowGraphBuilder::FlowGraphBuilder(const ParsedFunction& parsed_function)
   : parsed_function_(parsed_function),
+    copied_parameter_count_(parsed_function.copied_parameter_count()),
+    // All parameters are copied if any parameter is.
+    non_copied_parameter_count_((copied_parameter_count_ == 0)
+        ? parsed_function.function().num_fixed_parameters()
+        : 0),
+    stack_local_count_(parsed_function.stack_local_count()),
     preorder_block_entries_(),
     postorder_block_entries_(),
     context_level_(0),
     last_used_try_index_(CatchClauseNode::kInvalidTryIndex),
     try_index_(CatchClauseNode::kInvalidTryIndex),
     graph_entry_(NULL),
     current_ssa_temp_index_(0) { }
 
 
 void FlowGraphBuilder::AddCatchEntry(TargetEntryInstr* entry) {
@@ skipping 2247 matching lines @@
   TargetEntryInstr* normal_entry = new TargetEntryInstr();
   graph_entry_ = new GraphEntryInstr(normal_entry);
   EffectGraphVisitor for_effect(this, 0);
   parsed_function().node_sequence()->Visit(&for_effect);
   AppendFragment(normal_entry, for_effect);
   // Check that the graph is properly terminated.
   ASSERT(!for_effect.is_open());
   GrowableArray<intptr_t> parent;
   GrowableArray<BitVector*> assigned_vars;
 
-  // Either all parameters are fixed (none are named) or they are all copied.
-  // This could change, so we keep fixed/copied counts separate.
-  intptr_t fixed_parameter_count;  // This is really the "non-copied" count.
-  intptr_t copied_parameter_count;
-  if (parsed_function_.copied_parameter_count() > 0) {
-    fixed_parameter_count = 0;
-    copied_parameter_count = parsed_function_.copied_parameter_count();
-  } else {
-    fixed_parameter_count = parsed_function_.function().num_fixed_parameters();
-    copied_parameter_count = 0;
-  }
-  const intptr_t stack_local_count = parsed_function_.stack_local_count();
-  const intptr_t variable_count =
-      stack_local_count + fixed_parameter_count + copied_parameter_count;
-
   // Perform a depth-first traversal of the graph to build preorder and
   // postorder block orders.
   graph_entry_->DiscoverBlocks(NULL,  // Entry block predecessor.
                                &preorder_block_entries_,
                                &postorder_block_entries_,
                                &parent,
                                &assigned_vars,
-                               variable_count,
-                               fixed_parameter_count);
+                               variable_count(),
+                               non_copied_parameter_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) {
     // Link instructions backwards for optimized compilation.
     for (intptr_t i = 0; i < block_count; ++i) {
       BlockEntryInstr* entry = postorder_block_entries_[i];
       Instruction* previous = entry;
       for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
         Instruction* current = it.Current();
         current->set_previous(previous);
         previous = current;
       }
     }
   }
 
   if (for_optimized && use_ssa) {
     GrowableArray<BitVector*> dominance_frontier;
     ComputeDominators(&preorder_block_entries_, &parent, &dominance_frontier);
     InsertPhis(preorder_block_entries_,
                assigned_vars,
-               variable_count,
                dominance_frontier);
-    Rename(stack_local_count, fixed_parameter_count, copied_parameter_count);
+    Rename();
   }
   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 128 matching lines @@
     (*label)[current_index] =
         Utils::Minimum((*label)[current_index], (*label)[next_index]);
     (*parent)[current_index] = (*parent)[next_index];
   }
 }
 
 
 void FlowGraphBuilder::InsertPhis(
     const GrowableArray<BlockEntryInstr*>& preorder,
     const GrowableArray<BitVector*>& assigned_vars,
-    const intptr_t var_count,
     const GrowableArray<BitVector*>& dom_frontier) {
   const intptr_t block_count = preorder.length();
   // 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.
   GrowableArray<intptr_t> has_already(block_count);
   // 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.
   GrowableArray<intptr_t> work(block_count);
 
   // Initialize has_already and work.
   for (intptr_t block_index = 0; block_index < block_count; ++block_index) {
     has_already.Add(-1);
     work.Add(-1);
   }
 
   // Insert phis for each variable in turn.
   GrowableArray<BlockEntryInstr*> worklist;
-  for (intptr_t var_index = 0; var_index < var_count; ++var_index) {
+  for (intptr_t var_index = 0; var_index < variable_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);
+          block->AsJoinEntry()->InsertPhi(var_index, variable_count());
           has_already[index] = var_index;
           if (work[index] < var_index) {
             work[index] = var_index;
             worklist.Add(block);
           }
         }
       }
     }
   }
 }
 
 
-void FlowGraphBuilder::Rename(intptr_t stack_local_count,
-                              intptr_t fixed_parameter_count,
-                              intptr_t copied_parameter_count) {
+void FlowGraphBuilder::Rename() {
   // TODO(fschneider): Store counts in the FlowGraphBuilder instead of

[Kevin Millikin (Google), 2012/08/06 14:01:14]

I'll remove the TODO :)

   // passing it around.
   // TODO(fschneider): Support catch-entry.
   if (graph_entry_->SuccessorCount() > 1) {
     Bailout("Catch-entry support in SSA.");
   }
 
-  const intptr_t parameter_count =
-      fixed_parameter_count + copied_parameter_count;
-  const intptr_t variable_count = parameter_count + stack_local_count;
-
   // Initialize start environment.
-  GrowableArray<Value*> start_env(variable_count);
-  intptr_t i = 0;
-  for (; i < parameter_count; ++i) {
+  GrowableArray<Value*> start_env(variable_count());
+  for (intptr_t i = 0; i < parameter_count(); ++i) {
     ParameterInstr* param = new ParameterInstr(i);
     param->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
     start_env.Add(new UseVal(param));
   }
 
   // All locals are initialized with #null.
   Value* null_value = new ConstantVal(Object::ZoneHandle());
-  for (; i < variable_count; i++) {
+  while (start_env.length() < variable_count()) {
     start_env.Add(null_value);
   }
   graph_entry_->set_start_env(
-      new Environment(start_env, fixed_parameter_count));
+      new Environment(start_env, non_copied_parameter_count_));
 
   BlockEntryInstr* normal_entry = graph_entry_->SuccessorAt(0);
   ASSERT(normal_entry != NULL);  // Must have entry.
-  GrowableArray<Value*> env(variable_count);
+  GrowableArray<Value*> env(variable_count());
   env.AddArray(start_env);
-  RenameRecursive(normal_entry, &env, variable_count, fixed_parameter_count);
+  RenameRecursive(normal_entry, &env);
 }
 
 
 // Helper to a copy a value iff it is a UseVal.
 static Value* CopyValue(Value* value) {
   return value->IsUse()
       ? new UseVal(value->AsUse()->definition())
       : value;
 }
 
 
 void FlowGraphBuilder::RenameRecursive(BlockEntryInstr* block_entry,
-                                       GrowableArray<Value*>* env,
-                                       intptr_t var_count,
-                                       intptr_t fixed_parameter_count) {
+                                       GrowableArray<Value*>* env) {
   // 1. Process phis first.
   if (block_entry->IsJoinEntry()) {
     JoinEntryInstr* join = block_entry->AsJoinEntry();
     if (join->phis() != NULL) {
       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(alloc_ssa_temp_index());  // New SSA temp.
         }
       }
     }
   }
 
   // 2. Process normal instructions.
   for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
     // Attach current environment to the instruction. First, each instruction
     // gets a full copy of the environment. Later we optimize this by
     // eliminating unnecessary environments.
-    current->set_env(new Environment(*env, fixed_parameter_count));
+    current->set_env(new Environment(*env, non_copied_parameter_count_));
 
     // 2a. Handle uses:
     // Update expression stack environment for each use.
     // For each use of a LoadLocal or StoreLocal: Replace it with the value
     // from the environment.
     for (intptr_t i = 0; i < current->InputCount(); ++i) {
       Value* v = current->InputAt(i);
       if (!v->IsUse()) continue;
       // Update expression stack.
-      ASSERT(env->length() > var_count);
+      ASSERT(env->length() > variable_count());
       env->RemoveLast();
       BindInstr* as_bind = v->AsUse()->definition()->AsBind();
       if ((as_bind != NULL) && as_bind->computation()->IsLoadLocal()) {
         Computation* comp = as_bind->computation();
-        intptr_t index =
-            comp->AsLoadLocal()->local().BitIndexIn(fixed_parameter_count);
+        intptr_t index = comp->AsLoadLocal()->local().BitIndexIn(

[Florian Schneider, 2012/08/06 14:13:16]

Not sure if it's possible, but I'd break line after =

+            non_copied_parameter_count_);
         current->SetInputAt(i, CopyValue((*env)[index]));
       }
       if ((as_bind != NULL) && as_bind->computation()->IsStoreLocal()) {
         // For each use of a StoreLocal: Replace it with the value from the
         // environment.
         Computation* comp = as_bind->computation();
-        intptr_t index =
-            comp->AsStoreLocal()->local().BitIndexIn(fixed_parameter_count);
+        intptr_t index = comp->AsStoreLocal()->local().BitIndexIn(

[Florian Schneider, 2012/08/06 14:13:16]

Not sure if it's possible, but I'd break line after =

+            non_copied_parameter_count_);
         current->SetInputAt(i, CopyValue((*env)[index]));
       }
     }
 
     // Drop pushed arguments for calls.
     for (intptr_t j = 0; j < current->ArgumentCount(); j++) {
       env->RemoveLast();
     }
 
     // 2b. Handle LoadLocal and StoreLocal.
     // For each LoadLocal: Remove it from the graph.
     // For each StoreLocal: Remove it from the graph and update the environment.
     BindInstr* bind = current->AsBind();
     if (bind != NULL) {
       LoadLocalComp* load = bind->computation()->AsLoadLocal();
       StoreLocalComp* store = bind->computation()->AsStoreLocal();
       if ((load != NULL) || (store != NULL)) {
         intptr_t index;
         if (store != NULL) {
-          index = store->local().BitIndexIn(fixed_parameter_count);
+          index = store->local().BitIndexIn(non_copied_parameter_count_);
           // Update renaming environment.
           (*env)[index] = store->value();
         } else {
           // The graph construction ensures we do not have an unused LoadLocal
           // computation.
           ASSERT(bind->is_used());
-          index = load->local().BitIndexIn(fixed_parameter_count);
+          index = load->local().BitIndexIn(non_copied_parameter_count_);
         }
         // Update expression stack and remove from graph.
         if (bind->is_used()) {
           env->Add(CopyValue((*env)[index]));
         }
         it.RemoveCurrentFromGraph();
       } else {
         // Not a load or store.
         if (bind->is_used()) {
           // Assign fresh SSA temporary and update expression stack.
           bind->set_ssa_temp_index(alloc_ssa_temp_index());
           env->Add(new UseVal(bind));
         }
       }
     }
 
     // 2c. Handle pushed argument.
     PushArgumentInstr* push = current->AsPushArgument();
     if (push != NULL) {
       env->Add(push->value());
     }
   }
 
   // 3. Process dominated blocks.
   for (intptr_t i = 0; i < block_entry->dominated_blocks().length(); ++i) {
     BlockEntryInstr* block = block_entry->dominated_blocks()[i];
     GrowableArray<Value*> new_env(env->length());
     new_env.AddArray(*env);
-    RenameRecursive(block, &new_env, var_count, fixed_parameter_count);
+    RenameRecursive(block, &new_env);
   }
 
   // 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) &&
       block_entry->last_instruction()->SuccessorAt(0)->IsJoinEntry()) {
     JoinEntryInstr* successor =
         block_entry->last_instruction()->SuccessorAt(0)->AsJoinEntry();
     intptr_t pred_index = successor->IndexOfPredecessor(block_entry);
     ASSERT(pred_index >= 0);
@@ skipping 19 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