1234285Sdim//===- ScheduleDAGVLIW.cpp - SelectionDAG list scheduler for VLIW -*- C++ -*-=// 2234285Sdim// 3234285Sdim// The LLVM Compiler Infrastructure 4234285Sdim// 5234285Sdim// This file is distributed under the University of Illinois Open Source 6234285Sdim// License. See LICENSE.TXT for details. 7234285Sdim// 8234285Sdim//===----------------------------------------------------------------------===// 9234285Sdim// 10234285Sdim// This implements a top-down list scheduler, using standard algorithms. 11234285Sdim// The basic approach uses a priority queue of available nodes to schedule. 12234285Sdim// One at a time, nodes are taken from the priority queue (thus in priority 13234285Sdim// order), checked for legality to schedule, and emitted if legal. 14234285Sdim// 15234285Sdim// Nodes may not be legal to schedule either due to structural hazards (e.g. 16234285Sdim// pipeline or resource constraints) or because an input to the instruction has 17234285Sdim// not completed execution. 18234285Sdim// 19234285Sdim//===----------------------------------------------------------------------===// 20234285Sdim 21234285Sdim#define DEBUG_TYPE "pre-RA-sched" 22249423Sdim#include "llvm/CodeGen/SchedulerRegistry.h" 23234285Sdim#include "ScheduleDAGSDNodes.h" 24249423Sdim#include "llvm/ADT/Statistic.h" 25234285Sdim#include "llvm/CodeGen/LatencyPriorityQueue.h" 26249423Sdim#include "llvm/CodeGen/ResourcePriorityQueue.h" 27234285Sdim#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 28234285Sdim#include "llvm/CodeGen/SelectionDAGISel.h" 29249423Sdim#include "llvm/IR/DataLayout.h" 30234285Sdim#include "llvm/Support/Debug.h" 31234285Sdim#include "llvm/Support/ErrorHandling.h" 32234285Sdim#include "llvm/Support/raw_ostream.h" 33249423Sdim#include "llvm/Target/TargetInstrInfo.h" 34249423Sdim#include "llvm/Target/TargetRegisterInfo.h" 35234285Sdim#include <climits> 36234285Sdimusing namespace llvm; 37234285Sdim 38234285SdimSTATISTIC(NumNoops , "Number of noops inserted"); 39234285SdimSTATISTIC(NumStalls, "Number of pipeline stalls"); 40234285Sdim 41234285Sdimstatic RegisterScheduler 42234285Sdim VLIWScheduler("vliw-td", "VLIW scheduler", 43234285Sdim createVLIWDAGScheduler); 44234285Sdim 45234285Sdimnamespace { 46234285Sdim//===----------------------------------------------------------------------===// 47234285Sdim/// ScheduleDAGVLIW - The actual DFA list scheduler implementation. This 48234285Sdim/// supports / top-down scheduling. 49234285Sdim/// 50234285Sdimclass ScheduleDAGVLIW : public ScheduleDAGSDNodes { 51234285Sdimprivate: 52234285Sdim /// AvailableQueue - The priority queue to use for the available SUnits. 53234285Sdim /// 54234285Sdim SchedulingPriorityQueue *AvailableQueue; 55234285Sdim 56234285Sdim /// PendingQueue - This contains all of the instructions whose operands have 57234285Sdim /// been issued, but their results are not ready yet (due to the latency of 58234285Sdim /// the operation). Once the operands become available, the instruction is 59234285Sdim /// added to the AvailableQueue. 60234285Sdim std::vector<SUnit*> PendingQueue; 61234285Sdim 62234285Sdim /// HazardRec - The hazard recognizer to use. 63234285Sdim ScheduleHazardRecognizer *HazardRec; 64234285Sdim 65234285Sdim /// AA - AliasAnalysis for making memory reference queries. 66234285Sdim AliasAnalysis *AA; 67234285Sdim 68234285Sdimpublic: 69234285Sdim ScheduleDAGVLIW(MachineFunction &mf, 70234285Sdim AliasAnalysis *aa, 71234285Sdim SchedulingPriorityQueue *availqueue) 72234285Sdim : ScheduleDAGSDNodes(mf), AvailableQueue(availqueue), AA(aa) { 73234285Sdim 74234285Sdim const TargetMachine &tm = mf.getTarget(); 75234285Sdim HazardRec = tm.getInstrInfo()->CreateTargetHazardRecognizer(&tm, this); 76234285Sdim } 77234285Sdim 78234285Sdim ~ScheduleDAGVLIW() { 79234285Sdim delete HazardRec; 80234285Sdim delete AvailableQueue; 81234285Sdim } 82234285Sdim 83234285Sdim void Schedule(); 84234285Sdim 85234285Sdimprivate: 86234285Sdim void releaseSucc(SUnit *SU, const SDep &D); 87234285Sdim void releaseSuccessors(SUnit *SU); 88234285Sdim void scheduleNodeTopDown(SUnit *SU, unsigned CurCycle); 89234285Sdim void listScheduleTopDown(); 90234285Sdim}; 91234285Sdim} // end anonymous namespace 92234285Sdim 93234285Sdim/// Schedule - Schedule the DAG using list scheduling. 94234285Sdimvoid ScheduleDAGVLIW::Schedule() { 95234285Sdim DEBUG(dbgs() 96234285Sdim << "********** List Scheduling BB#" << BB->getNumber() 97234285Sdim << " '" << BB->getName() << "' **********\n"); 98234285Sdim 99234285Sdim // Build the scheduling graph. 100234285Sdim BuildSchedGraph(AA); 101234285Sdim 102234285Sdim AvailableQueue->initNodes(SUnits); 103234285Sdim 104234285Sdim listScheduleTopDown(); 105234285Sdim 106234285Sdim AvailableQueue->releaseState(); 107234285Sdim} 108234285Sdim 109234285Sdim//===----------------------------------------------------------------------===// 110234285Sdim// Top-Down Scheduling 111234285Sdim//===----------------------------------------------------------------------===// 112234285Sdim 113234285Sdim/// releaseSucc - Decrement the NumPredsLeft count of a successor. Add it to 114234285Sdim/// the PendingQueue if the count reaches zero. Also update its cycle bound. 115234285Sdimvoid ScheduleDAGVLIW::releaseSucc(SUnit *SU, const SDep &D) { 116234285Sdim SUnit *SuccSU = D.getSUnit(); 117234285Sdim 118234285Sdim#ifndef NDEBUG 119234285Sdim if (SuccSU->NumPredsLeft == 0) { 120234285Sdim dbgs() << "*** Scheduling failed! ***\n"; 121234285Sdim SuccSU->dump(this); 122234285Sdim dbgs() << " has been released too many times!\n"; 123234285Sdim llvm_unreachable(0); 124234285Sdim } 125234285Sdim#endif 126249423Sdim assert(!D.isWeak() && "unexpected artificial DAG edge"); 127249423Sdim 128234285Sdim --SuccSU->NumPredsLeft; 129234285Sdim 130234285Sdim SuccSU->setDepthToAtLeast(SU->getDepth() + D.getLatency()); 131234285Sdim 132234285Sdim // If all the node's predecessors are scheduled, this node is ready 133234285Sdim // to be scheduled. Ignore the special ExitSU node. 134234285Sdim if (SuccSU->NumPredsLeft == 0 && SuccSU != &ExitSU) { 135234285Sdim PendingQueue.push_back(SuccSU); 136234285Sdim } 137234285Sdim} 138234285Sdim 139234285Sdimvoid ScheduleDAGVLIW::releaseSuccessors(SUnit *SU) { 140234285Sdim // Top down: release successors. 141234285Sdim for (SUnit::succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 142234285Sdim I != E; ++I) { 143234285Sdim assert(!I->isAssignedRegDep() && 144234285Sdim "The list-td scheduler doesn't yet support physreg dependencies!"); 145234285Sdim 146234285Sdim releaseSucc(SU, *I); 147234285Sdim } 148234285Sdim} 149234285Sdim 150234285Sdim/// scheduleNodeTopDown - Add the node to the schedule. Decrement the pending 151234285Sdim/// count of its successors. If a successor pending count is zero, add it to 152234285Sdim/// the Available queue. 153234285Sdimvoid ScheduleDAGVLIW::scheduleNodeTopDown(SUnit *SU, unsigned CurCycle) { 154234285Sdim DEBUG(dbgs() << "*** Scheduling [" << CurCycle << "]: "); 155234285Sdim DEBUG(SU->dump(this)); 156234285Sdim 157234285Sdim Sequence.push_back(SU); 158234285Sdim assert(CurCycle >= SU->getDepth() && "Node scheduled above its depth!"); 159234285Sdim SU->setDepthToAtLeast(CurCycle); 160234285Sdim 161234285Sdim releaseSuccessors(SU); 162234285Sdim SU->isScheduled = true; 163234285Sdim AvailableQueue->scheduledNode(SU); 164234285Sdim} 165234285Sdim 166234285Sdim/// listScheduleTopDown - The main loop of list scheduling for top-down 167234285Sdim/// schedulers. 168234285Sdimvoid ScheduleDAGVLIW::listScheduleTopDown() { 169234285Sdim unsigned CurCycle = 0; 170234285Sdim 171234285Sdim // Release any successors of the special Entry node. 172234285Sdim releaseSuccessors(&EntrySU); 173234285Sdim 174234285Sdim // All leaves to AvailableQueue. 175234285Sdim for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 176234285Sdim // It is available if it has no predecessors. 177234285Sdim if (SUnits[i].Preds.empty()) { 178234285Sdim AvailableQueue->push(&SUnits[i]); 179234285Sdim SUnits[i].isAvailable = true; 180234285Sdim } 181234285Sdim } 182234285Sdim 183234285Sdim // While AvailableQueue is not empty, grab the node with the highest 184234285Sdim // priority. If it is not ready put it back. Schedule the node. 185234285Sdim std::vector<SUnit*> NotReady; 186234285Sdim Sequence.reserve(SUnits.size()); 187234285Sdim while (!AvailableQueue->empty() || !PendingQueue.empty()) { 188234285Sdim // Check to see if any of the pending instructions are ready to issue. If 189234285Sdim // so, add them to the available queue. 190234285Sdim for (unsigned i = 0, e = PendingQueue.size(); i != e; ++i) { 191234285Sdim if (PendingQueue[i]->getDepth() == CurCycle) { 192234285Sdim AvailableQueue->push(PendingQueue[i]); 193234285Sdim PendingQueue[i]->isAvailable = true; 194234285Sdim PendingQueue[i] = PendingQueue.back(); 195234285Sdim PendingQueue.pop_back(); 196234285Sdim --i; --e; 197234285Sdim } 198234285Sdim else { 199234285Sdim assert(PendingQueue[i]->getDepth() > CurCycle && "Negative latency?"); 200234285Sdim } 201234285Sdim } 202234285Sdim 203234285Sdim // If there are no instructions available, don't try to issue anything, and 204234285Sdim // don't advance the hazard recognizer. 205234285Sdim if (AvailableQueue->empty()) { 206234285Sdim // Reset DFA state. 207234285Sdim AvailableQueue->scheduledNode(0); 208234285Sdim ++CurCycle; 209234285Sdim continue; 210234285Sdim } 211234285Sdim 212234285Sdim SUnit *FoundSUnit = 0; 213234285Sdim 214234285Sdim bool HasNoopHazards = false; 215234285Sdim while (!AvailableQueue->empty()) { 216234285Sdim SUnit *CurSUnit = AvailableQueue->pop(); 217234285Sdim 218234285Sdim ScheduleHazardRecognizer::HazardType HT = 219234285Sdim HazardRec->getHazardType(CurSUnit, 0/*no stalls*/); 220234285Sdim if (HT == ScheduleHazardRecognizer::NoHazard) { 221234285Sdim FoundSUnit = CurSUnit; 222234285Sdim break; 223234285Sdim } 224234285Sdim 225234285Sdim // Remember if this is a noop hazard. 226234285Sdim HasNoopHazards |= HT == ScheduleHazardRecognizer::NoopHazard; 227234285Sdim 228234285Sdim NotReady.push_back(CurSUnit); 229234285Sdim } 230234285Sdim 231234285Sdim // Add the nodes that aren't ready back onto the available list. 232234285Sdim if (!NotReady.empty()) { 233234285Sdim AvailableQueue->push_all(NotReady); 234234285Sdim NotReady.clear(); 235234285Sdim } 236234285Sdim 237234285Sdim // If we found a node to schedule, do it now. 238234285Sdim if (FoundSUnit) { 239234285Sdim scheduleNodeTopDown(FoundSUnit, CurCycle); 240234285Sdim HazardRec->EmitInstruction(FoundSUnit); 241234285Sdim 242234285Sdim // If this is a pseudo-op node, we don't want to increment the current 243234285Sdim // cycle. 244234285Sdim if (FoundSUnit->Latency) // Don't increment CurCycle for pseudo-ops! 245234285Sdim ++CurCycle; 246234285Sdim } else if (!HasNoopHazards) { 247234285Sdim // Otherwise, we have a pipeline stall, but no other problem, just advance 248234285Sdim // the current cycle and try again. 249234285Sdim DEBUG(dbgs() << "*** Advancing cycle, no work to do\n"); 250234285Sdim HazardRec->AdvanceCycle(); 251234285Sdim ++NumStalls; 252234285Sdim ++CurCycle; 253234285Sdim } else { 254234285Sdim // Otherwise, we have no instructions to issue and we have instructions 255234285Sdim // that will fault if we don't do this right. This is the case for 256234285Sdim // processors without pipeline interlocks and other cases. 257234285Sdim DEBUG(dbgs() << "*** Emitting noop\n"); 258234285Sdim HazardRec->EmitNoop(); 259234285Sdim Sequence.push_back(0); // NULL here means noop 260234285Sdim ++NumNoops; 261234285Sdim ++CurCycle; 262234285Sdim } 263234285Sdim } 264234285Sdim 265234285Sdim#ifndef NDEBUG 266234285Sdim VerifyScheduledSequence(/*isBottomUp=*/false); 267234285Sdim#endif 268234285Sdim} 269234285Sdim 270234285Sdim//===----------------------------------------------------------------------===// 271234285Sdim// Public Constructor Functions 272234285Sdim//===----------------------------------------------------------------------===// 273234285Sdim 274234285Sdim/// createVLIWDAGScheduler - This creates a top-down list scheduler. 275234285SdimScheduleDAGSDNodes * 276234285Sdimllvm::createVLIWDAGScheduler(SelectionDAGISel *IS, CodeGenOpt::Level) { 277234285Sdim return new ScheduleDAGVLIW(*IS->MF, IS->AA, new ResourcePriorityQueue(IS)); 278234285Sdim} 279