Try allocating loop phi into a register even if phi has only unconstrained uses but there are cheap…

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"
 
@@ skipping 135 matching lines @@
 
   // Try to find a free register for an unallocated live range.
   bool AllocateFreeRegister(LiveRange* unallocated);
 
   // Try to find a register that can be used by a given live range.
   // If all registers are occupied consider evicting interference for
   // a register that is going to be used as far from the start of
   // the unallocated live range as possible.
   void AllocateAnyRegister(LiveRange* unallocated);
 
+  // Returns true if the given range has only unconstrained uses in
+  // the given loop.
+  bool RangeHasOnlyUnconstrainedUsesInLoop(LiveRange* range, intptr_t loop_id);
+
+  // Returns true if there is a register blocked by a range that
+  // has only unconstrained uses in the loop. Such range is a good
+  // eviction candidate when allocator tries to allocate loop phi.
+  // Spilling loop phi will have a bigger negative impact on the
+  // performance because it introduces multiple operations with memory
+  // inside the loop body and on the back edge.
+  bool HasCheapEvictionCandidate(LiveRange* phi_range);
+  bool IsCheapToEvictRegisterInLoop(BlockInfo* loop, intptr_t reg);
+
   // Assign selected non-free register to an unallocated live range and
   // evict any interference that can be evicted by splitting and spilling
   // parts of interfering live ranges.  Place non-spilled parts into
   // the list of unallocated ranges.
   void AssignNonFreeRegister(LiveRange* unallocated, intptr_t reg);
   bool EvictIntersection(LiveRange* allocated, LiveRange* unallocated);
   void RemoveEvicted(intptr_t reg, intptr_t first_evicted);
 
   // Find first intersection between unallocated live range and
   // live ranges currently allocated to the given register.
@@ skipping 132 matching lines @@
   // 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; }
+
  private:
   BlockEntryInstr* entry_;
   BlockInfo* loop_;
   bool is_loop_header_;
 
+  BlockEntryInstr* last_block_;
+  intptr_t loop_id_;
+
   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 137 matching lines @@
     : vreg_(vreg),
       representation_(rep),
       assigned_location_(),
       spill_slot_(),
       uses_(NULL),
       first_use_interval_(NULL),
       last_use_interval_(NULL),
       first_safepoint_(NULL),
       last_safepoint_(NULL),
       next_sibling_(NULL),
+      has_only_any_uses_in_loops_(0),
+      is_loop_phi_(false),
       finger_() {
   }
 
   static LiveRange* MakeTemp(intptr_t pos, Location* location_slot);
 
   intptr_t vreg() const { return vreg_; }
   Location::Representation representation() const { return representation_; }
   LiveRange* next_sibling() const { return next_sibling_; }
   UsePosition* first_use() const { return uses_; }
   void set_first_use(UsePosition* use) { uses_ = use; }
@@ skipping 37 matching lines @@
     return (Start() <= pos) && (pos < End());
   }
 
   // True if the range contains the given position.
   bool Contains(intptr_t pos) const;
 
   Location spill_slot() const {
     return spill_slot_;
   }
 
+  bool HasOnlyUnconstrainedUsesInLoop(intptr_t loop_id) const {
+    if (loop_id < kBitsPerWord) {
+      const intptr_t mask = static_cast<intptr_t>(1) << loop_id;
+      return (has_only_any_uses_in_loops_ & mask) != 0;
+    }
+    return false;
+  }
+
+  void MarkHasOnlyUnconstrainedUsesInLoop(intptr_t loop_id) {
+    if (loop_id < kBitsPerWord) {
+      has_only_any_uses_in_loops_ |= static_cast<intptr_t>(1) << loop_id;
+    }
+  }
+
+  bool is_loop_phi() const { return is_loop_phi_; }
+  void mark_loop_phi() {
+    is_loop_phi_ = true;
+  }
+
  private:
   LiveRange(intptr_t vreg,
             Location::Representation rep,
             UsePosition* uses,
             UseInterval* first_use_interval,
             UseInterval* last_use_interval,
             SafepointPosition* first_safepoint,
             LiveRange* next_sibling)
     : vreg_(vreg),
       representation_(rep),
       assigned_location_(),
       uses_(uses),
       first_use_interval_(first_use_interval),
       last_use_interval_(last_use_interval),
       first_safepoint_(first_safepoint),
       last_safepoint_(NULL),
       next_sibling_(next_sibling),
+      has_only_any_uses_in_loops_(0),
+      is_loop_phi_(false),
       finger_() {
   }
 
   const intptr_t vreg_;
   Location::Representation representation_;
   Location assigned_location_;
   Location spill_slot_;
 
   UsePosition* uses_;
   UseInterval* first_use_interval_;
   UseInterval* last_use_interval_;
 
   SafepointPosition* first_safepoint_;
   SafepointPosition* last_safepoint_;
 
   LiveRange* next_sibling_;
 
+  intptr_t has_only_any_uses_in_loops_;
+  bool is_loop_phi_;
+
   AllocationFinger finger_;
 
   DISALLOW_COPY_AND_ASSIGN(LiveRange);
 };
 
 
 }  // namespace dart
 
 #endif  // VM_FLOW_GRAPH_ALLOCATOR_H_