1ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===- ScheduleDAGVLIW.cpp - SelectionDAG list scheduler for VLIW -*- C++ -*-=// 2ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 3ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// The LLVM Compiler Infrastructure 4ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 5ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// This file is distributed under the University of Illinois Open Source 6ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// License. See LICENSE.TXT for details. 7ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 8ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 9ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 10ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// This implements a top-down list scheduler, using standard algorithms. 11ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// The basic approach uses a priority queue of available nodes to schedule. 12ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// One at a time, nodes are taken from the priority queue (thus in priority 13ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// order), checked for legality to schedule, and emitted if legal. 14ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 15ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// Nodes may not be legal to schedule either due to structural hazards (e.g. 16ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// pipeline or resource constraints) or because an input to the instruction has 17ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// not completed execution. 18ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// 19ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 20ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 21ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#define DEBUG_TYPE "pre-RA-sched" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/SchedulerRegistry.h" 23ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "ScheduleDAGSDNodes.h" 24d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 25ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/CodeGen/LatencyPriorityQueue.h" 26d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/CodeGen/ResourcePriorityQueue.h" 27ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 28ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/CodeGen/SelectionDAGISel.h" 290b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 30ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/Support/Debug.h" 31ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/Support/ErrorHandling.h" 32ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include "llvm/Support/raw_ostream.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 34d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 35ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#include <climits> 36ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickusing namespace llvm; 37ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 38ee498d3254b86bceb4f441741e9f442990647ce6Andrew TrickSTATISTIC(NumNoops , "Number of noops inserted"); 39ee498d3254b86bceb4f441741e9f442990647ce6Andrew TrickSTATISTIC(NumStalls, "Number of pipeline stalls"); 40ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 41ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickstatic RegisterScheduler 42ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick VLIWScheduler("vliw-td", "VLIW scheduler", 43ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick createVLIWDAGScheduler); 44ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 45ee498d3254b86bceb4f441741e9f442990647ce6Andrew Tricknamespace { 46ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 47ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This 48ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// supports / top-down scheduling. 49ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// 50ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickclass ScheduleDAGVLIW : public ScheduleDAGSDNodes { 51ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickprivate: 52ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// AvailableQueue - The priority queue to use for the available SUnits. 53ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// 54ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SchedulingPriorityQueue *AvailableQueue; 55ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 56ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// PendingQueue - This contains all of the instructions whose operands have 57ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// been issued, but their results are not ready yet (due to the latency of 58ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// the operation). Once the operands become available, the instruction is 59ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// added to the AvailableQueue. 60ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::vector<SUnit*> PendingQueue; 61ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 62ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// HazardRec - The hazard recognizer to use. 63ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ScheduleHazardRecognizer *HazardRec; 64ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 65ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick /// AA - AliasAnalysis for making memory reference queries. 66ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick AliasAnalysis *AA; 67ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 68ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickpublic: 69ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ScheduleDAGVLIW(MachineFunction &mf, 70ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick AliasAnalysis *aa, 71ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SchedulingPriorityQueue *availqueue) 72ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) { 73ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 74ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick const TargetMachine &tm = mf.getTarget(); 75ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HazardRec = tm.getInstrInfo()->CreateTargetHazardRecognizer(&tm, this); 76ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 77ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 78ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ~ScheduleDAGVLIW() { 79ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick delete HazardRec; 80ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick delete AvailableQueue; 81ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 82ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 83ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick void Schedule(); 84ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 85ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickprivate: 86ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick void releaseSucc(SUnit *SU, const SDep &D); 87ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick void releaseSuccessors(SUnit *SU); 88ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 89ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick void listScheduleTopDown(); 90ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick}; 91ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} // end anonymous namespace 92ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 93ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// Schedule - Schedule the DAG using list scheduling. 94ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ScheduleDAGVLIW::Schedule() { 95ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick DEBUG(dbgs() 96ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick << "********** List Scheduling BB#" << BB->getNumber() 97ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick << " '" << BB->getName() << "' **********\n"); 98ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 99ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Build the scheduling graph. 100ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick BuildSchedGraph(AA); 101ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 102ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick AvailableQueue->initNodes(SUnits); 103ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 104ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick listScheduleTopDown(); 105ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 106ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick AvailableQueue->releaseState(); 107ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 108ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 109ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 110ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// Top-Down Scheduling 111ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 112ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 113ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 114ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// the PendingQueue if the count reaches zero. Also update its cycle bound. 115ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) { 116ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *SuccSU = D.getSUnit(); 117ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 118ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#ifndef NDEBUG 119ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SuccSU->NumPredsLeft == 0) { 120ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick dbgs() << "*** Scheduling failed! ***\n"; 121ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SuccSU->dump(this); 122ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick dbgs() << " has been released too many times!\n"; 123ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick llvm_unreachable(0); 124ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 125ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#endif 126ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(!D.isWeak() && "unexpected artificial DAG edge"); 127ae692f2baedf53504af2715993b166950e185a55Andrew Trick 128ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick --SuccSU->NumPredsLeft; 129ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 130ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); 131ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 132ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If all the node's predecessors are scheduled, this node is ready 133ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // to be scheduled. Ignore the special ExitSU node. 134ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { 135ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick PendingQueue.push_back(SuccSU); 136ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 137ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 138ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 139ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) { 140ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Top down: release successors. 141ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 142ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick I != E; ++I) { 143ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick assert(!I->isAssignedRegDep() && 144ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick "The list-td scheduler doesn't yet support physreg dependencies!"); 145ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 146ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick releaseSucc(SU, *I); 147ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 148ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 149ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 150ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending 151ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// count of its successors. If a successor pending count is zero, add it to 152ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// the Available queue. 153ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 154ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 155ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick DEBUG(SU->dump(this)); 156ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 157ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Sequence.push_back(SU); 158ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 159ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SU->setDepthToAtLeast(CurCycle); 160ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 161ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick releaseSuccessors(SU); 162ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SU->isScheduled = true; 163953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick AvailableQueue->scheduledNode(SU); 164ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 165ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 166ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// listScheduleTopDown - The main loop of list scheduling for top-down 167ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// schedulers. 168ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickvoid ScheduleDAGVLIW::listScheduleTopDown() { 169ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick unsigned CurCycle = 0; 170ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 171ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Release any successors of the special Entry node. 172ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick releaseSuccessors(&EntrySU); 173ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 174ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // All leaves to AvailableQueue. 175ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 176ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // It is available if it has no predecessors. 177ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (SUnits[i].Preds.empty()) { 178ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick AvailableQueue->push(&SUnits[i]); 179ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnits[i].isAvailable = true; 180ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 181ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 182ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 183ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // While AvailableQueue is not empty, grab the node with the highest 184ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // priority. If it is not ready put it back. Schedule the node. 185ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick std::vector<SUnit*> NotReady; 186ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Sequence.reserve(SUnits.size()); 187ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick while (!AvailableQueue->empty() || !PendingQueue.empty()) { 188ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Check to see if any of the pending instructions are ready to issue. If 189ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // so, add them to the available queue. 190ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 191ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (PendingQueue[i]->getDepth() == CurCycle) { 192ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick AvailableQueue->push(PendingQueue[i]); 193ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick PendingQueue[i]->isAvailable = true; 194ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick PendingQueue[i] = PendingQueue.back(); 195ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick PendingQueue.pop_back(); 196ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick --i; --e; 197ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 198ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick else { 199ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?"); 200ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 201ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 202ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 203ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If there are no instructions available, don't try to issue anything, and 204ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // don't advance the hazard recognizer. 205ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (AvailableQueue->empty()) { 206ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Reset DFA state. 207953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick AvailableQueue->scheduledNode(0); 208ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ++CurCycle; 209ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick continue; 210ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 211ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 212ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *FoundSUnit = 0; 213ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 214ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick bool HasNoopHazards = false; 215ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick while (!AvailableQueue->empty()) { 216ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick SUnit *CurSUnit = AvailableQueue->pop(); 217ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 218ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ScheduleHazardRecognizer::HazardType HT = 219ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 220ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (HT == ScheduleHazardRecognizer::NoHazard) { 221ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick FoundSUnit = CurSUnit; 222ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick break; 223ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 224ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 225ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Remember if this is a noop hazard. 226ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 227ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 228ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NotReady.push_back(CurSUnit); 229ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 230ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 231ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Add the nodes that aren't ready back onto the available list. 232ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (!NotReady.empty()) { 233ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick AvailableQueue->push_all(NotReady); 234ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick NotReady.clear(); 235ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 236ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 237ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If we found a node to schedule, do it now. 238ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (FoundSUnit) { 239ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick scheduleNodeTopDown(FoundSUnit, CurCycle); 240ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HazardRec->EmitInstruction(FoundSUnit); 241ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 242ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // If this is a pseudo-op node, we don't want to increment the current 243ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // cycle. 244ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 245ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ++CurCycle; 246ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } else if (!HasNoopHazards) { 247ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Otherwise, we have a pipeline stall, but no other problem, just advance 248ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // the current cycle and try again. 249ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick DEBUG(dbgs() << "*** Advancing cycle, no work to do\n"); 250ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HazardRec->AdvanceCycle(); 251ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ++NumStalls; 252ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ++CurCycle; 253ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } else { 254ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // Otherwise, we have no instructions to issue and we have instructions 255ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // that will fault if we don't do this right. This is the case for 256ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick // processors without pipeline interlocks and other cases. 257ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick DEBUG(dbgs() << "*** Emitting noop\n"); 258ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick HazardRec->EmitNoop(); 259ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick Sequence.push_back(0); // NULL here means noop 260ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ++NumNoops; 261ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick ++CurCycle; 262ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 263ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick } 264ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 265ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#ifndef NDEBUG 2664c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick VerifyScheduledSequence(/*isBottomUp=*/false); 267ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick#endif 268ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 269ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 270ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 271ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick// Public Constructor Functions 272ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick//===----------------------------------------------------------------------===// 273ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick 274ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick/// createVLIWDAGScheduler - This creates a top-down list scheduler. 275ee498d3254b86bceb4f441741e9f442990647ce6Andrew TrickScheduleDAGSDNodes * 276ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trickllvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 277ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); 278ee498d3254b86bceb4f441741e9f442990647ce6Andrew Trick} 279