Turn definitions that do not produce results (e.g. Checks) into instructions.

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"
@@ skipping 15 matching lines @@
 void FlowGraphOptimizer::ApplyICData() {
   VisitBlocks();
 }
 
 
 void FlowGraphOptimizer::OptimizeComputations() {
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     BlockEntryInstr* entry = block_order_[i];
     entry->Accept(this);
     for (ForwardInstructionIterator it(entry); !it.Done(); it.Advance()) {
-      Definition* defn = it.Current()->AsDefinition();
-      if (defn != NULL) {
-        Definition* result = defn->Canonicalize();
-        if (result != defn) {
-          if (result != NULL) {
-            defn->ReplaceUsesWith(result);
-            if (FLAG_trace_optimization) {
-              OS::Print("Replacing v%"Pd" with v%"Pd"\n",
-                        defn->ssa_temp_index(),
-                        result->ssa_temp_index());
-            }
-          } else if (FLAG_trace_optimization) {
-              OS::Print("Removing v%"Pd".\n", defn->ssa_temp_index());
+      Instruction* current = it.Current();
+      Instruction* replacement = current->Canonicalize();
+      if (replacement != current) {

[Florian Schneider, 2012/09/19 13:24:49]

Maybe assert that Canonicalize for Instructions returns either NULL or this.

[Vyacheslav Egorov (Google), 2012/09/21 12:51:40]

Done.

+        if ((replacement != NULL) && current->IsDefinition()) {
+          Definition* current_defn = current->AsDefinition();
+          Definition* replacement_defn = replacement->AsDefinition();
+          ASSERT(replacement_defn != NULL);
+          current_defn->ReplaceUsesWith(replacement_defn);
+          if (FLAG_trace_optimization) {
+            OS::Print("Replacing v%"Pd" with v%"Pd"\n",
+                      current_defn->ssa_temp_index(),
+                      replacement_defn->ssa_temp_index());
           }
-          it.RemoveCurrentFromGraph();
+        } else if (FLAG_trace_optimization) {
+          ASSERT(!current->IsDefinition() ||
+                 ((current->AsDefinition()->input_use_list() == NULL) &&
+                  (current->AsDefinition()->env_use_list() == NULL)));
+          if (current->IsDefinition()) {
+            OS::Print("Removing v%"Pd".\n",
+                      current->AsDefinition()->ssa_temp_index());
+          } else {
+            OS::Print("Removing %s\n", current->DebugName());
+          }
         }
+        it.RemoveCurrentFromGraph();
       }
     }
   }
 }
 
 
 static Definition* CreateConversion(Representation from,
                                     Representation to,
                                     Definition* def,
                                     Instruction* deopt_target) {
@@ skipping 345 matching lines @@
       call->ReplaceWith(array_op, current_iterator());
       RemovePushArguments(call);
       return true;
     }
     default:
       return false;
   }
 }
 
 
