ScheduleDAG.cpp revision 40362067de30a493951e084ba59d9b4fb1654a20
1343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===---- ScheduleDAG.cpp - Implement the ScheduleDAG class ---------------===// 2343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 3343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// The LLVM Compiler Infrastructure 4343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 5343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This file is distributed under the University of Illinois Open Source 6343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// License. See LICENSE.TXT for details. 7343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 8343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 9343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 10343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// This implements the ScheduleDAG class, which is a base class used by 11343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// scheduling implementation classes. 12343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman// 13343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman//===----------------------------------------------------------------------===// 14343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 15343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#define DEBUG_TYPE "pre-RA-sched" 16343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/CodeGen/ScheduleDAG.h" 17343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetMachine.h" 18343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetInstrInfo.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 2140362067de30a493951e084ba59d9b4fb1654a20Dan Gohman#include <climits> 22343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 23343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 24343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanScheduleDAG::ScheduleDAG(SelectionDAG *dag, MachineBasicBlock *bb, 25343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman const TargetMachine &tm) 26343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman : DAG(dag), BB(bb), TM(tm), MRI(BB->getParent()->getRegInfo()) { 27343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman TII = TM.getInstrInfo(); 28343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman MF = BB->getParent(); 29343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman TRI = TM.getRegisterInfo(); 30343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman TLI = TM.getTargetLowering(); 31343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman ConstPool = MF->getConstantPool(); 32343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 33343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 34343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanScheduleDAG::~ScheduleDAG() {} 35343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 36343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CalculateDepths - compute depths using algorithms for the longest 37343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// paths in the DAG 38343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAG::CalculateDepths() { 39343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned DAGSize = SUnits.size(); 40343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman std::vector<SUnit*> WorkList; 41343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.reserve(DAGSize); 42343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Initialize the data structures 44343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 45343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[i]; 46343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Degree = SU->Preds.size(); 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Temporarily use the Depth field as scratch space for the degree count. 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Depth = Degree; 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 50343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Is it a node without dependencies? 51343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Degree == 0) { 52343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(SU->Preds.empty() && "SUnit should have no predecessors"); 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Collect leaf nodes 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.push_back(SU); 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Process nodes in the topological order 59343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (!WorkList.empty()) { 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = WorkList.back(); 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.pop_back(); 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned SUDepth = 0; 63343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 64343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Use dynamic programming: 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // When current node is being processed, all of its dependencies 66343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // are already processed. 67343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // So, just iterate over all predecessors and take the longest path 68343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 69343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 70343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned PredDepth = I->Dep->Depth; 71343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (PredDepth+1 > SUDepth) { 72343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUDepth = PredDepth + 1; 73343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 74343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 75343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 76343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Depth = SUDepth; 77343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 78343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update degrees of all nodes depending on current SUnit 79343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 80343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 81343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = I->Dep; 82343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (!--SU->Depth) 83343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If all dependencies of the node are processed already, 84343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // then the longest path for the node can be computed now 85343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.push_back(SU); 86343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 87343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 88343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 89343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 90343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// CalculateHeights - compute heights using algorithms for the longest 91343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// paths in the DAG 92343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAG::CalculateHeights() { 93343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned DAGSize = SUnits.size(); 94343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman std::vector<SUnit*> WorkList; 95343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.reserve(DAGSize); 96343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 97343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Initialize the data structures 98343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 99343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = &SUnits[i]; 100343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned Degree = SU->Succs.size(); 101343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Temporarily use the Height field as scratch space for the degree count. 102343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Height = Degree; 103343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 104343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Is it a node without dependencies? 105343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Degree == 0) { 106343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(SU->Succs.empty() && "Something wrong"); 107343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman assert(WorkList.empty() && "Should be empty"); 108343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Collect leaf nodes 109343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.push_back(SU); 110343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 111343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 112343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 113343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Process nodes in the topological order 114343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman while (!WorkList.empty()) { 115343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = WorkList.back(); 116343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.pop_back(); 117343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned SUHeight = 0; 118343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 119343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Use dynamic programming: 120343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // When current node is being processed, all of its dependencies 121343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // are already processed. 122343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // So, just iterate over all successors and take the longest path 123343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), E = SU->Succs.end(); 124343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 125343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman unsigned SuccHeight = I->Dep->Height; 126343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (SuccHeight+1 > SUHeight) { 127343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUHeight = SuccHeight + 1; 128343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 129343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 130343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 131343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->Height = SUHeight; 132343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 133343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // Update degrees of all nodes depending on current SUnit 134343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 135343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 136343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SUnit *SU = I->Dep; 137343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (!--SU->Height) 138343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // If all dependencies of the node are processed already, 139343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman // then the longest path for the node can be computed now 140343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman WorkList.push_back(SU); 141343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 142343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 143343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 144343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 145343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// dump - dump the schedule. 146343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAG::dumpSchedule() const { 147343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 148343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (SUnit *SU = Sequence[i]) 149343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->dump(this); 150343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman else 151343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "**** NOOP ****\n"; 152343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 153343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 154343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 155343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 156343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// Run - perform scheduling. 157343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// 158343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAG::Run() { 159343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman Schedule(); 160343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 161343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DOUT << "*** Final schedule ***\n"; 162343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DEBUG(dumpSchedule()); 163343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman DOUT << "\n"; 164343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 165343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 166343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 167343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a group of nodes flagged together. 168343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dump(const ScheduleDAG *G) const { 169343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "SU(" << NodeNum << "): "; 170343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman G->dumpNode(this); 171343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 172343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 173343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dumpAll(const ScheduleDAG *G) const { 174343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman dump(G); 175343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 176343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " # preds left : " << NumPredsLeft << "\n"; 177343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " # succs left : " << NumSuccsLeft << "\n"; 178343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " Latency : " << Latency << "\n"; 179343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " Depth : " << Depth << "\n"; 180343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " Height : " << Height << "\n"; 181343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 182343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Preds.size() != 0) { 183343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " Predecessors:\n"; 184343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 185343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 186343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (I->isCtrl) 187343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " ch #"; 188343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman else 189343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " val #"; 190343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; 191343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (I->isSpecial) 192343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " *"; 193343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "\n"; 194343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 195343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 196343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Succs.size() != 0) { 197343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " Successors:\n"; 198343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); 199343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 200343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (I->isCtrl) 201343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " ch #"; 202343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman else 203343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " val #"; 204343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << I->Dep << " - SU(" << I->Dep->NodeNum << ")"; 205343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (I->isSpecial) 206343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << " *"; 207343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "\n"; 208343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 209343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 210343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman cerr << "\n"; 211343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 212a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 213a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 214a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// VerifySchedule - Verify that all SUnits were scheduled and that 215a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// their state is consistent. 216a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// 217a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohmanvoid ScheduleDAG::VerifySchedule(bool isBottomUp) { 218a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman bool AnyNotSched = false; 219a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman unsigned DeadNodes = 0; 220a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman unsigned Noops = 0; 221a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 222a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!SUnits[i].isScheduled) { 223a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 224a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman ++DeadNodes; 225a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman continue; 226a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 227a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 228a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "*** Scheduling failed! ***\n"; 229a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 230a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "has not been scheduled!\n"; 231a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 232a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 233a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].isScheduled && SUnits[i].Cycle > (unsigned)INT_MAX) { 234a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 235a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "*** Scheduling failed! ***\n"; 236a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 237a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "has an unexpected Cycle value!\n"; 238a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 239a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 240a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (isBottomUp) { 241a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumSuccsLeft != 0) { 242a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 243a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "*** Scheduling failed! ***\n"; 244a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 245a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "has successors left!\n"; 246a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 247a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 248a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } else { 249a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPredsLeft != 0) { 250a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 251a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "*** Scheduling failed! ***\n"; 252a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 253a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman cerr << "has predecessors left!\n"; 254a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 255a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 256a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 257a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 258a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 259a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!Sequence[i]) 260a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman ++Noops; 261a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman assert(!AnyNotSched); 262a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 263a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman "The number of nodes scheduled doesn't match the expected number!"); 264a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman} 265a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 266