Google Git
Sign in
cobalt / cobalt / ac9ac065c5083565917b15e7a672a79599f2f00b / . / src / third_party / llvm-project / llvm / lib / CodeGen / MachinePipeliner.cpp
blob: 9bb00aaef86de950f158c72c04b9f10ddfa85f5f [file] [log] [blame]
//===- MachinePipeliner.cpp - Machine Software Pipeliner Pass -------------===//
//
// The LLVM Compiler Infrastructure
//
// This file is distributed under the University of Illinois Open Source
// License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
//
// Software pipelining (SWP) is an instruction scheduling technique for loops
// that overlap loop iterations and exploits ILP via a compiler transformation.
//
// Swing Modulo Scheduling is an implementation of software pipelining
// that generates schedules that are near optimal in terms of initiation
// interval, register requirements, and stage count. See the papers:
//
// "Swing Modulo Scheduling: A Lifetime-Sensitive Approach", by J. Llosa,
// A. Gonzalez, E. Ayguade, and M. Valero. In PACT '96 Proceedings of the 1996
// Conference on Parallel Architectures and Compilation Techiniques.
//
// "Lifetime-Sensitive Modulo Scheduling in a Production Environment", by J.
// Llosa, E. Ayguade, A. Gonzalez, M. Valero, and J. Eckhardt. In IEEE
// Transactions on Computers, Vol. 50, No. 3, 2001.
//
// "An Implementation of Swing Modulo Scheduling With Extensions for
// Superblocks", by T. Lattner, Master's Thesis, University of Illinois at
// Urbana-Chambpain, 2005.
//
//
// The SMS algorithm consists of three main steps after computing the minimal
// initiation interval (MII).
// 1) Analyze the dependence graph and compute information about each
// instruction in the graph.
// 2) Order the nodes (instructions) by priority based upon the heuristics
// described in the algorithm.
// 3) Attempt to schedule the nodes in the specified order using the MII.
//
// This SMS implementation is a target-independent back-end pass. When enabled,
// the pass runs just prior to the register allocation pass, while the machine
// IR is in SSA form. If software pipelining is successful, then the original
// loop is replaced by the optimized loop. The optimized loop contains one or
// more prolog blocks, the pipelined kernel, and one or more epilog blocks. If
// the instructions cannot be scheduled in a given MII, we increase the MII by
// one and try again.
//
// The SMS implementation is an extension of the ScheduleDAGInstrs class. We
// represent loop carried dependences in the DAG as order edges to the Phi
// nodes. We also perform several passes over the DAG to eliminate unnecessary
// edges that inhibit the ability to pipeline. The implementation uses the
// DFAPacketizer class to compute the minimum initiation interval and the check
// where an instruction may be inserted in the pipelined schedule.
//
// In order for the SMS pass to work, several target specific hooks need to be
// implemented to get information about the loop structure and to rewrite
// instructions.
//
//===----------------------------------------------------------------------===//
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/MapVector.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/SetVector.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/SmallSet.h"
#include "llvm/ADT/SmallVector.h"
#include "llvm/ADT/Statistic.h"
#include "llvm/ADT/iterator_range.h"
#include "llvm/Analysis/AliasAnalysis.h"
#include "llvm/Analysis/MemoryLocation.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/DFAPacketizer.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBasicBlock.h"
#include "llvm/CodeGen/MachineDominators.h"
#include "llvm/CodeGen/MachineFunction.h"
#include "llvm/CodeGen/MachineFunctionPass.h"
#include "llvm/CodeGen/MachineInstr.h"
#include "llvm/CodeGen/MachineInstrBuilder.h"
#include "llvm/CodeGen/MachineLoopInfo.h"
#include "llvm/CodeGen/MachineMemOperand.h"
#include "llvm/CodeGen/MachineOperand.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDAGInstrs.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetRegisterInfo.h"
#include "llvm/CodeGen/TargetSubtargetInfo.h"
#include "llvm/Config/llvm-config.h"
#include "llvm/IR/Attributes.h"
#include "llvm/IR/DebugLoc.h"
#include "llvm/IR/Function.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/MC/MCRegisterInfo.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/MathExtras.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <deque>
#include <functional>
#include <iterator>
#include <map>
#include <memory>
#include <tuple>
#include <utility>
#include <vector>
using namespace llvm;
#define DEBUG_TYPE "pipeliner"
STATISTIC(NumTrytoPipeline, "Number of loops that we attempt to pipeline");
STATISTIC(NumPipelined, "Number of loops software pipelined");
STATISTIC(NumNodeOrderIssues, "Number of node order issues found");
/// A command line option to turn software pipelining on or off.
static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true),
cl::ZeroOrMore,
cl::desc("Enable Software Pipelining"));
/// A command line option to enable SWP at -Os.
static cl::opt<bool> EnableSWPOptSize("enable-pipeliner-opt-size",
cl::desc("Enable SWP at Os."), cl::Hidden,
cl::init(false));
/// A command line argument to limit minimum initial interval for pipelining.
static cl::opt<int> SwpMaxMii("pipeliner-max-mii",
cl::desc("Size limit for the MII."),
cl::Hidden, cl::init(27));
/// A command line argument to limit the number of stages in the pipeline.
static cl::opt<int>
SwpMaxStages("pipeliner-max-stages",
cl::desc("Maximum stages allowed in the generated scheduled."),
cl::Hidden, cl::init(3));
/// A command line option to disable the pruning of chain dependences due to
/// an unrelated Phi.
static cl::opt<bool>
SwpPruneDeps("pipeliner-prune-deps",
cl::desc("Prune dependences between unrelated Phi nodes."),
cl::Hidden, cl::init(true));
/// A command line option to disable the pruning of loop carried order
/// dependences.
static cl::opt<bool>
SwpPruneLoopCarried("pipeliner-prune-loop-carried",
cl::desc("Prune loop carried order dependences."),
cl::Hidden, cl::init(true));
#ifndef NDEBUG
static cl::opt<int> SwpLoopLimit("pipeliner-max", cl::Hidden, cl::init(-1));
#endif
static cl::opt<bool> SwpIgnoreRecMII("pipeliner-ignore-recmii",
cl::ReallyHidden, cl::init(false),
cl::ZeroOrMore, cl::desc("Ignore RecMII"));
namespace {
class NodeSet;
class SMSchedule;
/// The main class in the implementation of the target independent
/// software pipeliner pass.
class MachinePipeliner : public MachineFunctionPass {
public:
MachineFunction *MF = nullptr;
const MachineLoopInfo *MLI = nullptr;
const MachineDominatorTree *MDT = nullptr;
const InstrItineraryData *InstrItins;
const TargetInstrInfo *TII = nullptr;
RegisterClassInfo RegClassInfo;
#ifndef NDEBUG
static int NumTries;
#endif
/// Cache the target analysis information about the loop.
struct LoopInfo {
MachineBasicBlock *TBB = nullptr;
MachineBasicBlock *FBB = nullptr;
SmallVector<MachineOperand, 4> BrCond;
MachineInstr *LoopInductionVar = nullptr;
MachineInstr *LoopCompare = nullptr;
};
LoopInfo LI;
static char ID;
MachinePipeliner() : MachineFunctionPass(ID) {
initializeMachinePipelinerPass(*PassRegistry::getPassRegistry());
}
bool runOnMachineFunction(MachineFunction &MF) override;
void getAnalysisUsage(AnalysisUsage &AU) const override {
AU.addRequired<AAResultsWrapperPass>();
AU.addPreserved<AAResultsWrapperPass>();
AU.addRequired<MachineLoopInfo>();
AU.addRequired<MachineDominatorTree>();
AU.addRequired<LiveIntervals>();
MachineFunctionPass::getAnalysisUsage(AU);
}
private:
void preprocessPhiNodes(MachineBasicBlock &B);
bool canPipelineLoop(MachineLoop &L);
bool scheduleLoop(MachineLoop &L);
bool swingModuloScheduler(MachineLoop &L);
};
/// This class builds the dependence graph for the instructions in a loop,
/// and attempts to schedule the instructions using the SMS algorithm.
class SwingSchedulerDAG : public ScheduleDAGInstrs {
MachinePipeliner &Pass;
/// The minimum initiation interval between iterations for this schedule.
unsigned MII = 0;
/// Set to true if a valid pipelined schedule is found for the loop.
bool Scheduled = false;
MachineLoop &Loop;
LiveIntervals &LIS;
const RegisterClassInfo &RegClassInfo;
/// A toplogical ordering of the SUnits, which is needed for changing
/// dependences and iterating over the SUnits.
ScheduleDAGTopologicalSort Topo;
struct NodeInfo {
int ASAP = 0;
int ALAP = 0;
int ZeroLatencyDepth = 0;
int ZeroLatencyHeight = 0;
NodeInfo() = default;
};
/// Computed properties for each node in the graph.
std::vector<NodeInfo> ScheduleInfo;
enum OrderKind { BottomUp = 0, TopDown = 1 };
/// Computed node ordering for scheduling.
SetVector<SUnit *> NodeOrder;
using NodeSetType = SmallVector<NodeSet, 8>;
using ValueMapTy = DenseMap<unsigned, unsigned>;
using MBBVectorTy = SmallVectorImpl<MachineBasicBlock *>;
using InstrMapTy = DenseMap<MachineInstr *, MachineInstr *>;
/// Instructions to change when emitting the final schedule.
DenseMap<SUnit *, std::pair<unsigned, int64_t>> InstrChanges;
/// We may create a new instruction, so remember it because it
/// must be deleted when the pass is finished.
SmallPtrSet<MachineInstr *, 4> NewMIs;
/// Ordered list of DAG postprocessing steps.
std::vector<std::unique_ptr<ScheduleDAGMutation>> Mutations;
/// Helper class to implement Johnson's circuit finding algorithm.
class Circuits {
std::vector<SUnit> &SUnits;
SetVector<SUnit *> Stack;
BitVector Blocked;
SmallVector<SmallPtrSet<SUnit *, 4>, 10> B;
SmallVector<SmallVector<int, 4>, 16> AdjK;
unsigned NumPaths;
static unsigned MaxPaths;
public:
Circuits(std::vector<SUnit> &SUs)
: SUnits(SUs), Blocked(SUs.size()), B(SUs.size()), AdjK(SUs.size()) {}
/// Reset the data structures used in the circuit algorithm.
void reset() {
Stack.clear();
Blocked.reset();
B.assign(SUnits.size(), SmallPtrSet<SUnit *, 4>());
NumPaths = 0;
}
void createAdjacencyStructure(SwingSchedulerDAG *DAG);
bool circuit(int V, int S, NodeSetType &NodeSets, bool HasBackedge = false);
void unblock(int U);
};
public:
SwingSchedulerDAG(MachinePipeliner &P, MachineLoop &L, LiveIntervals &lis,
const RegisterClassInfo &rci)
: ScheduleDAGInstrs(*P.MF, P.MLI, false), Pass(P), Loop(L), LIS(lis),
RegClassInfo(rci), Topo(SUnits, &ExitSU) {
P.MF->getSubtarget().getSMSMutations(Mutations);
}
void schedule() override;
void finishBlock() override;
/// Return true if the loop kernel has been scheduled.
bool hasNewSchedule() { return Scheduled; }
/// Return the earliest time an instruction may be scheduled.
int getASAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ASAP; }
/// Return the latest time an instruction my be scheduled.
int getALAP(SUnit *Node) { return ScheduleInfo[Node->NodeNum].ALAP; }
/// The mobility function, which the number of slots in which
/// an instruction may be scheduled.
int getMOV(SUnit *Node) { return getALAP(Node) - getASAP(Node); }
/// The depth, in the dependence graph, for a node.
unsigned getDepth(SUnit *Node) { return Node->getDepth(); }
/// The maximum unweighted length of a path from an arbitrary node to the
/// given node in which each edge has latency 0
int getZeroLatencyDepth(SUnit *Node) {
return ScheduleInfo[Node->NodeNum].ZeroLatencyDepth;
}
/// The height, in the dependence graph, for a node.
unsigned getHeight(SUnit *Node) { return Node->getHeight(); }
/// The maximum unweighted length of a path from the given node to an
/// arbitrary node in which each edge has latency 0
int getZeroLatencyHeight(SUnit *Node) {
return ScheduleInfo[Node->NodeNum].ZeroLatencyHeight;
}
/// 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.
bool isBackedge(SUnit *Source, const SDep &Dep) {
if (Dep.getKind() != SDep::Anti)
return false;
return Source->getInstr()->isPHI() || Dep.getSUnit()->getInstr()->isPHI();
}
bool isLoopCarriedDep(SUnit *Source, const SDep &Dep, bool isSucc = true);
/// The distance function, which indicates that operation V of iteration I
/// depends on operations U of iteration I-distance.
unsigned getDistance(SUnit *U, SUnit *V, const SDep &Dep) {
// Instructions that feed a Phi have a distance of 1. Computing larger
// values for arrays requires data dependence information.
if (V->getInstr()->isPHI() && Dep.getKind() == SDep::Anti)
return 1;
return 0;
}
/// Set the Minimum Initiation Interval for this schedule attempt.
void setMII(unsigned mii) { MII = mii; }
void applyInstrChange(MachineInstr *MI, SMSchedule &Schedule);
void fixupRegisterOverlaps(std::deque<SUnit *> &Instrs);
/// Return the new base register that was stored away for the changed
/// instruction.
unsigned getInstrBaseReg(SUnit *SU) {
DenseMap<SUnit *, std::pair<unsigned, int64_t>>::iterator It =
InstrChanges.find(SU);
if (It != InstrChanges.end())
return It->second.first;
return 0;
}
void addMutation(std::unique_ptr<ScheduleDAGMutation> Mutation) {
Mutations.push_back(std::move(Mutation));
}
private:
void addLoopCarriedDependences(AliasAnalysis *AA);
void updatePhiDependences();
void changeDependences();
unsigned calculateResMII();
unsigned calculateRecMII(NodeSetType &RecNodeSets);
void findCircuits(NodeSetType &NodeSets);
void fuseRecs(NodeSetType &NodeSets);
void removeDuplicateNodes(NodeSetType &NodeSets);
void computeNodeFunctions(NodeSetType &NodeSets);
void registerPressureFilter(NodeSetType &NodeSets);
void colocateNodeSets(NodeSetType &NodeSets);
void checkNodeSets(NodeSetType &NodeSets);
void groupRemainingNodes(NodeSetType &NodeSets);
void addConnectedNodes(SUnit *SU, NodeSet &NewSet,
SetVector<SUnit *> &NodesAdded);
void computeNodeOrder(NodeSetType &NodeSets);
void checkValidNodeOrder(const NodeSetType &Circuits) const;
bool schedulePipeline(SMSchedule &Schedule);
void generatePipelinedLoop(SMSchedule &Schedule);
void generateProlog(SMSchedule &Schedule, unsigned LastStage,
MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
MBBVectorTy &PrologBBs);
void generateEpilog(SMSchedule &Schedule, unsigned LastStage,
MachineBasicBlock *KernelBB, ValueMapTy *VRMap,
MBBVectorTy &EpilogBBs, MBBVectorTy &PrologBBs);
void generateExistingPhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
SMSchedule &Schedule, ValueMapTy *VRMap,
InstrMapTy &InstrMap, unsigned LastStageNum,
unsigned CurStageNum, bool IsLast);
void generatePhis(MachineBasicBlock *NewBB, MachineBasicBlock *BB1,
MachineBasicBlock *BB2, MachineBasicBlock *KernelBB,
SMSchedule &Schedule, ValueMapTy *VRMap,
InstrMapTy &InstrMap, unsigned LastStageNum,
unsigned CurStageNum, bool IsLast);
void removeDeadInstructions(MachineBasicBlock *KernelBB,
MBBVectorTy &EpilogBBs);
void splitLifetimes(MachineBasicBlock *KernelBB, MBBVectorTy &EpilogBBs,
SMSchedule &Schedule);
void addBranches(MBBVectorTy &PrologBBs, MachineBasicBlock *KernelBB,
MBBVectorTy &EpilogBBs, SMSchedule &Schedule,
ValueMapTy *VRMap);
bool computeDelta(MachineInstr &MI, unsigned &Delta);
void updateMemOperands(MachineInstr &NewMI, MachineInstr &OldMI,
unsigned Num);
MachineInstr *cloneInstr(MachineInstr *OldMI, unsigned CurStageNum,
unsigned InstStageNum);
MachineInstr *cloneAndChangeInstr(MachineInstr *OldMI, unsigned CurStageNum,
unsigned InstStageNum,
SMSchedule &Schedule);
void updateInstruction(MachineInstr *NewMI, bool LastDef,
unsigned CurStageNum, unsigned InstrStageNum,
SMSchedule &Schedule, ValueMapTy *VRMap);
MachineInstr *findDefInLoop(unsigned Reg);
unsigned getPrevMapVal(unsigned StageNum, unsigned PhiStage, unsigned LoopVal,
unsigned LoopStage, ValueMapTy *VRMap,
MachineBasicBlock *BB);
void rewritePhiValues(MachineBasicBlock *NewBB, unsigned StageNum,
SMSchedule &Schedule, ValueMapTy *VRMap,
InstrMapTy &InstrMap);
void rewriteScheduledInstr(MachineBasicBlock *BB, SMSchedule &Schedule,
InstrMapTy &InstrMap, unsigned CurStageNum,
unsigned PhiNum, MachineInstr *Phi,
unsigned OldReg, unsigned NewReg,
unsigned PrevReg = 0);
bool canUseLastOffsetValue(MachineInstr *MI, unsigned &BasePos,
unsigned &OffsetPos, unsigned &NewBase,
int64_t &NewOffset);
void postprocessDAG();
};
/// A NodeSet contains a set of SUnit DAG nodes with additional information
/// that assigns a priority to the set.
class NodeSet {
SetVector<SUnit *> Nodes;
bool HasRecurrence = false;
unsigned RecMII = 0;
int MaxMOV = 0;
unsigned MaxDepth = 0;
unsigned Colocate = 0;
SUnit *ExceedPressure = nullptr;
unsigned Latency = 0;
public:
using iterator = SetVector<SUnit *>::const_iterator;
NodeSet() = default;
NodeSet(iterator S, iterator E) : Nodes(S, E), HasRecurrence(true) {
Latency = 0;
for (unsigned i = 0, e = Nodes.size(); i < e; ++i)
for (const SDep &Succ : Nodes[i]->Succs)
if (Nodes.count(Succ.getSUnit()))
Latency += Succ.getLatency();
}
bool insert(SUnit *SU) { return Nodes.insert(SU); }
void insert(iterator S, iterator E) { Nodes.insert(S, E); }
template <typename UnaryPredicate> bool remove_if(UnaryPredicate P) {
return Nodes.remove_if(P);
}
unsigned count(SUnit *SU) const { return Nodes.count(SU); }
bool hasRecurrence() { return HasRecurrence; };
unsigned size() const { return Nodes.size(); }
bool empty() const { return Nodes.empty(); }
SUnit *getNode(unsigned i) const { return Nodes[i]; };
void setRecMII(unsigned mii) { RecMII = mii; };
void setColocate(unsigned c) { Colocate = c; };
void setExceedPressure(SUnit *SU) { ExceedPressure = SU; }
bool isExceedSU(SUnit *SU) { return ExceedPressure == SU; }
int compareRecMII(NodeSet &RHS) { return RecMII - RHS.RecMII; }
int getRecMII() { return RecMII; }
/// Summarize node functions for the entire node set.
void computeNodeSetInfo(SwingSchedulerDAG *SSD) {
for (SUnit *SU : *this) {
MaxMOV = std::max(MaxMOV, SSD->getMOV(SU));
MaxDepth = std::max(MaxDepth, SSD->getDepth(SU));
}
}
unsigned getLatency() { return Latency; }
unsigned getMaxDepth() { return MaxDepth; }
void clear() {
Nodes.clear();
RecMII = 0;
HasRecurrence = false;
MaxMOV = 0;
MaxDepth = 0;
Colocate = 0;
ExceedPressure = nullptr;
}
operator SetVector<SUnit *> &() { return Nodes; }
/// Sort the node sets by importance. First, rank them by recurrence MII,
/// then by mobility (least mobile done first), and finally by depth.
/// Each node set may contain a colocate value which is used as the first
/// tie breaker, if it's set.
bool operator>(const NodeSet &RHS) const {
if (RecMII == RHS.RecMII) {
if (Colocate != 0 && RHS.Colocate != 0 && Colocate != RHS.Colocate)
return Colocate < RHS.Colocate;
if (MaxMOV == RHS.MaxMOV)
return MaxDepth > RHS.MaxDepth;
return MaxMOV < RHS.MaxMOV;
}
return RecMII > RHS.RecMII;
}
bool operator==(const NodeSet &RHS) const {
return RecMII == RHS.RecMII && MaxMOV == RHS.MaxMOV &&
MaxDepth == RHS.MaxDepth;
}
bool operator!=(const NodeSet &RHS) const { return !operator==(RHS); }
iterator begin() { return Nodes.begin(); }
iterator end() { return Nodes.end(); }
void print(raw_ostream &os) const {
os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
<< " depth " << MaxDepth << " col " << Colocate << "\n";
for (const auto &I : Nodes)
os << " SU(" << I->NodeNum << ") " << *(I->getInstr());
os << "\n";
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void dump() const { print(dbgs()); }
#endif
};
/// This class represents the scheduled code. The main data structure is a
/// map from scheduled cycle to instructions. During scheduling, the
/// data structure explicitly represents all stages/iterations. When
/// the algorithm finshes, the schedule is collapsed into a single stage,
/// which represents instructions from different loop iterations.
///
/// The SMS algorithm allows negative values for cycles, so the first cycle
/// in the schedule is the smallest cycle value.
class SMSchedule {
private:
/// Map from execution cycle to instructions.
DenseMap<int, std::deque<SUnit *>> ScheduledInstrs;
/// Map from instruction to execution cycle.
std::map<SUnit *, int> InstrToCycle;
/// Map for each register and the max difference between its uses and def.
/// The first element in the pair is the max difference in stages. The
/// second is true if the register defines a Phi value and loop value is
/// scheduled before the Phi.
std::map<unsigned, std::pair<unsigned, bool>> RegToStageDiff;
/// Keep track of the first cycle value in the schedule. It starts
/// as zero, but the algorithm allows negative values.
int FirstCycle = 0;
/// Keep track of the last cycle value in the schedule.
int LastCycle = 0;
/// The initiation interval (II) for the schedule.
int InitiationInterval = 0;
/// Target machine information.
const TargetSubtargetInfo &ST;
/// Virtual register information.
MachineRegisterInfo &MRI;
std::unique_ptr<DFAPacketizer> Resources;
public:
SMSchedule(MachineFunction *mf)
: ST(mf->getSubtarget()), MRI(mf->getRegInfo()),
Resources(ST.getInstrInfo()->CreateTargetScheduleState(ST)) {}
void reset() {
ScheduledInstrs.clear();
InstrToCycle.clear();
RegToStageDiff.clear();
FirstCycle = 0;
LastCycle = 0;
InitiationInterval = 0;
}
/// Set the initiation interval for this schedule.
void setInitiationInterval(int ii) { InitiationInterval = ii; }
/// Return the first cycle in the completed schedule. This
/// can be a negative value.
int getFirstCycle() const { return FirstCycle; }
/// Return the last cycle in the finalized schedule.
int getFinalCycle() const { return FirstCycle + InitiationInterval - 1; }
/// Return the cycle of the earliest scheduled instruction in the dependence
/// chain.
int earliestCycleInChain(const SDep &Dep);
/// Return the cycle of the latest scheduled instruction in the dependence
/// chain.
int latestCycleInChain(const SDep &Dep);
void computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
int *MinEnd, int *MaxStart, int II, SwingSchedulerDAG *DAG);
bool insert(SUnit *SU, int StartCycle, int EndCycle, int II);
/// Iterators for the cycle to instruction map.
using sched_iterator = DenseMap<int, std::deque<SUnit *>>::iterator;
using const_sched_iterator =
DenseMap<int, std::deque<SUnit *>>::const_iterator;
/// Return true if the instruction is scheduled at the specified stage.
bool isScheduledAtStage(SUnit *SU, unsigned StageNum) {
return (stageScheduled(SU) == (int)StageNum);
}
/// Return the stage for a scheduled instruction. Return -1 if
/// the instruction has not been scheduled.
int stageScheduled(SUnit *SU) const {
std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
if (it == InstrToCycle.end())
return -1;
return (it->second - FirstCycle) / InitiationInterval;
}
/// Return the cycle for a scheduled instruction. This function normalizes
/// the first cycle to be 0.
unsigned cycleScheduled(SUnit *SU) const {
std::map<SUnit *, int>::const_iterator it = InstrToCycle.find(SU);
assert(it != InstrToCycle.end() && "Instruction hasn't been scheduled.");
return (it->second - FirstCycle) % InitiationInterval;
}
/// Return the maximum stage count needed for this schedule.
unsigned getMaxStageCount() {
return (LastCycle - FirstCycle) / InitiationInterval;
}
/// Return the max. number of stages/iterations that can occur between a
/// register definition and its uses.
unsigned getStagesForReg(int Reg, unsigned CurStage) {
std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
if (CurStage > getMaxStageCount() && Stages.first == 0 && Stages.second)
return 1;
return Stages.first;
}
/// The number of stages for a Phi is a little different than other
/// instructions. The minimum value computed in RegToStageDiff is 1
/// because we assume the Phi is needed for at least 1 iteration.
/// This is not the case if the loop value is scheduled prior to the
/// Phi in the same stage. This function returns the number of stages
/// or iterations needed between the Phi definition and any uses.
unsigned getStagesForPhi(int Reg) {
std::pair<unsigned, bool> Stages = RegToStageDiff[Reg];
if (Stages.second)
return Stages.first;
return Stages.first - 1;
}
/// Return the instructions that are scheduled at the specified cycle.
std::deque<SUnit *> &getInstructions(int cycle) {
return ScheduledInstrs[cycle];
}
bool isValidSchedule(SwingSchedulerDAG *SSD);
void finalizeSchedule(SwingSchedulerDAG *SSD);
void orderDependence(SwingSchedulerDAG *SSD, SUnit *SU,
std::deque<SUnit *> &Insts);
bool isLoopCarried(SwingSchedulerDAG *SSD, MachineInstr &Phi);
bool isLoopCarriedDefOfUse(SwingSchedulerDAG *SSD, MachineInstr *Def,
MachineOperand &MO);
void print(raw_ostream &os) const;
void dump() const;
};
} // end anonymous namespace
unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5;
char MachinePipeliner::ID = 0;
#ifndef NDEBUG
int MachinePipeliner::NumTries = 0;
#endif
char &llvm::MachinePipelinerID = MachinePipeliner::ID;
INITIALIZE_PASS_BEGIN(MachinePipeliner, DEBUG_TYPE,
"Modulo Software Pipelining", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfo)
INITIALIZE_PASS_DEPENDENCY(MachineDominatorTree)
INITIALIZE_PASS_DEPENDENCY(LiveIntervals)
INITIALIZE_PASS_END(MachinePipeliner, DEBUG_TYPE,
"Modulo Software Pipelining", false, false)
/// The "main" function for implementing Swing Modulo Scheduling.
bool MachinePipeliner::runOnMachineFunction(MachineFunction &mf) {
if (skipFunction(mf.getFunction()))
return false;
if (!EnableSWP)
return false;
if (mf.getFunction().getAttributes().hasAttribute(
AttributeList::FunctionIndex, Attribute::OptimizeForSize) &&
!EnableSWPOptSize.getPosition())
return false;
MF = &mf;
MLI = &getAnalysis<MachineLoopInfo>();
MDT = &getAnalysis<MachineDominatorTree>();
TII = MF->getSubtarget().getInstrInfo();
RegClassInfo.runOnMachineFunction(*MF);
for (auto &L : *MLI)
scheduleLoop(*L);
return false;
}
/// Attempt to perform the SMS algorithm on the specified loop. This function is
/// the main entry point for the algorithm. The function identifies candidate
/// loops, calculates the minimum initiation interval, and attempts to schedule
/// the loop.
bool MachinePipeliner::scheduleLoop(MachineLoop &L) {
bool Changed = false;
for (auto &InnerLoop : L)
Changed |= scheduleLoop(*InnerLoop);
#ifndef NDEBUG
// Stop trying after reaching the limit (if any).
int Limit = SwpLoopLimit;
if (Limit >= 0) {
if (NumTries >= SwpLoopLimit)
return Changed;
NumTries++;
}
#endif
if (!canPipelineLoop(L))
return Changed;
++NumTrytoPipeline;
Changed = swingModuloScheduler(L);
return Changed;
}
/// Return true if the loop can be software pipelined. The algorithm is
/// restricted to loops with a single basic block. Make sure that the
/// branch in the loop can be analyzed.
bool MachinePipeliner::canPipelineLoop(MachineLoop &L) {
if (L.getNumBlocks() != 1)
return false;
// Check if the branch can't be understood because we can't do pipelining
// if that's the case.
LI.TBB = nullptr;
LI.FBB = nullptr;
LI.BrCond.clear();
if (TII->analyzeBranch(*L.getHeader(), LI.TBB, LI.FBB, LI.BrCond))
return false;
LI.LoopInductionVar = nullptr;
LI.LoopCompare = nullptr;
if (TII->analyzeLoop(L, LI.LoopInductionVar, LI.LoopCompare))
return false;
if (!L.getLoopPreheader())
return false;
// Remove any subregisters from inputs to phi nodes.
preprocessPhiNodes(*L.getHeader());
return true;
}
void MachinePipeliner::preprocessPhiNodes(MachineBasicBlock &B) {
MachineRegisterInfo &MRI = MF->getRegInfo();
SlotIndexes &Slots = *getAnalysis<LiveIntervals>().getSlotIndexes();
for (MachineInstr &PI : make_range(B.begin(), B.getFirstNonPHI())) {
MachineOperand &DefOp = PI.getOperand(0);
assert(DefOp.getSubReg() == 0);
auto *RC = MRI.getRegClass(DefOp.getReg());
for (unsigned i = 1, n = PI.getNumOperands(); i != n; i += 2) {
MachineOperand &RegOp = PI.getOperand(i);
if (RegOp.getSubReg() == 0)
continue;
// If the operand uses a subregister, replace it with a new register
// without subregisters, and generate a copy to the new register.
unsigned NewReg = MRI.createVirtualRegister(RC);
MachineBasicBlock &PredB = *PI.getOperand(i+1).getMBB();
MachineBasicBlock::iterator At = PredB.getFirstTerminator();
const DebugLoc &DL = PredB.findDebugLoc(At);
auto Copy = BuildMI(PredB, At, DL, TII->get(TargetOpcode::COPY), NewReg)
.addReg(RegOp.getReg(), getRegState(RegOp),
RegOp.getSubReg());
Slots.insertMachineInstrInMaps(*Copy);
RegOp.setReg(NewReg);
RegOp.setSubReg(0);
}
}
}
/// The SMS algorithm consists of the following main steps:
/// 1. Computation and analysis of the dependence graph.
/// 2. Ordering of the nodes (instructions).
/// 3. Attempt to Schedule the loop.
bool MachinePipeliner::swingModuloScheduler(MachineLoop &L) {
assert(L.getBlocks().size() == 1 && "SMS works on single blocks only.");
SwingSchedulerDAG SMS(*this, L, getAnalysis<LiveIntervals>(), RegClassInfo);
MachineBasicBlock *MBB = L.getHeader();
// The kernel should not include any terminator instructions. These
// will be added back later.
SMS.startBlock(MBB);
// Compute the number of 'real' instructions in the basic block by
// ignoring terminators.
unsigned size = MBB->size();
for (MachineBasicBlock::iterator I = MBB->getFirstTerminator(),
E = MBB->instr_end();
I != E; ++I, --size)
;
SMS.enterRegion(MBB, MBB->begin(), MBB->getFirstTerminator(), size);
SMS.schedule();
SMS.exitRegion();
SMS.finishBlock();
return SMS.hasNewSchedule();
}
/// We override the schedule function in ScheduleDAGInstrs to implement the
/// scheduling part of the Swing Modulo Scheduling algorithm.
void SwingSchedulerDAG::schedule() {
AliasAnalysis *AA = &Pass.getAnalysis<AAResultsWrapperPass>().getAAResults();
buildSchedGraph(AA);
addLoopCarriedDependences(AA);
updatePhiDependences();
Topo.InitDAGTopologicalSorting();
postprocessDAG();
changeDependences();
LLVM_DEBUG({
for (unsigned su = 0, e = SUnits.size(); su != e; ++su)
SUnits[su].dumpAll(this);
});
NodeSetType NodeSets;
findCircuits(NodeSets);
NodeSetType Circuits = NodeSets;
// Calculate the MII.
unsigned ResMII = calculateResMII();
unsigned RecMII = calculateRecMII(NodeSets);
fuseRecs(NodeSets);
// This flag is used for testing and can cause correctness problems.
if (SwpIgnoreRecMII)
RecMII = 0;
MII = std::max(ResMII, RecMII);
LLVM_DEBUG(dbgs() << "MII = " << MII << " (rec=" << RecMII
<< ", res=" << ResMII << ")\n");
// Can't schedule a loop without a valid MII.
if (MII == 0)
return;
// Don't pipeline large loops.
if (SwpMaxMii != -1 && (int)MII > SwpMaxMii)
return;
computeNodeFunctions(NodeSets);
registerPressureFilter(NodeSets);
colocateNodeSets(NodeSets);
checkNodeSets(NodeSets);
LLVM_DEBUG({
for (auto &I : NodeSets) {
dbgs() << " Rec NodeSet ";
I.dump();
}
});
std::stable_sort(NodeSets.begin(), NodeSets.end(), std::greater<NodeSet>());
groupRemainingNodes(NodeSets);
removeDuplicateNodes(NodeSets);
LLVM_DEBUG({
for (auto &I : NodeSets) {
dbgs() << " NodeSet ";
I.dump();
}
});
computeNodeOrder(NodeSets);
// check for node order issues
checkValidNodeOrder(Circuits);
SMSchedule Schedule(Pass.MF);
Scheduled = schedulePipeline(Schedule);
if (!Scheduled)
return;
unsigned numStages = Schedule.getMaxStageCount();
// No need to generate pipeline if there are no overlapped iterations.
if (numStages == 0)
return;
// Check that the maximum stage count is less than user-defined limit.
if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages)
return;
generatePipelinedLoop(Schedule);
++NumPipelined;
}
/// Clean up after the software pipeliner runs.
void SwingSchedulerDAG::finishBlock() {
for (MachineInstr *I : NewMIs)
MF.DeleteMachineInstr(I);
NewMIs.clear();
// Call the superclass.
ScheduleDAGInstrs::finishBlock();
}
/// Return the register values for the operands of a Phi instruction.
/// This function assume the instruction is a Phi.
static void getPhiRegs(MachineInstr &Phi, MachineBasicBlock *Loop,
unsigned &InitVal, unsigned &LoopVal) {
assert(Phi.isPHI() && "Expecting a Phi.");
InitVal = 0;
LoopVal = 0;
for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
if (Phi.getOperand(i + 1).getMBB() != Loop)
InitVal = Phi.getOperand(i).getReg();
else
LoopVal = Phi.getOperand(i).getReg();
assert(InitVal != 0 && LoopVal != 0 && "Unexpected Phi structure.");
}
/// Return the Phi register value that comes from the incoming block.
static unsigned getInitPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
if (Phi.getOperand(i + 1).getMBB() != LoopBB)
return Phi.getOperand(i).getReg();
return 0;
}
/// Return the Phi register value that comes the loop block.
static unsigned getLoopPhiReg(MachineInstr &Phi, MachineBasicBlock *LoopBB) {
for (unsigned i = 1, e = Phi.getNumOperands(); i != e; i += 2)
if (Phi.getOperand(i + 1).getMBB() == LoopBB)
return Phi.getOperand(i).getReg();
return 0;
}
/// Return true if SUb can be reached from SUa following the chain edges.
static bool isSuccOrder(SUnit *SUa, SUnit *SUb) {
SmallPtrSet<SUnit *, 8> Visited;
SmallVector<SUnit *, 8> Worklist;
Worklist.push_back(SUa);
while (!Worklist.empty()) {
const SUnit *SU = Worklist.pop_back_val();
for (auto &SI : SU->Succs) {
SUnit *SuccSU = SI.getSUnit();
if (SI.getKind() == SDep::Order) {
if (Visited.count(SuccSU))
continue;
if (SuccSU == SUb)
return true;
Worklist.push_back(SuccSU);
Visited.insert(SuccSU);
}
}
}
return false;
}
/// Return true if the instruction causes a chain between memory
/// references before and after it.
static bool isDependenceBarrier(MachineInstr &MI, AliasAnalysis *AA) {
return MI.isCall() || MI.hasUnmodeledSideEffects() ||
(MI.hasOrderedMemoryRef() &&
(!MI.mayLoad() || !MI.isDereferenceableInvariantLoad(AA)));
}
/// Return the underlying objects for the memory references of an instruction.
/// This function calls the code in ValueTracking, but first checks that the
/// instruction has a memory operand.
static void getUnderlyingObjects(MachineInstr *MI,
SmallVectorImpl<Value *> &Objs,
const DataLayout &DL) {
if (!MI->hasOneMemOperand())
return;
MachineMemOperand *MM = *MI->memoperands_begin();
if (!MM->getValue())
return;
GetUnderlyingObjects(const_cast<Value *>(MM->getValue()), Objs, DL);
for (Value *V : Objs) {
if (!isIdentifiedObject(V)) {
Objs.clear();
return;
}
Objs.push_back(V);
}
}
/// 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.
void SwingSchedulerDAG::addLoopCarriedDependences(AliasAnalysis *AA) {
MapVector<Value *, SmallVector<SUnit *, 4>> PendingLoads;
Value *UnknownValue =
UndefValue::get(Type::getVoidTy(MF.getFunction().getContext()));
for (auto &SU : SUnits) {
MachineInstr &MI = *SU.getInstr();
if (isDependenceBarrier(MI, AA))
PendingLoads.clear();
else if (MI.mayLoad()) {
SmallVector<Value *, 4> Objs;
getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
if (Objs.empty())
Objs.push_back(UnknownValue);
for (auto V : Objs) {
SmallVector<SUnit *, 4> &SUs = PendingLoads[V];
SUs.push_back(&SU);
}
} else if (MI.mayStore()) {
SmallVector<Value *, 4> Objs;
getUnderlyingObjects(&MI, Objs, MF.getDataLayout());
if (Objs.empty())
Objs.push_back(UnknownValue);
for (auto V : Objs) {
MapVector<Value *, SmallVector<SUnit *, 4>>::iterator I =
PendingLoads.find(V);
if (I == PendingLoads.end())
continue;
for (auto Load : I->second) {
if (isSuccOrder(Load, &SU))
continue;
MachineInstr &LdMI = *Load->getInstr();
// First, perform the cheaper check that compares the base register.
// If they are the same and the load offset is less than the store
// offset, then mark the dependence as loop carried potentially.
unsigned BaseReg1, BaseReg2;
int64_t Offset1, Offset2;
if (TII->getMemOpBaseRegImmOfs(LdMI, BaseReg1, Offset1, TRI) &&
TII->getMemOpBaseRegImmOfs(MI, BaseReg2, Offset2, TRI)) {
if (BaseReg1 == BaseReg2 && (int)Offset1 < (int)Offset2) {
assert(TII->areMemAccessesTriviallyDisjoint(LdMI, MI, AA) &&
"What happened to the chain edge?");
SDep Dep(Load, SDep::Barrier);
Dep.setLatency(1);
SU.addPred(Dep);
continue;
}
}
// Second, the more expensive check that uses alias analysis on the
// base registers. If they alias, and the load offset is less than
// the store offset, the mark the dependence as loop carried.
if (!AA) {
SDep Dep(Load, SDep::Barrier);
Dep.setLatency(1);
SU.addPred(Dep);
continue;
}
MachineMemOperand *MMO1 = *LdMI.memoperands_begin();
MachineMemOperand *MMO2 = *MI.memoperands_begin();
if (!MMO1->getValue() || !MMO2->getValue()) {
SDep Dep(Load, SDep::Barrier);
Dep.setLatency(1);
SU.addPred(Dep);
continue;
}
if (MMO1->getValue() == MMO2->getValue() &&
MMO1->getOffset() <= MMO2->getOffset()) {
SDep Dep(Load, SDep::Barrier);
Dep.setLatency(1);
SU.addPred(Dep);
continue;
}
AliasResult AAResult = AA->alias(
MemoryLocation(MMO1->getValue(), MemoryLocation::UnknownSize,
MMO1->getAAInfo()),
MemoryLocation(MMO2->getValue(), MemoryLocation::UnknownSize,
MMO2->getAAInfo()));
if (AAResult != NoAlias) {
SDep Dep(Load, SDep::Barrier);
Dep.setLatency(1);
SU.addPred(Dep);
}
}
}
}
}
}
/// 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.
void SwingSchedulerDAG::updatePhiDependences() {
SmallVector<SDep, 4> RemoveDeps;
const TargetSubtargetInfo &ST = MF.getSubtarget<TargetSubtargetInfo>();
// Iterate over each DAG node.
for (SUnit &I : SUnits) {
RemoveDeps.clear();
// Set to true if the instruction has an operand defined by a Phi.
unsigned HasPhiUse = 0;
unsigned HasPhiDef = 0;
MachineInstr *MI = I.getInstr();
// Iterate over each operand, and we process the definitions.
for (MachineInstr::mop_iterator MOI = MI->operands_begin(),
MOE = MI->operands_end();
MOI != MOE; ++MOI) {
if (!MOI->isReg())
continue;
unsigned Reg = MOI->getReg();
if (MOI->isDef()) {
// If the register is used by a Phi, then create an anti dependence.
for (MachineRegisterInfo::use_instr_iterator
UI = MRI.use_instr_begin(Reg),
UE = MRI.use_instr_end();
UI != UE; ++UI) {
MachineInstr *UseMI = &*UI;
SUnit *SU = getSUnit(UseMI);
if (SU != nullptr && UseMI->isPHI()) {
if (!MI->isPHI()) {
SDep Dep(SU, SDep::Anti, Reg);
Dep.setLatency(1);
I.addPred(Dep);
} else {
HasPhiDef = Reg;
// Add a chain edge to a dependent Phi that isn't an existing
// predecessor.
if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
I.addPred(SDep(SU, SDep::Barrier));
}
}
}
} else if (MOI->isUse()) {
// If the register is defined by a Phi, then create a true dependence.
MachineInstr *DefMI = MRI.getUniqueVRegDef(Reg);
if (DefMI == nullptr)
continue;
SUnit *SU = getSUnit(DefMI);
if (SU != nullptr && DefMI->isPHI()) {
if (!MI->isPHI()) {
SDep Dep(SU, SDep::Data, Reg);
Dep.setLatency(0);
ST.adjustSchedDependency(SU, &I, Dep);
I.addPred(Dep);
} else {
HasPhiUse = Reg;
// Add a chain edge to a dependent Phi that isn't an existing
// predecessor.
if (SU->NodeNum < I.NodeNum && !I.isPred(SU))
I.addPred(SDep(SU, SDep::Barrier));
}
}
}
}
// Remove order dependences from an unrelated Phi.
if (!SwpPruneDeps)
continue;
for (auto &PI : I.Preds) {
MachineInstr *PMI = PI.getSUnit()->getInstr();
if (PMI->isPHI() && PI.getKind() == SDep::Order) {
if (I.getInstr()->isPHI()) {
if (PMI->getOperand(0).getReg() == HasPhiUse)
continue;
if (getLoopPhiReg(*PMI, PMI->getParent()) == HasPhiDef)
continue;
}
RemoveDeps.push_back(PI);
}
}
for (int i = 0, e = RemoveDeps.size(); i != e; ++i)
I.removePred(RemoveDeps[i]);
}
}
/// Iterate over each DAG node and see if we can change any dependences
/// in order to reduce the recurrence MII.
void SwingSchedulerDAG::changeDependences() {
// See if an instruction can use a value from the previous iteration.
// If so, we update the base and offset of the instruction and change
// the dependences.
for (SUnit &I : SUnits) {
unsigned BasePos = 0, OffsetPos = 0, NewBase = 0;
int64_t NewOffset = 0;
if (!canUseLastOffsetValue(I.getInstr(), BasePos, OffsetPos, NewBase,
NewOffset))
continue;
// Get the MI and SUnit for the instruction that defines the original base.
unsigned OrigBase = I.getInstr()->getOperand(BasePos).getReg();
MachineInstr *DefMI = MRI.getUniqueVRegDef(OrigBase);
if (!DefMI)
continue;
SUnit *DefSU = getSUnit(DefMI);
if (!DefSU)
continue;
// Get the MI and SUnit for the instruction that defins the new base.
MachineInstr *LastMI = MRI.getUniqueVRegDef(NewBase);
if (!LastMI)
continue;
SUnit *LastSU = getSUnit(LastMI);
if (!LastSU)
continue;
if (Topo.IsReachable(&I, LastSU))
continue;
// Remove the dependence. The value now depends on a prior iteration.
SmallVector<SDep, 4> Deps;
for (SUnit::pred_iterator P = I.Preds.begin(), E = I.Preds.end(); P != E;
++P)
if (P->getSUnit() == DefSU)
Deps.push_back(*P);
for (int i = 0, e = Deps.size(); i != e; i++) {
Topo.RemovePred(&I, Deps[i].getSUnit());
I.removePred(Deps[i]);
}
// Remove the chain dependence between the instructions.
Deps.clear();
for (auto &P : LastSU->Preds)
if (P.getSUnit() == &I && P.getKind() == SDep::Order)
Deps.push_back(P);
for (int i = 0, e = Deps.size(); i != e; i++) {
Topo.RemovePred(LastSU, Deps[i].getSUnit());
LastSU->removePred(Deps[i]);
}
// Add a dependence between the new instruction and the instruction
// that defines the new base.
SDep Dep(&I, SDep::Anti, NewBase);
LastSU->addPred(Dep);
// Remember the base and offset information so that we can update the
// instruction during code generation.
InstrChanges[&I] = std::make_pair(NewBase, NewOffset);
}
}
namespace {
// FuncUnitSorter - Comparison operator used to sort instructions by
// the number of functional unit choices.
struct FuncUnitSorter {
const InstrItineraryData *InstrItins;
DenseMap<unsigned, unsigned> Resources;
FuncUnitSorter(const InstrItineraryData *IID) : InstrItins(IID) {}
// Compute the number of functional unit alternatives needed
// at each stage, and take the minimum value. We prioritize the
// instructions by the least number of choices first.
unsigned minFuncUnits(const MachineInstr *Inst, unsigned &F) const {
unsigned schedClass = Inst->getDesc().getSchedClass();
unsigned min = UINT_MAX;
for (const InstrStage *IS = InstrItins->beginStage(schedClass),
*IE = InstrItins->endStage(schedClass);
IS != IE; ++IS) {
unsigned funcUnits = IS->getUnits();
unsigned numAlternatives = countPopulation(funcUnits);
if (numAlternatives < min) {
min = numAlternatives;
F = funcUnits;
}
}
return min;
}
// Compute the critical resources needed by the instruction. This
// function records the functional units needed by instructions that
// must use only one functional unit. We use this as a tie breaker
// for computing the resource MII. The instrutions that require
// the same, highly used, functional unit have high priority.
void calcCriticalResources(MachineInstr &MI) {
unsigned SchedClass = MI.getDesc().getSchedClass();
for (const InstrStage *IS = InstrItins->beginStage(SchedClass),
*IE = InstrItins->endStage(SchedClass);
IS != IE; ++IS) {
unsigned FuncUnits = IS->getUnits();
if (countPopulation(FuncUnits) == 1)
Resources[FuncUnits]++;
}
}
/// Return true if IS1 has less priority than IS2.
bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const {
unsigned F1 = 0, F2 = 0;
unsigned MFUs1 = minFuncUnits(IS1, F1);
unsigned MFUs2 = minFuncUnits(IS2, F2);
if (MFUs1 == 1 && MFUs2 == 1)
return Resources.lookup(F1) < Resources.lookup(F2);
return MFUs1 > MFUs2;
}
};
} // end anonymous namespace
/// 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.
unsigned SwingSchedulerDAG::calculateResMII() {
SmallVector<DFAPacketizer *, 8> Resources;
MachineBasicBlock *MBB = Loop.getHeader();
Resources.push_back(TII->CreateTargetScheduleState(MF.getSubtarget()));
// Sort the instructions by the number of available choices for scheduling,
// least to most. Use the number of critical resources as the tie breaker.
FuncUnitSorter FUS =
FuncUnitSorter(MF.getSubtarget().getInstrItineraryData());
for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
E = MBB->getFirstTerminator();
I != E; ++I)
FUS.calcCriticalResources(*I);
PriorityQueue<MachineInstr *, std::vector<MachineInstr *>, FuncUnitSorter>
FuncUnitOrder(FUS);
for (MachineBasicBlock::iterator I = MBB->getFirstNonPHI(),
E = MBB->getFirstTerminator();
I != E; ++I)
FuncUnitOrder.push(&*I);
while (!FuncUnitOrder.empty()) {
MachineInstr *MI = FuncUnitOrder.top();
FuncUnitOrder.pop();
if (TII->isZeroCost(MI->getOpcode()))
continue;
// Attempt to reserve the instruction in an existing DFA. At least one
// DFA is needed for each cycle.
unsigned NumCycles = getSUnit(MI)->Latency;
unsigned ReservedCycles = 0;
SmallVectorImpl<DFAPacketizer *>::iterator RI = Resources.begin();
SmallVectorImpl<DFAPacketizer *>::iterator RE = Resources.end();
for (unsigned C = 0; C < NumCycles; ++C)
while (RI != RE) {
if ((*RI++)->canReserveResources(*MI)) {
++ReservedCycles;
break;
}
}
// Start reserving resources using existing DFAs.
for (unsigned C = 0; C < ReservedCycles; ++C) {
--RI;
(*RI)->reserveResources(*MI);
}
// Add new DFAs, if needed, to reserve resources.
for (unsigned C = ReservedCycles; C < NumCycles; ++C) {
DFAPacketizer *NewResource =
TII->CreateTargetScheduleState(MF.getSubtarget());
assert(NewResource->canReserveResources(*MI) && "Reserve error.");
NewResource->reserveResources(*MI);
Resources.push_back(NewResource);
}
}
int Resmii = Resources.size();
// Delete the memory for each of the DFAs that were created earlier.
for (DFAPacketizer *RI : Resources) {
DFAPacketizer *D = RI;
delete D;
}
Resources.clear();
return Resmii;
}
/// 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.
unsigned SwingSchedulerDAG::calculateRecMII(NodeSetType &NodeSets) {
unsigned RecMII = 0;
for (NodeSet &Nodes : NodeSets) {
if (Nodes.empty())
continue;
unsigned Delay = Nodes.getLatency();
unsigned Distance = 1;
// ii = ceil(delay / distance)
unsigned CurMII = (Delay + Distance - 1) / Distance;
Nodes.setRecMII(CurMII);
if (CurMII > RecMII)
RecMII = CurMII;
}
return RecMII;
}
/// Swap all the anti dependences in the DAG. That means it is no longer a DAG,
/// but we do this to find the circuits, and then change them back.
static void swapAntiDependences(std::vector<SUnit> &SUnits) {
SmallVector<std::pair<SUnit *, SDep>, 8> DepsAdded;
for (unsigned i = 0, e = SUnits.size(); i != e; ++i) {
SUnit *SU = &SUnits[i];
for (SUnit::pred_iterator IP = SU->Preds.begin(), EP = SU->Preds.end();
IP != EP; ++IP) {
if (IP->getKind() != SDep::Anti)
continue;
DepsAdded.push_back(std::make_pair(SU, *IP));
}
}
for (SmallVector<std::pair<SUnit *, SDep>, 8>::iterator I = DepsAdded.begin(),
E = DepsAdded.end();
I != E; ++I) {
// Remove this anti dependency and add one in the reverse direction.
SUnit *SU = I->first;
SDep &D = I->second;
SUnit *TargetSU = D.getSUnit();
unsigned Reg = D.getReg();
unsigned Lat = D.getLatency();
SU->removePred(D);
SDep Dep(SU, SDep::Anti, Reg);
Dep.setLatency(Lat);
TargetSU->addPred(Dep);
}
}
/// Create the adjacency structure of the nodes in the graph.
void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
SwingSchedulerDAG *DAG) {
BitVector Added(SUnits.size());
DenseMap<int, int> OutputDeps;
for (int i = 0, e = SUnits.size(); i != e; ++i) {
Added.reset();
// Add any successor to the adjacency matrix and exclude duplicates.
for (auto &SI : SUnits[i].Succs) {
// Only create a back-edge on the first and last nodes of a dependence
// chain. This records any chains and adds them later.
if (SI.getKind() == SDep::Output) {
int N = SI.getSUnit()->NodeNum;
int BackEdge = i;
auto Dep = OutputDeps.find(BackEdge);
if (Dep != OutputDeps.end()) {
BackEdge = Dep->second;
OutputDeps.erase(Dep);
}
OutputDeps[N] = BackEdge;
}
// Do not process a boundary node and a back-edge is processed only
// if it goes to a Phi.
if (SI.getSUnit()->isBoundaryNode() ||
(SI.getKind() == SDep::Anti && !SI.getSUnit()->getInstr()->isPHI()))
continue;
int N = SI.getSUnit()->NodeNum;
if (!Added.test(N)) {
AdjK[i].push_back(N);
Added.set(N);
}
}
// A chain edge between a store and a load is treated as a back-edge in the
// adjacency matrix.
for (auto &PI : SUnits[i].Preds) {
if (!SUnits[i].getInstr()->mayStore() ||
!DAG->isLoopCarriedDep(&SUnits[i], PI, false))
continue;
if (PI.getKind() == SDep::Order && PI.getSUnit()->getInstr()->mayLoad()) {
int N = PI.getSUnit()->NodeNum;
if (!Added.test(N)) {
AdjK[i].push_back(N);
Added.set(N);
}
}
}
}
// Add back-eges in the adjacency matrix for the output dependences.
for (auto &OD : OutputDeps)
if (!Added.test(OD.second)) {
AdjK[OD.first].push_back(OD.second);
Added.set(OD.second);
}
}
/// Identify an elementary circuit in the dependence graph starting at the
/// specified node.
bool SwingSchedulerDAG::Circuits::circuit(int V, int S, NodeSetType &NodeSets,
bool HasBackedge) {
SUnit *SV = &SUnits[V];
bool F = false;
Stack.insert(SV);
Blocked.set(V);
for (auto W : AdjK[V]) {
if (NumPaths > MaxPaths)
break;
if (W < S)
continue;
if (W == S) {
if (!HasBackedge)
NodeSets.push_back(NodeSet(Stack.begin(), Stack.end()));
F = true;
++NumPaths;
break;
} else if (!Blocked.test(W)) {
if (circuit(W, S, NodeSets, W < V ? true : HasBackedge))
F = true;
}
}
if (F)
unblock(V);
else {
for (auto W : AdjK[V]) {
if (W < S)
continue;
if (B[W].count(SV) == 0)
B[W].insert(SV);
}
}
Stack.pop_back();
return F;
}
/// Unblock a node in the circuit finding algorithm.
void SwingSchedulerDAG::Circuits::unblock(int U) {
Blocked.reset(U);
SmallPtrSet<SUnit *, 4> &BU = B[U];
while (!BU.empty()) {
SmallPtrSet<SUnit *, 4>::iterator SI = BU.begin();
assert(SI != BU.end() && "Invalid B set.");
SUnit *W = *SI;
BU.erase(W);
if (Blocked.test(W->NodeNum))
unblock(W->NodeNum);
}
}
/// Identify all the elementary circuits in the dependence graph using
/// Johnson's circuit algorithm.
void SwingSchedulerDAG::findCircuits(NodeSetType &NodeSets) {
// Swap all the anti dependences in the DAG. That means it is no longer a DAG,
// but we do this to find the circuits, and then change them back.
swapAntiDependences(SUnits);
Circuits Cir(SUnits);
// Create the adjacency structure.
Cir.createAdjacencyStructure(this);
for (int i = 0, e = SUnits.size(); i != e; ++i) {
Cir.reset();
Cir.circuit(i, i, NodeSets);
}
// Change the dependences back so that we've created a DAG again.
swapAntiDependences(SUnits);
}
/// Return true for DAG nodes that we ignore when computing the cost functions.
/// We ignore the back-edge recurrence in order to avoid unbounded recursion
/// in the calculation of the ASAP, ALAP, etc functions.
static bool ignoreDependence(const SDep &D, bool isPred) {
if (D.isArtificial())
return true;
return D.getKind() == SDep::Anti && isPred;
}
/// 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.
void SwingSchedulerDAG::computeNodeFunctions(NodeSetType &NodeSets) {
ScheduleInfo.resize(SUnits.size());
LLVM_DEBUG({
for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
E = Topo.end();
I != E; ++I) {
SUnit *SU = &SUnits[*I];
SU->dump(this);
}
});
int maxASAP = 0;
// Compute ASAP and ZeroLatencyDepth.
for (ScheduleDAGTopologicalSort::const_iterator I = Topo.begin(),
E = Topo.end();
I != E; ++I) {
int asap = 0;
int zeroLatencyDepth = 0;
SUnit *SU = &SUnits[*I];
for (SUnit::const_pred_iterator IP = SU->Preds.begin(),
EP = SU->Preds.end();
IP != EP; ++IP) {
SUnit *pred = IP->getSUnit();
if (IP->getLatency() == 0)
zeroLatencyDepth =
std::max(zeroLatencyDepth, getZeroLatencyDepth(pred) + 1);
if (ignoreDependence(*IP, true))
continue;
asap = std::max(asap, (int)(getASAP(pred) + IP->getLatency() -
getDistance(pred, SU, *IP) * MII));
}
maxASAP = std::max(maxASAP, asap);
ScheduleInfo[*I].ASAP = asap;
ScheduleInfo[*I].ZeroLatencyDepth = zeroLatencyDepth;
}
// Compute ALAP, ZeroLatencyHeight, and MOV.
for (ScheduleDAGTopologicalSort::const_reverse_iterator I = Topo.rbegin(),
E = Topo.rend();
I != E; ++I) {
int alap = maxASAP;
int zeroLatencyHeight = 0;
SUnit *SU = &SUnits[*I];
for (SUnit::const_succ_iterator IS = SU->Succs.begin(),
ES = SU->Succs.end();
IS != ES; ++IS) {
SUnit *succ = IS->getSUnit();
if (IS->getLatency() == 0)
zeroLatencyHeight =
std::max(zeroLatencyHeight, getZeroLatencyHeight(succ) + 1);
if (ignoreDependence(*IS, true))
continue;
alap = std::min(alap, (int)(getALAP(succ) - IS->getLatency() +
getDistance(SU, succ, *IS) * MII));
}
ScheduleInfo[*I].ALAP = alap;
ScheduleInfo[*I].ZeroLatencyHeight = zeroLatencyHeight;
}
// After computing the node functions, compute the summary for each node set.
for (NodeSet &I : NodeSets)
I.computeNodeSetInfo(this);
LLVM_DEBUG({
for (unsigned i = 0; i < SUnits.size(); i++) {
dbgs() << "\tNode " << i << ":\n";
dbgs() << "\t ASAP = " << getASAP(&SUnits[i]) << "\n";
dbgs() << "\t ALAP = " << getALAP(&SUnits[i]) << "\n";
dbgs() << "\t MOV = " << getMOV(&SUnits[i]) << "\n";
dbgs() << "\t D = " << getDepth(&SUnits[i]) << "\n";
dbgs() << "\t H = " << getHeight(&SUnits[i]) << "\n";
dbgs() << "\t ZLD = " << getZeroLatencyDepth(&SUnits[i]) << "\n";
dbgs() << "\t ZLH = " << getZeroLatencyHeight(&SUnits[i]) << "\n";
}
});
}
/// Compute the Pred_L(O) set, as defined in the paper. The set is defined
/// as the predecessors of the elements of NodeOrder that are not also in
/// NodeOrder.
static bool pred_L(SetVector<SUnit *> &NodeOrder,
SmallSetVector<SUnit *, 8> &Preds,
const NodeSet *S = nullptr) {
Preds.clear();
for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
I != E; ++I) {
for (SUnit::pred_iterator PI = (*I)->Preds.begin(), PE = (*I)->Preds.end();
PI != PE; ++PI) {
if (S && S->count(PI->getSUnit()) == 0)
continue;
if (ignoreDependence(*PI, true))
continue;
if (NodeOrder.count(PI->getSUnit()) == 0)
Preds.insert(PI->getSUnit());
}
// Back-edges are predecessors with an anti-dependence.
for (SUnit::const_succ_iterator IS = (*I)->Succs.begin(),
ES = (*I)->Succs.end();
IS != ES; ++IS) {
if (IS->getKind() != SDep::Anti)
continue;
if (S && S->count(IS->getSUnit()) == 0)
continue;
if (NodeOrder.count(IS->getSUnit()) == 0)
Preds.insert(IS->getSUnit());
}
}
return !Preds.empty();
}
/// Compute the Succ_L(O) set, as defined in the paper. The set is defined
/// as the successors of the elements of NodeOrder that are not also in
/// NodeOrder.
static bool succ_L(SetVector<SUnit *> &NodeOrder,
SmallSetVector<SUnit *, 8> &Succs,
const NodeSet *S = nullptr) {
Succs.clear();
for (SetVector<SUnit *>::iterator I = NodeOrder.begin(), E = NodeOrder.end();
I != E; ++I) {
for (SUnit::succ_iterator SI = (*I)->Succs.begin(), SE = (*I)->Succs.end();
SI != SE; ++SI) {
if (S && S->count(SI->getSUnit()) == 0)
continue;
if (ignoreDependence(*SI, false))
continue;
if (NodeOrder.count(SI->getSUnit()) == 0)
Succs.insert(SI->getSUnit());
}
for (SUnit::const_pred_iterator PI = (*I)->Preds.begin(),
PE = (*I)->Preds.end();
PI != PE; ++PI) {
if (PI->getKind() != SDep::Anti)
continue;
if (S && S->count(PI->getSUnit()) == 0)
continue;
if (NodeOrder.count(PI->getSUnit()) == 0)
Succs.insert(PI->getSUnit());
}
}
return !Succs.empty();
}
/// Return true if there is a path from the specified node to any of the nodes
/// in DestNodes. Keep track and return the nodes in any path.
static bool computePath(SUnit *Cur, SetVector<SUnit *> &Path,
SetVector<SUnit *> &DestNodes,
SetVector<SUnit *> &Exclude,
SmallPtrSet<SUnit *, 8> &Visited) {
if (Cur->isBoundaryNode())
return false;
if (Exclude.count(Cur) != 0)
return false;
if (DestNodes.count(Cur) != 0)
return true;
if (!Visited.insert(Cur).second)
return Path.count(Cur) != 0;
bool FoundPath = false;
for (auto &SI : Cur->Succs)
FoundPath |= computePath(SI.getSUnit(), Path, DestNodes, Exclude, Visited);
for (auto &PI : Cur->Preds)
if (PI.getKind() == SDep::Anti)
FoundPath |=
computePath(PI.getSUnit(), Path, DestNodes, Exclude, Visited);
if (FoundPath)
Path.insert(Cur);
return FoundPath;
}
/// Return true if Set1 is a subset of Set2.
template <class S1Ty, class S2Ty> static bool isSubset(S1Ty &Set1, S2Ty &Set2) {
for (typename S1Ty::iterator I = Set1.begin(), E = Set1.end(); I != E; ++I)
if (Set2.count(*I) == 0)
return false;
return true;
}
/// Compute the live-out registers for the instructions in a node-set.
/// The live-out registers are those that are defined in the node-set,
/// but not used. Except for use operands of Phis.
static void computeLiveOuts(MachineFunction &MF, RegPressureTracker &RPTracker,
NodeSet &NS) {
const TargetRegisterInfo *TRI = MF.getSubtarget().getRegisterInfo();
MachineRegisterInfo &MRI = MF.getRegInfo();
SmallVector<RegisterMaskPair, 8> LiveOutRegs;
SmallSet<unsigned, 4> Uses;
for (SUnit *SU : NS) {
const MachineInstr *MI = SU->getInstr();
if (MI->isPHI())
continue;
for (const MachineOperand &MO : MI->operands())
if (MO.isReg() && MO.isUse()) {
unsigned Reg = MO.getReg();
if (TargetRegisterInfo::isVirtualRegister(Reg))
Uses.insert(Reg);
else if (MRI.isAllocatable(Reg))
for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
Uses.insert(*Units);
}
}
for (SUnit *SU : NS)
for (const MachineOperand &MO : SU->getInstr()->operands())
if (MO.isReg() && MO.isDef() && !MO.isDead()) {
unsigned Reg = MO.getReg();
if (TargetRegisterInfo::isVirtualRegister(Reg)) {
if (!Uses.count(Reg))
LiveOutRegs.push_back(RegisterMaskPair(Reg,
LaneBitmask::getNone()));
} else if (MRI.isAllocatable(Reg)) {
for (MCRegUnitIterator Units(Reg, TRI); Units.isValid(); ++Units)
if (!Uses.count(*Units))
LiveOutRegs.push_back(RegisterMaskPair(*Units,
LaneBitmask::getNone()));
}
}
RPTracker.addLiveRegs(LiveOutRegs);
}
/// A heuristic to filter nodes in recurrent node-sets if the register
/// pressure of a set is too high.
void SwingSchedulerDAG::registerPressureFilter(NodeSetType &NodeSets) {
for (auto &NS : NodeSets) {
// Skip small node-sets since they won't cause register pressure problems.
if (NS.size() <= 2)
continue;
IntervalPressure RecRegPressure;
RegPressureTracker RecRPTracker(RecRegPressure);
RecRPTracker.init(&MF, &RegClassInfo, &LIS, BB, BB->end(), false, true);
computeLiveOuts(MF, RecRPTracker, NS);
RecRPTracker.closeBottom();
std::vector<SUnit *> SUnits(NS.begin(), NS.end());
llvm::sort(SUnits.begin(), SUnits.end(),
[](const SUnit *A, const SUnit *B) {
return A->NodeNum > B->NodeNum;
});
for (auto &SU : SUnits) {
// Since we're computing the register pressure for a subset of the
// instructions in a block, we need to set the tracker for each
// instruction in the node-set. The tracker is set to the instruction
// just after the one we're interested in.
MachineBasicBlock::const_iterator CurInstI = SU->getInstr();
RecRPTracker.setPos(std::next(CurInstI));
RegPressureDelta RPDelta;
ArrayRef<PressureChange> CriticalPSets;
RecRPTracker.getMaxUpwardPressureDelta(SU->getInstr(), nullptr, RPDelta,
CriticalPSets,
RecRegPressure.MaxSetPressure);
if (RPDelta.Excess.isValid()) {
LLVM_DEBUG(
dbgs() << "Excess register pressure: SU(" << SU->NodeNum << ") "
<< TRI->getRegPressureSetName(RPDelta.Excess.getPSet())
<< ":" << RPDelta.Excess.getUnitInc());
NS.setExceedPressure(SU);
break;
}
RecRPTracker.recede();
}
}
}
/// A heuristic to colocate node sets that have the same set of
/// successors.
void SwingSchedulerDAG::colocateNodeSets(NodeSetType &NodeSets) {
unsigned Colocate = 0;
for (int i = 0, e = NodeSets.size(); i < e; ++i) {
NodeSet &N1 = NodeSets[i];
SmallSetVector<SUnit *, 8> S1;
if (N1.empty() || !succ_L(N1, S1))
continue;
for (int j = i + 1; j < e; ++j) {
NodeSet &N2 = NodeSets[j];
if (N1.compareRecMII(N2) != 0)
continue;
SmallSetVector<SUnit *, 8> S2;
if (N2.empty() || !succ_L(N2, S2))
continue;
if (isSubset(S1, S2) && S1.size() == S2.size()) {
N1.setColocate(++Colocate);
N2.setColocate(Colocate);
break;
}
}
}
}
/// 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.
void SwingSchedulerDAG::checkNodeSets(NodeSetType &NodeSets) {
// Look for loops with a large MII.
if (MII < 17)
return;
// Check if the node-set contains only a simple add recurrence.
for (auto &NS : NodeSets) {
if (NS.getRecMII() > 2)
return;
if (NS.getMaxDepth() > MII)
return;
}
NodeSets.clear();
LLVM_DEBUG(dbgs() << "Clear recurrence node-sets\n");
return;
}
/// Add the nodes that do not belong to a recurrence set into groups
/// based upon connected componenets.
void SwingSchedulerDAG::groupRemainingNodes(NodeSetType &NodeSets) {
SetVector<SUnit *> NodesAdded;
SmallPtrSet<SUnit *, 8> Visited;
// Add the nodes that are on a path between the previous node sets and
// the current node set.
for (NodeSet &I : NodeSets) {
SmallSetVector<SUnit *, 8> N;
// Add the nodes from the current node set to the previous node set.
if (succ_L(I, N)) {
SetVector<SUnit *> Path;
for (SUnit *NI : N) {
Visited.clear();
computePath(NI, Path, NodesAdded, I, Visited);
}
if (!Path.empty())
I.insert(Path.begin(), Path.end());
}
// Add the nodes from the previous node set to the current node set.
N.clear();
if (succ_L(NodesAdded, N)) {
SetVector<SUnit *> Path;
for (SUnit *NI : N) {
Visited.clear();
computePath(NI, Path, I, NodesAdded, Visited);
}
if (!Path.empty())
I.insert(Path.begin(), Path.end());
}
NodesAdded.insert(I.begin(), I.end());
}
// Create a new node set with the connected nodes of any successor of a node
// in a recurrent set.
NodeSet NewSet;
SmallSetVector<SUnit *, 8> N;
if (succ_L(NodesAdded, N))
for (SUnit *I : N)
addConnectedNodes(I, NewSet, NodesAdded);
if (!NewSet.empty())
NodeSets.push_back(NewSet);
// Create a new node set with the connected nodes of any predecessor of a node
// in a recurrent set.
NewSet.clear();
if (pred_L(NodesAdded, N))
for (SUnit *I : N)
addConnectedNodes(I, NewSet, NodesAdded);
if (!NewSet.empty())
NodeSets.push_back(NewSet);
// Create new nodes sets with the connected nodes any remaining node that
// has no predecessor.
for (unsigned i = 0; i < SUnits.size(); ++i) {
SUnit *SU = &SUnits[i];
if (NodesAdded.count(SU) == 0) {
NewSet.clear();
addConnectedNodes(SU, NewSet, NodesAdded);
if (!NewSet.empty())
NodeSets.push_back(NewSet);
}
}
}
/// Add the node to the set, and add all is its connected nodes to the set.
void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet,
SetVector<SUnit *> &NodesAdded) {
NewSet.insert(SU);
NodesAdded.insert(SU);
for (auto &SI : SU->Succs) {
SUnit *Successor = SI.getSUnit();
if (!SI.isArtificial() && NodesAdded.count(Successor) == 0)
addConnectedNodes(Successor, NewSet, NodesAdded);
}
for (auto &PI : SU->Preds) {
SUnit *Predecessor = PI.getSUnit();
if (!PI.isArtificial() && NodesAdded.count(Predecessor) == 0)
addConnectedNodes(Predecessor, NewSet, NodesAdded);
}
}
/// Return true if Set1 contains elements in Set2. The elements in common
/// are returned in a different container.
static bool isIntersect(SmallSetVector<SUnit *, 8> &Set1, const NodeSet &Set2,
SmallSetVector<SUnit *, 8> &Result) {
Result.clear();
for (unsigned i = 0, e = Set1.size(); i != e; ++i) {
SUnit *SU = Set1[i];
if (Set2.count(SU) != 0)
Result.insert(SU);
}
return !Result.empty();
}
/// Merge the recurrence node sets that have the same initial node.
void SwingSchedulerDAG::fuseRecs(NodeSetType &NodeSets) {
for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
++I) {
NodeSet &NI = *I;
for (NodeSetType::iterator J = I + 1; J != E;) {
NodeSet &NJ = *J;
if (NI.getNode(0)->NodeNum == NJ.getNode(0)->NodeNum) {
if (NJ.compareRecMII(NI) > 0)
NI.setRecMII(NJ.getRecMII());
for (NodeSet::iterator NII = J->begin(), ENI = J->end(); NII != ENI;
++NII)
I->insert(*NII);
NodeSets.erase(J);
E = NodeSets.end();
} else {
++J;
}
}
}
}
/// Remove nodes that have been scheduled in previous NodeSets.
void SwingSchedulerDAG::removeDuplicateNodes(NodeSetType &NodeSets) {
for (NodeSetType::iterator I = NodeSets.begin(), E = NodeSets.end(); I != E;
++I)
for (NodeSetType::iterator J = I + 1; J != E;) {
J->remove_if([&](SUnit *SUJ) { return I->count(SUJ); });
if (J->empty()) {
NodeSets.erase(J);
E = NodeSets.end();
} else {
++J;
}
}
}
/// 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.
void SwingSchedulerDAG::computeNodeOrder(NodeSetType &NodeSets) {
SmallSetVector<SUnit *, 8> R;
NodeOrder.clear();
for (auto &Nodes : NodeSets) {
LLVM_DEBUG(dbgs() << "NodeSet size " << Nodes.size() << "\n");
OrderKind Order;
SmallSetVector<SUnit *, 8> N;
if (pred_L(NodeOrder, N) && isSubset(N, Nodes)) {
R.insert(N.begin(), N.end());
Order = BottomUp;
LLVM_DEBUG(dbgs() << " Bottom up (preds) ");
} else if (succ_L(NodeOrder, N) && isSubset(N, Nodes)) {
R.insert(N.begin(), N.end());
Order = TopDown;
LLVM_DEBUG(dbgs() << " Top down (succs) ");
} else if (isIntersect(N, Nodes, R)) {
// If some of the successors are in the existing node-set, then use the
// top-down ordering.
Order = TopDown;
LLVM_DEBUG(dbgs() << " Top down (intersect) ");
} else if (NodeSets.size() == 1) {
for (auto &N : Nodes)
if (N->Succs.size() == 0)
R.insert(N);
Order = BottomUp;
LLVM_DEBUG(dbgs() << " Bottom up (all) ");
} else {
// Find the node with the highest ASAP.
SUnit *maxASAP = nullptr;
for (SUnit *SU : Nodes) {
if (maxASAP == nullptr || getASAP(SU) > getASAP(maxASAP) ||
(getASAP(SU) == getASAP(maxASAP) && SU->NodeNum > maxASAP->NodeNum))
maxASAP = SU;
}
R.insert(maxASAP);
Order = BottomUp;
LLVM_DEBUG(dbgs() << " Bottom up (default) ");
}
while (!R.empty()) {
if (Order == TopDown) {
// Choose the node with the maximum height. If more than one, choose
// the node wiTH the maximum ZeroLatencyHeight. If still more than one,
// choose the node with the lowest MOV.
while (!R.empty()) {
SUnit *maxHeight = nullptr;
for (SUnit *I : R) {
if (maxHeight == nullptr || getHeight(I) > getHeight(maxHeight))
maxHeight = I;
else if (getHeight(I) == getHeight(maxHeight) &&
getZeroLatencyHeight(I) > getZeroLatencyHeight(maxHeight))
maxHeight = I;
else if (getHeight(I) == getHeight(maxHeight) &&
getZeroLatencyHeight(I) ==
getZeroLatencyHeight(maxHeight) &&
getMOV(I) < getMOV(maxHeight))
maxHeight = I;
}
NodeOrder.insert(maxHeight);
LLVM_DEBUG(dbgs() << maxHeight->NodeNum << " ");
R.remove(maxHeight);
for (const auto &I : maxHeight->Succs) {
if (Nodes.count(I.getSUnit()) == 0)
continue;
if (NodeOrder.count(I.getSUnit()) != 0)
continue;
if (ignoreDependence(I, false))
continue;
R.insert(I.getSUnit());
}
// Back-edges are predecessors with an anti-dependence.
for (const auto &I : maxHeight->Preds) {
if (I.getKind() != SDep::Anti)
continue;
if (Nodes.count(I.getSUnit()) == 0)
continue;
if (NodeOrder.count(I.getSUnit()) != 0)
continue;
R.insert(I.getSUnit());
}
}
Order = BottomUp;
LLVM_DEBUG(dbgs() << "\n Switching order to bottom up ");
SmallSetVector<SUnit *, 8> N;
if (pred_L(NodeOrder, N, &Nodes))
R.insert(N.begin(), N.end());
} else {
// Choose the node with the maximum depth. If more than one, choose
// the node with the maximum ZeroLatencyDepth. If still more than one,
// choose the node with the lowest MOV.
while (!R.empty()) {
SUnit *maxDepth = nullptr;
for (SUnit *I : R) {
if (maxDepth == nullptr || getDepth(I) > getDepth(maxDepth))
maxDepth = I;
else if (getDepth(I) == getDepth(maxDepth) &&
getZeroLatencyDepth(I) > getZeroLatencyDepth(maxDepth))
maxDepth = I;
else if (getDepth(I) == getDepth(maxDepth) &&
getZeroLatencyDepth(I) == getZeroLatencyDepth(maxDepth) &&
getMOV(I) < getMOV(maxDepth))
maxDepth = I;
}
NodeOrder.insert(maxDepth);
LLVM_DEBUG(dbgs() << maxDepth->NodeNum << " ");
R.remove(maxDepth);
if (Nodes.isExceedSU(maxDepth)) {
Order = TopDown;
R.clear();
R.insert(Nodes.getNode(0));
break;
}
for (const auto &I : maxDepth->Preds) {
if (Nodes.count(I.getSUnit()) == 0)
continue;
if (NodeOrder.count(I.getSUnit()) != 0)
continue;
R.insert(I.getSUnit());
}
// Back-edges are predecessors with an anti-dependence.
for (const auto &I : maxDepth->Succs) {
if (I.getKind() != SDep::Anti)
continue;
if (Nodes.count(I.getSUnit()) == 0)
continue;
if (NodeOrder.count(I.getSUnit()) != 0)
continue;
R.insert(I.getSUnit());
}
}
Order = TopDown;
LLVM_DEBUG(dbgs() << "\n Switching order to top down ");
SmallSetVector<SUnit *, 8> N;
if (succ_L(NodeOrder, N, &Nodes))
R.insert(N.begin(), N.end());
}
}
LLVM_DEBUG(dbgs() << "\nDone with Nodeset\n");
}
LLVM_DEBUG({
dbgs() << "Node order: ";
for (SUnit *I : NodeOrder)
dbgs() << " " << I->NodeNum << " ";
dbgs() << "\n";
});
}
/// Process the nodes in the computed order and create the pipelined schedule
/// of the instructions, if possible. Return true if a schedule is found.
bool SwingSchedulerDAG::schedulePipeline(SMSchedule &Schedule) {
if (NodeOrder.empty())
return false;
bool scheduleFound = false;
// Keep increasing II until a valid schedule is found.
for (unsigned II = MII; II < MII + 10 && !scheduleFound; ++II) {
Schedule.reset();
Schedule.setInitiationInterval(II);
LLVM_DEBUG(dbgs() << "Try to schedule with " << II << "\n");
SetVector<SUnit *>::iterator NI = NodeOrder.begin();
SetVector<SUnit *>::iterator NE = NodeOrder.end();
do {
SUnit *SU = *NI;
// Compute the schedule time for the instruction, which is based
// upon the scheduled time for any predecessors/successors.
int EarlyStart = INT_MIN;
int LateStart = INT_MAX;
// These values are set when the size of the schedule window is limited
// due to chain dependences.
int SchedEnd = INT_MAX;
int SchedStart = INT_MIN;
Schedule.computeStart(SU, &EarlyStart, &LateStart, &SchedEnd, &SchedStart,
II, this);
LLVM_DEBUG({
dbgs() << "Inst (" << SU->NodeNum << ") ";
SU->getInstr()->dump();
dbgs() << "\n";
});
LLVM_DEBUG({
dbgs() << "\tes: " << EarlyStart << " ls: " << LateStart
<< " me: " << SchedEnd << " ms: " << SchedStart << "\n";
});
if (EarlyStart > LateStart || SchedEnd < EarlyStart ||
SchedStart > LateStart)
scheduleFound = false;
else if (EarlyStart != INT_MIN && LateStart == INT_MAX) {
SchedEnd = std::min(SchedEnd, EarlyStart + (int)II - 1);
scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
} else if (EarlyStart == INT_MIN && LateStart != INT_MAX) {
SchedStart = std::max(SchedStart, LateStart - (int)II + 1);
scheduleFound = Schedule.insert(SU, LateStart, SchedStart, II);
} else if (EarlyStart != INT_MIN && LateStart != INT_MAX) {
SchedEnd =
std::min(SchedEnd, std::min(LateStart, EarlyStart + (int)II - 1));
// When scheduling a Phi it is better to start at the late cycle and go
// backwards. The default order may insert the Phi too far away from
// its first dependence.
if (SU->getInstr()->isPHI())
scheduleFound = Schedule.insert(SU, SchedEnd, EarlyStart, II);
else
scheduleFound = Schedule.insert(SU, EarlyStart, SchedEnd, II);
} else {
int FirstCycle = Schedule.getFirstCycle();
scheduleFound = Schedule.insert(SU, FirstCycle + getASAP(SU),
FirstCycle + getASAP(SU) + II - 1, II);
}
// Even if we find a schedule, make sure the schedule doesn't exceed the
// allowable number of stages. We keep trying if this happens.
if (scheduleFound)
if (SwpMaxStages > -1 &&
Schedule.getMaxStageCount() > (unsigned)SwpMaxStages)
scheduleFound = false;
LLVM_DEBUG({
if (!scheduleFound)
dbgs() << "\tCan't schedule\n";
});
} while (++NI != NE && scheduleFound);
// If a schedule is found, check if it is a valid schedule too.
if (scheduleFound)
scheduleFound = Schedule.isValidSchedule(this);
}
LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound << "\n");
if (scheduleFound)
Schedule.finalizeSchedule(this);
else
Schedule.reset();
return scheduleFound && Schedule.getMaxStageCount() > 0;
}
/// Given a schedule for the loop, generate a new version of the loop,
/// and replace the old version. This function generates a prolog
/// that contains the initial iterations in the pipeline, and kernel
/// loop, and the epilogue that contains the code for the final
/// iterations.
void SwingSchedulerDAG::generatePipelinedLoop(SMSchedule &Schedule) {
// Create a new basic block for the kernel and add it to the CFG.
MachineBasicBlock *KernelBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
unsigned MaxStageCount = Schedule.getMaxStageCount();
// Remember the registers that are used in different stages. The index is
// the iteration, or stage, that the instruction is scheduled in. This is
// a map between register names in the original block and the names created
// in each stage of the pipelined loop.
ValueMapTy *VRMap = new ValueMapTy[(MaxStageCount + 1) * 2];
InstrMapTy InstrMap;
SmallVector<MachineBasicBlock *, 4> PrologBBs;
// Generate the prolog instructions that set up the pipeline.
generateProlog(Schedule, MaxStageCount, KernelBB, VRMap, PrologBBs);
MF.insert(BB->getIterator(), KernelBB);
// Rearrange the instructions to generate the new, pipelined loop,
// and update register names as needed.
for (int Cycle = Schedule.getFirstCycle(),
LastCycle = Schedule.getFinalCycle();
Cycle <= LastCycle; ++Cycle) {
std::deque<SUnit *> &CycleInstrs = Schedule.getInstructions(Cycle);
// This inner loop schedules each instruction in the cycle.
for (SUnit *CI : CycleInstrs) {
if (CI->getInstr()->isPHI())
continue;
unsigned StageNum = Schedule.stageScheduled(getSUnit(CI->getInstr()));
MachineInstr *NewMI = cloneInstr(CI->getInstr(), MaxStageCount, StageNum);
updateInstruction(NewMI, false, MaxStageCount, StageNum, Schedule, VRMap);
KernelBB->push_back(NewMI);
InstrMap[NewMI] = CI->getInstr();
}
}
// Copy any terminator instructions to the new kernel, and update
// names as needed.
for (MachineBasicBlock::iterator I = BB->getFirstTerminator(),
E = BB->instr_end();
I != E; ++I) {
MachineInstr *NewMI = MF.CloneMachineInstr(&*I);
updateInstruction(NewMI, false, MaxStageCount, 0, Schedule, VRMap);
KernelBB->push_back(NewMI);
InstrMap[NewMI] = &*I;
}
KernelBB->transferSuccessors(BB);
KernelBB->replaceSuccessor(BB, KernelBB);
generateExistingPhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule,
VRMap, InstrMap, MaxStageCount, MaxStageCount, false);
generatePhis(KernelBB, PrologBBs.back(), KernelBB, KernelBB, Schedule, VRMap,
InstrMap, MaxStageCount, MaxStageCount, false);
LLVM_DEBUG(dbgs() << "New block\n"; KernelBB->dump(););
SmallVector<MachineBasicBlock *, 4> EpilogBBs;
// Generate the epilog instructions to complete the pipeline.
generateEpilog(Schedule, MaxStageCount, KernelBB, VRMap, EpilogBBs,
PrologBBs);
// We need this step because the register allocation doesn't handle some
// situations well, so we insert copies to help out.
splitLifetimes(KernelBB, EpilogBBs, Schedule);
// Remove dead instructions due to loop induction variables.
removeDeadInstructions(KernelBB, EpilogBBs);
// Add branches between prolog and epilog blocks.
addBranches(PrologBBs, KernelBB, EpilogBBs, Schedule, VRMap);
// Remove the original loop since it's no longer referenced.
for (auto &I : *BB)
LIS.RemoveMachineInstrFromMaps(I);
BB->clear();
BB->eraseFromParent();
delete[] VRMap;
}
/// Generate the pipeline prolog code.
void SwingSchedulerDAG::generateProlog(SMSchedule &Schedule, unsigned LastStage,
MachineBasicBlock *KernelBB,
ValueMapTy *VRMap,
MBBVectorTy &PrologBBs) {
MachineBasicBlock *PreheaderBB = MLI->getLoopFor(BB)->getLoopPreheader();
assert(PreheaderBB != nullptr &&
"Need to add code to handle loops w/o preheader");
MachineBasicBlock *PredBB = PreheaderBB;
InstrMapTy InstrMap;
// Generate a basic block for each stage, not including the last stage,
// which will be generated in the kernel. Each basic block may contain
// instructions from multiple stages/iterations.
for (unsigned i = 0; i < LastStage; ++i) {
// Create and insert the prolog basic block prior to the original loop
// basic block. The original loop is removed later.
MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock(BB->getBasicBlock());
PrologBBs.push_back(NewBB);
MF.insert(BB->getIterator(), NewBB);
NewBB->transferSuccessors(PredBB);
PredBB->addSuccessor(NewBB);
PredBB = NewBB;
// Generate instructions for each appropriate stage. Process instructions
// in original program order.
for (int StageNum = i; StageNum >= 0; --StageNum) {
for (MachineBasicBlock::iterator BBI = BB->instr_begin(),
BBE = BB->getFirstTerminator();
BBI != BBE; ++BBI) {
if (Schedule.isScheduledAtStage(getSUnit(&*BBI), (unsigned)StageNum)) {
if (BBI->isPHI())
continue;
MachineInstr *NewMI =
cloneAndChangeInstr(&*BBI, i, (unsigned)StageNum, Schedule);
updateInstruction(NewMI, false, i, (unsigned)StageNum, Schedule,
VRMap);
NewBB->push_back(NewMI);
InstrMap[NewMI] = &*BBI;
}
}
}
rewritePhiValues(NewBB, i, Schedule, VRMap, InstrMap);
LLVM_DEBUG({
dbgs() << "prolog:\n";
NewBB->dump();
});
}
PredBB->replaceSuccessor(BB, KernelBB);
// Check if we need to remove the branch from the preheader to the original
// loop, and replace it with a branch to the new loop.
unsigned numBranches = TII->removeBranch(*PreheaderBB);
if (numBranches) {
SmallVector<MachineOperand, 0> Cond;
TII->insertBranch(*PreheaderBB, PrologBBs[0], nullptr, Cond, DebugLoc());
}
}
/// Generate the pipeline epilog code. The epilog code finishes the iterations
/// that were started in either the prolog or the kernel. We create a basic
/// block for each stage that needs to complete.
void SwingSchedulerDAG::generateEpilog(SMSchedule &Schedule, unsigned LastStage,
MachineBasicBlock *KernelBB,
ValueMapTy *VRMap,
MBBVectorTy &EpilogBBs,
MBBVectorTy &PrologBBs) {
// We need to change the branch from the kernel to the first epilog block, so
// this call to analyze branch uses the kernel rather than the original BB.
MachineBasicBlock *TBB = nullptr, *FBB = nullptr;
SmallVector<MachineOperand, 4> Cond;
bool checkBranch = TII->analyzeBranch(*KernelBB, TBB, FBB, Cond);
assert(!checkBranch && "generateEpilog must be able to analyze the branch");
if (checkBranch)
return;
MachineBasicBlock::succ_iterator LoopExitI = KernelBB->succ_begin();
if (*LoopExitI == KernelBB)
++LoopExitI;
assert(LoopExitI != KernelBB->succ_end() && "Expecting a successor");
MachineBasicBlock *LoopExitBB = *LoopExitI;
MachineBasicBlock *PredBB = KernelBB;
MachineBasicBlock *EpilogStart = LoopExitBB;
InstrMapTy InstrMap;
// Generate a basic block for each stage, not including the last stage,
// which was generated for the kernel. Each basic block may contain
// instructions from multiple stages/iterations.
int EpilogStage = LastStage + 1;
for (unsigned i = LastStage; i >= 1; --i, ++EpilogStage) {
MachineBasicBlock *NewBB = MF.CreateMachineBasicBlock();
EpilogBBs.push_back(NewBB);
MF.insert(BB->getIterator(), NewBB);
PredBB->replaceSuccessor(LoopExitBB, NewBB);
NewBB->addSuccessor(LoopExitBB);
if (EpilogStart == LoopExitBB)
EpilogStart = NewBB;
// Add instructions to the epilog depending on the current block.
// Process instructions in original program order.
for (unsigned StageNum = i; StageNum <= LastStage; ++StageNum) {
for (auto &BBI : *BB) {
if (BBI.isPHI())
continue;
MachineInstr *In = &BBI;
if (Schedule.isScheduledAtStage(getSUnit(In), StageNum)) {
// Instructions with memoperands in the epilog are updated with
// conservative values.
MachineInstr *NewMI = cloneInstr(In, UINT_MAX, 0);
updateInstruction(NewMI, i == 1, EpilogStage, 0, Schedule, VRMap);
NewBB->push_back(NewMI);
InstrMap[NewMI] = In;
}
}
}
generateExistingPhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, Schedule,
VRMap, InstrMap, LastStage, EpilogStage, i == 1);
generatePhis(NewBB, PrologBBs[i - 1], PredBB, KernelBB, Schedule, VRMap,
InstrMap, LastStage, EpilogStage, i == 1);
PredBB = NewBB;
LLVM_DEBUG({
dbgs() << "epilog:\n";
NewBB->dump();
});
}
// Fix any Phi nodes in the loop exit block.
for (MachineInstr &MI : *LoopExitBB) {
if (!MI.isPHI())
break;
for (unsigned i = 2, e = MI.getNumOperands() + 1; i != e; i += 2) {
MachineOperand &MO = MI.getOperand(i);
if (MO.getMBB() == BB)
MO.setMBB(PredBB);
}
}
// Create a branch to the new epilog from the kernel.
// Remove the original branch and add a new branch to the epilog.
TII->removeBranch(*KernelBB);
TII->insertBranch(*KernelBB, KernelBB, EpilogStart, Cond, DebugLoc());
// Add a branch to the loop exit.
if (EpilogBBs.size() > 0) {
MachineBasicBlock *LastEpilogBB = EpilogBBs.back();
SmallVector<MachineOperand, 4> Cond1;
TII->insertBranch(*LastEpilogBB, LoopExitBB, nullptr, Cond1, DebugLoc());
}
}
/// Replace all uses of FromReg that appear outside the specified
/// basic block with ToReg.
static void replaceRegUsesAfterLoop(unsigned FromReg, unsigned ToReg,
MachineBasicBlock *MBB,
MachineRegisterInfo &MRI,
LiveIntervals &LIS) {
for (MachineRegisterInfo::use_iterator I = MRI.use_begin(FromReg),
E = MRI.use_end();
I != E;) {
MachineOperand &O = *I;
++I;
if (O.getParent()->getParent() != MBB)
O.setReg(ToReg);
}
if (!LIS.hasInterval(ToReg))
LIS.createEmptyInterval(ToReg);
}
/// Return true if the register has a use that occurs outside the
/// specified loop.
static bool hasUseAfterLoop(unsigned Reg, MachineBasicBlock *BB,
MachineRegisterInfo &MRI) {
for (MachineRegisterInfo::use_iterator I = MRI.use_begin(Reg),
E = MRI.use_end();
I != E; ++I)
if (I->getParent()->getParent() != BB)
return true;
return false;
}
/// Generate Phis for the specific block in the generated pipelined code.
/// This function looks at the Phis from the original code to guide the
/// creation of new Phis.
void SwingSchedulerDAG::generateExistingPhis(
MachineBasicBlock *NewBB, MachineBasicBlock *BB1, MachineBasicBlock *BB2,
MachineBasicBlock *KernelBB, SMSchedule &Schedule, ValueMapTy *VRMap,
InstrMapTy &InstrMap, unsigned LastStageNum, unsigned CurStageNum,
bool IsLast) {
// Compute the stage number for the initial value of the Phi, which