class ScheduleDAGInstrs

Declaration

class ScheduleDAGInstrs : public ScheduleDAG { /* full declaration omitted */ };

Description

A ScheduleDAG for scheduling lists of MachineInstr.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:119

Inherits from: ScheduleDAG

Member Variables

protected const llvm::MachineLoopInfo* MLI
protected const llvm::MachineFrameInfo& MFI
protected llvm::TargetSchedModel SchedModel
TargetSchedModel provides an interface to the machine model.
protected bool RemoveKillFlags
True if the DAG builder should remove kill flags (in preparation for rescheduling).
protected bool CanHandleTerminators = false
The standard DAG builder does not normally include terminators as DAG nodes because it does not create the necessary dependencies to prevent reordering. A specialized scheduler can override TargetInstrInfo::isSchedulingBoundary then enable this flag to indicate it has taken responsibility for scheduling the terminator correctly.
protected bool TrackLaneMasks = false
Whether lane masks should get tracked.
protected llvm::MachineBasicBlock* BB
The block in which to insert instructions
protected MachineBasicBlock::iterator RegionBegin
The beginning of the range to be scheduled.
protected MachineBasicBlock::iterator RegionEnd
The end of the range to be scheduled.
protected unsigned int NumRegionInstrs
Instructions in this region (distance(RegionBegin, RegionEnd)).
protected DenseMap<llvm::MachineInstr*, llvm::SUnit*> MISUnitMap
After calling BuildSchedGraph, each machine instruction in the current scheduling region is mapped to an SUnit.
protected llvm::Reg2SUnitsMap Defs
Defs, Uses - Remember where defs and uses of each register are as we iterate upward through the instructions. This is allocated here instead of inside BuildSchedGraph to avoid the need for it to be initialized and destructed for each block.
protected llvm::Reg2SUnitsMap Uses
protected llvm::VReg2SUnitMultiMap CurrentVRegDefs
Tracks the last instruction(s) in this region defining each virtual register. There may be multiple current definitions for a register with disjunct lanemasks.
protected llvm::VReg2SUnitOperIdxMultiMap CurrentVRegUses
Tracks the last instructions in this region using each virtual register.
protected llvm::AAResults* AAForDep = nullptr
protected llvm::SUnit* BarrierChain = nullptr
Remember a generic side-effecting instruction as we proceed. No other SU ever gets scheduled around it (except in the special case of a huge region that gets reduced).
protected llvm::UndefValue* UnknownValue
For an unanalyzable memory access, this Value is used in maps.
protected llvm::ScheduleDAGTopologicalSort Topo
Topo - A topological ordering for SUnits which permits fast IsReachable and similar queries.
protected llvm::ScheduleDAGInstrs::DbgValueVector DbgValues
Remember instruction that precedes DBG_VALUE. These are generated by buildSchedGraph but persist so they can be referenced when emitting the final schedule.
protected llvm::MachineInstr* FirstDbgValue = nullptr
protected llvm::LivePhysRegs LiveRegs
Set of live physical registers for updating kill flags.

Inherited from ScheduleDAG:

public TM
public TII
public TRI
public MF
public MRI
public SUnits
public EntrySU
public ExitSU
public StressSched

