Revert "Compute local variable liveness before translation to SSA."

runtime/vm/flow_graph_allocator.cc

 // Copyright (c) 2013, 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.h"
@@ skipping 48 matching lines @@
   return (pos | 1);
 }
 
 
 FlowGraphAllocator::FlowGraphAllocator(const FlowGraph& flow_graph)
   : flow_graph_(flow_graph),
     reaching_defs_(flow_graph),
     value_representations_(flow_graph.max_virtual_register_number()),
     block_order_(flow_graph.reverse_postorder()),
     postorder_(flow_graph.postorder()),
-    liveness_(flow_graph),
+    live_out_(block_order_.length()),
+    kill_(block_order_.length()),
+    live_in_(block_order_.length()),
     vreg_count_(flow_graph.max_virtual_register_number()),
     live_ranges_(flow_graph.max_virtual_register_number()),
     cpu_regs_(),
     fpu_regs_(),
     blocked_cpu_registers_(),
     blocked_fpu_registers_(),
     cpu_spill_slot_count_(0) {
   for (intptr_t i = 0; i < vreg_count_; i++) live_ranges_.Add(NULL);
   for (intptr_t i = 0; i < vreg_count_; i++) {
     value_representations_.Add(kNoRepresentation);
@@ skipping 27 matching lines @@
   for (intptr_t i = 0; i < block_order_.length(); ++i) {
     BlockEntryInstr* block = block_order_[i];
     for (ForwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
       if (!current->CanDeoptimize()) current->RemoveEnvironment();
     }
   }
 }
 
 
-void SSALivenessAnalysis::ComputeInitialSets() {
+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];
 
     // Iterate backwards starting at the last instruction.
     for (BackwardInstructionIterator it(block); !it.Done(); it.Advance()) {
       Instruction* current = it.Current();
@@ skipping 52 matching lines @@
           const intptr_t use = val->definition()->ssa_temp_index();
           if (!kill_[pred->postorder_number()]->Contains(use)) {
             live_in_[pred->postorder_number()]->Add(use);
           }
         }
       }
     }
   }
 
   // Process initial definitions, ie, constants and incoming parameters.
-  for (intptr_t i = 0; i < graph_entry_->initial_definitions()->length(); i++) {
-    intptr_t vreg = (*graph_entry_->initial_definitions())[i]->ssa_temp_index();
-    kill_[graph_entry_->postorder_number()]->Add(vreg);
-    live_in_[graph_entry_->postorder_number()]->Remove(vreg);
+  GraphEntryInstr* graph_entry = flow_graph_.graph_entry();
+  for (intptr_t i = 0; i < graph_entry->initial_definitions()->length(); i++) {
+    intptr_t vreg = (*graph_entry->initial_definitions())[i]->ssa_temp_index();
+    kill_[graph_entry->postorder_number()]->Add(vreg);
+    live_in_[graph_entry->postorder_number()]->Remove(vreg);
   }
 
   // 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]);
   }
 }
 
 
