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()),
-    live_out_(block_order_.length()),
-    kill_(block_order_.length()),
-    live_in_(block_order_.length()),
+    liveness_(flow_graph),
     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 FlowGraphAllocator::ComputeInitialSets() {
+void SSALivenessAnalysis::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.
-  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);
+  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 211 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(live_out_[i]); !it.Done(); it.Advance()) {
+    for (BitVector::Iterator it(liveness_.GetLiveOutSetAt(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);
       loop_header->set_backedge_interference(
@@ skipping 11 matching lines @@
       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(live_in_[i]); !it.Done(); it.Advance()) {
+      for (BitVector::Iterator it(liveness_.GetLiveInSetAt(i));
+           !it.Done();
+           it.Advance()) {
         LiveRange* range = GetLiveRange(it.Current());
         if (HasOnlyUnconstrainedUsesInLoop(range, block_info)) {
           range->MarkHasOnlyUnconstrainedUsesInLoop(block_info->loop_id());
         }
       }
     }
 
     ConnectIncomingPhiMoves(block);
   }
 
@@ skipping 1798 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 = live_in_[block->postorder_number()];
+    BitVector* live = liveness_.GetLiveInSet(block);
     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();
 
-  AnalyzeLiveness();
+  liveness_.Analyze();
 
   NumberInstructions();
 
   DiscoverLoops();
 
   BuildLiveRanges();
 
   if (FLAG_print_ssa_liveness) {
-    DumpLiveness();
+    liveness_.Dump();
   }
 
   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