Method Overview

  • public bool IsReachable(llvm::SUnit * SU, llvm::SUnit * TargetSU)
  • public ScheduleDAGInstrs(llvm::MachineFunction & mf, const llvm::MachineLoopInfo * mli, bool RemoveKillFlags = false)
  • protected void addBarrierChain(llvm::ScheduleDAGInstrs::Value2SUsMap & map)
  • protected void addChainDependencies(llvm::SUnit * SU, llvm::ScheduleDAGInstrs::SUList & SUs, unsigned int Latency)
  • protected void addChainDependencies(llvm::SUnit * SU, llvm::ScheduleDAGInstrs::Value2SUsMap & Val2SUsMap)
  • protected void addChainDependencies(llvm::SUnit * SU, llvm::ScheduleDAGInstrs::Value2SUsMap & Val2SUsMap, llvm::ValueType V)
  • protected void addChainDependency(llvm::SUnit * SUa, llvm::SUnit * SUb, unsigned int Latency = 0)
  • public bool addEdge(llvm::SUnit * SuccSU, const llvm::SDep & PredDep)
  • protected void addPhysRegDataDeps(llvm::SUnit * SU, unsigned int OperIdx)
  • protected void addPhysRegDeps(llvm::SUnit * SU, unsigned int OperIdx)
  • public void addSchedBarrierDeps()
  • protected void addVRegDefDeps(llvm::SUnit * SU, unsigned int OperIdx)
  • protected void addVRegUseDeps(llvm::SUnit * SU, unsigned int OperIdx)
  • public MachineBasicBlock::iterator begin() const
  • public void buildSchedGraph(llvm::AAResults * AA, llvm::RegPressureTracker * RPTracker = nullptr, llvm::PressureDiffs * PDiffs = nullptr, llvm::LiveIntervals * LIS = nullptr, bool TrackLaneMasks = false)
  • public bool canAddEdge(llvm::SUnit * SuccSU, llvm::SUnit * PredSU)
  • protected bool deadDefHasNoUse(const llvm::MachineOperand & MO)
  • public virtual bool doMBBSchedRegionsTopDown() const
  • public void dump() const
  • public void dumpNode(const llvm::SUnit & SU) const
  • public MachineBasicBlock::iterator end() const
  • public virtual void enterRegion(llvm::MachineBasicBlock * bb, MachineBasicBlock::iterator begin, MachineBasicBlock::iterator end, unsigned int regioninstrs)
  • public virtual void exitRegion()
  • public virtual void finalizeSchedule()
  • public virtual void finishBlock()
  • public void fixupKills(llvm::MachineBasicBlock & MBB)
  • public std::string getDAGName() const
  • public std::string getGraphNodeLabel(const llvm::SUnit * SU) const
  • protected llvm::LaneBitmask getLaneMaskForMO(const llvm::MachineOperand & MO) const
  • public llvm::SUnit * getSUnit(llvm::MachineInstr * MI) const
  • public const llvm::MCSchedClassDesc * getSchedClass(llvm::SUnit * SU) const
  • public const llvm::TargetSchedModel * getSchedModel() const
  • protected void initSUnits()
  • protected void insertBarrierChain(llvm::ScheduleDAGInstrs::Value2SUsMap & map)
  • public llvm::SUnit * newSUnit(llvm::MachineInstr * MI)
  • protected void reduceHugeMemNodeMaps(llvm::ScheduleDAGInstrs::Value2SUsMap & stores, llvm::ScheduleDAGInstrs::Value2SUsMap & loads, unsigned int N)
  • public virtual void schedule()
  • public virtual void startBlock(llvm::MachineBasicBlock * BB)
  • public ~ScheduleDAGInstrs()

Inherited from ScheduleDAG:

Methods

bool IsReachable(llvm::SUnit* SU,
                 llvm::SUnit* TargetSU)

Description

IsReachable - Checks if SU is reachable from TargetSU.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:272

Parameters

llvm::SUnit* SU
llvm::SUnit* TargetSU

ScheduleDAGInstrs(
    llvm::MachineFunction& mf,
    const llvm::MachineLoopInfo* mli,
    bool RemoveKillFlags = false)

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:255

Parameters

llvm::MachineFunction& mf
const llvm::MachineLoopInfo* mli
bool RemoveKillFlags = false

void addBarrierChain(
    llvm::ScheduleDAGInstrs::Value2SUsMap& map)

Description

Adds barrier chain edges from all SUs in map, and then clear the map. This is equivalent to insertBarrierChain(), but optimized for the common case where the new BarrierChain (a global memory object) has a higher NodeNum than all SUs in map. It is assumed BarrierChain has been set before calling this.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:227

Parameters

llvm::ScheduleDAGInstrs::Value2SUsMap& map

void addChainDependencies(
    llvm::SUnit* SU,
    llvm::ScheduleDAGInstrs::SUList& SUs,
    unsigned int Latency)

Description

Adds dependencies as needed from all SUs in list to SU.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:210

Parameters

llvm::SUnit* SU
llvm::ScheduleDAGInstrs::SUList& SUs
unsigned int Latency

void addChainDependencies(
    llvm::SUnit* SU,
    llvm::ScheduleDAGInstrs::Value2SUsMap&
        Val2SUsMap)

Description

Adds dependencies as needed from all SUs in map, to SU.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:216

Parameters

llvm::SUnit* SU
llvm::ScheduleDAGInstrs::Value2SUsMap& Val2SUsMap

void addChainDependencies(
    llvm::SUnit* SU,
    llvm::ScheduleDAGInstrs::Value2SUsMap&
        Val2SUsMap,
    llvm::ValueType V)

