Initial implementation of sparse conditional constant propagation.

runtime/vm/flow_graph_optimizer.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_FLOW_GRAPH_OPTIMIZER_H_
 #define VM_FLOW_GRAPH_OPTIMIZER_H_
 
 #include "vm/intermediate_language.h"
 #include "vm/flow_graph.h"
 
@@ skipping 138 matching lines @@
  public:
   static void Optimize(FlowGraph* graph);
 
  private:
   static void OptimizeRecursive(
       BlockEntryInstr* entry,
       DirectChainedHashMap<Definition*>* map);
 };
 
 
+// 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_