[turbofan] Greedy: faster compile time.

src/compiler/greedy-allocator.cc

 // 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.
 
 #include "src/compiler/greedy-allocator.h"
 #include "src/compiler/register-allocator.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
@@ skipping 320 matching lines @@
 void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
   // TODO(mtrofin): once we introduce groups, we'll want to first try and
   // allocate at the preferred register.
   TRACE("Attempting to allocate live range %d:%d.\n", range->TopLevel()->vreg(),
         range->relative_id());
   int free_reg = -1;
   int evictable_reg = -1;
   int hinted_reg = -1;
 
   EnsureValidRangeWeight(range);
-  DCHECK(range->weight() != LiveRange::kInvalidWeight);
+  float competing_weight = range->weight();
+  DCHECK(competing_weight != LiveRange::kInvalidWeight);
 
   // Can we allocate at the hinted register?
   if (range->FirstHintPosition(&hinted_reg) != nullptr) {
     DCHECK(hinted_reg >= 0);
-    float max_conflict_weight = GetMaximumConflictingWeight(hinted_reg, range);
+    float max_conflict_weight =
+        GetMaximumConflictingWeight(hinted_reg, range, competing_weight);
     if (max_conflict_weight == LiveRange::kInvalidWeight) {
       free_reg = hinted_reg;
     } else if (max_conflict_weight < range->weight()) {
       evictable_reg = hinted_reg;
     }
   }
 
   if (free_reg < 0 && evictable_reg < 0) {
     // There was no hinted reg, or we cannot allocate there.
     float smallest_weight = LiveRange::kMaxWeight;
 
     // Seek either the first free register, or, from the set of registers
     // where the maximum conflict is lower than the candidate's weight, the one
     // with the smallest such weight.
     for (int i = 0; i < num_registers(); i++) {
       // Skip unnecessarily re-visiting the hinted register, if any.
       if (i == hinted_reg) continue;
-      float max_conflict_weight = GetMaximumConflictingWeight(i, range);
+      float max_conflict_weight =
+          GetMaximumConflictingWeight(i, range, competing_weight);
       if (max_conflict_weight == LiveRange::kInvalidWeight) {
         free_reg = i;
         break;
       }
       if (max_conflict_weight < range->weight() &&
           max_conflict_weight < smallest_weight) {
         smallest_weight = max_conflict_weight;
         evictable_reg = i;
       }
     }
@@ skipping 100 matching lines @@
     }
   }
   allocations_.clear();
 
   TRACE("End allocating function %s with the Greedy Allocator\n",
         data()->debug_name());
 }
 
 
 float GreedyAllocator::GetMaximumConflictingWeight(
-    unsigned reg_id, const LiveRange* range) const {
+    unsigned reg_id, const LiveRange* range, float competing_weight) const {
   float ret = LiveRange::kInvalidWeight;
 
   auto conflicts = current_allocations(reg_id)->GetConflicts(range);
   for (LiveRange* conflict = conflicts.Current(); conflict != nullptr;
        conflict = conflicts.GetNext()) {
     DCHECK_NE(conflict->weight(), LiveRange::kInvalidWeight);
+    if (competing_weight <= conflict->weight()) return LiveRange::kMaxWeight;
     ret = Max(ret, conflict->weight());
-    if (ret == LiveRange::kMaxWeight) return ret;
+    DCHECK(ret < LiveRange::kMaxWeight);
   }
 
   return ret;
 }
 
 
 float GreedyAllocator::GetMaximumConflictingWeight(unsigned reg_id,
                                                    const LiveRangeGroup* group,
                                                    float group_weight) const {
   float ret = LiveRange::kInvalidWeight;
 
   for (LiveRange* member : group->ranges()) {
-    float member_conflict_weight = GetMaximumConflictingWeight(reg_id, member);
+    float member_conflict_weight =
+        GetMaximumConflictingWeight(reg_id, member, group_weight);
     if (member_conflict_weight == LiveRange::kMaxWeight) {
       return LiveRange::kMaxWeight;
     }
     if (member_conflict_weight > group_weight) return LiveRange::kMaxWeight;
     ret = Max(member_conflict_weight, ret);
   }
 
   return ret;
 }
 
@@ skipping 142 matching lines @@
     scheduler().Schedule(range);
     return;
   }
   SpillRangeAsLastResort(range);
 }
 
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8