1894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// 2894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 3894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// The LLVM Compiler Infrastructure 4894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 5894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file is distributed under the University of Illinois Open Source 6894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// License. See LICENSE.TXT for details. 7894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 8894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 9894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 10894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// This file implements the ScheduleDAG class, which is used as the common 11894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// base class for instruction schedulers. 12894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman// 13894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman//===----------------------------------------------------------------------===// 14894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 15894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef LLVM_CODEGEN_SCHEDULEDAG_H 16894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#define LLVM_CODEGEN_SCHEDULEDAG_H 17894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 18894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/CodeGen/MachineBasicBlock.h" 19894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/Target/TargetMachine.h" 20894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/DenseMap.h" 21894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/BitVector.h" 22894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/GraphTraits.h" 23894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/SmallVector.h" 24894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#include "llvm/ADT/PointerIntPair.h" 25894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 26894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Baumannamespace llvm { 27894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class AliasAnalysis; 28894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class SUnit; 29894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class MachineConstantPool; 30894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class MachineFunction; 31894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class MachineRegisterInfo; 32894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class MachineInstr; 33894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class TargetRegisterInfo; 34894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class ScheduleDAG; 35894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class SDNode; 36894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class TargetInstrInfo; 3719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman class MCInstrDesc; 38894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class TargetMachine; 39894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class TargetRegisterClass; 40894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template<class Graph> class GraphWriter; 41894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 42894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SDep - Scheduling dependency. This represents one direction of an 43894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// edge in the scheduling DAG. 44894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class SDep { 45894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 46894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Kind - These are the different kinds of scheduling dependencies. 47894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman enum Kind { 48894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Data, ///< Regular data dependence (aka true-dependence). 49894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Anti, ///< A register anti-dependedence (aka WAR). 50894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Output, ///< A register output-dependence (aka WAW). 51894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Order ///< Any other ordering dependency. 52894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 53894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 54894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 55894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Dep - A pointer to the depending/depended-on SUnit, and an enum 56894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// indicating the kind of the dependency. 57894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman PointerIntPair<SUnit *, 2, Kind> Dep; 58894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 59894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Contents - A union discriminated by the dependence kind. 60894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman union { 61894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Reg - For Data, Anti, and Output dependencies, the associated 62894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// register. For Data dependencies that don't currently have a register 63894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// assigned, this is set to zero. 64894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Reg; 65894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 66894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Order - Additional information about Order dependencies. 67894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman struct { 68894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isNormalMemory - True if both sides of the dependence 69894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// access memory in non-volatile and fully modeled ways. 70894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isNormalMemory : 1; 71894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 72894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isMustAlias - True if both sides of the dependence are known to 73894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// access the same memory. 74894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isMustAlias : 1; 75894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 76894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isArtificial - True if this is an artificial dependency, meaning 77894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// it is not necessary for program correctness, and may be safely 78894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// deleted if necessary. 79894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isArtificial : 1; 80894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } Order; 81894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } Contents; 82894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 83894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Latency - The time associated with this edge. Often this is just 84894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// the value of the Latency field of the predecessor, however advanced 85894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// models may provide additional information about specific edges. 86894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Latency; 87894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 88894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 89894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SDep - Construct a null SDep. This is only for use by container 90894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// classes which require default constructors. SUnits may not 91894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// have null SDep edges. 92894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDep() : Dep(0, Data) {} 93894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 94894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SDep - Construct an SDep with the specified values. 95894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0, 96894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isNormalMemory = false, bool isMustAlias = false, 97894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isArtificial = false) 98894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Dep(S, kind), Contents(), Latency(latency) { 99894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (kind) { 100894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Anti: 101894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Output: 102894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Reg != 0 && 103894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "SDep::Anti and SDep::Output must use a non-zero Reg!"); 104894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // fall through 105894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Data: 106894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!isMustAlias && "isMustAlias only applies with SDep::Order!"); 107894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!isArtificial && "isArtificial only applies with SDep::Order!"); 108894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Contents.Reg = Reg; 109894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 110894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Order: 111894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(Reg == 0 && "Reg given for non-register dependence!"); 112894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Contents.Order.isNormalMemory = isNormalMemory; 113894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Contents.Order.isMustAlias = isMustAlias; 114894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Contents.Order.isArtificial = isArtificial; 115894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman break; 116894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 117894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 118894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 119894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator==(const SDep &Other) const { 120894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Dep != Other.Dep || Latency != Other.Latency) return false; 121894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman switch (Dep.getInt()) { 122894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Data: 123894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Anti: 124894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Output: 125894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Contents.Reg == Other.Contents.Reg; 126894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman case Order: 127894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Contents.Order.isNormalMemory == 128894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Other.Contents.Order.isNormalMemory && 129894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias && 130894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Contents.Order.isArtificial == Other.Contents.Order.isArtificial; 131894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 132894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(0 && "Invalid dependency kind!"); 133894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 134894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 135894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 136894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator!=(const SDep &Other) const { 137894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return !operator==(Other); 138894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 139894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 140894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getLatency - Return the latency value for this edge, which roughly 141894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// means the minimum number of cycles that must elapse between the 142894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// predecessor and the successor, given that they have this edge 143894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// between them. 144894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getLatency() const { 145894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Latency; 146894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 147894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 148894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setLatency - Set the latency for this edge. 149894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setLatency(unsigned Lat) { 150894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Latency = Lat; 151894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 152894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 153894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //// getSUnit - Return the SUnit to which this edge points. 154894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *getSUnit() const { 155894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Dep.getPointer(); 156894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 157894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 158894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //// setSUnit - Assign the SUnit to which this edge points. 159894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setSUnit(SUnit *SU) { 160894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Dep.setPointer(SU); 161894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 162894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 163894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getKind - Return an enum value representing the kind of the dependence. 164894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Kind getKind() const { 165894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Dep.getInt(); 166894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 167894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 168894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isCtrl - Shorthand for getKind() != SDep::Data. 169894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isCtrl() const { 170894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getKind() != Data; 171894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 172894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 173894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isNormalMemory - Test if this is an Order dependence between two 174894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// memory accesses where both sides of the dependence access memory 175894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// in non-volatile and fully modeled ways. 176894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isNormalMemory() const { 177894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getKind() == Order && Contents.Order.isNormalMemory; 178894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 179894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 180894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isMustAlias - Test if this is an Order dependence that is marked 181894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// as "must alias", meaning that the SUnits at either end of the edge 182894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// have a memory dependence on a known memory location. 183894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isMustAlias() const { 184894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getKind() == Order && Contents.Order.isMustAlias; 185894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 186894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 187894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isArtificial - Test if this is an Order dependence that is marked 188894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// as "artificial", meaning it isn't necessary for correctness. 189894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isArtificial() const { 190894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getKind() == Order && Contents.Order.isArtificial; 191894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 192894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 193894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isAssignedRegDep - Test if this is a Data dependence that is 194894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// associated with a register. 195894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isAssignedRegDep() const { 196894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getKind() == Data && Contents.Reg != 0; 197894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 198894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 199894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getReg - Return the register associated with this edge. This is 200894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// only valid on Data, Anti, and Output edges. On Data edges, this 201894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// value may be zero, meaning there is no associated register. 202894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getReg() const { 203894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 204894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "getReg called on non-register dependence edge!"); 205894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Contents.Reg; 206894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 207894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 208894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setReg - Assign the associated register for this edge. This is 209894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// only valid on Data, Anti, and Output edges. On Anti and Output 210894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// edges, this value must not be zero. On Data edges, the value may 211894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// be zero, which would mean that no specific register is associated 212894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// with this edge. 213894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setReg(unsigned Reg) { 214894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 215894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "setReg called on non-register dependence edge!"); 216894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((getKind() != Anti || Reg != 0) && 217894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "SDep::Anti edge cannot use the zero register!"); 218894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert((getKind() != Output || Reg != 0) && 219894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman "SDep::Output edge cannot use the zero register!"); 220894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Contents.Reg = Reg; 221894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 222894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 223894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 22419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman template <> 22519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman struct isPodLike<SDep> { static const bool value = true; }; 22619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 227894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SUnit - Scheduling unit. This is a node in the scheduling DAG. 228894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class SUnit { 229894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 230894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *Node; // Representative node. 231894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *Instr; // Alternatively, a MachineInstr. 232894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 233894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *OrigNode; // If not this, the node from which 234894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // this node was cloned. 23519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 23619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Preds/Succs - The SUnits before/after us in the graph. 237894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDep, 4> Preds; // All sunit predecessors. 238894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SmallVector<SDep, 4> Succs; // All sunit successors. 239894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 240894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SmallVector<SDep, 4>::iterator pred_iterator; 241894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SmallVector<SDep, 4>::iterator succ_iterator; 242894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; 243894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; 244894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 245894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NodeNum; // Entry # of node in the node vector. 246894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NodeQueueId; // Queue id of node. 247894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumPreds; // # of SDep::Data preds. 248894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumSuccs; // # of SDep::Data sucss. 249894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumPredsLeft; // # of preds not scheduled. 250894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned NumSuccsLeft; // # of succs not scheduled. 25119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. 25219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman unsigned short Latency; // Node latency. 25319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isVRegCycle : 1; // May use and def the same vreg. 25419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isCall : 1; // Is a function call. 25519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isCallOp : 1; // Is a function call operand. 256894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isTwoAddress : 1; // Is a two-address instruction. 257894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isCommutable : 1; // Is a commutable instruction. 258894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool hasPhysRegDefs : 1; // Has physreg defs that are being used. 259894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not. 260894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isPending : 1; // True once pending. 261894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isAvailable : 1; // True once available. 262894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isScheduled : 1; // True once scheduled. 263894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isScheduleHigh : 1; // True if preferable to schedule high. 26419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isScheduleLow : 1; // True if preferable to schedule low. 265894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isCloned : 1; // True if this node has been cloned. 266894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Sched::Preference SchedulingPref; // Scheduling preference. 267894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 268894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 269894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isDepthCurrent : 1; // True if Depth is current. 270894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isHeightCurrent : 1; // True if Height is current. 271894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Depth; // Node depth. 272894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Height; // Node height. 273894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 274894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 275894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterClass *CopySrcRC; 27619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 277894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent 278894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// an SDNode and any nodes flagged to it. 279894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit(SDNode *node, unsigned nodenum) 280894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), 28119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 28219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), 28319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 28419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 285894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isPending(false), isAvailable(false), isScheduled(false), 28619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isScheduleHigh(false), isScheduleLow(false), isCloned(false), 287894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SchedulingPref(Sched::None), 288894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 289894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CopyDstRC(NULL), CopySrcRC(NULL) {} 290894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 291894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SUnit - Construct an SUnit for post-regalloc scheduling to represent 292894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// a MachineInstr. 293894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit(MachineInstr *instr, unsigned nodenum) 294894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), 29519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 29619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), 29719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 29819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 299894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isPending(false), isAvailable(false), isScheduled(false), 30019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isScheduleHigh(false), isScheduleLow(false), isCloned(false), 301894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SchedulingPref(Sched::None), 302894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 303894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CopyDstRC(NULL), CopySrcRC(NULL) {} 304894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 305894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SUnit - Construct a placeholder SUnit. 306894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit() 307894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), 30819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 30919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), 31019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 31119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 312894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isPending(false), isAvailable(false), isScheduled(false), 31319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman isScheduleHigh(false), isScheduleLow(false), isCloned(false), 314894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SchedulingPref(Sched::None), 315894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 316894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CopyDstRC(NULL), CopySrcRC(NULL) {} 317894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 318894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setNode - Assign the representative SDNode for this SUnit. 319894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This may be used during pre-regalloc scheduling. 320894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setNode(SDNode *N) { 321894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 322894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Node = N; 323894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 324894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 325894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getNode - Return the representative SDNode for this SUnit. 326894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This may be used during pre-regalloc scheduling. 327894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDNode *getNode() const { 328894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 329894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Node; 330894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 331894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 33219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// isInstr - Return true if this SUnit refers to a machine instruction as 33319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// opposed to an SDNode. 33419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool isInstr() const { return Instr; } 33519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 336894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setInstr - Assign the instruction for the SUnit. 337894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This may be used during post-regalloc scheduling. 338894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setInstr(MachineInstr *MI) { 339894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 340894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Instr = MI; 341894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 342894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 343894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getInstr - Return the representative MachineInstr for this SUnit. 344894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This may be used during post-regalloc scheduling. 345894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineInstr *getInstr() const { 346894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 347894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Instr; 348894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 349894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 350894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// addPred - This adds the specified edge as a pred of the current node if 351894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// not already. It also adds the current node as a successor of the 352894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// specified node. 35319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool addPred(const SDep &D); 354894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 355894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// removePred - This removes the specified edge as a pred of the current 356894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// node if it exists. It also removes the current node as a successor of 357894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// the specified node. 358894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void removePred(const SDep &D); 359894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 360894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getDepth - Return the depth of this node, which is the length of the 36119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// maximum path up to any node which has no predecessors. 362894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getDepth() const { 36319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isDepthCurrent) 364894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_cast<SUnit *>(this)->ComputeDepth(); 365894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Depth; 366894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 367894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 368894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getHeight - Return the height of this node, which is the length of the 36919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// maximum path down to any node which has no successors. 370894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getHeight() const { 37119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (!isHeightCurrent) 372894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_cast<SUnit *>(this)->ComputeHeight(); 373894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Height; 374894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 375894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 376894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setDepthToAtLeast - If NewDepth is greater than this node's 377894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// depth value, set it to be the new depth value. This also 378894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// recursively marks successor nodes dirty. 379894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setDepthToAtLeast(unsigned NewDepth); 380894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 381894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setDepthToAtLeast - If NewDepth is greater than this node's 382894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// depth value, set it to be the new height value. This also 383894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// recursively marks predecessor nodes dirty. 384894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setHeightToAtLeast(unsigned NewHeight); 385894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 386894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setDepthDirty - Set a flag in this node to indicate that its 387894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// stored Depth value will require recomputation the next time 388894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getDepth() is called. 389894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setDepthDirty(); 390894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 391894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// setHeightDirty - Set a flag in this node to indicate that its 392894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// stored Height value will require recomputation the next time 393894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getHeight() is called. 394894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setHeightDirty(); 395894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 396894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isPred - Test if node N is a predecessor of this node. 397894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isPred(SUnit *N) { 398894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 399894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Preds[i].getSUnit() == N) 400894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 401894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 402894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 40319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 404894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isSucc - Test if node N is a successor of this node. 405894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isSucc(SUnit *N) { 406894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) 407894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman if (Succs[i].getSUnit() == N) 408894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return true; 409894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return false; 410894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 411894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 412894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void dump(const ScheduleDAG *G) const; 413894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void dumpAll(const ScheduleDAG *G) const; 414894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void print(raw_ostream &O, const ScheduleDAG *G) const; 415894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 416894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman private: 417894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void ComputeDepth(); 418894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void ComputeHeight(); 419894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 420894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 421894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman //===--------------------------------------------------------------------===// 422894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SchedulingPriorityQueue - This interface is used to plug different 423894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// priorities computation algorithms into the list scheduler. It implements 42419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// the interface of a standard priority queue, where nodes are inserted in 425894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// arbitrary order and returned in priority order. The computation of the 426894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// priority and the representation of the queue are totally up to the 427894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// implementation to decide. 42819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// 429894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class SchedulingPriorityQueue { 430894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned CurCycle; 43119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool HasReadyFilter; 432894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 43319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman SchedulingPriorityQueue(bool rf = false): 43419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman CurCycle(0), HasReadyFilter(rf) {} 435894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual ~SchedulingPriorityQueue() {} 43619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 43719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool isBottomUp() const = 0; 43819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 439894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 440894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void addNode(const SUnit *SU) = 0; 441894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void updateNode(const SUnit *SU) = 0; 442894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void releaseState() = 0; 443894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 444894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool empty() const = 0; 44519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool hasReadyFilter() const { return HasReadyFilter; } 44719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 44819bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool tracksRegPressure() const { return false; } 44919bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 45019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual bool isReady(SUnit *) const { 45119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman assert(!HasReadyFilter && "The ready filter must override isReady()"); 45219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return true; 45319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 454894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void push(SUnit *U) = 0; 45519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 456894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void push_all(const std::vector<SUnit *> &Nodes) { 457894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 458894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman E = Nodes.end(); I != E; ++I) 459894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman push(*I); 460894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 461894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 462894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual SUnit *pop() = 0; 463894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 464894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void remove(SUnit *SU) = 0; 465894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 46619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman virtual void dump(ScheduleDAG *) const {} 46719bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 468894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ScheduledNode - As each node is scheduled, this method is invoked. This 469894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// allows the priority function to adjust the priority of related 470894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// unscheduled nodes, for example. 471894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 472894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void ScheduledNode(SUnit *) {} 473894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 474894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void UnscheduledNode(SUnit *) {} 475894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 476894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void setCurCycle(unsigned Cycle) { 477894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman CurCycle = Cycle; 478894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 479894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 480894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getCurCycle() const { 481894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return CurCycle; 48219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 483894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 484894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 485894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class ScheduleDAG { 486894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 487894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock *BB; // The block in which to insert instructions 488894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineBasicBlock::iterator InsertPos;// The position to insert instructions 489894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetMachine &TM; // Target processor 490894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetInstrInfo *TII; // Target instruction information 491894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const TargetRegisterInfo *TRI; // Target processor register info 492894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineFunction &MF; // Machine function 493894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman MachineRegisterInfo &MRI; // Virtual/real register map 494894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<SUnit*> Sequence; // The schedule. Null SUnit*'s 495894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman // represent noop instructions. 496894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<SUnit> SUnits; // The scheduling units. 497894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit EntrySU; // Special node for the region entry. 498894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit ExitSU; // Special node for the region exit. 499894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 50019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#ifdef NDEBUG 50119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman static const bool StressSched = false; 50219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#else 50319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman bool StressSched; 50419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman#endif 50519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 506894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit ScheduleDAG(MachineFunction &mf); 507894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 508894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual ~ScheduleDAG(); 509894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 51019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// getInstrDesc - Return the MCInstrDesc of this SUnit. 51119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// Return NULL for SDNodes without a machine opcode. 51219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 51319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman if (SU->isInstr()) return &SU->getInstr()->getDesc(); 51419bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman return getNodeDesc(SU->getNode()); 51519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman } 51619bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 517894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 518894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// using 'dot'. 519894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 520894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void viewGraph(); 52119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 522894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// EmitSchedule - Insert MachineInstrs into the MachineBasicBlock 523894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// according to the order specified in Sequence. 524894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 525894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual MachineBasicBlock *EmitSchedule() = 0; 526894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 527894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void dumpSchedule() const; 528894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 529894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void dumpNode(const SUnit *SU) const = 0; 530894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 531894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// getGraphNodeLabel - Return a label for an SUnit node in a visualization 532894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// of the ScheduleDAG. 533894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 534894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 535894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// addCustomGraphFeatures - Add custom features for a visualization of 536894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// the ScheduleDAG. 537894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 538894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 539894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#ifndef NDEBUG 540894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// VerifySchedule - Verify that all SUnits were scheduled and that 541894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// their state is consistent. 542894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void VerifySchedule(bool isBottomUp); 543894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 544894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 545894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman protected: 546894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Run - perform scheduling. 547894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 548894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void Run(MachineBasicBlock *bb, MachineBasicBlock::iterator insertPos); 549894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 550894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// BuildSchedGraph - Build SUnits and set up their Preds and Succs 551894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// to form the scheduling dependency graph. 552894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 553894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void BuildSchedGraph(AliasAnalysis *AA) = 0; 554894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 555894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ComputeLatency - Compute node latency. 556894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 557894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void ComputeLatency(SUnit *SU) = 0; 558894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 559894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ComputeOperandLatency - Override dependence edge latency using 560894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// operand use/def information 561894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 562894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void ComputeOperandLatency(SUnit *, SUnit *, 563894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SDep&) const { } 564894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 565894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Schedule - Order nodes according to selected style, filling 566894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// in the Sequence member. 567894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 568894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual void Schedule() = 0; 569894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 570894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ForceUnitLatencies - Return true if all scheduling edges should be given 571894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// a latency value of one. The default is to return false; schedulers may 572894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// override this as needed. 573894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman virtual bool ForceUnitLatencies() const { return false; } 574894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 575894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// EmitNoop - Emit a noop instruction. 576894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 577894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void EmitNoop(); 578894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 579894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void EmitPhysRegCopy(SUnit *SU, DenseMap<SUnit*, unsigned> &VRBaseMap); 58019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman 58119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman private: 58219bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman // Return the MCInstrDesc of this SDNode or NULL. 58319bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 584894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 585894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 586894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class SUnitIterator : public std::iterator<std::forward_iterator_tag, 587894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit, ptrdiff_t> { 588894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnit *Node; 589894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned Operand; 590894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 591894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 592894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 593894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator==(const SUnitIterator& x) const { 594894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Operand == x.Operand; 595894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 596894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 597894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 598894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SUnitIterator &operator=(const SUnitIterator &I) { 599894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman assert(I.Node==Node && "Cannot assign iterators to two different nodes!"); 600894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman Operand = I.Operand; 601894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 602894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 603894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 604894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman pointer operator*() const { 605894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Node->Preds[Operand].getSUnit(); 606894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 607894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman pointer operator->() const { return operator*(); } 608894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 609894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnitIterator& operator++() { // Preincrement 610894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman ++Operand; 611894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return *this; 612894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 613894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnitIterator operator++(int) { // Postincrement 614894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman SUnitIterator tmp = *this; ++*this; return tmp; 615894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 616894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 617894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 618894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static SUnitIterator end (SUnit *N) { 619894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return SUnitIterator(N, (unsigned)N->Preds.size()); 620894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 621894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 622894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman unsigned getOperand() const { return Operand; } 623894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SUnit *getNode() const { return Node; } 624894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// isCtrlDep - Test if this is not an SDep::Data dependence. 625894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isCtrlDep() const { 626894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getSDep().isCtrl(); 627894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 628894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool isArtificialDep() const { 629894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return getSDep().isArtificial(); 630894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 631894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const SDep &getSDep() const { 632894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return Node->Preds[Operand]; 633894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 634894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 635894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 636894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template <> struct GraphTraits<SUnit*> { 637894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SUnit NodeType; 638894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef SUnitIterator ChildIteratorType; 639894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline NodeType *getEntryNode(SUnit *N) { return N; } 640894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_begin(NodeType *N) { 641894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return SUnitIterator::begin(N); 642894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 643894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static inline ChildIteratorType child_end(NodeType *N) { 644894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return SUnitIterator::end(N); 645894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 646894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 647894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 648894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 649894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<SUnit>::iterator nodes_iterator; 650894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_begin(ScheduleDAG *G) { 651894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return G->SUnits.begin(); 652894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 653894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman static nodes_iterator nodes_end(ScheduleDAG *G) { 654894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman return G->SUnits.end(); 655894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman } 656894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 657894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 658894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ScheduleDAGTopologicalSort is a class that computes a topological 659894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ordering for SUnits and provides methods for dynamically updating 660894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// the ordering as new edges are added. 661894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 662894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// This allows a very fast implementation of IsReachable, for example. 663894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// 664894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman class ScheduleDAGTopologicalSort { 665894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// SUnits - A reference to the ScheduleDAG's SUnits. 666894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<SUnit> &SUnits; 667894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 668894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Index2Node - Maps topological index to the node number. 669894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<int> Index2Node; 670894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Node2Index - Maps the node number to its topological index. 671894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman std::vector<int> Node2Index; 672894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Visited - a set of nodes visited during a DFS traversal. 673894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman BitVector Visited; 674894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 67519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// DFS - make a DFS traversal and mark all nodes affected by the 676894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// edge insertion. These nodes will later get new topological indexes 677894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// by means of the Shift method. 678894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 679894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 680894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Shift - reassign topological indexes for the nodes in the DAG 681894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// to preserve the topological ordering. 682894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void Shift(BitVector& Visited, int LowerBound, int UpperBound); 683894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 684894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// Allocate - assign the topological index to the node n. 685894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void Allocate(int n, int index); 686894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 687894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman public: 688894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits); 689894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 69019bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// InitDAGTopologicalSorting - create the initial topological 691894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// ordering from the DAG to be scheduled. 692894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void InitDAGTopologicalSorting(); 693894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 694894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// IsReachable - Checks if SU is reachable from TargetSU. 695894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 696894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 697894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU 698894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// will create a cycle. 699894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman bool WillCreateCycle(SUnit *SU, SUnit *TargetSU); 700894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 70119bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// AddPred - Updates the topological ordering to accommodate an edge 702894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// to be added from SUnit X to SUnit Y. 703894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void AddPred(SUnit *Y, SUnit *X); 704894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 70519bac1e08be200c31efd26f0f5fd144c9b3eefd3John Bauman /// RemovePred - Updates the topological ordering to accommodate an 706894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// an edge to be removed from the specified node N from the predecessors 707894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman /// of the current node M. 708894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman void RemovePred(SUnit *M, SUnit *N); 709894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 710894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<int>::iterator iterator; 711894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<int>::const_iterator const_iterator; 712894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator begin() { return Index2Node.begin(); } 713894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator begin() const { return Index2Node.begin(); } 714894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman iterator end() { return Index2Node.end(); } 715894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_iterator end() const { return Index2Node.end(); } 716894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 717894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<int>::reverse_iterator reverse_iterator; 718894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 719894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman reverse_iterator rbegin() { return Index2Node.rbegin(); } 720894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 721894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman reverse_iterator rend() { return Index2Node.rend(); } 722894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman const_reverse_iterator rend() const { return Index2Node.rend(); } 723894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman }; 724894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman} 725894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman 726894018228b0e0bdbd7aa7e8f47d4a9458789ca82John Bauman#endif 727