Revert of [WIP][turbofan] Instruction scheduler for Turbofan.

src/compiler/instruction-scheduler.cc

Index: src/compiler/instruction-scheduler.cc
diff --git a/src/compiler/instruction-scheduler.cc b/src/compiler/instruction-scheduler.cc
deleted file mode 100644
index 2f329ead41569959a6db4799f79b03a549d4f31a..0000000000000000000000000000000000000000
--- a/src/compiler/instruction-scheduler.cc
+++ /dev/null
@@ -1,280 +0,0 @@
-// 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"
-
-namespace v8 {
-namespace internal {
-namespace compiler {
-
-InstructionScheduler::ScheduleGraphNode::ScheduleGraphNode(
-    Zone* zone,
-    Instruction* instr)
-    : instr_(instr),
-      successors_(zone),
-      unscheduled_predecessors_count_(0),
-      latency_(GetInstructionLatency(instr)),
-      total_latency_(-1),
-      start_cycle_(-1) {
-}
-
-
-void InstructionScheduler::ScheduleGraphNode::AddSuccessor(
-    ScheduleGraphNode* node) {
-  successors_.push_back(node);
-  node->unscheduled_predecessors_count_++;
-}
-
-
-InstructionScheduler::InstructionScheduler(Zone* zone,
-                                           InstructionSequence* sequence)
-    : zone_(zone),
-      sequence_(sequence),
-      graph_(zone),
-      last_side_effect_instr_(nullptr),
-      pending_loads_(zone),
-      last_live_in_reg_marker_(nullptr) {
-}
-
-
-void InstructionScheduler::StartBlock(RpoNumber rpo) {
-  DCHECK(graph_.empty());
-  DCHECK(last_side_effect_instr_ == nullptr);
-  DCHECK(pending_loads_.empty());
-  DCHECK(last_live_in_reg_marker_ == nullptr);
-  sequence()->StartBlock(rpo);
-}
-
-
-void InstructionScheduler::EndBlock(RpoNumber rpo) {
-  ScheduleBlock();
-  sequence()->EndBlock(rpo);
-  graph_.clear();
-  last_side_effect_instr_ = nullptr;
-  pending_loads_.clear();
-  last_live_in_reg_marker_ = nullptr;
-}
-
-
-void InstructionScheduler::AddInstruction(Instruction* instr) {
-  ScheduleGraphNode* new_node = new (zone()) ScheduleGraphNode(zone(), instr);
-
-  if (IsBlockTerminator(instr)) {
-    // Make sure that basic block terminators are not moved by adding them
-    // as successor of every instruction.
-    for (auto node : graph_) {
-      node->AddSuccessor(new_node);
-    }
-  } else if (IsFixedRegisterParameter(instr)) {
-    if (last_live_in_reg_marker_ != nullptr) {
-      last_live_in_reg_marker_->AddSuccessor(new_node);
-    }
-    last_live_in_reg_marker_ = new_node;
-  } else {
-    if (last_live_in_reg_marker_ != nullptr) {
-      last_live_in_reg_marker_->AddSuccessor(new_node);
-    }
-
-    // Instructions with side effects and memory operations can't be
-    // reordered with respect to each other.
-    if (HasSideEffect(instr)) {
-      if (last_side_effect_instr_ != nullptr) {
-        last_side_effect_instr_->AddSuccessor(new_node);
-      }
-      for (auto load : pending_loads_) {
-        load->AddSuccessor(new_node);
-      }
-      pending_loads_.clear();
-      last_side_effect_instr_ = new_node;
-    } else if (IsLoadOperation(instr)) {
-      // Load operations can't be reordered with side effects instructions but
-      // independent loads can be reordered with respect to each other.
-      if (last_side_effect_instr_ != nullptr) {
-        last_side_effect_instr_->AddSuccessor(new_node);
-      }
-      pending_loads_.push_back(new_node);
-    }
-
-    // Look for operand dependencies.
-    for (auto node : graph_) {
-      if (HasOperandDependency(node->instruction(), instr)) {
-        node->AddSuccessor(new_node);
-      }
-    }
-  }
-
-  graph_.push_back(new_node);
-}
-
-
-bool InstructionScheduler::CompareNodes(ScheduleGraphNode *node1,
-                                        ScheduleGraphNode *node2) const {
-  return node1->total_latency() > node2->total_latency();
-}
-
-
-void InstructionScheduler::ScheduleBlock() {
-  ZoneLinkedList<ScheduleGraphNode*> ready_list(zone());
-
-  // Compute total latencies so that we can schedule the critical path first.
-  ComputeTotalLatencies();
-
-  // Add nodes which don't have dependencies to the ready list.
-  for (auto node : graph_) {
-    if (!node->HasUnscheduledPredecessor()) {
-      ready_list.push_back(node);
-    }
-  }
-
-  // Go through the ready list and schedule the instructions.
-  int cycle = 0;
-  while (!ready_list.empty()) {
-    auto candidate = ready_list.end();
-    for (auto iterator = ready_list.begin(); iterator != ready_list.end();
-         ++iterator) {
-      // Look for the best candidate to schedule.
-      // We only consider instructions that have all their operands ready and
-      // we try to schedule the critical path first (we look for the instruction
-      // with the highest latency on the path to reach the end of the graph).
-      if (cycle >= (*iterator)->start_cycle()) {
-        if ((candidate == ready_list.end()) ||
-            CompareNodes(*iterator, *candidate)) {
-          candidate = iterator;
-        }
-      }
-    }
-
-    if (candidate != ready_list.end()) {
-      sequence()->AddInstruction((*candidate)->instruction());
-
-      for (auto successor : (*candidate)->successors()) {
-        successor->DropUnscheduledPredecessor();
-        successor->set_start_cycle(
-            std::max(successor->start_cycle(),
-                     cycle + (*candidate)->latency()));
-
-        if (!successor->HasUnscheduledPredecessor()) {
-          ready_list.push_back(successor);
-        }
-      }
-
-      ready_list.erase(candidate);
-    }
-
-    cycle++;
-  }
-}
-
-
-int InstructionScheduler::GetInstructionFlags(const Instruction* instr) const {
-  switch (instr->arch_opcode()) {
-    case kArchNop:
-    case kArchStackPointer:
-    case kArchFramePointer:
-    case kArchTruncateDoubleToI:
-      return kNoOpcodeFlags;
-
-    case kArchPrepareCallCFunction:
-    case kArchPrepareTailCall:
-    case kArchCallCFunction:
-    case kArchCallCodeObject:
-    case kArchCallJSFunction:
-    case kArchLazyBailout:
-      return kHasSideEffect;
-
-    case kArchTailCallCodeObject:
-    case kArchTailCallJSFunction:
-      return kHasSideEffect | kIsBlockTerminator;
-
-    case kArchDeoptimize:
-    case kArchJmp:
-    case kArchLookupSwitch:
-    case kArchTableSwitch:
-    case kArchRet:
-    case kArchThrowTerminator:
-      return kIsBlockTerminator;
-
-    case kCheckedLoadInt8:
-    case kCheckedLoadUint8:
-    case kCheckedLoadInt16:
-    case kCheckedLoadUint16:
-    case kCheckedLoadWord32:
-    case kCheckedLoadWord64:
-    case kCheckedLoadFloat32:
-    case kCheckedLoadFloat64:
-      return kIsLoadOperation;
-
-    case kCheckedStoreWord8:
-    case kCheckedStoreWord16:
-    case kCheckedStoreWord32:
-    case kCheckedStoreWord64:
-    case kCheckedStoreFloat32:
-    case kCheckedStoreFloat64:
-    case kArchStoreWithWriteBarrier:
-      return kHasSideEffect;
-
-#define CASE(Name) case k##Name:
-    TARGET_ARCH_OPCODE_LIST(CASE)
-#undef CASE
-      return GetTargetInstructionFlags(instr);
-  }
-
-  UNREACHABLE();
-  return kNoOpcodeFlags;
-}
-
-
-bool InstructionScheduler::HasOperandDependency(
-    const Instruction* instr1, const Instruction* instr2) const {
-  for (size_t i = 0; i < instr1->OutputCount(); ++i) {
-    for (size_t j = 0; j < instr2->InputCount(); ++j) {
-      const InstructionOperand* output = instr1->OutputAt(i);
-      const InstructionOperand* input = instr2->InputAt(j);
-
-      if (output->IsUnallocated() && input->IsUnallocated() &&
-          (UnallocatedOperand::cast(output)->virtual_register() ==
-           UnallocatedOperand::cast(input)->virtual_register())) {
-        return true;
-      }
-
-      if (output->IsConstant() && input->IsUnallocated() &&
-          (ConstantOperand::cast(output)->virtual_register() ==
-           UnallocatedOperand::cast(input)->virtual_register())) {
-        return true;
-      }
-    }
-  }
-
-  // TODO(bafsa): Do we need to look for anti-dependencies/output-dependencies?
-
-  return false;
-}
-
-
-bool InstructionScheduler::IsBlockTerminator(const Instruction* instr) const {
-  return ((GetInstructionFlags(instr) & kIsBlockTerminator) ||
-          (instr->flags_mode() == kFlags_branch));
-}
-
-
-void InstructionScheduler::ComputeTotalLatencies() {
-  for (auto node : base::Reversed(graph_)) {
-    int max_latency = 0;
-
-    for (auto successor : node->successors()) {
-      DCHECK(successor->total_latency() != -1);
-      if (successor->total_latency() > max_latency) {
-        max_latency = successor->total_latency();
-      }
-    }
-
-    node->set_total_latency(max_latency + node->latency());
-  }
-}
-
-}  // namespace compiler
-}  // namespace internal
-}  // namespace v8