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

runtime/vm/flow_graph_allocator.h

 // 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.
 
 #ifndef VM_FLOW_GRAPH_ALLOCATOR_H_
 #define VM_FLOW_GRAPH_ALLOCATOR_H_
 
-#include "vm/flow_graph.h"
 #include "vm/growable_array.h"
 #include "vm/intermediate_language.h"
 
 namespace dart {
 
 class AllocationFinger;
 class BlockInfo;
 class FlowGraph;
 class LiveRange;
 class UseInterval;
@@ skipping 10 matching lines @@
 
  private:
   void AddPhi(PhiInstr* phi);
   void Compute();
 
   const FlowGraph& flow_graph_;
   GrowableArray<PhiInstr*> phis_;
 };
 
 
-class SSALivenessAnalysis : public LivenessAnalysis {
- public:
-  explicit SSALivenessAnalysis(const FlowGraph& flow_graph)
-      : LivenessAnalysis(flow_graph.max_virtual_register_number(),
-                         flow_graph.postorder()),
-        graph_entry_(flow_graph.graph_entry()) { }
-
- private:
-  // Compute initial values for live-out, kill and live-in sets.
-  virtual void ComputeInitialSets();
-
-  GraphEntryInstr* graph_entry_;
-};
-
-
 class FlowGraphAllocator : public ValueObject {
  public:
   // Number of stack slots needed for a double spill slot.
   static const intptr_t kDoubleSpillSlotFactor = kDoubleSize / kWordSize;
 
   explicit FlowGraphAllocator(const FlowGraph& flow_graph);
 
   void AllocateRegisters();
 
+  // Build live-in and live-out sets for each block.
+  void AnalyzeLiveness();
+
   // Map a virtual register number to its live range.
   LiveRange* GetLiveRange(intptr_t vreg);
 
  private:
   void CollectRepresentations();
 
   // Eliminate unnecessary environments from the IL.
   void EliminateEnvironments();
 
+  // Compute initial values for live-out, kill and live-in sets.
+  void ComputeInitialSets();
+
+  // Update live-out set for the given block: live-out should contain
+  // all values that are live-in for block's successors.
+  // Returns true if live-out set was changed.
+  bool UpdateLiveOut(const BlockEntryInstr& instr);
+
+  // Update live-in set for the given block: live-in should contain
+  // all values that are live-out from the block and are not defined
+  // by this block.
+  // Returns true if live-in set was changed.
+  bool UpdateLiveIn(const BlockEntryInstr& instr);
+
+  // Perform fix-point iteration updating live-out and live-in sets
+  // for blocks until they stop changing.
+  void ComputeLiveInAndLiveOutSets();
+
+  // Print results of liveness analysis.
+  void DumpLiveness();
+
   // Visit blocks in the code generation order (reverse post order) and
   // linearly assign consequent lifetime positions to every instruction.
   // We assign position as follows:
   //
   //    2 * n     - even position corresponding to instruction's start;
   //
   //    2 * n + 1 - odd position corresponding to instruction's end;
   //
   // Having two positions per instruction allows us to capture non-trivial
   // shapes of use intervals: e.g. by placing a use at the start or the
@@ skipping 152 matching lines @@
 
   const GrowableArray<BlockEntryInstr*>& block_order_;
   const GrowableArray<BlockEntryInstr*>& postorder_;
 
   // Mapping between lifetime positions and instructions.
   GrowableArray<Instruction*> instructions_;
 
   // Mapping between lifetime positions and blocks containing them.
   GrowableArray<BlockInfo*> block_info_;
 
-  SSALivenessAnalysis liveness_;
+  // Live-out sets for each block.  They contain indices of SSA values
+  // that are live out from this block: that is values that were either
+  // defined in this block or live into it and that are used in some
+  // successor block.
+  GrowableArray<BitVector*> live_out_;
+
+  // Kill sets for each block.  They contain indices of SSA values that
+  // are defined by this block.
+  GrowableArray<BitVector*> kill_;
+
+  // Live-in sets for each block.  They contain indices of SSA values
+  // that are used by this block or its successors.
+  GrowableArray<BitVector*> live_in_;
 
   // Number of virtual registers.  Currently equal to the number of
   // SSA values.
   const intptr_t vreg_count_;
 
   // LiveRanges corresponding to SSA values.
   GrowableArray<LiveRange*> live_ranges_;
 
   GrowableArray<LiveRange*> unallocated_cpu_;
   GrowableArray<LiveRange*> unallocated_xmm_;
@@ skipping 381 matching lines @@
 
   AllocationFinger finger_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_ALLOCATOR_H_