ScheduleDAG.cpp revision 1f6a329f79b3568d379142f921f59c4143ddaa14
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 294cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trickcl::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 3479ce276083ced01256a0eb7d80731e4948ca6e87Dan GohmanScheduleDAG::ScheduleDAG(MachineFunction &mf) 3547ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman : TM(mf.getTarget()), 3679ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman TII(TM.getInstrInfo()), 3779ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman TRI(TM.getRegisterInfo()), 3879ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman MF(mf), MRI(mf.getRegInfo()), 399e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman EntrySU(), ExitSU() { 404cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifndef NDEBUG 414cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick StressSched = StressSchedOpt; 424cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 43343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 44343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 45343f0c046702831a4a6aec951b6a297a23241a55Dan GohmanScheduleDAG::~ScheduleDAG() {} 46343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 472da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick/// getInstrDesc helper to handle SDNodes. 48e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Chengconst MCInstrDesc *ScheduleDAG::getNodeDesc(const SDNode *Node) const { 4924312230ada6f4cfa8776351dafb12eea8a81b33Andrew Trick if (!Node || !Node->isMachineOpcode()) return NULL; 502da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick return &TII->get(Node->getMachineOpcode()); 512da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick} 522da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 53343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// dump - dump the schedule. 54343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid ScheduleDAG::dumpSchedule() const { 55343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; i++) { 56343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (SUnit *SU = Sequence[i]) 57343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman SU->dump(this); 58343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman else 594b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "**** NOOP ****\n"; 60343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 61343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 62343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 63343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 64343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// Run - perform scheduling. 65343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// 6647ac0f0c7c39289f5970688154e385be22b7f293Dan Gohmanvoid ScheduleDAG::Run(MachineBasicBlock *bb, 6747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman MachineBasicBlock::iterator insertPos) { 6847ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman BB = bb; 6947ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman InsertPos = insertPos; 70f7119393a97c2a10757084b6bc186380f8c19a73Dan Gohman 7179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman SUnits.clear(); 7279ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman Sequence.clear(); 739e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman EntrySU = SUnit(); 749e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman ExitSU = SUnit(); 7579ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman 76343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman Schedule(); 7747ac0f0c7c39289f5970688154e385be22b7f293Dan Gohman 78960bb85b2165bd69feea3fc07d9cadd2da821c72Bill Wendling DEBUG({ 794b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Final schedule ***\n"; 80960bb85b2165bd69feea3fc07d9cadd2da821c72Bill Wendling dumpSchedule(); 814b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << '\n'; 82960bb85b2165bd69feea3fc07d9cadd2da821c72Bill Wendling }); 83343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 84343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 85c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// addPred - This adds the specified edge as a pred of the current node if 86c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// not already. It also adds the current node as a successor of the 87c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// specified node. 8892e946630d5f9bb092853b93501387dd216899b9Andrew Trickbool SUnit::addPred(const SDep &D) { 89c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // If this node already has this depenence, don't add a redundant one. 905cffa6fe271351a8fd80e7767b5d61a999acfa9bDan Gohman for (SmallVector<SDep, 4>::const_iterator I = Preds.begin(), E = Preds.end(); 915cffa6fe271351a8fd80e7767b5d61a999acfa9bDan Gohman I != E; ++I) 925cffa6fe271351a8fd80e7767b5d61a999acfa9bDan Gohman if (*I == D) 9392e946630d5f9bb092853b93501387dd216899b9Andrew Trick return false; 94c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Now add a corresponding succ to N. 95c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 96c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 97c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 98c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Update the bookkeeping. 99c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (D.getKind() == SDep::Data) { 100c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds < UINT_MAX && "NumPreds will overflow!"); 101c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs < UINT_MAX && "NumSuccs will overflow!"); 102c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++NumPreds; 103c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++N->NumSuccs; 104c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 105c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 106c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPredsLeft < UINT_MAX && "NumPredsLeft will overflow!"); 107c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++NumPredsLeft; 108c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 109c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 110c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!"); 111c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++N->NumSuccsLeft; 112c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 1133f23744df4809eba94284e601e81489212c974d4Dan Gohman Preds.push_back(D); 114a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman N->Succs.push_back(P); 115a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 116a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 117a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 118a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 11992e946630d5f9bb092853b93501387dd216899b9Andrew Trick return true; 120c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 121c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 122c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// removePred - This removes the specified edge as a pred of the current 123c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// node if it exists. It also removes the current node as a successor of 124c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// the specified node. 125c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohmanvoid SUnit::removePred(const SDep &D) { 126c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the matching predecessor. 127c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 128c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman I != E; ++I) 129c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (*I == D) { 130c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman bool FoundSucc = false; 131c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the corresponding successor in N. 132c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 133c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 134c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 135c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(), 136c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman EE = N->Succs.end(); II != EE; ++II) 137c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (*II == P) { 138c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman FoundSucc = true; 139c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman N->Succs.erase(II); 140c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman break; 141c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 142c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman assert(FoundSucc && "Mismatching preds / succs lists!"); 1431f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)FoundSucc; 144c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman Preds.erase(I); 145a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman // Update the bookkeeping. 146a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman if (P.getKind() == SDep::Data) { 147c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds > 0 && "NumPreds will underflow!"); 148c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs > 0 && "NumSuccs will underflow!"); 149c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --NumPreds; 150c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --N->NumSuccs; 151c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 152c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 153c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!"); 154c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --NumPredsLeft; 155c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 156c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 157c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!"); 158c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --N->NumSuccsLeft; 159c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 160a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 161a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 162a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 163a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 164c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman return; 165c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 166c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 167c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 1683f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setDepthDirty() { 1698044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isDepthCurrent) return; 1703f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 1713f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 1728044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman do { 173e19c6362d21c872abaf2f71ea9a0f859f33ee9b5Dan Gohman SUnit *SU = WorkList.pop_back_val(); 1743f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->isDepthCurrent = false; 175f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), 1768044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Succs.end(); I != E; ++I) { 1778044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *SuccSU = I->getSUnit(); 1788044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (SuccSU->isDepthCurrent) 1798044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(SuccSU); 1808044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 1818044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 1823f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1833f23744df4809eba94284e601e81489212c974d4Dan Gohman 1843f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setHeightDirty() { 1858044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isHeightCurrent) 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->isHeightCurrent = false; 191f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), 1928044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Preds.end(); I != E; ++I) { 1938044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *PredSU = I->getSUnit(); 1948044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (PredSU->isHeightCurrent) 1958044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(PredSU); 1968044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 1978044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 1983f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1993f23744df4809eba94284e601e81489212c974d4Dan Gohman 2003f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setDepthToAtLeast - Update this node's successors to reflect the 2013f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's depth just increased. 2023f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 203557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setDepthToAtLeast(unsigned NewDepth) { 204557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewDepth <= getDepth()) 2053f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 2063f23744df4809eba94284e601e81489212c974d4Dan Gohman setDepthDirty(); 2073f23744df4809eba94284e601e81489212c974d4Dan Gohman Depth = NewDepth; 2083f23744df4809eba94284e601e81489212c974d4Dan Gohman isDepthCurrent = true; 2093f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2103f23744df4809eba94284e601e81489212c974d4Dan Gohman 2113f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setHeightToAtLeast - Update this node's predecessors to reflect the 2123f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's height just increased. 2133f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 214557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setHeightToAtLeast(unsigned NewHeight) { 215557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewHeight <= getHeight()) 2163f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 2173f23744df4809eba94284e601e81489212c974d4Dan Gohman setHeightDirty(); 2183f23744df4809eba94284e601e81489212c974d4Dan Gohman Height = NewHeight; 2193f23744df4809eba94284e601e81489212c974d4Dan Gohman isHeightCurrent = true; 2203f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2213f23744df4809eba94284e601e81489212c974d4Dan Gohman 2223f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeDepth - Calculate the maximal path from the node to the exit. 2233f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 224557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeDepth() { 2253f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2263f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2271578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2283f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2293f23744df4809eba94284e601e81489212c974d4Dan Gohman 2303f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2313f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxPredDepth = 0; 2323f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_pred_iterator I = Cur->Preds.begin(), 2333f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Preds.end(); I != E; ++I) { 2343f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *PredSU = I->getSUnit(); 2353f23744df4809eba94284e601e81489212c974d4Dan Gohman if (PredSU->isDepthCurrent) 2363f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxPredDepth = std::max(MaxPredDepth, 2373f23744df4809eba94284e601e81489212c974d4Dan Gohman PredSU->Depth + I->getLatency()); 2383f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2393f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2403f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(PredSU); 2413f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2423f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2433f23744df4809eba94284e601e81489212c974d4Dan Gohman 2443f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2453f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2463f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxPredDepth != Cur->Depth) { 2473f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setDepthDirty(); 2483f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Depth = MaxPredDepth; 2493f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2503f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isDepthCurrent = true; 2513f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2521578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 2533f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2543f23744df4809eba94284e601e81489212c974d4Dan Gohman 2553f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeHeight - Calculate the maximal path from the node to the entry. 2563f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 257557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeHeight() { 2583f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2593f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2601578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2613f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2623f23744df4809eba94284e601e81489212c974d4Dan Gohman 2633f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2643f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxSuccHeight = 0; 2653f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_succ_iterator I = Cur->Succs.begin(), 2663f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Succs.end(); I != E; ++I) { 2673f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *SuccSU = I->getSUnit(); 2683f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SuccSU->isHeightCurrent) 2693f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxSuccHeight = std::max(MaxSuccHeight, 2703f23744df4809eba94284e601e81489212c974d4Dan Gohman SuccSU->Height + I->getLatency()); 2713f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2723f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2733f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(SuccSU); 2743f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2753f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2763f23744df4809eba94284e601e81489212c974d4Dan Gohman 2773f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2783f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2793f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxSuccHeight != Cur->Height) { 2803f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setHeightDirty(); 2813f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Height = MaxSuccHeight; 2823f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2833f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isHeightCurrent = true; 2843f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2851578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 2863f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2873f23744df4809eba94284e601e81489212c974d4Dan Gohman 288343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 289343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a group of nodes flagged together. 290343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dump(const ScheduleDAG *G) const { 2914b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "SU(" << NodeNum << "): "; 292343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman G->dumpNode(this); 293343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 294343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 295343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dumpAll(const ScheduleDAG *G) const { 296343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman dump(G); 297343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 2984b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # preds left : " << NumPredsLeft << "\n"; 2994b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # succs left : " << NumSuccsLeft << "\n"; 30092e946630d5f9bb092853b93501387dd216899b9Andrew Trick dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n"; 3014b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Latency : " << Latency << "\n"; 3024b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Depth : " << Depth << "\n"; 3034b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Height : " << Height << "\n"; 304343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 305343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Preds.size() != 0) { 3064b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Predecessors:\n"; 307343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 308343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 3094b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " "; 31054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (I->getKind()) { 3114b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Data: dbgs() << "val "; break; 3124b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Anti: dbgs() << "anti"; break; 3134b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Output: dbgs() << "out "; break; 3144b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Order: dbgs() << "ch "; break; 31554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 3164b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "#"; 3174b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 31854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 3194b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 3204b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 3214cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick if (I->isAssignedRegDep()) 3224cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick dbgs() << " Reg=" << G->TRI->getName(I->getReg()); 3234b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 324343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 325343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 326343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Succs.size() != 0) { 3274b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Successors:\n"; 328343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.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 } 3374b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "#"; 3384b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << I->getSUnit() << " - SU(" << I->getSUnit()->NodeNum << ")"; 33954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 3404b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 3414b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 3424b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 343343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 344343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 3454b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 346343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 347a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 348a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 349a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// VerifySchedule - Verify that all SUnits were scheduled and that 350a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// their state is consistent. 351a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// 352a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohmanvoid ScheduleDAG::VerifySchedule(bool isBottomUp) { 353a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman bool AnyNotSched = false; 354a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman unsigned DeadNodes = 0; 355a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman unsigned Noops = 0; 356a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 357a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!SUnits[i].isScheduled) { 358a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 359a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman ++DeadNodes; 360a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman continue; 361a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 362a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3634b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 364a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3654b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has not been scheduled!\n"; 366a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 367a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 3683f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SUnits[i].isScheduled && 3694de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getDepth()) > 3703f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned(INT_MAX)) { 371a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3724b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 373a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3744b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has an unexpected " 3753f23744df4809eba94284e601e81489212c974d4Dan Gohman << (isBottomUp ? "Height" : "Depth") << " value!\n"; 376a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 377a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 378a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (isBottomUp) { 379a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumSuccsLeft != 0) { 380a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3814b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 382a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3834b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has successors left!\n"; 384a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 385a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 386a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } else { 387a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPredsLeft != 0) { 388a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3894b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 390a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3914b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has predecessors left!\n"; 392a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 393a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 394a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 395a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 396a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman for (unsigned i = 0, e = Sequence.size(); i != e; ++i) 397a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!Sequence[i]) 398a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman ++Noops; 399a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman assert(!AnyNotSched); 400a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman assert(Sequence.size() + DeadNodes - Noops == SUnits.size() && 401a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman "The number of nodes scheduled doesn't match the expected number!"); 402a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman} 403a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 40421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 4059f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// InitDAGTopologicalSorting - create the initial topological 40621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// ordering from the DAG to be scheduled. 40721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4089f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// The idea of the algorithm is taken from 40921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Online algorithms for managing the topological order of 41021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 4119f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This is the MNR algorithm, which was first introduced by 4129f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 41321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Maintaining a topological order under edge insertions". 41421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4159f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Short description of the algorithm: 41621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 41721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Topological ordering, ord, of a DAG maps each node to a topological 41821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 41921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 4209f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This means that if there is a path from the node X to the node Z, 42121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// then ord(X) < ord(Z). 42221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 42321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// This property can be used to check for reachability of nodes: 4249f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// if Z is reachable from X, then an insertion of the edge Z->X would 42521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 42621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 42721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// The algorithm first computes a topological ordering for the DAG by 42821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// initializing the Index2Node and Node2Index arrays and then tries to keep 42921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the ordering up-to-date after edge insertions by reordering the DAG. 43021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 43121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 43221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the nodes reachable from Y, and then shifts them using Shift to lie 43321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// immediately after X in Index2Node. 43421d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 43521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned DAGSize = SUnits.size(); 43621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit*> WorkList; 43721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.reserve(DAGSize); 43821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 43921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node.resize(DAGSize); 44021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index.resize(DAGSize); 44121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 44221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Initialize the data structures. 44321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 44421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 44521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int NodeNum = SU->NodeNum; 44621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned Degree = SU->Succs.size(); 44721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Temporarily use the Node2Index array as scratch space for degree counts. 44821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[NodeNum] = Degree; 44921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 45021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is it a node without dependencies? 45121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Degree == 0) { 45221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(SU->Succs.empty() && "SUnit should have no successors"); 45321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Collect leaf nodes. 45421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 45521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 4569f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 45721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 45821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int Id = DAGSize; 45921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman while (!WorkList.empty()) { 46021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = WorkList.back(); 46121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 46221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(SU->NodeNum, --Id); 46321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 46421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 46554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SU = I->getSUnit(); 46621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!--Node2Index[SU->NodeNum]) 46721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If all dependencies of the node are processed already, 46821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then the node can be computed now. 46921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 47021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 47121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 47221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 47321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.resize(DAGSize); 47421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 47521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#ifndef NDEBUG 47621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Check correctness of the ordering 47721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 47821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 47921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 48021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 4819f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 48221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman "Wrong topological sorting"); 48321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 48421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 48521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#endif 48621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 48721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 4887a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// AddPred - Updates the topological ordering to accommodate an edge 48921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// to be added from SUnit X to SUnit Y. 49021d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 49121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 49221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[Y->NodeNum]; 49321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[X->NodeNum]; 49421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 49521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(X) < Ord(Y) ? 49621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 49721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Update the topological order. 49821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 49921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(Y, UpperBound, HasLoop); 50021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(!HasLoop && "Inserted edge creates a loop!"); 50121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Recompute topological indexes. 50221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Shift(Visited, LowerBound, UpperBound); 50321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 50421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 50521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5067a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// RemovePred - Updates the topological ordering to accommodate an 50721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// an edge to be removed from the specified node N from the predecessors 50821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// of the current node M. 50921d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 51021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // InitDAGTopologicalSorting(); 51121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 51221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 51321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 51421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// all nodes affected by the edge insertion. These nodes will later get new 51521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// topological indexes by means of the Shift method. 516e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanvoid ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 5175078293cc28dd03236384fa0a3b6c8347e0701fbChris Lattner bool &HasLoop) { 51821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<const SUnit*> WorkList; 5199f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby WorkList.reserve(SUnits.size()); 52021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 52121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 5221578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 52321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SU = WorkList.back(); 52421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 52521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.set(SU->NodeNum); 52621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (int I = SU->Succs.size()-1; I >= 0; --I) { 52754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman int s = SU->Succs[I].getSUnit()->NodeNum; 52821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Node2Index[s] == UpperBound) { 5299f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby HasLoop = true; 53021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return; 53121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 53221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Visit successors if not already and in affected region. 53321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!Visited.test(s) && Node2Index[s] < UpperBound) { 53454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman WorkList.push_back(SU->Succs[I].getSUnit()); 5359f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5369f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5371578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 53821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 53921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5409f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Shift - Renumber the nodes so that the topological ordering is 54121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// preserved. 5429f71f801b51cdc7df388b2693398cfea69fe67c7John Mosbyvoid ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 543e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman int UpperBound) { 54421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> L; 54521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int shift = 0; 54621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int i; 54721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 54821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (i = LowerBound; i <= UpperBound; ++i) { 54921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // w is node at topological index i. 55021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int w = Index2Node[i]; 55121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Visited.test(w)) { 55221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Unmark. 55321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(w); 55421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman L.push_back(w); 55521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman shift = shift + 1; 55621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } else { 55721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(w, i - shift); 55821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 55921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 56021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 56121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned j = 0; j < L.size(); ++j) { 56221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(L[j], i - shift); 56321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman i = i + 1; 56421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 56521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 56621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 56721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 56821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 56921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 57021d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanbool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 57121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (IsReachable(TargetSU, SU)) 57221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 57321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 57421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) 57554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep() && 57654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman IsReachable(TargetSU, I->getSUnit())) 57721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 57821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return false; 57921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 58021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 58121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// IsReachable - Checks if SU is reachable from TargetSU. 582e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanbool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 583e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman const SUnit *TargetSU) { 58421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If insertion of the edge SU->TargetSU would create a cycle 58521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then there is a path from TargetSU to SU. 58621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 58721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[TargetSU->NodeNum]; 58821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[SU->NodeNum]; 58921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 59021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(TargetSU) < Ord(SU) ? 59121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 59221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 5939f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby // There may be a path from TargetSU to SU. Check for it. 59421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(TargetSU, UpperBound, HasLoop); 59521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 59621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return HasLoop; 59721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 59821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 59921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Allocate - assign the topological index to the node n. 60021d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::Allocate(int n, int index) { 60121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[n] = index; 60221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node[index] = n; 60321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 60421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 6059f71f801b51cdc7df388b2693398cfea69fe67c7John MosbyScheduleDAGTopologicalSort:: 6069f71f801b51cdc7df388b2693398cfea69fe67c7John MosbyScheduleDAGTopologicalSort(std::vector<SUnit> &sunits) : SUnits(sunits) {} 607fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman 608fc54c552963545a81e4ea38e60460590afb2d5aeDan GohmanScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} 609