-
-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(NodeCount);
-
- const InstrItineraryData &InstrItins = TM.getInstrItineraryData();
-
- // Pass 1: create the SUnit's.
- for (unsigned i = 0, NC = NodeCount; i < NC; i++) {
- NodeInfo *NI = &Info[i];
- SDNode *N = NI->Node;
- if (isPassiveNode(N))
- continue;
-
- SUnit *SU;
- if (NI->isInGroup()) {
- if (NI != NI->Group->getBottom()) // Bottom up, so only look at bottom
- continue; // node of the NodeGroup
-
- SU = NewSUnit(N);
- // Find the flagged nodes.
- SDOperand FlagOp = N->getOperand(N->getNumOperands() - 1);
- SDNode *Flag = FlagOp.Val;
- unsigned ResNo = FlagOp.ResNo;
- while (Flag->getValueType(ResNo) == MVT::Flag) {
- NodeInfo *FNI = getNI(Flag);
- assert(FNI->Group == NI->Group);
- SU->FlaggedNodes.insert(SU->FlaggedNodes.begin(), Flag);
- SUnitMap[Flag] = SU;
-
- FlagOp = Flag->getOperand(Flag->getNumOperands() - 1);
- Flag = FlagOp.Val;
- ResNo = FlagOp.ResNo;
- }
- } else {
- SU = NewSUnit(N);
- }
- SUnitMap[N] = SU;
-
- // 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.
- SU->Latency = 1;
- } else {
- SU->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)
- SU->Latency += S->Cycles;
- }
- for (unsigned i = 0, e = SU->FlaggedNodes.size(); i != e; ++i) {
- SDNode *FNode = SU->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)
- SU->Latency += S->Cycles;
- }
- }
- }
- }
-
- // Pass 2: add the preds, succs, etc.
- for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
- SUnit *SU = &SUnits[i];
- SDNode *N = SU->Node;
- NodeInfo *NI = getNI(N);
-
- if (N->isTargetOpcode() && TII->isTwoAddrInstr(N->getTargetOpcode()))
- SU->isTwoAddress = true;
-
- if (NI->isInGroup()) {
- // Find all predecessors (of the group).
- NodeGroupOpIterator NGOI(NI);
- while (!NGOI.isEnd()) {
- SDOperand Op = NGOI.next();
- SDNode *OpN = Op.Val;
- MVT::ValueType VT = OpN->getValueType(Op.ResNo);
- NodeInfo *OpNI = getNI(OpN);
- if (OpNI->Group != NI->Group && !isPassiveNode(OpN)) {
- assert(VT != MVT::Flag);
- SUnit *OpSU = SUnitMap[OpN];
- if (VT == MVT::Other) {
- if (SU->ChainPreds.insert(OpSU).second)
- SU->NumChainPredsLeft++;
- if (OpSU->ChainSuccs.insert(SU).second)
- OpSU->NumChainSuccsLeft++;
- } else {
- if (SU->Preds.insert(OpSU).second)
- SU->NumPredsLeft++;
- if (OpSU->Succs.insert(SU).second)
- OpSU->NumSuccsLeft++;
- }
- }
- }
- } else {
- // Find node predecessors.
- for (unsigned j = 0, e = N->getNumOperands(); j != e; j++) {
- SDOperand Op = N->getOperand(j);
- SDNode *OpN = Op.Val;
- MVT::ValueType VT = OpN->getValueType(Op.ResNo);
- if (!isPassiveNode(OpN)) {
- assert(VT != MVT::Flag);
- SUnit *OpSU = SUnitMap[OpN];
- if (VT == MVT::Other) {
- if (SU->ChainPreds.insert(OpSU).second)
- SU->NumChainPredsLeft++;
- if (OpSU->ChainSuccs.insert(SU).second)
- OpSU->NumChainSuccsLeft++;
- } else {
- if (SU->Preds.insert(OpSU).second)
- SU->NumPredsLeft++;
- if (OpSU->Succs.insert(SU).second)
- OpSU->NumSuccsLeft++;
- if (j == 0 && SU->isTwoAddress)
- OpSU->isDefNUseOperand = true;
- }
- }
- }
- }
-
- DEBUG(SU->dumpAll(&DAG));
- }
-}
-
-/// EmitSchedule - Emit the machine code in scheduled order.
-void ScheduleDAGList::EmitSchedule() {
- 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++) {
- SDNode *N = SU->FlaggedNodes[j];
- EmitNode(getNI(N));
- }
- EmitNode(getNI(SU->Node));
- } 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.
-/// FIXME: Right now it only supports the burr (bottom up register reducing)
-/// heuristic.
-void ScheduleDAGList::Schedule() {
- DEBUG(std::cerr << "********** List Scheduling **********\n");
-
- // Build scheduling units.
- BuildSchedUnits();
-
- PriorityQueue->initNodes(SUnits);
-
- // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate.
- if (isBottomUp)
- ListScheduleBottomUp();
- else
- ListScheduleTopDown();
-
- PriorityQueue->releaseState();
-
- DEBUG(std::cerr << "*** Final schedule ***\n");
- DEBUG(dumpSchedule());
- DEBUG(std::cerr << "\n");
-
- // Emit in scheduled order
- EmitSchedule();
-}
-
-//===----------------------------------------------------------------------===//
-// RegReductionPriorityQueue Implementation
-//===----------------------------------------------------------------------===//
-//
-// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers
-// to reduce register pressure.
-//
-namespace {
- class RegReductionPriorityQueue;
-
- /// Sorting functions for the Available queue.
- struct ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> {
- RegReductionPriorityQueue *SPQ;
- ls_rr_sort(RegReductionPriorityQueue *spq) : SPQ(spq) {}
- ls_rr_sort(const ls_rr_sort &RHS) : SPQ(RHS.SPQ) {}
-
- bool operator()(const SUnit* left, const SUnit* right) const;
- };
-} // end anonymous namespace
-
-namespace {
- class RegReductionPriorityQueue : public SchedulingPriorityQueue {
- // SUnits - The SUnits for the current graph.
- const std::vector<SUnit> *SUnits;
-
- // SethiUllmanNumbers - The SethiUllman number for each node.
- std::vector<int> SethiUllmanNumbers;
-
- std::priority_queue<SUnit*, std::vector<SUnit*>, ls_rr_sort> Queue;
- public:
- RegReductionPriorityQueue() : Queue(ls_rr_sort(this)) {
- }
-
- void initNodes(const std::vector<SUnit> &sunits) {
- SUnits = &sunits;
- // Calculate node priorities.
- CalculatePriorities();
- }
- void releaseState() {
- SUnits = 0;
- SethiUllmanNumbers.clear();
- }
-
- unsigned getSethiUllmanNumber(unsigned NodeNum) const {
- assert(NodeNum < SethiUllmanNumbers.size());
- return SethiUllmanNumbers[NodeNum];
- }
-
- bool empty() const { return Queue.empty(); }
-
- void push(SUnit *U) {
- Queue.push(U);
- }
- SUnit *pop() {
- SUnit *V = Queue.top();
- Queue.pop();
- return V;
- }
- private:
- void CalculatePriorities();
- int CalcNodePriority(const SUnit *SU);
- };
-}
-
-bool ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const {
- unsigned LeftNum = left->NodeNum;
- unsigned RightNum = right->NodeNum;
-
- int LBonus = (int)left ->isDefNUseOperand;
- int RBonus = (int)right->isDefNUseOperand;
-
- // Special tie breaker: if two nodes share a operand, the one that
- // use it as a def&use operand is preferred.
- if (left->isTwoAddress && !right->isTwoAddress) {
- SDNode *DUNode = left->Node->getOperand(0).Val;
- if (DUNode->isOperand(right->Node))
- LBonus++;
- }
- if (!left->isTwoAddress && right->isTwoAddress) {
- SDNode *DUNode = right->Node->getOperand(0).Val;
- if (DUNode->isOperand(left->Node))
- RBonus++;
- }
-
- // Priority1 is just the number of live range genned.
- int LPriority1 = left ->NumPredsLeft - LBonus;
- int RPriority1 = right->NumPredsLeft - RBonus;
- int LPriority2 = SPQ->getSethiUllmanNumber(LeftNum) + LBonus;
- int RPriority2 = SPQ->getSethiUllmanNumber(RightNum) + RBonus;
-
- if (LPriority1 > RPriority1)
- return true;
- else if (LPriority1 == RPriority1)
- if (LPriority2 < RPriority2)
- return true;
- else if (LPriority2 == RPriority2)
- if (left->CycleBound > right->CycleBound)
- return true;
-
- return false;
-}
-
-
-/// CalcNodePriority - Priority is the Sethi Ullman number.
-/// Smaller number is the higher priority.
-int RegReductionPriorityQueue::CalcNodePriority(const SUnit *SU) {
- int &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum];
- if (SethiUllmanNumber != INT_MIN)
- return SethiUllmanNumber;
-
- if (SU->Preds.size() == 0) {
- SethiUllmanNumber = 1;
- } else {
- int Extra = 0;
- for (std::set<SUnit*>::const_iterator I = SU->Preds.begin(),
- E = SU->Preds.end(); I != E; ++I) {
- SUnit *PredSU = *I;
- int PredSethiUllman = CalcNodePriority(PredSU);
- if (PredSethiUllman > SethiUllmanNumber) {
- SethiUllmanNumber = PredSethiUllman;
- Extra = 0;
- } else if (PredSethiUllman == SethiUllmanNumber)
- Extra++;
- }
-
- if (SU->Node->getOpcode() != ISD::TokenFactor)
- SethiUllmanNumber += Extra;
- else
- SethiUllmanNumber = (Extra == 1) ? 0 : Extra-1;
- }
-
- return SethiUllmanNumber;
-}
-
-/// CalculatePriorities - Calculate priorities of all scheduling units.
-void RegReductionPriorityQueue::CalculatePriorities() {
- SethiUllmanNumbers.assign(SUnits->size(), INT_MIN);
-
- for (unsigned i = 0, e = SUnits->size(); i != e; ++i)
- CalcNodePriority(&(*SUnits)[i]);
-}
-