Description

Adds dependencies as needed to SU, from all SUs mapped to V.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:219

Parameters

llvm::SUnit* SU
llvm::ScheduleDAGInstrs::Value2SUsMap& Val2SUsMap
llvm::ValueType V

void addChainDependency(llvm::SUnit* SUa,
                        llvm::SUnit* SUb,
                        unsigned int Latency = 0)

Description

Adds a chain edge between SUa and SUb, but only if both AAResults and Target fail to deny the dependency.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:206

Parameters

llvm::SUnit* SUa
llvm::SUnit* SUb
unsigned int Latency = 0

bool addEdge(llvm::SUnit* SuccSU,
             const llvm::SDep& PredDep)

Description

Add a DAG edge to the given SU with the given predecessor dependence data.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:361

Parameters

llvm::SUnit* SuccSU
const llvm::SDep& PredDep

Returns

true if the edge may be added without creating a cycle OR if an equivalent edge already existed (false indicates failure).

void addPhysRegDataDeps(llvm::SUnit* SU,
                        unsigned int OperIdx)

Description

MO is an operand of SU's instruction that defines a physical register. Adds data dependencies from SU to any uses of the physical register.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:365

Parameters

llvm::SUnit* SU
unsigned int OperIdx

void addPhysRegDeps(llvm::SUnit* SU,
                    unsigned int OperIdx)

Description

Adds register dependencies (data, anti, and output) from this SUnit to following instructions in the same scheduling region that depend the physical register referenced at OperIdx.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:366

Parameters

llvm::SUnit* SU
unsigned int OperIdx

void addSchedBarrierDeps()

Description

Adds dependencies from instructions in the current list of instructions being scheduled to scheduling barrier. We want to make sure instructions which define registers that are either used by the terminator or are live-out are properly scheduled. This is especially important when the definition latency of the return value(s) are too high to be hidden by the branch or when the liveout registers used by instructions in the fallthrough block.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:328

void addVRegDefDeps(llvm::SUnit* SU,
                    unsigned int OperIdx)

Description

Adds register output and data dependencies from this SUnit to instructions that occur later in the same scheduling region if they read from or write to the virtual register defined at OperIdx. TODO: Hoist loop induction variable increments. This has to be reevaluated. Generally, IV scheduling should be done before coalescing.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:367

Parameters

llvm::SUnit* SU
unsigned int OperIdx

void addVRegUseDeps(llvm::SUnit* SU,
                    unsigned int OperIdx)

Description

Adds a register data dependency if the instruction that defines the virtual register used at OperIdx is mapped to an SUnit. Add a register antidependency from this SUnit to instructions that occur later in the same scheduling region if they write the virtual register. TODO: Handle ExitSU "uses" properly.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:368

Parameters

llvm::SUnit* SU
unsigned int OperIdx

MachineBasicBlock::iterator begin() const

Description

Returns an iterator to the top of the current scheduling region.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:277

void buildSchedGraph(
    llvm::AAResults* AA,
    llvm::RegPressureTracker* RPTracker = nullptr,
    llvm::PressureDiffs* PDiffs = nullptr,
    llvm::LiveIntervals* LIS = nullptr,
    bool TrackLaneMasks = false)

Description

Builds SUnits for the current region. If \p RPTracker is non-null, compute register pressure as a side effect. The DAG builder is an efficient place to do it because it already visits operands.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:315

Parameters

llvm::AAResults* AA
llvm::RegPressureTracker* RPTracker = nullptr
llvm::PressureDiffs* PDiffs = nullptr
llvm::LiveIntervals* LIS = nullptr
bool TrackLaneMasks = false

bool canAddEdge(llvm::SUnit* SuccSU,
                llvm::SUnit* PredSU)

Description

True if an edge can be added from PredSU to SuccSU without creating a cycle.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:354

Parameters

llvm::SUnit* SuccSU
llvm::SUnit* PredSU

bool deadDefHasNoUse(
    const llvm::MachineOperand& MO)

Description

Returns true if the def register in \p MO has no uses.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:375

Parameters

const llvm::MachineOperand& MO

virtual bool doMBBSchedRegionsTopDown() const

Description

If this method returns true, handling of the scheduling regions themselves (in case of a scheduling boundary in MBB) will be done beginning with the topmost region of MBB.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:291

void dump() const

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:341

void dumpNode(const llvm::SUnit& SU) const

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:340

Parameters

