class SwingSchedulerDAG

Declaration

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

Description

This class builds the dependence graph for the instructions in a loop, and attempts to schedule the instructions using the SMS algorithm.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:112

Inherits from: ScheduleDAGInstrs

Member Variables

private llvm::MachinePipeliner& Pass
private unsigned int MII = 0
The minimum initiation interval between iterations for this schedule.
private unsigned int MAX_II = 0
The maximum initiation interval between iterations for this schedule.
private bool Scheduled = false
Set to true if a valid pipelined schedule is found for the loop.
private llvm::MachineLoop& Loop
private llvm::LiveIntervals& LIS
private const llvm::RegisterClassInfo& RegClassInfo
private unsigned int II_setByPragma = 0
private TargetInstrInfo::PipelinerLoopInfo* LoopPipelinerInfo = nullptr
private llvm::ScheduleDAGTopologicalSort Topo
A toplogical ordering of the SUnits, which is needed for changing dependences and iterating over the SUnits.
private std::vector<NodeInfo> ScheduleInfo
Computed properties for each node in the graph.
private SetVector<llvm::SUnit*> NodeOrder
Computed node ordering for scheduling.
private DenseMap<llvm::SUnit*, std::pair<unsigned int, int64_t>> InstrChanges
Instructions to change when emitting the final schedule.
private DenseMap<llvm::MachineInstr*, llvm::MachineInstr*> NewMIs
We may create a new instruction, so remember it because it must be deleted when the pass is finished.
private std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations
Ordered list of DAG postprocessing steps.

Inherited from ScheduleDAGInstrs:

protected MLI
protected MFI
protected SchedModel
protected RemoveKillFlags
protected CanHandleTerminators = false
protected TrackLaneMasks = false
protected BB
protected RegionBegin
protected RegionEnd
protected NumRegionInstrs
protected MISUnitMap
protected Defs
protected Uses
protected CurrentVRegDefs
protected CurrentVRegUses
protected AAForDep = nullptr
protected BarrierChain = nullptr
protected UnknownValue
protected Topo
protected DbgValues
protected FirstDbgValue = nullptr
protected LiveRegs

Inherited from ScheduleDAG:

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

Method Overview

Inherited from ScheduleDAGInstrs:

Inherited from ScheduleDAG:

Methods

SwingSchedulerDAG(
    llvm::MachinePipeliner& P,
    llvm::MachineLoop& L,
    llvm::LiveIntervals& lis,
    const llvm::RegisterClassInfo& rci,
    unsigned int II,
    TargetInstrInfo::PipelinerLoopInfo* PLI)

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

Parameters

llvm::MachinePipeliner& P
llvm::MachineLoop& L
llvm::LiveIntervals& lis
const llvm::RegisterClassInfo& rci
unsigned int II
TargetInstrInfo::PipelinerLoopInfo* PLI

void addConnectedNodes(
    llvm::SUnit* SU,
    llvm::NodeSet& NewSet,
    SetVector<llvm::SUnit*>& NodesAdded)

Description

Add the node to the set, and add all of its connected nodes to the set.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:301

Parameters

llvm::SUnit* SU
llvm::NodeSet& NewSet
SetVector<llvm::SUnit*>& NodesAdded

void addLoopCarriedDependences(
    llvm::AAResults* AA)

Description

Add a chain edge between a load and store if the store can be an alias of the load on a subsequent iteration, i.e., a loop carried dependence. This code is very similar to the code in ScheduleDAGInstrs but that code doesn't create loop carried dependences.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:288

Parameters

llvm::AAResults* AA

void addMutation(
    std::unique_ptr<ScheduleDAGMutation> Mutation)

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:281

Parameters

std::unique_ptr<ScheduleDAGMutation> Mutation

void applyInstrChange(llvm::MachineInstr* MI,
                      llvm::SMSchedule& Schedule)

Description

Apply changes to the instruction if needed. The changes are need to improve the scheduling and depend up on the final schedule.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:267

Parameters

llvm::MachineInstr* MI
llvm::SMSchedule& Schedule

unsigned int calculateRecMII(
    llvm::SwingSchedulerDAG::NodeSetType&
        RecNodeSets)

Description

