ScheduleDAGFast.cpp revision 550f5afb68ce8f034991863cac65bef22a6554da
1ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----- ScheduleDAGFast.cpp - Fast poor list scheduler -----------------===// 2ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// 3ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// The LLVM Compiler Infrastructure 4ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// 5ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// This file is distributed under the University of Illinois Open Source 6ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// License. See LICENSE.TXT for details. 7ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// 8ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 9ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// 10ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// This implements a fast scheduler. 11ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// 12ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 13ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 14ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#define DEBUG_TYPE "pre-RA-sched" 15ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/CodeGen/ScheduleDAG.h" 16ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/CodeGen/SchedulerRegistry.h" 17ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Target/TargetRegisterInfo.h" 18ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Target/TargetData.h" 19ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Target/TargetMachine.h" 20ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Target/TargetInstrInfo.h" 21ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Support/Debug.h" 22ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Support/Compiler.h" 23ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/ADT/SmallSet.h" 24ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/ADT/Statistic.h" 25ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/ADT/STLExtras.h" 26ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Support/CommandLine.h" 27ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanusing namespace llvm; 28ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 29ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan GohmanSTATISTIC(NumUnfolds, "Number of nodes unfolded"); 30ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan GohmanSTATISTIC(NumDups, "Number of duplicated nodes"); 31ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan GohmanSTATISTIC(NumCCCopies, "Number of cross class copies"); 32ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 33ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanstatic RegisterScheduler 34b8cab9227a0f6ffbdaae33e3c64268e265008a6aDan Gohman fastDAGScheduler("fast", "Fast suboptimal list scheduling", 35ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman createFastDAGScheduler); 36ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 37ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmannamespace { 38ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// FastPriorityQueue - A degenerate priority queue that considers 39ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// all nodes to have the same priority. 40ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// 41ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman struct VISIBILITY_HIDDEN FastPriorityQueue { 42086ec9976ff6cee083de618429c78473491d5713Dan Gohman SmallVector<SUnit *, 16> Queue; 43ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 44ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool empty() const { return Queue.empty(); } 45ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 46ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void push(SUnit *U) { 47ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Queue.push_back(U); 48ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 49ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 50ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *pop() { 51ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (empty()) return NULL; 52ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *V = Queue.back(); 53ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Queue.pop_back(); 54ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return V; 55ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 56ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman }; 57ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 58ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 59ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// ScheduleDAGFast - The actual "fast" list scheduler implementation. 60ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// 61ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanclass VISIBILITY_HIDDEN ScheduleDAGFast : public ScheduleDAG { 62ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanprivate: 63ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// AvailableQueue - The priority queue to use for the available SUnits. 64ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman FastPriorityQueue AvailableQueue; 65ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 66086ec9976ff6cee083de618429c78473491d5713Dan Gohman /// LiveRegDefs - A set of physical registers and their definition 67ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// that are "live". These nodes must be scheduled before any other nodes that 68ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// modifies the registers can be scheduled. 69086ec9976ff6cee083de618429c78473491d5713Dan Gohman unsigned NumLiveRegs; 70ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman std::vector<SUnit*> LiveRegDefs; 71ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman std::vector<unsigned> LiveRegCycles; 72ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 73ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanpublic: 74a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman ScheduleDAGFast(SelectionDAG *dag, MachineBasicBlock *bb, 75ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetMachine &tm) 76ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman : ScheduleDAG(dag, bb, tm) {} 77ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 78ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void Schedule(); 79ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 80ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// AddPred - This adds the specified node X as a predecessor of 81ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// the current node Y if not already. 82ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// This returns true if this is a new predecessor. 83ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isSpecial, 84ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned PhyReg = 0, int Cost = 1); 85ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 86ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// RemovePred - This removes the specified node N from the predecessors of 87ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// the current node M. 88ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool RemovePred(SUnit *M, SUnit *N, bool isCtrl, bool isSpecial); 89ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 90ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanprivate: 91ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void ReleasePred(SUnit*, bool, unsigned); 92ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void ScheduleNodeBottomUp(SUnit*, unsigned); 93ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CopyAndMoveSuccessors(SUnit*); 94ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void InsertCCCopiesAndMoveSuccs(SUnit*, unsigned, 95ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass*, 96ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass*, 97ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SUnit*, 2>&); 98ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 99ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void ListScheduleBottomUp(); 100ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 101ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// CreateNewSUnit - Creates a new SUnit and returns a pointer to it. 102ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CreateNewSUnit(SDNode *N) { 103ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *NewNode = NewSUnit(N); 104ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NewNode; 105ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 106ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 107ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// CreateClone - Creates a new SUnit from an existing one. 108ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CreateClone(SUnit *N) { 109ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *NewNode = Clone(N); 110ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NewNode; 111ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 112ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman}; 113ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} // end anonymous namespace 114ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 115ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 116ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// Schedule - Schedule the DAG using list scheduling. 117ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanvoid ScheduleDAGFast::Schedule() { 118ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DOUT << "********** List Scheduling **********\n"; 119ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 120086ec9976ff6cee083de618429c78473491d5713Dan Gohman NumLiveRegs = 0; 121ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegDefs.resize(TRI->getNumRegs(), NULL); 122ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegCycles.resize(TRI->getNumRegs(), 0); 123ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 124ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Build scheduling units. 125ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman BuildSchedUnits(); 126ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 127ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 128a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SUnits[su].dumpAll(DAG)); 129ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 130ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Execute the actual scheduling loop. 131ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ListScheduleBottomUp(); 132ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 133ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 134ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 135ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// Bottom-Up Scheduling 136ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 137ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 138ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 139ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 140ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanvoid ScheduleDAGFast::ReleasePred(SUnit *PredSU, bool isChain, 141ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned CurCycle) { 142ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // FIXME: the distance between two nodes is not always == the predecessor's 143ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // latency. For example, the reader can very well read the register written 144ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // by the predecessor later than the issue cycle. It also depends on the 145ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // interrupt model (drain vs. freeze). 146ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman PredSU->CycleBound = std::max(PredSU->CycleBound, CurCycle + PredSU->Latency); 147ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 148ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman --PredSU->NumSuccsLeft; 149ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 150ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#ifndef NDEBUG 151ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (PredSU->NumSuccsLeft < 0) { 152ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman cerr << "*** List scheduling failed! ***\n"; 153a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman PredSU->dump(DAG); 154ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman cerr << " has been released too many times!\n"; 155ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(0); 156ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 157ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#endif 158ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 159ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (PredSU->NumSuccsLeft == 0) { 160ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman PredSU->isAvailable = true; 161ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AvailableQueue.push(PredSU); 162ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 163ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 164ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 165ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 166ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// count of its predecessors. If a predecessor pending count is zero, add it to 167ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// the Available queue. 168ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanvoid ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 169ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DOUT << "*** Scheduling [" << CurCycle << "]: "; 170a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman DEBUG(SU->dump(DAG)); 171ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SU->Cycle = CurCycle; 172ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 173ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Bottom up: release predecessors 174ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 175ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 176ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ReleasePred(I->Dep, I->isCtrl, CurCycle); 177ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->Cost < 0) { 178ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // This is a physical register dependency and it's impossible or 179ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // expensive to copy the register. Make sure nothing that can 180ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // clobber the register is scheduled between the predecessor and 181ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // this node. 182086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (!LiveRegDefs[I->Reg]) { 183086ec9976ff6cee083de618429c78473491d5713Dan Gohman ++NumLiveRegs; 184ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegDefs[I->Reg] = I->Dep; 185ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegCycles[I->Reg] = CurCycle; 186ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 187ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 188ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 189ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 190ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Release all the implicit physical register defs that are live. 191ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 192ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 193ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->Cost < 0) { 194ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (LiveRegCycles[I->Reg] == I->Dep->Cycle) { 195086ec9976ff6cee083de618429c78473491d5713Dan Gohman assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 196ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(LiveRegDefs[I->Reg] == SU && 197ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman "Physical register dependency violated?"); 198086ec9976ff6cee083de618429c78473491d5713Dan Gohman --NumLiveRegs; 199ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegDefs[I->Reg] = NULL; 200ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegCycles[I->Reg] = 0; 201ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 202ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 203ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 204ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 205ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SU->isScheduled = true; 206ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 207ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 208ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// AddPred - adds an edge from SUnit X to SUnit Y. 209ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanbool ScheduleDAGFast::AddPred(SUnit *Y, SUnit *X, bool isCtrl, bool isSpecial, 210ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned PhyReg, int Cost) { 211ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return Y->addPred(X, isCtrl, isSpecial, PhyReg, Cost); 212ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 213ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 214ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// RemovePred - This removes the specified node N from the predecessors of 215ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// the current node M. 216ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanbool ScheduleDAGFast::RemovePred(SUnit *M, SUnit *N, 217ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool isCtrl, bool isSpecial) { 218ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return M->removePred(N, isCtrl, isSpecial); 219ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 220ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 221ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 222ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// successors to the newly created node. 223ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan GohmanSUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { 224ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (SU->FlaggedNodes.size()) 225ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 226ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 227550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *N = SU->getNode(); 228ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!N) 229ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 230ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 231ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *NewSU; 232ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool TryUnfold = false; 233ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 234ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman MVT VT = N->getValueType(i); 235ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (VT == MVT::Flag) 236ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 237ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman else if (VT == MVT::Other) 238ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman TryUnfold = true; 239ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 240ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 241ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const SDValue &Op = N->getOperand(i); 242ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman MVT VT = Op.getNode()->getValueType(Op.getResNo()); 243ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (VT == MVT::Flag) 244ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 245ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 246ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 247ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (TryUnfold) { 248ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDNode*, 2> NewNodes; 249a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) 250ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 251ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 252ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DOUT << "Unfolding SU # " << SU->NodeNum << "\n"; 253ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(NewNodes.size() == 2 && "Expected a load folding node!"); 254ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 255ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman N = NewNodes[1]; 256ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SDNode *LoadNode = NewNodes[0]; 257ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned NumVals = N->getNumValues(); 258550f5afb68ce8f034991863cac65bef22a6554daDan Gohman unsigned OldNumVals = SU->getNode()->getNumValues(); 259ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0; i != NumVals; ++i) 260550f5afb68ce8f034991863cac65bef22a6554daDan Gohman DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); 261550f5afb68ce8f034991863cac65bef22a6554daDan Gohman DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), 262a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SDValue(LoadNode, 1)); 263ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 264ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *NewSU = CreateNewSUnit(N); 265ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 266ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman N->setNodeId(NewSU->NodeNum); 267ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 268ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 269ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0; i != TID.getNumOperands(); ++i) { 270ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (TID.getOperandConstraint(i, TOI::TIED_TO) != -1) { 271ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->isTwoAddress = true; 272ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman break; 273ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 274ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 275ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (TID.isCommutable()) 276ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->isCommutable = true; 277ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // FIXME: Calculate height / depth and propagate the changes? 278ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->Depth = SU->Depth; 279ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->Height = SU->Height; 280ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ComputeLatency(NewSU); 281ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 282ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // LoadNode may already exist. This can happen when there is another 283ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // load from the same location and producing the same type of value 284ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // but it has different alignment or volatileness. 285ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool isNewLoad = true; 286ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *LoadSU; 287ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (LoadNode->getNodeId() != -1) { 288ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadSU = &SUnits[LoadNode->getNodeId()]; 289ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman isNewLoad = false; 290ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } else { 291ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadSU = CreateNewSUnit(LoadNode); 292ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadNode->setNodeId(LoadSU->NodeNum); 293ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 294ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadSU->Depth = SU->Depth; 295ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadSU->Height = SU->Height; 296ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ComputeLatency(LoadSU); 297ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 298ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 299ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *ChainPred = NULL; 300ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> ChainSuccs; 301ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> LoadPreds; 302ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> NodePreds; 303ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> NodeSuccs; 304ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 305ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 306ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->isCtrl) 307ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ChainPred = I->Dep; 308550f5afb68ce8f034991863cac65bef22a6554daDan Gohman else if (I->Dep->getNode() && I->Dep->getNode()->isOperandOf(LoadNode)) 309ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadPreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false)); 310ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman else 311ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NodePreds.push_back(SDep(I->Dep, I->Reg, I->Cost, false, false)); 312ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 313ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 314ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 315ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->isCtrl) 316ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ChainSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost, 317ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I->isCtrl, I->isSpecial)); 318ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman else 319ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NodeSuccs.push_back(SDep(I->Dep, I->Reg, I->Cost, 320ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I->isCtrl, I->isSpecial)); 321ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 322ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 323ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (ChainPred) { 324ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RemovePred(SU, ChainPred, true, false); 325ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) 326ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(LoadSU, ChainPred, true, false); 327ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 328ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 329ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SDep *Pred = &LoadPreds[i]; 330ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isSpecial); 331ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) { 332ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(LoadSU, Pred->Dep, Pred->isCtrl, Pred->isSpecial, 333ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Pred->Reg, Pred->Cost); 334ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 335ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 336ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 337ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SDep *Pred = &NodePreds[i]; 338ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RemovePred(SU, Pred->Dep, Pred->isCtrl, Pred->isSpecial); 339ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(NewSU, Pred->Dep, Pred->isCtrl, Pred->isSpecial, 340ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Pred->Reg, Pred->Cost); 341ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 342ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 343ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SDep *Succ = &NodeSuccs[i]; 344ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isSpecial); 345ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(Succ->Dep, NewSU, Succ->isCtrl, Succ->isSpecial, 346ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Succ->Reg, Succ->Cost); 347ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 348ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 349ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SDep *Succ = &ChainSuccs[i]; 350ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RemovePred(Succ->Dep, SU, Succ->isCtrl, Succ->isSpecial); 351ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) { 352ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(Succ->Dep, LoadSU, Succ->isCtrl, Succ->isSpecial, 353ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Succ->Reg, Succ->Cost); 354ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 355ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 356ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) { 357ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(NewSU, LoadSU, false, false); 358ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 359ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 360ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++NumUnfolds; 361ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 362ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (NewSU->NumSuccsLeft == 0) { 363ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->isAvailable = true; 364ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NewSU; 365ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 366ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SU = NewSU; 367ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 368ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 369ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DOUT << "Duplicating SU # " << SU->NodeNum << "\n"; 370ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU = CreateClone(SU); 371ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 372ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // New SUnit has the exact same predecessors. 373ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 374ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) 375ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!I->isSpecial) { 376ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(NewSU, I->Dep, I->isCtrl, false, I->Reg, I->Cost); 377ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->Depth = std::max(NewSU->Depth, I->Dep->Depth+1); 378ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 379ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 380ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Only copy scheduled successors. Cut them from old node's successor 381ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // list and move them over. 382ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<std::pair<SUnit*, bool>, 4> DelDeps; 383ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 384ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 385ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->isSpecial) 386ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 387ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->Dep->isScheduled) { 388ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->Height = std::max(NewSU->Height, I->Dep->Height+1); 389ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(I->Dep, NewSU, I->isCtrl, false, I->Reg, I->Cost); 390ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl)); 391ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 392ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 393ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 394ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *Succ = DelDeps[i].first; 395ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool isCtrl = DelDeps[i].second; 396ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RemovePred(Succ, SU, isCtrl, false); 397ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 398ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 399ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++NumDups; 400ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NewSU; 401ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 402ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 403ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// InsertCCCopiesAndMoveSuccs - Insert expensive cross register class copies 404ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// and move all scheduled successors of the given SUnit to the last copy. 405ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanvoid ScheduleDAGFast::InsertCCCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 406ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass *DestRC, 407ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass *SrcRC, 408ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SUnit*, 2> &Copies) { 409ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CopyFromSU = CreateNewSUnit(NULL); 410ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyFromSU->CopySrcRC = SrcRC; 411ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyFromSU->CopyDstRC = DestRC; 412ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 413ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CopyToSU = CreateNewSUnit(NULL); 414ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyToSU->CopySrcRC = DestRC; 415ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyToSU->CopyDstRC = SrcRC; 416ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 417ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Only copy scheduled successors. Cut them from old node's successor 418ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // list and move them over. 419ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<std::pair<SUnit*, bool>, 4> DelDeps; 420ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 421ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 422ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->isSpecial) 423ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 424ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->Dep->isScheduled) { 425ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(I->Dep, CopyToSU, I->isCtrl, false, I->Reg, I->Cost); 426ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DelDeps.push_back(std::make_pair(I->Dep, I->isCtrl)); 427ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 428ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 429ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 430ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *Succ = DelDeps[i].first; 431ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool isCtrl = DelDeps[i].second; 432ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RemovePred(Succ, SU, isCtrl, false); 433ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 434ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 435ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(CopyFromSU, SU, false, false, Reg, -1); 436ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(CopyToSU, CopyFromSU, false, false, Reg, 1); 437ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 438ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Copies.push_back(CopyFromSU); 439ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Copies.push_back(CopyToSU); 440ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 441ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++NumCCCopies; 442ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 443ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 444ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// getPhysicalRegisterVT - Returns the ValueType of the physical register 445ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// definition of the specified node. 446ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// FIXME: Move to SelectionDAG? 447ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanstatic MVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, 448ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetInstrInfo *TII) { 449ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetInstrDesc &TID = TII->get(N->getMachineOpcode()); 450ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(TID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 451ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned NumRes = TID.getNumDefs(); 452ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (const unsigned *ImpDef = TID.getImplicitDefs(); *ImpDef; ++ImpDef) { 453ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (Reg == *ImpDef) 454ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman break; 455ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++NumRes; 456ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 457ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return N->getValueType(NumRes); 458ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 459ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 460ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 461ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// scheduling of the given node to satisfy live physical register dependencies. 462ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// If the specific node is the last one that's available to schedule, do 463ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// whatever is necessary (i.e. backtracking or cloning) to make it possible. 464ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanbool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, 465ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<unsigned, 4> &LRegs){ 466086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (NumLiveRegs == 0) 467ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return false; 468ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 469ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallSet<unsigned, 4> RegAdded; 470ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // If this node would clobber any "live" register, then it's not ready. 471ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 472ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 473ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (I->Cost < 0) { 474ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned Reg = I->Reg; 475086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (LiveRegDefs[Reg] && LiveRegDefs[Reg] != I->Dep) { 476ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (RegAdded.insert(Reg)) 477ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LRegs.push_back(Reg); 478ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 479ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (const unsigned *Alias = TRI->getAliasSet(Reg); 480ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman *Alias; ++Alias) 481086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != I->Dep) { 482ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (RegAdded.insert(*Alias)) 483ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LRegs.push_back(*Alias); 484ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 485ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 486ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 487ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 488ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = SU->FlaggedNodes.size()+1; i != e; ++i) { 489550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *Node = (i == 0) ? SU->getNode() : SU->FlaggedNodes[i-1]; 490ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!Node || !Node->isMachineOpcode()) 491ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 492ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetInstrDesc &TID = TII->get(Node->getMachineOpcode()); 493ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!TID.ImplicitDefs) 494ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 495ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (const unsigned *Reg = TID.ImplicitDefs; *Reg; ++Reg) { 496086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (LiveRegDefs[*Reg] && LiveRegDefs[*Reg] != SU) { 497ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (RegAdded.insert(*Reg)) 498ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LRegs.push_back(*Reg); 499ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 500ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (const unsigned *Alias = TRI->getAliasSet(*Reg); 501ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman *Alias; ++Alias) 502086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (LiveRegDefs[*Alias] && LiveRegDefs[*Alias] != SU) { 503ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (RegAdded.insert(*Alias)) 504ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LRegs.push_back(*Alias); 505ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 506ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 507ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 508ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return !LRegs.empty(); 509ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 510ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 511ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 512ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 513ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// schedulers. 514ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanvoid ScheduleDAGFast::ListScheduleBottomUp() { 515ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned CurCycle = 0; 516ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Add root to Available queue. 517ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!SUnits.empty()) { 518a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; 519ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); 520ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RootSU->isAvailable = true; 521ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AvailableQueue.push(RootSU); 522ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 523ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 524ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // While Available queue is not empty, grab the node with the highest 525ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // priority. If it is not ready put it back. Schedule the node. 526ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SUnit*, 4> NotReady; 527ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 528ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Sequence.reserve(SUnits.size()); 529ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman while (!AvailableQueue.empty()) { 530ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool Delayed = false; 531ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LRegsMap.clear(); 532ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CurSU = AvailableQueue.pop(); 533ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman while (CurSU) { 534ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (CurSU->CycleBound <= CurCycle) { 535ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<unsigned, 4> LRegs; 536ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 537ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman break; 538ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Delayed = true; 539ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LRegsMap.insert(std::make_pair(CurSU, LRegs)); 540ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 541ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 542ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CurSU->isPending = true; // This SU is not in AvailableQueue right now. 543ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NotReady.push_back(CurSU); 544ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CurSU = AvailableQueue.pop(); 545ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 546ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 547ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // All candidates are delayed due to live physical reg dependencies. 548ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Try code duplication or inserting cross class copies 549ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // to resolve it. 550ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (Delayed && !CurSU) { 551ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!CurSU) { 552ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Try duplicating the nodes that produces these 553ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // "expensive to copy" values to break the dependency. In case even 554ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // that doesn't work, insert cross class copies. 555ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *TrySU = NotReady[0]; 556ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 557ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(LRegs.size() == 1 && "Can't handle this yet!"); 558ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned Reg = LRegs[0]; 559ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *LRDef = LiveRegDefs[Reg]; 560ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *NewDef = CopyAndMoveSuccessors(LRDef); 561ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!NewDef) { 562ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Issue expensive cross register class copies. 563550f5afb68ce8f034991863cac65bef22a6554daDan Gohman MVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); 564ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass *RC = 565ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman TRI->getPhysicalRegisterRegClass(Reg, VT); 566ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 567ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!DestRC) { 568ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(false && "Don't know how to copy this physical register!"); 569ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman abort(); 570ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 571ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SUnit*, 2> Copies; 572ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman InsertCCCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 573ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DOUT << "Adding an edge from SU # " << TrySU->NodeNum 574ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman << " to SU #" << Copies.front()->NodeNum << "\n"; 575ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(TrySU, Copies.front(), true, true); 576ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewDef = Copies.back(); 577ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 578ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 579ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DOUT << "Adding an edge from SU # " << NewDef->NodeNum 580ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman << " to SU #" << TrySU->NodeNum << "\n"; 581ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegDefs[Reg] = NewDef; 582ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AddPred(NewDef, TrySU, true, true); 583ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman TrySU->isAvailable = false; 584ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CurSU = NewDef; 585ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 586ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 587ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!CurSU) { 588ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(false && "Unable to resolve live physical register dependencies!"); 589ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman abort(); 590ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 591ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 592ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 593ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Add the nodes that aren't ready back onto the available list. 594ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 595ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NotReady[i]->isPending = false; 596ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // May no longer be available due to backtracking. 597ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (NotReady[i]->isAvailable) 598ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AvailableQueue.push(NotReady[i]); 599ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 600ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NotReady.clear(); 601ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 602ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!CurSU) 603ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Sequence.push_back(0); 604ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman else { 605ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ScheduleNodeBottomUp(CurSU, CurCycle); 606ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Sequence.push_back(CurSU); 607ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 608ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++CurCycle; 609ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 610ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 611ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Reverse the order if it is bottom up. 612ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman std::reverse(Sequence.begin(), Sequence.end()); 613ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 614ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 615ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#ifndef NDEBUG 616ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Verify that all SUnits were scheduled. 617ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool AnyNotSched = false; 618ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned DeadNodes = 0; 619ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned Noops = 0; 620ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 621ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!SUnits[i].isScheduled) { 622ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 623ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++DeadNodes; 624ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 625ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 626ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!AnyNotSched) 627ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman cerr << "*** List scheduling failed! ***\n"; 628a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SUnits[i].dump(DAG); 629ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman cerr << "has not been scheduled!\n"; 630ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AnyNotSched = true; 631ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 632ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (SUnits[i].NumSuccsLeft != 0) { 633ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!AnyNotSched) 634ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman cerr << "*** List scheduling failed! ***\n"; 635a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SUnits[i].dump(DAG); 636ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman cerr << "has successors left!\n"; 637ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AnyNotSched = true; 638ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 639ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 640ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 641ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!Sequence[i]) 642ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++Noops; 643ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(!AnyNotSched); 644ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 645ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman "The number of nodes scheduled doesn't match the expected number!"); 646ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#endif 647ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 648ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 649ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 650ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// Public Constructor Functions 651ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 652ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 653ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanllvm::ScheduleDAG* llvm::createFastDAGScheduler(SelectionDAGISel *IS, 654ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SelectionDAG *DAG, 6559b75b373756288cd39489da7994207f50b31ee40Dan Gohman const TargetMachine *TM, 656ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman MachineBasicBlock *BB, bool) { 657a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman return new ScheduleDAGFast(DAG, BB, *TM); 658ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 659