ScheduleDAG.cpp revision cf6b6131dd0da37903a6e3a5173ea12aa8263713
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" 17fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman#include "llvm/CodeGen/ScheduleHazardRecognizer.h" 182da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick#include "llvm/CodeGen/SelectionDAGNodes.h" 19343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetMachine.h" 20343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetInstrInfo.h" 21343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Target/TargetRegisterInfo.h" 224cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#include "llvm/Support/CommandLine.h" 23343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/Support/Debug.h" 243f0e83067d7938f742d21e14fc87c006d2fc3161Daniel Dunbar#include "llvm/Support/raw_ostream.h" 2540362067de30a493951e084ba59d9b4fb1654a20Dan Gohman#include <climits> 26343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanusing namespace llvm; 27343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 284cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifndef NDEBUG 29a67f14bf53737f9bb0afefa28e08c4aac6ec4804Benjamin Kramerstatic cl::opt<bool> StressSchedOpt( 304cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick "stress-sched", cl::Hidden, cl::init(false), 314cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick cl::desc("Stress test instruction scheduling")); 324cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 334cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick 342d24e2a396a1d211baaeedf32148a3b657240170David Blaikievoid SchedulingPriorityQueue::anchor() { } 352d24e2a396a1d211baaeedf32148a3b657240170David Blaikie 3679ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAG::ScheduleDAG(MachineFunction &mf) 3747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman : TM(mf.getTarget()), 3879ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman TII(TM.getInstrInfo()), 3979ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman TRI(TM.getRegisterInfo()), 4079ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman MF(mf), MRI(mf.getRegInfo()), 419e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman EntrySU(), ExitSU() { 424cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifndef NDEBUG 434cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick StressSched = StressSchedOpt; 444cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 45343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 46343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 47343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanScheduleDAG::~ScheduleDAG() {} 48343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 4947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick/// Clear the DAG state (e.g. between scheduling regions). 5047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trickvoid ScheduleDAG::clearDAG() { 5179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman SUnits.clear(); 529e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman EntrySU = SUnit(); 539e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman ExitSU = SUnit(); 5447c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick} 5579ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman 5647c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick/// getInstrDesc helper to handle SDNodes. 5747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trickconst MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const { 5847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick if (!Node || !Node->isMachineOpcode()) return NULL; 5947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick return &TII->get(Node->getMachineOpcode()); 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 62c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// addPred - This adds the specified edge as a pred of the current node if 63c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// not already. It also adds the current node as a successor of the 64c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// specified node. 65ae692f2baedf53504af2715993b166950e185a55Andrew Trickbool SUnit::addPred(const SDep &D, bool Required) { 66c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // If this node already has this depenence, don't add a redundant one. 679df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 689df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick I != E; ++I) { 69ae692f2baedf53504af2715993b166950e185a55Andrew Trick // Zero-latency weak edges may be added purely for heuristic ordering. Don't 70ae692f2baedf53504af2715993b166950e185a55Andrew Trick // add them if another kind of edge already exists. 71ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (!Required && I->getSUnit() == D.getSUnit()) 72ae692f2baedf53504af2715993b166950e185a55Andrew Trick return false; 739df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (I->overlaps(D)) { 749df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick // Extend the latency if needed. Equivalent to removePred(I) + addPred(D). 759df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (I->getLatency() < D.getLatency()) { 769df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick SUnit *PredSU = I->getSUnit(); 779df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick // Find the corresponding successor in N. 789df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick SDep ForwardD = *I; 799df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick ForwardD.setSUnit(this); 809df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick for (SmallVector<SDep, 4>::iterator II = PredSU->Succs.begin(), 819df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick EE = PredSU->Succs.end(); II != EE; ++II) { 829df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (*II == ForwardD) { 839df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick II->setLatency(D.getLatency()); 849df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick break; 859df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 869df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 879df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick I->setLatency(D.getLatency()); 889df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 8992e946630d5f9bb092853b93501387dd216899b9Andrew Trick return false; 909df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 919df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 92c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Now add a corresponding succ to N. 93c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 94c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 95c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 96c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Update the bookkeeping. 97c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (D.getKind() == SDep::Data) { 98c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds < UINT_MAX && "NumPreds will overflow!"); 99c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs < UINT_MAX && "NumSuccs will overflow!"); 100c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++NumPreds; 101c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++N->NumSuccs; 102c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 103c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 104cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) { 105ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++WeakPredsLeft; 106ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 107ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 108ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(NumPredsLeft < UINT_MAX && "NumPredsLeft will overflow!"); 109ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++NumPredsLeft; 110ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 111c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 112c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 113cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) { 114ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++N->WeakSuccsLeft; 115ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 116ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 117ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(N->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!"); 118ae692f2baedf53504af2715993b166950e185a55Andrew Trick ++N->NumSuccsLeft; 119ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 120c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 1213f23744df4809eba94284e601e81489212c974d4Dan Gohman Preds.push_back(D); 122a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman N->Succs.push_back(P); 123a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 124a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 125a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 126a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 12792e946630d5f9bb092853b93501387dd216899b9Andrew Trick return true; 128c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 129c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 130c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// removePred - This removes the specified edge as a pred of the current 131c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// node if it exists. It also removes the current node as a successor of 132c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// the specified node. 133c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohmanvoid SUnit::removePred(const SDep &D) { 134c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the matching predecessor. 135c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 136c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman I != E; ++I) 137c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (*I == D) { 138c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman bool FoundSucc = false; 139c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the corresponding successor in N. 140c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 141c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 142c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 143c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(), 144c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman EE = N->Succs.end(); II != EE; ++II) 145c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (*II == P) { 146c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman FoundSucc = true; 147c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman N->Succs.erase(II); 148c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman break; 149c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 150c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman assert(FoundSucc && "Mismatching preds / succs lists!"); 1511f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)FoundSucc; 152c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman Preds.erase(I); 153a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman // Update the bookkeeping. 154a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman if (P.getKind() == SDep::Data) { 155c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds > 0 && "NumPreds will underflow!"); 156c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs > 0 && "NumSuccs will underflow!"); 157c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --NumPreds; 158c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --N->NumSuccs; 159c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 160c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 161cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) 162ae692f2baedf53504af2715993b166950e185a55Andrew Trick --WeakPredsLeft; 163ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 164ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!"); 165ae692f2baedf53504af2715993b166950e185a55Andrew Trick --NumPredsLeft; 166ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 167c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 168c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 169cf6b6131dd0da37903a6e3a5173ea12aa8263713Andrew Trick if (D.isWeak()) 170ae692f2baedf53504af2715993b166950e185a55Andrew Trick --N->WeakSuccsLeft; 171ae692f2baedf53504af2715993b166950e185a55Andrew Trick else { 172ae692f2baedf53504af2715993b166950e185a55Andrew Trick assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!"); 173ae692f2baedf53504af2715993b166950e185a55Andrew Trick --N->NumSuccsLeft; 174ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 175c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 176a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 177a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 178a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 179a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 180c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman return; 181c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 182c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 183c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 1843f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setDepthDirty() { 1858044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isDepthCurrent) return; 1863f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 1873f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 1888044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman do { 189e19c6362d21c872abaf2f71ea9a0f859f33ee9b5Dan Gohman SUnit *SU = WorkList.pop_back_val(); 1903f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->isDepthCurrent = false; 191f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), 1928044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Succs.end(); I != E; ++I) { 1938044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *SuccSU = I->getSUnit(); 1948044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (SuccSU->isDepthCurrent) 1958044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(SuccSU); 1968044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 1978044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 1983f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1993f23744df4809eba94284e601e81489212c974d4Dan Gohman 2003f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setHeightDirty() { 2018044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isHeightCurrent) return; 2023f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2033f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2048044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman do { 205e19c6362d21c872abaf2f71ea9a0f859f33ee9b5Dan Gohman SUnit *SU = WorkList.pop_back_val(); 2063f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->isHeightCurrent = false; 207f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), 2088044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Preds.end(); I != E; ++I) { 2098044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *PredSU = I->getSUnit(); 2108044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (PredSU->isHeightCurrent) 2118044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(PredSU); 2128044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 2138044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 2143f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2153f23744df4809eba94284e601e81489212c974d4Dan Gohman 2163f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setDepthToAtLeast - Update this node's successors to reflect the 2173f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's depth just increased. 2183f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 219557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setDepthToAtLeast(unsigned NewDepth) { 220557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewDepth <= getDepth()) 2213f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 2223f23744df4809eba94284e601e81489212c974d4Dan Gohman setDepthDirty(); 2233f23744df4809eba94284e601e81489212c974d4Dan Gohman Depth = NewDepth; 2243f23744df4809eba94284e601e81489212c974d4Dan Gohman isDepthCurrent = true; 2253f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2263f23744df4809eba94284e601e81489212c974d4Dan Gohman 2273f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setHeightToAtLeast - Update this node's predecessors to reflect the 2283f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's height just increased. 2293f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 230557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setHeightToAtLeast(unsigned NewHeight) { 231557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewHeight <= getHeight()) 2323f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 2333f23744df4809eba94284e601e81489212c974d4Dan Gohman setHeightDirty(); 2343f23744df4809eba94284e601e81489212c974d4Dan Gohman Height = NewHeight; 2353f23744df4809eba94284e601e81489212c974d4Dan Gohman isHeightCurrent = true; 2363f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2373f23744df4809eba94284e601e81489212c974d4Dan Gohman 2383f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeDepth - Calculate the maximal path from the node to the exit. 2393f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 240557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeDepth() { 2413f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2423f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2431578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2443f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2453f23744df4809eba94284e601e81489212c974d4Dan Gohman 2463f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2473f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxPredDepth = 0; 2483f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_pred_iterator I = Cur->Preds.begin(), 2493f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Preds.end(); I != E; ++I) { 2503f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *PredSU = I->getSUnit(); 2513f23744df4809eba94284e601e81489212c974d4Dan Gohman if (PredSU->isDepthCurrent) 2523f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxPredDepth = std::max(MaxPredDepth, 2533f23744df4809eba94284e601e81489212c974d4Dan Gohman PredSU->Depth + I->getLatency()); 2543f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2553f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2563f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(PredSU); 2573f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2583f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2593f23744df4809eba94284e601e81489212c974d4Dan Gohman 2603f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2613f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2623f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxPredDepth != Cur->Depth) { 2633f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setDepthDirty(); 2643f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Depth = MaxPredDepth; 2653f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2663f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isDepthCurrent = true; 2673f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2681578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 2693f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2703f23744df4809eba94284e601e81489212c974d4Dan Gohman 2713f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeHeight - Calculate the maximal path from the node to the entry. 2723f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 273557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeHeight() { 2743f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2753f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2761578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2773f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2783f23744df4809eba94284e601e81489212c974d4Dan Gohman 2793f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2803f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxSuccHeight = 0; 2813f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_succ_iterator I = Cur->Succs.begin(), 2823f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Succs.end(); I != E; ++I) { 2833f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *SuccSU = I->getSUnit(); 2843f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SuccSU->isHeightCurrent) 2853f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxSuccHeight = std::max(MaxSuccHeight, 2863f23744df4809eba94284e601e81489212c974d4Dan Gohman SuccSU->Height + I->getLatency()); 2873f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2883f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2893f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(SuccSU); 2903f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2913f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2923f23744df4809eba94284e601e81489212c974d4Dan Gohman 2933f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2943f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2953f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxSuccHeight != Cur->Height) { 2963f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setHeightDirty(); 2973f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Height = MaxSuccHeight; 2983f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2993f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isHeightCurrent = true; 3003f23744df4809eba94284e601e81489212c974d4Dan Gohman } 3011578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 3023f23744df4809eba94284e601e81489212c974d4Dan Gohman} 3033f23744df4809eba94284e601e81489212c974d4Dan Gohman 304b720be6a50f4e1b3280d2b029ee38dda14577525Manman Ren#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP) 305343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 306343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a group of nodes flagged together. 307343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dump(const ScheduleDAG *G) const { 3084b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "SU(" << NodeNum << "): "; 309343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman G->dumpNode(this); 310343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 311343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 312343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dumpAll(const ScheduleDAG *G) const { 313343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman dump(G); 314343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 3154b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # preds left : " << NumPredsLeft << "\n"; 3164b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # succs left : " << NumSuccsLeft << "\n"; 317ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (WeakPredsLeft) 318ae692f2baedf53504af2715993b166950e185a55Andrew Trick dbgs() << " # weak preds left : " << WeakPredsLeft << "\n"; 319ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (WeakSuccsLeft) 320ae692f2baedf53504af2715993b166950e185a55Andrew Trick dbgs() << " # weak succs left : " << WeakSuccsLeft << "\n"; 32192e946630d5f9bb092853b93501387dd216899b9Andrew Trick dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n"; 3224b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Latency : " << Latency << "\n"; 3234b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Depth : " << Depth << "\n"; 3244b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Height : " << Height << "\n"; 325343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 326343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Preds.size() != 0) { 3274b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Predecessors:\n"; 328343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 329343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 3304b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " "; 33154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (I->getKind()) { 3324b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Data: dbgs() << "val "; break; 3334b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Anti: dbgs() << "anti"; break; 3344b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Output: dbgs() << "out "; break; 3354b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Order: dbgs() << "ch "; break; 33654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 3370b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << "SU(" << I->getSUnit()->NodeNum << ")"; 33854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 3394b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 3404b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 3414cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick if (I->isAssignedRegDep()) 3420b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << " Reg=" << PrintReg(I->getReg(), G->TRI); 3434b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 344343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 345343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 346343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Succs.size() != 0) { 3474b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Successors:\n"; 348343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); 349343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 3504b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " "; 35154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (I->getKind()) { 3524b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Data: dbgs() << "val "; break; 3534b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Anti: dbgs() << "anti"; break; 3544b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Output: dbgs() << "out "; break; 3554b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Order: dbgs() << "ch "; break; 35654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 3570b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << "SU(" << I->getSUnit()->NodeNum << ")"; 35854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 3594b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 3604b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 3614b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 362343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 363343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 3644b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 365343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 36677e300e8f0b8db8eec448cae9c87d7c5bfad9757Manman Ren#endif 367a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 368a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 3694c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// VerifyScheduledDAG - Verify that all SUnits were scheduled and that 3704c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// their state is consistent. Return the number of scheduled nodes. 371a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// 3724c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trickunsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) { 373a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman bool AnyNotSched = false; 374a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman unsigned DeadNodes = 0; 375a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 376a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!SUnits[i].isScheduled) { 377a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 378a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman ++DeadNodes; 379a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman continue; 380a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 381a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3824b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 383a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3844b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has not been scheduled!\n"; 385a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 386a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 3873f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SUnits[i].isScheduled && 3884de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getDepth()) > 3893f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned(INT_MAX)) { 390a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3914b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 392a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3934b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has an unexpected " 3943f23744df4809eba94284e601e81489212c974d4Dan Gohman << (isBottomUp ? "Height" : "Depth") << " value!\n"; 395a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 396a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 397a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (isBottomUp) { 398a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumSuccsLeft != 0) { 399a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 4004b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 401a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 4024b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has successors left!\n"; 403a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 404a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 405a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } else { 406a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPredsLeft != 0) { 407a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 4084b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 409a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 4104b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has predecessors left!\n"; 411a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 412a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 413a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 414a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 415a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman assert(!AnyNotSched); 4164c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick return SUnits.size() - DeadNodes; 417a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman} 418a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 41921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 4209f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// InitDAGTopologicalSorting - create the initial topological 42121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// ordering from the DAG to be scheduled. 42221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4239f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// The idea of the algorithm is taken from 42421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Online algorithms for managing the topological order of 42521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 4269f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This is the MNR algorithm, which was first introduced by 4279f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 42821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Maintaining a topological order under edge insertions". 42921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4309f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Short description of the algorithm: 43121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 43221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Topological ordering, ord, of a DAG maps each node to a topological 43321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 43421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4359f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This means that if there is a path from the node X to the node Z, 43621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// then ord(X) < ord(Z). 43721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 43821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// This property can be used to check for reachability of nodes: 4399f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// if Z is reachable from X, then an insertion of the edge Z->X would 44021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 44121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 44221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// The algorithm first computes a topological ordering for the DAG by 44321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// initializing the Index2Node and Node2Index arrays and then tries to keep 44421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the ordering up-to-date after edge insertions by reordering the DAG. 44521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 44621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 44721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the nodes reachable from Y, and then shifts them using Shift to lie 44821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// immediately after X in Index2Node. 44921d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 45021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned DAGSize = SUnits.size(); 45121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit*> WorkList; 45221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.reserve(DAGSize); 45321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 45421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node.resize(DAGSize); 45521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index.resize(DAGSize); 45621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 45721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Initialize the data structures. 458ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (ExitSU) 459ae692f2baedf53504af2715993b166950e185a55Andrew Trick WorkList.push_back(ExitSU); 46021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 46121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 46221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int NodeNum = SU->NodeNum; 46321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned Degree = SU->Succs.size(); 46421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Temporarily use the Node2Index array as scratch space for degree counts. 46521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[NodeNum] = Degree; 46621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 46721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is it a node without dependencies? 46821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Degree == 0) { 46921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(SU->Succs.empty() && "SUnit should have no successors"); 47021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Collect leaf nodes. 47121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 47221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 4739f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 47421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 47521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int Id = DAGSize; 47621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman while (!WorkList.empty()) { 47721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = WorkList.back(); 47821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 479ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (SU->NodeNum < DAGSize) 480ae692f2baedf53504af2715993b166950e185a55Andrew Trick Allocate(SU->NodeNum, --Id); 48121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 48221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 48354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SU = I->getSUnit(); 484ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (SU->NodeNum < DAGSize && !--Node2Index[SU->NodeNum]) 48521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If all dependencies of the node are processed already, 48621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then the node can be computed now. 48721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 48821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 48921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 49021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 49121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.resize(DAGSize); 49221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 49321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#ifndef NDEBUG 49421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Check correctness of the ordering 49521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 49621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 49721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 49821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 4999f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 50021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman "Wrong topological sorting"); 50121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 50221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 50321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#endif 50421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 50521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5067a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// AddPred - Updates the topological ordering to accommodate an edge 50721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// to be added from SUnit X to SUnit Y. 50821d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 50921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 51021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[Y->NodeNum]; 51121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[X->NodeNum]; 51221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 51321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(X) < Ord(Y) ? 51421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 51521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Update the topological order. 51621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 51721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(Y, UpperBound, HasLoop); 51821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(!HasLoop && "Inserted edge creates a loop!"); 51921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Recompute topological indexes. 52021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Shift(Visited, LowerBound, UpperBound); 52121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 52221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 52321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5247a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// RemovePred - Updates the topological ordering to accommodate an 52521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// an edge to be removed from the specified node N from the predecessors 52621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// of the current node M. 52721d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 52821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // InitDAGTopologicalSorting(); 52921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 53021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 53121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 53221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// all nodes affected by the edge insertion. These nodes will later get new 53321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// topological indexes by means of the Shift method. 534e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanvoid ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 5355078293cc28dd03236384fa0a3b6c8347e0701fbChris Lattner bool &HasLoop) { 53621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<const SUnit*> WorkList; 5379f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby WorkList.reserve(SUnits.size()); 53821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 53921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 5401578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 54121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SU = WorkList.back(); 54221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 54321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.set(SU->NodeNum); 54421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (int I = SU->Succs.size()-1; I >= 0; --I) { 545ae692f2baedf53504af2715993b166950e185a55Andrew Trick unsigned s = SU->Succs[I].getSUnit()->NodeNum; 546ae692f2baedf53504af2715993b166950e185a55Andrew Trick // Edges to non-SUnits are allowed but ignored (e.g. ExitSU). 547ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (s >= Node2Index.size()) 548ae692f2baedf53504af2715993b166950e185a55Andrew Trick continue; 54921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Node2Index[s] == UpperBound) { 5509f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby HasLoop = true; 55121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return; 55221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 55321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Visit successors if not already and in affected region. 55421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!Visited.test(s) && Node2Index[s] < UpperBound) { 55554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman WorkList.push_back(SU->Succs[I].getSUnit()); 5569f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5579f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5581578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 55921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 56021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5619f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Shift - Renumber the nodes so that the topological ordering is 56221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// preserved. 5639f71f801b51cdc7df388b2693398cfea69fe67c7John Mosbyvoid ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 564e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman int UpperBound) { 56521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> L; 56621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int shift = 0; 56721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int i; 56821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 56921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (i = LowerBound; i <= UpperBound; ++i) { 57021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // w is node at topological index i. 57121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int w = Index2Node[i]; 57221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Visited.test(w)) { 57321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Unmark. 57421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(w); 57521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman L.push_back(w); 57621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman shift = shift + 1; 57721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } else { 57821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(w, i - shift); 57921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 58021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 58121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 58221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned j = 0; j < L.size(); ++j) { 58321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(L[j], i - shift); 58421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman i = i + 1; 58521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 58621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 58721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 58821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 589ae692f2baedf53504af2715993b166950e185a55Andrew Trick/// WillCreateCycle - Returns true if adding an edge to TargetSU from SU will 590ae692f2baedf53504af2715993b166950e185a55Andrew Trick/// create a cycle. If so, it is not safe to call AddPred(TargetSU, SU). 591ae692f2baedf53504af2715993b166950e185a55Andrew Trickbool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *TargetSU, SUnit *SU) { 592ae692f2baedf53504af2715993b166950e185a55Andrew Trick // Is SU reachable from TargetSU via successor edges? 593ae692f2baedf53504af2715993b166950e185a55Andrew Trick if (IsReachable(SU, TargetSU)) 59421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 595ae692f2baedf53504af2715993b166950e185a55Andrew Trick for (SUnit::pred_iterator 596ae692f2baedf53504af2715993b166950e185a55Andrew Trick I = TargetSU->Preds.begin(), E = TargetSU->Preds.end(); I != E; ++I) 59754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep() && 598ae692f2baedf53504af2715993b166950e185a55Andrew Trick IsReachable(SU, I->getSUnit())) 59921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 60021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return false; 60121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 60221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 60321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// IsReachable - Checks if SU is reachable from TargetSU. 604e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanbool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 605e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman const SUnit *TargetSU) { 60621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If insertion of the edge SU->TargetSU would create a cycle 60721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then there is a path from TargetSU to SU. 60821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 60921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[TargetSU->NodeNum]; 61021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[SU->NodeNum]; 61121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 61221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(TargetSU) < Ord(SU) ? 61321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 61421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 6159f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby // There may be a path from TargetSU to SU. Check for it. 61621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(TargetSU, UpperBound, HasLoop); 61721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 61821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return HasLoop; 61921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 62021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 62121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Allocate - assign the topological index to the node n. 62221d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::Allocate(int n, int index) { 62321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[n] = index; 62421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node[index] = n; 62521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 62621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 6279f71f801b51cdc7df388b2693398cfea69fe67c7John MosbyScheduleDAGTopologicalSort:: 628ae692f2baedf53504af2715993b166950e185a55Andrew TrickScheduleDAGTopologicalSort(std::vector<SUnit> &sunits, SUnit *exitsu) 629ae692f2baedf53504af2715993b166950e185a55Andrew Trick : SUnits(sunits), ExitSU(exitsu) {} 630fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman 631fc54c552963545a81e4ea38e60460590afb2d5aeDan GohmanScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} 632