[turbofan] Instruction scheduler: keep ready nodes list sorted by latency.

src/compiler/instruction-scheduler.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/instruction-scheduler.h"
 
 #include "src/base/adapters.h"
 #include "src/base/utils/random-number-generator.h"
 
 namespace v8 {
 namespace internal {
 namespace compiler {
 
-// Compare the two nodes and return true if node1 is a better candidate than
-// node2 (i.e. node1 should be scheduled before node2).
-bool InstructionScheduler::CriticalPathFirstQueue::CompareNodes(
-    ScheduleGraphNode *node1, ScheduleGraphNode *node2) const {
-  return node1->total_latency() > node2->total_latency();
+void InstructionScheduler::SchedulingQueueBase::AddNode(
+    ScheduleGraphNode* node) {
+  // We keep the ready list sorted by total latency so that we can quickly find
+  // the next best candidate to schedule.
+  auto it = nodes_.begin();
+  while ((it != nodes_.end()) &&
+         ((*it)->total_latency() > node->total_latency())) {
+    ++it;
+  }
+  nodes_.insert(it, node);
 }
 
 
 InstructionScheduler::ScheduleGraphNode*
 InstructionScheduler::CriticalPathFirstQueue::PopBestCandidate(int cycle) {
   DCHECK(!IsEmpty());
   auto candidate = nodes_.end();
   for (auto iterator = nodes_.begin(); iterator != nodes_.end(); ++iterator) {
-    // We only consider instructions that have all their operands ready and
-    // we try to schedule the critical path first.
+    // We only consider instructions that have all their operands ready.
     if (cycle >= (*iterator)->start_cycle()) {
-      if ((candidate == nodes_.end()) || CompareNodes(*iterator, *candidate)) {
-        candidate = iterator;
-      }
+      candidate = iterator;
+      break;
     }
   }
 
   if (candidate != nodes_.end()) {
     ScheduleGraphNode *result = *candidate;
     nodes_.erase(candidate);
     return result;
   }
 
   return nullptr;
@@ skipping 309 matching lines @@
       }
     }
 
     node->set_total_latency(max_latency + node->latency());
   }
 }
 
 }  // namespace compiler
 }  // namespace internal
 }  // namespace v8