1 //===---- ScheduleDAG.cpp - Implement the ScheduleDAG 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 "sched-instrs"
16 #include "llvm/CodeGen/ScheduleDAGInstrs.h"
17 #include "llvm/Target/TargetMachine.h"
18 #include "llvm/Target/TargetInstrInfo.h"
19 #include "llvm/Target/TargetRegisterInfo.h"
20 #include "llvm/Support/Debug.h"
21 #include "llvm/Support/raw_ostream.h"
24 ScheduleDAGInstrs::ScheduleDAGInstrs(MachineBasicBlock *bb,
25 const TargetMachine &tm)
26 : ScheduleDAG(0, bb, tm) {}
28 void ScheduleDAGInstrs::BuildSchedUnits() {
30 SUnits.reserve(BB->size());
32 std::vector<SUnit *> PendingLoads;
33 SUnit *Terminator = 0;
35 SUnit *Defs[TargetRegisterInfo::FirstVirtualRegister] = {};
36 std::vector<SUnit *> Uses[TargetRegisterInfo::FirstVirtualRegister] = {};
37 int Cost = 1; // FIXME
39 for (MachineBasicBlock::iterator MII = BB->end(), MIE = BB->begin();
41 MachineInstr *MI = prior(MII);
42 SUnit *SU = NewSUnit(MI);
44 for (unsigned j = 0, n = MI->getNumOperands(); j != n; ++j) {
45 const MachineOperand &MO = MI->getOperand(j);
46 if (!MO.isReg()) continue;
47 unsigned Reg = MO.getReg();
48 if (Reg == 0) continue;
50 assert(TRI->isPhysicalRegister(Reg) && "Virtual register encountered!");
51 std::vector<SUnit *> &UseList = Uses[Reg];
52 SUnit *&Def = Defs[Reg];
53 // Optionally add output and anti dependencies.
55 Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
56 /*PhyReg=*/Reg, Cost, /*isAntiDep=*/MO.isUse());
57 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
58 SUnit *&Def = Defs[*Alias];
60 Def->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false,
61 /*PhyReg=*/*Alias, Cost);
65 // Add any data dependencies.
66 for (unsigned i = 0, e = UseList.size(); i != e; ++i)
68 UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
69 /*PhysReg=*/Reg, Cost);
70 for (const unsigned *Alias = TRI->getAliasSet(Reg); *Alias; ++Alias) {
71 std::vector<SUnit *> &UseList = Uses[*Alias];
72 for (unsigned i = 0, e = UseList.size(); i != e; ++i)
74 UseList[i]->addPred(SU, /*isCtrl=*/false, /*isArtificial=*/false,
75 /*PhysReg=*/*Alias, Cost);
81 UseList.push_back(SU);
86 if (!MI->isSafeToMove(TII, False)) {
88 Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
89 for (unsigned k = 0, m = PendingLoads.size(); k != m; ++k)
90 PendingLoads[k]->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
93 } else if (!MI->isSafeToMove(TII, True)) {
95 Chain->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
96 PendingLoads.push_back(SU);
98 if (Terminator && SU->Succs.empty())
99 Terminator->addPred(SU, /*isCtrl=*/true, /*isArtificial=*/false);
100 if (MI->getDesc().isTerminator() || MI->isLabel())
103 // Assign the Latency field of SU using target-provided information.
108 void ScheduleDAGInstrs::ComputeLatency(SUnit *SU) {
109 const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
111 // Compute the latency for the node. We use the sum of the latencies for
112 // all nodes flagged together into this SUnit.
114 InstrItins.getLatency(SU->getInstr()->getDesc().getSchedClass());
117 void ScheduleDAGInstrs::dumpNode(const SUnit *SU) const {
118 SU->getInstr()->dump();
121 std::string ScheduleDAGInstrs::getGraphNodeLabel(const SUnit *SU) const {
123 raw_string_ostream oss(s);
124 SU->getInstr()->print(oss);
128 // EmitSchedule - Emit the machine code in scheduled order.
129 MachineBasicBlock *ScheduleDAGInstrs::EmitSchedule() {
130 // For MachineInstr-based scheduling, we're rescheduling the instructions in
131 // the block, so start by removing them from the block.
133 BB->remove(BB->begin());
135 for (unsigned i = 0, e = Sequence.size(); i != e; i++) {
136 SUnit *SU = Sequence[i];
138 // Null SUnit* is a noop.
143 BB->push_back(SU->getInstr());