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#include "llvm/CodeGen/ScheduleDAG.h" 16fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 172da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#include "llvm/CodeGen/SelectionDAGNodes.h" 184cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#include "llvm/Support/CommandLine.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 203f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbar#include "llvm/Support/raw_ostream.h" 21d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetInstrInfo.h" 22d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetMachine.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Target/TargetRegisterInfo.h" 2440362067de30a493951e084ba59d9b4fb1654a20Dan Gohman#include <climits> 25343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 26343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 27dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "pre-RA-sched" 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 294cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifndef NDEBUG 30a67f14bf53737f9bb0afefa28e08c4aac6ec4804Benjamin Kramerstatic cl::opt<bool> StressSchedOpt( 314cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick "stress-sched", cl::Hidden, cl::init(false), 324cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick cl::desc("Stress test instruction scheduling")); 334cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 344cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick 352d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid SchedulingPriorityQueue::anchor() { } 362d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 3779ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAG::ScheduleDAG(MachineFunction &mf) 3847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman : TM(mf.getTarget()), 3979ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman TII(TM.getInstrInfo()), 4079ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman TRI(TM.getRegisterInfo()), 4179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman MF(mf), MRI(mf.getRegInfo()), 429e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman EntrySU(), ExitSU() { 434cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifndef NDEBUG 444cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick StressSched = StressSchedOpt; 454cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 46343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 47343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 48343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanScheduleDAG::~ScheduleDAG() {} 49343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 5047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick/// Clear the DAG state (e.g. between scheduling regions). 5147c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trickvoid ScheduleDAG::clearDAG() { 5279ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman SUnits.clear(); 539e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman EntrySU = SUnit(); 549e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman ExitSU = SUnit(); 5547c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick} 5679ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman 5747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick/// getInstrDesc helper to handle SDNodes. 5847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trickconst MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const { 59dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (!Node || !Node->isMachineOpcode()) return nullptr; 6047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick return &TII->get(Node->getMachineOpcode()); 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 63c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// addPred - This adds the specified edge as a pred of the current node if 64c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// not already. It also adds the current node as a successor of the 65c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// specified node. 66ae692f2baedf53504af2715993b166950e185a55Andrew Trickbool SUnit::addPred(const SDep &D, bool Required) { 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If this node already has this dependence, don't add a redundant one. 68f22fd3f7b557a967b1edc1fa9ae770006a39e97cCraig Topper for (SmallVectorImpl<SDep>::iterator I = Preds.begin(), E = Preds.end(); 69f22fd3f7b557a967b1edc1fa9ae770006a39e97cCraig Topper I != E; ++I) { 70ae692f2baedf53504af2715993b166950e185a55Andrew Trick // Zero-latency weak edges may be added purely for heuristic ordering. Don't 71ae692f2baedf53504af2715993b166950e185a55Andrew Trick // add them if another kind of edge already exists. 72ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (!Required && I->getSUnit() == D.getSUnit()) 73ae692f2baedf53504af2715993b166950e185a55Andrew Trick return false; 749df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (I->overlaps(D)) { 759df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick // Extend the latency if needed. Equivalent to removePred(I) + addPred(D). 769df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (I->getLatency() < D.getLatency()) { 779df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick SUnit *PredSU = I->getSUnit(); 789df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick // Find the corresponding successor in N. 799df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick SDep ForwardD = *I; 809df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick ForwardD.setSUnit(this); 81f22fd3f7b557a967b1edc1fa9ae770006a39e97cCraig Topper for (SmallVectorImpl<SDep>::iterator II = PredSU->Succs.begin(), 829df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick EE = PredSU->Succs.end(); II != EE; ++II) { 839df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (*II == ForwardD) { 849df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick II->setLatency(D.getLatency()); 859df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick break; 869df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 879df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 889df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick I->setLatency(D.getLatency()); 899df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 9092e946630d5f9bb092853b93501387dd216899b9Andrew Trick return false; 919df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 929df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 93c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Now add a corresponding succ to N. 94c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 95c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 96c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 97c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Update the bookkeeping. 98c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (D.getKind() == SDep::Data) { 99c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds < UINT_MAX && "NumPreds will overflow!"); 100c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs < UINT_MAX && "NumSuccs will overflow!"); 101c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++NumPreds; 102c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++N->NumSuccs; 103c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 104c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 105cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) { 106ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++WeakPredsLeft; 107ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 108ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 109ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(NumPredsLeft < UINT_MAX && "NumPredsLeft will overflow!"); 110ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++NumPredsLeft; 111ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 112c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 113c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 114cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) { 115ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++N->WeakSuccsLeft; 116ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 117ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 118ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(N->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!"); 119ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++N->NumSuccsLeft; 120ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 121c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 1223f23744df4809eba94284e601e81489212c974d4Dan Gohman Preds.push_back(D); 123a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman N->Succs.push_back(P); 124a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 125a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 126a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 127a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 12892e946630d5f9bb092853b93501387dd216899b9Andrew Trick return true; 129c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 130c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 131c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// removePred - This removes the specified edge as a pred of the current 132c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// node if it exists. It also removes the current node as a successor of 133c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// the specified node. 134c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohmanvoid SUnit::removePred(const SDep &D) { 135c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the matching predecessor. 136f22fd3f7b557a967b1edc1fa9ae770006a39e97cCraig Topper for (SmallVectorImpl<SDep>::iterator I = Preds.begin(), E = Preds.end(); 137f22fd3f7b557a967b1edc1fa9ae770006a39e97cCraig Topper I != E; ++I) 138c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (*I == D) { 139c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the corresponding successor in N. 140c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 141c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 142c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 14381474e98e10565e2ee0ad257ddc9469217520711Benjamin Kramer SmallVectorImpl<SDep>::iterator Succ = std::find(N->Succs.begin(), 14481474e98e10565e2ee0ad257ddc9469217520711Benjamin Kramer N->Succs.end(), P); 14581474e98e10565e2ee0ad257ddc9469217520711Benjamin Kramer assert(Succ != N->Succs.end() && "Mismatching preds / succs lists!"); 14681474e98e10565e2ee0ad257ddc9469217520711Benjamin Kramer N->Succs.erase(Succ); 147c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman Preds.erase(I); 148a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman // Update the bookkeeping. 149a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman if (P.getKind() == SDep::Data) { 150c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds > 0 && "NumPreds will underflow!"); 151c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs > 0 && "NumSuccs will underflow!"); 152c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --NumPreds; 153c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --N->NumSuccs; 154c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 155c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 156cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) 157ae692f2baedf53504af2715993b166950e185a55Andrew Trick --WeakPredsLeft; 158ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 159ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!"); 160ae692f2baedf53504af2715993b166950e185a55Andrew Trick --NumPredsLeft; 161ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 162c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 163c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 164cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) 165ae692f2baedf53504af2715993b166950e185a55Andrew Trick --N->WeakSuccsLeft; 166ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 167ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!"); 168ae692f2baedf53504af2715993b166950e185a55Andrew Trick --N->NumSuccsLeft; 169ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 170c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 171a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 172a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 173a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 174a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 175c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman return; 176c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 177c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 178c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 1793f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setDepthDirty() { 1808044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isDepthCurrent) return; 1813f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 1823f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 1838044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman do { 184e19c6362d21c872abaf2f71ea9a0f859f33ee9b5Dan Gohman SUnit *SU = WorkList.pop_back_val(); 1853f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->isDepthCurrent = false; 186f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), 1878044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Succs.end(); I != E; ++I) { 1888044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *SuccSU = I->getSUnit(); 1898044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (SuccSU->isDepthCurrent) 1908044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(SuccSU); 1918044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 1928044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 1933f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1943f23744df4809eba94284e601e81489212c974d4Dan Gohman 1953f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setHeightDirty() { 1968044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isHeightCurrent) return; 1973f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 1983f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 1998044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman do { 200e19c6362d21c872abaf2f71ea9a0f859f33ee9b5Dan Gohman SUnit *SU = WorkList.pop_back_val(); 2013f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->isHeightCurrent = false; 202f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), 2038044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Preds.end(); I != E; ++I) { 2048044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *PredSU = I->getSUnit(); 2058044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (PredSU->isHeightCurrent) 2068044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(PredSU); 2078044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 2088044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 2093f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2103f23744df4809eba94284e601e81489212c974d4Dan Gohman 2113f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setDepthToAtLeast - Update this node's successors to reflect the 2123f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's depth just increased. 2133f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 214557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setDepthToAtLeast(unsigned NewDepth) { 215557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewDepth <= getDepth()) 2163f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 2173f23744df4809eba94284e601e81489212c974d4Dan Gohman setDepthDirty(); 2183f23744df4809eba94284e601e81489212c974d4Dan Gohman Depth = NewDepth; 2193f23744df4809eba94284e601e81489212c974d4Dan Gohman isDepthCurrent = true; 2203f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2213f23744df4809eba94284e601e81489212c974d4Dan Gohman 2223f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setHeightToAtLeast - Update this node's predecessors to reflect the 2233f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's height just increased. 2243f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 225557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setHeightToAtLeast(unsigned NewHeight) { 226557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewHeight <= getHeight()) 2273f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 2283f23744df4809eba94284e601e81489212c974d4Dan Gohman setHeightDirty(); 2293f23744df4809eba94284e601e81489212c974d4Dan Gohman Height = NewHeight; 2303f23744df4809eba94284e601e81489212c974d4Dan Gohman isHeightCurrent = true; 2313f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2323f23744df4809eba94284e601e81489212c974d4Dan Gohman 2333f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeDepth - Calculate the maximal path from the node to the exit. 2343f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 235557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeDepth() { 2363f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2373f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2381578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2393f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2403f23744df4809eba94284e601e81489212c974d4Dan Gohman 2413f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2423f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxPredDepth = 0; 2433f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_pred_iterator I = Cur->Preds.begin(), 2443f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Preds.end(); I != E; ++I) { 2453f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *PredSU = I->getSUnit(); 2463f23744df4809eba94284e601e81489212c974d4Dan Gohman if (PredSU->isDepthCurrent) 2473f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxPredDepth = std::max(MaxPredDepth, 2483f23744df4809eba94284e601e81489212c974d4Dan Gohman PredSU->Depth + I->getLatency()); 2493f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2503f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2513f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(PredSU); 2523f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2533f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2543f23744df4809eba94284e601e81489212c974d4Dan Gohman 2553f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2563f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2573f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxPredDepth != Cur->Depth) { 2583f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setDepthDirty(); 2593f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Depth = MaxPredDepth; 2603f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2613f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isDepthCurrent = true; 2623f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2631578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 2643f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2653f23744df4809eba94284e601e81489212c974d4Dan Gohman 2663f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeHeight - Calculate the maximal path from the node to the entry. 2673f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 268557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeHeight() { 2693f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2703f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2711578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2723f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2733f23744df4809eba94284e601e81489212c974d4Dan Gohman 2743f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2753f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxSuccHeight = 0; 2763f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_succ_iterator I = Cur->Succs.begin(), 2773f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Succs.end(); I != E; ++I) { 2783f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *SuccSU = I->getSUnit(); 2793f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SuccSU->isHeightCurrent) 2803f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxSuccHeight = std::max(MaxSuccHeight, 2813f23744df4809eba94284e601e81489212c974d4Dan Gohman SuccSU->Height + I->getLatency()); 2823f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2833f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2843f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(SuccSU); 2853f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2863f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2873f23744df4809eba94284e601e81489212c974d4Dan Gohman 2883f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2893f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2903f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxSuccHeight != Cur->Height) { 2913f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setHeightDirty(); 2923f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Height = MaxSuccHeight; 2933f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2943f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isHeightCurrent = true; 2953f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2961578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 2973f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2983f23744df4809eba94284e601e81489212c974d4Dan Gohman 29966658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trickvoid SUnit::biasCriticalPath() { 30066658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick if (NumPreds < 2) 30166658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick return; 30266658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick 30366658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick SUnit::pred_iterator BestI = Preds.begin(); 30466658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick unsigned MaxDepth = BestI->getSUnit()->getDepth(); 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (SUnit::pred_iterator I = std::next(BestI), E = Preds.end(); I != E; 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ++I) { 30766658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick if (I->getKind() == SDep::Data && I->getSUnit()->getDepth() > MaxDepth) 30866658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick BestI = I; 30966658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick } 31066658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick if (BestI != Preds.begin()) 31166658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick std::swap(*Preds.begin(), *BestI); 31266658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick} 31366658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick 314b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 315343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 316343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a group of nodes flagged together. 317343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dump(const ScheduleDAG *G) const { 3184b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "SU(" << NodeNum << "): "; 319343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman G->dumpNode(this); 320343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 321343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 322343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dumpAll(const ScheduleDAG *G) const { 323343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman dump(G); 324343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 3254b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # preds left : " << NumPredsLeft << "\n"; 3264b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # succs left : " << NumSuccsLeft << "\n"; 327ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (WeakPredsLeft) 328ae692f2baedf53504af2715993b166950e185a55Andrew Trick dbgs() << " # weak preds left : " << WeakPredsLeft << "\n"; 329ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (WeakSuccsLeft) 330ae692f2baedf53504af2715993b166950e185a55Andrew Trick dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n"; 33192e946630d5f9bb092853b93501387dd216899b9Andrew Trick dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n"; 3324b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Latency : " << Latency << "\n"; 333bf32b7f8446334b4a8fab0cc4153ed02046271b2Andrew Trick dbgs() << " Depth : " << getDepth() << "\n"; 334bf32b7f8446334b4a8fab0cc4153ed02046271b2Andrew Trick dbgs() << " Height : " << getHeight() << "\n"; 335343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 336343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Preds.size() != 0) { 3374b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Predecessors:\n"; 338343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 339343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 3404b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " "; 34154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (I->getKind()) { 3424b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Data: dbgs() << "val "; break; 3434b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Anti: dbgs() << "anti"; break; 3444b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Output: dbgs() << "out "; break; 3454b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Order: dbgs() << "ch "; break; 34654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 3470b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << "SU(" << I->getSUnit()->NodeNum << ")"; 34854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 3494b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 3504b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 3514cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick if (I->isAssignedRegDep()) 3520b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << " Reg=" << PrintReg(I->getReg(), G->TRI); 3534b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 354343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 355343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 356343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Succs.size() != 0) { 3574b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Successors:\n"; 358343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); 359343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 3604b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " "; 36154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (I->getKind()) { 3624b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Data: dbgs() << "val "; break; 3634b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Anti: dbgs() << "anti"; break; 3644b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Output: dbgs() << "out "; break; 3654b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Order: dbgs() << "ch "; break; 36654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 3670b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << "SU(" << I->getSUnit()->NodeNum << ")"; 36854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 3694b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 3704b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 371838038d3e16d0c319c94fec246d1141b27e0046aAndrew Trick if (I->isAssignedRegDep()) 372838038d3e16d0c319c94fec246d1141b27e0046aAndrew Trick dbgs() << " Reg=" << PrintReg(I->getReg(), G->TRI); 3734b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 374343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 375343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 3764b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 377343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 37877e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 379a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 380a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 3814c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// VerifyScheduledDAG - Verify that all SUnits were scheduled and that 3824c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// their state is consistent. Return the number of scheduled nodes. 383a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// 3844c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trickunsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) { 385a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman bool AnyNotSched = false; 386a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman unsigned DeadNodes = 0; 387a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 388a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!SUnits[i].isScheduled) { 389a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 390a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman ++DeadNodes; 391a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman continue; 392a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 393a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3944b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 395a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3964b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has not been scheduled!\n"; 397a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 398a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 3993f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SUnits[i].isScheduled && 4004de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getDepth()) > 4013f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned(INT_MAX)) { 402a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 4034b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 404a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 4054b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has an unexpected " 4063f23744df4809eba94284e601e81489212c974d4Dan Gohman << (isBottomUp ? "Height" : "Depth") << " value!\n"; 407a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 408a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 409a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (isBottomUp) { 410a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumSuccsLeft != 0) { 411a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 4124b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 413a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 4144b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has successors left!\n"; 415a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 416a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 417a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } else { 418a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPredsLeft != 0) { 419a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 4204b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 421a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 4224b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has predecessors left!\n"; 423a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 424a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 425a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 426a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 427a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman assert(!AnyNotSched); 4284c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick return SUnits.size() - DeadNodes; 429a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman} 430a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 43121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 4329f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// InitDAGTopologicalSorting - create the initial topological 43321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// ordering from the DAG to be scheduled. 43421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4359f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// The idea of the algorithm is taken from 43621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Online algorithms for managing the topological order of 43721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 4389f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This is the MNR algorithm, which was first introduced by 4399f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 44021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Maintaining a topological order under edge insertions". 44121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4429f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Short description of the algorithm: 44321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 44421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Topological ordering, ord, of a DAG maps each node to a topological 44521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 44621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4479f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This means that if there is a path from the node X to the node Z, 44821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// then ord(X) < ord(Z). 44921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 45021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// This property can be used to check for reachability of nodes: 4519f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// if Z is reachable from X, then an insertion of the edge Z->X would 45221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 45321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 45421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// The algorithm first computes a topological ordering for the DAG by 45521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// initializing the Index2Node and Node2Index arrays and then tries to keep 45621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the ordering up-to-date after edge insertions by reordering the DAG. 45721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 45821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 45921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the nodes reachable from Y, and then shifts them using Shift to lie 46021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// immediately after X in Index2Node. 46121d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 46221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned DAGSize = SUnits.size(); 46321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit*> WorkList; 46421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.reserve(DAGSize); 46521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 46621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node.resize(DAGSize); 46721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index.resize(DAGSize); 46821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 46921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Initialize the data structures. 470ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (ExitSU) 471ae692f2baedf53504af2715993b166950e185a55Andrew Trick WorkList.push_back(ExitSU); 47221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 47321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 47421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int NodeNum = SU->NodeNum; 47521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned Degree = SU->Succs.size(); 47621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Temporarily use the Node2Index array as scratch space for degree counts. 47721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[NodeNum] = Degree; 47821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 47921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is it a node without dependencies? 48021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Degree == 0) { 48121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(SU->Succs.empty() && "SUnit should have no successors"); 48221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Collect leaf nodes. 48321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 48421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 4859f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 48621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 48721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int Id = DAGSize; 48821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman while (!WorkList.empty()) { 48921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = WorkList.back(); 49021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 491ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (SU->NodeNum < DAGSize) 492ae692f2baedf53504af2715993b166950e185a55Andrew Trick Allocate(SU->NodeNum, --Id); 49321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 49421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 49554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SU = I->getSUnit(); 496ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum]) 49721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If all dependencies of the node are processed already, 49821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then the node can be computed now. 49921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 50021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 50121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 50221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 50321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.resize(DAGSize); 50421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 50521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#ifndef NDEBUG 50621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Check correctness of the ordering 50721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 50821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 50921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 51021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 5119f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 51221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman "Wrong topological sorting"); 51321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 51421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 51521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#endif 51621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 51721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5187a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// AddPred - Updates the topological ordering to accommodate an edge 51921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// to be added from SUnit X to SUnit Y. 52021d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 52121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 52221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[Y->NodeNum]; 52321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[X->NodeNum]; 52421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 52521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(X) < Ord(Y) ? 52621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 52721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Update the topological order. 52821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 52921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(Y, UpperBound, HasLoop); 53021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(!HasLoop && "Inserted edge creates a loop!"); 53121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Recompute topological indexes. 53221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Shift(Visited, LowerBound, UpperBound); 53321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 53421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 53521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5367a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// RemovePred - Updates the topological ordering to accommodate an 53721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// an edge to be removed from the specified node N from the predecessors 53821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// of the current node M. 53921d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 54021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // InitDAGTopologicalSorting(); 54121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 54221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 54321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 54421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// all nodes affected by the edge insertion. These nodes will later get new 54521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// topological indexes by means of the Shift method. 546e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanvoid ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 5475078293cc28dd03236384fa0a3b6c8347e0701fbChris Lattner bool &HasLoop) { 54821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<const SUnit*> WorkList; 5499f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby WorkList.reserve(SUnits.size()); 55021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 55121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 5521578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 55321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SU = WorkList.back(); 55421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 55521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.set(SU->NodeNum); 55621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (int I = SU->Succs.size()-1; I >= 0; --I) { 557ae692f2baedf53504af2715993b166950e185a55Andrew Trick unsigned s = SU->Succs[I].getSUnit()->NodeNum; 558ae692f2baedf53504af2715993b166950e185a55Andrew Trick // Edges to non-SUnits are allowed but ignored (e.g. ExitSU). 559ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (s >= Node2Index.size()) 560ae692f2baedf53504af2715993b166950e185a55Andrew Trick continue; 56121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Node2Index[s] == UpperBound) { 5629f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby HasLoop = true; 56321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return; 56421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 56521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Visit successors if not already and in affected region. 56621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!Visited.test(s) && Node2Index[s] < UpperBound) { 56754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman WorkList.push_back(SU->Succs[I].getSUnit()); 5689f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5699f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5701578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 57121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 57221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5739f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Shift - Renumber the nodes so that the topological ordering is 57421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// preserved. 5759f71f801b51cdc7df388b2693398cfea69fe67c7John Mosbyvoid ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 576e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman int UpperBound) { 57721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> L; 57821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int shift = 0; 57921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int i; 58021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 58121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (i = LowerBound; i <= UpperBound; ++i) { 58221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // w is node at topological index i. 58321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int w = Index2Node[i]; 58421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Visited.test(w)) { 58521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Unmark. 58621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(w); 58721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman L.push_back(w); 58821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman shift = shift + 1; 58921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } else { 59021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(w, i - shift); 59121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 59221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 59321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 59421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned j = 0; j < L.size(); ++j) { 59521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(L[j], i - shift); 59621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman i = i + 1; 59721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 59821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 59921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 60021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 601ae692f2baedf53504af2715993b166950e185a55Andrew Trick/// WillCreateCycle - Returns true if adding an edge to TargetSU from SU will 602ae692f2baedf53504af2715993b166950e185a55Andrew Trick/// create a cycle. If so, it is not safe to call AddPred(TargetSU, SU). 603ae692f2baedf53504af2715993b166950e185a55Andrew Trickbool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) { 604ae692f2baedf53504af2715993b166950e185a55Andrew Trick // Is SU reachable from TargetSU via successor edges? 605ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (IsReachable(SU, TargetSU)) 60621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 607ae692f2baedf53504af2715993b166950e185a55Andrew Trick for (SUnit::pred_iterator 608ae692f2baedf53504af2715993b166950e185a55Andrew Trick I = TargetSU->Preds.begin(), E = TargetSU->Preds.end(); I != E; ++I) 60954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep() && 610ae692f2baedf53504af2715993b166950e185a55Andrew Trick IsReachable(SU, I->getSUnit())) 61121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 61221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return false; 61321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 61421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 61521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// IsReachable - Checks if SU is reachable from TargetSU. 616e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanbool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 617e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman const SUnit *TargetSU) { 61821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If insertion of the edge SU->TargetSU would create a cycle 61921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then there is a path from TargetSU to SU. 62021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 62121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[TargetSU->NodeNum]; 62221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[SU->NodeNum]; 62321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 62421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(TargetSU) < Ord(SU) ? 62521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 62621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 6279f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby // There may be a path from TargetSU to SU. Check for it. 62821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(TargetSU, UpperBound, HasLoop); 62921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 63021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return HasLoop; 63121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 63221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 63321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Allocate - assign the topological index to the node n. 63421d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::Allocate(int n, int index) { 63521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[n] = index; 63621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node[index] = n; 63721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 63821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 6399f71f801b51cdc7df388b2693398cfea69fe67c7John MosbyScheduleDAGTopologicalSort:: 640ae692f2baedf53504af2715993b166950e185a55Andrew TrickScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu) 641ae692f2baedf53504af2715993b166950e185a55Andrew Trick : SUnits(sunits), ExitSU(exitsu) {} 642fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman 643fc54c552963545a81e4ea38e60460590afb2d5aeDan GohmanScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} 644