Convert some compiler passes to preserve valid def-use chains.

runtime/vm/flow_graph.cc

Index: runtime/vm/flow_graph.cc
diff --git a/runtime/vm/flow_graph.cc b/runtime/vm/flow_graph.cc
index ea66a5a2480b1a1558aba7fd9b78d1199acd97aa..deed8c0007feeb5dcc0f83ca3f5884f13318a7c1 100644
--- a/runtime/vm/flow_graph.cc
+++ b/runtime/vm/flow_graph.cc
@@ -60,6 +60,34 @@ void FlowGraph::AddToInitialDefinitions(Definition* defn) {
 }
 
 
+void FlowGraph::InsertBefore(Instruction* next,
+                             Instruction* instr,
+                             Environment* env,
+                             Definition::UseKind use_kind) {
+  InsertAfter(next->previous(), instr, env, use_kind);
+}
+
+
+void FlowGraph::InsertAfter(Instruction* prev,
+                            Instruction* instr,
+                            Environment* env,
+                            Definition::UseKind use_kind) {
+  for (intptr_t i = instr->InputCount() - 1; i >= 0; --i) {
+    Value* input = instr->InputAt(i);
+    input->definition()->AddInputUse(input);
+    input->set_instruction(instr);
+    input->set_use_index(i);
+  }
+  ASSERT(instr->env() == NULL);
+  if (env != NULL) env->DeepCopyTo(instr);
+  if (use_kind == Definition::kValue) {
+    ASSERT(instr->IsDefinition());
+    instr->AsDefinition()->set_ssa_temp_index(alloc_ssa_temp_index());
+  }
+  instr->InsertAfter(prev);
+}
+
+
 void FlowGraph::DiscoverBlocks() {
   // Initialize state.
   preorder_.Clear();
@@ -149,6 +177,9 @@ static void ValidateUseListsInInstruction(Instruction* instr) {
   ASSERT(!instr->IsJoinEntry());
   for (intptr_t i = 0; i < instr->InputCount(); ++i) {
     Value* use = instr->InputAt(i);
+    ASSERT(use->definition() != NULL);
+    ASSERT(use->definition() != instr);
+    ASSERT(use->instruction() == instr);
     ASSERT(use->use_index() == i);
     ASSERT(!FLAG_verify_compiler ||
            (1 == MembershipCount(use, use->definition()->input_use_list())));
@@ -157,6 +188,9 @@ static void ValidateUseListsInInstruction(Instruction* instr) {
     intptr_t use_index = 0;
     for (Environment::DeepIterator it(instr->env()); !it.Done(); it.Advance()) {
       Value* use = it.CurrentValue();
+      ASSERT(use->definition() != NULL);
+      ASSERT(use->definition() != instr);
+      ASSERT(use->instruction() == instr);
       ASSERT(use->use_index() == use_index++);
       ASSERT(!FLAG_verify_compiler ||
              (1 == MembershipCount(use, use->definition()->env_use_list())));
@@ -170,9 +204,13 @@ static void ValidateUseListsInInstruction(Instruction* instr) {
       ASSERT(prev == curr->previous_use());
       ASSERT(defn == curr->definition());
       Instruction* instr = curr->instruction();
-      // The instruction should not be removed from the graph (phis are not
-      // removed until register allocation.)
-      ASSERT(instr->IsPhi() || (instr->previous() != NULL));
+      // The instruction should not be removed from the graph.  Removed
+      // instructions have a NULL previous link.  Phis are not removed until
+      // register allocation.  Comparisons used only in a branch will have a
+      // NULL previous link though they are still in the graph.
+      ASSERT(instr->IsPhi() ||
+             (instr->IsDefinition() && instr->AsDefinition()->IsComparison()) ||
+             (instr->previous() != NULL));

[Vyacheslav Egorov (Google), 2013/02/08 16:44:49]

Consider changing WasEliminated() and using it:

bool WasEliminated() const {
  ASSERT(!IsGraphEntry());
  return !IsPhi() && instr->previous();
}

[Kevin Millikin (Google), 2013/02/19 10:49:30]

I think it's better to (a) remove phis eagerly and (b) not have comparison as an
instruction (it can only be part of a BranchInstr or a "BoolifyInstr").

As it is, WasEliminated above just gives false negatives for phis and false
positives for comparisons.  That seems misleading to expose as a general
predicate blessed by an API, so I'd rather just keep the verification low level.

       ASSERT(curr == instr->InputAt(curr->use_index()));
       prev = curr;
       curr = curr->next_use();
@@ -185,9 +223,9 @@ static void ValidateUseListsInInstruction(Instruction* instr) {
       ASSERT(defn == curr->definition());
       Instruction* instr = curr->instruction();
       ASSERT(curr == instr->env()->ValueAtUseIndex(curr->use_index()));
-      // The instruction should not be removed from the graph (phis are not
-      // removed until register allocation.)
-      ASSERT(instr->IsPhi() || (instr->previous() != NULL));
+      ASSERT(instr->IsPhi() ||
+             (instr->IsDefinition() && instr->AsDefinition()->IsComparison()) ||
+             (instr->previous() != NULL));

[Vyacheslav Egorov (Google), 2013/02/08 16:44:49]

ditto

       prev = curr;
       curr = curr->next_use();
     }