1 //===--- ScheduleDAGSDNodes.cpp - Implement the ScheduleDAGSDNodes class --===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This implements the ScheduleDAG class, which is a base class used by
11 // scheduling implementation classes.
13 //===----------------------------------------------------------------------===//
15 #define DEBUG_TYPE "pre-RA-sched"
16 #include "ScheduleDAGSDNodes.h"
17 #include "InstrEmitter.h"
18 #include "llvm/CodeGen/SelectionDAG.h"
19 #include "llvm/Target/TargetMachine.h"
20 #include "llvm/Target/TargetInstrInfo.h"
21 #include "llvm/Target/TargetRegisterInfo.h"
22 #include "llvm/Target/TargetSubtarget.h"
23 #include "llvm/Support/Debug.h"
24 #include "llvm/Support/raw_ostream.h"
27 ScheduleDAGSDNodes::ScheduleDAGSDNodes(MachineFunction &mf)
31 /// Run - perform scheduling.
33 void ScheduleDAGSDNodes::Run(SelectionDAG *dag, MachineBasicBlock *bb,
34 MachineBasicBlock::iterator insertPos) {
36 ScheduleDAG::Run(bb, insertPos);
39 SUnit *ScheduleDAGSDNodes::Clone(SUnit *Old) {
40 SUnit *SU = NewSUnit(Old->getNode());
41 SU->OrigNode = Old->OrigNode;
42 SU->Latency = Old->Latency;
43 SU->isTwoAddress = Old->isTwoAddress;
44 SU->isCommutable = Old->isCommutable;
45 SU->hasPhysRegDefs = Old->hasPhysRegDefs;
46 SU->hasPhysRegClobbers = Old->hasPhysRegClobbers;
51 /// CheckForPhysRegDependency - Check if the dependency between def and use of
52 /// a specified operand is a physical register dependency. If so, returns the
53 /// register and the cost of copying the register.
54 static void CheckForPhysRegDependency(SDNode *Def, SDNode *User, unsigned Op,
55 const TargetRegisterInfo *TRI,
56 const TargetInstrInfo *TII,
57 unsigned &PhysReg, int &Cost) {
58 if (Op != 2 || User->getOpcode() != ISD::CopyToReg)
61 unsigned Reg = cast<RegisterSDNode>(User->getOperand(1))->getReg();
62 if (TargetRegisterInfo::isVirtualRegister(Reg))
65 unsigned ResNo = User->getOperand(2).getResNo();
66 if (Def->isMachineOpcode()) {
67 const TargetInstrDesc &II = TII->get(Def->getMachineOpcode());
68 if (ResNo >= II.getNumDefs() &&
69 II.ImplicitDefs[ResNo - II.getNumDefs()] == Reg) {
71 const TargetRegisterClass *RC =
72 TRI->getPhysicalRegisterRegClass(Reg, Def->getValueType(ResNo));
73 Cost = RC->getCopyCost();
78 void ScheduleDAGSDNodes::BuildSchedUnits() {
79 // During scheduling, the NodeId field of SDNode is used to map SDNodes
80 // to their associated SUnits by holding SUnits table indices. A value
81 // of -1 means the SDNode does not yet have an associated SUnit.
82 unsigned NumNodes = 0;
83 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
84 E = DAG->allnodes_end(); NI != E; ++NI) {
89 // Reserve entries in the vector for each of the SUnits we are creating. This
90 // ensure that reallocation of the vector won't happen, so SUnit*'s won't get
92 // FIXME: Multiply by 2 because we may clone nodes during scheduling.
93 // This is a temporary workaround.
94 SUnits.reserve(NumNodes * 2);
96 // Check to see if the scheduler cares about latencies.
97 bool UnitLatencies = ForceUnitLatencies();
99 for (SelectionDAG::allnodes_iterator NI = DAG->allnodes_begin(),
100 E = DAG->allnodes_end(); NI != E; ++NI) {
101 if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate.
104 // If this node has already been processed, stop now.
105 if (NI->getNodeId() != -1) continue;
107 SUnit *NodeSUnit = NewSUnit(NI);
109 // See if anything is flagged to this node, if so, add them to flagged
110 // nodes. Nodes can have at most one flag input and one flag output. Flags
111 // are required to be the last operand and result of a node.
113 // Scan up to find flagged preds.
115 while (N->getNumOperands() &&
116 N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) {
117 N = N->getOperand(N->getNumOperands()-1).getNode();
118 assert(N->getNodeId() == -1 && "Node already inserted!");
119 N->setNodeId(NodeSUnit->NodeNum);
122 // Scan down to find any flagged succs.
124 while (N->getValueType(N->getNumValues()-1) == MVT::Flag) {
125 SDValue FlagVal(N, N->getNumValues()-1);
127 // There are either zero or one users of the Flag result.
128 bool HasFlagUse = false;
129 for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end();
131 if (FlagVal.isOperandOf(*UI)) {
133 assert(N->getNodeId() == -1 && "Node already inserted!");
134 N->setNodeId(NodeSUnit->NodeNum);
138 if (!HasFlagUse) break;
141 // If there are flag operands involved, N is now the bottom-most node
142 // of the sequence of nodes that are flagged together.
144 NodeSUnit->setNode(N);
145 assert(N->getNodeId() == -1 && "Node already inserted!");
146 N->setNodeId(NodeSUnit->NodeNum);
148 // Assign the Latency field of NodeSUnit using target-provided information.
150 NodeSUnit->Latency = 1;
152 ComputeLatency(NodeSUnit);
156 void ScheduleDAGSDNodes::AddSchedEdges() {
157 const TargetSubtarget &ST = TM.getSubtarget<TargetSubtarget>();
159 // Check to see if the scheduler cares about latencies.
160 bool UnitLatencies = ForceUnitLatencies();
162 // Pass 2: add the preds, succs, etc.
163 for (unsigned su = 0, e = SUnits.size(); su != e; ++su) {
164 SUnit *SU = &SUnits[su];
165 SDNode *MainNode = SU->getNode();
167 if (MainNode->isMachineOpcode()) {
168 unsigned Opc = MainNode->getMachineOpcode();
169 const TargetInstrDesc &TID = TII->get(Opc);
170 for (unsigned i = 0; i != TID.getNumOperands(); ++i) {
171 if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) {
172 SU->isTwoAddress = true;
176 if (TID.isCommutable())
177 SU->isCommutable = true;
180 // Find all predecessors and successors of the group.
181 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode()) {
182 if (N->isMachineOpcode() &&
183 TII->get(N->getMachineOpcode()).getImplicitDefs()) {
184 SU->hasPhysRegClobbers = true;
185 unsigned NumUsed = InstrEmitter::CountResults(N);
186 while (NumUsed != 0 && !N->hasAnyUseOfValue(NumUsed - 1))
187 --NumUsed; // Skip over unused values at the end.
188 if (NumUsed > TII->get(N->getMachineOpcode()).getNumDefs())
189 SU->hasPhysRegDefs = true;
192 for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) {
193 SDNode *OpN = N->getOperand(i).getNode();
194 if (isPassiveNode(OpN)) continue; // Not scheduled.
195 SUnit *OpSU = &SUnits[OpN->getNodeId()];
196 assert(OpSU && "Node has no SUnit!");
197 if (OpSU == SU) continue; // In the same group.
199 EVT OpVT = N->getOperand(i).getValueType();
200 assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!");
201 bool isChain = OpVT == MVT::Other;
203 unsigned PhysReg = 0;
205 // Determine if this is a physical register dependency.
206 CheckForPhysRegDependency(OpN, N, i, TRI, TII, PhysReg, Cost);
207 assert((PhysReg == 0 || !isChain) &&
208 "Chain dependence via physreg data?");
209 // FIXME: See ScheduleDAGSDNodes::EmitCopyFromReg. For now, scheduler
210 // emits a copy from the physical register to a virtual register unless
211 // it requires a cross class copy (cost < 0). That means we are only
212 // treating "expensive to copy" register dependency as physical register
213 // dependency. This may change in the future though.
217 const SDep& dep = SDep(OpSU, isChain ? SDep::Order : SDep::Data,
218 OpSU->Latency, PhysReg);
219 if (!isChain && !UnitLatencies) {
220 ComputeOperandLatency(OpSU, SU, (SDep &)dep);
221 ST.adjustSchedDependency(OpSU, SU, (SDep &)dep);
230 /// BuildSchedGraph - Build the SUnit graph from the selection dag that we
231 /// are input. This SUnit graph is similar to the SelectionDAG, but
232 /// excludes nodes that aren't interesting to scheduling, and represents
233 /// flagged together nodes with a single SUnit.
234 void ScheduleDAGSDNodes::BuildSchedGraph(AliasAnalysis *AA) {
235 // Populate the SUnits array.
237 // Compute all the scheduling dependencies between nodes.
241 void ScheduleDAGSDNodes::ComputeLatency(SUnit *SU) {
242 const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
244 // Compute the latency for the node. We use the sum of the latencies for
245 // all nodes flagged together into this SUnit.
247 for (SDNode *N = SU->getNode(); N; N = N->getFlaggedNode())
248 if (N->isMachineOpcode()) {
249 SU->Latency += InstrItins.
250 getStageLatency(TII->get(N->getMachineOpcode()).getSchedClass());
254 void ScheduleDAGSDNodes::dumpNode(const SUnit *SU) const {
255 if (!SU->getNode()) {
256 errs() << "PHYS REG COPY\n";
260 SU->getNode()->dump(DAG);
262 SmallVector<SDNode *, 4> FlaggedNodes;
263 for (SDNode *N = SU->getNode()->getFlaggedNode(); N; N = N->getFlaggedNode())
264 FlaggedNodes.push_back(N);
265 while (!FlaggedNodes.empty()) {
267 FlaggedNodes.back()->dump(DAG);
269 FlaggedNodes.pop_back();
273 /// EmitSchedule - Emit the machine code in scheduled order.
274 MachineBasicBlock *ScheduleDAGSDNodes::
275 EmitSchedule(DenseMap<MachineBasicBlock*, MachineBasicBlock*> *EM) {
276 InstrEmitter Emitter(BB, InsertPos);
277 DenseMap<SDValue, unsigned> VRBaseMap;
278 DenseMap<SUnit*, unsigned> CopyVRBaseMap;
279 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
280 SUnit *SU = Sequence[i];
282 // Null SUnit* is a noop.
287 // For pre-regalloc scheduling, create instructions corresponding to the
288 // SDNode and any flagged SDNodes and append them to the block.
289 if (!SU->getNode()) {
291 EmitPhysRegCopy(SU, CopyVRBaseMap);
295 SmallVector<SDNode *, 4> FlaggedNodes;
296 for (SDNode *N = SU->getNode()->getFlaggedNode(); N;
297 N = N->getFlaggedNode())
298 FlaggedNodes.push_back(N);
299 while (!FlaggedNodes.empty()) {
300 Emitter.EmitNode(FlaggedNodes.back(), SU->OrigNode != SU, SU->isCloned,
302 FlaggedNodes.pop_back();
304 Emitter.EmitNode(SU->getNode(), SU->OrigNode != SU, SU->isCloned,
308 BB = Emitter.getBlock();
309 InsertPos = Emitter.getInsertPos();