-void FlowGraphOptimizer::InsertBefore(Instruction* instr,
-                                      Definition* defn,
+void FlowGraphOptimizer::InsertBefore(Instruction* next,
+                                      Instruction* instr,
                                       Environment* env,
                                       Definition::UseKind use_kind) {
-  if (env != NULL) env->DeepCopyTo(defn);
+  if (env != NULL) env->DeepCopyTo(instr);
   if (use_kind == Definition::kValue) {
-    defn->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
+    ASSERT(instr->IsDefinition());
+    instr->AsDefinition()->set_ssa_temp_index(
+        flow_graph_->alloc_ssa_temp_index());
   }
-  defn->InsertBefore(instr);
+  instr->InsertBefore(next);
 }
 
 
-void FlowGraphOptimizer::InsertAfter(Instruction* instr,
-                                     Definition* defn,
+void FlowGraphOptimizer::InsertAfter(Instruction* prev,
+                                     Instruction* instr,
                                      Environment* env,
                                      Definition::UseKind use_kind) {
-  if (env != NULL) env->DeepCopyTo(defn);
+  if (env != NULL) env->DeepCopyTo(instr);
   if (use_kind == Definition::kValue) {
-    defn->set_ssa_temp_index(flow_graph_->alloc_ssa_temp_index());
+    ASSERT(instr->IsDefinition());
+    instr->AsDefinition()->set_ssa_temp_index(
+        flow_graph_->alloc_ssa_temp_index());
   }
-  defn->InsertAfter(instr);
+  instr->InsertAfter(prev);
 }
 
 
 bool FlowGraphOptimizer::TryReplaceWithBinaryOp(InstanceCallInstr* call,
                                                 Token::Kind op_kind) {
   intptr_t operands_type = kIllegalCid;
   ASSERT(call->HasICData());
   const ICData& ic_data = *call->ic_data();
   switch (op_kind) {
     case Token::kADD:
@@ skipping 976 matching lines @@
     if (header->dominator() == candidate) {
       return candidate;
     }
   }
   return NULL;
 }
 
 
 void LICM::Hoist(ForwardInstructionIterator* it,
                  BlockEntryInstr* pre_header,
-                 Definition* current) {
+                 Instruction* current) {
   // TODO(fschneider): Avoid repeated deoptimization when
   // speculatively hoisting checks.
   if (FLAG_trace_optimization) {
     OS::Print("Hoisting instruction %s:%"Pd" from B%"Pd" to B%"Pd"\n",
               current->DebugName(),
               current->deopt_id(),
               current->GetBlock()->block_id(),
               pre_header->block_id());
   }
   // Move the instruction out of the loop.
   it->RemoveCurrentFromGraph();
   GotoInstr* last = pre_header->last_instruction()->AsGoto();
   current->InsertBefore(last);
   // Attach the environment of the Goto instruction to the hoisted
   // instruction and set the correct deopt_id.
   ASSERT(last->env() != NULL);
   last->env()->DeepCopyTo(current);
   current->deopt_id_ = last->GetDeoptId();
 }
 
 
 void LICM::TryHoistCheckSmiThroughPhi(ForwardInstructionIterator* it,
                                       BlockEntryInstr* header,
                                       BlockEntryInstr* pre_header,
-                                      Definition* current) {
+                                      Instruction* current) {
   PhiInstr* phi = current->InputAt(0)->definition()->AsPhi();
   if (!header->loop_info()->Contains(phi->block()->preorder_number())) {
     return;
   }
 
   if (phi->GetPropagatedCid() == kSmiCid) {
     it->RemoveCurrentFromGraph();
     return;
   }
 
@@ skipping 36 matching lines @@
     BlockEntryInstr* pre_header = FindPreHeader(header);
     if (pre_header == NULL) continue;
 
     for (BitVector::Iterator loop_it(header->loop_info());
          !loop_it.Done();
          loop_it.Advance()) {
       BlockEntryInstr* block = flow_graph->preorder()[loop_it.Current()];
       for (ForwardInstructionIterator it(block);
            !it.Done();
            it.Advance()) {
-        Definition* current = it.Current()->AsDefinition();
-        if (current != NULL &&
-            !current->IsPushArgument() &&
-            !current->AffectedBySideEffect()) {
+        Instruction* current = it.Current();
+        if (!current->IsPushArgument() && !current->AffectedBySideEffect()) {
           bool inputs_loop_invariant = true;
           for (int i = 0; i < current->InputCount(); ++i) {
             Definition* input_def = current->InputAt(i)->definition();
             if (!input_def->GetBlock()->Dominates(pre_header)) {
               inputs_loop_invariant = false;
               break;
             }
           }
           if (inputs_loop_invariant) {
             Hoist(&it, pre_header, current);
@@ skipping 199 matching lines @@
 
       GrowableArray<Definition*> definitions(max_expr_id);
       for (intptr_t j = 0; j < max_expr_id ; j++) {
         definitions.Add(NULL);
       }
 
       OptimizeLoads(graph->graph_entry(), &definitions, avail_in);
     }
   }
 
-  DirectChainedHashMap<Definition*> map;
+  DirectChainedHashMap<Instruction*> map;
   OptimizeRecursive(graph->graph_entry(), &map);
 }
 
 
 void DominatorBasedCSE::OptimizeRecursive(
     BlockEntryInstr* block,
-    DirectChainedHashMap<Definition*>* map) {
+    DirectChainedHashMap<Instruction*>* map) {
   for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
-    Definition* defn = it.Current()->AsDefinition();
-    if ((defn == NULL) || defn->AffectedBySideEffect()) continue;
-    Definition* result = map->Lookup(defn);
-    if (result == NULL) {
-      map->Insert(defn);
+    Instruction* current = it.Current();
+    if (current->AffectedBySideEffect()) continue;
+    Instruction* replacement = map->Lookup(current);
+    if (replacement == NULL) {
+      map->Insert(current);
       continue;
     }
     // Replace current with lookup result.
-    defn->ReplaceUsesWith(result);
+    if (current->IsDefinition()) {
+      ASSERT(replacement->IsDefinition());
+      current->AsDefinition()->ReplaceUsesWith(replacement->AsDefinition());
+      if (FLAG_trace_optimization) {
+        OS::Print("Replacing v%"Pd" with v%"Pd"\n",
+                  current->AsDefinition()->ssa_temp_index(),
+                  replacement->AsDefinition()->ssa_temp_index());
+      }
+    }

[Florian Schneider, 2012/09/19 13:24:49]

Maybe add the same debug output as in the Canonicalize-pass:

OS::Print("Removing %s\n", current->DebugName());

[Vyacheslav Egorov (Google), 2012/09/21 12:51:40]

Done.

     it.RemoveCurrentFromGraph();
-    if (FLAG_trace_optimization) {
-      OS::Print("Replacing v%"Pd" with v%"Pd"\n",
-                defn->ssa_temp_index(),
-                result->ssa_temp_index());
-    }
   }
 
   // Process children in the dominator tree recursively.
   intptr_t num_children = block->dominated_blocks().length();
   for (intptr_t i = 0; i < num_children; ++i) {
     BlockEntryInstr* child = block->dominated_blocks()[i];
     if (i  < num_children - 1) {
-      DirectChainedHashMap<Definition*> child_map(*map);  // Copy map.
+      DirectChainedHashMap<Instruction*> child_map(*map);  // Copy map.
       OptimizeRecursive(child, &child_map);
     } else {
       OptimizeRecursive(child, map);  // Reuse map for the last child.
     }
   }
 }
 
 
 }  // namespace dart