ScheduleDAG.cpp revision 47c144505b9be28ed22c626b3a407c11dba2fec5
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. 6592e946630d5f9bb092853b93501387dd216899b9Andrew Trickbool SUnit::addPred(const SDep &D) { 66c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // If this node already has this depenence, don't add a redundant one. 675cffa6fe271351a8fd80e7767b5d61a999acfa9bDan Gohman for (SmallVector<SDep, 4>::const_iterator I = Preds.begin(), E = Preds.end(); 685cffa6fe271351a8fd80e7767b5d61a999acfa9bDan Gohman I != E; ++I) 695cffa6fe271351a8fd80e7767b5d61a999acfa9bDan Gohman if (*I == D) 7092e946630d5f9bb092853b93501387dd216899b9Andrew Trick return false; 71c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Now add a corresponding succ to N. 72c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 73c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 74c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 75c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Update the bookkeeping. 76c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (D.getKind() == SDep::Data) { 77c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds < UINT_MAX && "NumPreds will overflow!"); 78c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs < UINT_MAX && "NumSuccs will overflow!"); 79c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++NumPreds; 80c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++N->NumSuccs; 81c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 82c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 83c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPredsLeft < UINT_MAX && "NumPredsLeft will overflow!"); 84c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++NumPredsLeft; 85c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 86c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 87c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccsLeft < UINT_MAX && "NumSuccsLeft will overflow!"); 88c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman ++N->NumSuccsLeft; 89c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 903f23744df4809eba94284e601e81489212c974d4Dan Gohman Preds.push_back(D); 91a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman N->Succs.push_back(P); 92a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 93a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 94a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 95a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 9692e946630d5f9bb092853b93501387dd216899b9Andrew Trick return true; 97c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 98c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 99c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// removePred - This removes the specified edge as a pred of the current 100c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// node if it exists. It also removes the current node as a successor of 101c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman/// the specified node. 102c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohmanvoid SUnit::removePred(const SDep &D) { 103c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the matching predecessor. 104c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman for (SmallVector<SDep, 4>::iterator I = Preds.begin(), E = Preds.end(); 105c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman I != E; ++I) 106c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (*I == D) { 107c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman bool FoundSucc = false; 108c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman // Find the corresponding successor in N. 109c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SDep P = D; 110c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman P.setSUnit(this); 111c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman SUnit *N = D.getSUnit(); 112c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman for (SmallVector<SDep, 4>::iterator II = N->Succs.begin(), 113c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman EE = N->Succs.end(); II != EE; ++II) 114c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman if (*II == P) { 115c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman FoundSucc = true; 116c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman N->Succs.erase(II); 117c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman break; 118c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 119c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman assert(FoundSucc && "Mismatching preds / succs lists!"); 1201f6a329f79b3568d379142f921f59c4143ddaa14Duncan Sands (void)FoundSucc; 121c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman Preds.erase(I); 122a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman // Update the bookkeeping. 123a1f50e2c2cad12dd8fe7ef80e394ee7a96654021Dan Gohman if (P.getKind() == SDep::Data) { 124c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPreds > 0 && "NumPreds will underflow!"); 125c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccs > 0 && "NumSuccs will underflow!"); 126c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --NumPreds; 127c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --N->NumSuccs; 128c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 129c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!N->isScheduled) { 130c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(NumPredsLeft > 0 && "NumPredsLeft will underflow!"); 131c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --NumPredsLeft; 132c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 133c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner if (!isScheduled) { 134c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner assert(N->NumSuccsLeft > 0 && "NumSuccsLeft will underflow!"); 135c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman --N->NumSuccsLeft; 136c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner } 137a80c859df377908c687d59e9c0fc65006796b719Dan Gohman if (P.getLatency() != 0) { 138a80c859df377908c687d59e9c0fc65006796b719Dan Gohman this->setDepthDirty(); 139a80c859df377908c687d59e9c0fc65006796b719Dan Gohman N->setHeightDirty(); 140a80c859df377908c687d59e9c0fc65006796b719Dan Gohman } 141c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman return; 142c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman } 143c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman} 144c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman 1453f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setDepthDirty() { 1468044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isDepthCurrent) return; 1473f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 1483f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 1498044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman do { 150e19c6362d21c872abaf2f71ea9a0f859f33ee9b5Dan Gohman SUnit *SU = WorkList.pop_back_val(); 1513f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->isDepthCurrent = false; 152f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_succ_iterator I = SU->Succs.begin(), 1538044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Succs.end(); I != E; ++I) { 1548044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *SuccSU = I->getSUnit(); 1558044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (SuccSU->isDepthCurrent) 1568044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(SuccSU); 1578044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 1588044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 1593f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1603f23744df4809eba94284e601e81489212c974d4Dan Gohman 1613f23744df4809eba94284e601e81489212c974d4Dan Gohmanvoid SUnit::setHeightDirty() { 1628044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (!isHeightCurrent) return; 1633f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 1643f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 1658044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman do { 166e19c6362d21c872abaf2f71ea9a0f859f33ee9b5Dan Gohman SUnit *SU = WorkList.pop_back_val(); 1673f23744df4809eba94284e601e81489212c974d4Dan Gohman SU->isHeightCurrent = false; 168f89e6e65770edccd8cc3baf2314b89ba894ffa4fDan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), 1698044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman E = SU->Preds.end(); I != E; ++I) { 1708044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman SUnit *PredSU = I->getSUnit(); 1718044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman if (PredSU->isHeightCurrent) 1728044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman WorkList.push_back(PredSU); 1738044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } 1748044e9b3af6e62afe89cd60bf76de22ae7138306Dan Gohman } while (!WorkList.empty()); 1753f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1763f23744df4809eba94284e601e81489212c974d4Dan Gohman 1773f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setDepthToAtLeast - Update this node's successors to reflect the 1783f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's depth just increased. 1793f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 180557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setDepthToAtLeast(unsigned NewDepth) { 181557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewDepth <= getDepth()) 1823f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 1833f23744df4809eba94284e601e81489212c974d4Dan Gohman setDepthDirty(); 1843f23744df4809eba94284e601e81489212c974d4Dan Gohman Depth = NewDepth; 1853f23744df4809eba94284e601e81489212c974d4Dan Gohman isDepthCurrent = true; 1863f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1873f23744df4809eba94284e601e81489212c974d4Dan Gohman 1883f23744df4809eba94284e601e81489212c974d4Dan Gohman/// setHeightToAtLeast - Update this node's predecessors to reflect the 1893f23744df4809eba94284e601e81489212c974d4Dan Gohman/// fact that this node's height just increased. 1903f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 191557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::setHeightToAtLeast(unsigned NewHeight) { 192557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin if (NewHeight <= getHeight()) 1933f23744df4809eba94284e601e81489212c974d4Dan Gohman return; 1943f23744df4809eba94284e601e81489212c974d4Dan Gohman setHeightDirty(); 1953f23744df4809eba94284e601e81489212c974d4Dan Gohman Height = NewHeight; 1963f23744df4809eba94284e601e81489212c974d4Dan Gohman isHeightCurrent = true; 1973f23744df4809eba94284e601e81489212c974d4Dan Gohman} 1983f23744df4809eba94284e601e81489212c974d4Dan Gohman 1993f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeDepth - Calculate the maximal path from the node to the exit. 2003f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 201557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeDepth() { 2023f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2033f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2041578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2053f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2063f23744df4809eba94284e601e81489212c974d4Dan Gohman 2073f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2083f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxPredDepth = 0; 2093f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_pred_iterator I = Cur->Preds.begin(), 2103f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Preds.end(); I != E; ++I) { 2113f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *PredSU = I->getSUnit(); 2123f23744df4809eba94284e601e81489212c974d4Dan Gohman if (PredSU->isDepthCurrent) 2133f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxPredDepth = std::max(MaxPredDepth, 2143f23744df4809eba94284e601e81489212c974d4Dan Gohman PredSU->Depth + I->getLatency()); 2153f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2163f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2173f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(PredSU); 2183f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2193f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2203f23744df4809eba94284e601e81489212c974d4Dan Gohman 2213f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2223f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2233f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxPredDepth != Cur->Depth) { 2243f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setDepthDirty(); 2253f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Depth = MaxPredDepth; 2263f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2273f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isDepthCurrent = true; 2283f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2291578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 2303f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2313f23744df4809eba94284e601e81489212c974d4Dan Gohman 2323f23744df4809eba94284e601e81489212c974d4Dan Gohman/// ComputeHeight - Calculate the maximal path from the node to the entry. 2333f23744df4809eba94284e601e81489212c974d4Dan Gohman/// 234557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwinvoid SUnit::ComputeHeight() { 2353f23744df4809eba94284e601e81489212c974d4Dan Gohman SmallVector<SUnit*, 8> WorkList; 2363f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(this); 2371578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 2383f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *Cur = WorkList.back(); 2393f23744df4809eba94284e601e81489212c974d4Dan Gohman 2403f23744df4809eba94284e601e81489212c974d4Dan Gohman bool Done = true; 2413f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned MaxSuccHeight = 0; 2423f23744df4809eba94284e601e81489212c974d4Dan Gohman for (SUnit::const_succ_iterator I = Cur->Succs.begin(), 2433f23744df4809eba94284e601e81489212c974d4Dan Gohman E = Cur->Succs.end(); I != E; ++I) { 2443f23744df4809eba94284e601e81489212c974d4Dan Gohman SUnit *SuccSU = I->getSUnit(); 2453f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SuccSU->isHeightCurrent) 2463f23744df4809eba94284e601e81489212c974d4Dan Gohman MaxSuccHeight = std::max(MaxSuccHeight, 2473f23744df4809eba94284e601e81489212c974d4Dan Gohman SuccSU->Height + I->getLatency()); 2483f23744df4809eba94284e601e81489212c974d4Dan Gohman else { 2493f23744df4809eba94284e601e81489212c974d4Dan Gohman Done = false; 2503f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.push_back(SuccSU); 2513f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2523f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2533f23744df4809eba94284e601e81489212c974d4Dan Gohman 2543f23744df4809eba94284e601e81489212c974d4Dan Gohman if (Done) { 2553f23744df4809eba94284e601e81489212c974d4Dan Gohman WorkList.pop_back(); 2563f23744df4809eba94284e601e81489212c974d4Dan Gohman if (MaxSuccHeight != Cur->Height) { 2573f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->setHeightDirty(); 2583f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->Height = MaxSuccHeight; 2593f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2603f23744df4809eba94284e601e81489212c974d4Dan Gohman Cur->isHeightCurrent = true; 2613f23744df4809eba94284e601e81489212c974d4Dan Gohman } 2621578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 2633f23744df4809eba94284e601e81489212c974d4Dan Gohman} 2643f23744df4809eba94284e601e81489212c974d4Dan Gohman 265343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// SUnit - Scheduling unit. It's an wrapper around either a single SDNode or 266343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman/// a group of nodes flagged together. 267343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dump(const ScheduleDAG *G) const { 2684b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "SU(" << NodeNum << "): "; 269343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman G->dumpNode(this); 270343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 271343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 272343f0c046702831a4a6aec951b6a297a23241a55Dan Gohmanvoid SUnit::dumpAll(const ScheduleDAG *G) const { 273343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman dump(G); 274343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 2754b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # preds left : " << NumPredsLeft << "\n"; 2764b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " # succs left : " << NumSuccsLeft << "\n"; 27792e946630d5f9bb092853b93501387dd216899b9Andrew Trick dbgs() << " # rdefs left : " << NumRegDefsLeft << "\n"; 2784b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Latency : " << Latency << "\n"; 2794b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Depth : " << Depth << "\n"; 2804b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Height : " << Height << "\n"; 281343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman 282343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Preds.size() != 0) { 2834b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Predecessors:\n"; 284343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Preds.begin(), E = Preds.end(); 285343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 2864b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " "; 28754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (I->getKind()) { 2884b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Data: dbgs() << "val "; break; 2894b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Anti: dbgs() << "anti"; break; 2904b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Output: dbgs() << "out "; break; 2914b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Order: dbgs() << "ch "; break; 29254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 2930b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << "SU(" << I->getSUnit()->NodeNum << ")"; 29454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 2954b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 2964b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 2974cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick if (I->isAssignedRegDep()) 2980b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << " Reg=" << PrintReg(I->getReg(), G->TRI); 2994b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 300343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 301343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 302343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman if (Succs.size() != 0) { 3034b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " Successors:\n"; 304343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman for (SUnit::const_succ_iterator I = Succs.begin(), E = Succs.end(); 305343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman I != E; ++I) { 3064b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " "; 30754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (I->getKind()) { 3084b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Data: dbgs() << "val "; break; 3094b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Anti: dbgs() << "anti"; break; 3104b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Output: dbgs() << "out "; break; 3114b134d1661214427834bf89ef1183f458919837eDavid Greene case SDep::Order: dbgs() << "ch "; break; 31254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 3130b923d9ee9e406c7dadc0803106656391a0ffd68Jakob Stoklund Olesen dbgs() << "SU(" << I->getSUnit()->NodeNum << ")"; 31454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isArtificial()) 3154b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << " *"; 3164b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << ": Latency=" << I->getLatency(); 3174b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 318343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 319343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman } 3204b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "\n"; 321343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman} 322a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 323a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 3244c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// VerifyScheduledDAG - Verify that all SUnits were scheduled and that 3254c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick/// their state is consistent. Return the number of scheduled nodes. 326a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman/// 3274c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trickunsigned ScheduleDAG::VerifyScheduledDAG(bool isBottomUp) { 328a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman bool AnyNotSched = false; 329a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman unsigned DeadNodes = 0; 330a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman for (unsigned i = 0, e = SUnits.size(); i != e; ++i) { 331a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!SUnits[i].isScheduled) { 332a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPreds == 0 && SUnits[i].NumSuccs == 0) { 333a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman ++DeadNodes; 334a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman continue; 335a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 336a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3374b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 338a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3394b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has not been scheduled!\n"; 340a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 341a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 3423f23744df4809eba94284e601e81489212c974d4Dan Gohman if (SUnits[i].isScheduled && 3434de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin (isBottomUp ? SUnits[i].getHeight() : SUnits[i].getDepth()) > 3443f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned(INT_MAX)) { 345a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3464b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 347a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3484b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has an unexpected " 3493f23744df4809eba94284e601e81489212c974d4Dan Gohman << (isBottomUp ? "Height" : "Depth") << " value!\n"; 350a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 351a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 352a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (isBottomUp) { 353a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumSuccsLeft != 0) { 354a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3554b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 356a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3574b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has successors left!\n"; 358a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 359a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 360a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } else { 361a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (SUnits[i].NumPredsLeft != 0) { 362a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman if (!AnyNotSched) 3634b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "*** Scheduling failed! ***\n"; 364a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman SUnits[i].dump(this); 3654b134d1661214427834bf89ef1183f458919837eDavid Greene dbgs() << "has predecessors left!\n"; 366a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman AnyNotSched = true; 367a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 368a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 369a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman } 370a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman assert(!AnyNotSched); 3714c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick return SUnits.size() - DeadNodes; 372a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman} 373a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 37421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 3759f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// InitDAGTopologicalSorting - create the initial topological 37621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// ordering from the DAG to be scheduled. 37721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 3789f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// The idea of the algorithm is taken from 37921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Online algorithms for managing the topological order of 38021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// a directed acyclic graph" by David J. Pearce and Paul H.J. Kelly 3819f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This is the MNR algorithm, which was first introduced by 3829f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// A. Marchetti-Spaccamela, U. Nanni and H. Rohnert in 38321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// "Maintaining a topological order under edge insertions". 38421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 3859f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Short description of the algorithm: 38621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 38721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Topological ordering, ord, of a DAG maps each node to a topological 38821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// index so that for all edges X->Y it is the case that ord(X) < ord(Y). 38921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 3909f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// This means that if there is a path from the node X to the node Z, 39121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// then ord(X) < ord(Z). 39221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 39321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// This property can be used to check for reachability of nodes: 3949f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// if Z is reachable from X, then an insertion of the edge Z->X would 39521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 39621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 39721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// The algorithm first computes a topological ordering for the DAG by 39821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// initializing the Index2Node and Node2Index arrays and then tries to keep 39921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the ordering up-to-date after edge insertions by reordering the DAG. 40021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// 40121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// On insertion of the edge X->Y, the algorithm first marks by calling DFS 40221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// the nodes reachable from Y, and then shifts them using Shift to lie 40321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// immediately after X in Index2Node. 40421d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::InitDAGTopologicalSorting() { 40521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned DAGSize = SUnits.size(); 40621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit*> WorkList; 40721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.reserve(DAGSize); 40821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 40921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node.resize(DAGSize); 41021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index.resize(DAGSize); 41121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 41221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Initialize the data structures. 41321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 41421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 41521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int NodeNum = SU->NodeNum; 41621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman unsigned Degree = SU->Succs.size(); 41721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Temporarily use the Node2Index array as scratch space for degree counts. 41821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[NodeNum] = Degree; 41921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 42021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is it a node without dependencies? 42121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Degree == 0) { 42221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(SU->Succs.empty() && "SUnit should have no successors"); 42321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Collect leaf nodes. 42421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 42521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 4269f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 42721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 42821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int Id = DAGSize; 42921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman while (!WorkList.empty()) { 43021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = WorkList.back(); 43121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 43221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(SU->NodeNum, --Id); 43321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 43421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 43554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *SU = I->getSUnit(); 43621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!--Node2Index[SU->NodeNum]) 43721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If all dependencies of the node are processed already, 43821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then the node can be computed now. 43921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 44021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 44121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 44221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 44321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.resize(DAGSize); 44421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 44521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#ifndef NDEBUG 44621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Check correctness of the ordering 44721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned i = 0, e = DAGSize; i != e; ++i) { 44821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SUnit *SU = &SUnits[i]; 44921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::const_pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 45021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) { 4519f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby assert(Node2Index[SU->NodeNum] > Node2Index[I->getSUnit()->NodeNum] && 45221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman "Wrong topological sorting"); 45321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 45421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 45521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#endif 45621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 45721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 4587a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// AddPred - Updates the topological ordering to accommodate an edge 45921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// to be added from SUnit X to SUnit Y. 46021d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::AddPred(SUnit *Y, SUnit *X) { 46121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 46221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[Y->NodeNum]; 46321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[X->NodeNum]; 46421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 46521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(X) < Ord(Y) ? 46621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 46721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Update the topological order. 46821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 46921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(Y, UpperBound, HasLoop); 47021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman assert(!HasLoop && "Inserted edge creates a loop!"); 47121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Recompute topological indexes. 47221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Shift(Visited, LowerBound, UpperBound); 47321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 47421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 47521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 4767a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner/// RemovePred - Updates the topological ordering to accommodate an 47721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// an edge to be removed from the specified node N from the predecessors 47821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// of the current node M. 47921d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::RemovePred(SUnit *M, SUnit *N) { 48021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // InitDAGTopologicalSorting(); 48121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 48221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 48321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// DFS - Make a DFS traversal to mark all nodes reachable from SU and mark 48421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// all nodes affected by the edge insertion. These nodes will later get new 48521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// topological indexes by means of the Shift method. 486e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanvoid ScheduleDAGTopologicalSort::DFS(const SUnit *SU, int UpperBound, 4875078293cc28dd03236384fa0a3b6c8347e0701fbChris Lattner bool &HasLoop) { 48821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<const SUnit*> WorkList; 4899f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby WorkList.reserve(SUnits.size()); 49021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 49121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.push_back(SU); 4921578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman do { 49321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman SU = WorkList.back(); 49421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman WorkList.pop_back(); 49521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.set(SU->NodeNum); 49621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (int I = SU->Succs.size()-1; I >= 0; --I) { 49754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman int s = SU->Succs[I].getSUnit()->NodeNum; 49821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Node2Index[s] == UpperBound) { 4999f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby HasLoop = true; 50021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return; 50121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 50221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Visit successors if not already and in affected region. 50321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (!Visited.test(s) && Node2Index[s] < UpperBound) { 50454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman WorkList.push_back(SU->Succs[I].getSUnit()); 5059f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5069f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby } 5071578f8486d401a16bdfbe7f27cd4d644920000bfDan Gohman } while (!WorkList.empty()); 50821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 50921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5109f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby/// Shift - Renumber the nodes so that the topological ordering is 51121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// preserved. 5129f71f801b51cdc7df388b2693398cfea69fe67c7John Mosbyvoid ScheduleDAGTopologicalSort::Shift(BitVector& Visited, int LowerBound, 513e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman int UpperBound) { 51421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> L; 51521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int shift = 0; 51621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int i; 51721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 51821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (i = LowerBound; i <= UpperBound; ++i) { 51921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // w is node at topological index i. 52021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int w = Index2Node[i]; 52121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (Visited.test(w)) { 52221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Unmark. 52321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(w); 52421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman L.push_back(w); 52521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman shift = shift + 1; 52621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } else { 52721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(w, i - shift); 52821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 52921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 53021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 53121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (unsigned j = 0; j < L.size(); ++j) { 53221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Allocate(L[j], i - shift); 53321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman i = i + 1; 53421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 53521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 53621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 53721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 53821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// WillCreateCycle - Returns true if adding an edge from SU to TargetSU will 53921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// create a cycle. 54021d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanbool ScheduleDAGTopologicalSort::WillCreateCycle(SUnit *SU, SUnit *TargetSU) { 54121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (IsReachable(TargetSU, SU)) 54221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 54321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman for (SUnit::pred_iterator I = SU->Preds.begin(), E = SU->Preds.end(); 54421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman I != E; ++I) 54554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (I->isAssignedRegDep() && 54654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman IsReachable(TargetSU, I->getSUnit())) 54721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return true; 54821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return false; 54921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 55021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 55121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// IsReachable - Checks if SU is reachable from TargetSU. 552e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohmanbool ScheduleDAGTopologicalSort::IsReachable(const SUnit *SU, 553e3a49cd944ad41eba5a594f1de773d531ad25403Dan Gohman const SUnit *TargetSU) { 55421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // If insertion of the edge SU->TargetSU would create a cycle 55521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // then there is a path from TargetSU to SU. 55621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman int UpperBound, LowerBound; 55721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman LowerBound = Node2Index[TargetSU->NodeNum]; 55821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman UpperBound = Node2Index[SU->NodeNum]; 55921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool HasLoop = false; 56021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman // Is Ord(TargetSU) < Ord(SU) ? 56121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman if (LowerBound < UpperBound) { 56221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Visited.reset(); 5639f71f801b51cdc7df388b2693398cfea69fe67c7John Mosby // There may be a path from TargetSU to SU. Check for it. 56421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman DFS(TargetSU, UpperBound, HasLoop); 56521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman } 56621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman return HasLoop; 56721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 56821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 56921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman/// Allocate - assign the topological index to the node n. 57021d9003087c9a707e6cd95460136b499df358fb8Dan Gohmanvoid ScheduleDAGTopologicalSort::Allocate(int n, int index) { 57121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Node2Index[n] = index; 57221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman Index2Node[index] = n; 57321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman} 57421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 5759f71f801b51cdc7df388b2693398cfea69fe67c7John MosbyScheduleDAGTopologicalSort:: 5769f71f801b51cdc7df388b2693398cfea69fe67c7John MosbyScheduleDAGTopologicalSort(std::vector<SUnit> &sunits) : SUnits(sunits) {} 577fc54c552963545a81e4ea38e60460590afb2d5aeDan Gohman 578fc54c552963545a81e4ea38e60460590afb2d5aeDan GohmanScheduleHazardRecognizer::~ScheduleHazardRecognizer() {} 579