Heuristically predict interference on the back edge and use it to minimize number of register reshu…

runtime/vm/flow_graph_allocator.h

Index: runtime/vm/flow_graph_allocator.h
diff --git a/runtime/vm/flow_graph_allocator.h b/runtime/vm/flow_graph_allocator.h
index b98fbb34b0ecc6042dcd27454fae0fbc3780d5f2..d88e6e15325f45ba4db9fea4ab914ef2a43bef1a 100644
--- a/runtime/vm/flow_graph_allocator.h
+++ b/runtime/vm/flow_graph_allocator.h
@@ -17,6 +17,24 @@ class LiveRange;
 class UseInterval;
 class UsePosition;
 
+
+class ReachingDefs : public ValueObject {
+ public:
+  explicit ReachingDefs(const FlowGraph& flow_graph)
+      : flow_graph_(flow_graph),
+        phis_(10) { }
+
+  BitVector* Get(PhiInstr* phi);
+
+ private:
+  void AddPhi(PhiInstr* phi);
+  void Compute();
+
+  const FlowGraph& flow_graph_;
+  GrowableArray<PhiInstr*> phis_;
+};
+
+
 class FlowGraphAllocator : public ValueObject {
  public:
   // Number of stack slots needed for a double spill slot.
@@ -94,9 +112,12 @@ class FlowGraphAllocator : public ValueObject {
   // Visit instructions in the postorder and build live ranges for
   // all SSA values.
   void BuildLiveRanges();
-  Instruction* ConnectOutgoingPhiMoves(BlockEntryInstr* block);
+  Instruction* ConnectOutgoingPhiMoves(BlockEntryInstr* block,
+                                       BitVector* interference_set);
   void ProcessEnvironmentUses(BlockEntryInstr* block, Instruction* current);
-  void ProcessOneInstruction(BlockEntryInstr* block, Instruction* instr);
+  void ProcessOneInstruction(BlockEntryInstr* block,
+                             Instruction* instr,
+                             BitVector* interference_set);
   void ConnectIncomingPhiMoves(BlockEntryInstr* block);
   void BlockLocation(Location loc, intptr_t from, intptr_t to);
   void BlockRegisterLocation(Location loc,
@@ -214,6 +235,8 @@ class FlowGraphAllocator : public ValueObject {
 
   const FlowGraph& flow_graph_;
 
+  ReachingDefs reaching_defs_;
+
   // Set of SSA values that have unboxed mint representation. Indexed
   // by SSA temp index.
   BitVector* mint_values_;
@@ -299,7 +322,10 @@ class FlowGraphAllocator : public ValueObject {
 class BlockInfo : public ZoneAllocated {
  public:
   explicit BlockInfo(BlockEntryInstr* entry)
-    : entry_(entry), loop_(NULL), is_loop_header_(false) {
+    : entry_(entry),
+      loop_(NULL),
+      is_loop_header_(false),
+      backedge_interference_(NULL) {
   }
 
   BlockEntryInstr* entry() const { return entry_; }
@@ -307,6 +333,17 @@ class BlockInfo : public ZoneAllocated {
   // Returns true is this node is a header of a structural loop.
   bool is_loop_header() const { return is_loop_header_; }
 
+  // Returns header of the innermost loop containing this block.
+  BlockInfo* loop_header() {
+    if (is_loop_header()) {
+      return this;
+    } else if (loop() != NULL) {
+      return loop();
+    } else {
+      return NULL;
+    }
+  }
+
   // Innermost reducible loop containing this node. Loop headers point to
   // outer loop not to themselves.
   BlockInfo* loop() const { return loop_; }
@@ -326,6 +363,14 @@ class BlockInfo : public ZoneAllocated {
   intptr_t loop_id() const { return loop_id_; }
   void set_loop_id(intptr_t loop_id) { loop_id_ = loop_id; }
 
+  BitVector* backedge_interference() const {
+    return backedge_interference_;
+  }
+
+  void set_backedge_interference(BitVector* backedge_interference) {
+    backedge_interference_ = backedge_interference;
+  }
+
  private:
   BlockEntryInstr* entry_;
   BlockInfo* loop_;
@@ -334,6 +379,8 @@ class BlockInfo : public ZoneAllocated {
   BlockEntryInstr* last_block_;
   intptr_t loop_id_;
 
+  BitVector* backedge_interference_;
+
   DISALLOW_COPY_AND_ASSIGN(BlockInfo);
 };