Make CTX allocatable by the register allocator.

runtime/vm/flow_graph.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.h"
 
 #include "vm/bit_vector.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/intermediate_language.h"
 #include "vm/growable_array.h"
+#include "vm/object_store.h"
 #include "vm/report.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, reorder_basic_blocks);
 DECLARE_FLAG(bool, trace_optimization);
 DECLARE_FLAG(bool, verify_compiler);
 
 
 FlowGraph::FlowGraph(const FlowGraphBuilder& builder,
                      GraphEntryInstr* graph_entry,
                      intptr_t max_block_id)
   : isolate_(Isolate::Current()),
     parent_(),
     current_ssa_temp_index_(0),
     max_block_id_(max_block_id),
     builder_(builder),
     parsed_function_(*builder.parsed_function()),
     num_copied_params_(builder.num_copied_params()),
     num_non_copied_params_(builder.num_non_copied_params()),
     num_stack_locals_(builder.num_stack_locals()),
     graph_entry_(graph_entry),
     preorder_(),
     postorder_(),
     reverse_postorder_(),
     optimized_block_order_(),
     constant_null_(NULL),
     constant_dead_(NULL),
+    constant_empty_context_(NULL),
     block_effects_(NULL),
     licm_allowed_(true),
     loop_headers_(NULL),
     loop_invariant_loads_(NULL),
     guarded_fields_(builder.guarded_fields()),
     deferred_prefixes_(builder.deferred_prefixes()),
     captured_parameters_(
         new(isolate_) BitVector(isolate_, variable_count())) {
   DiscoverBlocks();
 }
@@ skipping 409 matching lines @@
       }
       assigned_vars_.Add(kill);
     }
 
     return assigned_vars_;
   }
 
   // Returns true if the value set by the given store reaches any load from the
   // same local variable.
   bool IsStoreAlive(BlockEntryInstr* block, StoreLocalInstr* store) {
+    if (store->local().Equals(*flow_graph_->CurrentContextVar())) {
+      return true;
+    }
+
     if (store->is_dead()) {
       return false;
     }
-
     if (store->is_last()) {
       const intptr_t index = store->local().BitIndexIn(num_non_copied_params_);
       return GetLiveOutSet(block)->Contains(index);
     }
 
     return true;
   }
 
   // Returns true if the given load is the last for the local and the value
   // of the local will not flow into another one.
   bool IsLastLoad(BlockEntryInstr* block, LoadLocalInstr* load) {
+    if (load->local().Equals(*flow_graph_->CurrentContextVar())) {
+      return false;
+    }
     const intptr_t index = load->local().BitIndexIn(num_non_copied_params_);
     return load->is_last() && !GetLiveOutSet(block)->Contains(index);
   }
 
  private:
   virtual void ComputeInitialSets();
 
   const FlowGraph* flow_graph_;
   const intptr_t num_non_copied_params_;
   GrowableArray<BitVector*> assigned_vars_;
@@ skipping 65 matching lines @@
     intptr_t next_virtual_register_number,
     ZoneGrowableArray<Definition*>* inlining_parameters) {
   ASSERT((next_virtual_register_number == 0) || (inlining_parameters != NULL));
   current_ssa_temp_index_ = next_virtual_register_number;
   GrowableArray<BitVector*> dominance_frontier;
   ComputeDominators(&dominance_frontier);
 
   VariableLivenessAnalysis variable_liveness(this);
   variable_liveness.Analyze();
 
+  GrowableArray<PhiInstr*> live_phis;
+
   InsertPhis(preorder_,
              variable_liveness.ComputeAssignedVars(),
-             dominance_frontier);
+             dominance_frontier,
+             &live_phis);
 
-  GrowableArray<PhiInstr*> live_phis;
 
   // Rename uses to reference inserted phis where appropriate.
   // Collect phis that reach a non-environment use.
   Rename(&live_phis, &variable_liveness, inlining_parameters);
 
   // Propagate alive mark transitively from alive phis and then remove
   // non-live ones.
   RemoveDeadPhis(&live_phis);
 }
 
