diff options
| -rw-r--r-- | include/llvm/CodeGen/ScheduleDAG.h | 111 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAG.cpp | 251 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp | 927 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/ScheduleDAGRRList.cpp | 813 | ||||
| -rw-r--r-- | lib/CodeGen/SelectionDAG/SelectionDAGISel.cpp | 45 |
5 files changed, 1215 insertions, 932 deletions
diff --git a/include/llvm/CodeGen/ScheduleDAG.h b/include/llvm/CodeGen/ScheduleDAG.h index f72285e0f4..5f9236d401 100644 --- a/include/llvm/CodeGen/ScheduleDAG.h +++ b/include/llvm/CodeGen/ScheduleDAG.h @@ -17,6 +17,8 @@ #include "llvm/CodeGen/SelectionDAG.h" +#include <set> + namespace llvm { struct InstrStage; class MachineConstantPool; @@ -71,8 +73,88 @@ namespace llvm { } }; + /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or + /// a group of nodes flagged together. + struct SUnit { + SDNode *Node; // Representative node. + std::vector<SDNode*> FlaggedNodes; // All nodes flagged to Node. + + // Preds/Succs - The SUnits before/after us in the graph. The boolean value + // is true if the edge is a token chain edge, false if it is a value edge. + std::set<std::pair<SUnit*,bool> > Preds; // All sunit predecessors. + std::set<std::pair<SUnit*,bool> > Succs; // All sunit successors. + + short NumPreds; // # of preds. + short NumSuccs; // # of sucss. + short NumPredsLeft; // # of preds not scheduled. + short NumSuccsLeft; // # of succs not scheduled. + short NumChainPredsLeft; // # of chain preds not scheduled. + short NumChainSuccsLeft; // # of chain succs not scheduled. + bool isTwoAddress : 1; // Is a two-address instruction. + bool isDefNUseOperand : 1; // Is a def&use operand. + bool isPending : 1; // True once pending. + bool isAvailable : 1; // True once available. + bool isScheduled : 1; // True once scheduled. + unsigned short Latency; // Node latency. + unsigned CycleBound; // Upper/lower cycle to be scheduled at. + unsigned Cycle; // Once scheduled, the cycle of the op. + unsigned Depth; // Node depth; + unsigned Height; // Node height; + unsigned NodeNum; // Entry # of node in the node vector. + + SUnit(SDNode *node, unsigned nodenum) + : Node(node), NumPreds(0), NumSuccs(0), NumPredsLeft(0), NumSuccsLeft(0), + NumChainPredsLeft(0), NumChainSuccsLeft(0), + isTwoAddress(false), isDefNUseOperand(false), + isPending(false), isAvailable(false), isScheduled(false), + Latency(0), CycleBound(0), Cycle(0), Depth(0), Height(0), + NodeNum(nodenum) {} + + void dump(const SelectionDAG *G) const; + void dumpAll(const SelectionDAG *G) const; + }; + + //===--------------------------------------------------------------------===// + /// SchedulingPriorityQueue - This interface is used to plug different + /// priorities computation algorithms into the list scheduler. It implements + /// the interface of a standard priority queue, where nodes are inserted in + /// arbitrary order and returned in priority order. The computation of the + /// priority and the representation of the queue are totally up to the + /// implementation to decide. + /// + class SchedulingPriorityQueue { + public: + virtual ~SchedulingPriorityQueue() {} + + virtual void initNodes(const std::vector<SUnit> &SUnits) = 0; + virtual void releaseState() = 0; + + virtual bool empty() const = 0; + virtual void push(SUnit *U) = 0; + + virtual void push_all(const std::vector<SUnit *> &Nodes) = 0; + virtual SUnit *pop() = 0; + + /// ScheduledNode - As each node is scheduled, this method is invoked. This + /// allows the priority function to adjust the priority of node that have + /// already been emitted. + virtual void ScheduledNode(SUnit *Node) {} + }; + class ScheduleDAG { public: + + // Scheduling heuristics + enum SchedHeuristics { + defaultScheduling, // Let the target specify its preference. + noScheduling, // No scheduling, emit breadth first sequence. + simpleScheduling, // Two pass, min. critical path, max. utilization. + simpleNoItinScheduling, // Same as above exact using generic latency. + listSchedulingBURR, // Bottom-up reg reduction list scheduling. + listSchedulingTDRR, // Top-down reg reduction list scheduling. + listSchedulingTD // Top-down list scheduler. + }; + SelectionDAG &DAG; // DAG of the current basic block MachineBasicBlock *BB; // Current basic block const TargetMachine &TM; // Target processor @@ -80,6 +162,10 @@ namespace llvm { const MRegisterInfo *MRI; // Target processor register info SSARegMap *RegMap; // Virtual/real register map MachineConstantPool *ConstPool; // Target constant pool + std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s represent + // noop instructions. + std::map<SDNode*, SUnit*> SUnitMap; // SDNode to SUnit mapping (n -> 1). + std::vector<SUnit> SUnits; // The scheduling units. ScheduleDAG(SelectionDAG &dag, MachineBasicBlock *bb, const TargetMachine &tm) @@ -105,6 +191,23 @@ namespace llvm { return false; } + /// NewSUnit - Creates a new SUnit and return a ptr to it. + /// + SUnit *NewSUnit(SDNode *N) { + SUnits.push_back(SUnit(N, SUnits.size())); + return &SUnits.back(); + } + + /// BuildSchedUnits - Build SUnits from the selection dag that we are input. + /// This SUnit graph is similar to the SelectionDAG, but represents flagged + /// together nodes with a single SUnit. + void BuildSchedUnits(); + + /// CalculateDepths, CalculateHeights - Calculate node depth / height. + /// + void CalculateDepths(); + void CalculateHeights(); + /// EmitNode - Generate machine code for an node and needed dependencies. /// VRBaseMap contains, for each already emitted node, the first virtual /// register number for the results of the node. @@ -115,6 +218,9 @@ namespace llvm { /// void EmitNoop(); + void EmitSchedule(); + + void dumpSchedule() const; /// Schedule - Order nodes according to selected style. /// @@ -138,6 +244,11 @@ namespace llvm { ScheduleDAG* createBURRListDAGScheduler(SelectionDAG &DAG, MachineBasicBlock *BB); + /// createTDRRListDAGScheduler - This creates a top down register usage + /// reduction list scheduler. + ScheduleDAG* createTDRRListDAGScheduler(SelectionDAG &DAG, + MachineBasicBlock *BB); + /// createTDListDAGScheduler - This creates a top-down list scheduler with /// the specified hazard recognizer. This takes ownership of the hazard /// recognizer and deletes it when done. diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp index f9749903a7..4a9b9c7f04 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAG.cpp @@ -13,6 +13,7 @@ // //===----------------------------------------------------------------------===// +#define DEBUG_TYPE "sched" #include "llvm/CodeGen/ScheduleDAG.h" #include "llvm/CodeGen/MachineConstantPool.h" #include "llvm/CodeGen/MachineFunction.h" @@ -20,10 +21,185 @@ #include "llvm/Target/TargetMachine.h" #include "llvm/Target/TargetInstrInfo.h" #include "llvm/Target/TargetLowering.h" +#include "llvm/Support/Debug.h" #include "llvm/Support/MathExtras.h" +#include <iostream> using namespace llvm; +/// BuildSchedUnits - Build SUnits from the selection dag that we are input. +/// This SUnit graph is similar to the SelectionDAG, but represents flagged +/// together nodes with a single SUnit. +void ScheduleDAG::BuildSchedUnits() { + // Reserve entries in the vector for each of the SUnits we are creating. This + // ensure that reallocation of the vector won't happen, so SUnit*'s won't get + // invalidated. + SUnits.reserve(std::distance(DAG.allnodes_begin(), DAG.allnodes_end())); + + const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); + + for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(), + E = DAG.allnodes_end(); NI != E; ++NI) { + if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. + continue; + + // If this node has already been processed, stop now. + if (SUnitMap[NI]) continue; + + SUnit *NodeSUnit = NewSUnit(NI); + + // See if anything is flagged to this node, if so, add them to flagged + // nodes. Nodes can have at most one flag input and one flag output. Flags + // are required the be the last operand and result of a node. + + // Scan up, adding flagged preds to FlaggedNodes. + SDNode *N = NI; + while (N->getNumOperands() && + N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { + N = N->getOperand(N->getNumOperands()-1).Val; + NodeSUnit->FlaggedNodes.push_back(N); + SUnitMap[N] = NodeSUnit; + } + + // Scan down, adding this node and any flagged succs to FlaggedNodes if they + // have a user of the flag operand. + N = NI; + while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { + SDOperand FlagVal(N, N->getNumValues()-1); + + // There are either zero or one users of the Flag result. + bool HasFlagUse = false; + for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); + UI != E; ++UI) + if (FlagVal.isOperand(*UI)) { + HasFlagUse = true; + NodeSUnit->FlaggedNodes.push_back(N); + SUnitMap[N] = NodeSUnit; + N = *UI; + break; + } + if (!HasFlagUse) break; + } + + // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node. + // Update the SUnit + NodeSUnit->Node = N; + SUnitMap[N] = NodeSUnit; + + // Compute the latency for the node. We use the sum of the latencies for + // all nodes flagged together into this SUnit. + if (InstrItins.isEmpty()) { + // No latency information. + NodeSUnit->Latency = 1; + } else { + NodeSUnit->Latency = 0; + if (N->isTargetOpcode()) { + unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode()); + InstrStage *S = InstrItins.begin(SchedClass); + InstrStage *E = InstrItins.end(SchedClass); + for (; S != E; ++S) + NodeSUnit->Latency += S->Cycles; + } + for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) { + SDNode *FNode = NodeSUnit->FlaggedNodes[i]; + if (FNode->isTargetOpcode()) { + unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode()); + InstrStage *S = InstrItins.begin(SchedClass); + InstrStage *E = InstrItins.end(SchedClass); + for (; S != E; ++S) + NodeSUnit->Latency += S->Cycles; + } + } + } + } + + // Pass 2: add the preds, succs, etc. + for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { + SUnit *SU = &SUnits[su]; + SDNode *MainNode = SU->Node; + + if (MainNode->isTargetOpcode()) { + unsigned Opc = MainNode->getTargetOpcode(); + if (TII->isTwoAddrInstr(Opc)) { + SU->isTwoAddress = true; + SDNode *OpN = MainNode->getOperand(0).Val; + SUnit *OpSU = SUnitMap[OpN]; + if (OpSU) + OpSU->isDefNUseOperand = true; + } + } + + // Find all predecessors and successors of the group. + // Temporarily add N to make code simpler. + SU->FlaggedNodes.push_back(MainNode); + + for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) { + SDNode *N = SU->FlaggedNodes[n]; + + for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { + SDNode *OpN = N->getOperand(i).Val; + if (isPassiveNode(OpN)) continue; // Not scheduled. + SUnit *OpSU = SUnitMap[OpN]; + assert(OpSU && "Node has no SUnit!"); + if (OpSU == SU) continue; // In the same group. + + MVT::ValueType OpVT = N->getOperand(i).getValueType(); + assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); + bool isChain = OpVT == MVT::Other; + + if (SU->Preds.insert(std::make_pair(OpSU, isChain)).second) { + if (!isChain) { + SU->NumPreds++; + SU->NumPredsLeft++; + } else { + SU->NumChainPredsLeft++; + } + } + if (OpSU->Succs.insert(std::make_pair(SU, isChain)).second) { + if (!isChain) { + OpSU->NumSuccs++; + OpSU->NumSuccsLeft++; + } else { + OpSU->NumChainSuccsLeft++; + } + } + } + } + + // Remove MainNode from FlaggedNodes again. + SU->FlaggedNodes.pop_back(); + } + + return; +} + +static void CalculateDepths(SUnit *SU, unsigned Depth) { + if (Depth > SU->Depth) SU->Depth = Depth; + for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Succs.begin(), + E = SU->Succs.end(); I != E; ++I) + CalculateDepths(I->first, Depth+1); +} + +void ScheduleDAG::CalculateDepths() { + SUnit *Entry = SUnitMap[DAG.getEntryNode().Val]; + ::CalculateDepths(Entry, 0U); + for (unsigned i = 0, e = SUnits.size(); i != e; ++i) + if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) { + ::CalculateDepths(&SUnits[i], 0U); + } +} + +static void CalculateHeights(SUnit *SU, unsigned Height) { + if (Height > SU->Height) SU->Height = Height; + for (std::set<std::pair<SUnit*, bool> >::iterator I = SU->Preds.begin(), + E = SU->Preds.end(); I != E; ++I) + CalculateHeights(I->first, Height+1); +} +void ScheduleDAG::CalculateHeights() { + SUnit *Root = SUnitMap[DAG.getRoot().Val]; + ::CalculateHeights(Root, 0U); +} + /// CountResults - The results of target nodes have register or immediate /// operands first, then an optional chain, and optional flag operands (which do /// not go into the machine instrs.) @@ -348,6 +524,32 @@ void ScheduleDAG::EmitNoop() { TII->insertNoop(*BB, BB->end()); } +/// EmitSchedule - Emit the machine code in scheduled order. +void ScheduleDAG::EmitSchedule() { + std::map<SDNode*, unsigned> VRBaseMap; + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + if (SUnit *SU = Sequence[i]) { + for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++) + EmitNode(SU->FlaggedNodes[j], VRBaseMap); + EmitNode(SU->Node, VRBaseMap); + } else { + // Null SUnit* is a noop. + EmitNoop(); + } + } +} + +/// dump - dump the schedule. +void ScheduleDAG::dumpSchedule() const { + for (unsigned i = 0, e = Sequence.size(); i != e; i++) { + if (SUnit *SU = Sequence[i]) + SU->dump(&DAG); + else + std::cerr << "**** NOOP ****\n"; + } +} + + /// Run - perform scheduling. /// MachineBasicBlock *ScheduleDAG::Run() { @@ -360,4 +562,53 @@ MachineBasicBlock *ScheduleDAG::Run() { return BB; } +/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or +/// a group of nodes flagged together. +void SUnit::dump(const SelectionDAG *G) const { + std::cerr << "SU(" << NodeNum << "): "; + Node->dump(G); + std::cerr << "\n"; + if (FlaggedNodes.size() != 0) { + for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) { + std::cerr << " "; + FlaggedNodes[i]->dump(G); + std::cerr << "\n"; + } + } +} + +void SUnit::dumpAll(const SelectionDAG *G) const { + dump(G); + std::cerr << " # preds left : " << NumPredsLeft << "\n"; + std::cerr << " # succs left : " << NumSuccsLeft << "\n"; + std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n"; + std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n"; + std::cerr << " Latency : " << Latency << "\n"; + std::cerr << " Depth : " << Depth << "\n"; + std::cerr << " Height : " << Height << "\n"; + + if (Preds.size() != 0) { + std::cerr << " Predecessors:\n"; + for (std::set<std::pair<SUnit*,bool> >::const_iterator I = Preds.begin(), + E = Preds.end(); I != E; ++I) { + if (I->second) + std::cerr << " ch "; + else + std::cerr << " val "; + I->first->dump(G); + } + } + if (Succs.size() != 0) { + std::cerr << " Successors:\n"; + for (std::set<std::pair<SUnit*, bool> >::const_iterator I = Succs.begin(), + E = Succs.end(); I != E; ++I) { + if (I->second) + std::cerr << " ch "; + else + std::cerr << " val "; + I->first->dump(G); + } + } + std::cerr << "\n"; +} diff --git a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp index 7e87b525a0..34136d847c 100644 --- a/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp +++ b/lib/CodeGen/SelectionDAG/ScheduleDAGList.cpp @@ -7,10 +7,10 @@ // //===----------------------------------------------------------------------===// // -// This implements bottom-up and top-down list schedulers, using standard -// algorithms. The basic approach uses a priority queue of available nodes to -// schedule. One at a time, nodes are taken from the priority queue (thus in -// priority order), checked for legality to schedule, and emitted if legal. +// This implements a top-down list scheduler, using standard algorithms. +// The basic approach uses a priority queue of available nodes to schedule. +// One at a time, nodes are taken from the priority queue (thus in priority +// order), checked for legality to schedule, and emitted if legal. // // Nodes may not be legal to schedule either due to structural hazards (e.g. // pipeline or resource constraints) or because an input to the instruction has @@ -29,157 +29,20 @@ #include <climits> #include <iostream> #include <queue> -#include <set> -#include <vector> -#include "llvm/Support/CommandLine.h" using namespace llvm; namespace { - cl::opt<bool> SchedVertically("sched-vertically", cl::Hidden); - cl::opt<bool> SchedLowerDefNUse("sched-lower-defnuse", cl::Hidden); -} - -namespace { Statistic<> NumNoops ("scheduler", "Number of noops inserted"); Statistic<> NumStalls("scheduler", "Number of pipeline stalls"); - - /// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or - /// a group of nodes flagged together. - struct SUnit { - SDNode *Node; // Representative node. - std::vector<SDNode*> FlaggedNodes; // All nodes flagged to Node. - - // Preds/Succs - The SUnits before/after us in the graph. The boolean value - // is true if the edge is a token chain edge, false if it is a value edge. - std::set<std::pair<SUnit*,bool> > Preds; // All sunit predecessors. - std::set<std::pair<SUnit*,bool> > Succs; // All sunit successors. - - short NumPredsLeft; // # of preds not scheduled. - short NumSuccsLeft; // # of succs not scheduled. - short NumChainPredsLeft; // # of chain preds not scheduled. - short NumChainSuccsLeft; // # of chain succs not scheduled. - bool isTwoAddress : 1; // Is a two-address instruction. - bool isDefNUseOperand : 1; // Is a def&use operand. - bool isPending : 1; // True once pending. - bool isAvailable : 1; // True once available. - bool isScheduled : 1; // True once scheduled. - unsigned short Latency; // Node latency. - unsigned CycleBound; // Upper/lower cycle to be scheduled at. - unsigned Cycle; // Once scheduled, the cycle of the op. - unsigned NodeNum; // Entry # of node in the node vector. - - SUnit(SDNode *node, unsigned nodenum) - : Node(node), NumPredsLeft(0), NumSuccsLeft(0), - NumChainPredsLeft(0), NumChainSuccsLeft(0), - isTwoAddress(false), isDefNUseOperand(false), - isPending(false), isAvailable(false), isScheduled(false), - Latency(0), CycleBound(0), Cycle(0), NodeNum(nodenum) {} - - void dump(const SelectionDAG *G) const; - void dumpAll(const SelectionDAG *G) const; - }; -} - -void SUnit::dump(const SelectionDAG *G) const { - std::cerr << "SU(" << NodeNum << "): "; - Node->dump(G); - std::cerr << "\n"; - if (FlaggedNodes.size() != 0) { - for (unsigned i = 0, e = FlaggedNodes.size(); i != e; i++) { - std::cerr << " "; - FlaggedNodes[i]->dump(G); - std::cerr << "\n"; - } - } -} - -void SUnit::dumpAll(const SelectionDAG *G) const { - dump(G); - - std::cerr << " # preds left : " << NumPredsLeft << "\n"; - std::cerr << " # succs left : " << NumSuccsLeft << "\n"; - std::cerr << " # chain preds left : " << NumChainPredsLeft << "\n"; - std::cerr << " # chain succs left : " << NumChainSuccsLeft << "\n"; - std::cerr << " Latency : " << Latency << "\n"; - - if (Preds.size() != 0) { - std::cerr << " Predecessors:\n"; - for (std::set<std::pair<SUnit*,bool> >::const_iterator I = Preds.begin(), - E = Preds.end(); I != E; ++I) { - if (I->second) - std::cerr << " ch "; - else - std::cerr << " val "; - I->first->dump(G); - } - } - if (Succs.size() != 0) { - std::cerr << " Successors:\n"; - for (std::set<std::pair<SUnit*, bool> >::const_iterator I = Succs.begin(), - E = Succs.end(); I != E; ++I) { - if (I->second) - std::cerr << " ch "; - else - std::cerr << " val "; - I->first->dump(G); - } - } - std::cerr << "\n"; -} - -//===----------------------------------------------------------------------===// -/// SchedulingPriorityQueue - This interface is used to plug different -/// priorities computation algorithms into the list scheduler. It implements the -/// interface of a standard priority queue, where nodes are inserted in -/// arbitrary order and returned in priority order. The computation of the -/// priority and the representation of the queue are totally up to the -/// implementation to decide. -/// -namespace { -class SchedulingPriorityQueue { -public: - virtual ~SchedulingPriorityQueue() {} - - virtual void initNodes(const std::vector<SUnit> &SUnits) = 0; - virtual void releaseState() = 0; - - virtual bool empty() const = 0; - virtual void push(SUnit *U) = 0; - - virtual void push_all(const std::vector<SUnit *> &Nodes) = 0; - virtual SUnit *pop() = 0; - - virtual void RemoveFromPriorityQueue(SUnit *SU) = 0; - - /// ScheduledNode - As each node is scheduled, this method is invoked. This - /// allows the priority function to adjust the priority of node that have - /// already been emitted. - virtual void ScheduledNode(SUnit *Node) {} -}; } - - namespace { //===----------------------------------------------------------------------===// /// ScheduleDAGList - The actual list scheduler implementation. This supports -/// both top-down and bottom-up scheduling. +/// top-down scheduling. /// class ScheduleDAGList : public ScheduleDAG { private: - // SDNode to SUnit mapping (many to one). - std::map<SDNode*, SUnit*> SUnitMap; - - // The schedule. Null SUnit*'s represent noop instructions. - std::vector<SUnit*> Sequence; - - // The scheduling units. - std::vector<SUnit> SUnits; - - /// isBottomUp - This is true if the scheduling problem is bottom-up, false if - /// it is top-down. - bool isBottomUp; - /// AvailableQueue - The priority queue to use for the available SUnits. /// SchedulingPriorityQueue *AvailableQueue; @@ -194,20 +57,12 @@ private: /// HazardRec - The hazard recognizer to use. HazardRecognizer *HazardRec; - /// OpenNodes - Nodes with open live ranges, i.e. predecessors or successors - /// of scheduled nodes which are not themselves scheduled. - std::map<const TargetRegisterClass*, std::set<SUnit*> > OpenNodes; - - /// RegPressureLimits - Keep track of upper limit of register pressure for - /// each register class that allows the scheduler to go into vertical mode. - std::map<const TargetRegisterClass*, unsigned> RegPressureLimits; - public: ScheduleDAGList(SelectionDAG &dag, MachineBasicBlock *bb, - const TargetMachine &tm, bool isbottomup, + const TargetMachine &tm, SchedulingPriorityQueue *availqueue, HazardRecognizer *HR) - : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), + : ScheduleDAG(dag, bb, tm), AvailableQueue(availqueue), HazardRec(HR) { } @@ -218,202 +73,16 @@ public: void Schedule(); - void dumpSchedule() const; - private: - SUnit *NewSUnit(SDNode *N); - void ReleasePred(SUnit *PredSU, bool isChain, unsigned CurCycle); void ReleaseSucc(SUnit *SuccSU, bool isChain); - void ScheduleNodeBottomUp(SUnit *SU, unsigned& CurCycle, bool Veritical=true); - void ScheduleVertically(SUnit *SU, unsigned& CurCycle); void ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle); void ListScheduleTopDown(); - void ListScheduleBottomUp(); - void BuildSchedUnits(); - void EmitSchedule(); }; } // end anonymous namespace HazardRecognizer::~HazardRecognizer() {} -/// NewSUnit - Creates a new SUnit and return a ptr to it. -SUnit *ScheduleDAGList::NewSUnit(SDNode *N) { - SUnits.push_back(SUnit(N, SUnits.size())); - return &SUnits.back(); -} - -/// BuildSchedUnits - Build SUnits from the selection dag that we are input. -/// This SUnit graph is similar to the SelectionDAG, but represents flagged -/// together nodes with a single SUnit. -void ScheduleDAGList::BuildSchedUnits() { - // Reserve entries in the vector for each of the SUnits we are creating. This - // ensure that reallocation of the vector won't happen, so SUnit*'s won't get - // invalidated. - SUnits.reserve(std::distance(DAG.allnodes_begin(), DAG.allnodes_end())); - - const InstrItineraryData &InstrItins = TM.getInstrItineraryData(); - - for (SelectionDAG::allnodes_iterator NI = DAG.allnodes_begin(), - E = DAG.allnodes_end(); NI != E; ++NI) { - if (isPassiveNode(NI)) // Leaf node, e.g. a TargetImmediate. - continue; - - // If this node has already been processed, stop now. - if (SUnitMap[NI]) continue; - - SUnit *NodeSUnit = NewSUnit(NI); - - // See if anything is flagged to this node, if so, add them to flagged - // nodes. Nodes can have at most one flag input and one flag output. Flags - // are required the be the last operand and result of a node. - - // Scan up, adding flagged preds to FlaggedNodes. - SDNode *N = NI; - while (N->getNumOperands() && - N->getOperand(N->getNumOperands()-1).getValueType() == MVT::Flag) { - N = N->getOperand(N->getNumOperands()-1).Val; - NodeSUnit->FlaggedNodes.push_back(N); - SUnitMap[N] = NodeSUnit; - } - - // Scan down, adding this node and any flagged succs to FlaggedNodes if they - // have a user of the flag operand. - N = NI; - while (N->getValueType(N->getNumValues()-1) == MVT::Flag) { - SDOperand FlagVal(N, N->getNumValues()-1); - - // There are either zero or one users of the Flag result. - bool HasFlagUse = false; - for (SDNode::use_iterator UI = N->use_begin(), E = N->use_end(); - UI != E; ++UI) - if (FlagVal.isOperand(*UI)) { - HasFlagUse = true; - NodeSUnit->FlaggedNodes.push_back(N); - SUnitMap[N] = NodeSUnit; - N = *UI; - break; - } - if (!HasFlagUse) break; - } - - // Now all flagged nodes are in FlaggedNodes and N is the bottom-most node. - // Update the SUnit - NodeSUnit->Node = N; - SUnitMap[N] = NodeSUnit; - - // Compute the latency for the node. We use the sum of the latencies for - // all nodes flagged together into this SUnit. - if (InstrItins.isEmpty()) { - // No latency information. - NodeSUnit->Latency = 1; - } else { - NodeSUnit->Latency = 0; - if (N->isTargetOpcode()) { - unsigned SchedClass = TII->getSchedClass(N->getTargetOpcode()); - InstrStage *S = InstrItins.begin(SchedClass); - InstrStage *E = InstrItins.end(SchedClass); - for (; S != E; ++S) - NodeSUnit->Latency += S->Cycles; - } - for (unsigned i = 0, e = NodeSUnit->FlaggedNodes.size(); i != e; ++i) { - SDNode *FNode = NodeSUnit->FlaggedNodes[i]; - if (FNode->isTargetOpcode()) { - unsigned SchedClass = TII->getSchedClass(FNode->getTargetOpcode()); - InstrStage *S = InstrItins.begin(SchedClass); - InstrStage *E = InstrItins.end(SchedClass); - for (; S != E; ++S) - NodeSUnit->Latency += S->Cycles; - } - } - } - } - - // Pass 2: add the preds, succs, etc. - for (unsigned su = 0, e = SUnits.size(); su != e; ++su) { - SUnit *SU = &SUnits[su]; - SDNode *MainNode = SU->Node; - - if (MainNode->isTargetOpcode()) { - unsigned Opc = MainNode->getTargetOpcode(); - if (TII->isTwoAddrInstr(Opc)) { - SU->isTwoAddress = true; - SDNode *OpN = MainNode->getOperand(0).Val; - SUnit *OpSU = SUnitMap[OpN]; - if (OpSU) - OpSU->isDefNUseOperand = true; - } - } - - // Find all predecessors and successors of the group. - // Temporarily add N to make code simpler. - SU->FlaggedNodes.push_back(MainNode); - - for (unsigned n = 0, e = SU->FlaggedNodes.size(); n != e; ++n) { - SDNode *N = SU->FlaggedNodes[n]; - - for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { - SDNode *OpN = N->getOperand(i).Val; - if (isPassiveNode(OpN)) continue; // Not scheduled. - SUnit *OpSU = SUnitMap[OpN]; - assert(OpSU && "Node has no SUnit!"); - if (OpSU == SU) continue; // In the same group. - - MVT::ValueType OpVT = N->getOperand(i).getValueType(); - assert(OpVT != MVT::Flag && "Flagged nodes should be in same sunit!"); - bool isChain = OpVT == MVT::Other; - - if (SU->Preds.insert(std::make_pair(OpSU, isChain)).second) { - if (!isChain) { - SU->NumPredsLeft++; - } else { - SU->NumChainPredsLeft++; - } - } - if (OpSU->Succs.insert(std::make_pair(SU, isChain)).second) { - if (!isChain) { - OpSU->NumSuccsLeft++; - } else { - OpSU->NumChainSuccsLeft++; - } - } - } - } - - // Remove MainNode from FlaggedNodes again. - SU->FlaggedNodes.pop_back(); - } - - DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) - SUnits[su].dumpAll(&DAG)); - return; -} - -/// EmitSchedule - Emit the machine code in scheduled order. -void ScheduleDAGList::EmitSchedule() { - std::map<SDNode*, unsigned> VRBaseMap; - for (unsigned i = 0, e = Sequence.size(); i != e; i++) { - if (SUnit *SU = Sequence[i]) { - for (unsigned j = 0, ee = SU->FlaggedNodes.size(); j != ee; j++) - EmitNode(SU->FlaggedNodes[j], VRBaseMap); - EmitNode(SU->Node, VRBaseMap); - } else { - // Null SUnit* is a noop. - EmitNoop(); - } - } -} - -/// dump - dump the schedule. -void ScheduleDAGList::dumpSchedule() const { - for (unsigned i = 0, e = Sequence.size(); i != e; i++) { - if (SUnit *SU = Sequence[i]) - SU->dump(&DAG); - else - std::cerr << "**** NOOP ****\n"; - } -} - /// Schedule - Schedule the DAG using list scheduling. void ScheduleDAGList::Schedule() { DEBUG(std::cerr << "********** List Scheduling **********\n"); @@ -423,11 +92,7 @@ void ScheduleDAGList::Schedule() { AvailableQueue->initNodes(SUnits); - // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. - if (isBottomUp) - ListScheduleBottomUp(); - else - ListScheduleTopDown(); + ListScheduleTopDown(); AvailableQueue->releaseState(); @@ -440,273 +105,6 @@ void ScheduleDAGList::Schedule() { } //===----------------------------------------------------------------------===// -// Bottom-Up Scheduling -//===----------------------------------------------------------------------===// - -static const TargetRegisterClass *getRegClass(SUnit *SU, - const TargetInstrInfo *TII, - const MRegisterInfo *MRI, - SSARegMap *RegMap) { - if (SU->Node->isTargetOpcode()) { - unsigned Opc = SU->Node->getTargetOpcode(); - const TargetInstrDescriptor &II = TII->get(Opc); - return II.OpInfo->RegClass; - } else { - assert(SU->Node->getOpcode() == ISD::CopyFromReg); - unsigned SrcReg = cast<RegisterSDNode>(SU->Node->getOperand(1))->getReg(); - if (MRegisterInfo::isVirtualRegister(SrcReg)) - return RegMap->getRegClass(SrcReg); - else { - for (MRegisterInfo::regclass_iterator I = MRI->regclass_begin(), - E = MRI->regclass_end(); I != E; ++I) - if ((*I)->hasType(SU->Node->getValueType(0)) && - (*I)->contains(SrcReg)) - return *I; - assert(false && "Couldn't find register class for reg copy!"); - } - return NULL; - } -} - -static unsigned getNumResults(SUnit *SU) { - unsigned NumResults = 0; - for (unsigned i = 0, e = SU->Node->getNumValues(); i != e; ++i) { - MVT::ValueType VT = SU->Node->getValueType(i); - if (VT != MVT::Other && VT != MVT::Flag) - NumResults++; - } - return NumResults; -} - -/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to -/// the Available queue is the count reaches zero. Also update its cycle bound. -void ScheduleDAGList::ReleasePred(SUnit *PredSU, bool isChain, - unsigned CurCycle) { - // FIXME: the distance between two nodes is not always == the predecessor's - // latency. For example, the reader can very well read the register written - // by the predecessor later than the issue cycle. It also depends on the - // interrupt model (drain vs. freeze). - PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency); - - if (!isChain) - PredSU->NumSuccsLeft--; - else - PredSU->NumChainSuccsLeft--; - -#ifndef NDEBUG - if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) { - std::cerr << "*** List scheduling failed! ***\n"; - PredSU->dump(&DAG); - std::cerr << " has been released too many times!\n"; - assert(0); - } -#endif - - if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) { - // EntryToken has to go last! Special case it here. - if (PredSU->Node->getOpcode() != ISD::EntryToken) { - PredSU->isAvailable = true; - AvailableQueue->push(PredSU); - } - } - - if (getNumResults(PredSU) > 0) { - const TargetRegisterClass *RegClass = getRegClass(PredSU, TII, MRI, RegMap); - OpenNodes[ |