[turbofan] Unit tests for live range conflicts.

src/compiler/greedy-allocator.h

 // Copyright 2015 the V8 project authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #ifndef V8_GREEDY_ALLOCATOR_H_
 #define V8_GREEDY_ALLOCATOR_H_
 
 #include "src/compiler/coalesced-live-ranges.h"
 #include "src/compiler/register-allocator.h"
 #include "src/zone-containers.h"
@@ skipping 44 matching lines @@
 // A variant of the LLVM Greedy Register Allocator. See
 // http://blog.llvm.org/2011/09/greedy-register-allocation-in-llvm-30.html
 class GreedyAllocator final : public RegisterAllocator {
  public:
   explicit GreedyAllocator(RegisterAllocationData* data, RegisterKind kind,
                            Zone* local_zone);
 
   void AllocateRegisters();
 
  private:
+  static const float kAllocatedRangeMultiplier;
+
+  static void UpdateWeightAtAllocation(LiveRange* range) {
+    DCHECK_NE(range->weight(), LiveRange::kInvalidWeight);
+    range->set_weight(range->weight() * kAllocatedRangeMultiplier);
+  }
+
+
+  static void UpdateWeightAtEviction(LiveRange* range) {
+    DCHECK_NE(range->weight(), LiveRange::kInvalidWeight);
+    range->set_weight(range->weight() / kAllocatedRangeMultiplier);
+  }
+
   AllocationScheduler& scheduler() { return scheduler_; }
   CoalescedLiveRanges* current_allocations(unsigned i) {
     return allocations_[i];
   }
+
+  CoalescedLiveRanges* current_allocations(unsigned i) const {
+    return allocations_[i];
+  }
+
   Zone* local_zone() const { return local_zone_; }
 
   // Insert fixed ranges.
   void PreallocateFixedRanges();
 
   // Schedule unassigned live ranges for allocation.
   // TODO(mtrofin): groups.
   void ScheduleAllocationCandidates();
 
+  void AllocateRegisterToRange(unsigned reg_id, LiveRange* range) {
+    UpdateWeightAtAllocation(range);
+    current_allocations(reg_id)->AllocateRange(range);
+  }
+  // Evict and reschedule conflicts of a given range, at a given register.
+  void EvictAndRescheduleConflicts(unsigned reg_id, const LiveRange* range);
+
   // Find the optimal split for ranges defined by a memory operand, e.g.
   // constants or function parameters passed on the stack.
   void SplitAndSpillRangesDefinedByMemoryOperand();
 
   void TryAllocateCandidate(const AllocationCandidate& candidate);
   void TryAllocateLiveRange(LiveRange* range);
 
   bool CanProcessRange(LiveRange* range) const {
     return range != nullptr && !range->IsEmpty() && range->kind() == mode();
   }
 
   // Calculate the weight of a candidate for allocation.
   void EnsureValidRangeWeight(LiveRange* range);
 
   // Calculate the new weight of a range that is about to be allocated.
   float GetAllocatedRangeWeight(float candidate_weight);
 
+  // Returns kInvalidWeight if there are no conflicts, or the largest weight of
+  // a range conflicting with the given range, at the given register.
+  float GetMaximumConflictingWeight(unsigned reg_id,
+                                    const LiveRange* range) const;
+
   // This is the extension point for splitting heuristics.
   void SplitOrSpillBlockedRange(LiveRange* range);
 
   // Necessary heuristic: spill when all else failed.
   void SpillRangeAsLastResort(LiveRange* range);
 
   void AssignRangeToRegister(int reg_id, LiveRange* range);
 
   Zone* local_zone_;
   ZoneVector<CoalescedLiveRanges*> allocations_;
   AllocationScheduler scheduler_;
   DISALLOW_COPY_AND_ASSIGN(GreedyAllocator);
 };
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8
 #endif  // V8_GREEDY_ALLOCATOR_H_