Support constant folding of instructions with constant smi values.

runtime/vm/flow_graph_optimizer.cc

Index: runtime/vm/flow_graph_optimizer.cc
diff --git a/runtime/vm/flow_graph_optimizer.cc b/runtime/vm/flow_graph_optimizer.cc
index dc706fb19f158f616617e002052997c5bd041804..5183750c77222d7fb3a3bf252394ec53233a5c2f 100644
--- a/runtime/vm/flow_graph_optimizer.cc
+++ b/runtime/vm/flow_graph_optimizer.cc
@@ -23,6 +23,8 @@ DEFINE_FLAG(bool, trace_optimization, false, "Print optimization details.");
 DECLARE_FLAG(bool, trace_type_check_elimination);
 DEFINE_FLAG(bool, use_cha, true, "Use class hierarchy analysis.");
 DEFINE_FLAG(bool, load_cse, true, "Use redundant load elimination.");
+DEFINE_FLAG(bool, trace_constant_propagation, false,
+            "Print constant propagation and useless code elimination.");
 
 void FlowGraphOptimizer::ApplyICData() {
   VisitBlocks();
@@ -2425,6 +2427,35 @@ void ConstantPropagator::VisitBranch(BranchInstr* instr) {
 
 
 // --------------------------------------------------------------------------
+// Analysis of non-definition instructions.  They do not have values so they
+// cannot have constant values.
+void ConstantPropagator::VisitStoreContext(StoreContextInstr* instr) { }
+
+
+void ConstantPropagator::VisitChainContext(ChainContextInstr* instr) { }
+
+
+void ConstantPropagator::VisitCatchEntry(CatchEntryInstr* instr) { }
+
+
+void ConstantPropagator::VisitCheckStackOverflow(
+    CheckStackOverflowInstr* instr) { }
+
+
+void ConstantPropagator::VisitCheckClass(CheckClassInstr* instr) { }
+
+
+void ConstantPropagator::VisitCheckSmi(CheckSmiInstr* instr) { }
+
+
+void ConstantPropagator::VisitCheckEitherNonSmi(
+    CheckEitherNonSmiInstr* instr) { }
+
+
+void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) { }
+
+
+// --------------------------------------------------------------------------
 // Analysis of definitions.  Compute the constant value.  If it has changed
 // and the definition has input uses, add the definition to the definition
 // worklist so that the used can be processed.
@@ -2488,11 +2519,6 @@ void ConstantPropagator::VisitCurrentContext(CurrentContextInstr* instr) {
 }
 
 
-void ConstantPropagator::VisitStoreContext(StoreContextInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::VisitClosureCall(ClosureCallInstr* instr) {
   SetValue(instr, non_constant_);
 }
@@ -2515,11 +2541,13 @@ void ConstantPropagator::VisitStaticCall(StaticCallInstr* instr) {
 
 
 void ConstantPropagator::VisitLoadLocal(LoadLocalInstr* instr) {
+  // Instruction is eliminated when translating to SSA.
   UNREACHABLE();
 }
 
 
 void ConstantPropagator::VisitStoreLocal(StoreLocalInstr* instr) {
+  // Instruction is eliminated when translating to SSA.
   UNREACHABLE();
 }
 
@@ -2668,21 +2696,11 @@ void ConstantPropagator::VisitAllocateContext(AllocateContextInstr* instr) {
 }
 
 
-void ConstantPropagator::VisitChainContext(ChainContextInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::VisitCloneContext(CloneContextInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
-void ConstantPropagator::VisitCatchEntry(CatchEntryInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::VisitBinarySmiOp(BinarySmiOpInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
   const Object& right = instr->right()->definition()->constant_value();
@@ -2690,15 +2708,31 @@ void ConstantPropagator::VisitBinarySmiOp(BinarySmiOpInstr* instr) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(left) && IsConstant(right)) {
     if (left.IsSmi() && right.IsSmi()) {
+      const Smi& left_smi = Smi::Cast(left);
+      const Smi& right_smi = Smi::Cast(right);
       switch (instr->op_kind()) {
         case Token::kADD:
         case Token::kSUB:
         case Token::kMUL:
         case Token::kTRUNCDIV:
         case Token::kMOD: {
-          const Object& result =
-              Integer::ZoneHandle(Smi::Cast(left).BinaryOp(instr->op_kind(),
-                                                           Smi::Cast(right)));
+          const Object& result = Integer::ZoneHandle(
+              left_smi.ArithmeticOp(instr->op_kind(), right_smi));
+          SetValue(instr, result);
+          break;
+        }
+        case Token::kSHL:
+        case Token::kSHR: {
+          const Object& result = Integer::ZoneHandle(
+              left_smi.ShiftOp(instr->op_kind(), right_smi));
+          SetValue(instr, result);
+          break;
+        }
+        case Token::kBIT_AND:
+        case Token::kBIT_OR:
+        case Token::kBIT_XOR: {
+          const Object& result = Integer::ZoneHandle(
+              left_smi.BitOp(instr->op_kind(), right_smi));
           SetValue(instr, result);
           break;
         }
@@ -2737,12 +2771,6 @@ void ConstantPropagator::VisitUnarySmiOp(UnarySmiOpInstr* instr) {
 }
 
 
-void ConstantPropagator::VisitCheckStackOverflow(
-    CheckStackOverflowInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::VisitDoubleToDouble(DoubleToDoubleInstr* instr) {
   const Object& value = instr->value()->definition()->constant_value();
   if (IsNonConstant(value)) {
@@ -2760,16 +2788,6 @@ void ConstantPropagator::VisitSmiToDouble(SmiToDoubleInstr* instr) {
 }
 
 
-void ConstantPropagator::VisitCheckClass(CheckClassInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
-void ConstantPropagator::VisitCheckSmi(CheckSmiInstr* instr) {
-  // Nothing to do. Has no value.
-}
-
-
 void ConstantPropagator::VisitConstant(ConstantInstr* instr) {
   SetValue(instr, instr->value());
 }
@@ -2781,11 +2799,6 @@ void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) {
 }
 
 
-void ConstantPropagator::VisitCheckEitherNonSmi(CheckEitherNonSmiInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::VisitUnboxedDoubleBinaryOp(
     UnboxedDoubleBinaryOpInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
@@ -2832,11 +2845,6 @@ void ConstantPropagator::VisitBoxDouble(BoxDoubleInstr* instr) {
 }
 
 
-void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::Analyze() {
   GraphEntryInstr* entry = graph_->graph_entry();
   reachable_->Add(entry->preorder_number());
@@ -2863,6 +2871,12 @@ void ConstantPropagator::Analyze() {
 
 
 void ConstantPropagator::Transform() {
+  if (FLAG_trace_constant_propagation) {
+    OS::Print("\n==== Before constant propagation ====\n");
+    FlowGraphPrinter printer(*graph_);
+    printer.PrintBlocks();
+  }
+
   // We will recompute dominators, block ordering, block ids, block last
   // instructions, previous pointers, predecessors, etc. after eliminating
   // unreachable code.  We do not maintain those properties during the
@@ -2872,6 +2886,9 @@ void ConstantPropagator::Transform() {
        b.Advance()) {
     BlockEntryInstr* block = b.Current();
     if (!reachable_->Contains(block->preorder_number())) {
+      if (FLAG_trace_constant_propagation) {
+        OS::Print("Unreachable B%"Pd"\n", block->block_id());
+      }
       continue;
     }
 
@@ -2909,17 +2926,23 @@ void ConstantPropagator::Transform() {
 
     for (ForwardInstructionIterator i(block); !i.Done(); i.Advance()) {
       Definition* defn = i.Current()->AsDefinition();
-      if (defn != NULL && IsConstant(defn->constant_value())) {
-        if (!defn->IsConstant() &&
-            !defn->IsPushArgument() &&
-            !defn->IsStoreLocal() &&
-            !defn->IsStoreIndexed() &&
-            !defn->IsStoreInstanceField() &&
-            !defn->IsStoreStaticField() &&
-            !defn->IsStoreVMField()) {
-          // TODO(kmillikin): propagate constants to replace instructions
-          // without side effects.
+      // Replace constant-valued instructions without observable side
+      // effects.  Do this for smis only to avoid having to copy other
+      // objects into the heap's old generation.

[Florian Schneider, 2012/09/24 11:36:17]

Maybe add a TODO to extend the analysis for bool-valued constants or other known
old-space objects like null.

[Kevin Millikin (Google), 2012/09/24 12:23:46]

Done.

+      if ((defn != NULL) &&
+          defn->constant_value().IsSmi() &&
+          !defn->IsConstant() &&
+          !defn->IsPushArgument() &&
+          !defn->IsStoreIndexed() &&
+          !defn->IsStoreInstanceField() &&
+          !defn->IsStoreStaticField() &&
+          !defn->IsStoreVMField()) {
+        if (FLAG_trace_constant_propagation) {
+          OS::Print("Constant v%"Pd" = %s\n",
+                    defn->ssa_temp_index(),
+                    defn->constant_value().ToCString());
         }
+        i.ReplaceCurrentWith(new ConstantInstr(defn->constant_value()));
       }
     }
 
@@ -2953,10 +2976,6 @@ void ConstantPropagator::Transform() {
         // as it is a strict compare (the only one we can determine is
         // constant with the current analysis).
         GotoInstr* jump = new GotoInstr(join);
-        // Removing the branch from the graph will leave the iterator in a
-        // state where current is detached from the graph.  Since current
-        // has no successors and neither does its replacement, that's
-        // safe.
         Instruction* previous = branch->previous();
         branch->set_previous(NULL);
         previous->set_next(jump);
@@ -2971,6 +2990,12 @@ void ConstantPropagator::Transform() {
   GrowableArray<BitVector*> dominance_frontier;
   graph_->ComputeDominators(&dominance_frontier);
   graph_->ComputeUseLists();
+
+  if (FLAG_trace_constant_propagation) {
+    OS::Print("\n==== After constant propagation ====\n");
+    FlowGraphPrinter printer(*graph_);
+    printer.PrintBlocks();
+  }
 }