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 1921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman#include "llvm/ADT/BitVector.h" 203e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman#include "llvm/ADT/GraphTraits.h" 2154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman#include "llvm/ADT/PointerIntPair.h" 22255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/ADT/SmallVector.h" 23751bc8d4c9ee4298449fed264571ffc162852e06Jakub Staszak#include "llvm/CodeGen/MachineInstr.h" 24255f89faee13dc491cb64fbeae3c763e7e2ea4e6Chandler Carruth#include "llvm/Target/TargetLowering.h" 25e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 26a9c2091cd38e401c846391c9951ff416e709b65eEvan Chengnamespace llvm { 2798976e4dcd18adbbe676048c0069e67346eb4adeDan Gohman class AliasAnalysis; 2848fe63526e35ddaee7e98879596a569911f41319Sebastian Redl class SUnit; 29a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class MachineConstantPool; 306b2cf285bd43fdc98ca68df477570ef6938d4fb2Evan Cheng class MachineFunction; 3184bc5427d6883f73cfeae3da640acd011d35c006Chris Lattner class MachineRegisterInfo; 32a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class MachineInstr; 338d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick struct MCSchedClassDesc; 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 55ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // Strong dependencies must be respected by the scheduler. Artificial 56ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // dependencies may be removed only if they are redundant with another 57ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // strong depedence. 58ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // 59ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // Weak dependencies may be violated by the scheduling strategy, but only if 60ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // the strategy can prove it is correct to do so. 61ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // 62ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // Strong OrderKinds must occur before "Weak". 63ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick // Weak OrderKinds must occur after "Weak". 64a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick enum OrderKind { 65a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Barrier, ///< An unknown scheduling barrier. 66a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick MayAliasMem, ///< Nonvolatile load/Store instructions that may alias. 67a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick MustAliasMem, ///< Nonvolatile load/Store instructions that must alias. 68ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick Artificial, ///< Arbitrary strong DAG edge (no real dependence). 69ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick Weak, ///< Arbitrary weak DAG edge. 70ae692f2baedf53504af2715993b166950e185a55Andrew Trick Cluster ///< Weak DAG edge linking a chain of clustered instrs. 71a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick }; 72a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick 7354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman private: 7454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Dep - A pointer to the depending/depended-on SUnit, and an enum 7554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// indicating the kind of the dependency. 7654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman PointerIntPair<SUnit *, 2, Kind> Dep; 7754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 7854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Contents - A union discriminated by the dependence kind. 7954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman union { 8054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Reg - For Data, Anti, and Output dependencies, the associated 8154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// register. For Data dependencies that don't currently have a register 8254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// assigned, this is set to zero. 8354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned Reg; 8454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 8554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Order - Additional information about Order dependencies. 86a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick unsigned OrdKind; // enum OrderKind 8754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } Contents; 8854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 8954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// Latency - The time associated with this edge. Often this is just 9054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// the value of the Latency field of the predecessor, however advanced 9154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// models may provide additional information about specific edges. 9254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned Latency; 93ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// Record MinLatency seperately from "expected" Latency. 94a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick /// 95a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick /// FIXME: this field is not packed on LP64. Convert to 16-bit DAG edge 96a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick /// latency after introducing saturating truncation. 97ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick unsigned MinLatency; 9854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 9954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman public: 10054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// SDep - Construct a null SDep. This is only for use by container 10154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// classes which require default constructors. SUnits may not 10254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// have null SDep edges. 10354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SDep() : Dep(0, Data) {} 10454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 10554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// SDep - Construct an SDep with the specified values. 106a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep(SUnit *S, Kind kind, unsigned Reg) 107a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick : Dep(S, kind), Contents() { 10854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (kind) { 109a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick default: 110a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick llvm_unreachable("Reg given for non-register dependence!"); 11154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Anti: 11254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Output: 11354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(Reg != 0 && 11454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Anti and SDep::Output must use a non-zero Reg!"); 11554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Reg = Reg; 116a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Latency = 0; 11754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman break; 118a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick case Data: 119a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Contents.Reg = Reg; 120a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Latency = 1; 12154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman break; 12254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 123a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick MinLatency = Latency; 124a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick } 125a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep(SUnit *S, OrderKind kind) 126a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick : Dep(S, Order), Contents(), Latency(0), MinLatency(0) { 127a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Contents.OrdKind = kind; 12854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 12954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 1309df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick /// Return true if the specified SDep is equivalent except for latency. 1319df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick bool overlaps(const SDep &Other) const { 1329df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (Dep != Other.Dep) return false; 13354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (Dep.getInt()) { 13454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Data: 13554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Anti: 13654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Output: 13754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Contents.Reg == Other.Contents.Reg; 13854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Order: 139a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return Contents.OrdKind == Other.Contents.OrdKind; 14054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 141aae875c27ce59e1c98dbc4a2358a006f2edef433Craig Topper llvm_unreachable("Invalid dependency kind!"); 14254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 14354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 1449df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick bool operator==(const SDep &Other) const { 145ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick return overlaps(Other) 146ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick && Latency == Other.Latency && MinLatency == Other.MinLatency; 1479df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 1489df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick 14954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool operator!=(const SDep &Other) const { 15054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return !operator==(Other); 15154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 15254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 15354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getLatency - Return the latency value for this edge, which roughly 15454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// means the minimum number of cycles that must elapse between the 15554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// predecessor and the successor, given that they have this edge 15654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// between them. 15754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned getLatency() const { 15854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Latency; 15954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 16054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 161710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin /// setLatency - Set the latency for this edge. 162710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin void setLatency(unsigned Lat) { 163710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin Latency = Lat; 164710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin } 165710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 166ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// getMinLatency - Return the minimum latency for this edge. Minimum 167ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// latency is used for scheduling groups, while normal (expected) latency 168ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// is for instruction cost and critical path. 169ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick unsigned getMinLatency() const { 170ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick return MinLatency; 171ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick } 172ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick 173ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick /// setMinLatency - Set the minimum latency for this edge. 174ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick void setMinLatency(unsigned Lat) { 175ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick MinLatency = Lat; 176ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick } 177ffd2526fa4e2d78564694b4797b96236c9ba9d85Andrew Trick 17854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman //// getSUnit - Return the SUnit to which this edge points. 17954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *getSUnit() const { 18054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Dep.getPointer(); 18154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 18254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 18354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman //// setSUnit - Assign the SUnit to which this edge points. 18454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void setSUnit(SUnit *SU) { 18554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Dep.setPointer(SU); 18654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 18754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 18854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getKind - Return an enum value representing the kind of the dependence. 18954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Kind getKind() const { 19054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Dep.getInt(); 19154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 19254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 19354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isCtrl - Shorthand for getKind() != SDep::Data. 19454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isCtrl() const { 19554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return getKind() != Data; 19654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 19754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 198fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// isNormalMemory - Test if this is an Order dependence between two 199fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// memory accesses where both sides of the dependence access memory 200fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// in non-volatile and fully modeled ways. 201fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman bool isNormalMemory() const { 202a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return getKind() == Order && (Contents.OrdKind == MayAliasMem 203a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick || Contents.OrdKind == MustAliasMem); 204fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman } 205fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman 20654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isMustAlias - Test if this is an Order dependence that is marked 20754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// as "must alias", meaning that the SUnits at either end of the edge 20854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// have a memory dependence on a known memory location. 20954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isMustAlias() const { 210a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return getKind() == Order && Contents.OrdKind == MustAliasMem; 21154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 21254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 213ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// isWeak - Test if this a weak dependence. Weak dependencies are 214ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// considered DAG edges for height computation and other heuristics, but do 215ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// not force ordering. Breaking a weak edge may require the scheduler to 216ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// compensate, for example by inserting a copy. 217ae692f2baedf53504af2715993b166950e185a55Andrew Trick bool isWeak() const { 218ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick return getKind() == Order && Contents.OrdKind >= Weak; 219ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 220ae692f2baedf53504af2715993b166950e185a55Andrew Trick 221e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman /// isArtificial - Test if this is an Order dependence that is marked 222e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman /// as "artificial", meaning it isn't necessary for correctness. 223e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman bool isArtificial() const { 224a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return getKind() == Order && Contents.OrdKind == Artificial; 225e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman } 226e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman 227ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// isCluster - Test if this is an Order dependence that is marked 228ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// as "cluster", meaning it is artificial and wants to be adjacent. 229ae692f2baedf53504af2715993b166950e185a55Andrew Trick bool isCluster() const { 230ae692f2baedf53504af2715993b166950e185a55Andrew Trick return getKind() == Order && Contents.OrdKind == Cluster; 231ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 232ae692f2baedf53504af2715993b166950e185a55Andrew Trick 23354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isAssignedRegDep - Test if this is a Data dependence that is 23454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// associated with a register. 23554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isAssignedRegDep() const { 23654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return getKind() == Data && Contents.Reg != 0; 23754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 23854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 23954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getReg - Return the register associated with this edge. This is 24054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// only valid on Data, Anti, and Output edges. On Data edges, this 24154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// value may be zero, meaning there is no associated register. 24254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned getReg() const { 24354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 24454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "getReg called on non-register dependence edge!"); 24554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Contents.Reg; 24654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 24754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 24854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// setReg - Assign the associated register for this edge. This is 24954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// only valid on Data, Anti, and Output edges. On Anti and Output 25054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// edges, this value must not be zero. On Data edges, the value may 25154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// be zero, which would mean that no specific register is associated 25254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// with this edge. 25354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void setReg(unsigned Reg) { 25454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 25554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "setReg called on non-register dependence edge!"); 25654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() != Anti || Reg != 0) && 25754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Anti edge cannot use the zero register!"); 25854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() != Output || Reg != 0) && 25954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Output edge cannot use the zero register!"); 26054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Reg = Reg; 26154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 262713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng }; 263713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng 264dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer template <> 265dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer struct isPodLike<SDep> { static const bool value = true; }; 266dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer 267343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// SUnit - Scheduling unit. This is a node in the scheduling DAG. 268aff9c270de8de7d1a0bc138d391bc67136bad58eCedric Venet class SUnit { 269550f5afb68ce8f034991863cac65bef22a6554daDan Gohman private: 270a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick enum { BoundaryID = ~0u }; 271a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick 272e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SDNode *Node; // Representative node. 273f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman MachineInstr *Instr; // Alternatively, a MachineInstr. 274550f5afb68ce8f034991863cac65bef22a6554daDan Gohman public: 2754c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman SUnit *OrigNode; // If not this, the node from which 2764c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman // this node was cloned. 277b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick // (SD scheduling only) 2786e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 2798d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass. 2808d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick 2816e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick // Preds/Succs - The SUnits before/after us in the graph. 282713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SmallVector<SDep, 4> Preds; // All sunit predecessors. 283713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SmallVector<SDep, 4> Succs; // All sunit successors. 284713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng 285713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::iterator pred_iterator; 286713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::iterator succ_iterator; 287713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::const_iterator const_pred_iterator; 288713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng typedef SmallVector<SDep, 4>::const_iterator const_succ_iterator; 2891cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 290a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng unsigned NodeNum; // Entry # of node in the node vector. 291a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein unsigned NodeQueueId; // Queue id of node. 292c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumPreds; // # of SDep::Data preds. 293c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumSuccs; // # of SDep::Data sucss. 294c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumPredsLeft; // # of preds not scheduled. 295c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumSuccsLeft; // # of succs not scheduled. 296ae692f2baedf53504af2715993b166950e185a55Andrew Trick unsigned WeakPredsLeft; // # of weak preds not scheduled. 297ae692f2baedf53504af2715993b166950e185a55Andrew Trick unsigned WeakSuccsLeft; // # of weak succs not scheduled. 29892e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. 299dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer unsigned short Latency; // Node latency. 30054699765064842fd08d1466adc93453660bc2a85Andrew Trick bool isVRegCycle : 1; // May use and def the same vreg. 3018239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng bool isCall : 1; // Is a function call. 302554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng bool isCallOp : 1; // Is a function call operand. 303e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isTwoAddress : 1; // Is a two-address instruction. 30413d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng bool isCommutable : 1; // Is a commutable instruction. 305f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng bool hasPhysRegDefs : 1; // Has physreg defs that are being used. 3063974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not. 307e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isPending : 1; // True once pending. 308e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isAvailable : 1; // True once available. 309e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isScheduled : 1; // True once scheduled. 3108749b61178228ba1fb2668034d79da1b247173d7Dan Gohman bool isScheduleHigh : 1; // True if preferable to schedule high. 31112f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick bool isScheduleLow : 1; // True if preferable to schedule low. 312e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng bool isCloned : 1; // True if this node has been cloned. 3131cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng Sched::Preference SchedulingPref; // Scheduling preference. 314309d20c89c5fde5a6ebe3b40a3fd0fbc3e5ffe40Jim Grosbach 3153f23744df4809eba94284e601e81489212c974d4Dan Gohman private: 3163f23744df4809eba94284e601e81489212c974d4Dan Gohman bool isDepthCurrent : 1; // True if Depth is current. 3173f23744df4809eba94284e601e81489212c974d4Dan Gohman bool isHeightCurrent : 1; // True if Height is current. 3183f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned Depth; // Node depth. 3193f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned Height; // Node height. 3203f23744df4809eba94284e601e81489212c974d4Dan Gohman public: 321b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick unsigned TopReadyCycle; // Cycle relative to start when node is ready. 322b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick unsigned BotReadyCycle; // Cycle relative to end when node is ready. 323b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick 3248ed3ffee53105275ca03f06ba0195bc6008477faEvan Cheng const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 3258ed3ffee53105275ca03f06ba0195bc6008477faEvan Cheng const TargetRegisterClass *CopySrcRC; 3266e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 327f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent 328f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// an SDNode and any nodes flagged to it. 329e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnit(SDNode *node, unsigned nodenum) 3308d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick : Node(node), Instr(0), OrigNode(0), SchedClass(0), NodeNum(nodenum), 331dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 332ae692f2baedf53504af2715993b166950e185a55Andrew Trick NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), 333ae692f2baedf53504af2715993b166950e185a55Andrew Trick Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), 334ae692f2baedf53504af2715993b166950e185a55Andrew Trick isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), 335ae692f2baedf53504af2715993b166950e185a55Andrew Trick hasPhysRegClobbers(false), isPending(false), isAvailable(false), 336ae692f2baedf53504af2715993b166950e185a55Andrew Trick isScheduled(false), isScheduleHigh(false), isScheduleLow(false), 337ae692f2baedf53504af2715993b166950e185a55Andrew Trick isCloned(false), SchedulingPref(Sched::None), 338e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 339b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 340f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 341f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// SUnit - Construct an SUnit for post-regalloc scheduling to represent 342f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// a MachineInstr. 343f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman SUnit(MachineInstr *instr, unsigned nodenum) 3448d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick : Node(0), Instr(instr), OrigNode(0), SchedClass(0), NodeNum(nodenum), 345dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 346ae692f2baedf53504af2715993b166950e185a55Andrew Trick NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), 347ae692f2baedf53504af2715993b166950e185a55Andrew Trick Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), 348ae692f2baedf53504af2715993b166950e185a55Andrew Trick isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), 349ae692f2baedf53504af2715993b166950e185a55Andrew Trick hasPhysRegClobbers(false), isPending(false), isAvailable(false), 350ae692f2baedf53504af2715993b166950e185a55Andrew Trick isScheduled(false), isScheduleHigh(false), isScheduleLow(false), 351ae692f2baedf53504af2715993b166950e185a55Andrew Trick isCloned(false), SchedulingPref(Sched::None), 352e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 353b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 354a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 3559e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// SUnit - Construct a placeholder SUnit. 3569e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit() 357a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick : Node(0), Instr(0), OrigNode(0), SchedClass(0), NodeNum(BoundaryID), 358dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer NodeQueueId(0), NumPreds(0), NumSuccs(0), NumPredsLeft(0), 359ae692f2baedf53504af2715993b166950e185a55Andrew Trick NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), NumRegDefsLeft(0), 360ae692f2baedf53504af2715993b166950e185a55Andrew Trick Latency(0), isVRegCycle(false), isCall(false), isCallOp(false), 361ae692f2baedf53504af2715993b166950e185a55Andrew Trick isTwoAddress(false), isCommutable(false), hasPhysRegDefs(false), 362ae692f2baedf53504af2715993b166950e185a55Andrew Trick hasPhysRegClobbers(false), isPending(false), isAvailable(false), 363ae692f2baedf53504af2715993b166950e185a55Andrew Trick isScheduled(false), isScheduleHigh(false), isScheduleLow(false), 364ae692f2baedf53504af2715993b166950e185a55Andrew Trick isCloned(false), SchedulingPref(Sched::None), 3659e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman isDepthCurrent(false), isHeightCurrent(false), Depth(0), Height(0), 366b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick TopReadyCycle(0), BotReadyCycle(0), CopyDstRC(NULL), CopySrcRC(NULL) {} 3679e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 368a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// \brief Boundary nodes are placeholders for the boundary of the 369a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// scheduling region. 370a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// 371a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// BoundaryNodes can have DAG edges, including Data edges, but they do not 372a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// correspond to schedulable entities (e.g. instructions) and do not have a 373a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// valid ID. Consequently, always check for boundary nodes before accessing 374a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// an assoicative data structure keyed on node ID. 375a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick bool isBoundaryNode() const { return NodeNum == BoundaryID; }; 376a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick 377550f5afb68ce8f034991863cac65bef22a6554daDan Gohman /// setNode - Assign the representative SDNode for this SUnit. 378f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during pre-regalloc scheduling. 379f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman void setNode(SDNode *N) { 380f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 381f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman Node = N; 382f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 383550f5afb68ce8f034991863cac65bef22a6554daDan Gohman 384550f5afb68ce8f034991863cac65bef22a6554daDan Gohman /// getNode - Return the representative SDNode for this SUnit. 385f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during pre-regalloc scheduling. 386f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman SDNode *getNode() const { 387f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 388f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman return Node; 389f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 390f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 3912da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// isInstr - Return true if this SUnit refers to a machine instruction as 3922da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// opposed to an SDNode. 393a75ce9f5d2236d93c117e861e60e6f3f748c9555Andrew Trick bool isInstr() const { return Instr; } 3942da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 395f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// setInstr - Assign the instruction for the SUnit. 396f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during post-regalloc scheduling. 397f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman void setInstr(MachineInstr *MI) { 398f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 399f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman Instr = MI; 400f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 401f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 402f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// getInstr - Return the representative MachineInstr for this SUnit. 403f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during post-regalloc scheduling. 404f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman MachineInstr *getInstr() const { 405f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 406f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman return Instr; 407f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 408550f5afb68ce8f034991863cac65bef22a6554daDan Gohman 40954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// addPred - This adds the specified edge as a pred of the current node if 410cddd428459a66830b0d072823f94224ace58e625Dan Gohman /// not already. It also adds the current node as a successor of the 411ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman /// specified node. 412ae692f2baedf53504af2715993b166950e185a55Andrew Trick bool addPred(const SDep &D, bool Required = true); 413228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner 41454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// removePred - This removes the specified edge as a pred of the current 41554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// node if it exists. It also removes the current node as a successor of 416ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman /// the specified node. 417c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman void removePred(const SDep &D); 418a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 41989bf4f2f5e6f54fe6382f07c515e36adc9e0c9c2Dan Gohman /// getDepth - Return the depth of this node, which is the length of the 420d756eceb83fc9a7536f76adfe24cdb19d4c2f253Eric Christopher /// maximum path up to any node which has no predecessors. 421557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin unsigned getDepth() const { 4226e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick if (!isDepthCurrent) 423557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin const_cast<SUnit *>(this)->ComputeDepth(); 4243f23744df4809eba94284e601e81489212c974d4Dan Gohman return Depth; 4253f23744df4809eba94284e601e81489212c974d4Dan Gohman } 4263f23744df4809eba94284e601e81489212c974d4Dan Gohman 4273f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getHeight - Return the height of this node, which is the length of the 428d756eceb83fc9a7536f76adfe24cdb19d4c2f253Eric Christopher /// maximum path down to any node which has no successors. 429557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin unsigned getHeight() const { 4306e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick if (!isHeightCurrent) 431557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin const_cast<SUnit *>(this)->ComputeHeight(); 4323f23744df4809eba94284e601e81489212c974d4Dan Gohman return Height; 4333f23744df4809eba94284e601e81489212c974d4Dan Gohman } 4343f23744df4809eba94284e601e81489212c974d4Dan Gohman 4354de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// setDepthToAtLeast - If NewDepth is greater than this node's 4364de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// depth value, set it to be the new depth value. This also 437557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin /// recursively marks successor nodes dirty. 438557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void setDepthToAtLeast(unsigned NewDepth); 4393f23744df4809eba94284e601e81489212c974d4Dan Gohman 4404de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// setDepthToAtLeast - If NewDepth is greater than this node's 4414de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// depth value, set it to be the new height value. This also 442557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin /// recursively marks predecessor nodes dirty. 443557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void setHeightToAtLeast(unsigned NewHeight); 4443f23744df4809eba94284e601e81489212c974d4Dan Gohman 4453f23744df4809eba94284e601e81489212c974d4Dan Gohman /// setDepthDirty - Set a flag in this node to indicate that its 4463f23744df4809eba94284e601e81489212c974d4Dan Gohman /// stored Depth value will require recomputation the next time 4473f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getDepth() is called. 4483f23744df4809eba94284e601e81489212c974d4Dan Gohman void setDepthDirty(); 4493f23744df4809eba94284e601e81489212c974d4Dan Gohman 4503f23744df4809eba94284e601e81489212c974d4Dan Gohman /// setHeightDirty - Set a flag in this node to indicate that its 4513f23744df4809eba94284e601e81489212c974d4Dan Gohman /// stored Height value will require recomputation the next time 4523f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getHeight() is called. 4533f23744df4809eba94284e601e81489212c974d4Dan Gohman void setHeightDirty(); 4543f23744df4809eba94284e601e81489212c974d4Dan Gohman 4553f23744df4809eba94284e601e81489212c974d4Dan Gohman /// isPred - Test if node N is a predecessor of this node. 456a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng bool isPred(SUnit *N) { 45734cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 45854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (Preds[i].getSUnit() == N) 459a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return true; 460a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 461a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 4626e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 4633f23744df4809eba94284e601e81489212c974d4Dan Gohman /// isSucc - Test if node N is a successor of this node. 464a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng bool isSucc(SUnit *N) { 46534cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) 46654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (Succs[i].getSUnit() == N) 467a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return true; 468a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 469228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner } 4701cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 47117d35e57a585e869dc3084666abd17f173723735Andrew Trick bool isTopReady() const { 47217d35e57a585e869dc3084666abd17f173723735Andrew Trick return NumPredsLeft == 0; 47317d35e57a585e869dc3084666abd17f173723735Andrew Trick } 47417d35e57a585e869dc3084666abd17f173723735Andrew Trick bool isBottomReady() const { 47517d35e57a585e869dc3084666abd17f173723735Andrew Trick return NumSuccsLeft == 0; 47617d35e57a585e869dc3084666abd17f173723735Andrew Trick } 47717d35e57a585e869dc3084666abd17f173723735Andrew Trick 47866658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick /// \brief Order this node's predecessor edges such that the critical path 47966658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick /// edge occurs first. 48066658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick void biasCriticalPath(); 48166658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick 4823cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman void dump(const ScheduleDAG *G) const; 4833cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman void dumpAll(const ScheduleDAG *G) const; 484252ae9e8ae4efaf1f67a608ad2563323308bd803Dan Gohman void print(raw_ostream &O, const ScheduleDAG *G) const; 4853f23744df4809eba94284e601e81489212c974d4Dan Gohman 4863f23744df4809eba94284e601e81489212c974d4Dan Gohman private: 487557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void ComputeDepth(); 488557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void ComputeHeight(); 489e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 490e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 491e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng //===--------------------------------------------------------------------===// 492e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// SchedulingPriorityQueue - This interface is used to plug different 493e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// priorities computation algorithms into the list scheduler. It implements 4946e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// the interface of a standard priority queue, where nodes are inserted in 495e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// arbitrary order and returned in priority order. The computation of the 496e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// priority and the representation of the queue are totally up to the 497e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// implementation to decide. 4986e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// 499e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng class SchedulingPriorityQueue { 5002d24e2a396a1d211baaeedf32148a3b657240170David Blaikie virtual void anchor(); 50115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned CurCycle; 5022da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick bool HasReadyFilter; 503e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng public: 5042da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick SchedulingPriorityQueue(bool rf = false): 5052da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick CurCycle(0), HasReadyFilter(rf) {} 506e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual ~SchedulingPriorityQueue() {} 5076e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 5082da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick virtual bool isBottomUp() const = 0; 5092da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 51094d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 511a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void addNode(const SUnit *SU) = 0; 512a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void updateNode(const SUnit *SU) = 0; 513e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual void releaseState() = 0; 514a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 515e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual bool empty() const = 0; 5162da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 5172da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick bool hasReadyFilter() const { return HasReadyFilter; } 5182da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 51992e946630d5f9bb092853b93501387dd216899b9Andrew Trick virtual bool tracksRegPressure() const { return false; } 52092e946630d5f9bb092853b93501387dd216899b9Andrew Trick 5217853ae1d97acb65bd4dfd9a15478c14f475dbd41Eric Christopher virtual bool isReady(SUnit *) const { 5222da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick assert(!HasReadyFilter && "The ready filter must override isReady()"); 5232da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick return true; 5242da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 525e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual void push(SUnit *U) = 0; 5266e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 527a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman void push_all(const std::vector<SUnit *> &Nodes) { 528a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 529a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman E = Nodes.end(); I != E; ++I) 530a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman push(*I); 531a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman } 532a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman 533e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual SUnit *pop() = 0; 534e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 535a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void remove(SUnit *SU) = 0; 536a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 5377853ae1d97acb65bd4dfd9a15478c14f475dbd41Eric Christopher virtual void dump(ScheduleDAG *) const {} 5382da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 539953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// scheduledNode - As each node is scheduled, this method is invoked. This 540a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// allows the priority function to adjust the priority of related 541a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// unscheduled nodes, for example. 542a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// 543953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void scheduledNode(SUnit *) {} 544a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 545953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void unscheduledNode(SUnit *) {} 54615a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 54715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng void setCurCycle(unsigned Cycle) { 54815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng CurCycle = Cycle; 54915a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 55015a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 55115a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned getCurCycle() const { 55215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return CurCycle; 5536e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick } 554e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 555e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 556a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class ScheduleDAG { 557a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng public: 558a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng const TargetMachine &TM; // Target processor 559a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng const TargetInstrInfo *TII; // Target instruction information 5606f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI; // Target processor register info 56179ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman MachineFunction &MF; // Machine function 5629e23336d0c99fc5cae04037ead6d8f2b677e8764Evan Cheng MachineRegisterInfo &MRI; // Virtual/real register map 563e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng std::vector<SUnit> SUnits; // The scheduling units. 5649e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit EntrySU; // Special node for the region entry. 5659e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit ExitSU; // Special node for the region exit. 566a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 5674cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifdef NDEBUG 5684cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick static const bool StressSched = false; 5694cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#else 5704cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick bool StressSched; 5714cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 5724cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick 57379ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAG(MachineFunction &mf); 574cccf1232a69e2d78516c61a97e7bfa26acefb714Evan Cheng 575343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAG(); 576a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 57747c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// clearDAG - clear the DAG state (between regions). 57847c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick void clearDAG(); 57947c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 580e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng /// getInstrDesc - Return the MCInstrDesc of this SUnit. 5812da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// Return NULL for SDNodes without a machine opcode. 582e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 5832da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick if (SU->isInstr()) return &SU->getInstr()->getDesc(); 5842da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick return getNodeDesc(SU->getNode()); 5852da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 5862da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 5873e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 5883e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// using 'dot'. 5893e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// 5903084979ff27f48487c7421536144c41a36cae997Andrew Trick virtual void viewGraph(const Twine &Name, const Twine &Title); 5913084979ff27f48487c7421536144c41a36cae997Andrew Trick virtual void viewGraph(); 5926e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 593343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const = 0; 5947d1cd3f21d68179f4ebf4ee18fb7a0ddca9c5a37Dan Gohman 595343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// getGraphNodeLabel - Return a label for an SUnit node in a visualization 596343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// of the ScheduleDAG. 597343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 5988a50f1fcf0147d4ba959dc48066ddf281d5bc7e6Evan Cheng 59956b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick /// getDAGLabel - Return a label for the region of code covered by the DAG. 60056b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick virtual std::string getDAGName() const = 0; 60156b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 602343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// addCustomGraphFeatures - Add custom features for a visualization of 603343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// the ScheduleDAG. 604d59b083d22a01d9c48c9ea16757186ebf7c7049aDan Gohman virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 6058a50f1fcf0147d4ba959dc48066ddf281d5bc7e6Evan Cheng 606a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 6074c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// VerifyScheduledDAG - Verify that all SUnits were scheduled and that 6084c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// their state is consistent. Return the number of scheduled SUnits. 6094c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick unsigned VerifyScheduledDAG(bool isBottomUp); 610a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 611a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 6122da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick private: 613e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng // Return the MCInstrDesc of this SDNode or NULL. 614e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 615a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng }; 616a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 6177362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif class SUnitIterator : public std::iterator<std::forward_iterator_tag, 6187362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif SUnit, ptrdiff_t> { 6193e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnit *Node; 6203e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman unsigned Operand; 6213e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6223e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 6233e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman public: 6243e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman bool operator==(const SUnitIterator& x) const { 6253e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return Operand == x.Operand; 6263e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6273e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 6283e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6293e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman const SUnitIterator &operator=(const SUnitIterator &I) { 6307362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif assert(I.Node==Node && "Cannot assign iterators to two different nodes!"); 6313e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman Operand = I.Operand; 6323e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return *this; 6333e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6343e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6353e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman pointer operator*() const { 63654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Node->Preds[Operand].getSUnit(); 6373e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6383e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman pointer operator->() const { return operator*(); } 6393e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6403e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator& operator++() { // Preincrement 6413e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman ++Operand; 6423e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return *this; 6433e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6443e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator operator++(int) { // Postincrement 6453e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator tmp = *this; ++*this; return tmp; 6463e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6473e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6483e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 6493e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static SUnitIterator end (SUnit *N) { 65034cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return SUnitIterator(N, (unsigned)N->Preds.size()); 6513e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6523e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6533e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman unsigned getOperand() const { return Operand; } 6543e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman const SUnit *getNode() const { return Node; } 65554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isCtrlDep - Test if this is not an SDep::Data dependence. 65654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isCtrlDep() const { 657c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return getSDep().isCtrl(); 65854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 65954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isArtificialDep() const { 660c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return getSDep().isArtificial(); 661c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman } 662c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman const SDep &getSDep() const { 663c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return Node->Preds[Operand]; 66454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 6653e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 6663e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6673e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman template <> struct GraphTraits<SUnit*> { 6683e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef SUnit NodeType; 6693e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef SUnitIterator ChildIteratorType; 6703e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline NodeType *getEntryNode(SUnit *N) { return N; } 6713e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline ChildIteratorType child_begin(NodeType *N) { 6723e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return SUnitIterator::begin(N); 6733e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6743e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline ChildIteratorType child_end(NodeType *N) { 6753e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return SUnitIterator::end(N); 6763e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6773e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 6783e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6793e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 6803e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef std::vector<SUnit>::iterator nodes_iterator; 6813e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static nodes_iterator nodes_begin(ScheduleDAG *G) { 6823e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return G->SUnits.begin(); 6833e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6843e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static nodes_iterator nodes_end(ScheduleDAG *G) { 6853e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return G->SUnits.end(); 6863e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6873e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 68821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 68921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ScheduleDAGTopologicalSort is a class that computes a topological 69021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ordering for SUnits and provides methods for dynamically updating 69121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// the ordering as new edges are added. 69221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// 69321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// This allows a very fast implementation of IsReachable, for example. 69421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// 69521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman class ScheduleDAGTopologicalSort { 69621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// SUnits - A reference to the ScheduleDAG's SUnits. 69721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit> &SUnits; 698ae692f2baedf53504af2715993b166950e185a55Andrew Trick SUnit *ExitSU; 69921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 70021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Index2Node - Maps topological index to the node number. 70121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> Index2Node; 70221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Node2Index - Maps the node number to its topological index. 70321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> Node2Index; 70421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Visited - a set of nodes visited during a DFS traversal. 70521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman BitVector Visited; 70621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7076e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// DFS - make a DFS traversal and mark all nodes affected by the 70821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// edge insertion. These nodes will later get new topological indexes 70921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// by means of the Shift method. 71021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 71121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 71221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Shift - reassign topological indexes for the nodes in the DAG 71321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// to preserve the topological ordering. 71421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void Shift(BitVector& Visited, int LowerBound, int UpperBound); 71521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 71621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Allocate - assign the topological index to the node n. 71721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void Allocate(int n, int index); 71821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 71921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman public: 720ae692f2baedf53504af2715993b166950e185a55Andrew Trick ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); 72121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7226e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// InitDAGTopologicalSorting - create the initial topological 72321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ordering from the DAG to be scheduled. 72421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void InitDAGTopologicalSorting(); 72521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 72621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// IsReachable - Checks if SU is reachable from TargetSU. 72721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 72821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 72921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// WillCreateCycle - Returns true if adding an edge from SU to TargetSU 73021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// will create a cycle. 73121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool WillCreateCycle(SUnit *SU, SUnit *TargetSU); 73221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7337a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner /// AddPred - Updates the topological ordering to accommodate an edge 73421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// to be added from SUnit X to SUnit Y. 73521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void AddPred(SUnit *Y, SUnit *X); 73621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7377a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner /// RemovePred - Updates the topological ordering to accommodate an 73821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// an edge to be removed from the specified node N from the predecessors 73921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// of the current node M. 74021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void RemovePred(SUnit *M, SUnit *N); 74121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 74221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::iterator iterator; 74321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::const_iterator const_iterator; 74421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman iterator begin() { return Index2Node.begin(); } 74521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_iterator begin() const { return Index2Node.begin(); } 74621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman iterator end() { return Index2Node.end(); } 74721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_iterator end() const { return Index2Node.end(); } 74821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 74921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::reverse_iterator reverse_iterator; 75021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 75121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman reverse_iterator rbegin() { return Index2Node.rbegin(); } 75221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 75321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman reverse_iterator rend() { return Index2Node.rend(); } 75421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_reverse_iterator rend() const { return Index2Node.rend(); } 75521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman }; 756a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng} 757a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 758a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng#endif 759