blob: fafbe47908019115d95f2dabfb3aec3f73c80b1f (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
// 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-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,
kIsBlockTerminator = 1, // The instruction marks the end of a basic block
// e.g.: jump and return instructions.
kHasSideEffect = 2, // The instruction has some side effects (memory
// store, function call...)
kIsLoadOperation = 4, // The instruction is a memory load.
};
class InstructionScheduler final : public ZoneObject {
public:
InstructionScheduler(Zone* zone, InstructionSequence* sequence);
void StartBlock(RpoNumber rpo);
void EndBlock(RpoNumber rpo);
void AddInstruction(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(unscheduled_predecessors_count_ > 0);
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_;
};
// Compare the two nodes and return true if node1 is a better candidate than
// node2 (i.e. node1 should be scheduled before node2).
bool CompareNodes(ScheduleGraphNode *node1, ScheduleGraphNode *node2) const;
// Perform scheduling for the current block.
void ScheduleBlock();
// Return the scheduling properties of the given instruction.
int GetInstructionFlags(const Instruction* instr) const;
int GetTargetInstructionFlags(const Instruction* instr) const;
// Return true if instr2 uses any value defined by instr1.
bool HasOperandDependency(const Instruction* instr1,
const Instruction* instr2) const;
// Return true if the instruction is a basic block terminator.
bool IsBlockTerminator(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;
}
// Return true if the instruction is a memory load.
bool IsLoadOperation(const Instruction* instr) const {
return GetInstructionFlags(instr) & kIsLoadOperation;
}
// 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();
}
void ComputeTotalLatencies();
static int GetInstructionLatency(const Instruction* instr);
Zone* zone() { return zone_; }
InstructionSequence* sequence() { return sequence_; }
Zone* zone_;
InstructionSequence* sequence_;
ZoneVector<ScheduleGraphNode*> graph_;
// 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_;
};
} // namespace compiler
} // namespace internal
} // namespace v8
#endif // V8_COMPILER_INSTRUCTION_SCHEDULER_H_
|
