1a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng//===------- llvm/CodeGen/ScheduleDAG.h - Common Base Class------*- C++ -*-===// 2a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng// 3a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng// The LLVM Compiler Infrastructure 4a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng// 57ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// This file is distributed under the University of Illinois Open Source 67ed47a13356daed2a34cd2209a31f92552e3bdd8Chris Lattner// License. See LICENSE.TXT for details. 7a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng// 8a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng//===----------------------------------------------------------------------===// 9a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng// 10a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng// This file implements the ScheduleDAG class, which is used as the common 11e75537a243858d8293832109e61bafc8484bb52aAndrew Trick// base class for instruction schedulers. This encapsulates the scheduling DAG, 12e75537a243858d8293832109e61bafc8484bb52aAndrew Trick// which is shared between SelectionDAG and MachineInstr scheduling. 13a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng// 14a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng//===----------------------------------------------------------------------===// 15a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 16a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng#ifndef LLVM_CODEGEN_SCHEDULEDAG_H 17a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng#define LLVM_CODEGEN_SCHEDULEDAG_H 18a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 199e23336d0c99fc5cae04037ead6d8f2b677e8764Evan Cheng#include "llvm/CodeGen/MachineBasicBlock.h" 20e5dafc395656645c3a5d90e7c1b55477800f2ab1Evan Cheng#include "llvm/Target/TargetLowering.h" 212ba528b3a75955c960347e5b5b28ae74d5a81909Chris Lattner#include "llvm/ADT/DenseMap.h" 2221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#include "llvm/ADT/BitVector.h" 233e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman#include "llvm/ADT/GraphTraits.h" 24343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman#include "llvm/ADT/SmallVector.h" 2554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman#include "llvm/ADT/PointerIntPair.h" 26e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 27a9c2091cd38e401c846391c9951ff416e709b65eEvan Chengnamespace llvm { 2898976e4dcd18adbbe676048c0069e67346eb4adeDan Gohman class AliasAnalysis; 2948fe63526e35ddaee7e98879596a569911f41319Sebastian Redl class SUnit; 30a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class MachineConstantPool; 316b2cf285bd43fdc98ca68df477570ef6938d4fb2Evan Cheng class MachineFunction; 3284bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner class MachineRegisterInfo; 33a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class MachineInstr; 346f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman class TargetRegisterInfo; 353cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman class ScheduleDAG; 36343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman class SDNode; 37a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class TargetInstrInfo; 38e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng class MCInstrDesc; 39a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class TargetMachine; 408ed3ffee53105275ca03f06ba0195bc6008477faEvan Cheng class TargetRegisterClass; 41343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman template<class Graph> class GraphWriter; 42713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng 4354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// SDep - Scheduling dependency. This represents one direction of an 4454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// edge in the scheduling DAG. 4554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman class SDep { 4654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman public: 4754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Kind - These are the different kinds of scheduling dependencies. 4854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman enum Kind { 4954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Data, ///< Regular data dependence (aka true-dependence). 5054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Anti, ///< A register anti-dependedence (aka WAR). 5154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Output, ///< A register output-dependence (aka WAW). 5254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Order ///< Any other ordering dependency. 5354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman }; 5454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 5554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman private: 5654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Dep - A pointer to the depending/depended-on SUnit, and an enum 5754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// indicating the kind of the dependency. 5854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman PointerIntPair<SUnit *, 2, Kind> Dep; 5954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 6054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Contents - A union discriminated by the dependence kind. 6154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman union { 6254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Reg - For Data, Anti, and Output dependencies, the associated 6354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// register. For Data dependencies that don't currently have a register 6454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// assigned, this is set to zero. 6554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned Reg; 6654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 6754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Order - Additional information about Order dependencies. 6854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman struct { 6954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isNormalMemory - True if both sides of the dependence 7054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// access memory in non-volatile and fully modeled ways. 7154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isNormalMemory : 1; 7254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 7354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isMustAlias - True if both sides of the dependence are known to 7454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// access the same memory. 7554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isMustAlias : 1; 7654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 7754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isArtificial - True if this is an artificial dependency, meaning 7854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// it is not necessary for program correctness, and may be safely 7954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// deleted if necessary. 8054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isArtificial : 1; 8154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } Order; 8254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } Contents; 8354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 8454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Latency - The time associated with this edge. Often this is just 8554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// the value of the Latency field of the predecessor, however advanced 8654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// models may provide additional information about specific edges. 8754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned Latency; 88ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// Record MinLatency seperately from "expected" Latency. 89ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick unsigned MinLatency; 9054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 9154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman public: 9254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// SDep - Construct a null SDep. This is only for use by container 9354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// classes which require default constructors. SUnits may not 9454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// have null SDep edges. 9554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep() : Dep(0, Data) {} 9654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 9754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// SDep - Construct an SDep with the specified values. 9854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep(SUnit *S, Kind kind, unsigned latency = 1, unsigned Reg = 0, 9954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isNormalMemory = false, bool isMustAlias = false, 10054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isArtificial = false) 101ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick : Dep(S, kind), Contents(), Latency(latency), MinLatency(latency) { 10254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (kind) { 10354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Anti: 10454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Output: 10554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(Reg != 0 && 10654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Anti and SDep::Output must use a non-zero Reg!"); 10754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman // fall through 10854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Data: 10954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(!isMustAlias && "isMustAlias only applies with SDep::Order!"); 11054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(!isArtificial && "isArtificial only applies with SDep::Order!"); 11154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Reg = Reg; 11254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman break; 11354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Order: 11454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(Reg == 0 && "Reg given for non-register dependence!"); 11554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Order.isNormalMemory = isNormalMemory; 11654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Order.isMustAlias = isMustAlias; 11754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Order.isArtificial = isArtificial; 11854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman break; 11954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 12054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 12154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 1229df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick /// Return true if the specified SDep is equivalent except for latency. 1239df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick bool overlaps(const SDep &Other) const { 1249df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (Dep != Other.Dep) return false; 12554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (Dep.getInt()) { 12654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Data: 12754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Anti: 12854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Output: 12954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Contents.Reg == Other.Contents.Reg; 13054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Order: 13154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Contents.Order.isNormalMemory == 13254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Other.Contents.Order.isNormalMemory && 13354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Order.isMustAlias == Other.Contents.Order.isMustAlias && 13454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Order.isArtificial == Other.Contents.Order.isArtificial; 13554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 136aae875c27ce59e1c98dbc4a2358a006f2edef433Craig Topper llvm_unreachable("Invalid dependency kind!"); 13754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 13854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 1399df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick bool operator==(const SDep &Other) const { 140ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick return overlaps(Other) 141ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick && Latency == Other.Latency && MinLatency == Other.MinLatency; 1429df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 1439df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick 14454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool operator!=(const SDep &Other) const { 14554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return !operator==(Other); 14654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 14754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 14854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getLatency - Return the latency value for this edge, which roughly 14954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// means the minimum number of cycles that must elapse between the 15054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// predecessor and the successor, given that they have this edge 15154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// between them. 15254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned getLatency() const { 15354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Latency; 15454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 15554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 156710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin /// setLatency - Set the latency for this edge. 157710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin void setLatency(unsigned Lat) { 158710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin Latency = Lat; 159710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin } 160710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 161ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// getMinLatency - Return the minimum latency for this edge. Minimum 162ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// latency is used for scheduling groups, while normal (expected) latency 163ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// is for instruction cost and critical path. 164ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick unsigned getMinLatency() const { 165ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick return MinLatency; 166ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick } 167ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick 168ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// setMinLatency - Set the minimum latency for this edge. 169ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick void setMinLatency(unsigned Lat) { 170ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick MinLatency = Lat; 171ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick } 172ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick 17354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman //// getSUnit - Return the SUnit to which this edge points. 17454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *getSUnit() const { 17554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Dep.getPointer(); 17654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 17754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 17854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman //// setSUnit - Assign the SUnit to which this edge points. 17954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void setSUnit(SUnit *SU) { 18054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Dep.setPointer(SU); 18154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 18254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 18354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getKind - Return an enum value representing the kind of the dependence. 18454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Kind getKind() const { 18554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Dep.getInt(); 18654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 18754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 18854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isCtrl - Shorthand for getKind() != SDep::Data. 18954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isCtrl() const { 19054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return getKind() != Data; 19154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 19254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 193fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// isNormalMemory - Test if this is an Order dependence between two 194fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// memory accesses where both sides of the dependence access memory 195fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// in non-volatile and fully modeled ways. 196fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman bool isNormalMemory() const { 197fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman return getKind() == Order && Contents.Order.isNormalMemory; 198fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman } 199fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman 20054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isMustAlias - Test if this is an Order dependence that is marked 20154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// as "must alias", meaning that the SUnits at either end of the edge 20254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// have a memory dependence on a known memory location. 20354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isMustAlias() const { 20454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return getKind() == Order && Contents.Order.isMustAlias; 20554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 20654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 207e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman /// isArtificial - Test if this is an Order dependence that is marked 208e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman /// as "artificial", meaning it isn't necessary for correctness. 209e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman bool isArtificial() const { 210e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman return getKind() == Order && Contents.Order.isArtificial; 211e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman } 212e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman 21354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isAssignedRegDep - Test if this is a Data dependence that is 21454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// associated with a register. 21554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isAssignedRegDep() const { 21654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return getKind() == Data && Contents.Reg != 0; 21754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 21854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 21954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getReg - Return the register associated with this edge. This is 22054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// only valid on Data, Anti, and Output edges. On Data edges, this 22154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// value may be zero, meaning there is no associated register. 22254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned getReg() const { 22354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 22454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "getReg called on non-register dependence edge!"); 22554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Contents.Reg; 22654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 22754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 22854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// setReg - Assign the associated register for this edge. This is 22954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// only valid on Data, Anti, and Output edges. On Anti and Output 23054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// edges, this value must not be zero. On Data edges, the value may 23154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// be zero, which would mean that no specific register is associated 23254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// with this edge. 23354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void setReg(unsigned Reg) { 23454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 23554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "setReg called on non-register dependence edge!"); 23654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() != Anti || Reg != 0) && 23754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Anti edge cannot use the zero register!"); 23854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() != Output || Reg != 0) && 23954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Output edge cannot use the zero register!"); 24054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Reg = Reg; 24154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 242713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng }; 243713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng 244dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer template <> 245dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer struct isPodLike<SDep> { static const bool value = true; }; 246dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer 247343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// SUnit - Scheduling unit. This is a node in the scheduling DAG. 248aff9c270de8de7d1a0bc138d391bc67136bad58eCedric Venet class SUnit { 249550f5afb68ce8f034991863cac65bef22a6554daDan Gohman private: 250e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SDNode *Node; // Representative node. 251f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman MachineInstr *Instr; // Alternatively, a MachineInstr. 252550f5afb68ce8f034991863cac65bef22a6554daDan Gohman public: 2534c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman SUnit *OrigNode; // If not this, the node from which 2544c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman // this node was cloned. 255b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick // (SD scheduling only) 2566e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 2576e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick // Preds/Succs - The SUnits before/after us in the graph. 258713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SmallVector<SDep, 4> Preds; // All sunit predecessors. 259713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SmallVector<SDep, 4> Succs; // All sunit successors. 260713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng 261713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::iterator pred_iterator; 262713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::iterator succ_iterator; 263713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; 264713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; 2651cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 266a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng unsigned NodeNum; // Entry # of node in the node vector. 267a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein unsigned NodeQueueId; // Queue id of node. 268c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumPreds; // # of SDep::Data preds. 269c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumSuccs; // # of SDep::Data sucss. 270c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumPredsLeft; // # of preds not scheduled. 271c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumSuccsLeft; // # of succs not scheduled. 27292e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. 273dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer unsigned short Latency; // Node latency. 27454699765064842fd08d1466adc93453660bc2a85Andrew Trick bool isVRegCycle : 1; // May use and def the same vreg. 2758239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng bool isCall : 1; // Is a function call. 276554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng bool isCallOp : 1; // Is a function call operand. 277e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isTwoAddress : 1; // Is a two-address instruction. 27813d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng bool isCommutable : 1; // Is a commutable instruction. 279f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng bool hasPhysRegDefs : 1; // Has physreg defs that are being used. 2803974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not. 281e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isPending : 1; // True once pending. 282e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isAvailable : 1; // True once available. 283e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isScheduled : 1; // True once scheduled. 2848749b61178228ba1fb2668034d79da1b247173d7Dan Gohman bool isScheduleHigh : 1; // True if preferable to schedule high. 28512f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick bool isScheduleLow : 1; // True if preferable to schedule low. 286e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng bool isCloned : 1; // True if this node has been cloned. 2871cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng Sched::Preference SchedulingPref; // Scheduling preference. 288309d20c89c5fde5a6ebe3b40a3fd0fbc3e5ffe40Jim Grosbach 2893f23744df4809eba94284e601e81489212c974d4Dan Gohman private: 2903f23744df4809eba94284e601e81489212c974d4Dan Gohman bool isDepthCurrent : 1; // True if Depth is current. 2913f23744df4809eba94284e601e81489212c974d4Dan Gohman bool isHeightCurrent : 1; // True if Height is current. 2923f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned Depth; // Node depth. 2933f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned Height; // Node height. 2943f23744df4809eba94284e601e81489212c974d4Dan Gohman public: 295b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick unsigned TopReadyCycle; // Cycle relative to start when node is ready. 296b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick unsigned BotReadyCycle; // Cycle relative to end when node is ready. 297b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick 2988ed3ffee53105275ca03f06ba0195bc6008477faEvan Cheng const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 2998ed3ffee53105275ca03f06ba0195bc6008477faEvan Cheng const TargetRegisterClass *CopySrcRC; 3006e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 301f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent 302f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// an SDNode and any nodes flagged to it. 303e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnit(SDNode *node, unsigned nodenum) 304309d20c89c5fde5a6ebe3b40a3fd0fbc3e5ffe40Jim Grosbach : Node(node), Instr(0), OrigNode(0), NodeNum(nodenum), 305dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 30692e946630d5f9bb092853b93501387dd216899b9Andrew Trick NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), 307554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 30854699765064842fd08d1466adc93453660bc2a85Andrew Trick isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 309f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman isPending(false), isAvailable(false), isScheduled(false), 31012f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick isScheduleHigh(false), isScheduleLow(false), isCloned(false), 3111cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SchedulingPref(Sched::None), 312e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 313b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 314f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 315f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// SUnit - Construct an SUnit for post-regalloc scheduling to represent 316f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// a MachineInstr. 317f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman SUnit(MachineInstr *instr, unsigned nodenum) 318309d20c89c5fde5a6ebe3b40a3fd0fbc3e5ffe40Jim Grosbach : Node(0), Instr(instr), OrigNode(0), NodeNum(nodenum), 319dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 32092e946630d5f9bb092853b93501387dd216899b9Andrew Trick NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), 321554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 32254699765064842fd08d1466adc93453660bc2a85Andrew Trick isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 323e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng isPending(false), isAvailable(false), isScheduled(false), 32412f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick isScheduleHigh(false), isScheduleLow(false), isCloned(false), 3251cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SchedulingPref(Sched::None), 326e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 327b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 328a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 3299e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// SUnit - Construct a placeholder SUnit. 3309e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit() 331309d20c89c5fde5a6ebe3b40a3fd0fbc3e5ffe40Jim Grosbach : Node(0), Instr(0), OrigNode(0), NodeNum(~0u), 332dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 33392e946630d5f9bb092853b93501387dd216899b9Andrew Trick NumSuccsLeft(0), NumRegDefsLeft(0), Latency(0), 334554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng isVRegCycle(false), isCall(false), isCallOp(false), isTwoAddress(false), 33554699765064842fd08d1466adc93453660bc2a85Andrew Trick isCommutable(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 3369e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman isPending(false), isAvailable(false), isScheduled(false), 33712f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick isScheduleHigh(false), isScheduleLow(false), isCloned(false), 3381cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng SchedulingPref(Sched::None), 3399e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 340b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 3419e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 342550f5afb68ce8f034991863cac65bef22a6554daDan Gohman /// setNode - Assign the representative SDNode for this SUnit. 343f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during pre-regalloc scheduling. 344f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman void setNode(SDNode *N) { 345f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 346f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman Node = N; 347f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 348550f5afb68ce8f034991863cac65bef22a6554daDan Gohman 349550f5afb68ce8f034991863cac65bef22a6554daDan Gohman /// getNode - Return the representative SDNode for this SUnit. 350f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during pre-regalloc scheduling. 351f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman SDNode *getNode() const { 352f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 353f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman return Node; 354f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 355f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 3562da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// isInstr - Return true if this SUnit refers to a machine instruction as 3572da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// opposed to an SDNode. 358a75ce9f5d2236d93c117e861e60e6f3f748c9555Andrew Trick bool isInstr() const { return Instr; } 3592da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 360f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// setInstr - Assign the instruction for the SUnit. 361f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during post-regalloc scheduling. 362f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman void setInstr(MachineInstr *MI) { 363f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 364f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman Instr = MI; 365f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 366f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 367f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// getInstr - Return the representative MachineInstr for this SUnit. 368f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during post-regalloc scheduling. 369f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman MachineInstr *getInstr() const { 370f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 371f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman return Instr; 372f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 373550f5afb68ce8f034991863cac65bef22a6554daDan Gohman 37454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// addPred - This adds the specified edge as a pred of the current node if 375cddd428459a66830b0d072823f94224ace58e625Dan Gohman /// not already. It also adds the current node as a successor of the 376ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman /// specified node. 37792e946630d5f9bb092853b93501387dd216899b9Andrew Trick bool addPred(const SDep &D); 378228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner 37954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// removePred - This removes the specified edge as a pred of the current 38054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// node if it exists. It also removes the current node as a successor of 381ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman /// the specified node. 382c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman void removePred(const SDep &D); 383a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 38489bf4f2f5e6f54fe6382f07c515e36adc9e0c9c2Dan Gohman /// getDepth - Return the depth of this node, which is the length of the 385d756eceb83fc9a7536f76adfe24cdb19d4c2f253Eric Christopher /// maximum path up to any node which has no predecessors. 386557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin unsigned getDepth() const { 3876e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick if (!isDepthCurrent) 388557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin const_cast<SUnit *>(this)->ComputeDepth(); 3893f23744df4809eba94284e601e81489212c974d4Dan Gohman return Depth; 3903f23744df4809eba94284e601e81489212c974d4Dan Gohman } 3913f23744df4809eba94284e601e81489212c974d4Dan Gohman 3923f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getHeight - Return the height of this node, which is the length of the 393d756eceb83fc9a7536f76adfe24cdb19d4c2f253Eric Christopher /// maximum path down to any node which has no successors. 394557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin unsigned getHeight() const { 3956e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick if (!isHeightCurrent) 396557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin const_cast<SUnit *>(this)->ComputeHeight(); 3973f23744df4809eba94284e601e81489212c974d4Dan Gohman return Height; 3983f23744df4809eba94284e601e81489212c974d4Dan Gohman } 3993f23744df4809eba94284e601e81489212c974d4Dan Gohman 4004de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// setDepthToAtLeast - If NewDepth is greater than this node's 4014de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// depth value, set it to be the new depth value. This also 402557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin /// recursively marks successor nodes dirty. 403557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void setDepthToAtLeast(unsigned NewDepth); 4043f23744df4809eba94284e601e81489212c974d4Dan Gohman 4054de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// setDepthToAtLeast - If NewDepth is greater than this node's 4064de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// depth value, set it to be the new height value. This also 407557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin /// recursively marks predecessor nodes dirty. 408557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void setHeightToAtLeast(unsigned NewHeight); 4093f23744df4809eba94284e601e81489212c974d4Dan Gohman 4103f23744df4809eba94284e601e81489212c974d4Dan Gohman /// setDepthDirty - Set a flag in this node to indicate that its 4113f23744df4809eba94284e601e81489212c974d4Dan Gohman /// stored Depth value will require recomputation the next time 4123f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getDepth() is called. 4133f23744df4809eba94284e601e81489212c974d4Dan Gohman void setDepthDirty(); 4143f23744df4809eba94284e601e81489212c974d4Dan Gohman 4153f23744df4809eba94284e601e81489212c974d4Dan Gohman /// setHeightDirty - Set a flag in this node to indicate that its 4163f23744df4809eba94284e601e81489212c974d4Dan Gohman /// stored Height value will require recomputation the next time 4173f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getHeight() is called. 4183f23744df4809eba94284e601e81489212c974d4Dan Gohman void setHeightDirty(); 4193f23744df4809eba94284e601e81489212c974d4Dan Gohman 4203f23744df4809eba94284e601e81489212c974d4Dan Gohman /// isPred - Test if node N is a predecessor of this node. 421a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng bool isPred(SUnit *N) { 42234cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 42354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (Preds[i].getSUnit() == N) 424a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return true; 425a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 426a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 4276e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 4283f23744df4809eba94284e601e81489212c974d4Dan Gohman /// isSucc - Test if node N is a successor of this node. 429a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng bool isSucc(SUnit *N) { 43034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) 43154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (Succs[i].getSUnit() == N) 432a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return true; 433a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 434228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner } 4351cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 43617d35e57a585e869dc3084666abd17f173723735Andrew Trick bool isTopReady() const { 43717d35e57a585e869dc3084666abd17f173723735Andrew Trick return NumPredsLeft == 0; 43817d35e57a585e869dc3084666abd17f173723735Andrew Trick } 43917d35e57a585e869dc3084666abd17f173723735Andrew Trick bool isBottomReady() const { 44017d35e57a585e869dc3084666abd17f173723735Andrew Trick return NumSuccsLeft == 0; 44117d35e57a585e869dc3084666abd17f173723735Andrew Trick } 44217d35e57a585e869dc3084666abd17f173723735Andrew Trick 4433cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman void dump(const ScheduleDAG *G) const; 4443cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman void dumpAll(const ScheduleDAG *G) const; 445252ae9e8ae4efaf1f67a608ad2563323308bd803Dan Gohman void print(raw_ostream &O, const ScheduleDAG *G) const; 4463f23744df4809eba94284e601e81489212c974d4Dan Gohman 4473f23744df4809eba94284e601e81489212c974d4Dan Gohman private: 448557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void ComputeDepth(); 449557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void ComputeHeight(); 450e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 451e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 452e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng //===--------------------------------------------------------------------===// 453e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// SchedulingPriorityQueue - This interface is used to plug different 454e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// priorities computation algorithms into the list scheduler. It implements 4556e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// the interface of a standard priority queue, where nodes are inserted in 456e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// arbitrary order and returned in priority order. The computation of the 457e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// priority and the representation of the queue are totally up to the 458e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// implementation to decide. 4596e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// 460e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng class SchedulingPriorityQueue { 4612d24e2a396a1d211baaeedf32148a3b657240170David Blaikie virtual void anchor(); 46215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned CurCycle; 4632da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick bool HasReadyFilter; 464e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng public: 4652da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick SchedulingPriorityQueue(bool rf = false): 4662da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick CurCycle(0), HasReadyFilter(rf) {} 467e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual ~SchedulingPriorityQueue() {} 4686e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 4692da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick virtual bool isBottomUp() const = 0; 4702da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 47194d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 472a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void addNode(const SUnit *SU) = 0; 473a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void updateNode(const SUnit *SU) = 0; 474e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual void releaseState() = 0; 475a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 476e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual bool empty() const = 0; 4772da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 4782da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick bool hasReadyFilter() const { return HasReadyFilter; } 4792da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 48092e946630d5f9bb092853b93501387dd216899b9Andrew Trick virtual bool tracksRegPressure() const { return false; } 48192e946630d5f9bb092853b93501387dd216899b9Andrew Trick 4827853ae1d97acb65bd4dfd9a15478c14f475dbd41Eric Christopher virtual bool isReady(SUnit *) const { 4832da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick assert(!HasReadyFilter && "The ready filter must override isReady()"); 4842da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick return true; 4852da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 486e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual void push(SUnit *U) = 0; 4876e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 488a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman void push_all(const std::vector<SUnit *> &Nodes) { 489a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 490a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman E = Nodes.end(); I != E; ++I) 491a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman push(*I); 492a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman } 493a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman 494e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual SUnit *pop() = 0; 495e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 496a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void remove(SUnit *SU) = 0; 497a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 4987853ae1d97acb65bd4dfd9a15478c14f475dbd41Eric Christopher virtual void dump(ScheduleDAG *) const {} 4992da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 500953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// scheduledNode - As each node is scheduled, this method is invoked. This 501a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// allows the priority function to adjust the priority of related 502a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// unscheduled nodes, for example. 503a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// 504953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void scheduledNode(SUnit *) {} 505a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 506953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void unscheduledNode(SUnit *) {} 50715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 50815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng void setCurCycle(unsigned Cycle) { 50915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng CurCycle = Cycle; 51015a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 51115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 51215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned getCurCycle() const { 51315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return CurCycle; 5146e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick } 515e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 516e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 517a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class ScheduleDAG { 518a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng public: 519a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng const TargetMachine &TM; // Target processor 520a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng const TargetInstrInfo *TII; // Target instruction information 5216f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI; // Target processor register info 52279ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman MachineFunction &MF; // Machine function 5239e23336d0c99fc5cae04037ead6d8f2b677e8764Evan Cheng MachineRegisterInfo &MRI; // Virtual/real register map 524e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng std::vector<SUnit> SUnits; // The scheduling units. 5259e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit EntrySU; // Special node for the region entry. 5269e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit ExitSU; // Special node for the region exit. 527a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 5284cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifdef NDEBUG 5294cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick static const bool StressSched = false; 5304cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#else 5314cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick bool StressSched; 5324cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 5334cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick 53479ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAG(MachineFunction &mf); 535cccf1232a69e2d78516c61a97e7bfa26acefb714Evan Cheng 536343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAG(); 537a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 53847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// clearDAG - clear the DAG state (between regions). 53947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick void clearDAG(); 54047c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 541e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng /// getInstrDesc - Return the MCInstrDesc of this SUnit. 5422da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// Return NULL for SDNodes without a machine opcode. 543e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 5442da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick if (SU->isInstr()) return &SU->getInstr()->getDesc(); 5452da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick return getNodeDesc(SU->getNode()); 5462da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 5472da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 5483e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 5493e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// using 'dot'. 5503e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// 55156b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick void viewGraph(const Twine &Name, const Twine &Title); 5523e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman void viewGraph(); 5536e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 554343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const = 0; 5557d1cd3f21d68179f4ebf4ee18fb7a0ddca9c5a37Dan Gohman 556343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// getGraphNodeLabel - Return a label for an SUnit node in a visualization 557343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// of the ScheduleDAG. 558343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 5598a50f1fcf0147d4ba959dc48066ddf281d5bc7e6Evan Cheng 56056b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick /// getDAGLabel - Return a label for the region of code covered by the DAG. 56156b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick virtual std::string getDAGName() const = 0; 56256b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 563343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// addCustomGraphFeatures - Add custom features for a visualization of 564343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// the ScheduleDAG. 565d59b083d22a01d9c48c9ea16757186ebf7c7049aDan Gohman virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 5668a50f1fcf0147d4ba959dc48066ddf281d5bc7e6Evan Cheng 567a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 5684c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// VerifyScheduledDAG - Verify that all SUnits were scheduled and that 5694c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// their state is consistent. Return the number of scheduled SUnits. 5704c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick unsigned VerifyScheduledDAG(bool isBottomUp); 571a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 572a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 573343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman protected: 5743948d8102a1a070944d57aa6ea4c124a8d63e1f5Dan Gohman /// ComputeLatency - Compute node latency. 5753948d8102a1a070944d57aa6ea4c124a8d63e1f5Dan Gohman /// 576953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void computeLatency(SUnit *SU) = 0; 5773948d8102a1a070944d57aa6ea4c124a8d63e1f5Dan Gohman 5787362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif /// ForceUnitLatencies - Return true if all scheduling edges should be given 5797362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif /// a latency value of one. The default is to return false; schedulers may 5803f23744df4809eba94284e601e81489212c974d4Dan Gohman /// override this as needed. 581953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual bool forceUnitLatencies() const { return false; } 5823f23744df4809eba94284e601e81489212c974d4Dan Gohman 5832da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick private: 584e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng // Return the MCInstrDesc of this SDNode or NULL. 585e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 586a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng }; 587a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 5887362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif class SUnitIterator : public std::iterator<std::forward_iterator_tag, 5897362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif SUnit, ptrdiff_t> { 5903e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnit *Node; 5913e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman unsigned Operand; 5923e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 5933e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 5943e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman public: 5953e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman bool operator==(const SUnitIterator& x) const { 5963e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return Operand == x.Operand; 5973e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 5983e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 5993e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6003e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman const SUnitIterator &operator=(const SUnitIterator &I) { 6017362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif assert(I.Node==Node && "Cannot assign iterators to two different nodes!"); 6023e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman Operand = I.Operand; 6033e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return *this; 6043e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6053e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6063e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman pointer operator*() const { 60754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Node->Preds[Operand].getSUnit(); 6083e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6093e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman pointer operator->() const { return operator*(); } 6103e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6113e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator& operator++() { // Preincrement 6123e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman ++Operand; 6133e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return *this; 6143e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6153e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator operator++(int) { // Postincrement 6163e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator tmp = *this; ++*this; return tmp; 6173e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6183e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6193e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 6203e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static SUnitIterator end (SUnit *N) { 62134cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return SUnitIterator(N, (unsigned)N->Preds.size()); 6223e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6233e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6243e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman unsigned getOperand() const { return Operand; } 6253e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman const SUnit *getNode() const { return Node; } 62654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isCtrlDep - Test if this is not an SDep::Data dependence. 62754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isCtrlDep() const { 628c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return getSDep().isCtrl(); 62954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 63054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isArtificialDep() const { 631c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return getSDep().isArtificial(); 632c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman } 633c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman const SDep &getSDep() const { 634c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return Node->Preds[Operand]; 63554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 6363e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 6373e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6383e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman template <> struct GraphTraits<SUnit*> { 6393e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef SUnit NodeType; 6403e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef SUnitIterator ChildIteratorType; 6413e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline NodeType *getEntryNode(SUnit *N) { return N; } 6423e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline ChildIteratorType child_begin(NodeType *N) { 6433e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return SUnitIterator::begin(N); 6443e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6453e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline ChildIteratorType child_end(NodeType *N) { 6463e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return SUnitIterator::end(N); 6473e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6483e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 6493e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6503e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 6513e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef std::vector<SUnit>::iterator nodes_iterator; 6523e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static nodes_iterator nodes_begin(ScheduleDAG *G) { 6533e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return G->SUnits.begin(); 6543e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6553e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static nodes_iterator nodes_end(ScheduleDAG *G) { 6563e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return G->SUnits.end(); 6573e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6583e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 65921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 66021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ScheduleDAGTopologicalSort is a class that computes a topological 66121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ordering for SUnits and provides methods for dynamically updating 66221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// the ordering as new edges are added. 66321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// 66421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// This allows a very fast implementation of IsReachable, for example. 66521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// 66621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman class ScheduleDAGTopologicalSort { 66721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// SUnits - A reference to the ScheduleDAG's SUnits. 66821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit> &SUnits; 66921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 67021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Index2Node - Maps topological index to the node number. 67121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> Index2Node; 67221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Node2Index - Maps the node number to its topological index. 67321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> Node2Index; 67421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Visited - a set of nodes visited during a DFS traversal. 67521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman BitVector Visited; 67621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 6776e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// DFS - make a DFS traversal and mark all nodes affected by the 67821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// edge insertion. These nodes will later get new topological indexes 67921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// by means of the Shift method. 68021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 68121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 68221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Shift - reassign topological indexes for the nodes in the DAG 68321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// to preserve the topological ordering. 68421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void Shift(BitVector& Visited, int LowerBound, int UpperBound); 68521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 68621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Allocate - assign the topological index to the node n. 68721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void Allocate(int n, int index); 68821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 68921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman public: 69021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman explicit ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits); 69121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 6926e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// InitDAGTopologicalSorting - create the initial topological 69321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ordering from the DAG to be scheduled. 69421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void InitDAGTopologicalSorting(); 69521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 69621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// IsReachable - Checks if SU is reachable from TargetSU. 69721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 69821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 69921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU 70021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// will create a cycle. 70121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool WillCreateCycle(SUnit *SU, SUnit *TargetSU); 70221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7037a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner /// AddPred - Updates the topological ordering to accommodate an edge 70421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// to be added from SUnit X to SUnit Y. 70521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void AddPred(SUnit *Y, SUnit *X); 70621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7077a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner /// RemovePred - Updates the topological ordering to accommodate an 70821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// an edge to be removed from the specified node N from the predecessors 70921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// of the current node M. 71021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void RemovePred(SUnit *M, SUnit *N); 71121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 71221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::iterator iterator; 71321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::const_iterator const_iterator; 71421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman iterator begin() { return Index2Node.begin(); } 71521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_iterator begin() const { return Index2Node.begin(); } 71621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman iterator end() { return Index2Node.end(); } 71721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_iterator end() const { return Index2Node.end(); } 71821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 71921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::reverse_iterator reverse_iterator; 72021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 72121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman reverse_iterator rbegin() { return Index2Node.rbegin(); } 72221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 72321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman reverse_iterator rend() { return Index2Node.rend(); } 72421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_reverse_iterator rend() const { return Index2Node.rend(); } 72521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman }; 726a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng} 727a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 728a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng#endif 729