@@ skipping 112 matching lines @@
     (*label)[current_index] =
         Utils::Minimum((*label)[current_index], (*label)[next_index]);
     (*parent)[current_index] = (*parent)[next_index];
   }
 }
 
 
 void FlowGraph::InsertPhis(
     const GrowableArray<BlockEntryInstr*>& preorder,
     const GrowableArray<BitVector*>& assigned_vars,
-    const GrowableArray<BitVector*>& dom_frontier) {
+    const GrowableArray<BitVector*>& dom_frontier,
+    GrowableArray<PhiInstr*>* live_phis) {
   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 < variable_count(); ++var_index) {
+    const bool always_live = var_index == CurrentContextEnvIndex();
     // 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.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, variable_count());
+          PhiInstr* phi = block->AsJoinEntry()->InsertPhi(var_index,
+                                                          variable_count());
+          if (always_live) {
+            phi->mark_alive();
+            live_phis->Add(phi);
+          }
           has_already[index] = var_index;
           if (work[index] < var_index) {
             work[index] = var_index;
             worklist.Add(block);
           }
         }
       }
     }
   }
 }
 
 
 void FlowGraph::Rename(GrowableArray<PhiInstr*>* live_phis,
                        VariableLivenessAnalysis* variable_liveness,
                        ZoneGrowableArray<Definition*>* inlining_parameters) {
   GraphEntryInstr* entry = graph_entry();
 
   // Initial renaming environment.
   GrowableArray<Definition*> env(variable_count());
 
   // Add global constants to the initial definitions.
   constant_null_ = GetConstant(Object::ZoneHandle());
   constant_dead_ = GetConstant(Symbols::OptimizedOut());
+  constant_empty_context_ = GetConstant(Context::Handle(
+      isolate()->object_store()->empty_context()));
 
   // Add parameters to the initial definitions and renaming environment.
   if (inlining_parameters != NULL) {
     // Use known parameters.
     ASSERT(parameter_count() == inlining_parameters->length());
     for (intptr_t i = 0; i < parameter_count(); ++i) {
       Definition* defn = (*inlining_parameters)[i];
       AllocateSSAIndexes(defn);
       AddToInitialDefinitions(defn);
       env.Add(defn);
     }
   } else {
     // Create new parameters.  For functions compiled for OSR, the locals
     // are unknown and so treated like parameters.
     intptr_t count = IsCompiledForOsr() ? variable_count() : parameter_count();
     for (intptr_t i = 0; i < count; ++i) {
       ParameterInstr* param = new(isolate()) ParameterInstr(i, entry);
       param->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
       AddToInitialDefinitions(param);
       env.Add(param);
     }
   }
 
-  // Initialize all locals with #null in the renaming environment.  For OSR,
-  // the locals have already been handled as parameters.
+  // Initialize all locals in the renaming environment  For OSR, the locals have
+  // already been handled as parameters.
   if (!IsCompiledForOsr()) {
     for (intptr_t i = parameter_count(); i < variable_count(); ++i) {
-      env.Add(constant_null());
+      if (i == CurrentContextEnvIndex()) {
+        if (parsed_function().function().IsClosureFunction()) {
+          CurrentContextInstr* context = new CurrentContextInstr();
+          context->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
+          AddToInitialDefinitions(context);
+          env.Add(context);
+        } else {
+          env.Add(constant_empty_context());
+        }
+      } else {
+        env.Add(constant_null());
+      }
     }
   }
 
   if (entry->SuccessorCount() > 1) {
     // Functions with try-catch have a fixed area of stack slots reserved
     // so that all local variables are stored at a known location when
     // on entry to the catch.
     entry->set_fixed_slot_count(num_stack_locals() + num_copied_params());
   }
   RenameRecursive(entry, &env, live_phis, variable_liveness);
 }
 
 
 void FlowGraph::AttachEnvironment(Instruction* instr,
                                   GrowableArray<Definition*>* env) {
   Environment* deopt_env =
       Environment::From(isolate(),
                         *env,
                         num_non_copied_params_,
                         &parsed_function_);
-  // TODO(fschneider): Add predicates CanEagerlyDeoptimize and
-  // CanLazilyDeoptimize to instructions to generally deal with instructions
-  // that have pushed arguments and input operands.
-  // Right now, closure calls are the only instructions that have both. They
-  // also don't have an eager deoptimziation point, so the environment attached
-  // here is only used for after the call.
   if (instr->IsClosureCall()) {
     deopt_env = deopt_env->DeepCopy(isolate(),
                                     deopt_env->Length() - instr->InputCount());
   }
   instr->SetEnvironment(deopt_env);
   for (Environment::DeepIterator it(deopt_env); !it.Done(); it.Advance()) {
     Value* use = it.CurrentValue();
     use->definition()->AddEnvUse(use);
   }
   if (instr->CanDeoptimize()) {
     instr->env()->set_deopt_id(instr->deopt_id());
   }
 }
 
 
 void FlowGraph::RenameRecursive(BlockEntryInstr* block_entry,
                                 GrowableArray<Definition*>* env,
                                 GrowableArray<PhiInstr*>* live_phis,
                                 VariableLivenessAnalysis* variable_liveness) {
   // 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] = phi;
           phi->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
-          if (block_entry->InsideTryBlock()) {
+          if (block_entry->InsideTryBlock() && !phi->is_alive()) {
             // This is a safe approximation.  Inside try{} all locals are
             // used at every call implicitly, so we mark all phis as live
             // from the start.
             // TODO(fschneider): Improve this approximation to eliminate
             // more redundant phis.
             phi->mark_alive();
             live_phis->Add(phi);
           }
         }
       }
     }
   } else if (block_entry->IsCatchBlockEntry()) {
     // Add real definitions for all locals and parameters.
     for (intptr_t i = 0; i < env->length(); ++i) {
       ParameterInstr* param = new(isolate()) ParameterInstr(i, block_entry);
       param->set_ssa_temp_index(alloc_ssa_temp_index());  // New SSA temp.
       (*env)[i] = param;
       block_entry->AsCatchBlockEntry()->initial_definitions()->Add(param);
     }
   }
 
   // Prune non-live variables at block entry by replacing their environment
   // slots with null.
   BitVector* live_in = variable_liveness->GetLiveInSet(block_entry);
   for (intptr_t i = 0; i < variable_count(); i++) {
-    if (!live_in->Contains(i)) {
+    // TODO(fschneider): Make sure that live_in always contains the
+    // CurrentContext variable to avoid the special case here.
+    if (!live_in->Contains(i) && (i != CurrentContextEnvIndex())) {
       (*env)[i] = constant_dead();
     }
   }
 
   // Attach environment to the block entry.
   AttachEnvironment(block_entry, env);
 
   // 2. Process normal instructions.
   for (ForwardInstructionIterator it(block_entry); !it.Done(); it.Advance()) {
     Instruction* current = it.Current();
@@ skipping 422 matching lines @@
 }
 
 
 bool BlockEffects::IsSideEffectFreePath(BlockEntryInstr* from,
                                         BlockEntryInstr* to) const {
   return available_at_[to->postorder_number()]->Contains(
       from->postorder_number());
 }
 
 }  // namespace dart