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/SchedulerRegistry.h" 16d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "InstrEmitter.h" 17d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "ScheduleDAGSDNodes.h" 18d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 19d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/SmallSet.h" 20d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 2179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman#include "llvm/CodeGen/SelectionDAGISel.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 230b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/InlineAsm.h" 24ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#include "llvm/Support/Debug.h" 257d696d80409aad20bb5da0fc4eccab941dd371d4Torok Edwin#include "llvm/Support/ErrorHandling.h" 26bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner#include "llvm/Support/raw_ostream.h" 27d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 28d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 29ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanusing namespace llvm; 30ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 31ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan GohmanSTATISTIC(NumUnfolds, "Number of nodes unfolded"); 32ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan GohmanSTATISTIC(NumDups, "Number of duplicated nodes"); 33c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan ChengSTATISTIC(NumPRCopies, "Number of physical copies"); 34ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 35ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanstatic RegisterScheduler 36b8cab9227a0f6ffbdaae33e3c64268e265008a6aDan Gohman fastDAGScheduler("fast", "Fast suboptimal list scheduling", 37ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman createFastDAGScheduler); 38d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengstatic RegisterScheduler 39d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng linearizeDAGScheduler("linearize", "Linearize DAG, no scheduling", 40d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng createDAGLinearizer); 41d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 42ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 43ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmannamespace { 44ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// FastPriorityQueue - A degenerate priority queue that considers 45ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// all nodes to have the same priority. 46ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// 476726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewycky struct FastPriorityQueue { 48086ec9976ff6cee083de618429c78473491d5713Dan Gohman SmallVector<SUnit *, 16> Queue; 49ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 50ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool empty() const { return Queue.empty(); } 51dbdca36af8ee6028dbea93c639408ba95e5fda2eAndrew Trick 52ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void push(SUnit *U) { 53ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Queue.push_back(U); 54ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 55ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 56ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *pop() { 57ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (empty()) return NULL; 58ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *V = Queue.back(); 59ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Queue.pop_back(); 60ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return V; 61ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 62ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman }; 63ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 64ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 65ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// ScheduleDAGFast - The actual "fast" list scheduler implementation. 66ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// 676726b6d75a8b679068a58cb954ba97cf9d1690baNick Lewyckyclass ScheduleDAGFast : public ScheduleDAGSDNodes { 68ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanprivate: 69ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// AvailableQueue - The priority queue to use for the available SUnits. 70ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman FastPriorityQueue AvailableQueue; 71ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 72086ec9976ff6cee083de618429c78473491d5713Dan Gohman /// LiveRegDefs - A set of physical registers and their definition 73ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// that are "live". These nodes must be scheduled before any other nodes that 74ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// modifies the registers can be scheduled. 75086ec9976ff6cee083de618429c78473491d5713Dan Gohman unsigned NumLiveRegs; 76ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman std::vector<SUnit*> LiveRegDefs; 77ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman std::vector<unsigned> LiveRegCycles; 78ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 79ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanpublic: 8079ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman ScheduleDAGFast(MachineFunction &mf) 8179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman : ScheduleDAGSDNodes(mf) {} 82ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 83ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void Schedule(); 84ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 8554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// AddPred - adds a predecessor edge to SUnit SU. 86ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman /// This returns true if this is a new predecessor. 87ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman void AddPred(SUnit *SU, const SDep &D) { 88ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman SU->addPred(D); 8954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 90ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 9154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// RemovePred - removes a predecessor edge from SUnit SU. 9254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// This returns true if an edge was removed. 93ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman void RemovePred(SUnit *SU, const SDep &D) { 94ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman SU->removePred(D); 9554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 96ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 97ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanprivate: 9854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void ReleasePred(SUnit *SU, SDep *PredEdge); 999e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman void ReleasePredecessors(SUnit *SU, unsigned CurCycle); 100ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void ScheduleNodeBottomUp(SUnit*, unsigned); 101ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CopyAndMoveSuccessors(SUnit*); 102c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng void InsertCopiesAndMoveSuccs(SUnit*, unsigned, 103c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass*, 104c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass*, 105c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SmallVector<SUnit*, 2>&); 106ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool DelayForLiveRegsBottomUp(SUnit*, SmallVector<unsigned, 4>&); 107ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman void ListScheduleBottomUp(); 1083f23744df4809eba94284e601e81489212c974d4Dan Gohman 109953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// forceUnitLatencies - The fast scheduler doesn't care about real latencies. 110953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick bool forceUnitLatencies() const { return true; } 111ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman}; 112ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} // end anonymous namespace 113ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 114ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 115ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// Schedule - Schedule the DAG using list scheduling. 116ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanvoid ScheduleDAGFast::Schedule() { 11733db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene DEBUG(dbgs() << "********** List Scheduling **********\n"); 118ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 119086ec9976ff6cee083de618429c78473491d5713Dan Gohman NumLiveRegs = 0; 120dbdca36af8ee6028dbea93c639408ba95e5fda2eAndrew Trick LiveRegDefs.resize(TRI->getNumRegs(), NULL); 121ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegCycles.resize(TRI->getNumRegs(), 0); 122ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 123c9a5b9e38b442c2ae6b115213a07df3fcd14708dDan Gohman // Build the scheduling graph. 12498976e4dcd18adbbe676048c0069e67346eb4adeDan Gohman BuildSchedGraph(NULL); 125ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 126ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DEBUG(for (unsigned su = 0, e = SUnits.size(); su != e; ++su) 1273cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman SUnits[su].dumpAll(this)); 128ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 129ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Execute the actual scheduling loop. 130ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ListScheduleBottomUp(); 131ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 132ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 133ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 134ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// Bottom-Up Scheduling 135ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 136ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 137ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// ReleasePred - Decrement the NumSuccsLeft count of a predecessor. Add it to 138ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// the AvailableQueue if the count reaches zero. Also update its cycle bound. 13954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohmanvoid ScheduleDAGFast::ReleasePred(SUnit *SU, SDep *PredEdge) { 14054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *PredSU = PredEdge->getSUnit(); 141c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner 142ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#ifndef NDEBUG 143c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (PredSU->NumSuccsLeft == 0) { 14433db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 1453cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman PredSU->dump(this); 14633db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene dbgs() << " has been released too many times!\n"; 147c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable(0); 148ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 149ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#endif 150c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner --PredSU->NumSuccsLeft; 151c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner 1529e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman // If all the node's successors are scheduled, this node is ready 1539e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman // to be scheduled. Ignore the special EntrySU node. 1549e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman if (PredSU->NumSuccsLeft == 0 && PredSU != &EntrySU) { 155ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman PredSU->isAvailable = true; 156ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AvailableQueue.push(PredSU); 157ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 158ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 159ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 1609e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohmanvoid ScheduleDAGFast::ReleasePredecessors(SUnit *SU, unsigned CurCycle) { 161ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Bottom up: release predecessors 162ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 163ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 16454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman ReleasePred(SU, &*I); 16554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep()) { 166ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // This is a physical register dependency and it's impossible or 167dbdca36af8ee6028dbea93c639408ba95e5fda2eAndrew Trick // expensive to copy the register. Make sure nothing that can 168ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // clobber the register is scheduled between the predecessor and 169ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // this node. 17054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (!LiveRegDefs[I->getReg()]) { 171086ec9976ff6cee083de618429c78473491d5713Dan Gohman ++NumLiveRegs; 17254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegDefs[I->getReg()] = I->getSUnit(); 17354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegCycles[I->getReg()] = CurCycle; 174ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 175ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 176ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 1779e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman} 1789e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 1799e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman/// ScheduleNodeBottomUp - Add the node to the schedule. Decrement the pending 1809e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman/// count of its predecessors. If a predecessor pending count is zero, add it to 1819e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman/// the Available queue. 1829e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohmanvoid ScheduleDAGFast::ScheduleNodeBottomUp(SUnit *SU, unsigned CurCycle) { 18333db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 1849e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman DEBUG(SU->dump(this)); 1859e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 1869e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman assert(CurCycle >= SU->getHeight() && "Node scheduled below its height!"); 1879e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SU->setHeightToAtLeast(CurCycle); 1889e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman Sequence.push_back(SU); 1899e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 1909e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman ReleasePredecessors(SU, CurCycle); 191ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 192ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Release all the implicit physical register defs that are live. 193ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 194ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 19554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep()) { 1963f23744df4809eba94284e601e81489212c974d4Dan Gohman if (LiveRegCycles[I->getReg()] == I->getSUnit()->getHeight()) { 197086ec9976ff6cee083de618429c78473491d5713Dan Gohman assert(NumLiveRegs > 0 && "NumLiveRegs is already zero!"); 19854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(LiveRegDefs[I->getReg()] == SU && 199ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman "Physical register dependency violated?"); 200086ec9976ff6cee083de618429c78473491d5713Dan Gohman --NumLiveRegs; 20154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegDefs[I->getReg()] = NULL; 20254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LiveRegCycles[I->getReg()] = 0; 203ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 204ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 205ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 206ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 207ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SU->isScheduled = true; 208ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 209ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 210ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// CopyAndMoveSuccessors - Clone the specified node and move its scheduled 211ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// successors to the newly created node. 212ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan GohmanSUnit *ScheduleDAGFast::CopyAndMoveSuccessors(SUnit *SU) { 21329d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner if (SU->getNode()->getGluedNode()) 214ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 215ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 216550f5afb68ce8f034991863cac65bef22a6554daDan Gohman SDNode *N = SU->getNode(); 217ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!N) 218ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 219ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 220ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *NewSU; 221ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool TryUnfold = false; 222ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = N->getNumValues(); i != e; ++i) { 223e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT VT = N->getValueType(i); 224f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner if (VT == MVT::Glue) 225ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 226825b72b0571821bf2d378749f69d6c4cfb52d2f9Owen Anderson else if (VT == MVT::Other) 227ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman TryUnfold = true; 228ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 229ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = N->getNumOperands(); i != e; ++i) { 230ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const SDValue &Op = N->getOperand(i); 231e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT VT = Op.getNode()->getValueType(Op.getResNo()); 232f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner if (VT == MVT::Glue) 233ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 234ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 235ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 236ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (TryUnfold) { 237ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDNode*, 2> NewNodes; 238a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman if (!TII->unfoldMemoryOperand(*DAG, N, NewNodes)) 239ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NULL; 240ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 24133db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene DEBUG(dbgs() << "Unfolding SU # " << SU->NodeNum << "\n"); 242ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(NewNodes.size() == 2 && "Expected a load folding node!"); 243ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 244ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman N = NewNodes[1]; 245ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SDNode *LoadNode = NewNodes[0]; 246ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned NumVals = N->getNumValues(); 247550f5afb68ce8f034991863cac65bef22a6554daDan Gohman unsigned OldNumVals = SU->getNode()->getNumValues(); 248ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0; i != NumVals; ++i) 249550f5afb68ce8f034991863cac65bef22a6554daDan Gohman DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), i), SDValue(N, i)); 250550f5afb68ce8f034991863cac65bef22a6554daDan Gohman DAG->ReplaceAllUsesOfValueWith(SDValue(SU->getNode(), OldNumVals-1), 251a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SDValue(LoadNode, 1)); 252ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 253953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick SUnit *NewSU = newSUnit(N); 254ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(N->getNodeId() == -1 && "Node already inserted!"); 255ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman N->setNodeId(NewSU->NodeNum); 256dbdca36af8ee6028dbea93c639408ba95e5fda2eAndrew Trick 257e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); 258e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng for (unsigned i = 0; i != MCID.getNumOperands(); ++i) { 259e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.getOperandConstraint(i, MCOI::TIED_TO) != -1) { 260ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->isTwoAddress = true; 261ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman break; 262ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 263ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 264e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (MCID.isCommutable()) 265ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->isCommutable = true; 266ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 267ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // LoadNode may already exist. This can happen when there is another 268ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // load from the same location and producing the same type of value 269ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // but it has different alignment or volatileness. 270ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool isNewLoad = true; 271ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *LoadSU; 272ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (LoadNode->getNodeId() != -1) { 273ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadSU = &SUnits[LoadNode->getNodeId()]; 274ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman isNewLoad = false; 275ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } else { 276953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick LoadSU = newSUnit(LoadNode); 277ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LoadNode->setNodeId(LoadSU->NodeNum); 278ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 279ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 28054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep ChainPred; 281ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> ChainSuccs; 282ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> LoadPreds; 283ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> NodePreds; 284ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SDep, 4> NodeSuccs; 285ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 286ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 28754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) 28854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman ChainPred = *I; 28954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman else if (I->getSUnit()->getNode() && 29054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman I->getSUnit()->getNode()->isOperandOf(LoadNode)) 29154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman LoadPreds.push_back(*I); 292ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman else 29354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman NodePreds.push_back(*I); 294ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 295ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 296ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 29754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isCtrl()) 29854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman ChainSuccs.push_back(*I); 299ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman else 30054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman NodeSuccs.push_back(*I); 301ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 302ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 30354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (ChainPred.getSUnit()) { 30454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SU, ChainPred); 305ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) 30654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(LoadSU, ChainPred); 307ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 308ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = LoadPreds.size(); i != e; ++i) { 30954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman const SDep &Pred = LoadPreds[i]; 31054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SU, Pred); 311ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) { 31254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(LoadSU, Pred); 313ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 314ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 315ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = NodePreds.size(); i != e; ++i) { 31654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman const SDep &Pred = NodePreds[i]; 31754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SU, Pred); 31854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(NewSU, Pred); 319ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 320ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = NodeSuccs.size(); i != e; ++i) { 32154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = NodeSuccs[i]; 32254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccDep = D.getSUnit(); 32354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(SU); 32454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SuccDep, D); 32554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(NewSU); 32654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccDep, D); 327ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 328ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = ChainSuccs.size(); i != e; ++i) { 32954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = ChainSuccs[i]; 33054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccDep = D.getSUnit(); 33154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(SU); 33254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(SuccDep, D); 333ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) { 33454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(LoadSU); 33554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccDep, D); 336ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 337dbdca36af8ee6028dbea93c639408ba95e5fda2eAndrew Trick } 338ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (isNewLoad) { 339a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep D(LoadSU, SDep::Barrier); 340a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick D.setLatency(LoadSU->Latency); 341a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick AddPred(NewSU, D); 342ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 343ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 344ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++NumUnfolds; 345ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 346ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (NewSU->NumSuccsLeft == 0) { 347ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewSU->isAvailable = true; 348ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NewSU; 349ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 350ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SU = NewSU; 351ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 352ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 35333db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene DEBUG(dbgs() << "Duplicating SU # " << SU->NodeNum << "\n"); 354cdb260de83e209cd97632343e03343da3629d59fDan Gohman NewSU = Clone(SU); 355ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 356ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // New SUnit has the exact same predecessors. 357ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 358ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) 3593f23744df4809eba94284e601e81489212c974d4Dan Gohman if (!I->isArtificial()) 36054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(NewSU, *I); 361ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 362ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Only copy scheduled successors. Cut them from old node's successor 363ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // list and move them over. 36454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 365ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 366ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 36754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 368ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 36954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccSU = I->getSUnit(); 37054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (SuccSU->isScheduled) { 37154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = *I; 37254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(NewSU); 37354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccSU, D); 37454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(SU); 37554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman DelDeps.push_back(std::make_pair(SuccSU, D)); 376ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 377ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 378c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) 37954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(DelDeps[i].first, DelDeps[i].second); 380ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 381ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++NumDups; 382ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return NewSU; 383ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 384ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 385c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// InsertCopiesAndMoveSuccs - Insert register copies and move all 386c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng/// scheduled successors of the given SUnit to the last copy. 387c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Chengvoid ScheduleDAGFast::InsertCopiesAndMoveSuccs(SUnit *SU, unsigned Reg, 388ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass *DestRC, 389ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetRegisterClass *SrcRC, 390ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SUnit*, 2> &Copies) { 391953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick SUnit *CopyFromSU = newSUnit(static_cast<SDNode *>(NULL)); 392ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyFromSU->CopySrcRC = SrcRC; 393ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyFromSU->CopyDstRC = DestRC; 394ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 395953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick SUnit *CopyToSU = newSUnit(static_cast<SDNode *>(NULL)); 396ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyToSU->CopySrcRC = DestRC; 397ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CopyToSU->CopyDstRC = SrcRC; 398ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 399ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Only copy scheduled successors. Cut them from old node's successor 400ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // list and move them over. 40154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SmallVector<std::pair<SUnit *, SDep>, 4> DelDeps; 402ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 403ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 40454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 405ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 40654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SuccSU = I->getSUnit(); 40754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (SuccSU->isScheduled) { 40854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep D = *I; 40954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman D.setSUnit(CopyToSU); 41054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman AddPred(SuccSU, D); 41154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman DelDeps.push_back(std::make_pair(SuccSU, *I)); 412ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 413ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 414ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = DelDeps.size(); i != e; ++i) { 41554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman RemovePred(DelDeps[i].first, DelDeps[i].second); 416ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 417a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep FromDep(SU, SDep::Data, Reg); 418a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick FromDep.setLatency(SU->Latency); 419a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick AddPred(CopyFromSU, FromDep); 420a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep ToDep(CopyFromSU, SDep::Data, 0); 421a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick ToDep.setLatency(CopyFromSU->Latency); 422a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick AddPred(CopyToSU, ToDep); 423ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 424ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Copies.push_back(CopyFromSU); 425ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Copies.push_back(CopyToSU); 426ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 427c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng ++NumPRCopies; 428ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 429ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 430ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// getPhysicalRegisterVT - Returns the ValueType of the physical register 431ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// definition of the specified node. 432ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// FIXME: Move to SelectionDAG? 433e50ed30282bb5b4a9ed952580523f2dda16215acOwen Andersonstatic EVT getPhysicalRegisterVT(SDNode *N, unsigned Reg, 434ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman const TargetInstrInfo *TII) { 435e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = TII->get(N->getMachineOpcode()); 436e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng assert(MCID.ImplicitDefs && "Physical reg def must be in implicit def list!"); 437e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng unsigned NumRes = MCID.getNumDefs(); 438fac259814923d091942b230e7bd002a8d1130bc3Craig Topper for (const uint16_t *ImpDef = MCID.getImplicitDefs(); *ImpDef; ++ImpDef) { 439ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (Reg == *ImpDef) 440ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman break; 441ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++NumRes; 442ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 443ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return N->getValueType(NumRes); 444ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 445ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 4466cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen/// CheckForLiveRegDef - Return true and update live register vector if the 4476cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen/// specified register def of the specified SUnit clobbers any "live" registers. 4486cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesenstatic bool CheckForLiveRegDef(SUnit *SU, unsigned Reg, 4496cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen std::vector<SUnit*> &LiveRegDefs, 4506cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen SmallSet<unsigned, 4> &RegAdded, 4516cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen SmallVector<unsigned, 4> &LRegs, 4526cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen const TargetRegisterInfo *TRI) { 4536cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen bool Added = false; 4548c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen for (MCRegAliasIterator AI(Reg, TRI, true); AI.isValid(); ++AI) { 4558c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen if (LiveRegDefs[*AI] && LiveRegDefs[*AI] != SU) { 4568c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen if (RegAdded.insert(*AI)) { 4578c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen LRegs.push_back(*AI); 4586cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen Added = true; 4596cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen } 4606cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen } 4618c70ea47fae6d61441d150cbe9431cf5e06222e5Jakob Stoklund Olesen } 4626cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen return Added; 4636cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen} 4646cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen 465ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// DelayForLiveRegsBottomUp - Returns true if it is necessary to delay 466ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// scheduling of the given node to satisfy live physical register dependencies. 467ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// If the specific node is the last one that's available to schedule, do 468ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// whatever is necessary (i.e. backtracking or cloning) to make it possible. 469ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanbool ScheduleDAGFast::DelayForLiveRegsBottomUp(SUnit *SU, 470ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<unsigned, 4> &LRegs){ 471086ec9976ff6cee083de618429c78473491d5713Dan Gohman if (NumLiveRegs == 0) 472ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return false; 473ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 474ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallSet<unsigned, 4> RegAdded; 475ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // If this node would clobber any "live" register, then it's not ready. 476ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 477ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman I != E; ++I) { 47854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep()) { 4796cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen CheckForLiveRegDef(I->getSUnit(), I->getReg(), LiveRegDefs, 4806cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen RegAdded, LRegs, TRI); 481ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 482ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 483ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 48429d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner for (SDNode *Node = SU->getNode(); Node; Node = Node->getGluedNode()) { 4856cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen if (Node->getOpcode() == ISD::INLINEASM) { 4866cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen // Inline asm can clobber physical defs. 4876cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen unsigned NumOps = Node->getNumOperands(); 488f1b4eafbfec976f939ec0ea3e8acf91cef5363e3Chris Lattner if (Node->getOperand(NumOps-1).getValueType() == MVT::Glue) 48929d8f0cae425f1bba583565227eaebf58f26ce73Chris Lattner --NumOps; // Ignore the glue operand. 4906cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen 4916cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen for (unsigned i = InlineAsm::Op_FirstOperand; i != NumOps;) { 4926cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen unsigned Flags = 4936cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen cast<ConstantSDNode>(Node->getOperand(i))->getZExtValue(); 4946cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen unsigned NumVals = InlineAsm::getNumOperandRegisters(Flags); 4956cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen 4966cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen ++i; // Skip the ID value. 4976cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen if (InlineAsm::isRegDefKind(Flags) || 498f792fa90f1125553008659c743cba85b9b5d2e5eJakob Stoklund Olesen InlineAsm::isRegDefEarlyClobberKind(Flags) || 499f792fa90f1125553008659c743cba85b9b5d2e5eJakob Stoklund Olesen InlineAsm::isClobberKind(Flags)) { 5006cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen // Check for def of register or earlyclobber register. 5016cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen for (; NumVals; --NumVals, ++i) { 5026cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen unsigned Reg = cast<RegisterSDNode>(Node->getOperand(i))->getReg(); 5036cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen if (TargetRegisterInfo::isPhysicalRegister(Reg)) 5046cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen CheckForLiveRegDef(SU, Reg, LiveRegDefs, RegAdded, LRegs, TRI); 5056cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen } 5066cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen } else 5076cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen i += NumVals; 5086cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen } 5096cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen continue; 5106cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen } 511d23e0f81bc76902052e9198cad3a0d87a412a632Dan Gohman if (!Node->isMachineOpcode()) 512ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 513e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc &MCID = TII->get(Node->getMachineOpcode()); 514e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng if (!MCID.ImplicitDefs) 515ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman continue; 516fac259814923d091942b230e7bd002a8d1130bc3Craig Topper for (const uint16_t *Reg = MCID.getImplicitDefs(); *Reg; ++Reg) { 5176cf64a631a1522c137a1fcf88858ea1336822abfDale Johannesen CheckForLiveRegDef(SU, *Reg, LiveRegDefs, RegAdded, LRegs, TRI); 518ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 519ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 520ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman return !LRegs.empty(); 521ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 522ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 523ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 524ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// ListScheduleBottomUp - The main loop of list scheduling for bottom-up 525ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman/// schedulers. 526ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohmanvoid ScheduleDAGFast::ListScheduleBottomUp() { 527ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned CurCycle = 0; 5289e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 5299e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman // Release any predecessors of the special Exit node. 5309e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman ReleasePredecessors(&ExitSU, CurCycle); 5319e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 532ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Add root to Available queue. 533ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!SUnits.empty()) { 534a23b3b803e3c65e84d6cadaa221de8b256cbe28dDan Gohman SUnit *RootSU = &SUnits[DAG->getRoot().getNode()->getNodeId()]; 535ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(RootSU->Succs.empty() && "Graph root shouldn't have successors!"); 536ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman RootSU->isAvailable = true; 537ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AvailableQueue.push(RootSU); 538ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 539ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 540ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // While Available queue is not empty, grab the node with the highest 541ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // priority. If it is not ready put it back. Schedule the node. 542ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SUnit*, 4> NotReady; 543ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman DenseMap<SUnit*, SmallVector<unsigned, 4> > LRegsMap; 544ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman Sequence.reserve(SUnits.size()); 545ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman while (!AvailableQueue.empty()) { 546ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman bool Delayed = false; 547ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LRegsMap.clear(); 548ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *CurSU = AvailableQueue.pop(); 549ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman while (CurSU) { 550e93483d855af7acf831d1d8c3c77ed117f0df4d3Dan Gohman SmallVector<unsigned, 4> LRegs; 551e93483d855af7acf831d1d8c3c77ed117f0df4d3Dan Gohman if (!DelayForLiveRegsBottomUp(CurSU, LRegs)) 552e93483d855af7acf831d1d8c3c77ed117f0df4d3Dan Gohman break; 553e93483d855af7acf831d1d8c3c77ed117f0df4d3Dan Gohman Delayed = true; 554e93483d855af7acf831d1d8c3c77ed117f0df4d3Dan Gohman LRegsMap.insert(std::make_pair(CurSU, LRegs)); 555ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 556ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CurSU->isPending = true; // This SU is not in AvailableQueue right now. 557ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NotReady.push_back(CurSU); 558ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CurSU = AvailableQueue.pop(); 559ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 560ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 561ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // All candidates are delayed due to live physical reg dependencies. 562ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Try code duplication or inserting cross class copies 563ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // to resolve it. 564ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (Delayed && !CurSU) { 565ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!CurSU) { 566ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Try duplicating the nodes that produces these 567ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // "expensive to copy" values to break the dependency. In case even 568ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // that doesn't work, insert cross class copies. 569ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *TrySU = NotReady[0]; 570ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<unsigned, 4> &LRegs = LRegsMap[TrySU]; 571ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman assert(LRegs.size() == 1 && "Can't handle this yet!"); 572ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman unsigned Reg = LRegs[0]; 573ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SUnit *LRDef = LiveRegDefs[Reg]; 574e50ed30282bb5b4a9ed952580523f2dda16215acOwen Anderson EVT VT = getPhysicalRegisterVT(LRDef->getNode(), Reg, TII); 575c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *RC = 576d31f972bd33de85071c716f69bf5c6d735f730f2Rafael Espindola TRI->getMinimalPhysRegClass(Reg, VT); 577c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng const TargetRegisterClass *DestRC = TRI->getCrossCopyRegClass(RC); 578c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng 579b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng // If cross copy register class is the same as RC, then it must be 580b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng // possible copy the value directly. Do not try duplicate the def. 581b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng // If cross copy register class is not the same as RC, then it's 582b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng // possible to copy the value but it require cross register class copies 583b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng // and it is expensive. 584b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng // If cross copy register class is null, then it's not possible to copy 585b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng // the value at all. 586c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng SUnit *NewDef = 0; 587b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng if (DestRC != RC) { 588c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng NewDef = CopyAndMoveSuccessors(LRDef); 589b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng if (!DestRC && !NewDef) 590b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng report_fatal_error("Can't handle live physical " 591b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng "register dependency!"); 592b0519e15f70cef7ba16b712f258d4782ade17e13Evan Cheng } 593ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!NewDef) { 594c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng // Issue copies, these can be expensive cross register class copies. 595ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman SmallVector<SUnit*, 2> Copies; 596c29a56dedbe4297dad94b9bf2e19035c5903fd1fEvan Cheng InsertCopiesAndMoveSuccs(LRDef, Reg, DestRC, RC, Copies); 59733db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene DEBUG(dbgs() << "Adding an edge from SU # " << TrySU->NodeNum 598bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner << " to SU #" << Copies.front()->NodeNum << "\n"); 599a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick AddPred(TrySU, SDep(Copies.front(), SDep::Artificial)); 600ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NewDef = Copies.back(); 601ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 602ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 60333db62ce23790b5db57dad66e77a1a06cccfb06eDavid Greene DEBUG(dbgs() << "Adding an edge from SU # " << NewDef->NodeNum 604bbbfa99d3d18fe9f20265305e833666645ada528Chris Lattner << " to SU #" << TrySU->NodeNum << "\n"); 605ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman LiveRegDefs[Reg] = NewDef; 606a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick AddPred(NewDef, SDep(TrySU, SDep::Artificial)); 607ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman TrySU->isAvailable = false; 608ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman CurSU = NewDef; 609ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 610ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 611ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (!CurSU) { 612c23197a26f34f559ea9797de51e187087c039c42Torok Edwin llvm_unreachable("Unable to resolve live physical register dependencies!"); 613ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 614ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 615ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 616ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // Add the nodes that aren't ready back onto the available list. 617ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman for (unsigned i = 0, e = NotReady.size(); i != e; ++i) { 618ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NotReady[i]->isPending = false; 619ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman // May no longer be available due to backtracking. 620ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman if (NotReady[i]->isAvailable) 621ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman AvailableQueue.push(NotReady[i]); 622ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 623ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman NotReady.clear(); 624ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 62547d1a214a7013d12140a0c4972d7ba761150dfd4Dan Gohman if (CurSU) 626ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ScheduleNodeBottomUp(CurSU, CurCycle); 627ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman ++CurCycle; 628ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman } 629ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 630937d2d86242339c17e77a6016b96999f439a1714Dan Gohman // Reverse the order since it is bottom up. 631ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman std::reverse(Sequence.begin(), Sequence.end()); 632937d2d86242339c17e77a6016b96999f439a1714Dan Gohman 633ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#ifndef NDEBUG 6344c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick VerifyScheduledSequence(/*isBottomUp=*/true); 635ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman#endif 636ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 637ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 638d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 63963a4c24616fafa2b86d6391308ffd93e012115e4Benjamin Kramernamespace { 640d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng//===----------------------------------------------------------------------===// 641d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng// ScheduleDAGLinearize - No scheduling scheduler, it simply linearize the 642d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng// DAG in topological order. 643d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng// IMPORTANT: this may not work for targets with phyreg dependency. 644d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng// 645d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengclass ScheduleDAGLinearize : public ScheduleDAGSDNodes { 646d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengpublic: 647d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng ScheduleDAGLinearize(MachineFunction &mf) : ScheduleDAGSDNodes(mf) {} 648d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 649d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng void Schedule(); 650d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 651d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng MachineBasicBlock *EmitSchedule(MachineBasicBlock::iterator &InsertPos); 652d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 653d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengprivate: 654d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng std::vector<SDNode*> Sequence; 655d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DenseMap<SDNode*, SDNode*> GluedMap; // Cache glue to its user 656d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 657d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng void ScheduleNode(SDNode *N); 658d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng}; 65963a4c24616fafa2b86d6391308ffd93e012115e4Benjamin Kramer} // end anonymous namespace 660d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 661d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengvoid ScheduleDAGLinearize::ScheduleNode(SDNode *N) { 662d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (N->getNodeId() != 0) 663d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng llvm_unreachable(0); 664d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 665d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (!N->isMachineOpcode() && 666d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng (N->getOpcode() == ISD::EntryToken || isPassiveNode(N))) 667d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // These nodes do not need to be translated into MIs. 668d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng return; 669d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 670d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DEBUG(dbgs() << "\n*** Scheduling: "); 671d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DEBUG(N->dump(DAG)); 672d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng Sequence.push_back(N); 673d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 674d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned NumOps = N->getNumOperands(); 675d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (unsigned NumLeft = NumOps) { 676d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *GluedOpN = 0; 677d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng do { 678d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng const SDValue &Op = N->getOperand(NumLeft-1); 679d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *OpN = Op.getNode(); 680d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 681d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (NumLeft == NumOps && Op.getValueType() == MVT::Glue) { 682d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // Schedule glue operand right above N. 683d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng GluedOpN = OpN; 684d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng assert(OpN->getNodeId() != 0 && "Glue operand not ready?"); 685d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng OpN->setNodeId(0); 686d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng ScheduleNode(OpN); 687d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng continue; 688d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } 689d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 690d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (OpN == GluedOpN) 691d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // Glue operand is already scheduled. 692d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng continue; 693d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 694d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DenseMap<SDNode*, SDNode*>::iterator DI = GluedMap.find(OpN); 695d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (DI != GluedMap.end() && DI->second != N) 696d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // Users of glues are counted against the glued users. 697d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng OpN = DI->second; 698d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 699d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned Degree = OpN->getNodeId(); 700d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng assert(Degree > 0 && "Predecessor over-released!"); 701d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng OpN->setNodeId(--Degree); 702d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (Degree == 0) 703d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng ScheduleNode(OpN); 704d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } while (--NumLeft); 705d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } 706d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng} 707d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 708d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng/// findGluedUser - Find the representative use of a glue value by walking 709d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng/// the use chain. 710d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengstatic SDNode *findGluedUser(SDNode *N) { 711d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng while (SDNode *Glued = N->getGluedUser()) 712d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng N = Glued; 713d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng return N; 714d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng} 715d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 716d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengvoid ScheduleDAGLinearize::Schedule() { 717d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DEBUG(dbgs() << "********** DAG Linearization **********\n"); 718d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 719d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SmallVector<SDNode*, 8> Glues; 720d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned DAGSize = 0; 721d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng for (SelectionDAG::allnodes_iterator I = DAG->allnodes_begin(), 722d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng E = DAG->allnodes_end(); I != E; ++I) { 723d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *N = I; 724d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 725d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // Use node id to record degree. 726d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned Degree = N->use_size(); 727d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng N->setNodeId(Degree); 728d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned NumVals = N->getNumValues(); 729d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (NumVals && N->getValueType(NumVals-1) == MVT::Glue && 730d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng N->hasAnyUseOfValue(NumVals-1)) { 731d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *User = findGluedUser(N); 732d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (User) { 733d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng Glues.push_back(N); 734d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng GluedMap.insert(std::make_pair(N, User)); 735d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } 736d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } 737d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 738d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (N->isMachineOpcode() || 739d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng (N->getOpcode() != ISD::EntryToken && !isPassiveNode(N))) 740d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng ++DAGSize; 741d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } 742d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 743d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng for (unsigned i = 0, e = Glues.size(); i != e; ++i) { 744d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *Glue = Glues[i]; 745d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *GUser = GluedMap[Glue]; 746d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned Degree = Glue->getNodeId(); 747d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned UDegree = GUser->getNodeId(); 748d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 749d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // Glue user must be scheduled together with the glue operand. So other 750d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // users of the glue operand must be treated as its users. 751d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *ImmGUser = Glue->getGluedUser(); 752d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng for (SDNode::use_iterator ui = Glue->use_begin(), ue = Glue->use_end(); 753d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng ui != ue; ++ui) 754d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng if (*ui == ImmGUser) 755d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng --Degree; 756d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng GUser->setNodeId(UDegree + Degree); 757d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng Glue->setNodeId(1); 758d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } 759d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 760d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng Sequence.reserve(DAGSize); 761d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng ScheduleNode(DAG->getRoot().getNode()); 762d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng} 763d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 764d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan ChengMachineBasicBlock* 765d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan ChengScheduleDAGLinearize::EmitSchedule(MachineBasicBlock::iterator &InsertPos) { 766d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng InstrEmitter Emitter(BB, InsertPos); 767d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DenseMap<SDValue, unsigned> VRBaseMap; 768d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 769d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DEBUG({ 770d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng dbgs() << "\n*** Final schedule ***\n"; 771d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng }); 772d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 773d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng // FIXME: Handle dbg_values. 774d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng unsigned NumNodes = Sequence.size(); 775d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng for (unsigned i = 0; i != NumNodes; ++i) { 776d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng SDNode *N = Sequence[NumNodes-i-1]; 777d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DEBUG(N->dump(DAG)); 778d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng Emitter.EmitNode(N, false, false, VRBaseMap); 779d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng } 780d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 781d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng DEBUG(dbgs() << '\n'); 782d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 783d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng InsertPos = Emitter.getInsertPos(); 784d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng return Emitter.getBlock(); 785d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng} 786d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 787ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 788ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman// Public Constructor Functions 789ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman//===----------------------------------------------------------------------===// 790ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman 79147ac0f0c7c39289f5970688154e385be22b7f293Dan Gohmanllvm::ScheduleDAGSDNodes * 79298a366d547772010e94609e4584489b3e5ce0043Bill Wendlingllvm::createFastDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 79379ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman return new ScheduleDAGFast(*IS->MF); 794ee2e4035450a2d0d6159831e9b9cfa3ffd8da8bcDan Gohman} 795d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng 796d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengllvm::ScheduleDAGSDNodes * 797d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Chengllvm::createDAGLinearizer(SelectionDAGISel *IS, CodeGenOpt::Level) { 798d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng return new ScheduleDAGLinearize(*IS->MF); 799d4f759696d1bd0ba7c0e6eefd7ed8b556840419aEvan Cheng} 800