+bool FlowGraphAllocator::UpdateLiveOut(const BlockEntryInstr& instr) {
+  BitVector* live_out = live_out_[instr.postorder_number()];
+  bool changed = false;
+  Instruction* last = instr.last_instruction();
+  ASSERT(last != NULL);
+  for (intptr_t i = 0; i < last->SuccessorCount(); i++) {
+    BlockEntryInstr* succ = last->SuccessorAt(i);
+    ASSERT(succ != NULL);
+    if (live_out->AddAll(live_in_[succ->postorder_number()])) {
+      changed = true;
+    }
+  }
+  return changed;
+}
+
+
+bool FlowGraphAllocator::UpdateLiveIn(const BlockEntryInstr& instr) {
+  BitVector* live_out = live_out_[instr.postorder_number()];
+  BitVector* kill = kill_[instr.postorder_number()];
+  BitVector* live_in = live_in_[instr.postorder_number()];
+  return live_in->KillAndAdd(kill, live_out);
+}
+
+
+void FlowGraphAllocator::ComputeLiveInAndLiveOutSets() {
+  const intptr_t block_count = postorder_.length();
+  bool changed;
+  do {
+    changed = false;
+
+    for (intptr_t i = 0; i < block_count; i++) {
+      const BlockEntryInstr& block = *postorder_[i];
+
+      // Live-in set depends only on kill set which does not
+      // change in this loop and live-out set.  If live-out
+      // set does not change there is no need to recompute
+      // live-in set.
+      if (UpdateLiveOut(block) && UpdateLiveIn(block)) {
+        changed = true;
+      }
+    }
+  } while (changed);
+}
+
+
+void FlowGraphAllocator::AnalyzeLiveness() {
+  const intptr_t block_count = postorder_.length();
+  for (intptr_t i = 0; i < block_count; i++) {
+    live_out_.Add(new BitVector(vreg_count_));
+    kill_.Add(new BitVector(vreg_count_));
+    live_in_.Add(new BitVector(vreg_count_));
+  }
+
+  ComputeInitialSets();
+  ComputeLiveInAndLiveOutSets();
+}
+
+
+static void PrintBitVector(const char* tag, BitVector* v) {
+  OS::Print("%s:", tag);
+  for (BitVector::Iterator it(v); !it.Done(); it.Advance()) {
+    OS::Print(" %"Pd"", it.Current());
+  }
+  OS::Print("\n");
+}
+
+
+void FlowGraphAllocator::DumpLiveness() {
+  const intptr_t block_count = postorder_.length();
+  for (intptr_t i = 0; i < block_count; i++) {
+    BlockEntryInstr* block = postorder_[i];
+    OS::Print("block @%"Pd" -> ", block->block_id());
+
+    Instruction* last = block->last_instruction();
+    for (intptr_t j = 0; j < last->SuccessorCount(); j++) {
+      BlockEntryInstr* succ = last->SuccessorAt(j);
+      OS::Print(" @%"Pd"", succ->block_id());
+    }
+    OS::Print("\n");
+
+    PrintBitVector("  live out", live_out_[i]);
+    PrintBitVector("  kill", kill_[i]);
+    PrintBitVector("  live in", live_in_[i]);
+  }
+}
+
+
 void LiveRange::AddUse(intptr_t pos, Location* location_slot) {
   ASSERT(location_slot != NULL);
   ASSERT((first_use_interval_->start_ <= pos) &&
          (pos <= first_use_interval_->end_));
   if ((uses_ != NULL) &&
       (uses_->pos() == pos) &&
       (uses_->location_slot() == location_slot)) {
     return;
   }
   uses_ = new UsePosition(pos, uses_, location_slot);
@@ skipping 224 matching lines @@
   ASSERT(postorder_.Last()->IsGraphEntry());
   BitVector* current_interference_set = NULL;
   for (intptr_t i = 0; i < (block_count - 1); i++) {
     BlockEntryInstr* block = postorder_[i];
 
     BlockInfo* block_info = BlockInfoAt(block->start_pos());
 
     // For every SSA value that is live out of this block, create an interval
     // that covers the whole block.  It will be shortened if we encounter a
     // definition of this value in this block.
-    for (BitVector::Iterator it(liveness_.GetLiveOutSetAt(i));
-         !it.Done();
-         it.Advance()) {
+    for (BitVector::Iterator it(live_out_[i]); !it.Done(); it.Advance()) {
       LiveRange* range = GetLiveRange(it.Current());
       range->AddUseInterval(block->start_pos(), block->end_pos());
     }
 
     BlockInfo* loop_header = block_info->loop_header();
     if ((loop_header != NULL) && (loop_header->last_block() == block)) {
       current_interference_set =
           new BitVector(flow_graph_.max_virtual_register_number());
       ASSERT(loop_header->backedge_interference() == NULL);
       // All values flowing into the loop header are live at the back-edge and
       // can interfere with phi moves.
       current_interference_set->AddAll(
-          liveness_.GetLiveInSet(loop_header->entry()));
+          live_in_[loop_header->entry()->postorder_number()]);
       loop_header->set_backedge_interference(
           current_interference_set);
     }
 
     // Connect outgoing phi-moves that were created in NumberInstructions
     // and find last instruction that contributes to liveness.
     Instruction* current = ConnectOutgoingPhiMoves(block,
                                                    current_interference_set);
 
     // Now process all instructions in reverse order.
     while (current != block) {
       // Skip parallel moves that we insert while processing instructions.
       if (!current->IsParallelMove()) {
         ProcessOneInstruction(block, current, current_interference_set);
       }
       current = current->previous();
     }
 
 
     // Check if any values live into the loop can be spilled for free.
     if (block_info->is_loop_header()) {
       current_interference_set = NULL;
-      for (BitVector::Iterator it(liveness_.GetLiveInSetAt(i));
-           !it.Done();
-           it.Advance()) {
+      for (BitVector::Iterator it(live_in_[i]); !it.Done(); it.Advance()) {
         LiveRange* range = GetLiveRange(it.Current());
         if (HasOnlyUnconstrainedUsesInLoop(range, block_info)) {
           range->MarkHasOnlyUnconstrainedUsesInLoop(block_info->loop_id());
         }
       }
     }
 
     ConnectIncomingPhiMoves(block);
   }
 
@@ skipping 1815 matching lines @@
                   sibling->assigned_location(),
                   range->assigned_location());
       }
       range = sibling;
     }
   }
 
   // Resolve non-linear control flow across branches.
   for (intptr_t i = 1; i < block_order_.length(); i++) {
     BlockEntryInstr* block = block_order_[i];
-    BitVector* live = liveness_.GetLiveInSet(block);
+    BitVector* live = live_in_[block->postorder_number()];
     for (BitVector::Iterator it(live); !it.Done(); it.Advance()) {
       LiveRange* range = GetLiveRange(it.Current());
       for (intptr_t j = 0; j < block->PredecessorCount(); j++) {
         ConnectSplitSiblings(range, block->PredecessorAt(j), block);
       }
     }
   }
 
   // Eagerly spill values.
   // TODO(vegorov): if value is spilled on the cold path (e.g. by the call)
@@ skipping 46 matching lines @@
     }
   }
 }
 
 
 void FlowGraphAllocator::AllocateRegisters() {
   CollectRepresentations();
 
   EliminateEnvironments();
 
-  liveness_.Analyze();
+  AnalyzeLiveness();
 
   NumberInstructions();
 
   DiscoverLoops();
 
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
-    liveness_.Dump();
+    DumpLiveness();
   }
 
   if (FLAG_print_ssa_liveranges) {
     const Function& function = flow_graph_.parsed_function().function();
 
     OS::Print("-- [before ssa allocator] ranges [%s] ---------\n",
               function.ToFullyQualifiedCString());
     PrintLiveRanges();
     OS::Print("----------------------------------------------\n");
 
@@ skipping 40 matching lines @@
     OS::Print("-- [after ssa allocator] ir [%s] -------------\n",
               function.ToFullyQualifiedCString());
     FlowGraphPrinter printer(flow_graph_, true);
     printer.PrintBlocks();
     OS::Print("----------------------------------------------\n");
   }
 }
 
 
 }  // namespace dart