Initial implementation of sparse conditional constant propagation.

runtime/vm/flow_graph_optimizer.h

Index: runtime/vm/flow_graph_optimizer.h
diff --git a/runtime/vm/flow_graph_optimizer.h b/runtime/vm/flow_graph_optimizer.h
index 4efbbf0b7ee26f0feb36a463a47edf57ab679db1..fe4cc9af1ff24c61a1266f92588f5e7e773f0c9f 100644
--- a/runtime/vm/flow_graph_optimizer.h
+++ b/runtime/vm/flow_graph_optimizer.h
@@ -156,6 +156,69 @@ class DominatorBasedCSE : public AllStatic {
 };
 
 
+// Sparse conditional constant propagation and unreachable code elimination.
+// Assumes that use lists are computed and preserves them.
+class ConstantPropagator : public FlowGraphVisitor {
+ public:
+  explicit ConstantPropagator(FlowGraph* graph);
+
+  static void Optimize(FlowGraph* graph) {
+    ConstantPropagator cp(graph);
+    cp.Analyze();
+    cp.Transform();
+  }
+
+  // Used to initialize the abstract value of definitions.
+  static RawObject* Unknown() { return Object::transition_sentinel(); }
+
+ private:
+  void Analyze();
+  void Transform();
+
+  void SetReachable(BlockEntryInstr* block);
+  void SetValue(Definition* definition, const Object& value);
+
+  // Assign the join (least upper bound) of a pair of abstract values to the
+  // first one.
+  void Join(Object& left, const Object& right);
+
+  bool IsUnknown(const Object& value) {
+    return value.raw() == unknown_.raw();
+  }
+  bool IsNonConstant(const Object& value) {
+    return value.raw() == non_constant_.raw();
+  }
+  bool IsConstant(const Object& value) {
+    return !IsNonConstant(value) && !IsUnknown(value);
+  }
+
+  virtual void VisitBlocks() { UNREACHABLE(); }
+
+#define DECLARE_VISIT(type) virtual void Visit##type(type##Instr* instr);
+  FOR_EACH_INSTRUCTION(DECLARE_VISIT)
+#undef DECLARE_VISIT
+
+  FlowGraph* graph_;
+
+  // Sentinels for unknown constant and non-constant values.
+  const Object& unknown_;
+  const Object& non_constant_;
+
+  // Analysis results. For each block, a reachability bit.  Indexed by
+  // preorder number.
+  BitVector* reachable_;
+
+  // Definitions can move up the lattice twice, so we use a mark bit to
+  // indicate that they are already on the worklist in order to avoid adding
+  // them again.  Indexed by SSA temp index.
+  BitVector* definition_marks_;
+
+  // Worklists of blocks and definitions.
+  GrowableArray<BlockEntryInstr*> block_worklist_;
+  GrowableArray<Definition*> definition_worklist_;
+};
+
+
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_OPTIMIZER_H_