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

vm/flow_graph_allocator.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_allocator.h"
 
 #include "vm/bit_vector.h"
 #include "vm/intermediate_language.h"
 #include "vm/il_printer.h"
 #include "vm/flow_graph_builder.h"
@@ skipping 50 matching lines @@
 
 
 void FlowGraphAllocator::ComputeInitialSets() {
   const intptr_t block_count = postorder_.length();
   for (intptr_t i = 0; i < block_count; i++) {
     BlockEntryInstr* block = postorder_[i];
 
     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);
         }
       }
 
       // Add uses from the deoptimization environment.
       if (current->env() != NULL) {
         const GrowableArray<Value*>& values = current->env()->values();
         for (intptr_t j = 0; j < values.length(); j++) {
           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);
+            }
+          }
+        }
       }
     }
   }
 
   // Update initial live_in sets to match live_out sets. Has to be
   // done in a separate path because of backwards branches.
   for (intptr_t i = 0; i < block_count; i++) {
     UpdateLiveIn(*postorder_[i]);
   }
 }
@@ skipping 821 matching lines @@
 
   if (FLAG_trace_ssa_allocator) {
     OS::Print("-- ir after allocation -------------------------\n");
     FlowGraphPrinter printer(Function::Handle(), block_order_, true);
     printer.PrintBlocks();
   }
 }
 
 
 }  // namespace dart