Support constant folding of instructions with constant smi values.

runtime/vm/flow_graph_optimizer.cc

 // 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.
 
 #include "vm/flow_graph_optimizer.h"
 
 #include "vm/bit_vector.h"
 #include "vm/cha.h"
 #include "vm/flow_graph_builder.h"
 #include "vm/hash_map.h"
 #include "vm/il_printer.h"
 #include "vm/intermediate_language.h"
 #include "vm/object_store.h"
 #include "vm/parser.h"
 #include "vm/scopes.h"
 #include "vm/symbols.h"
 
 namespace dart {
 
 DECLARE_FLAG(bool, eliminate_type_checks);
 DECLARE_FLAG(bool, enable_type_checks);
 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();
 }
 
 
 static void ReplaceCurrentInstruction(ForwardInstructionIterator* it,
                                       Instruction* current,
                                       Instruction* replacement) {
   if ((replacement != NULL) && current->IsDefinition()) {
@@ skipping 2382 matching lines @@
     } else if (value.raw() == Bool::True()) {
       SetReachable(instr->true_successor());
     } else if (!IsUnknown(value)) {  // Any other constant.
       SetReachable(instr->false_successor());
     }
   }
 }
 
 
 // --------------------------------------------------------------------------
+// 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.
 void ConstantPropagator::VisitPhi(PhiInstr* instr) {
   // Compute the join over all the reachable predecessor values.
   JoinEntryInstr* block = instr->block();
   Object& value = Object::ZoneHandle(Unknown());
   for (intptr_t pred_idx = 0; pred_idx < instr->InputCount(); ++pred_idx) {
     if (reachable_->Contains(
             block->PredecessorAt(pred_idx)->preorder_number())) {
@@ skipping 43 matching lines @@
     ArgumentDefinitionTestInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitCurrentContext(CurrentContextInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
-void ConstantPropagator::VisitStoreContext(StoreContextInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::VisitClosureCall(ClosureCallInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitInstanceCall(InstanceCallInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitPolymorphicInstanceCall(
     PolymorphicInstanceCallInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitStaticCall(StaticCallInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 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();
 }
 
 
 void ConstantPropagator::VisitStrictCompare(StrictCompareInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
   const Object& right = instr->right()->definition()->constant_value();
   if (IsNonConstant(left) || IsNonConstant(right)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(left) && IsConstant(right)) {
@@ skipping 128 matching lines @@
     ExtractConstructorInstantiatorInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
 void ConstantPropagator::VisitAllocateContext(AllocateContextInstr* instr) {
   SetValue(instr, non_constant_);
 }
 
 
-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();
   if (IsNonConstant(left) || IsNonConstant(right)) {
     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;
+        }
         default:
           // TODO(kmillikin): support other smi operations.
           SetValue(instr, non_constant_);
       }
     } else {
       // TODO(kmillikin): support other types.
       SetValue(instr, non_constant_);
     }
   }
 }
@@ skipping 15 matching lines @@
   const Object& value = instr->value()->definition()->constant_value();
   if (IsNonConstant(value)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(value)) {
     // TODO(kmillikin): Handle unary operations.
     SetValue(instr, non_constant_);
   }
 }
 
 
-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)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(value)) {
     // TODO(kmillikin): Handle conversion.
     SetValue(instr, non_constant_);
   }
 }
 
 
 void ConstantPropagator::VisitSmiToDouble(SmiToDoubleInstr* instr) {
   // TODO(kmillikin): Handle conversion.
   SetValue(instr, non_constant_);
 }
 
 
-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());
 }
 
 
 void ConstantPropagator::VisitConstraint(ConstraintInstr* instr) {
   // Should not be used outside of range analysis.
   UNREACHABLE();
 }
 
 
-void ConstantPropagator::VisitCheckEitherNonSmi(CheckEitherNonSmiInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::VisitUnboxedDoubleBinaryOp(
     UnboxedDoubleBinaryOpInstr* instr) {
   const Object& left = instr->left()->definition()->constant_value();
   const Object& right = instr->right()->definition()->constant_value();
   if (IsNonConstant(left) || IsNonConstant(right)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(left) && IsConstant(right)) {
     // TODO(kmillikin): Handle binary operation.
     SetValue(instr, non_constant_);
   }
@@ skipping 26 matching lines @@
   const Object& value = instr->value()->definition()->constant_value();
   if (IsNonConstant(value)) {
     SetValue(instr, non_constant_);
   } else if (IsConstant(value)) {
     // TODO(kmillikin): Handle conversion.
     SetValue(instr, non_constant_);
   }
 }
 
 
-void ConstantPropagator::VisitCheckArrayBound(CheckArrayBoundInstr* instr) {
-  // Nothing to do. Not a value.
-}
-
-
 void ConstantPropagator::Analyze() {
   GraphEntryInstr* entry = graph_->graph_entry();
   reachable_->Add(entry->preorder_number());
   block_worklist_.Add(entry);
 
   while (true) {
     if (block_worklist_.is_empty()) {
       if (definition_worklist_.is_empty()) break;
       Definition* definition = definition_worklist_.Last();
       definition_worklist_.RemoveLast();
       definition_marks_->Remove(definition->ssa_temp_index());
       Value* use = definition->input_use_list();
       while (use != NULL) {
         use->instruction()->Accept(this);
         use = use->next_use();
       }
     } else {
       BlockEntryInstr* block = block_worklist_.Last();
       block_worklist_.RemoveLast();
       block->Accept(this);
     }
   }
 }
 
 
 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
   // transformation.
   for (BlockIterator b = graph_->reverse_postorder_iterator();
        !b.Done();
        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;
     }
 
     JoinEntryInstr* join = block->AsJoinEntry();
     if (join != NULL) {
       // Remove phi inputs corresponding to unreachable predecessor blocks.
       // Predecessors will be recomputed (in block id order) after removing
       // unreachable code so we merely have to keep the phi inputs in order.
       ZoneGrowableArray<PhiInstr*>* phis = join->phis();
       if (phis != NULL) {
@@ skipping 17 matching lines @@
             PhiInstr* phi = (*phis)[phi_idx];
             if (phi == NULL) continue;
             phi->inputs_.TruncateTo(live_count);
           }
         }
       }
     }
 
     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()));
       }
     }
 
     // Replace branches where one target is unreachable with jumps.
     BranchInstr* branch = block->last_instruction()->AsBranch();
     if (branch != NULL) {
       TargetEntryInstr* if_true = branch->true_successor();
       TargetEntryInstr* if_false = branch->false_successor();
       JoinEntryInstr* join = NULL;
       Instruction* next = NULL;
@@ skipping 13 matching lines @@
         join = new JoinEntryInstr(if_true->block_id(), if_true->try_index());
         next = if_true->next();
       }
 
       if (join != NULL) {
         // Replace the branch with a jump to the reachable successor.
         // Drop the comparison, which does not have side effects as long
         // 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);
         // Replace the false target entry with the new join entry. We will
         // recompute the dominators after this pass.
         join->set_next(next);
       }
     }
   }
 
   graph_->DiscoverBlocks();
   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();
+  }
 }
 
 
 }  // namespace dart