Calculate the recurrence-constrainted minimum initiation interval. Iterate over each circuit. Compute the delay(c) and distance(c) for each circuit. The II needs to satisfy the inequality delay(c) - II*distance(c) < = 0. For each circuit, choose the smallest II that satisfies the inequality, and the RecMII is the maximum of those values.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:292

Parameters

llvm::SwingSchedulerDAG::NodeSetType& RecNodeSets

unsigned int calculateResMII()

Description

Calculate the resource constrained minimum initiation interval for the specified loop. We use the DFA to model the resources needed for each instruction, and we ignore dependences. A different DFA is created for each cycle that is required. When adding a new instruction, we attempt to add it to each existing DFA, until a legal space is found. If the instruction cannot be reserved in an existing DFA, we create a new one.

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

bool canUseLastOffsetValue(
    llvm::MachineInstr* MI,
    unsigned int& BasePos,
    unsigned int& OffsetPos,
    unsigned int& NewBase,
    int64_t& NewOffset)

Description

Check if we can change the instruction to use an offset value from the previous iteration. If so, return true and set the base and offset values so that we can rewrite the load, if necessary. v1 = Phi(v0, v3) v2 = load v1, 0 v3 = post_store v1, 4, x This function enables the load to be rewritten as v2 = load v3, 4.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:308

Parameters

llvm::MachineInstr* MI
unsigned int& BasePos
unsigned int& OffsetPos
unsigned int& NewBase
int64_t& NewOffset

void changeDependences()

Description

Iterate over each DAG node and see if we can change any dependences in order to reduce the recurrence MII.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:290

