// 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.
|
|
#ifndef V8_COMPILER_INSTRUCTION_SCHEDULER_H_
|
#define V8_COMPILER_INSTRUCTION_SCHEDULER_H_
|
|
#include "src/compiler/instruction.h"
|
#include "src/zone/zone-containers.h"
|
|
namespace v8 {
|
namespace internal {
|
namespace compiler {
|
|
// A set of flags describing properties of the instructions so that the
|
// scheduler is aware of dependencies between instructions.
|
enum ArchOpcodeFlags {
|
kNoOpcodeFlags = 0,
|
kHasSideEffect = 1, // The instruction has some side effects (memory
|
// store, function call...)
|
kIsLoadOperation = 2, // The instruction is a memory load.
|
kMayNeedDeoptOrTrapCheck = 4, // The instruction may be associated with a
|
// deopt or trap check which must be run before
|
// instruction e.g. div on Intel platform which
|
// will raise an exception when the divisor is
|
// zero.
|
};
|
|
class InstructionScheduler final : public ZoneObject {
|
public:
|
InstructionScheduler(Zone* zone, InstructionSequence* sequence);
|
|
void StartBlock(RpoNumber rpo);
|
void EndBlock(RpoNumber rpo);
|
|
void AddInstruction(Instruction* instr);
|
void AddTerminator(Instruction* instr);
|
|
static bool SchedulerSupported();
|
|
private:
|
// A scheduling graph node.
|
// Represent an instruction and their dependencies.
|
class ScheduleGraphNode: public ZoneObject {
|
public:
|
ScheduleGraphNode(Zone* zone, Instruction* instr);
|
|
// Mark the instruction represented by 'node' as a dependecy of this one.
|
// The current instruction will be registered as an unscheduled predecessor
|
// of 'node' (i.e. it must be scheduled before 'node').
|
void AddSuccessor(ScheduleGraphNode* node);
|
|
// Check if all the predecessors of this instruction have been scheduled.
|
bool HasUnscheduledPredecessor() {
|
return unscheduled_predecessors_count_ != 0;
|
}
|
|
// Record that we have scheduled one of the predecessors of this node.
|
void DropUnscheduledPredecessor() {
|
DCHECK_LT(0, unscheduled_predecessors_count_);
|
unscheduled_predecessors_count_--;
|
}
|
|
Instruction* instruction() { return instr_; }
|
ZoneDeque<ScheduleGraphNode*>& successors() { return successors_; }
|
int latency() const { return latency_; }
|
|
int total_latency() const { return total_latency_; }
|
void set_total_latency(int latency) { total_latency_ = latency; }
|
|
int start_cycle() const { return start_cycle_; }
|
void set_start_cycle(int start_cycle) { start_cycle_ = start_cycle; }
|
|
private:
|
Instruction* instr_;
|
ZoneDeque<ScheduleGraphNode*> successors_;
|
|
// Number of unscheduled predecessors for this node.
|
int unscheduled_predecessors_count_;
|
|
// Estimate of the instruction latency (the number of cycles it takes for
|
// instruction to complete).
|
int latency_;
|
|
// The sum of all the latencies on the path from this node to the end of
|
// the graph (i.e. a node with no successor).
|
int total_latency_;
|
|
// The scheduler keeps a nominal cycle count to keep track of when the
|
// result of an instruction is available. This field is updated by the
|
// scheduler to indicate when the value of all the operands of this
|
// instruction will be available.
|
int start_cycle_;
|
};
|
|
// Keep track of all nodes ready to be scheduled (i.e. all their dependencies
|
// have been scheduled. Note that this class is inteded to be extended by
|
// concrete implementation of the scheduling queue which define the policy
|
// to pop node from the queue.
|
class SchedulingQueueBase {
|
public:
|
explicit SchedulingQueueBase(InstructionScheduler* scheduler)
|
: scheduler_(scheduler),
|
nodes_(scheduler->zone()) {
|
}
|
|
void AddNode(ScheduleGraphNode* node);
|
|
bool IsEmpty() const {
|
return nodes_.empty();
|
}
|
|
protected:
|
InstructionScheduler* scheduler_;
|
ZoneLinkedList<ScheduleGraphNode*> nodes_;
|
};
|
|
// A scheduling queue which prioritize nodes on the critical path (we look
|
// for the instruction with the highest latency on the path to reach the end
|
// of the graph).
|
class CriticalPathFirstQueue : public SchedulingQueueBase {
|
public:
|
explicit CriticalPathFirstQueue(InstructionScheduler* scheduler)
|
: SchedulingQueueBase(scheduler) { }
|
|
// Look for the best candidate to schedule, remove it from the queue and
|
// return it.
|
ScheduleGraphNode* PopBestCandidate(int cycle);
|
};
|
|
// A queue which pop a random node from the queue to perform stress tests on
|
// the scheduler.
|
class StressSchedulerQueue : public SchedulingQueueBase {
|
public:
|
explicit StressSchedulerQueue(InstructionScheduler* scheduler)
|
: SchedulingQueueBase(scheduler) { }
|
|
ScheduleGraphNode* PopBestCandidate(int cycle);
|
|
private:
|
Isolate *isolate() {
|
return scheduler_->isolate();
|
}
|
};
|
|
// Perform scheduling for the current block specifying the queue type to
|
// use to determine the next best candidate.
|
template <typename QueueType>
|
void ScheduleBlock();
|
|
// Return the scheduling properties of the given instruction.
|
int GetInstructionFlags(const Instruction* instr) const;
|
int GetTargetInstructionFlags(const Instruction* instr) const;
|
|
// Check whether the given instruction has side effects (e.g. function call,
|
// memory store).
|
bool HasSideEffect(const Instruction* instr) const {
|
return (GetInstructionFlags(instr) & kHasSideEffect) != 0;
|
}
|
|
// Return true if the instruction is a memory load.
|
bool IsLoadOperation(const Instruction* instr) const {
|
return (GetInstructionFlags(instr) & kIsLoadOperation) != 0;
|
}
|
|
// The scheduler will not move the following instructions before the last
|
// deopt/trap check:
|
// * loads (this is conservative)
|
// * instructions with side effect
|
// * other deopts/traps
|
// Any other instruction can be moved, apart from those that raise exceptions
|
// on specific inputs - these are filtered out by the deopt/trap check.
|
bool MayNeedDeoptOrTrapCheck(const Instruction* instr) const {
|
return (GetInstructionFlags(instr) & kMayNeedDeoptOrTrapCheck) != 0;
|
}
|
|
// Return true if the instruction cannot be moved before the last deopt or
|
// trap point we encountered.
|
bool DependsOnDeoptOrTrap(const Instruction* instr) const {
|
return MayNeedDeoptOrTrapCheck(instr) || instr->IsDeoptimizeCall() ||
|
instr->IsTrap() || HasSideEffect(instr) || IsLoadOperation(instr);
|
}
|
|
// Identify nops used as a definition point for live-in registers at
|
// function entry.
|
bool IsFixedRegisterParameter(const Instruction* instr) const {
|
return (instr->arch_opcode() == kArchNop) && (instr->OutputCount() == 1) &&
|
(instr->OutputAt(0)->IsUnallocated()) &&
|
(UnallocatedOperand::cast(instr->OutputAt(0))
|
->HasFixedRegisterPolicy() ||
|
UnallocatedOperand::cast(instr->OutputAt(0))
|
->HasFixedFPRegisterPolicy());
|
}
|
|
void ComputeTotalLatencies();
|
|
static int GetInstructionLatency(const Instruction* instr);
|
|
Zone* zone() { return zone_; }
|
InstructionSequence* sequence() { return sequence_; }
|
Isolate* isolate() { return sequence()->isolate(); }
|
|
Zone* zone_;
|
InstructionSequence* sequence_;
|
ZoneVector<ScheduleGraphNode*> graph_;
|
|
friend class InstructionSchedulerTester;
|
|
// Last side effect instruction encountered while building the graph.
|
ScheduleGraphNode* last_side_effect_instr_;
|
|
// Set of load instructions encountered since the last side effect instruction
|
// which will be added as predecessors of the next instruction with side
|
// effects.
|
ZoneVector<ScheduleGraphNode*> pending_loads_;
|
|
// Live-in register markers are nop instructions which are emitted at the
|
// beginning of a basic block so that the register allocator will find a
|
// defining instruction for live-in values. They must not be moved.
|
// All these nops are chained together and added as a predecessor of every
|
// other instructions in the basic block.
|
ScheduleGraphNode* last_live_in_reg_marker_;
|
|
// Last deoptimization or trap instruction encountered while building the
|
// graph.
|
ScheduleGraphNode* last_deopt_or_trap_;
|
|
// Keep track of definition points for virtual registers. This is used to
|
// record operand dependencies in the scheduling graph.
|
ZoneMap<int32_t, ScheduleGraphNode*> operands_map_;
|
};
|
|
} // namespace compiler
|
} // namespace internal
|
} // namespace v8
|
|
#endif // V8_COMPILER_INSTRUCTION_SCHEDULER_H_
|
