Upgrade V8 to version 4.9.385.28
https://chromium.googlesource.com/v8/v8/+/4.9.385.28
Change-Id: I4b2e74289d4bf3667f2f3dc8aa2e541f63e26eb4
diff --git a/src/compiler/instruction-scheduler.cc b/src/compiler/instruction-scheduler.cc
new file mode 100644
index 0000000..2f329ea
--- /dev/null
+++ b/src/compiler/instruction-scheduler.cc
@@ -0,0 +1,280 @@
+// 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