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

runtime/vm/flow_graph_allocator.h

 // 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.
 
 #ifndef VM_FLOW_GRAPH_ALLOCATOR_H_
 #define VM_FLOW_GRAPH_ALLOCATOR_H_
 
 #include "vm/growable_array.h"
 #include "vm/intermediate_language.h"
 
 namespace dart {
 
 class AllocationFinger;
 class BlockInfo;
 class FlowGraph;
 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.
   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.
@@ skipping 57 matching lines @@
   // Discover structural (reducible) loops nesting structure.
   // It will be used later in SplitBetween heuristic that selects an
   // optimal splitting position.
   void DiscoverLoops();
 
   LiveRange* MakeLiveRangeForTemporary();
 
   // 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,
                              intptr_t from,
                              intptr_t to,
                              bool* blocked_registers,
                              LiveRange** blocking_ranges);
 
   intptr_t NumberOfRegisters() const { return number_of_registers_; }
 
@@ skipping 97 matching lines @@
   MoveOperands* AddMoveAt(intptr_t pos, Location to, Location from);
 
   Location MakeRegisterLocation(intptr_t reg, Location::Representation rep) {
     return Location::MachineRegisterLocation(register_kind_, reg, rep);
   }
 
   void PrintLiveRanges();
 
   const FlowGraph& flow_graph_;
 
+  ReachingDefs reaching_defs_;
+
   // Set of SSA values that have unboxed mint representation. Indexed
   // by SSA temp index.
   BitVector* mint_values_;
 
   const GrowableArray<BlockEntryInstr*>& block_order_;
   const GrowableArray<BlockEntryInstr*>& postorder_;
 
   // Mapping between lifetime positions and instructions.
   GrowableArray<Instruction*> instructions_;
 
@@ skipping 65 matching lines @@
 
   DISALLOW_COPY_AND_ASSIGN(FlowGraphAllocator);
 };
 
 
 // Additional information about a block that is not contained in a
 // block entry.
 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_; }
 
   // 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_; }
 
   void mark_loop_header() { is_loop_header_ = true; }
   void set_loop(BlockInfo* loop) {
     ASSERT(loop_ == NULL);
     ASSERT((loop == NULL) || loop->is_loop_header());
     loop_ = loop;
   }
 
   BlockEntryInstr* last_block() const { return last_block_; }
   void set_last_block(BlockEntryInstr* last_block) {
     last_block_ = last_block;
   }
 
   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_;
   bool is_loop_header_;
 
   BlockEntryInstr* last_block_;
   intptr_t loop_id_;
 
+  BitVector* backedge_interference_;
+
   DISALLOW_COPY_AND_ASSIGN(BlockInfo);
 };
 
 
 // UsePosition represents a single use of an SSA value by some instruction.
 // It points to a location slot which either tells register allocator
 // where instruction expects the value (if slot contains a fixed location) or
 // asks register allocator to allocate storage (register or spill slot) for
 // this use with certain properties (if slot contains an unallocated location).
 class UsePosition : public ZoneAllocated {
@@ skipping 263 matching lines @@
 
   AllocationFinger finger_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_ALLOCATOR_H_