CodeGen/SelectionDAG/ScheduleDAGRRList.cpp

124   std::vector<SUnit*> PendingQueue;
143   std::vector<SUnit*> LiveRegDefs;
144   std::vector<SUnit*> LiveRegGens;
147   // Each interference is an SUnit and set of physical registers.
148   SmallVector<SUnit*, 4> Interferences;
149   typedef DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMapT;
158   DenseMap<SUnit*, SUnit*> CallSeqEndForStart;
185   bool IsReachable(const SUnit *SU, const SUnit *TargetSU) {
191   bool WillCreateCycle(SUnit *SU, SUnit *TargetSU) {
195   /// AddPred - adds a predecessor edge to SUnit SU.
198   void AddPred(SUnit *SU, const SDep &D) {
203   /// RemovePred - removes a predecessor edge from SUnit SU.
206   void RemovePred(SUnit *SU, const SDep &D) {
212   bool isReady(SUnit *SU) {
217   void ReleasePred(SUnit *SU, const SDep *PredEdge);
218   void ReleasePredecessors(SUnit *SU);
221   void AdvancePastStalls(SUnit *SU);
222   void EmitNode(SUnit *SU);
223   void ScheduleNodeBottomUp(SUnit*);
225   void UnscheduleNodeBottomUp(SUnit*);
227   void BacktrackBottomUp(SUnit*, SUnit*);
228   SUnit *CopyAndMoveSuccessors(SUnit*);
229   void InsertCopiesAndMoveSuccs(SUnit*, unsigned,
232                                 SmallVectorImpl<SUnit*>&);
233   bool DelayForLiveRegsBottomUp(SUnit*, SmallVectorImpl<unsigned>&);
237   SUnit *PickNodeToScheduleBottomUp();
240   /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it.
242   SUnit *CreateNewSUnit(SDNode *N) {
244     SUnit *NewNode = newSUnit(N);
251   /// CreateClone - Creates a new SUnit from an existing one.
253   SUnit *CreateClone(SUnit *N) {
255     SUnit *NewNode = Clone(N);
364 void ScheduleDAGRRList::ReleasePred(SUnit *SU, const SDep *PredEdge) {
365   SUnit *PredSU = PredEdge->getSUnit();
524 void ScheduleDAGRRList::ReleasePredecessors(SUnit *SU) {
526   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
534       SUnit *RegDef = LiveRegDefs[I->getReg()]; (void)RegDef;
557         SUnit *Def = &SUnits[N->getNodeId()];
621 void ScheduleDAGRRList::AdvancePastStalls(SUnit *SU) {
661 /// Record this SUnit in the HazardRecognizer.
663 void ScheduleDAGRRList::EmitNode(SUnit *SU) {
700 static void resetVRegCycle(SUnit *SU);
705 void ScheduleDAGRRList::ScheduleNodeBottomUp(SUnit *SU) {
716   // backtracking. Instead add a "ready cycle" to SUnit. Before scheduling the
739   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
791   SUnit *PredSU = PredEdge->getSUnit();
804 void ScheduleDAGRRList::UnscheduleNodeBottomUp(SUnit *SU) {
808   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
850   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
890   std::vector<SUnit*>::const_iterator I = (Sequence.end() - LookAhead);
892   for (std::vector<SUnit*>::const_iterator E = Sequence.end(); I != E; ++I) {
893     SUnit *SU = *I;
903 void ScheduleDAGRRList::BacktrackBottomUp(SUnit *SU, SUnit *BtSU) {
904   SUnit *OldSU = Sequence.back();
925 static bool isOperandOf(const SUnit *SU, SDNode *N) {
936 SUnit *ScheduleDAGRRList::CopyAndMoveSuccessors(SUnit *SU) {
944   SUnit *NewSU;
986     SUnit *LoadSU;
998     SUnit *NewSU = CreateNewSUnit(N);
1021     for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1030     for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1058       SUnit *SuccDep = D.getSUnit();
1070       SUnit *SuccDep = D.getSUnit();
1101   // New SUnit has the exact same predecessors.
1102   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1109   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1110   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1114     SUnit *SuccSU = I->getSUnit();
1134 /// scheduled successors of the given SUnit to the last copy.
1135 void ScheduleDAGRRList::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg,
1138                                               SmallVectorImpl<SUnit*> &Copies) {
1139   SUnit *CopyFromSU = CreateNewSUnit(NULL);
1143   SUnit *CopyToSU = CreateNewSUnit(NULL);
1149   SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps;
1150   for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
1154     SUnit *SuccSU = I->getSUnit();
1204 /// specified register def of the specified SUnit clobbers any "live" registers.
1205 static void CheckForLiveRegDef(SUnit *SU, unsigned Reg,
1206                                std::vector<SUnit*> &LiveRegDefs,
1227 static void CheckForLiveRegDefMasked(SUnit *SU, const uint32_t *RegMask,
1228                                      std::vector<SUnit*> &LiveRegDefs,
1255 DelayForLiveRegsBottomUp(SUnit *SU, SmallVectorImpl<unsigned> &LRegs) {
1264   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1331     SUnit *SU = Interferences[i-1];
1357 SUnit *ScheduleDAGRRList::PickNodeToScheduleBottomUp() {
1358   SUnit *CurSU = AvailableQueue->empty() ? 0 : AvailableQueue->pop();
1387     SUnit *TrySU = Interferences[i];
1392     SUnit *BtSU = NULL;
1435     SUnit *TrySU = Interferences[0];
1439     SUnit *LRDef = LiveRegDefs[Reg];
1452     SUnit *NewDef = 0;
1460       SmallVector<SUnit*, 2> Copies;
1487     SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()];
1502     SUnit *SU = PickNodeToScheduleBottomUp();
1533 struct queue_sort : public std::binary_function<SUnit*, SUnit*, bool> {
1534   bool isReady(SUnit* SU, unsigned CurCycle) const { return true; }
1544   bool operator()(SUnit* left, SUnit* right) const {
1564   bool operator()(SUnit* left, SUnit* right) const;
1580   bool operator()(SUnit* left, SUnit* right) const;
1596   bool isReady(SUnit *SU, unsigned CurCycle) const;
1598   bool operator()(SUnit* left, SUnit* right) const;
1615   bool isReady(SUnit *SU, unsigned CurCycle) const;
1617   bool operator()(SUnit* left, SUnit* right) const;
1622   std::vector<SUnit*> Queue;
1628   std::vector<SUnit> *SUnits;
1678   void initNodes(std::vector<SUnit> &sunits);
1680   void addNode(const SUnit *SU);
1682   void updateNode(const SUnit *SU);
1690   unsigned getNodePriority(const SUnit *SU) const;
1692   unsigned getNodeOrdering(const SUnit *SU) const {
1700   void push(SUnit *U) {
1706   void remove(SUnit *SU) {
1709     std::vector<SUnit *>::iterator I = std::find(Queue.begin(), Queue.end(),
1721   bool HighRegPressure(const SUnit *SU) const;
1723   bool MayReduceRegPressure(SUnit *SU) const;
1725   int RegPressureDiff(SUnit *SU, unsigned &LiveUses) const;
1727   void scheduledNode(SUnit *SU);
1729   void unscheduledNode(SUnit *SU);
1732   bool canClobber(const SUnit *SU, const SUnit *Op);
1739 static SUnit *popFromQueueImpl(std::vector<SUnit*> &Q, SF &Picker) {
1740   std::vector<SUnit *>::iterator Best = Q.begin();
1741   for (std::vector<SUnit *>::iterator I = llvm::next(Q.begin()),
1745   SUnit *V = *Best;
1753 SUnit *popFromQueue(std::vector<SUnit*> &Q, SF &Picker, ScheduleDAG *DAG) {
1781   bool isReady(SUnit *U) const {
1785   SUnit *pop() {
1788     SUnit *V = popFromQueue(Queue, Picker, scheduleDAG);
1796     std::vector<SUnit*> DumpQueue = Queue;
1799       SUnit *SU = popFromQueue(DumpQueue, DumpPicker, scheduleDAG);
1830 static int checkSpecialNodes(const SUnit *left, const SUnit *right) {
1841 CalcNodeSethiUllmanNumber(const SUnit *SU, std::vector<unsigned> &SUNumbers) {
1847   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
1850     SUnit *PredSU = I->getSUnit();
1876 void RegReductionPQBase::addNode(const SUnit *SU) {
1883 void RegReductionPQBase::updateNode(const SUnit *SU) {
1890 unsigned RegReductionPQBase::getNodePriority(const SUnit *SU) const {
1945 bool RegReductionPQBase::HighRegPressure(const SUnit *SU) const {
1949   for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
1953     SUnit *PredSU = I->getSUnit();
1971 bool RegReductionPQBase::MayReduceRegPressure(SUnit *SU) const {
1996 int RegReductionPQBase::RegPressureDiff(SUnit *SU, unsigned &LiveUses) const {
1999   for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
2003     SUnit *PredSU = I->getSUnit();
2036 void RegReductionPQBase::scheduledNode(SUnit *SU) {
2043   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
2047     SUnit *PredSU = I->getSUnit();
2105 void RegReductionPQBase::unscheduledNode(SUnit *SU) {
2125   for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
2129     SUnit *PredSU = I->getSUnit();
2192 static unsigned closestSucc(const SUnit *SU) {
2194   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
2211 static unsigned calcMaxScratches(const SUnit *SU) {
2213   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
2223 static bool hasOnlyLiveInOpers(const SUnit *SU) {
2225   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
2228     const SUnit *PredSU = I->getSUnit();
2246 static bool hasOnlyLiveOutUses(const SUnit *SU) {
2248   for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end();
2251     const SUnit *SuccSU = I->getSUnit();
2275 static void initVRegCycle(SUnit *SU) {
2286   for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end();
2295 static void resetVRegCycle(SUnit *SU) {
2299   for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
2302     SUnit *PredSU = I->getSUnit();
2311 // Return true if this SUnit uses a CopyFromReg node marked as a VRegCycle. This
2313 static bool hasVRegCycleUse(const SUnit *SU) {
2318   for (SUnit::const_pred_iterator I = SU->Preds.begin(),E = SU->Preds.end();
2333 static bool BUHasStall(SUnit *SU, int Height, RegReductionPQBase *SPQ) {
2343 static int BUCompareLatency(SUnit *left, SUnit *right, bool checkPref,
2394 static bool BURRSort(SUnit *left, SUnit *right, RegReductionPQBase *SPQ) {
2498 bool bu_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2506 bool src_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2525 bool hybrid_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2540 bool hybrid_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2572 bool ilp_ls_rr_sort::isReady(SUnit *SU, unsigned CurCycle) const {
2582 static bool canEnableCoalescing(SUnit *SU) {
2606 bool ilp_ls_rr_sort::operator()(SUnit *left, SUnit *right) const {
2665 void RegReductionPQBase::initNodes(std::vector<SUnit> &sunits) {
2688 bool RegReductionPQBase::canClobber(const SUnit *SU, const SUnit *Op) {
2709 static bool canClobberReachingPhysRegUse(const SUnit *DepSU, const SUnit *SU,
2719   for (SUnit::const_succ_iterator SI = SU->Succs.begin(), SE = SU->Succs.end();
2721     SUnit *SuccSU = SI->getSUnit();
2722     for (SUnit::const_pred_iterator PI = SuccSU->Preds.begin(),
2746 static bool canClobberPhysRegDefs(const SUnit *SuccSU, const SUnit *SU,
2817     SUnit *SU = &(*SUnits)[i];
2835     SUnit *PredSU = 0;
2836     for (SUnit::const_pred_iterator II = SU->Preds.begin(),
2860     for (SUnit::const_succ_iterator II = PredSU->Succs.begin(),
2862       SUnit *PredSuccSU = II->getSUnit();
2885       SUnit *SuccSU = Edge.getSUnit();
2908     SUnit *SU = &(*SUnits)[i];
2927       const SUnit *DUSU = &(*SUnits)[DU->getNodeId()];
2929       for (SUnit::const_succ_iterator I = DUSU->Succs.begin(),
2932         SUnit *SuccSU = I->getSUnit();