Compute assigned variables and dominance frontiers.

runtime/vm/intermediate_language.h

 // 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.
 
 #ifndef VM_INTERMEDIATE_LANGUAGE_H_
 #define VM_INTERMEDIATE_LANGUAGE_H_
 
 #include "vm/allocation.h"
 #include "vm/ast.h"
 #include "vm/growable_array.h"
 #include "vm/handles_impl.h"
 #include "vm/object.h"
 
 namespace dart {
 
+class BitVector;
 class FlowGraphVisitor;
 class LocalVariable;
 
 // M is a two argument macro.  It is applied to each concrete value's
 // typename and classname.
 #define FOR_EACH_VALUE(M)                                                      \
   M(Use, UseVal)                                                               \
   M(Constant, ConstantVal)                                                     \
 
 
@@ skipping 53 matching lines @@
   // Unique computation/instruction id, used for deoptimization.
   intptr_t cid() const { return cid_; }
 
   const ICData* ic_data() const { return ic_data_; }
 
   // Visiting support.
   virtual void Accept(FlowGraphVisitor* visitor) = 0;
 
   virtual intptr_t InputCount() const = 0;
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);

[srdjan, 2012/05/12 00:00:55]

Please document what does BitVector represent.

[Kevin Millikin (Google), 2012/05/15 11:51:44]

Done.

