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; 9354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 9454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman public: 9554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// SDep - Construct a null SDep. This is only for use by container 9654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// classes which require default constructors. SUnits may not 9754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// have null SDep edges. 98dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SDep() : Dep(nullptr, Data) {} 9954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 10054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// SDep - Construct an SDep with the specified values. 101a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep(SUnit *S, Kind kind, unsigned Reg) 102a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick : Dep(S, kind), Contents() { 10354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (kind) { 104a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick default: 105a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick llvm_unreachable("Reg given for non-register dependence!"); 10654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Anti: 10754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Output: 10854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert(Reg != 0 && 10954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Anti and SDep::Output must use a non-zero Reg!"); 11054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Reg = Reg; 111a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Latency = 0; 11254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman break; 113a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick case Data: 114a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Contents.Reg = Reg; 115a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Latency = 1; 11654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman break; 11754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 118a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick } 119a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick SDep(SUnit *S, OrderKind kind) 120b86a0cdb674549d8493043331cecd9cbf53b80daAndrew Trick : Dep(S, Order), Contents(), Latency(0) { 121a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick Contents.OrdKind = kind; 12254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 12354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 1249df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick /// Return true if the specified SDep is equivalent except for latency. 1259df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick bool overlaps(const SDep &Other) const { 1269df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick if (Dep != Other.Dep) return false; 12754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman switch (Dep.getInt()) { 12854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Data: 12954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Anti: 13054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Output: 13154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Contents.Reg == Other.Contents.Reg; 13254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman case Order: 133a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return Contents.OrdKind == Other.Contents.OrdKind; 13454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 135aae875c27ce59e1c98dbc4a2358a006f2edef433Craig Topper llvm_unreachable("Invalid dependency kind!"); 13654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 13754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 1389df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick bool operator==(const SDep &Other) const { 139b86a0cdb674549d8493043331cecd9cbf53b80daAndrew Trick return overlaps(Other) && Latency == Other.Latency; 1409df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick } 1419df55eed0470c898c4003dc433c4479bdb0e0aacAndrew Trick 14254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool operator!=(const SDep &Other) const { 14354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return !operator==(Other); 14454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 14554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 14654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getLatency - Return the latency value for this edge, which roughly 14754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// means the minimum number of cycles that must elapse between the 14854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// predecessor and the successor, given that they have this edge 14954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// between them. 15054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned getLatency() const { 15154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Latency; 15254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 15354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 154710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin /// setLatency - Set the latency for this edge. 155710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin void setLatency(unsigned Lat) { 156710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin Latency = Lat; 157710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin } 158710461688bba935f0ad5c75da7fec2ad0f225c00David Goodwin 15954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman //// getSUnit - Return the SUnit to which this edge points. 16054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman SUnit *getSUnit() const { 16154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Dep.getPointer(); 16254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 16354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 16454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman //// setSUnit - Assign the SUnit to which this edge points. 16554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void setSUnit(SUnit *SU) { 16654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Dep.setPointer(SU); 16754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 16854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 16954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getKind - Return an enum value representing the kind of the dependence. 17054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Kind getKind() const { 17154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Dep.getInt(); 17254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 17354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 17454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isCtrl - Shorthand for getKind() != SDep::Data. 17554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isCtrl() const { 17654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return getKind() != Data; 17754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 17854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 179fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// isNormalMemory - Test if this is an Order dependence between two 180fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// memory accesses where both sides of the dependence access memory 181fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman /// in non-volatile and fully modeled ways. 182fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman bool isNormalMemory() const { 183a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return getKind() == Order && (Contents.OrdKind == MayAliasMem 184a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick || Contents.OrdKind == MustAliasMem); 185fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman } 186fb8a1356b2aa2869b2a8ad13fe87bc43c349dd31Dan Gohman 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// isBarrier - Test if this is an Order dependence that is marked 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// as a barrier. 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isBarrier() const { 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return getKind() == Order && Contents.OrdKind == Barrier; 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isMustAlias - Test if this is an Order dependence that is marked 19454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// as "must alias", meaning that the SUnits at either end of the edge 19554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// have a memory dependence on a known memory location. 19654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isMustAlias() const { 197a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return getKind() == Order && Contents.OrdKind == MustAliasMem; 19854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 19954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 200ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// isWeak - Test if this a weak dependence. Weak dependencies are 201ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// considered DAG edges for height computation and other heuristics, but do 202ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// not force ordering. Breaking a weak edge may require the scheduler to 203ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// compensate, for example by inserting a copy. 204ae692f2baedf53504af2715993b166950e185a55Andrew Trick bool isWeak() const { 205ebff1d903508155f1b3d906fbc37023094843c1fAndrew Trick return getKind() == Order && Contents.OrdKind >= Weak; 206ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 207ae692f2baedf53504af2715993b166950e185a55Andrew Trick 208e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman /// isArtificial - Test if this is an Order dependence that is marked 209e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman /// as "artificial", meaning it isn't necessary for correctness. 210e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman bool isArtificial() const { 211a78d3228e8b2a14915ea9908dbaaf2c934803e11Andrew Trick return getKind() == Order && Contents.OrdKind == Artificial; 212e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman } 213e7c1c660ad420aa49f888ce955c4d17660616505Dan Gohman 214ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// isCluster - Test if this is an Order dependence that is marked 215ae692f2baedf53504af2715993b166950e185a55Andrew Trick /// as "cluster", meaning it is artificial and wants to be adjacent. 216ae692f2baedf53504af2715993b166950e185a55Andrew Trick bool isCluster() const { 217ae692f2baedf53504af2715993b166950e185a55Andrew Trick return getKind() == Order && Contents.OrdKind == Cluster; 218ae692f2baedf53504af2715993b166950e185a55Andrew Trick } 219ae692f2baedf53504af2715993b166950e185a55Andrew Trick 22054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isAssignedRegDep - Test if this is a Data dependence that is 22154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// associated with a register. 22254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isAssignedRegDep() const { 22354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return getKind() == Data && Contents.Reg != 0; 22454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 22554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 22654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// getReg - Return the register associated with this edge. This is 22754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// only valid on Data, Anti, and Output edges. On Data edges, this 22854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// value may be zero, meaning there is no associated register. 22954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman unsigned getReg() const { 23054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 23154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "getReg called on non-register dependence edge!"); 23254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Contents.Reg; 23354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 23454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman 23554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// setReg - Assign the associated register for this edge. This is 23654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// only valid on Data, Anti, and Output edges. On Anti and Output 23754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// edges, this value must not be zero. On Data edges, the value may 23854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// be zero, which would mean that no specific register is associated 23954e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// with this edge. 24054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman void setReg(unsigned Reg) { 24154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() == Data || getKind() == Anti || getKind() == Output) && 24254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "setReg called on non-register dependence edge!"); 24354e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() != Anti || Reg != 0) && 24454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Anti edge cannot use the zero register!"); 24554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman assert((getKind() != Output || Reg != 0) && 24654e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman "SDep::Output edge cannot use the zero register!"); 24754e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman Contents.Reg = Reg; 24854e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 249713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng }; 250713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng 251dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer template <> 252dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer struct isPodLike<SDep> { static const bool value = true; }; 253dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer 254343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// SUnit - Scheduling unit. This is a node in the scheduling DAG. 255aff9c270de8de7d1a0bc138d391bc67136bad58eCedric Venet class SUnit { 256550f5afb68ce8f034991863cac65bef22a6554daDan Gohman private: 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines enum : unsigned { BoundaryID = ~0u }; 258a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick 259e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SDNode *Node; // Representative node. 260f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman MachineInstr *Instr; // Alternatively, a MachineInstr. 261550f5afb68ce8f034991863cac65bef22a6554daDan Gohman public: 2624c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman SUnit *OrigNode; // If not this, the node from which 2634c8c83022b501759d8559e224c84ae2a9921ba41Dan Gohman // this node was cloned. 264b4566a999970b514d7c6973d99e293a6625d3f70Andrew Trick // (SD scheduling only) 2656e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 2668d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick const MCSchedClassDesc *SchedClass; // NULL or resolved SchedClass. 2678d4abb2446f80986ad5136bbec30c5da18cd6f4bAndrew Trick 2686e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick // Preds/Succs - The SUnits before/after us in the graph. 269713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SmallVector<SDep, 4> Preds; // All sunit predecessors. 270713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng SmallVector<SDep, 4> Succs; // All sunit successors. 271713a98dee8ab07a3066d1707a07648d27dd0c19cEvan Cheng 272d0a3916e430201d0179c723e4ebdd9bf4f0ee02bEric Christopher typedef SmallVectorImpl<SDep>::iterator pred_iterator; 273d0a3916e430201d0179c723e4ebdd9bf4f0ee02bEric Christopher typedef SmallVectorImpl<SDep>::iterator succ_iterator; 274d0a3916e430201d0179c723e4ebdd9bf4f0ee02bEric Christopher typedef SmallVectorImpl<SDep>::const_iterator const_pred_iterator; 275d0a3916e430201d0179c723e4ebdd9bf4f0ee02bEric Christopher typedef SmallVectorImpl<SDep>::const_iterator const_succ_iterator; 2761cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 277a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng unsigned NodeNum; // Entry # of node in the node vector. 278a0201d52049be8dcefffe4304a49690a831bcb34Roman Levenstein unsigned NodeQueueId; // Queue id of node. 279c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumPreds; // # of SDep::Data preds. 280c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumSuccs; // # of SDep::Data sucss. 281c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumPredsLeft; // # of preds not scheduled. 282c277ab08a24d2dbe9b4ff1a9154ea6115ed6a4e3Reid Kleckner unsigned NumSuccsLeft; // # of succs not scheduled. 283ae692f2baedf53504af2715993b166950e185a55Andrew Trick unsigned WeakPredsLeft; // # of weak preds not scheduled. 284ae692f2baedf53504af2715993b166950e185a55Andrew Trick unsigned WeakSuccsLeft; // # of weak succs not scheduled. 28592e946630d5f9bb092853b93501387dd216899b9Andrew Trick unsigned short NumRegDefsLeft; // # of reg defs with no scheduled use. 286dd1fc8cbf146a951ab0f15c25e92adef3f84ee58Benjamin Kramer unsigned short Latency; // Node latency. 28754699765064842fd08d1466adc93453660bc2a85Andrew Trick bool isVRegCycle : 1; // May use and def the same vreg. 2888239daf7c83a65a189c352cce3191cdc3bbfe151Evan Cheng bool isCall : 1; // Is a function call. 289554daa67bd1c4f01fb7a00f2f4255a52b81e9fa3Evan Cheng bool isCallOp : 1; // Is a function call operand. 290e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isTwoAddress : 1; // Is a two-address instruction. 29113d41b9d721f98372b97d2ec119e6c91932ab0aeEvan Cheng bool isCommutable : 1; // Is a commutable instruction. 2924392f0f407fe4e2a9ec53b2560a1cbf86357c190Andrew Trick bool hasPhysRegUses : 1; // Has physreg uses. 293f10c973797cf79da802f9b0118543cbd50954c9cEvan Cheng bool hasPhysRegDefs : 1; // Has physreg defs that are being used. 2943974667c1a6d48686e92f85bc4463bb239af7442Dan Gohman bool hasPhysRegClobbers : 1; // Has any physreg defs, used or not. 295e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isPending : 1; // True once pending. 296e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isAvailable : 1; // True once available. 297e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng bool isScheduled : 1; // True once scheduled. 2988749b61178228ba1fb2668034d79da1b247173d7Dan Gohman bool isScheduleHigh : 1; // True if preferable to schedule high. 29912f0dc6bb556976f22d89ebcf42bce273c9e7d38Andrew Trick bool isScheduleLow : 1; // True if preferable to schedule low. 300e57187cbe321a286f6a7f409a7badd1ae4e4642cEvan Cheng bool isCloned : 1; // True if this node has been cloned. 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool isUnbuffered : 1; // Uses an unbuffered resource. 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool hasReservedResource : 1; // Uses a reserved resource. 3031cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng Sched::Preference SchedulingPref; // Scheduling preference. 304309d20c89c5fde5a6ebe3b40a3fd0fbc3e5ffe40Jim Grosbach 3053f23744df4809eba94284e601e81489212c974d4Dan Gohman private: 3063f23744df4809eba94284e601e81489212c974d4Dan Gohman bool isDepthCurrent : 1; // True if Depth is current. 3073f23744df4809eba94284e601e81489212c974d4Dan Gohman bool isHeightCurrent : 1; // True if Height is current. 3083f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned Depth; // Node depth. 3093f23744df4809eba94284e601e81489212c974d4Dan Gohman unsigned Height; // Node height. 3103f23744df4809eba94284e601e81489212c974d4Dan Gohman public: 311b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick unsigned TopReadyCycle; // Cycle relative to start when node is ready. 312b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick unsigned BotReadyCycle; // Cycle relative to end when node is ready. 313b7e0289fb320c8440ba5eed121a8b932dbd806a2Andrew Trick 3148ed3ffee53105275ca03f06ba0195bc6008477faEvan Cheng const TargetRegisterClass *CopyDstRC; // Is a special copy node if not null. 3158ed3ffee53105275ca03f06ba0195bc6008477faEvan Cheng const TargetRegisterClass *CopySrcRC; 3166e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 317f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// SUnit - Construct an SUnit for pre-regalloc scheduling to represent 318f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// an SDNode and any nodes flagged to it. 319e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng SUnit(SDNode *node, unsigned nodenum) 320dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : Node(node), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr), 321dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), 322dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), 323dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), 324dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isCallOp(false), isTwoAddress(false), isCommutable(false), 325dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 326dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isPending(false), isAvailable(false), isScheduled(false), 327dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isScheduleHigh(false), isScheduleLow(false), isCloned(false), 328dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isUnbuffered(false), hasReservedResource(false), 329dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SchedulingPref(Sched::None), isDepthCurrent(false), 330dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), 331dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {} 332f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 333f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// SUnit - Construct an SUnit for post-regalloc scheduling to represent 334f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// a MachineInstr. 335f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman SUnit(MachineInstr *instr, unsigned nodenum) 336dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : Node(nullptr), Instr(instr), OrigNode(nullptr), SchedClass(nullptr), 337dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeNum(nodenum), NodeQueueId(0), NumPreds(0), NumSuccs(0), 338dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), 339dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), 340dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isCallOp(false), isTwoAddress(false), isCommutable(false), 341dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 342dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isPending(false), isAvailable(false), isScheduled(false), 343dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isScheduleHigh(false), isScheduleLow(false), isCloned(false), 344dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isUnbuffered(false), hasReservedResource(false), 345dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SchedulingPref(Sched::None), isDepthCurrent(false), 346dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), 347dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {} 348a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 3499e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman /// SUnit - Construct a placeholder SUnit. 3509e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit() 351dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines : Node(nullptr), Instr(nullptr), OrigNode(nullptr), SchedClass(nullptr), 352dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NodeNum(BoundaryID), NodeQueueId(0), NumPreds(0), NumSuccs(0), 353dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumPredsLeft(0), NumSuccsLeft(0), WeakPredsLeft(0), WeakSuccsLeft(0), 354dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines NumRegDefsLeft(0), Latency(0), isVRegCycle(false), isCall(false), 355dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isCallOp(false), isTwoAddress(false), isCommutable(false), 356dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines hasPhysRegUses(false), hasPhysRegDefs(false), hasPhysRegClobbers(false), 357dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isPending(false), isAvailable(false), isScheduled(false), 358dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isScheduleHigh(false), isScheduleLow(false), isCloned(false), 359dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isUnbuffered(false), hasReservedResource(false), 360dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines SchedulingPref(Sched::None), isDepthCurrent(false), 361dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines isHeightCurrent(false), Depth(0), Height(0), TopReadyCycle(0), 362dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BotReadyCycle(0), CopyDstRC(nullptr), CopySrcRC(nullptr) {} 3639e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman 364a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// \brief Boundary nodes are placeholders for the boundary of the 365a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// scheduling region. 366a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// 367a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// BoundaryNodes can have DAG edges, including Data edges, but they do not 368a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// correspond to schedulable entities (e.g. instructions) and do not have a 369a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// valid ID. Consequently, always check for boundary nodes before accessing 370a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick /// an assoicative data structure keyed on node ID. 371a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick bool isBoundaryNode() const { return NodeNum == BoundaryID; }; 372a5a73ad15905c18843a8312bb3f20f5c501744deAndrew Trick 373550f5afb68ce8f034991863cac65bef22a6554daDan Gohman /// setNode - Assign the representative SDNode for this SUnit. 374f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during pre-regalloc scheduling. 375f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman void setNode(SDNode *N) { 376f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Instr && "Setting SDNode of SUnit with MachineInstr!"); 377f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman Node = N; 378f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 379550f5afb68ce8f034991863cac65bef22a6554daDan Gohman 380550f5afb68ce8f034991863cac65bef22a6554daDan Gohman /// getNode - Return the representative SDNode for this SUnit. 381f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during pre-regalloc scheduling. 382f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman SDNode *getNode() const { 383f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Instr && "Reading SDNode of SUnit with MachineInstr!"); 384f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman return Node; 385f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 386f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 3872da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// isInstr - Return true if this SUnit refers to a machine instruction as 3882da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// opposed to an SDNode. 389a75ce9f5d2236d93c117e861e60e6f3f748c9555Andrew Trick bool isInstr() const { return Instr; } 3902da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 391f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// setInstr - Assign the instruction for the SUnit. 392f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during post-regalloc scheduling. 393f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman void setInstr(MachineInstr *MI) { 394f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Node && "Setting MachineInstr of SUnit with SDNode!"); 395f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman Instr = MI; 396f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 397f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman 398f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// getInstr - Return the representative MachineInstr for this SUnit. 399f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman /// This may be used during post-regalloc scheduling. 400f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman MachineInstr *getInstr() const { 401f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman assert(!Node && "Reading MachineInstr of SUnit with SDNode!"); 402f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman return Instr; 403f449bf36ef5cb8e23fa2b5bc43f8d54d2b48fa4eDan Gohman } 404550f5afb68ce8f034991863cac65bef22a6554daDan Gohman 40554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// addPred - This adds the specified edge as a pred of the current node if 406cddd428459a66830b0d072823f94224ace58e625Dan Gohman /// not already. It also adds the current node as a successor of the 407ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman /// specified node. 408ae692f2baedf53504af2715993b166950e185a55Andrew Trick bool addPred(const SDep &D, bool Required = true); 409228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner 41054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// removePred - This removes the specified edge as a pred of the current 41154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// node if it exists. It also removes the current node as a successor of 412ffa391272bad598d73fd5404dadf3686b69f2a63Dan Gohman /// the specified node. 413c6b680eee58d27f4d38684c95e8fbfef61eb6558Dan Gohman void removePred(const SDep &D); 414a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 41589bf4f2f5e6f54fe6382f07c515e36adc9e0c9c2Dan Gohman /// getDepth - Return the depth of this node, which is the length of the 416d756eceb83fc9a7536f76adfe24cdb19d4c2f253Eric Christopher /// maximum path up to any node which has no predecessors. 417557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin unsigned getDepth() const { 4186e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick if (!isDepthCurrent) 419557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin const_cast<SUnit *>(this)->ComputeDepth(); 4203f23744df4809eba94284e601e81489212c974d4Dan Gohman return Depth; 4213f23744df4809eba94284e601e81489212c974d4Dan Gohman } 4223f23744df4809eba94284e601e81489212c974d4Dan Gohman 4233f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getHeight - Return the height of this node, which is the length of the 424d756eceb83fc9a7536f76adfe24cdb19d4c2f253Eric Christopher /// maximum path down to any node which has no successors. 425557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin unsigned getHeight() const { 4266e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick if (!isHeightCurrent) 427557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin const_cast<SUnit *>(this)->ComputeHeight(); 4283f23744df4809eba94284e601e81489212c974d4Dan Gohman return Height; 4293f23744df4809eba94284e601e81489212c974d4Dan Gohman } 4303f23744df4809eba94284e601e81489212c974d4Dan Gohman 4314de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// setDepthToAtLeast - If NewDepth is greater than this node's 4324de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// depth value, set it to be the new depth value. This also 433557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin /// recursively marks successor nodes dirty. 434557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void setDepthToAtLeast(unsigned NewDepth); 4353f23744df4809eba94284e601e81489212c974d4Dan Gohman 4364de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// setDepthToAtLeast - If NewDepth is greater than this node's 4374de099d8ca651e00fa5fac22bace4f4dba2d0292David Goodwin /// depth value, set it to be the new height value. This also 438557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin /// recursively marks predecessor nodes dirty. 439557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void setHeightToAtLeast(unsigned NewHeight); 4403f23744df4809eba94284e601e81489212c974d4Dan Gohman 4413f23744df4809eba94284e601e81489212c974d4Dan Gohman /// setDepthDirty - Set a flag in this node to indicate that its 4423f23744df4809eba94284e601e81489212c974d4Dan Gohman /// stored Depth value will require recomputation the next time 4433f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getDepth() is called. 4443f23744df4809eba94284e601e81489212c974d4Dan Gohman void setDepthDirty(); 4453f23744df4809eba94284e601e81489212c974d4Dan Gohman 4463f23744df4809eba94284e601e81489212c974d4Dan Gohman /// setHeightDirty - Set a flag in this node to indicate that its 4473f23744df4809eba94284e601e81489212c974d4Dan Gohman /// stored Height value will require recomputation the next time 4483f23744df4809eba94284e601e81489212c974d4Dan Gohman /// getHeight() is called. 4493f23744df4809eba94284e601e81489212c974d4Dan Gohman void setHeightDirty(); 4503f23744df4809eba94284e601e81489212c974d4Dan Gohman 4513f23744df4809eba94284e601e81489212c974d4Dan Gohman /// isPred - Test if node N is a predecessor of this node. 452a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng bool isPred(SUnit *N) { 45334cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = (unsigned)Preds.size(); i != e; ++i) 45454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (Preds[i].getSUnit() == N) 455a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return true; 456a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 457a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng } 4586e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 4593f23744df4809eba94284e601e81489212c974d4Dan Gohman /// isSucc - Test if node N is a successor of this node. 460a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng bool isSucc(SUnit *N) { 46134cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng for (unsigned i = 0, e = (unsigned)Succs.size(); i != e; ++i) 46254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman if (Succs[i].getSUnit() == N) 463a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return true; 464a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng return false; 465228a18e0f220fb85ee06fd5bfa29304e57047ff1Chris Lattner } 4661cc3984148be113c6e5e470f23c9ddbd37679c5fEvan Cheng 46717d35e57a585e869dc3084666abd17f173723735Andrew Trick bool isTopReady() const { 46817d35e57a585e869dc3084666abd17f173723735Andrew Trick return NumPredsLeft == 0; 46917d35e57a585e869dc3084666abd17f173723735Andrew Trick } 47017d35e57a585e869dc3084666abd17f173723735Andrew Trick bool isBottomReady() const { 47117d35e57a585e869dc3084666abd17f173723735Andrew Trick return NumSuccsLeft == 0; 47217d35e57a585e869dc3084666abd17f173723735Andrew Trick } 47317d35e57a585e869dc3084666abd17f173723735Andrew Trick 47466658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick /// \brief Order this node's predecessor edges such that the critical path 47566658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick /// edge occurs first. 47666658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick void biasCriticalPath(); 47766658dd9a1ffe00a5f6e0afca7afb16ec6704ed3Andrew Trick 4783cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman void dump(const ScheduleDAG *G) const; 4793cc6243ddfdba3ad64035b919c88b09773a60880Dan Gohman void dumpAll(const ScheduleDAG *G) const; 480252ae9e8ae4efaf1f67a608ad2563323308bd803Dan Gohman void print(raw_ostream &O, const ScheduleDAG *G) const; 4813f23744df4809eba94284e601e81489212c974d4Dan Gohman 4823f23744df4809eba94284e601e81489212c974d4Dan Gohman private: 483557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void ComputeDepth(); 484557bbe6b5d13faaec38f85a266db457c7cb09ff2David Goodwin void ComputeHeight(); 485e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 486e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 487e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng //===--------------------------------------------------------------------===// 488e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// SchedulingPriorityQueue - This interface is used to plug different 489e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// priorities computation algorithms into the list scheduler. It implements 4906e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// the interface of a standard priority queue, where nodes are inserted in 491e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// arbitrary order and returned in priority order. The computation of the 492e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// priority and the representation of the queue are totally up to the 493e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng /// implementation to decide. 4946e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// 495e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng class SchedulingPriorityQueue { 4962d24e2a396a1d211baaeedf32148a3b657240170David Blaikie virtual void anchor(); 49715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned CurCycle; 4982da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick bool HasReadyFilter; 499e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng public: 5002da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick SchedulingPriorityQueue(bool rf = false): 5012da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick CurCycle(0), HasReadyFilter(rf) {} 502e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual ~SchedulingPriorityQueue() {} 5036e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 5042da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick virtual bool isBottomUp() const = 0; 5052da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 50694d7a5f8156e62532870fbaf197377b34e52ff2aDan Gohman virtual void initNodes(std::vector<SUnit> &SUnits) = 0; 507a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void addNode(const SUnit *SU) = 0; 508a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void updateNode(const SUnit *SU) = 0; 509e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual void releaseState() = 0; 510a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 511e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual bool empty() const = 0; 5122da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 5132da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick bool hasReadyFilter() const { return HasReadyFilter; } 5142da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 51592e946630d5f9bb092853b93501387dd216899b9Andrew Trick virtual bool tracksRegPressure() const { return false; } 51692e946630d5f9bb092853b93501387dd216899b9Andrew Trick 5177853ae1d97acb65bd4dfd9a15478c14f475dbd41Eric Christopher virtual bool isReady(SUnit *) const { 5182da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick assert(!HasReadyFilter && "The ready filter must override isReady()"); 5192da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick return true; 5202da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 521e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual void push(SUnit *U) = 0; 5226e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 523a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman void push_all(const std::vector<SUnit *> &Nodes) { 524a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman for (std::vector<SUnit *>::const_iterator I = Nodes.begin(), 525a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman E = Nodes.end(); I != E; ++I) 526a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman push(*I); 527a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman } 528a4e4ffd389497eb28f5fe91521fb71da4340e5d6Dan Gohman 529e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng virtual SUnit *pop() = 0; 530e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 531a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng virtual void remove(SUnit *SU) = 0; 532a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 5337853ae1d97acb65bd4dfd9a15478c14f475dbd41Eric Christopher virtual void dump(ScheduleDAG *) const {} 5342da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 535953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick /// scheduledNode - As each node is scheduled, this method is invoked. This 536a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// allows the priority function to adjust the priority of related 537a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// unscheduled nodes, for example. 538a0b50d7f0dd965b4269cce198cab395e2c2be900Dan Gohman /// 539953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void scheduledNode(SUnit *) {} 540a6fb1b6743ee1411accf2d6e636f73f2ee0a7f5bEvan Cheng 541953be893e8cffa0ef9bf410036cd96aeb526e98aAndrew Trick virtual void unscheduledNode(SUnit *) {} 54215a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 54315a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng void setCurCycle(unsigned Cycle) { 54415a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng CurCycle = Cycle; 54515a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng } 54615a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng 54715a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng unsigned getCurCycle() const { 54815a16def6e70c8f7df1023da80ceb89887203b40Evan Cheng return CurCycle; 5496e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick } 550e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng }; 551e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng 552a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng class ScheduleDAG { 553a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng public: 554a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng const TargetMachine &TM; // Target processor 555a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng const TargetInstrInfo *TII; // Target instruction information 5566f0d024a534af18d9e60b3ea757376cd8a3a980eDan Gohman const TargetRegisterInfo *TRI; // Target processor register info 55779ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman MachineFunction &MF; // Machine function 5589e23336d0c99fc5cae04037ead6d8f2b677e8764Evan Cheng MachineRegisterInfo &MRI; // Virtual/real register map 559e165a78551a91d8420cd8f074d97701e8788f8b5Evan Cheng std::vector<SUnit> SUnits; // The scheduling units. 5609e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit EntrySU; // Special node for the region entry. 5619e64bbb322417c09f27afdf08e3946287c9df5aaDan Gohman SUnit ExitSU; // Special node for the region exit. 562a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 5634cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#ifdef NDEBUG 5644cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick static const bool StressSched = false; 5654cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#else 5664cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick bool StressSched; 5674cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick#endif 5684cb971ce1c8b254f29365c988b55f6dcfe86d21eAndrew Trick 56979ce276083ced01256a0eb7d80731e4948ca6e87Dan Gohman explicit ScheduleDAG(MachineFunction &mf); 570cccf1232a69e2d78516c61a97e7bfa26acefb714Evan Cheng 571343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual ~ScheduleDAG(); 572a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 57347c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick /// clearDAG - clear the DAG state (between regions). 57447c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick void clearDAG(); 57547c144505b9be28ed22c626b3a407c11dba2fec5Andrew Trick 576e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng /// getInstrDesc - Return the MCInstrDesc of this SUnit. 5772da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick /// Return NULL for SDNodes without a machine opcode. 578e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc *getInstrDesc(const SUnit *SU) const { 5792da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick if (SU->isInstr()) return &SU->getInstr()->getDesc(); 5802da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick return getNodeDesc(SU->getNode()); 5812da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick } 5822da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick 5833e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// viewGraph - Pop up a GraphViz/gv window with the ScheduleDAG rendered 5843e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// using 'dot'. 5853e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman /// 5863084979ff27f48487c7421536144c41a36cae997Andrew Trick virtual void viewGraph(const Twine &Name, const Twine &Title); 5873084979ff27f48487c7421536144c41a36cae997Andrew Trick virtual void viewGraph(); 5886e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick 589343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual void dumpNode(const SUnit *SU) const = 0; 5907d1cd3f21d68179f4ebf4ee18fb7a0ddca9c5a37Dan Gohman 591343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// getGraphNodeLabel - Return a label for an SUnit node in a visualization 592343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// of the ScheduleDAG. 593343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman virtual std::string getGraphNodeLabel(const SUnit *SU) const = 0; 5948a50f1fcf0147d4ba959dc48066ddf281d5bc7e6Evan Cheng 59556b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick /// getDAGLabel - Return a label for the region of code covered by the DAG. 59656b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick virtual std::string getDAGName() const = 0; 59756b94c52c9bf0342106ca7d274b9bb469d5ef619Andrew Trick 598343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// addCustomGraphFeatures - Add custom features for a visualization of 599343f0c046702831a4a6aec951b6a297a23241a55Dan Gohman /// the ScheduleDAG. 600d59b083d22a01d9c48c9ea16757186ebf7c7049aDan Gohman virtual void addCustomGraphFeatures(GraphWriter<ScheduleDAG*> &) const {} 6018a50f1fcf0147d4ba959dc48066ddf281d5bc7e6Evan Cheng 602a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#ifndef NDEBUG 6034c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// VerifyScheduledDAG - Verify that all SUnits were scheduled and that 6044c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick /// their state is consistent. Return the number of scheduled SUnits. 6054c727204271067f3dbf50bd23098b2df8e1cc47aAndrew Trick unsigned VerifyScheduledDAG(bool isBottomUp); 606a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman#endif 607a1e6d363e5efa9eb1a2e7ac21a0394c870bef5adDan Gohman 6082da8bc8a5f7705ac131184cd247f48500da0d74eAndrew Trick private: 609e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng // Return the MCInstrDesc of this SDNode or NULL. 610e837dead3c8dc3445ef6a0e2322179c57e264a13Evan Cheng const MCInstrDesc *getNodeDesc(const SDNode *Node) const; 611a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng }; 612a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 6137362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif class SUnitIterator : public std::iterator<std::forward_iterator_tag, 6147362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif SUnit, ptrdiff_t> { 6153e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnit *Node; 6163e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman unsigned Operand; 6173e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6183e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator(SUnit *N, unsigned Op) : Node(N), Operand(Op) {} 6193e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman public: 6203e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman bool operator==(const SUnitIterator& x) const { 6213e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return Operand == x.Operand; 6223e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6233e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman bool operator!=(const SUnitIterator& x) const { return !operator==(x); } 6243e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6253e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman const SUnitIterator &operator=(const SUnitIterator &I) { 6267362ce08cb2c1f0b544b18dbc21630fb4baebcfcGabor Greif assert(I.Node==Node && "Cannot assign iterators to two different nodes!"); 6273e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman Operand = I.Operand; 6283e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return *this; 6293e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6303e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6313e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman pointer operator*() const { 63254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman return Node->Preds[Operand].getSUnit(); 6333e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6343e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman pointer operator->() const { return operator*(); } 6353e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6363e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator& operator++() { // Preincrement 6373e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman ++Operand; 6383e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return *this; 6393e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6403e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator operator++(int) { // Postincrement 6413e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman SUnitIterator tmp = *this; ++*this; return tmp; 6423e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6433e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6443e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static SUnitIterator begin(SUnit *N) { return SUnitIterator(N, 0); } 6453e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static SUnitIterator end (SUnit *N) { 64634cd4a484e532cc463fd5a4bf59b88d13c5467c1Evan Cheng return SUnitIterator(N, (unsigned)N->Preds.size()); 6473e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6483e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6493e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman unsigned getOperand() const { return Operand; } 6503e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman const SUnit *getNode() const { return Node; } 65154e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman /// isCtrlDep - Test if this is not an SDep::Data dependence. 65254e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isCtrlDep() const { 653c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return getSDep().isCtrl(); 65454e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 65554e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman bool isArtificialDep() const { 656c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return getSDep().isArtificial(); 657c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman } 658c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman const SDep &getSDep() const { 659c3df7a8884971e72a5f0f25c951da0007b4ea503Dan Gohman return Node->Preds[Operand]; 66054e4c36a7349e94a84773afb56eccd4ca65b49e9Dan Gohman } 6613e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 6623e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6633e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman template <> struct GraphTraits<SUnit*> { 6643e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef SUnit NodeType; 6653e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef SUnitIterator ChildIteratorType; 6663e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline NodeType *getEntryNode(SUnit *N) { return N; } 6673e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline ChildIteratorType child_begin(NodeType *N) { 6683e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return SUnitIterator::begin(N); 6693e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6703e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static inline ChildIteratorType child_end(NodeType *N) { 6713e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return SUnitIterator::end(N); 6723e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6733e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 6743e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman 6753e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman template <> struct GraphTraits<ScheduleDAG*> : public GraphTraits<SUnit*> { 6763e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman typedef std::vector<SUnit>::iterator nodes_iterator; 6773e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static nodes_iterator nodes_begin(ScheduleDAG *G) { 6783e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return G->SUnits.begin(); 6793e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6803e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman static nodes_iterator nodes_end(ScheduleDAG *G) { 6813e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman return G->SUnits.end(); 6823e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman } 6833e1a7aef17575d9c7058a035449d57e3c7295ed0Dan Gohman }; 68421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 68521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ScheduleDAGTopologicalSort is a class that computes a topological 68621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ordering for SUnits and provides methods for dynamically updating 68721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// the ordering as new edges are added. 68821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// 68921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// This allows a very fast implementation of IsReachable, for example. 69021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// 69121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman class ScheduleDAGTopologicalSort { 69221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// SUnits - A reference to the ScheduleDAG's SUnits. 69321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<SUnit> &SUnits; 694ae692f2baedf53504af2715993b166950e185a55Andrew Trick SUnit *ExitSU; 69521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 69621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Index2Node - Maps topological index to the node number. 69721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> Index2Node; 69821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Node2Index - Maps the node number to its topological index. 69921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman std::vector<int> Node2Index; 70021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Visited - a set of nodes visited during a DFS traversal. 70121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman BitVector Visited; 70221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7036e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// DFS - make a DFS traversal and mark all nodes affected by the 70421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// edge insertion. These nodes will later get new topological indexes 70521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// by means of the Shift method. 70621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void DFS(const SUnit *SU, int UpperBound, bool& HasLoop); 70721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 70821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Shift - reassign topological indexes for the nodes in the DAG 70921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// to preserve the topological ordering. 71021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void Shift(BitVector& Visited, int LowerBound, int UpperBound); 71121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 71221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// Allocate - assign the topological index to the node n. 71321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void Allocate(int n, int index); 71421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 71521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman public: 716ae692f2baedf53504af2715993b166950e185a55Andrew Trick ScheduleDAGTopologicalSort(std::vector<SUnit> &SUnits, SUnit *ExitSU); 71721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7186e8f4c404825b79f9b9176483653f1aa927dfbdeAndrew Trick /// InitDAGTopologicalSorting - create the initial topological 71921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// ordering from the DAG to be scheduled. 72021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void InitDAGTopologicalSorting(); 72121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 72221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// IsReachable - Checks if SU is reachable from TargetSU. 72321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman bool IsReachable(const SUnit *SU, const SUnit *TargetSU); 72421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 725e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick /// WillCreateCycle - Return true if addPred(TargetSU, SU) creates a cycle. 726e38afe1e335084134f7830ba6f2208e2ddde59b4Andrew Trick bool WillCreateCycle(SUnit *TargetSU, SUnit *SU); 72721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7287a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner /// AddPred - Updates the topological ordering to accommodate an edge 72921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// to be added from SUnit X to SUnit Y. 73021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void AddPred(SUnit *Y, SUnit *X); 73121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 7327a2bdde0a0eebcd2125055e0eacaca040f0b766cChris Lattner /// RemovePred - Updates the topological ordering to accommodate an 73321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// an edge to be removed from the specified node N from the predecessors 73421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman /// of the current node M. 73521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman void RemovePred(SUnit *M, SUnit *N); 73621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 73721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::iterator iterator; 73821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::const_iterator const_iterator; 73921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman iterator begin() { return Index2Node.begin(); } 74021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_iterator begin() const { return Index2Node.begin(); } 74121d9003087c9a707e6cd95460136b499df358fb8Dan Gohman iterator end() { return Index2Node.end(); } 74221d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_iterator end() const { return Index2Node.end(); } 74321d9003087c9a707e6cd95460136b499df358fb8Dan Gohman 74421d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::reverse_iterator reverse_iterator; 74521d9003087c9a707e6cd95460136b499df358fb8Dan Gohman typedef std::vector<int>::const_reverse_iterator const_reverse_iterator; 74621d9003087c9a707e6cd95460136b499df358fb8Dan Gohman reverse_iterator rbegin() { return Index2Node.rbegin(); } 74721d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_reverse_iterator rbegin() const { return Index2Node.rbegin(); } 74821d9003087c9a707e6cd95460136b499df358fb8Dan Gohman reverse_iterator rend() { return Index2Node.rend(); } 74921d9003087c9a707e6cd95460136b499df358fb8Dan Gohman const_reverse_iterator rend() const { return Index2Node.rend(); } 75021d9003087c9a707e6cd95460136b499df358fb8Dan Gohman }; 751a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng} 752a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng 753a9c2091cd38e401c846391c9951ff416e709b65eEvan Cheng#endif 754