void checkNodeSets(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

Check if the existing node-sets are profitable. If not, then ignore the recurrent node-sets, and attempt to schedule all nodes together. This is a heuristic. If the MII is large and all the recurrent node-sets are small, then it's best to try to schedule all instructions together instead of starting with the recurrent node-sets.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:299

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

void checkValidNodeOrder(
    const llvm::SwingSchedulerDAG::NodeSetType&
        Circuits) const

Description

A property of the node order in swing-modulo-scheduling is that for nodes outside circuits the following holds: none of them is scheduled after both a successor and a predecessor. The method below checks whether the property is met. If not, debug information is printed and statistics information updated. Note that we do not use an assert statement. The reason is that although an invalid node oder may prevent the pipeliner from finding a pipelined schedule for arbitrary II, it does not lead to the generation of incorrect code.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:304

Parameters

const llvm::SwingSchedulerDAG::NodeSetType& Circuits

static bool classof(
    const llvm::ScheduleDAGInstrs* DAG)

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:285

Parameters

const llvm::ScheduleDAGInstrs* DAG

void colocateNodeSets(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

A heuristic to colocate node sets that have the same set of successors.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:298

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

bool computeDelta(llvm::MachineInstr& MI,
                  unsigned int& Delta)

Description

Return true if we can compute the amount the instruction changes during each iteration. Set Delta to the amount of the change.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:306

Parameters

llvm::MachineInstr& MI
unsigned int& Delta

void computeNodeFunctions(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

Compute several functions need to order the nodes for scheduling. ASAP - Earliest time to schedule a node. ALAP - Latest time to schedule a node. MOV - Mobility function, difference between ALAP and ASAP. D - Depth of each node. H - Height of each node.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:296

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

void computeNodeOrder(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

Compute an ordered list of the dependence graph nodes, which indicates the order that the nodes will be scheduled. This is a two-level algorithm. First, a partial order is created, which consists of a list of sets ordered from highest to lowest priority.

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

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

void findCircuits(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

Identify all the elementary circuits in the dependence graph using Johnson's circuit algorithm.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:293

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

llvm::MachineInstr* findDefInLoop(
    llvm::Register Reg)

Description

Return the instruction in the loop that defines the register. If the definition is a Phi, then follow the Phi operand to the instruction in the loop.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:307

Parameters

llvm::Register Reg

void finishBlock()

Description

Clean up after the software pipeliner runs.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:213

void fixupRegisterOverlaps(
    std::deque<SUnit*>& Instrs)

Description

Attempt to fix the degenerate cases when the instruction serialization causes the register lifetimes to overlap. For example, p' = store_pi(p, b) = load p, offset In this case p and p' overlap, which means that two registers are needed. Instead, this function changes the load to use p' and updates the offset.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:269

Parameters

std::deque<SUnit*>& Instrs

void fuseRecs(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

Merge the recurrence node sets that have the same initial node.

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

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

int getALAP(llvm::SUnit* Node)

Description

Return the latest time an instruction my be scheduled.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:222

Parameters

llvm::SUnit* Node

int getASAP(llvm::SUnit* Node)

Description

Return the earliest time an instruction may be scheduled.

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

Parameters

llvm::SUnit* Node

unsigned int getDepth(llvm::SUnit* Node)

Description

The depth, in the dependence graph, for a node.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:229

Parameters

llvm::SUnit* Node

unsigned int getDistance(llvm::SUnit* U,
                         llvm::SUnit* V,
                         const llvm::SDep& Dep)

Description

The distance function, which indicates that operation V of iteration I depends on operations U of iteration I-distance.

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

Parameters

llvm::SUnit* U
llvm::SUnit* V
const llvm::SDep& Dep

unsigned int getHeight(llvm::SUnit* Node)

Description

The height, in the dependence graph, for a node.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:238

Parameters

llvm::SUnit* Node

unsigned int getInstrBaseReg(llvm::SUnit* SU)

Description

Return the new base register that was stored away for the changed instruction.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:273

Parameters

llvm::SUnit* SU

int getMOV(llvm::SUnit* Node)

Description

The mobility function, which the number of slots in which an instruction may be scheduled.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:226

Parameters

llvm::SUnit* Node

int getZeroLatencyDepth(llvm::SUnit* Node)

Description

The maximum unweighted length of a path from an arbitrary node to the given node in which each edge has latency 0

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

Parameters

llvm::SUnit* Node

int getZeroLatencyHeight(llvm::SUnit* Node)

Description

The maximum unweighted length of a path from the given node to an arbitrary node in which each edge has latency 0

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:242

Parameters

llvm::SUnit* Node

void groupRemainingNodes(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

Add the nodes that do not belong to a recurrence set into groups based upon connected components.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:300

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

bool hasNewSchedule()

Description

Return true if the loop kernel has been scheduled.

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

bool isBackedge(llvm::SUnit* Source,
                const llvm::SDep& Dep)

Description

Return true if the dependence is a back-edge in the data dependence graph. Since the DAG doesn't contain cycles, we represent a cycle in the graph using an anti dependence from a Phi to an instruction.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:249

Parameters

llvm::SUnit* Source
const llvm::SDep& Dep

bool isLoopCarriedDep(llvm::SUnit* Source,
                      const llvm::SDep& Dep,
                      bool isSucc = true)

Description

Return true for an order or output dependence that is loop carried potentially. A dependence is loop carried if the destination defines a valu that may be used or defined by the source in a subsequent iteration.

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

Parameters

llvm::SUnit* Source
const llvm::SDep& Dep
bool isSucc = true

void postprocessDAG()

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:311

void registerPressureFilter(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

A heuristic to filter nodes in recurrent node-sets if the register pressure of a set is too high.

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

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

void removeDuplicateNodes(
    llvm::SwingSchedulerDAG::NodeSetType&
        NodeSets)

Description

Remove nodes that have been scheduled in previous NodeSets.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:295

Parameters

llvm::SwingSchedulerDAG::NodeSetType& NodeSets

void schedule()

Description

We override the schedule function in ScheduleDAGInstrs to implement the scheduling part of the Swing Modulo Scheduling algorithm.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:212

bool schedulePipeline(llvm::SMSchedule& Schedule)

Description

Process the nodes in the computed order and create the pipelined schedule of the instructions, if possible. Return true if a schedule is found.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:305

Parameters

llvm::SMSchedule& Schedule

void setMAX_II()

Description

Set the Maximum Initiation Interval for this schedule attempt.

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

void setMII(unsigned int ResMII,
            unsigned int RecMII)

Description

Set the Minimum Initiation Interval for this schedule attempt.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:313

Parameters

unsigned int ResMII
unsigned int RecMII

void updatePhiDependences()

Description

Update the phi dependences to the DAG because ScheduleDAGInstrs no longer processes dependences for PHIs. This function adds true dependences from a PHI to a use, and a loop carried dependence from the use to the PHI. The loop carried dependence is represented as an anti dependence edge. This function also removes chain dependences between unrelated PHIs.

Declared at: llvm/include/llvm/CodeGen/MachinePipeliner.h:289