+
  private:
   friend class Instruction;
   static intptr_t GetNextCid(Isolate* isolate) {
     intptr_t tmp = isolate->computation_id();
     isolate->set_computation_id(tmp + 1);
     return tmp;
   }
   static ICData* GetICDataForCid(intptr_t cid, Isolate* isolate) {
     if (isolate->ic_data_array() == Array::null()) {
       return NULL;
@@ skipping 412 matching lines @@
       : local_(local), context_level_(context_level) {
     inputs_[0] = value;
   }
 
   DECLARE_COMPUTATION(StoreLocal)
 
   const LocalVariable& local() const { return local_; }
   Value* value() { return inputs_[0]; }
   intptr_t context_level() const { return context_level_; }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
  private:
   const LocalVariable& local_;
   const intptr_t context_level_;
 
   DISALLOW_COPY_AND_ASSIGN(StoreLocalComp);
 };
 
 
 class NativeCallComp : public TemplateComputation<0> {
  public:
@@ skipping 654 matching lines @@
   virtual Instruction* StraightLineSuccessor() const = 0;
   virtual void SetSuccessor(Instruction* instr) = 0;
 
   // Discover basic-block structure by performing a recursive depth first
   // traversal of the instruction graph reachable from this instruction.  As
   // a side effect, the block entry instructions in the graph are assigned
   // numbers in both preorder and postorder.  The array 'preorder' maps
   // preorder block numbers to the block entry instruction with that number
   // and analogously for the array 'postorder'.  The depth first spanning
   // tree is recorded in the array 'parent', which maps preorder block
-  // numbers to the preorder number of the block's spanning-tree parent.  As
-  // a side effect of this function, the set of basic block predecessors
-  // (e.g., block entry instructions of predecessor blocks) and also the
-  // last instruction in the block is recorded in each entry instruction.
+  // numbers to the preorder number of the block's spanning-tree parent.
+  // The array 'assigned_vars' maps preorder block numbers to the set of
+  // assigned frame-allocated local variables in the block.  As a side
+  // effect of this function, the set of basic block predecessors (e.g.,
+  // block entry instructions of predecessor blocks) and also the last
+  // instruction in the block is recorded in each entry instruction.
   virtual void DiscoverBlocks(
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent) {
+      GrowableArray<intptr_t>* parent,
+      GrowableArray<BitVector*>* assigned_vars,
+      intptr_t variable_count) {
     // Never called for instructions except block entries and branches.
     UNREACHABLE();
   }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
 #define INSTRUCTION_TYPE_CHECK(type)                                           \
   virtual bool Is##type() const { return false; }                              \
   virtual type##Instr* As##type() { return NULL; }
 FOR_EACH_INSTRUCTION(INSTRUCTION_TYPE_CHECK)
 #undef INSTRUCTION_TYPE_CHECK
 
  private:
   intptr_t cid_;
   ICData* ic_data_;
   DISALLOW_COPY_AND_ASSIGN(Instruction);
 };
 
 
 // Basic block entries are administrative nodes.  Joins are the only nodes
 // with multiple predecessors.  Targets are the other basic block entries.
 // The types enforce edge-split form---joins are forbidden as the successors
 // of branches.
 class BlockEntryInstr : public Instruction {
  public:
   virtual bool IsBlockEntry() const { return true; }
 
   virtual intptr_t PredecessorCount() const = 0;
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const = 0;
+  virtual void AddPredecessor(BlockEntryInstr* predecessor) = 0;
 
   intptr_t preorder_number() const { return preorder_number_; }
   void set_preorder_number(intptr_t number) { preorder_number_ = number; }
 
   intptr_t postorder_number() const { return postorder_number_; }
   void set_postorder_number(intptr_t number) { postorder_number_ = number; }
 
   BlockEntryInstr* dominator() const { return dominator_; }
   void set_dominator(BlockEntryInstr* instr) { dominator_ = instr; }
 
   Instruction* last_instruction() const { return last_instruction_; }
   void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
 
+  virtual void DiscoverBlocks(

[Kevin Millikin (Google), 2012/05/11 10:39:00]

All these arguments is a bad smell, I plan to refactor later.

[srdjan, 2012/05/12 00:00:55]

Sounds good.

+      BlockEntryInstr* current_block,
+      GrowableArray<BlockEntryInstr*>* preorder,
+      GrowableArray<BlockEntryInstr*>* postorder,
+      GrowableArray<intptr_t>* parent,
+      GrowableArray<BitVector*>* assigned_vars,
+      intptr_t variable_count);
+
  protected:
   BlockEntryInstr()
       : preorder_number_(-1),
         postorder_number_(-1),
         dominator_(NULL),
         last_instruction_(NULL) { }
 
  private:
   intptr_t preorder_number_;
   intptr_t postorder_number_;
@@ skipping 10 matching lines @@
       : BlockEntryInstr(),
         predecessors_(2),  // Two is the assumed to be the common case.
         successor_(NULL) { }
 
   DECLARE_INSTRUCTION(JoinEntry)
 
   virtual intptr_t PredecessorCount() const { return predecessors_.length(); }
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
     return predecessors_[index];
   }
+  virtual void AddPredecessor(BlockEntryInstr* predecessor) {
+    predecessors_.Add(predecessor);
+  }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void DiscoverBlocks(
-      BlockEntryInstr* current_block,
-      GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent);
-
  private:
   ZoneGrowableArray<BlockEntryInstr*> predecessors_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
 };
 
 
 class TargetEntryInstr : public BlockEntryInstr {
  public:
@@ skipping 12 matching lines @@
 
   DECLARE_INSTRUCTION(TargetEntry)
 
   virtual intptr_t PredecessorCount() const {
     return (predecessor_ == NULL) ? 0 : 1;
   }
   virtual BlockEntryInstr* PredecessorAt(intptr_t index) const {
     ASSERT((index == 0) && (predecessor_ != NULL));
     return predecessor_;
   }
+  virtual void AddPredecessor(BlockEntryInstr* predecessor) {
+    ASSERT(predecessor_ == NULL);
+    predecessor_ = predecessor;
+  }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
-  virtual void DiscoverBlocks(
-      BlockEntryInstr* current_block,
-      GrowableArray<BlockEntryInstr*>* preorder,
-      GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent);
-
   bool HasTryIndex() const {
     return try_index_ != CatchClauseNode::kInvalidTryIndex;
   }
 
   intptr_t try_index() const {
     ASSERT(HasTryIndex());
     return try_index_;
   }
 
  private:
@@ skipping 15 matching lines @@
   Computation* computation() const { return computation_; }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(DoInstr);
 };
 
 
 class Definition : public Instruction {
  public:
@@ skipping 21 matching lines @@
   Computation* computation() const { return computation_; }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
+  virtual void RecordAssignedVars(BitVector* assigned_vars);
+
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
 // The non-optimizing compiler assumes that there is exactly one use of
 // every temporary so they can be deallocated at their use.  Some AST nodes,
@@ skipping 181 matching lines @@
   TargetEntryInstr** true_successor_address() { return &true_successor_; }
   TargetEntryInstr** false_successor_address() { return &false_successor_; }
 
   virtual Instruction* StraightLineSuccessor() const { return NULL; }
   virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
 
   virtual void DiscoverBlocks(
       BlockEntryInstr* current_block,
       GrowableArray<BlockEntryInstr*>* preorder,
       GrowableArray<BlockEntryInstr*>* postorder,
-      GrowableArray<intptr_t>* parent);
+      GrowableArray<intptr_t>* parent,
+      GrowableArray<BitVector*>* assigned_vars,
+      intptr_t variable_count);
 
  private:
   Value* value_;
   TargetEntryInstr* true_successor_;
   TargetEntryInstr* false_successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BranchInstr);
 };
 
 #undef DECLARE_INSTRUCTION
@@ skipping 36 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_