const llvm::SUnit& SU

MachineBasicBlock::iterator end() const

Description

Returns an iterator to the bottom of the current scheduling region.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:280

virtual void enterRegion(
    llvm::MachineBasicBlock* bb,
    MachineBasicBlock::iterator begin,
    MachineBasicBlock::iterator end,
    unsigned int regioninstrs)

Description

Initialize the DAG and common scheduler state for a new scheduling region. This does not actually create the DAG, only clears it. The scheduling driver may call BuildSchedGraph multiple times per scheduling region.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:303

Parameters

llvm::MachineBasicBlock* bb
MachineBasicBlock::iterator begin
MachineBasicBlock::iterator end
unsigned int regioninstrs

virtual void exitRegion()

Description

Called when the scheduler has finished scheduling the current region.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:309

virtual void finalizeSchedule()

Description

Allow targets to perform final scheduling actions at the level of the whole MachineFunction. By default does nothing.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:338

virtual void finishBlock()

Description

Cleans up after scheduling in the given block.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:297

void fixupKills(llvm::MachineBasicBlock& MBB)

Description

Fixes register kill flags that scheduling has made invalid.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:350

Parameters

llvm::MachineBasicBlock& MBB

std::string getDAGName() const

Description

Returns a label for the region of code covered by the DAG.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:347

std::string getGraphNodeLabel(
    const llvm::SUnit* SU) const

Description

Returns a label for a DAG node that points to an instruction.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:344

Parameters

const llvm::SUnit* SU

llvm::LaneBitmask getLaneMaskForMO(
    const llvm::MachineOperand& MO) const

Description

Returns a mask for which lanes get read/written by the given (register) machine operand.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:372

Parameters

const llvm::MachineOperand& MO

llvm::SUnit* getSUnit(
    llvm::MachineInstr* MI) const

Description

Returns an existing SUnit for this MI, or nullptr.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:286

Parameters

llvm::MachineInstr* MI

const llvm::MCSchedClassDesc* getSchedClass(
    llvm::SUnit* SU) const

Description

Resolves and cache a resolved scheduling class for an SUnit.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:265

Parameters

llvm::SUnit* SU

const llvm::TargetSchedModel* getSchedModel()
    const

Description

Gets the machine model for instruction scheduling.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:262

void initSUnits()

Description

Creates an SUnit for each real instruction, numbered in top-down topological order. The instruction order A < B, implies that no edge exists from B to A. Map each real instruction to its SUnit. After initSUnits, the SUnits vector cannot be resized and the scheduler may hang onto SUnit pointers. We may relax this in the future by using SUnit IDs instead of pointers. MachineScheduler relies on initSUnits numbering the nodes by their order in the original instruction list.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:364

void insertBarrierChain(
    llvm::ScheduleDAGInstrs::Value2SUsMap& map)

Description

Inserts a barrier chain in a huge region, far below current SU. Adds barrier chain edges from all SUs in map with higher NodeNums than this new BarrierChain, and remove them from map. It is assumed BarrierChain has been set before calling this.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:233

Parameters

llvm::ScheduleDAGInstrs::Value2SUsMap& map

llvm::SUnit* newSUnit(llvm::MachineInstr* MI)

Description

Creates a new SUnit and return a ptr to it.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:283

Parameters

llvm::MachineInstr* MI

void reduceHugeMemNodeMaps(
    llvm::ScheduleDAGInstrs::Value2SUsMap& stores,
    llvm::ScheduleDAGInstrs::Value2SUsMap& loads,
    unsigned int N)

Description

Reduces maps in FIFO order, by N SUs. This is better than turning every Nth memory SU into BarrierChain in buildSchedGraph(), since it avoids unnecessary edges between seen SUs above the new BarrierChain, and those below it.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:201

Parameters

llvm::ScheduleDAGInstrs::Value2SUsMap& stores
llvm::ScheduleDAGInstrs::Value2SUsMap& loads
unsigned int N

virtual void schedule()

Description

Orders nodes according to selected style. Typically, a scheduling algorithm will implement schedule() without overriding enterRegion() or exitRegion().

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:334

virtual void startBlock(
    llvm::MachineBasicBlock* BB)

Description

Prepares to perform scheduling in the given block.

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:294

Parameters

llvm::MachineBasicBlock* BB

~ScheduleDAGInstrs()

Declared at: llvm/include/llvm/CodeGen/ScheduleDAGInstrs.h:259