From 93f1f198a629420d416d9e4805b921a807b5b7d6 Mon Sep 17 00:00:00 2001
From: hablich <hablich@chromium.org>
Date: Wed, 2 Sep 2015 01:35:02 -0700
Subject: [PATCH] Revert of [turbofan] Greedy: using hints (patchset #2
 id:60001 of https://codereview.chromium.org/1329493004/ )

Reason for revert:
http://build.chromium.org/p/client.v8/builders/V8%20Linux%20-%20debug%20-%20greedy%20allocator/builds/1338

Original issue's description:
> [turbofan] Greedy: using hints
>
> This is a rudimentary introduction of hints. Primarily this helps with
> allocating on the same register variables are defined (from instructions)
> For dealing with phis, we need to introduce groups, in a subsequent
> CL.
>
> From the last CL (memory ops heuristics), this CL improves some
> benchmarks - notably Life (11.94%) in Emscripten x64, and Memops
> (Emscripten), 24% on x86; notable regressions: Memops in
> AreWeFastYet (-14%, x64) and Corrections -25% on x86.
>
> BUG=
>
> Committed: https://crrev.com/038f5eaf3bd6796ed6b7519de83c21d4e1f54850
> Cr-Commit-Position: refs/heads/master@{#30534}

TBR=jarin@chromium.org,bmeurer@chromium.org,mtrofin@chromium.org
NOPRESUBMIT=true
NOTREECHECKS=true
NOTRY=true
BUG=

Review URL: https://codereview.chromium.org/1324763005

Cr-Commit-Position: refs/heads/master@{#30537}
---
 src/compiler/greedy-allocator.cc | 61 ++++++++++++++------------------
 1 file changed, 26 insertions(+), 35 deletions(-)

diff --git a/src/compiler/greedy-allocator.cc b/src/compiler/greedy-allocator.cc
index 63a2e436e..aad322e35 100644
--- a/src/compiler/greedy-allocator.cc
+++ b/src/compiler/greedy-allocator.cc
@@ -21,11 +21,12 @@ const float GreedyAllocator::kAllocatedRangeMultiplier = 10.0;
 
 namespace {
 
-void UpdateOperands(LiveRange* range, RegisterAllocationData* data) {
+
+void UpdateOperands(TopLevelLiveRange* range, RegisterAllocationData* data) {
   int reg_id = range->assigned_register();
   range->SetUseHints(reg_id);
-  if (range->IsTopLevel() && range->TopLevel()->is_phi()) {
-    data->GetPhiMapValueFor(range->TopLevel())->set_assigned_register(reg_id);
+  if (range->is_phi()) {
+    data->GetPhiMapValueFor(range)->set_assigned_register(reg_id);
   }
 }
 
@@ -139,7 +140,6 @@ void GreedyAllocator::AssignRangeToRegister(int reg_id, LiveRange* range) {
   TRACE("Assigning %s to range %d%d.\n", RegisterName(reg_id),
         range->TopLevel()->vreg(), range->relative_id());
   range->set_assigned_register(reg_id);
-  UpdateOperands(range, data());
 }
 
 
@@ -189,42 +189,24 @@ void GreedyAllocator::TryAllocateLiveRange(LiveRange* range) {
         range->relative_id());
   int free_reg = -1;
   int evictable_reg = -1;
-  int hinted_reg = -1;
-
   EnsureValidRangeWeight(range);
   DCHECK(range->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 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++) {
+    float max_conflict_weight = GetMaximumConflictingWeight(i, range);
     if (max_conflict_weight == LiveRange::kInvalidWeight) {
-      free_reg = hinted_reg;
-    } else if (max_conflict_weight < range->weight()) {
-      evictable_reg = hinted_reg;
+      free_reg = i;
+      break;
     }
-  }
-
-  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);
-      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;
-      }
+    if (max_conflict_weight < range->weight() &&
+        max_conflict_weight < smallest_weight) {
+      smallest_weight = max_conflict_weight;
+      evictable_reg = i;
     }
   }
 
@@ -322,6 +304,15 @@ void GreedyAllocator::AllocateRegisters() {
     TryAllocateCandidate(candidate);
   }
 
+
+  // We do not rely on the hint mechanism used by LinearScan, so no need to
+  // actively update/reset operands until the end.
+  for (auto range : data()->live_ranges()) {
+    if (CanProcessRange(range) && range->HasRegisterAssigned()) {
+      UpdateOperands(range, data());
+    }
+  }
+
   for (size_t i = 0; i < allocations_.size(); ++i) {
     if (!allocations_[i]->empty()) {
       data()->MarkAllocated(mode(), static_cast<int>(i));
-- 
2.34.1