First step to SSA construction: Phi insertion.

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"
@@ skipping 264 matching lines @@
   virtual RawAbstractType* StaticType() const;                                 \
   virtual LocationSummary* MakeLocationSummary() const;                        \
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
 // Functions defined in all concrete value classes.
 #define DECLARE_VALUE(ShortName)                                               \
   DECLARE_COMPUTATION(ShortName)                                               \
   virtual void PrintTo(BufferFormatter* f) const;
 
 
+class Definition;
 class BindInstr;
+class PhiInstr;
 
 class UseVal : public Value {
  public:
-  explicit UseVal(BindInstr* definition) : definition_(definition) {}
+  explicit UseVal(Definition* definition) : definition_(definition) {}
 
   DECLARE_VALUE(Use)
 
-  BindInstr* definition() const { return definition_; }
+  Definition* definition() const { return definition_; }
+  void set_definition(Definition* definition) {
+    definition_ = definition;
+  }

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

Why do you need set_defintion?

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

Renaming. I could leave it out for this CL. Left-over from splitting my CL into
pieces.

 
  private:
-  BindInstr* definition_;
+  Definition* definition_;
 
   DISALLOW_COPY_AND_ASSIGN(UseVal);
 };
 
 
 class ConstantVal: public Value {
  public:
   explicit ConstantVal(const Object& value)
       : value_(value) {
     ASSERT(value.IsZoneHandle());
@@ skipping 1168 matching lines @@
     ASSERT(value != NULL);
     inputs_[0] = value;
   }
 
   Value* value() const { return inputs_[0]; }
 
   InstanceCallComp* instance_call() const { return instance_call_; }
 
   DECLARE_COMPUTATION(NumberNegate)
 
+  void InsertPhi(intptr_t variable_index) { }

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

Why is this needed?

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

Accidental edit.

+
  private:
   InstanceCallComp* instance_call_;
 
   DISALLOW_COPY_AND_ASSIGN(NumberNegateComp);
 };
 
 
 class CheckStackOverflowComp : public TemplateComputation<0> {
  public:
   CheckStackOverflowComp(intptr_t token_index, intptr_t try_index)
@@ skipping 40 matching lines @@
 
 // M is a single argument macro.  It is applied to each concrete instruction
 // type name.  The concrete instruction classes are the name with Instr
 // concatenated.
 #define FOR_EACH_INSTRUCTION(M)                                                \
   M(GraphEntry)                                                                \
   M(JoinEntry)                                                                 \
   M(TargetEntry)                                                               \
   M(Do)                                                                        \
   M(Bind)                                                                      \
+  M(Phi)                                                                       \
   M(Return)                                                                    \
   M(Throw)                                                                     \
   M(ReThrow)                                                                   \
   M(Branch)                                                                    \
 
 
 // Forward declarations for Instruction classes.
 class BlockEntryInstr;
 class FlowGraphBuilder;
 
 #define FORWARD_DECLARATION(type) class type##Instr;
 FOR_EACH_INSTRUCTION(FORWARD_DECLARATION)
 #undef FORWARD_DECLARATION
 
 
 // Functions required in all concrete instruction classes.
 #define DECLARE_INSTRUCTION(type)                                              \
   virtual Instruction* Accept(FlowGraphVisitor* visitor);                      \
   virtual bool Is##type() const { return true; }                               \
   virtual type##Instr* As##type() { return this; }                             \
   virtual intptr_t InputCount() const;                                         \
+  virtual Value* InputAt(intptr_t i) const;                                    \
   virtual const char* DebugName() const { return #type; }                      \
   virtual void PrintTo(BufferFormatter* f) const;                              \
   virtual void PrintToVisualizer(BufferFormatter* f) const;
 
 
 class Instruction : public ZoneAllocated {
  public:
   Instruction() : cid_(-1), ic_data_(NULL) {
     Isolate* isolate = Isolate::Current();
     cid_ = Computation::GetNextCid(isolate);
     ic_data_ = Computation::GetICDataForCid(cid_, isolate);
   }
 
   // Unique computation/instruction id, used for deoptimization, e.g. for
   // ReturnInstr, ThrowInstr and ReThrowInstr.
   intptr_t cid() const { return cid_; }
 
   const ICData* ic_data() const { return ic_data_; }
 
   virtual bool IsBlockEntry() const { return false; }
   BlockEntryInstr* AsBlockEntry() {
     return IsBlockEntry() ? reinterpret_cast<BlockEntryInstr*>(this) : NULL;
   }
-  virtual bool IsBindInstr() const { return false; }
-  virtual BindInstr* AsBindInstr() {
-    return NULL;
-  }
+  virtual bool IsDefinition() const { return false; }
+  virtual Definition* AsDefinition() { return NULL; }
 
   virtual intptr_t InputCount() const = 0;
+  virtual Value* InputAt(intptr_t i) const = 0;
 
   // Visiting support.
   virtual Instruction* Accept(FlowGraphVisitor* visitor) = 0;
 
   virtual Instruction* StraightLineSuccessor() const = 0;
   virtual void SetSuccessor(Instruction* instr) = 0;
 
   // Normal instructions can have 0 (inside a block) or 1 (last instruction in
   // a block) successors. Branch instruction with >1 successors override this
   // function.
@@ skipping 106 matching lines @@
 
   intptr_t postorder_number() const { return postorder_number_; }
   void set_postorder_number(intptr_t number) { postorder_number_ = number; }
 
   intptr_t block_id() const { return block_id_; }
   void set_block_id(intptr_t value) { block_id_ = value; }
 
   BlockEntryInstr* dominator() const { return dominator_; }
   void set_dominator(BlockEntryInstr* instr) { dominator_ = instr; }
 
+  // TODO(fschneider): Optimize the case of one child to save space.
+  GrowableArray<BlockEntryInstr*>* dominated_blocks() {
+    return &dominated_blocks_;
+  }

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

Instead of returning a modifieable array, better add:

void AddDominatedBlock(intptr_t block_index) {
  dominated_blocks_.Add(block_index);
}

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

Done.

+
   Instruction* last_instruction() const { return last_instruction_; }
   void set_last_instruction(Instruction* instr) { last_instruction_ = instr; }
 
   virtual void DiscoverBlocks(
       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),
         block_id_(-1),
         dominator_(NULL),
+        dominated_blocks_(1),
         last_instruction_(NULL) { }
 
  private:
   intptr_t preorder_number_;
   intptr_t postorder_number_;
   intptr_t block_id_;
   BlockEntryInstr* dominator_;  // Immediate dominator, NULL for graph entry.
+  GrowableArray<BlockEntryInstr*> dominated_blocks_;
   Instruction* last_instruction_;
 
   DISALLOW_COPY_AND_ASSIGN(BlockEntryInstr);
 };
 
 
 class GraphEntryInstr : public BlockEntryInstr {
  public:
   explicit GraphEntryInstr(TargetEntryInstr* normal_entry)
       : BlockEntryInstr(), normal_entry_(normal_entry), catch_entries_() { }
@@ skipping 31 matching lines @@
 
   DISALLOW_COPY_AND_ASSIGN(GraphEntryInstr);
 };
 
 
 class JoinEntryInstr : public BlockEntryInstr {
  public:
   JoinEntryInstr()
       : BlockEntryInstr(),
         predecessors_(2),  // Two is the assumed to be the common case.
-        successor_(NULL) { }
+        successor_(NULL),
+        phis_(NULL),
+        phi_count_(0) { }
 
   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;
   }
 
+  ZoneGrowableArray<PhiInstr*>* phis() const { return phis_; }

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

const ZoneGrowableArray<...>& ?

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

phis_ can be NULL.

+
   virtual void PrepareEntry(FlowGraphCompiler* compiler);
 
+  void InsertPhi(intptr_t var_index, intptr_t var_count);

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

Get rid of var_count, it is used only to allocate optimal capacity of growable
array.

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

Growable arrays incur a high cost when not used with good initial size
estimates. (in this case I actually want a fixed-size array). I need some
initial size and this is readily available to avoid reallocating 3 times for
adding very few elements.

[srdjan, 2012/06/13 18:45:26]

Yes, but the 'var_count' looks weird in the API, as it has nothing to do with
the computation of phis. Have we measured a negative performance impact so that
it validates the more complicate API?  We must refrain from premature
optimizations (e.g., passing isolates, zones, best allocation size)!

+
+  intptr_t phi_count() const { return phi_count_; }
+
  private:
   ZoneGrowableArray<BlockEntryInstr*> predecessors_;
   Instruction* successor_;
+  ZoneGrowableArray<PhiInstr*>* phis_;
+  intptr_t phi_count_;
 
   DISALLOW_COPY_AND_ASSIGN(JoinEntryInstr);
 };
 
 
 class TargetEntryInstr : public BlockEntryInstr {
  public:
   TargetEntryInstr()
       : BlockEntryInstr(),
         predecessor_(NULL),
@@ skipping 82 matching lines @@
   }
 
  private:
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(DoInstr);
 };
 
 
