ScheduleDAG.cpp revision e3a49cd944ad41eba5a594f1de773d531ad25403
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) { 52e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman assert(SU->Preds.empty() && "SUnit should have no predecessors"); 53e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman // Collect leaf nodes 54e3a49cd944ad41eba5a594f1de773d531ad25403Dan 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) { 72e3a49cd944ad41eba5a594f1de773d531ad25403Dan 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) { 106e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman assert(SU->Succs.empty() && "Something wrong"); 107e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman assert(WorkList.empty() && "Should be empty"); 108e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman // Collect leaf nodes 109e3a49cd944ad41eba5a594f1de773d531ad25403Dan 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) { 127e3a49cd944ad41eba5a594f1de773d531ad25403Dan 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 << ")"; 19198adea11496400c8385b774b4d9f9acd4c99d254Dan Gohman if (I->isArtificial) 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 << ")"; 20598adea11496400c8385b774b4d9f9acd4c99d254Dan Gohman if (I->isArtificial) 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 26621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 26721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// InitDAGTopologicalSorting - create the initial topological 26821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// ordering from the DAG to be scheduled. 26921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 27021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// The idea of the algorithm is taken from 27121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Online algorithms for managing the topological order of 27221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 27321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// This is the MNR algorithm, which was first introduced by 27421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 27521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Maintaining a topological order under edge insertions". 27621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 27721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Short description of the algorithm: 27821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 27921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Topological ordering, ord, of a DAG maps each node to a topological 28021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 28121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 28221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// This means that if there is a path from the node X to the node Z, 28321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// then ord(X) < ord(Z). 28421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 28521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// This property can be used to check for reachability of nodes: 28621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// if Z is reachable from X, then an insertion of the edge Z->X would 28721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 28821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 28921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// The algorithm first computes a topological ordering for the DAG by 29021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// initializing the Index2Node and Node2Index arrays and then tries to keep 29121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the ordering up-to-date after edge insertions by reordering the DAG. 29221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 29321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 29421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the nodes reachable from Y, and then shifts them using Shift to lie 29521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// immediately after X in Index2Node. 29621d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 29721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned DAGSize = SUnits.size(); 29821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit*> WorkList; 29921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.reserve(DAGSize); 30021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 30121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node.resize(DAGSize); 30221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index.resize(DAGSize); 30321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 30421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Initialize the data structures. 30521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 30621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 30721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int NodeNum = SU->NodeNum; 30821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned Degree = SU->Succs.size(); 30921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Temporarily use the Node2Index array as scratch space for degree counts. 31021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[NodeNum] = Degree; 31121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 31221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is it a node without dependencies? 31321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Degree == 0) { 31421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(SU->Succs.empty() && "SUnit should have no successors"); 31521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Collect leaf nodes. 31621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 31721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 31821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 31921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 32021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int Id = DAGSize; 32121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman while (!WorkList.empty()) { 32221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = WorkList.back(); 32321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 32421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(SU->NodeNum, --Id); 32521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 32621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 32721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = I->Dep; 32821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!--Node2Index[SU->NodeNum]) 32921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If all dependencies of the node are processed already, 33021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then the node can be computed now. 33121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 33221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 33321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 33421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 33521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.resize(DAGSize); 33621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 33721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#ifndef NDEBUG 33821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Check correctness of the ordering 33921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 34021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 34121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 34221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 34321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(Node2Index[SU->NodeNum] > Node2Index[I->Dep->NodeNum] && 34421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman "Wrong topological sorting"); 34521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 34621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 34721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#endif 34821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 34921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 35021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// AddPred - Updates the topological ordering to accomodate an edge 35121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// to be added from SUnit X to SUnit Y. 35221d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 35321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 35421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[Y->NodeNum]; 35521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[X->NodeNum]; 35621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 35721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(X) < Ord(Y) ? 35821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 35921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Update the topological order. 36021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 36121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(Y, UpperBound, HasLoop); 36221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(!HasLoop && "Inserted edge creates a loop!"); 36321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Recompute topological indexes. 36421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Shift(Visited, LowerBound, UpperBound); 36521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 36621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 36721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 36821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// RemovePred - Updates the topological ordering to accomodate an 36921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// an edge to be removed from the specified node N from the predecessors 37021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// of the current node M. 37121d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 37221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // InitDAGTopologicalSorting(); 37321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 37421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 37521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 37621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// all nodes affected by the edge insertion. These nodes will later get new 37721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// topological indexes by means of the Shift method. 378e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanvoid ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 379e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman bool& HasLoop) { 38021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<const SUnit*> WorkList; 38121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.reserve(SUnits.size()); 38221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 38321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 38421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman while (!WorkList.empty()) { 38521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SU = WorkList.back(); 38621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 38721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.set(SU->NodeNum); 38821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (int I = SU->Succs.size()-1; I >= 0; --I) { 38921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int s = SU->Succs[I].Dep->NodeNum; 39021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Node2Index[s] == UpperBound) { 39121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman HasLoop = true; 39221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return; 39321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 39421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Visit successors if not already and in affected region. 39521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!Visited.test(s) && Node2Index[s] < UpperBound) { 39621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU->Succs[I].Dep); 39721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 39821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 39921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 40021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 40121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 40221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Shift - Renumber the nodes so that the topological ordering is 40321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// preserved. 40421d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 405e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman int UpperBound) { 40621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> L; 40721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int shift = 0; 40821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int i; 40921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 41021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (i = LowerBound; i <= UpperBound; ++i) { 41121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // w is node at topological index i. 41221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int w = Index2Node[i]; 41321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Visited.test(w)) { 41421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Unmark. 41521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(w); 41621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman L.push_back(w); 41721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman shift = shift + 1; 41821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } else { 41921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(w, i - shift); 42021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 42121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 42221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 42321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned j = 0; j < L.size(); ++j) { 42421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(L[j], i - shift); 42521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman i = i + 1; 42621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 42721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 42821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 42921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 43021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 43121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 43221d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanbool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 43321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (IsReachable(TargetSU, SU)) 43421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 43521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 43621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) 43721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (I->Cost < 0 && IsReachable(TargetSU, I->Dep)) 43821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 43921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return false; 44021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 44121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 44221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// IsReachable - Checks if SU is reachable from TargetSU. 443e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanbool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 444e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman const SUnit *TargetSU) { 44521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If insertion of the edge SU->TargetSU would create a cycle 44621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then there is a path from TargetSU to SU. 44721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 44821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[TargetSU->NodeNum]; 44921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[SU->NodeNum]; 45021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 45121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(TargetSU) < Ord(SU) ? 45221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 45321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 45421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // There may be a path from TargetSU to SU. Check for it. 45521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(TargetSU, UpperBound, HasLoop); 45621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 45721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return HasLoop; 45821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 45921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 46021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Allocate - assign the topological index to the node n. 46121d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::Allocate(int n, int index) { 46221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[n] = index; 46321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node[index] = n; 46421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 46521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 46621d9003087c9a707e6cd95460136b499df358fb8Dan GohmanScheduleDAGTopologicalSort::ScheduleDAGTopologicalSort( 46721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit> &sunits) 46821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman : SUnits(sunits) {} 469