ScheduleDAGRRList.cpp revision 6e4c46cea5daef8bc807a36ce2ab9bb7f9855b67
1cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet//===----- ScheduleDAGList.cpp - Reg pressure reduction list scheduler ----===// 2cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// 3cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// The LLVM Compiler Infrastructure 4cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// 5cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// This file was developed by Evan Cheng and is distributed under the 6cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// University of Illinois Open Source License. See LICENSE.TXT for details. 7cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// 8cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet//===----------------------------------------------------------------------===// 9cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// 10cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// This implements bottom-up and top-down register pressure reduction list 11cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// schedulers, using standard algorithms. The basic approach uses a priority 12cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// queue of available nodes to schedule. One at a time, nodes are taken from 13cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// the priority queue (thus in priority order), checked for legality to 14cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// schedule, and emitted if legal. 15cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet// 16cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet//===----------------------------------------------------------------------===// 17cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 18cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet#define DEBUG_TYPE "pre-RA-sched" 19918aaa5717fce6081557c82ce1c439b6922737d5Xavier Ducrohet#include "llvm/CodeGen/ScheduleDAG.h" 20d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include "llvm/CodeGen/SchedulerRegistry.h" 21d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include "llvm/CodeGen/SSARegMap.h" 22b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet#include "llvm/Target/MRegisterInfo.h" 23cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet#include "llvm/Target/TargetData.h" 24d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include "llvm/Target/TargetMachine.h" 25d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include "llvm/Target/TargetInstrInfo.h" 26d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include "llvm/Support/Debug.h" 27d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include "llvm/Support/Compiler.h" 28cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet#include "llvm/ADT/SmallSet.h" 29b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet#include "llvm/ADT/Statistic.h" 30d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include <climits> 31d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#include <queue> 32cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet#include "llvm/Support/CommandLine.h" 33d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetusing namespace llvm; 34d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 35d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetstatic RegisterScheduler 36cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet burrListDAGScheduler("list-burr", 37d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet " Bottom-up register reduction list scheduling", 38cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet createBURRListDAGScheduler); 39cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohetstatic RegisterScheduler 40cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet tdrListrDAGScheduler("list-tdrr", 41cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet " Top-down register reduction list scheduling", 42d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet createTDRRListDAGScheduler); 43d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 44cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohetnamespace { 45cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet//===----------------------------------------------------------------------===// 46cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet/// ScheduleDAGRRList - The actual register reduction list scheduler 47cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet/// implementation. This supports both top-down and bottom-up scheduling. 48cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet/// 49cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohetclass VISIBILITY_HIDDEN ScheduleDAGRRList : public ScheduleDAG { 50d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetprivate: 51d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet /// isBottomUp - This is true if the scheduling problem is bottom-up, false if 52d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet /// it is top-down. 53cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet bool isBottomUp; 5420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 5520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet /// AvailableQueue - The priority queue to use for the available SUnits. 5620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet ///a 5720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SchedulingPriorityQueue *AvailableQueue; 58cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 59cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet /// LiveRegs / LiveRegDefs - A set of physical registers and their definition 60cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet /// that are "live". These nodes must be scheduled before any other nodes that 61cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet /// modifies the registers can be scheduled. 62cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SmallSet<unsigned, 4> LiveRegs; 63cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet std::vector<SUnit*> LiveRegDefs; 6420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet std::vector<unsigned> LiveRegCycles; 65d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 66d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetpublic: 67cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet ScheduleDAGRRList(SelectionDAG &dag, MachineBasicBlock *bb, 68cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet const TargetMachine &tm, bool isbottomup, 69cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SchedulingPriorityQueue *availqueue) 70cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet : ScheduleDAG(dag, bb, tm), isBottomUp(isbottomup), 71cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet AvailableQueue(availqueue) { 72d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 7320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 7420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet ~ScheduleDAGRRList() { 7520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet delete AvailableQueue; 7620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 7720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 78d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void Schedule(); 79d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 8020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohetprivate: 81d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void ReleasePred(SUnit*, bool, unsigned); 82d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void ReleaseSucc(SUnit*, bool isChain, unsigned); 83d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void CapturePred(SUnit*, SUnit*, bool); 84d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void ScheduleNodeBottomUp(SUnit*, unsigned); 85d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void ScheduleNodeTopDown(SUnit*, unsigned); 86d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void UnscheduleNodeBottomUp(SUnit*); 8720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet void BacktrackBottomUp(SUnit*, unsigned, unsigned&); 8820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SUnit *CopyAndMoveSuccessors(SUnit*); 8920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SUnit *InsertCopiesAndMoveSuccs(SUnit*, unsigned, 90d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet const TargetRegisterClass*, 91d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet const TargetRegisterClass*); 92d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet bool DelayForLiveRegsBottomUp(SUnit*, unsigned&); 93b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet void ListScheduleTopDown(); 94d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet void ListScheduleBottomUp(); 9520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet void CommuteNodesToReducePressure(); 9620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet}; 9720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet} // end anonymous namespace 9820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 9920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 10020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet/// Schedule - Schedule the DAG using list scheduling. 101d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetvoid ScheduleDAGRRList::Schedule() { 102d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet DOUT << "********** List Scheduling **********\n"; 103b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 10420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet LiveRegDefs.resize(MRI->getNumRegs(), NULL); 10520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet LiveRegCycles.resize(MRI->getNumRegs(), 0); 106b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 107b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // Build scheduling units. 108b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet BuildSchedUnits(); 109b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 110b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 111b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet SUnits[su].dumpAll(&DAG)); 112b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet CalculateDepths(); 113b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet CalculateHeights(); 11420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 115b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet AvailableQueue->initNodes(SUnitMap, SUnits); 116b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 117b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // Execute the actual scheduling loop Top-Down or Bottom-Up as appropriate. 118b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet if (isBottomUp) 11920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet ListScheduleBottomUp(); 12020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet else 121b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet ListScheduleTopDown(); 12220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 12320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet AvailableQueue->releaseState(); 12420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 125b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet CommuteNodesToReducePressure(); 12620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 127d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet DOUT << "*** Final schedule ***\n"; 128b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet DEBUG(dumpSchedule()); 129d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet DOUT << "\n"; 13020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 131d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Emit in scheduled order 132d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet EmitSchedule(); 133d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet} 134d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 135d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// CommuteNodesToReducePressure - If a node is two-address and commutable, and 136d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// it is not the last use of its first operand, add it to the CommuteSet if 137d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// possible. It will be commuted when it is translated to a MI. 138d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetvoid ScheduleDAGRRList::CommuteNodesToReducePressure() { 139d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SmallPtrSet<SUnit*, 4> OperandSeen; 140d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (unsigned i = Sequence.size()-1; i != 0; --i) { // Ignore first node. 141d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnit *SU = Sequence[i]; 142d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!SU || !SU->Node) continue; 14320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (SU->isCommutable) { 14420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet unsigned Opc = SU->Node->getTargetOpcode(); 14520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet unsigned NumRes = TII->getNumDefs(Opc); 14620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet unsigned NumOps = CountOperands(SU->Node); 14720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet for (unsigned j = 0; j != NumOps; ++j) { 14820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) == -1) 14920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet continue; 15020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 15120805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SDNode *OpN = SU->Node->getOperand(j).Val; 152d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnit *OpSU = SUnitMap[OpN][SU->InstanceNo]; 153b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet if (OpSU && OperandSeen.count(OpSU) == 1) { 154b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // Ok, so SU is not the last use of OpSU, but SU is two-address so 155b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // it will clobber OpSU. Try to commute SU if no other source operands 156b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // are live below. 15720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet bool DoCommute = true; 158d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (unsigned k = 0; k < NumOps; ++k) { 159d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (k != j) { 160d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet OpN = SU->Node->getOperand(k).Val; 161d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet OpSU = SUnitMap[OpN][SU->InstanceNo]; 162d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (OpSU && OperandSeen.count(OpSU) == 1) { 163d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet DoCommute = false; 164d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet break; 165d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 166d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 167d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 168b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet if (DoCommute) 169b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet CommuteSet.insert(SU->Node); 170b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet } 171b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 172b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // Only look at the first use&def node for now. 173b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet break; 174a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 175a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 176a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet 177a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 178a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet I != E; ++I) { 179a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet if (!I->isCtrl) 180a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet OperandSeen.insert(I->Dep); 181a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 182a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 183a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet} 184a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet 185a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet//===----------------------------------------------------------------------===// 186a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet// Bottom-Up Scheduling 187a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet//===----------------------------------------------------------------------===// 188a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet 189a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 190a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 191a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohetvoid ScheduleDAGRRList::ReleasePred(SUnit *PredSU, bool isChain, 192a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet unsigned CurCycle) { 193a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet // FIXME: the distance between two nodes is not always == the predecessor's 194a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet // latency. For example, the reader can very well read the register written 195a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet // by the predecessor later than the issue cycle. It also depends on the 196a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet // interrupt model (drain vs. freeze). 197d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency); 198d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 199cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (!isChain) 200b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet --PredSU->NumSuccsLeft; 201d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet else 202b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet --PredSU->NumChainSuccsLeft; 203d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 204d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#ifndef NDEBUG 205d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (PredSU->NumSuccsLeft < 0 || PredSU->NumChainSuccsLeft < 0) { 206d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet cerr << "*** List scheduling failed! ***\n"; 207d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet PredSU->dump(&DAG); 208d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet cerr << " has been released too many times!\n"; 209b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet assert(0); 210d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 211b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet#endif 212b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 213d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if ((PredSU->NumSuccsLeft + PredSU->NumChainSuccsLeft) == 0) { 214d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // EntryToken has to go last! Special case it here. 215d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!PredSU->Node || PredSU->Node->getOpcode() != ISD::EntryToken) { 216d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet PredSU->isAvailable = true; 217d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->push(PredSU); 218d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 219d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 220cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet} 221d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 222d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 223d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// count of its predecessors. If a predecessor pending count is zero, add it to 224d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// the Available queue. 225d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetvoid ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 226d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet DOUT << "*** Scheduling [" << CurCycle << "]: "; 227cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet DEBUG(SU->dump(&DAG)); 228d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SU->Cycle = CurCycle; 229d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 230d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->ScheduledNode(SU); 231d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 232d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Bottom up: release predecessors 233d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 234d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet I != E; ++I) { 235d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet ReleasePred(I->Dep, I->isCtrl, CurCycle); 236d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (I->Cost < 0) { 237d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // This is a physical register dependency and it's impossible or 238d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // expensive to copy the register. Make sure nothing that can 239d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // clobber the register is scheduled between the predecessor and 240d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // this node. 241d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (LiveRegs.insert(I->Reg)) { 242d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegDefs[I->Reg] = I->Dep; 243d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegCycles[I->Reg] = CurCycle; 244d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 245d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 246d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 247cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 248cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // Release all the implicit physical register defs that are live. 249cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 250cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet I != E; ++I) { 251cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (I->Cost < 0) { 252cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (LiveRegCycles[I->Reg] == I->Dep->Cycle) { 253d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegs.erase(I->Reg); 254cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet assert(LiveRegDefs[I->Reg] == SU && 255cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet "Physical register dependency violated?"); 256d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegDefs[I->Reg] = NULL; 257d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegCycles[I->Reg] = 0; 25820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 259d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 260d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 261d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 262d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SU->isScheduled = true; 263d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet} 264d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 265d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// CapturePred - This does the opposite of ReleasePred. Since SU is being 266d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// unscheduled, incrcease the succ left count of its predecessors. Remove 267d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// them from AvailableQueue if necessary. 268d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetvoid ScheduleDAGRRList::CapturePred(SUnit *PredSU, SUnit *SU, bool isChain) { 269d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet PredSU->CycleBound = 0; 270d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (SUnit::succ_iterator I = PredSU->Succs.begin(), E = PredSU->Succs.end(); 271d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet I != E; ++I) { 272d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (I->Dep == SU) 273d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet continue; 274d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet PredSU->CycleBound = std::max(PredSU->CycleBound, 275d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet I->Dep->Cycle + PredSU->Latency); 276d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 277d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 278d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (PredSU->isAvailable) { 279d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet PredSU->isAvailable = false; 280d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!PredSU->isPending) 281d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->remove(PredSU); 282d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 283d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 284d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!isChain) 285d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet ++PredSU->NumSuccsLeft; 286d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet else 287d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet ++PredSU->NumChainSuccsLeft; 288d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet} 28920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 290d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// UnscheduleNodeBottomUp - Remove the node from the schedule, update its and 291d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// its predecessor states to reflect the change. 29220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohetvoid ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) { 29320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet DOUT << "*** Unscheduling [" << SU->Cycle << "]: "; 294d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet DEBUG(SU->dump(&DAG)); 295d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 296d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->UnscheduledNode(SU); 297d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 298d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 299d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet I != E; ++I) { 300d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet CapturePred(I->Dep, SU, I->isCtrl); 301d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (I->Cost < 0 && SU->Cycle == LiveRegCycles[I->Reg]) { 30220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet LiveRegs.erase(I->Reg); 30320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet assert(LiveRegDefs[I->Reg] == I->Dep && 30420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet "Physical register dependency violated?"); 305d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegDefs[I->Reg] = NULL; 306d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegCycles[I->Reg] = 0; 307d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 308d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 309d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 310d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 311d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet I != E; ++I) { 312d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (I->Cost < 0) { 313d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (LiveRegs.insert(I->Reg)) { 314d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet assert(!LiveRegDefs[I->Reg] && 31520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet "Physical register dependency violated?"); 316d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegDefs[I->Reg] = SU; 317a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 318a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet if (I->Dep->Cycle < LiveRegCycles[I->Reg]) 319a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet LiveRegCycles[I->Reg] = I->Dep->Cycle; 320a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 321d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 322d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 323d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SU->Cycle = 0; 324d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SU->isScheduled = false; 325d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SU->isAvailable = true; 326d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->push(SU); 32720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet} 32820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 329d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet// FIXME: This is probably too slow! 330d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetstatic void isReachable(SUnit *SU, SUnit *TargetSU, 331d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SmallPtrSet<SUnit*, 32> &Visited, bool &Reached) { 332d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (Reached) return; 333d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (SU == TargetSU) { 334d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet Reached = true; 33520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet return; 33620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 337d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!Visited.insert(SU)) return; 338d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 339d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); I != E; 340d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet ++I) 341d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet isReachable(I->Dep, TargetSU, Visited, Reached); 342d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet} 343d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 34420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohetstatic bool isReachable(SUnit *SU, SUnit *TargetSU) { 345d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SmallPtrSet<SUnit*, 32> Visited; 346d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet bool Reached = false; 347d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet isReachable(SU, TargetSU, Visited, Reached); 348cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet return Reached; 349cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet} 350cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 351d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// willCreateCycle - Returns true if adding an edge from SU to TargetSU will 352d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// create a cycle. 353cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohetstatic bool willCreateCycle(SUnit *SU, SUnit *TargetSU) { 354cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (isReachable(TargetSU, SU)) 355cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet return true; 356cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 357cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet I != E; ++I) 358cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (I->Cost < 0 && isReachable(TargetSU, I->Dep)) 359cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet return true; 360cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet return false; 361cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet} 362cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 363cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet/// BacktrackBottomUp - Backtrack scheduling to a previous cycle specified in 364cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet/// BTCycle in order to schedule a specific node. Returns the last unscheduled 365cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet/// SUnit. Also returns if a successor is unscheduled in the process. 366cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohetvoid ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, unsigned BtCycle, 367cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet unsigned &CurCycle) { 368cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SUnit *OldSU = NULL; 369cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet while (CurCycle > BtCycle) { 370cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet OldSU = Sequence.back(); 371cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet Sequence.pop_back(); 372cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (SU->isSucc(OldSU)) 373cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // Don't try to remove SU from AvailableQueue. 374cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SU->isAvailable = false; 375cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet UnscheduleNodeBottomUp(OldSU); 376cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet --CurCycle; 377cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 378cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 379cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 380cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (SU->isSucc(OldSU)) { 381cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet assert(false && "Something is wrong!"); 382cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet abort(); 383cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 384cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet} 385cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 386b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet/// isSafeToCopy - True if the SUnit for the given SDNode can safely cloned, 387d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// i.e. the node does not produce a flag, it does not read a flag and it does 388d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// not have an incoming chain. 389b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohetstatic bool isSafeToCopy(SDNode *N) { 390d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!N) 391d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet return true; 392cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 393b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) 394cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (N->getValueType(i) == MVT::Flag) 395b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet return false; 396a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 397b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet const SDOperand &Op = N->getOperand(i); 398a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet MVT::ValueType VT = Op.Val->getValueType(Op.ResNo); 399a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet if (VT == MVT::Other || VT == MVT::Flag) 4000831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet return false; 4010831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet } 4020831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet 403a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet return true; 4040831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet} 4050831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet 4060831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 407a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet/// successors to the newly created node. 4080831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier DucrohetSUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) { 4090831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; 4100831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet 4110831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet SUnit *NewSU = Clone(SU); 4120831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet 4130831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet // New SUnit has the exact same predecessors. 4140831b3fae504e8fa94e6b1cc0d4e6c3fccaef231Xavier Ducrohet for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 415cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet I != E; ++I) 416cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (!I->isSpecial) { 417cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet NewSU->addPred(I->Dep, I->isCtrl, false, I->Reg, I->Cost); 418cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1); 419d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 420d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 421d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Only copy scheduled successors. Cut them from old node's successor 422d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // list and move them over. 423cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SmallVector<SDep*, 2> DelDeps; 424cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 425cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet I != E; ++I) { 426cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (I->isSpecial) 427cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet continue; 428cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1); 429cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (I->Dep->isScheduled) { 430cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet I->Dep->addPred(NewSU, I->isCtrl, false, I->Reg, I->Cost); 431cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet DelDeps.push_back(I); 432d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 433d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 434d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 435d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnit *Succ = DelDeps[i]->Dep; 436cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet bool isCtrl = DelDeps[i]->isCtrl; 437cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet Succ->removePred(SU, isCtrl, false); 438cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 439cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 440cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet AvailableQueue->updateNode(SU); 441cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet AvailableQueue->addNode(NewSU); 442cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 443cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet return NewSU; 444cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet} 445d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 446d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// InsertCopiesAndMoveSuccs - Insert expensive cross register class copies and 447d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// move all scheduled successors of the given SUnit to the last copy. 448d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier DucrohetSUnit *ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 449cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet const TargetRegisterClass *DestRC, 450cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet const TargetRegisterClass *SrcRC) { 451cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SUnit *CopyFromSU = NewSUnit(NULL); 452cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet CopyFromSU->CopySrcRC = SrcRC; 453cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet CopyFromSU->CopyDstRC = DestRC; 454cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet CopyFromSU->Depth = SU->Depth; 455cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet CopyFromSU->Height = SU->Height; 456cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 457cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SUnit *CopyToSU = NewSUnit(NULL); 458d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet CopyToSU->CopySrcRC = DestRC; 459d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet CopyToSU->CopyDstRC = SrcRC; 460d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 461cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // Only copy scheduled successors. Cut them from old node's successor 462cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // list and move them over. 463cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SmallVector<SDep*, 2> DelDeps; 464cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 465cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet I != E; ++I) { 466cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (I->isSpecial) 467cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet continue; 468cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet CopyToSU->Height = std::max(CopyToSU->Height, I->Dep->Height+1); 469cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (I->Dep->isScheduled) { 470d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet I->Dep->addPred(CopyToSU, I->isCtrl, false, I->Reg, I->Cost); 471d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet DelDeps.push_back(I); 472d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 473d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 474cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 475cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SUnit *Succ = DelDeps[i]->Dep; 476cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet bool isCtrl = DelDeps[i]->isCtrl; 477cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet Succ->removePred(SU, isCtrl, false); 478cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 479cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 480cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet CopyFromSU->addPred(SU, false, false, Reg, -1); 481cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet CopyToSU->addPred(CopyFromSU, false, false, Reg, 1); 482b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet 483a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet AvailableQueue->updateNode(SU); 484a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet AvailableQueue->addNode(CopyFromSU); 485a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet AvailableQueue->addNode(CopyToSU); 486a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet 487a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet return CopyToSU; 488a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet} 489a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet 490a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet/// getPhysicalRegisterVT - Returns the ValueType of the physical register 491a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet/// definition of the specified node. 492a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet/// FIXME: Move to SelectionDAG? 493a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohetstatic MVT::ValueType getPhysicalRegisterVT(SDNode *N, unsigned Reg, 494a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet const TargetInstrInfo *TII) { 495b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet const TargetInstrDescriptor &TID = TII->get(N->getTargetOpcode()); 496a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 497b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet unsigned NumRes = TID.numDefs; 498b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet for (const unsigned *ImpDef = TID.ImplicitDefs; *ImpDef; ++ImpDef) { 499b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet if (Reg == *ImpDef) 500b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet break; 501b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet ++NumRes; 502cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 503b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet return N->getValueType(NumRes); 504cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet} 505b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet 506b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 507d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// scheduling of the given node to satisfy live physical register dependencies. 508a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet/// If the specific node is the last one that's available to schedule, do 509d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// whatever is necessary (i.e. backtracking or cloning) to make it possible. 510d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetbool ScheduleDAGRRList::DelayForLiveRegsBottomUp(SUnit *SU, unsigned &CurCycle){ 511d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (LiveRegs.empty()) 512a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet return false; 513a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet 514cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // If this node would clobber any "live" register, then it's not ready. 515b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet // However, if this is the last "available" node, then we may have to 516b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet // backtrack. 517b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet bool MustSched = AvailableQueue->empty(); 518cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SmallVector<unsigned, 4> LRegs; 519cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 520cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet I != E; ++I) { 521cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (I->Cost < 0) { 522cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet unsigned Reg = I->Reg; 523cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (LiveRegs.count(Reg) && LiveRegDefs[Reg] != I->Dep) 524cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet LRegs.push_back(Reg); 525b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet for (const unsigned *Alias = MRI->getAliasSet(Reg); 526b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet *Alias; ++Alias) 527b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != I->Dep) 528b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet LRegs.push_back(*Alias); 529a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 530a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet } 531a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet 532cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) { 533d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SDNode *Node = (i == 0) ? SU->Node : SU->FlaggedNodes[i-1]; 534d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!Node || !Node->isTargetOpcode()) 535d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet continue; 536cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet const TargetInstrDescriptor &TID = TII->get(Node->getTargetOpcode()); 537cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (!TID.ImplicitDefs) 538cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet continue; 539cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) { 540cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (LiveRegs.count(*Reg) && LiveRegDefs[*Reg] != SU) 541cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet LRegs.push_back(*Reg); 542cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (const unsigned *Alias = MRI->getAliasSet(*Reg); 543cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet *Alias; ++Alias) 544cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (LiveRegs.count(*Alias) && LiveRegDefs[*Alias] != SU) 545cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet LRegs.push_back(*Alias); 546cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 547cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 548cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 549cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (MustSched && !LRegs.empty()) { 550cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // We have made a mistake by scheduling some nodes too early. Now we must 551cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // schedule the current node which will end up clobbering some live 552cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // registers that are expensive / impossible to copy. Try unscheduling 553cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // up to the point where it's safe to schedule the current node. 554cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet unsigned LiveCycle = CurCycle; 555cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet for (unsigned i = 0, e = LRegs.size(); i != e; ++i) { 556d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet unsigned Reg = LRegs[i]; 557d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet unsigned LCycle = LiveRegCycles[Reg]; 558d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveCycle = std::min(LiveCycle, LCycle); 559d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 560d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 561d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnit *OldSU = Sequence[LiveCycle]; 562d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!willCreateCycle(SU, OldSU)) { 563b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // If CycleBound is greater than backtrack cycle, then some of SU 564d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // successors are going to be unscheduled. 565d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet bool SuccUnsched = SU->CycleBound > LiveCycle; 566d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet BacktrackBottomUp(SU, LiveCycle, CurCycle); 567d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Force the current node to be scheduled before the node that 568d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // requires the physical reg dep. 569d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (OldSU->isAvailable) { 570d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet OldSU->isAvailable = false; 571d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->remove(OldSU); 572d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 573d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SU->addPred(OldSU, true, true); 574b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // If a successor has been unscheduled, then it's not possible to 575d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // schedule the current node. 576b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet return SuccUnsched; 577b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet } else { 57820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // Try duplicating the nodes that produces these "expensive to copy" 57920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // values to break the dependency. 58020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet assert(LRegs.size() == 1 && "Can't handle this yet!"); 58120805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet unsigned Reg = LRegs[0]; 58220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SUnit *LRDef = LiveRegDefs[Reg]; 58320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SUnit *NewDef; 584d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (isSafeToCopy(LRDef->Node)) 58520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet NewDef = CopyAndMoveSuccessors(LRDef); 58620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet else { 58720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // Issue expensive cross register class copies. 58820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet MVT::ValueType VT = getPhysicalRegisterVT(LRDef->Node, Reg, TII); 58920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet const TargetRegisterClass *RC = 59020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet MRI->getPhysicalRegisterRegClass(VT, Reg); 59120805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet const TargetRegisterClass *DestRC = MRI->getCrossCopyRegClass(RC); 59220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (!DestRC) { 593b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet assert(false && "Don't know how to copy this physical register!"); 59420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet abort(); 59520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 59620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet NewDef = InsertCopiesAndMoveSuccs(LRDef,Reg,DestRC,RC); 59720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 59820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 59920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet DOUT << "Adding an edge from SU # " << SU->NodeNum 600d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet << " to SU #" << NewDef->NodeNum << "\n"; 601d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet LiveRegDefs[Reg] = NewDef; 602d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet NewDef->addPred(SU, true, true); 603d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SU->isAvailable = false; 604b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet AvailableQueue->push(NewDef); 605d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet return true; 606d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 607d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 608d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet return !LRegs.empty(); 609b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet} 610d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 611d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 612d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// schedulers. 613d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetvoid ScheduleDAGRRList::ListScheduleBottomUp() { 614b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet unsigned CurCycle = 0; 615d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Add root to Available queue. 616d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnit *RootSU = SUnitMap[DAG.getRoot().Val].front(); 617d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet RootSU->isAvailable = true; 618d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->push(RootSU); 619d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 620d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // While Available queue is not empty, grab the node with the highest 621cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // priority. If it is not ready put it back. Schedule the node. 622cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet SmallVector<SUnit*, 4> NotReady; 623d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet while (!AvailableQueue->empty()) { 62420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SUnit *CurSU = AvailableQueue->pop(); 62520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet while (CurSU) { 62620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (CurSU->CycleBound <= CurCycle) 62720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (!DelayForLiveRegsBottomUp(CurSU, CurCycle)) 62820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet break; 62920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 63020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // Verify node is still ready. It may not be in case the 63120805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // scheduler has backtracked. 63220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (CurSU->isAvailable) { 63320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet CurSU->isPending = true; 63420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet NotReady.push_back(CurSU); 63520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 636d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet CurSU = AvailableQueue->pop(); 637d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 638d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 639d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Add the nodes that aren't ready back onto the available list. 640d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 641cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet NotReady[i]->isPending = false; 64220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (NotReady[i]->isAvailable) 643d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->push(NotReady[i]); 644d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 645d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet NotReady.clear(); 646d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 647cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (!CurSU) 648cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet Sequence.push_back(0); 649cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet else { 65020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet ScheduleNodeBottomUp(CurSU, CurCycle); 651d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet Sequence.push_back(CurSU); 652d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 653a7cac5e0542779cadf0f5ccf71584e4b4425f7a6Xavier Ducrohet ++CurCycle; 654d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 655cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 656cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // Add entry node last 657cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet if (DAG.getEntryNode().Val != DAG.getRoot().Val) { 658d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front(); 659d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet Sequence.push_back(Entry); 660cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet } 661cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 662cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet // Reverse the order if it is bottom up. 663cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet std::reverse(Sequence.begin(), Sequence.end()); 664cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohet 66520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 66620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet#ifndef NDEBUG 66720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // Verify that all SUnits were scheduled. 66820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet bool AnyNotSched = false; 66920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 67020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (SUnits[i].NumSuccsLeft != 0 || SUnits[i].NumChainSuccsLeft != 0) { 67120805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (!AnyNotSched) 67220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet cerr << "*** List scheduling failed! ***\n"; 67320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SUnits[i].dump(&DAG); 67420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet cerr << "has not been scheduled!\n"; 67520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet AnyNotSched = true; 67620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 67720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet } 67820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet assert(!AnyNotSched); 67920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet#endif 68020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet} 68120805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 68220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet//===----------------------------------------------------------------------===// 68320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet// Top-Down Scheduling 68420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet//===----------------------------------------------------------------------===// 68520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 68620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet/// ReleaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 68720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 68820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohetvoid ScheduleDAGRRList::ReleaseSucc(SUnit *SuccSU, bool isChain, 68920805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet unsigned CurCycle) { 69020805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // FIXME: the distance between two nodes is not always == the predecessor's 69120805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // latency. For example, the reader can very well read the register written 69220805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // by the predecessor later than the issue cycle. It also depends on the 69320805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet // interrupt model (drain vs. freeze). 69420805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet SuccSU->CycleBound = std::max(SuccSU->CycleBound, CurCycle + SuccSU->Latency); 69520805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet 69620805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet if (!isChain) 69720805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet --SuccSU->NumPredsLeft; 69820805343296eef04081fee82fd04547f51225fe3Xavier Ducrohet else 699d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet --SuccSU->NumChainPredsLeft; 700d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 701d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#ifndef NDEBUG 702d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (SuccSU->NumPredsLeft < 0 || SuccSU->NumChainPredsLeft < 0) { 703d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet cerr << "*** List scheduling failed! ***\n"; 704b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet SuccSU->dump(&DAG); 705d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet cerr << " has been released too many times!\n"; 706d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet assert(0); 707d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 708d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#endif 709d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 710d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if ((SuccSU->NumPredsLeft + SuccSU->NumChainPredsLeft) == 0) { 711d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SuccSU->isAvailable = true; 712d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->push(SuccSU); 713d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 714d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet} 715d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 716d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 717d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// ScheduleNodeTopDown - Add the node to the schedule. Decrement the pending 718d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// count of its successors. If a successor pending count is zero, add it to 719d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// the Available queue. 720d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetvoid ScheduleDAGRRList::ScheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 721d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet DOUT << "*** Scheduling [" << CurCycle << "]: "; 722d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet DEBUG(SU->dump(&DAG)); 723d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet SU->Cycle = CurCycle; 724d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet 725d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet AvailableQueue->ScheduledNode(SU); 726d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet 727d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet // Top down: release successors 728d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 729d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet I != E; ++I) 730d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet ReleaseSucc(I->Dep, I->isCtrl, CurCycle); 731918aaa5717fce6081557c82ce1c439b6922737d5Xavier Ducrohet SU->isScheduled = true; 732d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet} 73351a7e5447de94791c464cda5cc6ebbf616d73c80Xavier Ducrohet 734d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// ListScheduleTopDown - The main loop of list scheduling for top-down 735d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet/// schedulers. 736d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohetvoid ScheduleDAGRRList::ListScheduleTopDown() { 737d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet unsigned CurCycle = 0; 738d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnit *Entry = SUnitMap[DAG.getEntryNode().Val].front(); 739d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 740d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // All leaves to Available queue. 741d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 742b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet // It is available if it has no predecessors. 743b44b43b1579486ff7ecd0f7528f17711acdeae98Xavier Ducrohet if (SUnits[i].Preds.size() == 0 && &SUnits[i] != Entry) { 744d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AvailableQueue->push(&SUnits[i]); 745d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnits[i].isAvailable = true; 746d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 747d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 748d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 749d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Emit the entry node first. 750b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet ScheduleNodeTopDown(Entry, CurCycle); 751b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet Sequence.push_back(Entry); 752b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet ++CurCycle; 753b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 754b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet // While Available queue is not empty, grab the node with the highest 755d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet // priority. If it is not ready put it back. Schedule the node. 756d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet std::vector<SUnit*> NotReady; 757d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet while (!AvailableQueue->empty()) { 758d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet SUnit *CurSU = AvailableQueue->pop(); 759d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet while (CurSU && CurSU->CycleBound > CurCycle) { 760d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet NotReady.push_back(CurSU); 761d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet CurSU = AvailableQueue->pop(); 762d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet } 763d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 764d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet // Add the nodes that aren't ready back onto the available list. 765918aaa5717fce6081557c82ce1c439b6922737d5Xavier Ducrohet AvailableQueue->push_all(NotReady); 766d43909c7503e11eb335a452d296a10804bb01fd6Xavier Ducrohet NotReady.clear(); 76751a7e5447de94791c464cda5cc6ebbf616d73c80Xavier Ducrohet 768d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!CurSU) 769d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet Sequence.push_back(0); 770d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet else { 771b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet ScheduleNodeTopDown(CurSU, CurCycle); 772b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet Sequence.push_back(CurSU); 773b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet } 774b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet CurCycle++; 775b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet } 776b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 777b1da1afa7418960b650780250bbd34c81af61aa3Xavier Ducrohet 778d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#ifndef NDEBUG 779d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet // Verify that all SUnits were scheduled. 780d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet bool AnyNotSched = false; 781d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 782d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!SUnits[i].isScheduled) { 783d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet if (!AnyNotSched) 784d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet cerr << "*** List scheduling failed! ***\n"; 785d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet SUnits[i].dump(&DAG); 786d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet cerr << "has not been scheduled!\n"; 787d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet AnyNotSched = true; 788d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 789d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet } 790d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet assert(!AnyNotSched); 791d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet#endif 792d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet} 793d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 794d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 795d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet 796d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet//===----------------------------------------------------------------------===// 797d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet// RegReductionPriorityQueue Implementation 798d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet//===----------------------------------------------------------------------===// 799d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet// 800d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet// This is a SchedulingPriorityQueue that schedules using Sethi Ullman numbers 801d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet// to reduce register pressure. 802d38e776a3cc8cb53945cbebafbe6f6c2e3501fa5Xavier Ducrohet// 803cfdc784b6cdcbbb2bf2ba4d53d9a9eb2c37278a3Xavier Ducrohetnamespace { 804 template<class SF> 805 class RegReductionPriorityQueue; 806 807 /// Sorting functions for the Available queue. 808 struct bu_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 809 RegReductionPriorityQueue<bu_ls_rr_sort> *SPQ; 810 bu_ls_rr_sort(RegReductionPriorityQueue<bu_ls_rr_sort> *spq) : SPQ(spq) {} 811 bu_ls_rr_sort(const bu_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 812 813 bool operator()(const SUnit* left, const SUnit* right) const; 814 }; 815 816 struct td_ls_rr_sort : public std::binary_function<SUnit*, SUnit*, bool> { 817 RegReductionPriorityQueue<td_ls_rr_sort> *SPQ; 818 td_ls_rr_sort(RegReductionPriorityQueue<td_ls_rr_sort> *spq) : SPQ(spq) {} 819 td_ls_rr_sort(const td_ls_rr_sort &RHS) : SPQ(RHS.SPQ) {} 820 821 bool operator()(const SUnit* left, const SUnit* right) const; 822 }; 823} // end anonymous namespace 824 825static inline bool isCopyFromLiveIn(const SUnit *SU) { 826 SDNode *N = SU->Node; 827 return N && N->getOpcode() == ISD::CopyFromReg && 828 N->getOperand(N->getNumOperands()-1).getValueType() != MVT::Flag; 829} 830 831namespace { 832 template<class SF> 833 class VISIBILITY_HIDDEN RegReductionPriorityQueue 834 : public SchedulingPriorityQueue { 835 std::priority_queue<SUnit*, std::vector<SUnit*>, SF> Queue; 836 837 public: 838 RegReductionPriorityQueue() : 839 Queue(SF(this)) {} 840 841 virtual void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 842 std::vector<SUnit> &sunits) {} 843 844 virtual void addNode(const SUnit *SU) {} 845 846 virtual void updateNode(const SUnit *SU) {} 847 848 virtual void releaseState() {} 849 850 virtual unsigned getNodePriority(const SUnit *SU) const { 851 return 0; 852 } 853 854 unsigned size() const { return Queue.size(); } 855 856 bool empty() const { return Queue.empty(); } 857 858 void push(SUnit *U) { 859 Queue.push(U); 860 } 861 void push_all(const std::vector<SUnit *> &Nodes) { 862 for (unsigned i = 0, e = Nodes.size(); i != e; ++i) 863 Queue.push(Nodes[i]); 864 } 865 866 SUnit *pop() { 867 if (empty()) return NULL; 868 SUnit *V = Queue.top(); 869 Queue.pop(); 870 return V; 871 } 872 873 /// remove - This is a really inefficient way to remove a node from a 874 /// priority queue. We should roll our own heap to make this better or 875 /// something. 876 void remove(SUnit *SU) { 877 std::vector<SUnit*> Temp; 878 879 assert(!Queue.empty() && "Not in queue!"); 880 while (Queue.top() != SU) { 881 Temp.push_back(Queue.top()); 882 Queue.pop(); 883 assert(!Queue.empty() && "Not in queue!"); 884 } 885 886 // Remove the node from the PQ. 887 Queue.pop(); 888 889 // Add all the other nodes back. 890 for (unsigned i = 0, e = Temp.size(); i != e; ++i) 891 Queue.push(Temp[i]); 892 } 893 }; 894 895 template<class SF> 896 class VISIBILITY_HIDDEN BURegReductionPriorityQueue 897 : public RegReductionPriorityQueue<SF> { 898 // SUnitMap SDNode to SUnit mapping (n -> n). 899 DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap; 900 901 // SUnits - The SUnits for the current graph. 902 const std::vector<SUnit> *SUnits; 903 904 // SethiUllmanNumbers - The SethiUllman number for each node. 905 std::vector<unsigned> SethiUllmanNumbers; 906 907 const TargetInstrInfo *TII; 908 public: 909 explicit BURegReductionPriorityQueue(const TargetInstrInfo *tii) 910 : TII(tii) {} 911 912 void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 913 std::vector<SUnit> &sunits) { 914 SUnitMap = &sumap; 915 SUnits = &sunits; 916 // Add pseudo dependency edges for two-address nodes. 917 AddPseudoTwoAddrDeps(); 918 // Calculate node priorities. 919 CalculateSethiUllmanNumbers(); 920 } 921 922 void addNode(const SUnit *SU) { 923 SethiUllmanNumbers.resize(SUnits->size(), 0); 924 CalcNodeSethiUllmanNumber(SU); 925 } 926 927 void updateNode(const SUnit *SU) { 928 SethiUllmanNumbers[SU->NodeNum] = 0; 929 CalcNodeSethiUllmanNumber(SU); 930 } 931 932 void releaseState() { 933 SUnits = 0; 934 SethiUllmanNumbers.clear(); 935 } 936 937 unsigned getNodePriority(const SUnit *SU) const { 938 assert(SU->NodeNum < SethiUllmanNumbers.size()); 939 unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; 940 if (Opc == ISD::CopyFromReg && !isCopyFromLiveIn(SU)) 941 // CopyFromReg should be close to its def because it restricts 942 // allocation choices. But if it is a livein then perhaps we want it 943 // closer to its uses so it can be coalesced. 944 return 0xffff; 945 else if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 946 // CopyToReg should be close to its uses to facilitate coalescing and 947 // avoid spilling. 948 return 0; 949 else if (SU->NumSuccs == 0) 950 // If SU does not have a use, i.e. it doesn't produce a value that would 951 // be consumed (e.g. store), then it terminates a chain of computation. 952 // Give it a large SethiUllman number so it will be scheduled right 953 // before its predecessors that it doesn't lengthen their live ranges. 954 return 0xffff; 955 else if (SU->NumPreds == 0) 956 // If SU does not have a def, schedule it close to its uses because it 957 // does not lengthen any live ranges. 958 return 0; 959 else 960 return SethiUllmanNumbers[SU->NodeNum]; 961 } 962 963 private: 964 bool canClobber(SUnit *SU, SUnit *Op); 965 void AddPseudoTwoAddrDeps(); 966 void CalculateSethiUllmanNumbers(); 967 unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); 968 }; 969 970 971 template<class SF> 972 class VISIBILITY_HIDDEN TDRegReductionPriorityQueue 973 : public RegReductionPriorityQueue<SF> { 974 // SUnitMap SDNode to SUnit mapping (n -> n). 975 DenseMap<SDNode*, std::vector<SUnit*> > *SUnitMap; 976 977 // SUnits - The SUnits for the current graph. 978 const std::vector<SUnit> *SUnits; 979 980 // SethiUllmanNumbers - The SethiUllman number for each node. 981 std::vector<unsigned> SethiUllmanNumbers; 982 983 public: 984 TDRegReductionPriorityQueue() {} 985 986 void initNodes(DenseMap<SDNode*, std::vector<SUnit*> > &sumap, 987 std::vector<SUnit> &sunits) { 988 SUnitMap = &sumap; 989 SUnits = &sunits; 990 // Calculate node priorities. 991 CalculateSethiUllmanNumbers(); 992 } 993 994 void addNode(const SUnit *SU) { 995 SethiUllmanNumbers.resize(SUnits->size(), 0); 996 CalcNodeSethiUllmanNumber(SU); 997 } 998 999 void updateNode(const SUnit *SU) { 1000 SethiUllmanNumbers[SU->NodeNum] = 0; 1001 CalcNodeSethiUllmanNumber(SU); 1002 } 1003 1004 void releaseState() { 1005 SUnits = 0; 1006 SethiUllmanNumbers.clear(); 1007 } 1008 1009 unsigned getNodePriority(const SUnit *SU) const { 1010 assert(SU->NodeNum < SethiUllmanNumbers.size()); 1011 return SethiUllmanNumbers[SU->NodeNum]; 1012 } 1013 1014 private: 1015 void CalculateSethiUllmanNumbers(); 1016 unsigned CalcNodeSethiUllmanNumber(const SUnit *SU); 1017 }; 1018} 1019 1020/// closestSucc - Returns the scheduled cycle of the successor which is 1021/// closet to the current cycle. 1022static unsigned closestSucc(const SUnit *SU) { 1023 unsigned MaxCycle = 0; 1024 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1025 I != E; ++I) { 1026 unsigned Cycle = I->Dep->Cycle; 1027 // If there are bunch of CopyToRegs stacked up, they should be considered 1028 // to be at the same position. 1029 if (I->Dep->Node && I->Dep->Node->getOpcode() == ISD::CopyToReg) 1030 Cycle = closestSucc(I->Dep)+1; 1031 if (Cycle > MaxCycle) 1032 MaxCycle = Cycle; 1033 } 1034 return MaxCycle; 1035} 1036 1037/// calcMaxScratches - Returns an cost estimate of the worse case requirement 1038/// for scratch registers. Live-in operands and live-out results don't count 1039/// since they are "fixed". 1040static unsigned calcMaxScratches(const SUnit *SU) { 1041 unsigned Scratches = 0; 1042 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1043 I != E; ++I) { 1044 if (I->isCtrl) continue; // ignore chain preds 1045 if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyFromReg) 1046 Scratches++; 1047 } 1048 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1049 I != E; ++I) { 1050 if (I->isCtrl) continue; // ignore chain succs 1051 if (!I->Dep->Node || I->Dep->Node->getOpcode() != ISD::CopyToReg) 1052 Scratches += 10; 1053 } 1054 return Scratches; 1055} 1056 1057// Bottom up 1058bool bu_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1059 // There used to be a special tie breaker here that looked for 1060 // two-address instructions and preferred the instruction with a 1061 // def&use operand. The special case triggered diagnostics when 1062 // _GLIBCXX_DEBUG was enabled because it broke the strict weak 1063 // ordering that priority_queue requires. It didn't help much anyway 1064 // because AddPseudoTwoAddrDeps already covers many of the cases 1065 // where it would have applied. In addition, it's counter-intuitive 1066 // that a tie breaker would be the first thing attempted. There's a 1067 // "real" tie breaker below that is the operation of last resort. 1068 // The fact that the "special tie breaker" would trigger when there 1069 // wasn't otherwise a tie is what broke the strict weak ordering 1070 // constraint. 1071 1072 unsigned LPriority = SPQ->getNodePriority(left); 1073 unsigned RPriority = SPQ->getNodePriority(right); 1074 if (LPriority > RPriority) 1075 return true; 1076 else if (LPriority == RPriority) { 1077 // Try schedule def + use closer when Sethi-Ullman numbers are the same. 1078 // e.g. 1079 // t1 = op t2, c1 1080 // t3 = op t4, c2 1081 // 1082 // and the following instructions are both ready. 1083 // t2 = op c3 1084 // t4 = op c4 1085 // 1086 // Then schedule t2 = op first. 1087 // i.e. 1088 // t4 = op c4 1089 // t2 = op c3 1090 // t1 = op t2, c1 1091 // t3 = op t4, c2 1092 // 1093 // This creates more short live intervals. 1094 unsigned LDist = closestSucc(left); 1095 unsigned RDist = closestSucc(right); 1096 if (LDist < RDist) 1097 return true; 1098 else if (LDist == RDist) { 1099 // Intuitively, it's good to push down instructions whose results are 1100 // liveout so their long live ranges won't conflict with other values 1101 // which are needed inside the BB. Further prioritize liveout instructions 1102 // by the number of operands which are calculated within the BB. 1103 unsigned LScratch = calcMaxScratches(left); 1104 unsigned RScratch = calcMaxScratches(right); 1105 if (LScratch > RScratch) 1106 return true; 1107 else if (LScratch == RScratch) 1108 if (left->Height > right->Height) 1109 return true; 1110 else if (left->Height == right->Height) 1111 if (left->Depth < right->Depth) 1112 return true; 1113 else if (left->Depth == right->Depth) 1114 if (left->CycleBound > right->CycleBound) 1115 return true; 1116 } 1117 } 1118 return false; 1119} 1120 1121template<class SF> 1122bool BURegReductionPriorityQueue<SF>::canClobber(SUnit *SU, SUnit *Op) { 1123 if (SU->isTwoAddress) { 1124 unsigned Opc = SU->Node->getTargetOpcode(); 1125 unsigned NumRes = TII->getNumDefs(Opc); 1126 unsigned NumOps = ScheduleDAG::CountOperands(SU->Node); 1127 for (unsigned i = 0; i != NumOps; ++i) { 1128 if (TII->getOperandConstraint(Opc, i+NumRes, TOI::TIED_TO) != -1) { 1129 SDNode *DU = SU->Node->getOperand(i).Val; 1130 if (Op == (*SUnitMap)[DU][SU->InstanceNo]) 1131 return true; 1132 } 1133 } 1134 } 1135 return false; 1136} 1137 1138 1139/// AddPseudoTwoAddrDeps - If two nodes share an operand and one of them uses 1140/// it as a def&use operand. Add a pseudo control edge from it to the other 1141/// node (if it won't create a cycle) so the two-address one will be scheduled 1142/// first (lower in the schedule). 1143template<class SF> 1144void BURegReductionPriorityQueue<SF>::AddPseudoTwoAddrDeps() { 1145 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) { 1146 SUnit *SU = (SUnit *)&((*SUnits)[i]); 1147 if (!SU->isTwoAddress) 1148 continue; 1149 1150 SDNode *Node = SU->Node; 1151 if (!Node || !Node->isTargetOpcode()) 1152 continue; 1153 1154 unsigned Opc = Node->getTargetOpcode(); 1155 unsigned NumRes = TII->getNumDefs(Opc); 1156 unsigned NumOps = ScheduleDAG::CountOperands(Node); 1157 for (unsigned j = 0; j != NumOps; ++j) { 1158 if (TII->getOperandConstraint(Opc, j+NumRes, TOI::TIED_TO) != -1) { 1159 SDNode *DU = SU->Node->getOperand(j).Val; 1160 SUnit *DUSU = (*SUnitMap)[DU][SU->InstanceNo]; 1161 if (!DUSU) continue; 1162 for (SUnit::succ_iterator I = DUSU->Succs.begin(),E = DUSU->Succs.end(); 1163 I != E; ++I) { 1164 if (I->isCtrl) continue; 1165 SUnit *SuccSU = I->Dep; 1166 // Don't constraint nodes with implicit defs. It can create cycles 1167 // plus it may increase register pressures. 1168 if (SuccSU == SU || SuccSU->hasImplicitDefs) 1169 continue; 1170 // Be conservative. Ignore if nodes aren't at the same depth. 1171 if (SuccSU->Depth != SU->Depth) 1172 continue; 1173 if ((!canClobber(SuccSU, DUSU) || 1174 (!SU->isCommutable && SuccSU->isCommutable)) && 1175 !isReachable(SuccSU, SU)) { 1176 DOUT << "Adding an edge from SU # " << SU->NodeNum 1177 << " to SU #" << SuccSU->NodeNum << "\n"; 1178 SU->addPred(SuccSU, true, true); 1179 } 1180 } 1181 } 1182 } 1183 } 1184} 1185 1186/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. 1187/// Smaller number is the higher priority. 1188template<class SF> 1189unsigned BURegReductionPriorityQueue<SF>:: 1190CalcNodeSethiUllmanNumber(const SUnit *SU) { 1191 unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 1192 if (SethiUllmanNumber != 0) 1193 return SethiUllmanNumber; 1194 1195 unsigned Extra = 0; 1196 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1197 I != E; ++I) { 1198 if (I->isCtrl) continue; // ignore chain preds 1199 SUnit *PredSU = I->Dep; 1200 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); 1201 if (PredSethiUllman > SethiUllmanNumber) { 1202 SethiUllmanNumber = PredSethiUllman; 1203 Extra = 0; 1204 } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) 1205 ++Extra; 1206 } 1207 1208 SethiUllmanNumber += Extra; 1209 1210 if (SethiUllmanNumber == 0) 1211 SethiUllmanNumber = 1; 1212 1213 return SethiUllmanNumber; 1214} 1215 1216/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 1217/// scheduling units. 1218template<class SF> 1219void BURegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 1220 SethiUllmanNumbers.assign(SUnits->size(), 0); 1221 1222 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 1223 CalcNodeSethiUllmanNumber(&(*SUnits)[i]); 1224} 1225 1226static unsigned SumOfUnscheduledPredsOfSuccs(const SUnit *SU) { 1227 unsigned Sum = 0; 1228 for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 1229 I != E; ++I) { 1230 SUnit *SuccSU = I->Dep; 1231 for (SUnit::const_pred_iterator II = SuccSU->Preds.begin(), 1232 EE = SuccSU->Preds.end(); II != EE; ++II) { 1233 SUnit *PredSU = II->Dep; 1234 if (!PredSU->isScheduled) 1235 ++Sum; 1236 } 1237 } 1238 1239 return Sum; 1240} 1241 1242 1243// Top down 1244bool td_ls_rr_sort::operator()(const SUnit *left, const SUnit *right) const { 1245 unsigned LPriority = SPQ->getNodePriority(left); 1246 unsigned RPriority = SPQ->getNodePriority(right); 1247 bool LIsTarget = left->Node && left->Node->isTargetOpcode(); 1248 bool RIsTarget = right->Node && right->Node->isTargetOpcode(); 1249 bool LIsFloater = LIsTarget && left->NumPreds == 0; 1250 bool RIsFloater = RIsTarget && right->NumPreds == 0; 1251 unsigned LBonus = (SumOfUnscheduledPredsOfSuccs(left) == 1) ? 2 : 0; 1252 unsigned RBonus = (SumOfUnscheduledPredsOfSuccs(right) == 1) ? 2 : 0; 1253 1254 if (left->NumSuccs == 0 && right->NumSuccs != 0) 1255 return false; 1256 else if (left->NumSuccs != 0 && right->NumSuccs == 0) 1257 return true; 1258 1259 // Special tie breaker: if two nodes share a operand, the one that use it 1260 // as a def&use operand is preferred. 1261 if (LIsTarget && RIsTarget) { 1262 if (left->isTwoAddress && !right->isTwoAddress) { 1263 SDNode *DUNode = left->Node->getOperand(0).Val; 1264 if (DUNode->isOperand(right->Node)) 1265 RBonus += 2; 1266 } 1267 if (!left->isTwoAddress && right->isTwoAddress) { 1268 SDNode *DUNode = right->Node->getOperand(0).Val; 1269 if (DUNode->isOperand(left->Node)) 1270 LBonus += 2; 1271 } 1272 } 1273 if (LIsFloater) 1274 LBonus -= 2; 1275 if (RIsFloater) 1276 RBonus -= 2; 1277 if (left->NumSuccs == 1) 1278 LBonus += 2; 1279 if (right->NumSuccs == 1) 1280 RBonus += 2; 1281 1282 if (LPriority+LBonus < RPriority+RBonus) 1283 return true; 1284 else if (LPriority == RPriority) 1285 if (left->Depth < right->Depth) 1286 return true; 1287 else if (left->Depth == right->Depth) 1288 if (left->NumSuccsLeft > right->NumSuccsLeft) 1289 return true; 1290 else if (left->NumSuccsLeft == right->NumSuccsLeft) 1291 if (left->CycleBound > right->CycleBound) 1292 return true; 1293 return false; 1294} 1295 1296/// CalcNodeSethiUllmanNumber - Priority is the Sethi Ullman number. 1297/// Smaller number is the higher priority. 1298template<class SF> 1299unsigned TDRegReductionPriorityQueue<SF>:: 1300CalcNodeSethiUllmanNumber(const SUnit *SU) { 1301 unsigned &SethiUllmanNumber = SethiUllmanNumbers[SU->NodeNum]; 1302 if (SethiUllmanNumber != 0) 1303 return SethiUllmanNumber; 1304 1305 unsigned Opc = SU->Node ? SU->Node->getOpcode() : 0; 1306 if (Opc == ISD::TokenFactor || Opc == ISD::CopyToReg) 1307 SethiUllmanNumber = 0xffff; 1308 else if (SU->NumSuccsLeft == 0) 1309 // If SU does not have a use, i.e. it doesn't produce a value that would 1310 // be consumed (e.g. store), then it terminates a chain of computation. 1311 // Give it a small SethiUllman number so it will be scheduled right before 1312 // its predecessors that it doesn't lengthen their live ranges. 1313 SethiUllmanNumber = 0; 1314 else if (SU->NumPredsLeft == 0 && 1315 (Opc != ISD::CopyFromReg || isCopyFromLiveIn(SU))) 1316 SethiUllmanNumber = 0xffff; 1317 else { 1318 int Extra = 0; 1319 for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 1320 I != E; ++I) { 1321 if (I->isCtrl) continue; // ignore chain preds 1322 SUnit *PredSU = I->Dep; 1323 unsigned PredSethiUllman = CalcNodeSethiUllmanNumber(PredSU); 1324 if (PredSethiUllman > SethiUllmanNumber) { 1325 SethiUllmanNumber = PredSethiUllman; 1326 Extra = 0; 1327 } else if (PredSethiUllman == SethiUllmanNumber && !I->isCtrl) 1328 ++Extra; 1329 } 1330 1331 SethiUllmanNumber += Extra; 1332 } 1333 1334 return SethiUllmanNumber; 1335} 1336 1337/// CalculateSethiUllmanNumbers - Calculate Sethi-Ullman numbers of all 1338/// scheduling units. 1339template<class SF> 1340void TDRegReductionPriorityQueue<SF>::CalculateSethiUllmanNumbers() { 1341 SethiUllmanNumbers.assign(SUnits->size(), 0); 1342 1343 for (unsigned i = 0, e = SUnits->size(); i != e; ++i) 1344 CalcNodeSethiUllmanNumber(&(*SUnits)[i]); 1345} 1346 1347//===----------------------------------------------------------------------===// 1348// Public Constructor Functions 1349//===----------------------------------------------------------------------===// 1350 1351llvm::ScheduleDAG* llvm::createBURRListDAGScheduler(SelectionDAGISel *IS, 1352 SelectionDAG *DAG, 1353 MachineBasicBlock *BB) { 1354 const TargetInstrInfo *TII = DAG->getTarget().getInstrInfo(); 1355 return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), true, 1356 new BURegReductionPriorityQueue<bu_ls_rr_sort>(TII)); 1357} 1358 1359llvm::ScheduleDAG* llvm::createTDRRListDAGScheduler(SelectionDAGISel *IS, 1360 SelectionDAG *DAG, 1361 MachineBasicBlock *BB) { 1362 return new ScheduleDAGRRList(*DAG, BB, DAG->getTarget(), false, 1363 new TDRegReductionPriorityQueue<td_ls_rr_sort>()); 1364} 1365 1366