Add a backward instruction iterator and use it in the liveness analysis.

vm/flow_graph_allocator.cc

Index: vm/flow_graph_allocator.cc
===================================================================
--- vm/flow_graph_allocator.cc	(revision 9842)
+++ vm/flow_graph_allocator.cc	(working copy)
@@ -68,34 +68,23 @@
     BitVector* kill = kill_[i];
     BitVector* live_in = live_in_[i];
 
-    if (block->IsJoinEntry()) {
-      JoinEntryInstr* join = block->AsJoinEntry();
-      if (join->phis() != NULL) {
-        for (intptr_t j = 0; j < join->phis()->length(); j++) {
-          PhiInstr* phi = (*join->phis())[j];
-          if (phi == NULL) continue;
-          kill->Add(phi->ssa_temp_index());
+    // Iterate backwards.

[srdjan, 2012/07/24 15:49:30]

Add:, starting with the last instruction of block.

[Florian Schneider, 2012/07/25 08:31:29]

Done.

+    for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) {
+      Instruction* current = it.Current();
 
-          for (intptr_t k = 0; k < phi->InputCount(); k++) {
-            Value* val = phi->InputAt(k);
-            if (val->IsUse()) {
-              BlockEntryInstr* pred = block->PredecessorAt(k);
-              const intptr_t use = val->AsUse()->definition()->ssa_temp_index();
-              live_out_[pred->postorder_number()]->Add(use);
-            }
-          }
-        }
+      // Handle definitions.
+      Definition* current_def = current->AsDefinition();
+      if ((current_def != NULL) && (current_def->ssa_temp_index() >= 0)) {

[srdjan, 2012/07/24 17:41:44]

current_def->HasSSATemp()

[Florian Schneider, 2012/07/25 08:31:29]

Done.

+        kill->Add(current_def->ssa_temp_index());
+        live_in->Remove(current_def->ssa_temp_index());
       }
-    }
 
-    // TODO(vegorov): iterate backwards.
-    for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
-      Instruction* current = it.Current();
+      // Handle uses.
       for (intptr_t j = 0; j < current->InputCount(); j++) {
         Value* input = current->InputAt(j);
         if (input->IsUse()) {
           const intptr_t use = input->AsUse()->definition()->ssa_temp_index();
-          if (!kill->Contains(use)) live_in->Add(use);
+          live_in->Add(use);
         }
       }
 
@@ -106,14 +95,31 @@
           Value* val = values[j];
           if (val->IsUse()) {
             const intptr_t use = val->AsUse()->definition()->ssa_temp_index();
-            if (!kill->Contains(use)) live_in->Add(use);
+            live_in->Add(use);
           }
         }
       }
+    }
 
-      Definition* current_def = current->AsDefinition();
-      if ((current_def != NULL) && (current_def->ssa_temp_index() >= 0)) {
-        kill->Add(current_def->ssa_temp_index());
+    // Handle phis.
+    if (block->IsJoinEntry()) {
+      JoinEntryInstr* join = block->AsJoinEntry();
+      if (join->phis() != NULL) {
+        for (intptr_t j = 0; j < join->phis()->length(); j++) {
+          PhiInstr* phi = (*join->phis())[j];
+          if (phi == NULL) continue;
+          kill->Add(phi->ssa_temp_index());
+          live_in->Remove(phi->ssa_temp_index());
+
+          for (intptr_t k = 0; k < phi->InputCount(); k++) {
+            Value* val = phi->InputAt(k);
+            if (val->IsUse()) {
+              BlockEntryInstr* pred = block->PredecessorAt(k);
+              const intptr_t use = val->AsUse()->definition()->ssa_temp_index();
+              live_out_[pred->postorder_number()]->Add(use);
+            }
+          }
+        }
       }
     }
   }