-class BindInstr : public Instruction {
+class Definition : public Instruction {
+ public:
+  Definition() : temp_index_(-1) { }
+
+  virtual bool IsDefinition() const { return true; }
+  virtual Definition* AsDefinition() { return this; }
+
+  intptr_t temp_index() const { return temp_index_; }
+  void set_temp_index(intptr_t index) { temp_index_ = index; }

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

Add a comment to something like that this is the common sueprclass of Phis and
Binds and is not allocatable (since it does not DECLARE_INSTRUCTION)

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

Done.

+
+ private:
+  intptr_t temp_index_;
+
+  DISALLOW_COPY_AND_ASSIGN(Definition);
+};
+
+
+class BindInstr : public Definition {
  public:
   explicit BindInstr(Computation* computation)
-      : temp_index_(-1), computation_(computation), successor_(NULL) {
+      : computation_(computation), successor_(NULL) {
     ASSERT(computation != NULL);
     computation->set_instr(this);
   }
 
   DECLARE_INSTRUCTION(Bind)
 
-  virtual bool IsBindInstr() const { return true; }
-  virtual BindInstr* AsBindInstr() { return this; }
-
-  intptr_t temp_index() const { return temp_index_; }
-  void set_temp_index(intptr_t index) { temp_index_ = index; }
-
   Computation* computation() const { return computation_; }
   virtual void replace_computation(Computation* value) { computation_ = value; }
 
   virtual Instruction* StraightLineSuccessor() const {
     return successor_;
   }
 
   virtual void SetSuccessor(Instruction* instr) {
     ASSERT(successor_ == NULL);
     successor_ = instr;
   }
 
   // Static type of the underlying computation.
   virtual RawAbstractType* StaticType() const {
     return computation()->StaticType();
   }
 
   virtual void RecordAssignedVars(BitVector* assigned_vars);
 
   virtual LocationSummary* locs() {
     return computation()->locs();
   }
 
   virtual void EmitNativeCode(FlowGraphCompiler* compiler);
 
  private:
-  intptr_t temp_index_;
   Computation* computation_;
   Instruction* successor_;
 
   DISALLOW_COPY_AND_ASSIGN(BindInstr);
 };
 
 
+class PhiInstr: public Definition {
+ public:
+  explicit PhiInstr(intptr_t num_inputs) : inputs_(num_inputs) {
+    for (intptr_t i = 0; i < num_inputs; ++i) {
+      inputs_.Add(NULL);
+    }
+  }
+
+  DECLARE_INSTRUCTION(Phi)
+
+  void SetInputAt(intptr_t i, Value* value) {
+    inputs_[i] = value;
+  }
+
+  virtual Instruction* StraightLineSuccessor() const { return NULL; }
+  virtual void SetSuccessor(Instruction* instr) { UNREACHABLE(); }
+
+ private:
+  GrowableArray<Value*> inputs_;
+
+  DISALLOW_COPY_AND_ASSIGN(PhiInstr);
+};
+
+
+
+
 class ReturnInstr : public InstructionWithInputs {
  public:
   ReturnInstr(intptr_t token_index, Value* value)
       : InstructionWithInputs(), token_index_(token_index), value_(value) {
     ASSERT(value_ != NULL);
   }
 
   DECLARE_INSTRUCTION(Return)
 
   Value* value() const { return value_; }
@@ skipping 177 matching lines @@
   const GrowableArray<BlockEntryInstr*>& block_order_;
 
  private:
   DISALLOW_COPY_AND_ASSIGN(FlowGraphVisitor);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_INTERMEDIATE_LANGUAGE_H_