Google Git Google Git
Sign in
llvm/llvm-project/792bf8ef030d7c2aa12abbab7662ffbcbe2d8b21/./llvm/lib/CodeGen/MachinePipeliner.cpp
blob: 9b9392fb8c3255c52dc2815de84bbd6d5614ac76 [file]
//===- MachinePipeliner.cpp - Machine Software Pipeliner Pass -------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// An implementation of the Swing Modulo Scheduling (SMS) software pipeliner.
//
// 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/CodeGen/MachinePipeliner.h"
#include "llvm/ADT/ArrayRef.h"
#include "llvm/ADT/BitVector.h"
#include "llvm/ADT/DenseMap.h"
#include "llvm/ADT/PriorityQueue.h"
#include "llvm/ADT/STLExtras.h"
#include "llvm/ADT/SetOperations.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/OptimizationRemarkEmitter.h"
#include "llvm/Analysis/ValueTracking.h"
#include "llvm/CodeGen/DFAPacketizer.h"
#include "llvm/CodeGen/LiveIntervals.h"
#include "llvm/CodeGen/MachineBasicBlock.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/MachinePassManager.h"
#include "llvm/CodeGen/MachineRegisterInfo.h"
#include "llvm/CodeGen/ModuloSchedule.h"
#include "llvm/CodeGen/Register.h"
#include "llvm/CodeGen/RegisterClassInfo.h"
#include "llvm/CodeGen/RegisterPressure.h"
#include "llvm/CodeGen/ScheduleDAG.h"
#include "llvm/CodeGen/ScheduleDAGMutation.h"
#include "llvm/CodeGen/TargetInstrInfo.h"
#include "llvm/CodeGen/TargetOpcodes.h"
#include "llvm/CodeGen/TargetPassConfig.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/Function.h"
#include "llvm/InitializePasses.h"
#include "llvm/MC/LaneBitmask.h"
#include "llvm/MC/MCInstrDesc.h"
#include "llvm/MC/MCInstrItineraries.h"
#include "llvm/Pass.h"
#include "llvm/Support/CommandLine.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Support/Debug.h"
#include "llvm/Support/raw_ostream.h"
#include <algorithm>
#include <cassert>
#include <climits>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iterator>
#include <map>
#include <memory>
#include <sstream>
#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");
STATISTIC(NumFailBranch, "Pipeliner abort due to unknown branch");
STATISTIC(NumFailLoop, "Pipeliner abort due to unsupported loop");
STATISTIC(NumFailPreheader, "Pipeliner abort due to missing preheader");
STATISTIC(NumFailLargeMaxMII, "Pipeliner abort due to MaxMII too large");
STATISTIC(NumFailZeroMII, "Pipeliner abort due to zero MII");
STATISTIC(NumFailNoSchedule, "Pipeliner abort due to no schedule found");
STATISTIC(NumFailZeroStage, "Pipeliner abort due to zero stage");
STATISTIC(NumFailLargeMaxStage, "Pipeliner abort due to too many stages");
STATISTIC(NumFailTooManyStores, "Pipeliner abort due to too many stores");
/// A command line option to turn software pipelining on or off.
static cl::opt<bool> EnableSWP("enable-pipeliner", cl::Hidden, cl::init(true),
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 force pipeliner to use specified initial
/// interval.
static cl::opt<int> SwpForceII("pipeliner-force-ii",
cl::desc("Force pipeliner to use specified II."),
cl::Hidden, cl::init(-1));
/// 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::desc("Ignore RecMII"));
static cl::opt<bool> SwpShowResMask("pipeliner-show-mask", cl::Hidden,
cl::init(false));
static cl::opt<bool> SwpDebugResource("pipeliner-dbg-res", cl::Hidden,
cl::init(false));
static cl::opt<bool> EmitTestAnnotations(
"pipeliner-annotate-for-testing", cl::Hidden, cl::init(false),
cl::desc("Instead of emitting the pipelined code, annotate instructions "
"with the generated schedule for feeding into the "
"-modulo-schedule-test pass"));
static cl::opt<bool> ExperimentalCodeGen(
"pipeliner-experimental-cg", cl::Hidden, cl::init(false),
cl::desc(
"Use the experimental peeling code generator for software pipelining"));
static cl::opt<int> SwpIISearchRange("pipeliner-ii-search-range",
cl::desc("Range to search for II"),
cl::Hidden, cl::init(10));
static cl::opt<bool>
LimitRegPressure("pipeliner-register-pressure", cl::Hidden, cl::init(false),
cl::desc("Limit register pressure of scheduled loop"));
static cl::opt<int>
RegPressureMargin("pipeliner-register-pressure-margin", cl::Hidden,
cl::init(5),
cl::desc("Margin representing the unused percentage of "
"the register pressure limit"));
static cl::opt<bool>
MVECodeGen("pipeliner-mve-cg", cl::Hidden, cl::init(false),
cl::desc("Use the MVE code generator for software pipelining"));
/// A command line argument to limit the number of store instructions in the
/// target basic block.
static cl::opt<unsigned> SwpMaxNumStores(
"pipeliner-max-num-stores",
cl::desc("Maximum number of stores allwed in the target loop."), cl::Hidden,
cl::init(200));
// A command line option to enable the CopyToPhi DAG mutation.
static cl::opt<bool>
SwpEnableCopyToPhi("pipeliner-enable-copytophi", cl::ReallyHidden,
cl::init(true),
cl::desc("Enable CopyToPhi DAG Mutation"));
/// A command line argument to force pipeliner to use specified issue
/// width.
static cl::opt<int> SwpForceIssueWidth(
"pipeliner-force-issue-width",
cl::desc("Force pipeliner to use specified issue width."), cl::Hidden,
cl::init(-1));
/// A command line argument to set the window scheduling option.
static cl::opt<WindowSchedulingFlag> WindowSchedulingOption(
"window-sched", cl::Hidden, cl::init(WindowSchedulingFlag::WS_On),
cl::desc("Set how to use window scheduling algorithm."),
cl::values(clEnumValN(WindowSchedulingFlag::WS_Off, "off",
"Turn off window algorithm."),
clEnumValN(WindowSchedulingFlag::WS_On, "on",
"Use window algorithm after SMS algorithm fails."),
clEnumValN(WindowSchedulingFlag::WS_Force, "force",
"Use window algorithm instead of SMS algorithm.")));
unsigned SwingSchedulerDAG::Circuits::MaxPaths = 5;
char MachinePipelinerLegacy::ID = 0;
char &llvm::MachinePipelinerID = MachinePipelinerLegacy::ID;
INITIALIZE_PASS_BEGIN(MachinePipelinerLegacy, DEBUG_TYPE,
"Modulo Software Pipelining", false, false)
INITIALIZE_PASS_DEPENDENCY(AAResultsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineLoopInfoWrapperPass)
INITIALIZE_PASS_DEPENDENCY(LiveIntervalsWrapperPass)
INITIALIZE_PASS_DEPENDENCY(MachineRegisterClassInfoWrapperPass)
INITIALIZE_PASS_END(MachinePipelinerLegacy, DEBUG_TYPE,
"Modulo Software Pipelining", false, false)
namespace {
/// This class holds an SUnit corresponding to a memory operation and other
/// information related to the instruction.
struct SUnitWithMemInfo {
SUnit *SU;
SmallVector<const Value *, 2> UnderlyingObjs;
/// The value of a memory operand.
const Value *MemOpValue = nullptr;
/// The offset of a memory operand.
int64_t MemOpOffset = 0;
AAMDNodes AATags;
/// True if all the underlying objects are identified.
bool IsAllIdentified = false;
SUnitWithMemInfo(SUnit *SU);
bool isTriviallyDisjoint(const SUnitWithMemInfo &Other) const;
bool isUnknown() const { return MemOpValue == nullptr; }
private:
bool getUnderlyingObjects();
};
/// Add loop-carried chain dependencies. This class handles the same type of
/// dependencies added by `ScheduleDAGInstrs::buildSchedGraph`, but takes into
/// account dependencies across iterations.
class LoopCarriedOrderDepsTracker {
// Type of instruction that is relevant to order-dependencies
enum class InstrTag {
Barrier = 0, ///< A barrier event instruction.
LoadOrStore = 1, ///< An instruction that may load or store memory, but is
///< not a barrier event.
FPExceptions = 2, ///< An instruction that does not match above, but may
///< raise floatin-point exceptions.
};
struct TaggedSUnit : PointerIntPair<SUnit *, 2> {
TaggedSUnit(SUnit *SU, InstrTag Tag)
: PointerIntPair<SUnit *, 2>(SU, unsigned(Tag)) {}
InstrTag getTag() const { return InstrTag(getInt()); }
};
/// Holds instructions that may form loop-carried order-dependencies, but not
/// global barriers.
struct NoBarrierInstsChunk {
SmallVector<SUnitWithMemInfo, 4> Loads;
SmallVector<SUnitWithMemInfo, 4> Stores;
SmallVector<SUnitWithMemInfo, 1> FPExceptions;
void append(SUnit *SU);
};
SwingSchedulerDAG *DAG;
BatchAAResults *BAA;
std::vector<SUnit> &SUnits;
/// The size of SUnits, for convenience.
const unsigned N;
/// Loop-carried Edges.
std::vector<BitVector> LoopCarried;
/// Instructions related to chain dependencies. They are one of the
/// following:
///
/// 1. Barrier event.
/// 2. Load, but neither a barrier event, invariant load, nor may load trap
/// value.
/// 3. Store, but not a barrier event.
/// 4. None of them, but may raise floating-point exceptions.
///
/// This is used when analyzing loop-carried dependencies that access global
/// barrier instructions.
std::vector<TaggedSUnit> TaggedSUnits;
const TargetInstrInfo *TII = nullptr;
const TargetRegisterInfo *TRI = nullptr;
public:
LoopCarriedOrderDepsTracker(SwingSchedulerDAG *SSD, BatchAAResults *BAA,
const TargetInstrInfo *TII,
const TargetRegisterInfo *TRI);
/// The main function to compute loop-carried order-dependencies.
void computeDependencies();
const BitVector &getLoopCarried(unsigned Idx) const {
return LoopCarried[Idx];
}
private:
/// Tags to \p SU if the instruction may affect the order-dependencies.
std::optional<InstrTag> getInstrTag(SUnit *SU) const;
void addLoopCarriedDepenenciesForChunks(const NoBarrierInstsChunk &From,
const NoBarrierInstsChunk &To);
/// Add a loop-carried order dependency between \p Src and \p Dst if we
/// cannot prove they are independent.
void addDependenciesBetweenSUs(const SUnitWithMemInfo &Src,
const SUnitWithMemInfo &Dst);
void computeDependenciesAux();
void setLoopCarriedDep(const SUnit *Src, const SUnit *Dst) {
LoopCarried[Src->NodeNum].set(Dst->NodeNum);
}
};
/// The main class in the implementation of the target independent
/// software pipeliner pass.
class MachinePipelinerImpl {
public:
MachineFunction *MF = nullptr;
MachineOptimizationRemarkEmitter *ORE = nullptr;
const MachineLoopInfo *MLI = nullptr;
const InstrItineraryData *InstrItins = nullptr;
const TargetInstrInfo *TII = nullptr;
RegisterClassInfo *RegClassInfo = nullptr;
LiveIntervals *LIS = nullptr;
AAResults *AA = nullptr;
const TargetMachine *TM = nullptr;
bool disabledByPragma = false;
unsigned II_setByPragma = 0;
#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;
std::unique_ptr<TargetInstrInfo::PipelinerLoopInfo> LoopPipelinerInfo =
nullptr;
};
LoopInfo LI;
MachinePipelinerImpl(MachineFunction &MF, const MachineLoopInfo &MLI,
LiveIntervals &LIS, AAResults &AA,
MachineOptimizationRemarkEmitter &ORE,
RegisterClassInfo &RegClassInfo);
/// Run the software pipeliner over all loops in the function.
bool run();
private:
void preprocessPhiNodes(MachineBasicBlock &B);
bool canPipelineLoop(MachineLoop &L);
bool scheduleLoop(MachineLoop &L);
bool swingModuloScheduler(MachineLoop &L);
void setPragmaPipelineOptions(MachineLoop &L);
bool runWindowScheduler(MachineLoop &L);
bool useSwingModuloScheduler();
bool useWindowScheduler(bool Changed);
};
} // end anonymous namespace
#ifndef NDEBUG
int MachinePipelinerImpl::NumTries = 0;
#endif
MachinePipelinerImpl::MachinePipelinerImpl(
MachineFunction &MF, const MachineLoopInfo &MLI, LiveIntervals &LIS,
AAResults &AA, MachineOptimizationRemarkEmitter &ORE,
RegisterClassInfo &RegClassInfo)
: MF(&MF), ORE(&ORE), MLI(&MLI), TII(MF.getSubtarget().getInstrInfo()),
RegClassInfo(&RegClassInfo), LIS(&LIS), AA(&AA), TM(&MF.getTarget()) {}
/// The "main" function for implementing Swing Modulo Scheduling.
bool MachinePipelinerImpl::run() {
bool Changed = false;
for (const auto &L : *MLI)
Changed |= scheduleLoop(*L);
return Changed;
}
static bool runMachinePipeliner(
MachineFunction &MF, function_ref<const MachineLoopInfo &()> GetMLI,
function_ref<LiveIntervals &()> GetLIS, function_ref<AAResults &()> GetAA,
function_ref<MachineOptimizationRemarkEmitter &()> GetORE,
function_ref<RegisterClassInfo &()> GetRCI) {
if (!EnableSWP)
return false;
if (MF.getFunction().getAttributes().hasFnAttr(Attribute::OptimizeForSize) &&
!EnableSWPOptSize.getPosition())
return false;
if (!MF.getSubtarget().enableMachinePipeliner())
return false;
// Cannot pipeline loops without instruction itineraries if we are using
// DFA for the pipeliner.
if (MF.getSubtarget().useDFAforSMS() &&
(!MF.getSubtarget().getInstrItineraryData() ||
MF.getSubtarget().getInstrItineraryData()->isEmpty()))
return false;
MachinePipelinerImpl MP(MF, GetMLI(), GetLIS(), GetAA(), GetORE(), GetRCI());
return MP.run();
}
bool MachinePipelinerLegacy::runOnMachineFunction(MachineFunction &MF) {
if (skipFunction(MF.getFunction()))
return false;
return runMachinePipeliner(
MF,
[&]() -> const MachineLoopInfo & {
return getAnalysis<MachineLoopInfoWrapperPass>().getLI();
},
[&]() -> LiveIntervals & {
return getAnalysis<LiveIntervalsWrapperPass>().getLIS();
},
[&]() -> AAResults & {
return getAnalysis<AAResultsWrapperPass>().getAAResults();
},
[&]() -> MachineOptimizationRemarkEmitter & {
return getAnalysis<MachineOptimizationRemarkEmitterPass>().getORE();
},
[&]() -> RegisterClassInfo & {
return getAnalysis<MachineRegisterClassInfoWrapperPass>().getRCI();
});
}
PreservedAnalyses
MachinePipelinerPass::run(MachineFunction &MF,
MachineFunctionAnalysisManager &MFAM) {
if (!runMachinePipeliner(
MF,
[&]() -> const MachineLoopInfo & {
return MFAM.getResult<MachineLoopAnalysis>(MF);
},
[&]() -> LiveIntervals & {
return MFAM.getResult<LiveIntervalsAnalysis>(MF);
},
[&]() -> AAResults & {
return MFAM
.getResult<FunctionAnalysisManagerMachineFunctionProxy>(MF)
.getManager()
.getResult<AAManager>(MF.getFunction());
},
[&]() -> MachineOptimizationRemarkEmitter & {
return MFAM.getResult<MachineOptimizationRemarkEmitterAnalysis>(MF);
},
[&]() -> RegisterClassInfo & {
return MFAM.getResult<MachineRegisterClassAnalysis>(MF);
}))
return PreservedAnalyses::all();
PreservedAnalyses PA = getMachineFunctionPassPreservedAnalyses();
PA.preserve<MachineRegisterClassAnalysis>();
return PA;
}
/// 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 MachinePipelinerImpl::scheduleLoop(MachineLoop &L) {
bool Changed = false;
for (const 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
setPragmaPipelineOptions(L);
if (!canPipelineLoop(L)) {
LLVM_DEBUG(dbgs() << "\n!!! Can not pipeline loop.\n");
ORE->emit([&]() {
return MachineOptimizationRemarkMissed(DEBUG_TYPE, "canPipelineLoop",
L.getStartLoc(), L.getHeader())
<< "Failed to pipeline loop";
});
LI.LoopPipelinerInfo.reset();
return Changed;
}
++NumTrytoPipeline;
if (useSwingModuloScheduler())
Changed = swingModuloScheduler(L);
if (useWindowScheduler(Changed))
Changed = runWindowScheduler(L);
LI.LoopPipelinerInfo.reset();
return Changed;
}
void MachinePipelinerImpl::setPragmaPipelineOptions(MachineLoop &L) {
// Reset the pragma for the next loop in iteration.
disabledByPragma = false;
II_setByPragma = 0;
MachineBasicBlock *LBLK = L.getTopBlock();
if (LBLK == nullptr)
return;
const BasicBlock *BBLK = LBLK->getBasicBlock();
if (BBLK == nullptr)
return;
const Instruction *TI = BBLK->getTerminator();
MDNode *LoopID = TI->getMetadata(LLVMContext::MD_loop);
if (LoopID == nullptr)
return;
assert(LoopID->getNumOperands() > 0 && "requires atleast one operand");
assert(LoopID->getOperand(0) == LoopID && "invalid loop");
for (const MDOperand &MDO : llvm::drop_begin(LoopID->operands())) {
MDNode *MD = dyn_cast<MDNode>(MDO);
if (MD == nullptr)
continue;
MDString *S = dyn_cast<MDString>(MD->getOperand(0));
if (S == nullptr)
continue;
if (S->getString() == "llvm.loop.pipeline.initiationinterval") {
assert(MD->getNumOperands() == 2 &&
"Pipeline initiation interval hint metadata should have two operands.");
II_setByPragma =
mdconst::extract<ConstantInt>(MD->getOperand(1))->getZExtValue();
assert(II_setByPragma >= 1 && "Pipeline initiation interval must be positive.");
} else if (S->getString() == "llvm.loop.pipeline.disable") {
disabledByPragma = true;
}
}
}
/// Depth-first search to detect cycles among PHI dependencies.
/// Returns true if a cycle is detected within the PHI-only subgraph.
static bool hasPHICycleDFS(
unsigned Reg, const DenseMap<unsigned, SmallVector<unsigned, 2>> &PhiDeps,
SmallSet<unsigned, 8> &Visited, SmallSet<unsigned, 8> &RecStack) {
// If Reg is not a PHI-def it cannot contribute to a PHI cycle.
auto It = PhiDeps.find(Reg);
if (It == PhiDeps.end())
return false;
if (RecStack.count(Reg))
return true; // backedge.
if (Visited.count(Reg))
return false;
Visited.insert(Reg);
RecStack.insert(Reg);
for (unsigned Dep : It->second) {
if (hasPHICycleDFS(Dep, PhiDeps, Visited, RecStack))
return true;
}
RecStack.erase(Reg);
return false;
}
static bool hasPHICycle(const MachineBasicBlock *LoopHeader,
const MachineRegisterInfo &MRI) {
DenseMap<unsigned, SmallVector<unsigned, 2>> PhiDeps;
// Collect PHI nodes and their dependencies.
for (const MachineInstr &MI : LoopHeader->phis()) {
unsigned DefReg = MI.getOperand(0).getReg();
auto Ins = PhiDeps.try_emplace(DefReg).first;
// PHI operands are (Reg, MBB) pairs starting at index 1.
for (unsigned I = 1; I < MI.getNumOperands(); I += 2)
Ins->second.push_back(MI.getOperand(I).getReg());
}
// DFS to detect cycles among PHI nodes.
SmallSet<unsigned, 8> Visited, RecStack;
// Start DFS from each PHI-def.
for (const auto &KV : PhiDeps) {
unsigned Reg = KV.first;
if (hasPHICycleDFS(Reg, PhiDeps, Visited, RecStack))
return true;
}
return false;
}
/// 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 MachinePipelinerImpl::canPipelineLoop(MachineLoop &L) {
if (L.getNumBlocks() != 1) {
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
L.getStartLoc(), L.getHeader())
<< "Not a single basic block: "
<< ore::NV("NumBlocks", L.getNumBlocks());
});
return false;
}
if (hasPHICycle(L.getHeader(), MF->getRegInfo())) {
LLVM_DEBUG(dbgs() << "Cannot pipeline loop due to PHI cycle\n");
return false;
}
if (disabledByPragma) {
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
L.getStartLoc(), L.getHeader())
<< "Disabled by Pragma.";
});
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)) {
LLVM_DEBUG(dbgs() << "Unable to analyzeBranch, can NOT pipeline Loop\n");
NumFailBranch++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
L.getStartLoc(), L.getHeader())
<< "The branch can't be understood";
});
return false;
}
LI.LoopInductionVar = nullptr;
LI.LoopCompare = nullptr;
LI.LoopPipelinerInfo = TII->analyzeLoopForPipelining(L.getTopBlock());
if (!LI.LoopPipelinerInfo) {
LLVM_DEBUG(dbgs() << "Unable to analyzeLoop, can NOT pipeline Loop\n");
NumFailLoop++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
L.getStartLoc(), L.getHeader())
<< "The loop structure is not supported";
});
return false;
}
if (!L.getLoopPreheader()) {
LLVM_DEBUG(dbgs() << "Preheader not found, can NOT pipeline Loop\n");
NumFailPreheader++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
L.getStartLoc(), L.getHeader())
<< "No loop preheader found";
});
return false;
}
unsigned NumStores = 0;
for (MachineInstr &MI : *L.getHeader())
if (MI.mayStore())
++NumStores;
if (NumStores > SwpMaxNumStores) {
LLVM_DEBUG(dbgs() << "Too many stores\n");
NumFailTooManyStores++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(DEBUG_TYPE, "canPipelineLoop",
L.getStartLoc(), L.getHeader())
<< "Too many store instructions in the loop: "
<< ore::NV("NumStores", NumStores) << " > "
<< ore::NV("SwpMaxNumStores", SwpMaxNumStores) << ".";
});
return false;
}
// Remove any subregisters from inputs to phi nodes.
preprocessPhiNodes(*L.getHeader());
return true;
}
void MachinePipelinerImpl::preprocessPhiNodes(MachineBasicBlock &B) {
MachineRegisterInfo &MRI = MF->getRegInfo();
SlotIndexes &Slots = *LIS->getSlotIndexes();
for (MachineInstr &PI : B.phis()) {
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.
Register 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 MachinePipelinerImpl::swingModuloScheduler(MachineLoop &L) {
assert(L.getBlocks().size() == 1 && "SMS works on single blocks only.");
SwingSchedulerDAG SMS(*MF, MLI, ORE, L, *LIS, *RegClassInfo, II_setByPragma,
LI.LoopPipelinerInfo.get(), AA);
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();
}
void MachinePipelinerLegacy::getAnalysisUsage(AnalysisUsage &AU) const {
AU.addRequired<AAResultsWrapperPass>();
AU.addPreserved<AAResultsWrapperPass>();
AU.addRequired<MachineLoopInfoWrapperPass>();
AU.addRequired<LiveIntervalsWrapperPass>();
AU.addRequired<MachineOptimizationRemarkEmitterPass>();
AU.addRequired<MachineRegisterClassInfoWrapperPass>();
AU.addPreserved<MachineRegisterClassInfoWrapperPass>();
AU.addRequired<TargetPassConfig>();
MachineFunctionPass::getAnalysisUsage(AU);
}
bool MachinePipelinerImpl::runWindowScheduler(MachineLoop &L) {
MachineSchedContext Context;
Context.MF = MF;
Context.MLI = MLI;
Context.TM = TM;
Context.AA = AA;
Context.LIS = LIS;
Context.RegClassInfo = RegClassInfo;
WindowScheduler WS(&Context, L);
return WS.run();
}
bool MachinePipelinerImpl::useSwingModuloScheduler() {
// SwingModuloScheduler does not work when WindowScheduler is forced.
return WindowSchedulingOption != WindowSchedulingFlag::WS_Force;
}
bool MachinePipelinerImpl::useWindowScheduler(bool Changed) {
// WindowScheduler does not work for following cases:
// 1. when it is off.
// 2. when SwingModuloScheduler is successfully scheduled.
// 3. when pragma II is enabled.
if (II_setByPragma) {
LLVM_DEBUG(dbgs() << "Window scheduling is disabled when "
"llvm.loop.pipeline.initiationinterval is set.\n");
return false;
}
return WindowSchedulingOption == WindowSchedulingFlag::WS_Force ||
(WindowSchedulingOption == WindowSchedulingFlag::WS_On && !Changed);
}
void SwingSchedulerDAG::setMII(unsigned ResMII, unsigned RecMII) {
if (SwpForceII > 0)
MII = SwpForceII;
else if (II_setByPragma > 0)
MII = II_setByPragma;
else
MII = std::max(ResMII, RecMII);
}
void SwingSchedulerDAG::setMAX_II() {
if (SwpForceII > 0)
MAX_II = SwpForceII;
else if (II_setByPragma > 0)
MAX_II = II_setByPragma;
else
MAX_II = MII + SwpIISearchRange;
}
SwingSchedulerDAG::SwingSchedulerDAG(MachineFunction &MF,
const MachineLoopInfo *MLI,
MachineOptimizationRemarkEmitter *ORE,
MachineLoop &L, LiveIntervals &lis,
const RegisterClassInfo &rci, unsigned II,
TargetInstrInfo::PipelinerLoopInfo *PLI,
AliasAnalysis *AA)
: ScheduleDAGInstrs(MF, MLI, false), ORE(ORE), Loop(L), LIS(lis),
RegClassInfo(rci), II_setByPragma(II), LoopPipelinerInfo(PLI),
Topo(SUnits, &ExitSU), AA(AA), BAA(*AA) {
initPolicy();
MF.getSubtarget().getSMSMutations(Mutations);
if (SwpEnableCopyToPhi)
Mutations.push_back(std::make_unique<CopyToPhiMutation>());
BAA.enableCrossIterationMode();
}
/// We override the schedule function in ScheduleDAGInstrs to implement the
/// scheduling part of the Swing Modulo Scheduling algorithm.
void SwingSchedulerDAG::schedule() {
buildSchedGraph(AA);
const LoopCarriedEdges LCE = addLoopCarriedDependences();
updatePhiDependences();
Topo.InitDAGTopologicalSorting();
changeDependences();
postProcessDAG();
DDG = std::make_unique<SwingSchedulerDDG>(SUnits, &EntrySU, &ExitSU, LCE);
LLVM_DEBUG({
dump();
dbgs() << "===== Loop Carried Edges Begin =====\n";
for (SUnit &SU : SUnits)
LCE.dump(&SU, TRI, &MRI);
dbgs() << "===== Loop Carried Edges End =====\n";
});
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;
setMII(ResMII, RecMII);
setMAX_II();
LLVM_DEBUG(dbgs() << "MII = " << MII << " MAX_II = " << MAX_II
<< " (rec=" << RecMII << ", res=" << ResMII << ")\n");
// Can't schedule a loop without a valid MII.
if (MII == 0) {
LLVM_DEBUG(dbgs() << "Invalid Minimal Initiation Interval: 0\n");
NumFailZeroMII++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
<< "Invalid Minimal Initiation Interval: 0";
});
return;
}
// Don't pipeline large loops.
if (SwpMaxMii != -1 && (int)MII > SwpMaxMii) {
LLVM_DEBUG(dbgs() << "MII > " << SwpMaxMii
<< ", we don't pipeline large loops\n");
NumFailLargeMaxMII++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
<< "Minimal Initiation Interval too large: "
<< ore::NV("MII", (int)MII) << " > "
<< ore::NV("SwpMaxMii", SwpMaxMii) << "."
<< "Refer to -pipeliner-max-mii.";
});
return;
}
computeNodeFunctions(NodeSets);
registerPressureFilter(NodeSets);
colocateNodeSets(NodeSets);
checkNodeSets(NodeSets);
LLVM_DEBUG({
for (auto &I : NodeSets) {
dbgs() << " Rec NodeSet ";
I.dump();
}
});
llvm::stable_sort(NodeSets, 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(&MF, this);
Scheduled = schedulePipeline(Schedule);
if (!Scheduled){
LLVM_DEBUG(dbgs() << "No schedule found, return\n");
NumFailNoSchedule++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
<< "Unable to find schedule";
});
return;
}
unsigned numStages = Schedule.getMaxStageCount();
// No need to generate pipeline if there are no overlapped iterations.
if (numStages == 0) {
LLVM_DEBUG(dbgs() << "No overlapped iterations, skip.\n");
NumFailZeroStage++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
<< "No need to pipeline - no overlapped iterations in schedule.";
});
return;
}
// Check that the maximum stage count is less than user-defined limit.
if (SwpMaxStages > -1 && (int)numStages > SwpMaxStages) {
LLVM_DEBUG(dbgs() << "numStages:" << numStages << ">" << SwpMaxStages
<< " : too many stages, abort\n");
NumFailLargeMaxStage++;
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
<< "Too many stages in schedule: "
<< ore::NV("numStages", (int)numStages) << " > "
<< ore::NV("SwpMaxStages", SwpMaxStages)
<< ". Refer to -pipeliner-max-stages.";
});
return;
}
ORE->emit([&]() {
return MachineOptimizationRemark(DEBUG_TYPE, "schedule", Loop.getStartLoc(),
Loop.getHeader())
<< "Pipelined succesfully!";
});
// Generate the schedule as a ModuloSchedule.
DenseMap<MachineInstr *, int> Cycles, Stages;
std::vector<MachineInstr *> OrderedInsts;
for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
++Cycle) {
for (SUnit *SU : Schedule.getInstructions(Cycle)) {
OrderedInsts.push_back(SU->getInstr());
Cycles[SU->getInstr()] = Cycle;
Stages[SU->getInstr()] = Schedule.stageScheduled(SU);
}
}
DenseMap<MachineInstr *, std::pair<Register, int64_t>> NewInstrChanges;
for (auto &KV : NewMIs) {
Cycles[KV.first] = Cycles[KV.second];
Stages[KV.first] = Stages[KV.second];
NewInstrChanges[KV.first] = InstrChanges[getSUnit(KV.first)];
}
ModuloSchedule MS(MF, &Loop, std::move(OrderedInsts), std::move(Cycles),
std::move(Stages));
if (EmitTestAnnotations) {
assert(NewInstrChanges.empty() &&
"Cannot serialize a schedule with InstrChanges!");
ModuloScheduleTestAnnotater MSTI(MF, MS);
MSTI.annotate();
return;
}
// The experimental code generator can't work if there are InstChanges.
if (ExperimentalCodeGen && NewInstrChanges.empty()) {
PeelingModuloScheduleExpander MSE(MF, MS, &LIS);
MSE.expand();
} else if (MVECodeGen && NewInstrChanges.empty() &&
LoopPipelinerInfo->isMVEExpanderSupported() &&
ModuloScheduleExpanderMVE::canApply(Loop)) {
ModuloScheduleExpanderMVE MSE(MF, MS, LIS);
MSE.expand();
} else {
ModuloScheduleExpander MSE(MF, MS, LIS, std::move(NewInstrChanges));
MSE.expand();
MSE.cleanup();
}
++NumPipelined;
}
/// Clean up after the software pipeliner runs.
void SwingSchedulerDAG::finishBlock() {
for (auto &KV : NewMIs)
MF.deleteMachineInstr(KV.second);
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,
Register &InitVal, Register &LoopVal) {
assert(Phi.isPHI() && "Expecting a Phi.");
InitVal = Register();
LoopVal = Register();
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 && LoopVal && "Unexpected Phi structure.");
}
/// Return the Phi register value that comes the loop block.
static Register getLoopPhiReg(const MachineInstr &Phi,
const 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 Register();
}
/// 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 (const 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;
}
SUnitWithMemInfo::SUnitWithMemInfo(SUnit *SU) : SU(SU) {
if (!getUnderlyingObjects())
return;
for (const Value *Obj : UnderlyingObjs)
if (!isIdentifiedObject(Obj)) {
IsAllIdentified = false;
break;
}
}
bool SUnitWithMemInfo::isTriviallyDisjoint(
const SUnitWithMemInfo &Other) const {
// If all underlying objects are identified objects and there is no overlap
// between them, then these two instructions are disjoint.
if (!IsAllIdentified || !Other.IsAllIdentified)
return false;
for (const Value *Obj : UnderlyingObjs)
if (llvm::is_contained(Other.UnderlyingObjs, Obj))
return false;
return true;
}
/// Collect 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.
/// Returns false if we cannot find the underlying objects.
bool SUnitWithMemInfo::getUnderlyingObjects() {
const MachineInstr *MI = SU->getInstr();
if (!MI->hasOneMemOperand())
return false;
MachineMemOperand *MM = *MI->memoperands_begin();
if (!MM->getValue())
return false;
MemOpValue = MM->getValue();
MemOpOffset = MM->getOffset();
llvm::getUnderlyingObjects(MemOpValue, UnderlyingObjs);
// TODO: A no alias scope may be valid only in a single iteration. In this
// case we need to peel off it like LoopAccessAnalysis does.
AATags = MM->getAAInfo();
return true;
}
/// Returns true if there is a loop-carried order dependency from \p Src to \p
/// Dst.
static bool hasLoopCarriedMemDep(const SUnitWithMemInfo &Src,
const SUnitWithMemInfo &Dst,
BatchAAResults &BAA,
const TargetInstrInfo *TII,
const TargetRegisterInfo *TRI,
const SwingSchedulerDAG *SSD) {
if (Src.isTriviallyDisjoint(Dst))
return false;
if (isSuccOrder(Src.SU, Dst.SU))
return false;
MachineInstr &SrcMI = *Src.SU->getInstr();
MachineInstr &DstMI = *Dst.SU->getInstr();
if (!SSD->mayOverlapInLaterIter(&SrcMI, &DstMI))
return false;
// 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 (Src.isUnknown() || Dst.isUnknown())
return true;
if (Src.MemOpValue == Dst.MemOpValue && Src.MemOpOffset <= Dst.MemOpOffset)
return true;
if (BAA.isNoAlias(
MemoryLocation::getBeforeOrAfter(Src.MemOpValue, Src.AATags),
MemoryLocation::getBeforeOrAfter(Dst.MemOpValue, Dst.AATags)))
return false;
// AliasAnalysis sometimes gives up on following the underlying
// object. In such a case, separate checks for underlying objects may
// prove that there are no aliases between two accesses.
for (const Value *SrcObj : Src.UnderlyingObjs)
for (const Value *DstObj : Dst.UnderlyingObjs)
if (!BAA.isNoAlias(MemoryLocation::getBeforeOrAfter(SrcObj, Src.AATags),
MemoryLocation::getBeforeOrAfter(DstObj, Dst.AATags)))
return true;
return false;
}
void LoopCarriedOrderDepsTracker::NoBarrierInstsChunk::append(SUnit *SU) {
const MachineInstr *MI = SU->getInstr();
if (MI->mayStore())
Stores.emplace_back(SU);
else if (MI->mayLoad())
Loads.emplace_back(SU);
else if (MI->mayRaiseFPException())
FPExceptions.emplace_back(SU);
else
llvm_unreachable("Unexpected instruction type.");
}
LoopCarriedOrderDepsTracker::LoopCarriedOrderDepsTracker(
SwingSchedulerDAG *SSD, BatchAAResults *BAA, const TargetInstrInfo *TII,
const TargetRegisterInfo *TRI)
: DAG(SSD), BAA(BAA), SUnits(DAG->SUnits), N(SUnits.size()),
LoopCarried(N, BitVector(N)), TII(TII), TRI(TRI) {}
void LoopCarriedOrderDepsTracker::computeDependencies() {
// Traverse all instructions and extract only what we are targetting.
for (auto &SU : SUnits) {
auto Tagged = getInstrTag(&SU);
// This instruction has no loop-carried order-dependencies.
if (!Tagged)
continue;
TaggedSUnits.emplace_back(&SU, *Tagged);
}
computeDependenciesAux();
}
std::optional<LoopCarriedOrderDepsTracker::InstrTag>
LoopCarriedOrderDepsTracker::getInstrTag(SUnit *SU) const {
MachineInstr *MI = SU->getInstr();
if (TII->isGlobalMemoryObject(MI))
return InstrTag::Barrier;
if (MI->mayStore() ||
(MI->mayLoad() && !MI->isDereferenceableInvariantLoad()))
return InstrTag::LoadOrStore;
if (MI->mayRaiseFPException())
return InstrTag::FPExceptions;
return std::nullopt;
}
void LoopCarriedOrderDepsTracker::addDependenciesBetweenSUs(
const SUnitWithMemInfo &Src, const SUnitWithMemInfo &Dst) {
// Avoid self-dependencies.
if (Src.SU == Dst.SU)
return;
if (hasLoopCarriedMemDep(Src, Dst, *BAA, TII, TRI, DAG))
setLoopCarriedDep(Src.SU, Dst.SU);
}
void LoopCarriedOrderDepsTracker::addLoopCarriedDepenenciesForChunks(
const NoBarrierInstsChunk &From, const NoBarrierInstsChunk &To) {
// Add load-to-store dependencies (WAR).
for (const SUnitWithMemInfo &Src : From.Loads)
for (const SUnitWithMemInfo &Dst : To.Stores)
addDependenciesBetweenSUs(Src, Dst);
// Add store-to-load dependencies (RAW).
for (const SUnitWithMemInfo &Src : From.Stores)
for (const SUnitWithMemInfo &Dst : To.Loads)
addDependenciesBetweenSUs(Src, Dst);
// Add store-to-store dependencies (WAW).
for (const SUnitWithMemInfo &Src : From.Stores)
for (const SUnitWithMemInfo &Dst : To.Stores)
addDependenciesBetweenSUs(Src, Dst);
}
void LoopCarriedOrderDepsTracker::computeDependenciesAux() {
SmallVector<NoBarrierInstsChunk, 2> Chunks(1);
SUnit *FirstBarrier = nullptr;
SUnit *LastBarrier = nullptr;
for (const auto &TSU : TaggedSUnits) {
InstrTag Tag = TSU.getTag();
SUnit *SU = TSU.getPointer();
switch (Tag) {
case InstrTag::Barrier:
if (!FirstBarrier)
FirstBarrier = SU;
LastBarrier = SU;
Chunks.emplace_back();
break;
case InstrTag::LoadOrStore:
case InstrTag::FPExceptions:
Chunks.back().append(SU);
break;
}
}
// Add dependencies between memory operations. If there are one or more
// barrier events between two memory instructions, we don't add a
// loop-carried dependence for them.
for (const NoBarrierInstsChunk &Chunk : Chunks)
addLoopCarriedDepenenciesForChunks(Chunk, Chunk);
// There is no barrier instruction between load/store/fp-exception
// instructions in the same chunk. If there are one or more barrier
// instructions, the instructions sequence is as follows:
//
// Loads/Stores/FPExceptions (Chunks.front())
// Barrier (FirstBarrier)
// Loads/Stores/FPExceptions
// Barrier
// ...
// Loads/Stores/FPExceptions
// Barrier (LastBarrier)
// Loads/Stores/FPExceptions (Chunks.back())
//
// Since loads/stores/fp-exceptions must not be reordered across barrier
// instructions, and the order of barrier instructions must be preserved, add
// the following loop-carried dependences:
//
// Loads/Stores/FPExceptions (Chunks.front()) <-----+
// +--> Barrier (FirstBarrier) <----------------------+ |
// | Loads/Stores/FPExceptions | |
// | Barrier | |
// | ... | |
// | Loads/Stores/FPExceptions | |
// | Barrier (LastBarrier) ------------------------+--+
// +--- Loads/Stores/FPExceptions (Chunks.back())
//
if (FirstBarrier) {
assert(LastBarrier && "Both barriers should be set.");
// LastBarrier -> Loads/Stores/FPExceptions in Chunks.front()
for (const SUnitWithMemInfo &Dst : Chunks.front().Loads)
setLoopCarriedDep(LastBarrier, Dst.SU);
for (const SUnitWithMemInfo &Dst : Chunks.front().Stores)
setLoopCarriedDep(LastBarrier, Dst.SU);
for (const SUnitWithMemInfo &Dst : Chunks.front().FPExceptions)
setLoopCarriedDep(LastBarrier, Dst.SU);
// Loads/Stores/FPExceptions in Chunks.back() -> FirstBarrier
for (const SUnitWithMemInfo &Src : Chunks.back().Loads)
setLoopCarriedDep(Src.SU, FirstBarrier);
for (const SUnitWithMemInfo &Src : Chunks.back().Stores)
setLoopCarriedDep(Src.SU, FirstBarrier);
for (const SUnitWithMemInfo &Src : Chunks.back().FPExceptions)
setLoopCarriedDep(Src.SU, FirstBarrier);
// LastBarrier -> FirstBarrier (if they are different)
if (FirstBarrier != LastBarrier)
setLoopCarriedDep(LastBarrier, FirstBarrier);
}
}
/// 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.
/// TODO: Also compute output-dependencies.
LoopCarriedEdges SwingSchedulerDAG::addLoopCarriedDependences() {
LoopCarriedEdges LCE;
// Add loop-carried order-dependencies
LoopCarriedOrderDepsTracker LCODTracker(this, &BAA, TII, TRI);
LCODTracker.computeDependencies();
for (unsigned I = 0; I != SUnits.size(); I++)
for (const int Succ : LCODTracker.getLoopCarried(I).set_bits())
LCE.OrderDeps[&SUnits[I]].insert(&SUnits[Succ]);
LCE.modifySUnits(SUnits, TII);
return LCE;
}
/// 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.
Register HasPhiUse;
Register HasPhiDef;
MachineInstr *MI = I.getInstr();
// Iterate over each operand, and we process the definitions.
for (const MachineOperand &MO : MI->operands()) {
if (!MO.isReg())
continue;
Register Reg = MO.getReg();
if (!Reg.isVirtual())
continue;
if (MO.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.
// %3:intregs = PHI %21:intregs, %bb.6, %7:intregs, %bb.1 - SU0
// %7:intregs = PHI %21:intregs, %bb.6, %13:intregs, %bb.1 - SU1
// %27:intregs = A2_zxtb %3:intregs - SU2
// %13:intregs = C2_muxri %45:predregs, 0, %46:intreg
// If we have dependent phis, SU0 should be the successor of SU1
// not the other way around. (it used to be SU1 is the successor
// of SU0). In some cases, SU0 is scheduled earlier than SU1
// resulting in bad IR as we do not have a value that can be used
// by SU2.
if (SU->NodeNum < I.NodeNum && !SU->isPred(&I))
SU->addPred(SDep(&I, SDep::Barrier));
}
}
}
} else if (MO.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, 0, &I, MO.getOperandNo(), Dep,
&SchedModel);
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 (const SDep &D : RemoveDeps)
I.removePred(D);
}
}
/// 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;
Register NewBase;
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.
Register 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 (const SDep &P : I.Preds)
if (P.getSUnit() == DefSU)
Deps.push_back(P);
for (const SDep &D : Deps) {
Topo.RemovePred(&I, D.getSUnit());
I.removePred(D);
}
// 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 (const SDep &D : Deps) {
Topo.RemovePred(LastSU, D.getSUnit());
LastSU->removePred(D);
}
// Add a dependence between the new instruction and the instruction
// that defines the new base.
SDep Dep(&I, SDep::Anti, NewBase);
Topo.AddPred(LastSU, &I);
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);
}
}
/// Create an instruction stream that represents a single iteration and stage of
/// each instruction. This function differs from SMSchedule::finalizeSchedule in
/// that this doesn't have any side-effect to SwingSchedulerDAG. That is, this
/// function is an approximation of SMSchedule::finalizeSchedule with all
/// non-const operations removed.
static void computeScheduledInsts(const SwingSchedulerDAG *SSD,
SMSchedule &Schedule,
std::vector<MachineInstr *> &OrderedInsts,
DenseMap<MachineInstr *, unsigned> &Stages) {
DenseMap<int, std::deque<SUnit *>> Instrs;
// Move all instructions to the first stage from the later stages.
for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
++Cycle) {
for (int Stage = 0, LastStage = Schedule.getMaxStageCount();
Stage <= LastStage; ++Stage) {
for (SUnit *SU : llvm::reverse(Schedule.getInstructions(
Cycle + Stage * Schedule.getInitiationInterval()))) {
Instrs[Cycle].push_front(SU);
}
}
}
for (int Cycle = Schedule.getFirstCycle(); Cycle <= Schedule.getFinalCycle();
++Cycle) {
std::deque<SUnit *> &CycleInstrs = Instrs[Cycle];
CycleInstrs = Schedule.reorderInstructions(SSD, CycleInstrs);
for (SUnit *SU : CycleInstrs) {
MachineInstr *MI = SU->getInstr();
OrderedInsts.push_back(MI);
Stages[MI] = Schedule.stageScheduled(SU);
}
}
}
namespace {
// FuncUnitSorter - Comparison operator used to sort instructions by
// the number of functional unit choices.
struct FuncUnitSorter {
const InstrItineraryData *InstrItins;
const MCSubtargetInfo *STI;
DenseMap<InstrStage::FuncUnits, unsigned> Resources;
FuncUnitSorter(const TargetSubtargetInfo &TSI)
: InstrItins(TSI.getInstrItineraryData()), STI(&TSI) {}
// 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,
InstrStage::FuncUnits &F) const {
unsigned SchedClass = Inst->getDesc().getSchedClass();
unsigned min = UINT_MAX;
if (InstrItins && !InstrItins->isEmpty()) {
for (const InstrStage &IS :
make_range(InstrItins->beginStage(SchedClass),
InstrItins->endStage(SchedClass))) {
InstrStage::FuncUnits funcUnits = IS.getUnits();
unsigned numAlternatives = llvm::popcount(funcUnits);
if (numAlternatives < min) {
min = numAlternatives;
F = funcUnits;
}
}
return min;
}
if (STI && STI->getSchedModel().hasInstrSchedModel()) {
const MCSchedClassDesc *SCDesc =
STI->getSchedModel().getSchedClassDesc(SchedClass);
if (!SCDesc->isValid())
// No valid Schedule Class Desc for schedClass, should be
// Pseudo/PostRAPseudo
return min;
for (const MCWriteProcResEntry &PRE :
make_range(STI->getWriteProcResBegin(SCDesc),
STI->getWriteProcResEnd(SCDesc))) {
if (!PRE.ReleaseAtCycle)
continue;
const MCProcResourceDesc *ProcResource =
STI->getSchedModel().getProcResource(PRE.ProcResourceIdx);
unsigned NumUnits = ProcResource->NumUnits;
if (NumUnits < min) {
min = NumUnits;
F = PRE.ProcResourceIdx;
}
}
return min;
}
llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!");
}
// 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();
if (InstrItins && !InstrItins->isEmpty()) {
for (const InstrStage &IS :
make_range(InstrItins->beginStage(SchedClass),
InstrItins->endStage(SchedClass))) {
InstrStage::FuncUnits FuncUnits = IS.getUnits();
if (llvm::popcount(FuncUnits) == 1)
Resources[FuncUnits]++;
}
return;
}
if (STI && STI->getSchedModel().hasInstrSchedModel()) {
const MCSchedClassDesc *SCDesc =
STI->getSchedModel().getSchedClassDesc(SchedClass);
if (!SCDesc->isValid())
// No valid Schedule Class Desc for schedClass, should be
// Pseudo/PostRAPseudo
return;
for (const MCWriteProcResEntry &PRE :
make_range(STI->getWriteProcResBegin(SCDesc),
STI->getWriteProcResEnd(SCDesc))) {
if (!PRE.ReleaseAtCycle)
continue;
Resources[PRE.ProcResourceIdx]++;
}
return;
}
llvm_unreachable("Should have non-empty InstrItins or hasInstrSchedModel!");
}
/// Return true if IS1 has less priority than IS2.
bool operator()(const MachineInstr *IS1, const MachineInstr *IS2) const {
InstrStage::FuncUnits F1 = 0, F2 = 0;
unsigned MFUs1 = minFuncUnits(IS1, F1);
unsigned MFUs2 = minFuncUnits(IS2, F2);
if (MFUs1 == MFUs2)
return Resources.lookup(F1) < Resources.lookup(F2);
return MFUs1 > MFUs2;
}
};
/// Calculate the maximum register pressure of the scheduled instructions stream
class HighRegisterPressureDetector {
MachineBasicBlock *OrigMBB;
const MachineRegisterInfo &MRI;
const TargetRegisterInfo *TRI;
const unsigned PSetNum;
// Indexed by PSet ID
// InitSetPressure takes into account the register pressure of live-in
// registers. It's not depend on how the loop is scheduled, so it's enough to
// calculate them once at the beginning.
std::vector<unsigned> InitSetPressure;
// Indexed by PSet ID
// Upper limit for each register pressure set
std::vector<unsigned> PressureSetLimit;
DenseMap<MachineInstr *, RegisterOperands> ROMap;
using Instr2LastUsesTy = DenseMap<MachineInstr *, SmallSet<VirtRegOrUnit, 4>>;
public:
using OrderedInstsTy = std::vector<MachineInstr *>;
using Instr2StageTy = DenseMap<MachineInstr *, unsigned>;
private:
static void dumpRegisterPressures(const std::vector<unsigned> &Pressures) {
if (Pressures.size() == 0) {
dbgs() << "[]";
} else {
char Prefix = '[';
for (unsigned P : Pressures) {
dbgs() << Prefix << P;
Prefix = ' ';
}
dbgs() << ']';
}
}
void dumpPSet(VirtRegOrUnit VRegOrUnit) const {
dbgs() << "Reg=" << printVRegOrUnit(VRegOrUnit, TRI) << " PSet=";
for (auto PSetIter = MRI.getPressureSets(VRegOrUnit); PSetIter.isValid();
++PSetIter) {
dbgs() << *PSetIter << ' ';
}
dbgs() << '\n';
}
void increaseRegisterPressure(std::vector<unsigned> &Pressure,
VirtRegOrUnit VRegOrUnit) const {
auto PSetIter = MRI.getPressureSets(VRegOrUnit);
unsigned Weight = PSetIter.getWeight();
for (; PSetIter.isValid(); ++PSetIter)
Pressure[*PSetIter] += Weight;
}
void decreaseRegisterPressure(std::vector<unsigned> &Pressure,
VirtRegOrUnit VRegOrUnit) const {
auto PSetIter = MRI.getPressureSets(VRegOrUnit);
unsigned Weight = PSetIter.getWeight();
for (; PSetIter.isValid(); ++PSetIter) {
auto &P = Pressure[*PSetIter];
assert(P >= Weight &&
"register pressure must be greater than or equal weight");
P -= Weight;
}
}
/// Return true if \p VRegOrUnit is reserved one, for example, stack pointer
bool isReservedRegUnit(VirtRegOrUnit VRegOrUnit) const {
return !VRegOrUnit.isVirtualReg() &&
MRI.isReservedRegUnit(VRegOrUnit.asMCRegUnit());
}
bool isDefinedInThisLoop(VirtRegOrUnit VRegOrUnit) const {
return VRegOrUnit.isVirtualReg() &&
MRI.getDefBlock(VRegOrUnit.asVirtualReg()) == OrigMBB;
}
// Search for live-in variables. They are factored into the register pressure
// from the begining. Live-in variables used by every iteration should be
// considered as alive throughout the loop. For example, the variable `c` in
// following code. \code
// int c = ...;
// for (int i = 0; i < n; i++)
// a[i] += b[i] + c;
// \endcode
void computeLiveIn() {
SmallSet<VirtRegOrUnit, 8> Used;
for (auto &MI : *OrigMBB) {
if (MI.isDebugInstr())
continue;
for (auto &Use : ROMap[&MI].Uses) {
VirtRegOrUnit Reg = Use.VRegOrUnit;
// Ignore the variable that appears only on one side of phi instruction
// because it's used only at the first iteration.
if (MI.isPHI() && Reg.isVirtualReg() &&
Reg.asVirtualReg() != getLoopPhiReg(MI, OrigMBB))
continue;
if (isReservedRegUnit(Reg))
continue;
if (isDefinedInThisLoop(Reg))
continue;
Used.insert(Reg);
}
}
for (auto LiveIn : Used)
increaseRegisterPressure(InitSetPressure, LiveIn);
}
// Calculate the upper limit of each pressure set
void computePressureSetLimit(const RegisterClassInfo &RCI) {
for (unsigned PSet = 0; PSet < PSetNum; PSet++)
PressureSetLimit[PSet] = RCI.getRegPressureSetLimit(PSet);
}
// There are two patterns of last-use.
// - by an instruction of the current iteration
// - by a phi instruction of the next iteration (loop carried value)
//
// Furthermore, following two groups of instructions are executed
// simultaneously
// - next iteration's phi instructions in i-th stage
// - current iteration's instructions in i+1-th stage
//
// This function calculates the last-use of each register while taking into
// account the above two patterns.
Instr2LastUsesTy computeLastUses(const OrderedInstsTy &OrderedInsts,
Instr2StageTy &Stages) const {
// We treat virtual registers that are defined and used in this loop.
// Following virtual register will be ignored
// - live-in one
// - defined but not used in the loop (potentially live-out)
SmallSet<VirtRegOrUnit, 8> TargetRegs;
const auto UpdateTargetRegs = [this, &TargetRegs](VirtRegOrUnit Reg) {
if (isDefinedInThisLoop(Reg))
TargetRegs.insert(Reg);
};
for (MachineInstr *MI : OrderedInsts) {
if (MI->isPHI()) {
Register Reg = getLoopPhiReg(*MI, OrigMBB);
UpdateTargetRegs(VirtRegOrUnit(Reg));
} else {
for (auto &Use : ROMap.find(MI)->getSecond().Uses)
UpdateTargetRegs(Use.VRegOrUnit);
}
}
const auto InstrScore = [&Stages](MachineInstr *MI) {
return Stages[MI] + MI->isPHI();
};
std::map<VirtRegOrUnit, MachineInstr *> LastUseMI;
for (MachineInstr *MI : llvm::reverse(OrderedInsts)) {
for (auto &Use : ROMap.find(MI)->getSecond().Uses) {
VirtRegOrUnit Reg = Use.VRegOrUnit;
if (!TargetRegs.contains(Reg))
continue;
auto [Ite, Inserted] = LastUseMI.try_emplace(Reg, MI);
if (!Inserted) {
MachineInstr *Orig = Ite->second;
MachineInstr *New = MI;
if (InstrScore(Orig) < InstrScore(New))
Ite->second = New;
}
}
}
Instr2LastUsesTy LastUses;
for (auto [Reg, MI] : LastUseMI)
LastUses[MI].insert(Reg);
return LastUses;
}
// Compute the maximum register pressure of the kernel. We'll simulate #Stage
// iterations and check the register pressure at the point where all stages
// overlapping.
//
// An example of unrolled loop where #Stage is 4..
// Iter i+0 i+1 i+2 i+3
// ------------------------
// Stage 0
// Stage 1 0
// Stage 2 1 0
// Stage 3 2 1 0 <- All stages overlap
//
std::vector<unsigned>
computeMaxSetPressure(const OrderedInstsTy &OrderedInsts,
Instr2StageTy &Stages,
const unsigned StageCount) const {
using RegSetTy = SmallSet<VirtRegOrUnit, 16>;
// Indexed by #Iter. To treat "local" variables of each stage separately, we
// manage the liveness of the registers independently by iterations.
SmallVector<RegSetTy> LiveRegSets(StageCount);
auto CurSetPressure = InitSetPressure;
auto MaxSetPressure = InitSetPressure;
auto LastUses = computeLastUses(OrderedInsts, Stages);
LLVM_DEBUG({
dbgs() << "Ordered instructions:\n";
for (MachineInstr *MI : OrderedInsts) {
dbgs() << "Stage " << Stages[MI] << ": ";
MI->dump();
}
});
const auto InsertReg = [this, &CurSetPressure](RegSetTy &RegSet,
VirtRegOrUnit Reg) {
if (isReservedRegUnit(Reg))
return;
bool Inserted = RegSet.insert(Reg).second;
if (!Inserted)
return;
LLVM_DEBUG(dbgs() << "insert " << printVRegOrUnit(Reg, TRI) << "\n");
increaseRegisterPressure(CurSetPressure, Reg);
LLVM_DEBUG(dumpPSet(Reg));
};
const auto EraseReg = [this, &CurSetPressure](RegSetTy &RegSet,
VirtRegOrUnit Reg) {
if (isReservedRegUnit(Reg))
return;
// live-in register
if (!RegSet.contains(Reg))
return;
LLVM_DEBUG(dbgs() << "erase " << printVRegOrUnit(Reg, TRI) << "\n");
RegSet.erase(Reg);
decreaseRegisterPressure(CurSetPressure, Reg);
LLVM_DEBUG(dumpPSet(Reg));
};
for (unsigned I = 0; I < StageCount; I++) {
for (MachineInstr *MI : OrderedInsts) {
const auto Stage = Stages[MI];
if (I < Stage)
continue;
const unsigned Iter = I - Stage;
for (auto &Def : ROMap.find(MI)->getSecond().Defs)
InsertReg(LiveRegSets[Iter], Def.VRegOrUnit);
for (auto LastUse : LastUses[MI]) {
if (MI->isPHI()) {
if (Iter != 0)
EraseReg(LiveRegSets[Iter - 1], LastUse);
} else {
EraseReg(LiveRegSets[Iter], LastUse);
}
}
for (unsigned PSet = 0; PSet < PSetNum; PSet++)
MaxSetPressure[PSet] =
std::max(MaxSetPressure[PSet], CurSetPressure[PSet]);
LLVM_DEBUG({
dbgs() << "CurSetPressure=";
dumpRegisterPressures(CurSetPressure);
dbgs() << " iter=" << Iter << " stage=" << Stage << ":";
MI->dump();
});
}
}
return MaxSetPressure;
}
public:
HighRegisterPressureDetector(MachineBasicBlock *OrigMBB,
const MachineFunction &MF)
: OrigMBB(OrigMBB), MRI(MF.getRegInfo()),
TRI(MF.getSubtarget().getRegisterInfo()),
PSetNum(TRI->getNumRegPressureSets()), InitSetPressure(PSetNum, 0),
PressureSetLimit(PSetNum, 0) {}
// Used to calculate register pressure, which is independent of loop
// scheduling.
void init(const RegisterClassInfo &RCI) {
for (MachineInstr &MI : *OrigMBB) {
if (MI.isDebugInstr())
continue;
ROMap[&MI].collect(MI, *TRI, MRI, false, true);
}
computeLiveIn();
computePressureSetLimit(RCI);
}
// Calculate the maximum register pressures of the loop and check if they
// exceed the limit
bool detect(const SwingSchedulerDAG *SSD, SMSchedule &Schedule,
const unsigned MaxStage) const {
assert(0 <= RegPressureMargin && RegPressureMargin <= 100 &&
"the percentage of the margin must be between 0 to 100");
OrderedInstsTy OrderedInsts;
Instr2StageTy Stages;
computeScheduledInsts(SSD, Schedule, OrderedInsts, Stages);
const auto MaxSetPressure =
computeMaxSetPressure(OrderedInsts, Stages, MaxStage + 1);
LLVM_DEBUG({
dbgs() << "Dump MaxSetPressure:\n";
for (unsigned I = 0; I < MaxSetPressure.size(); I++) {
dbgs() << format("MaxSetPressure[%d]=%d\n", I, MaxSetPressure[I]);
}
dbgs() << '\n';
});
for (unsigned PSet = 0; PSet < PSetNum; PSet++) {
unsigned Limit = PressureSetLimit[PSet];
unsigned Margin = Limit * RegPressureMargin / 100;
LLVM_DEBUG(dbgs() << "PSet=" << PSet << " Limit=" << Limit
<< " Margin=" << Margin << "\n");
if (Limit < MaxSetPressure[PSet] + Margin) {
LLVM_DEBUG(
dbgs()
<< "Rejected the schedule because of too high register pressure\n");
return true;
}
}
return false;
}
};
} // 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() {
LLVM_DEBUG(dbgs() << "calculateResMII:\n");
ResourceManager RM(&MF.getSubtarget(), this);
return RM.calculateResMII();
}
/// 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;
}
/// Create the adjacency structure of the nodes in the graph.
void SwingSchedulerDAG::Circuits::createAdjacencyStructure(
SwingSchedulerDDG *DDG) {
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 &OE : DDG->getOutEdges(&SUnits[i])) {
// Only create a back-edge on the first and last nodes of a dependence
// chain. This records any chains and adds them later.
if (OE.isOutputDep()) {
int N = OE.getDst()->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, an artificial node.
if (OE.getDst()->isBoundaryNode() || OE.isArtificial())
continue;
// This code is retained o preserve previous behavior and prevent
// regression. This condition means that anti-dependnecies within an
// iteration are ignored when searching circuits. Therefore it's natural
// to consider this dependence as well.
// FIXME: Remove this code if it doesn't have significant impact on
// performance.
if (OE.isAntiDep())
continue;
int N = OE.getDst()->NodeNum;
if (!Added.test(N)) {
AdjK[i].push_back(N);
Added.set(N);
}
}
// Also add any extra out edges to the adjacency matrix.
for (const SUnit *Dst : DDG->getExtraOutEdges(&SUnits[i])) {
int N = Dst->NodeNum;
if (!Added.test(N)) {
AdjK[i].push_back(N);
Added.set(N);
}
}
}
// Add back-edges 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,
const SwingSchedulerDAG *DAG,
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(), DAG));
F = true;
++NumPaths;
break;
}
if (!Blocked.test(W)) {
if (circuit(W, S, NodeSets, DAG,
Node2Idx->at(W) < Node2Idx->at(V) ? true : HasBackedge))
F = true;
}
}
if (F)
unblock(V);
else {
for (auto W : AdjK[V]) {
if (W < S)
continue;
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) {
Circuits Cir(SUnits, Topo);
// Create the adjacency structure.
Cir.createAdjacencyStructure(&*DDG);
for (int I = 0, E = SUnits.size(); I != E; ++I) {
Cir.reset();
Cir.circuit(I, I, NodeSets, this);
}
}
// Create artificial dependencies between the source of COPY/REG_SEQUENCE that
// is loop-carried to the USE in next iteration. This will help pipeliner avoid
// additional copies that are needed across iterations. An artificial dependence
// edge is added from USE to SOURCE of COPY/REG_SEQUENCE.
// PHI-------Anti-Dep-----> COPY/REG_SEQUENCE (loop-carried)
// SRCOfCopY------True-Dep---> COPY/REG_SEQUENCE
// PHI-------True-Dep------> USEOfPhi
// The mutation creates
// USEOfPHI -------Artificial-Dep---> SRCOfCopy
// This overall will ensure, the USEOfPHI is scheduled before SRCOfCopy
// (since USE is a predecessor), implies, the COPY/ REG_SEQUENCE is scheduled
// late to avoid additional copies across iterations. The possible scheduling
// order would be
// USEOfPHI --- SRCOfCopy--- COPY/REG_SEQUENCE.
void SwingSchedulerDAG::CopyToPhiMutation::apply(ScheduleDAGInstrs *DAG) {
for (SUnit &SU : DAG->SUnits) {
// Find the COPY/REG_SEQUENCE instruction.
if (!SU.getInstr()->isCopy() && !SU.getInstr()->isRegSequence())
continue;
// Record the loop carried PHIs.
SmallVector<SUnit *, 4> PHISUs;
// Record the SrcSUs that feed the COPY/REG_SEQUENCE instructions.
SmallVector<SUnit *, 4> SrcSUs;
for (auto &Dep : SU.Preds) {
SUnit *TmpSU = Dep.getSUnit();
MachineInstr *TmpMI = TmpSU->getInstr();
SDep::Kind DepKind = Dep.getKind();
// Save the loop carried PHI.
if (DepKind == SDep::Anti && TmpMI->isPHI())
PHISUs.push_back(TmpSU);
// Save the source of COPY/REG_SEQUENCE.
// If the source has no pre-decessors, we will end up creating cycles.
else if (DepKind == SDep::Data && !TmpMI->isPHI() && TmpSU->NumPreds > 0)
SrcSUs.push_back(TmpSU);
}
if (PHISUs.size() == 0 || SrcSUs.size() == 0)
continue;
// Find the USEs of PHI. If the use is a PHI or REG_SEQUENCE, push back this
// SUnit to the container.
SmallVector<SUnit *, 8> UseSUs;
// Do not use iterator based loop here as we are updating the container.
for (size_t Index = 0; Index < PHISUs.size(); ++Index) {
for (auto &Dep : PHISUs[Index]->Succs) {
if (Dep.getKind() != SDep::Data)
continue;
SUnit *TmpSU = Dep.getSUnit();
MachineInstr *TmpMI = TmpSU->getInstr();
if (TmpMI->isPHI() || TmpMI->isRegSequence()) {
PHISUs.push_back(TmpSU);
continue;
}
UseSUs.push_back(TmpSU);
}
}
if (UseSUs.size() == 0)
continue;
SwingSchedulerDAG *SDAG = cast<SwingSchedulerDAG>(DAG);
// Add the artificial dependencies if it does not form a cycle.
for (auto *I : UseSUs) {
for (auto *Src : SrcSUs) {
if (!SDAG->Topo.IsReachable(I, Src) && Src != I) {
Src->addPred(SDep(I, SDep::Artificial));
SDAG->Topo.AddPred(Src, I);
}
}
}
}
}
/// 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 (int I : Topo) {
const SUnit &SU = SUnits[I];
dumpNode(SU);
}
});
int maxASAP = 0;
// Compute ASAP and ZeroLatencyDepth.
for (int I : Topo) {
int asap = 0;
int zeroLatencyDepth = 0;
SUnit *SU = &SUnits[I];
for (const auto &IE : DDG->getInEdges(SU)) {
SUnit *Pred = IE.getSrc();
if (IE.getLatency() == 0)
zeroLatencyDepth =
std::max(zeroLatencyDepth, getZeroLatencyDepth(Pred) + 1);
if (IE.ignoreDependence(true))
continue;
asap = std::max(asap, (int)(getASAP(Pred) + IE.getLatency() -
IE.getDistance() * MII));
}
maxASAP = std::max(maxASAP, asap);
ScheduleInfo[I].ASAP = asap;
ScheduleInfo[I].ZeroLatencyDepth = zeroLatencyDepth;
}
// Compute ALAP, ZeroLatencyHeight, and MOV.
for (int I : llvm::reverse(Topo)) {
int alap = maxASAP;
int zeroLatencyHeight = 0;
SUnit *SU = &SUnits[I];
for (const auto &OE : DDG->getOutEdges(SU)) {
SUnit *Succ = OE.getDst();
if (Succ->isBoundaryNode())
continue;
if (OE.getLatency() == 0)
zeroLatencyHeight =
std::max(zeroLatencyHeight, getZeroLatencyHeight(Succ) + 1);
if (OE.ignoreDependence(true))
continue;
alap = std::min(alap, (int)(getALAP(Succ) - OE.getLatency() +
OE.getDistance() * 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, SwingSchedulerDDG *DDG,
const NodeSet *S = nullptr) {
Preds.clear();
for (SUnit *SU : NodeOrder) {
for (const auto &IE : DDG->getInEdges(SU)) {
SUnit *PredSU = IE.getSrc();
if (S && S->count(PredSU) == 0)
continue;
if (IE.ignoreDependence(true))
continue;
if (NodeOrder.count(PredSU) == 0)
Preds.insert(PredSU);
}
// FIXME: The following loop-carried dependencies may also need to be
// considered.
// - Physical register dependencies (true-dependence and WAW).
// - Memory dependencies.
for (const auto &OE : DDG->getOutEdges(SU)) {
SUnit *SuccSU = OE.getDst();
if (!OE.isAntiDep())
continue;
if (S && S->count(SuccSU) == 0)
continue;
if (NodeOrder.count(SuccSU) == 0)
Preds.insert(SuccSU);
}
}
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, SwingSchedulerDDG *DDG,
const NodeSet *S = nullptr) {
Succs.clear();
for (SUnit *SU : NodeOrder) {
for (const auto &OE : DDG->getOutEdges(SU)) {
SUnit *SuccSU = OE.getDst();
if (S && S->count(SuccSU) == 0)
continue;
if (OE.ignoreDependence(false))
continue;
if (NodeOrder.count(SuccSU) == 0)
Succs.insert(SuccSU);
}
// FIXME: The following loop-carried dependencies may also need to be
// considered.
// - Physical register dependnecies (true-dependnece and WAW).
// - Memory dependencies.
for (const auto &IE : DDG->getInEdges(SU)) {
SUnit *PredSU = IE.getSrc();
if (!IE.isAntiDep())
continue;
if (S && S->count(PredSU) == 0)
continue;
if (NodeOrder.count(PredSU) == 0)
Succs.insert(PredSU);
}
}
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,
SwingSchedulerDDG *DDG) {
if (Cur->isBoundaryNode())
return false;
if (Exclude.contains(Cur))
return false;
if (DestNodes.contains(Cur))
return true;
if (!Visited.insert(Cur).second)
return Path.contains(Cur);
bool FoundPath = false;
for (const auto &OE : DDG->getOutEdges(Cur))
if (!OE.ignoreDependence(false))
FoundPath |=
computePath(OE.getDst(), Path, DestNodes, Exclude, Visited, DDG);
for (const auto &IE : DDG->getInEdges(Cur))
if (IE.isAntiDep() && IE.getDistance() == 0)
FoundPath |=
computePath(IE.getSrc(), Path, DestNodes, Exclude, Visited, DDG);
if (FoundPath)
Path.insert(Cur);
return FoundPath;
}
/// 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<VRegMaskOrUnit, 8> LiveOutRegs;
SmallSet<VirtRegOrUnit, 4> Uses;
for (SUnit *SU : NS) {
const MachineInstr *MI = SU->getInstr();
if (MI->isPHI())
continue;
for (const MachineOperand &MO : MI->all_uses()) {
Register Reg = MO.getReg();
if (Reg.isVirtual())
Uses.insert(VirtRegOrUnit(Reg));
else if (MRI.isAllocatable(Reg))
for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))
Uses.insert(VirtRegOrUnit(Unit));
}
}
for (SUnit *SU : NS)
for (const MachineOperand &MO : SU->getInstr()->all_defs())
if (!MO.isDead()) {
Register Reg = MO.getReg();
if (Reg.isVirtual()) {
if (!Uses.count(VirtRegOrUnit(Reg)))
LiveOutRegs.emplace_back(VirtRegOrUnit(Reg),
LaneBitmask::getNone());
} else if (MRI.isAllocatable(Reg)) {
for (MCRegUnit Unit : TRI->regunits(Reg.asMCReg()))
if (!Uses.count(VirtRegOrUnit(Unit)))
LiveOutRegs.emplace_back(VirtRegOrUnit(Unit),
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, [](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 << " "
<< TRI->getRegPressureSetName(RPDelta.Excess.getPSet())
<< ":" << RPDelta.Excess.getUnitInc() << "\n");
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, DDG.get()))
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, DDG.get()))
continue;
if (llvm::set_is_subset(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");
}
/// Add the nodes that do not belong to a recurrence set into groups
/// based upon connected components.
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, DDG.get())) {
SetVector<SUnit *> Path;
for (SUnit *NI : N) {
Visited.clear();
computePath(NI, Path, NodesAdded, I, Visited, DDG.get());
}
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, DDG.get())) {
SetVector<SUnit *> Path;
for (SUnit *NI : N) {
Visited.clear();
computePath(NI, Path, I, NodesAdded, Visited, DDG.get());
}
if (!Path.empty())
I.insert(Path.begin(), Path.end());
}
NodesAdded.insert_range(I);
}
// 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, DDG.get()))
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, DDG.get()))
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 (SUnit &SU : SUnits) {
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 of its connected nodes to the set.
void SwingSchedulerDAG::addConnectedNodes(SUnit *SU, NodeSet &NewSet,
SetVector<SUnit *> &NodesAdded) {
NewSet.insert(SU);
NodesAdded.insert(SU);
for (auto &OE : DDG->getOutEdges(SU)) {
SUnit *Successor = OE.getDst();
if (!OE.isArtificial() && !Successor->isBoundaryNode() &&
NodesAdded.count(Successor) == 0)
addConnectedNodes(Successor, NewSet, NodesAdded);
}
for (auto &IE : DDG->getInEdges(SU)) {
SUnit *Predecessor = IE.getSrc();
if (!IE.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 (SUnit *SU : Set1) {
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 (SUnit *SU : *J)
I->insert(SU);
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, DDG.get()) && llvm::set_is_subset(N, Nodes)) {
R.insert_range(N);
Order = BottomUp;
LLVM_DEBUG(dbgs() << " Bottom up (preds) ");
} else if (succ_L(NodeOrder, N, DDG.get()) &&
llvm::set_is_subset(N, Nodes)) {
R.insert_range(N);
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 (const 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 << " ");
R.remove(maxHeight);
for (const auto &OE : DDG->getOutEdges(maxHeight)) {
SUnit *SU = OE.getDst();
if (Nodes.count(SU) == 0)
continue;
if (NodeOrder.contains(SU))
continue;
if (OE.ignoreDependence(false))
continue;
R.insert(SU);
}
// FIXME: The following loop-carried dependencies may also need to be
// considered.
// - Physical register dependnecies (true-dependnece and WAW).
// - Memory dependencies.
for (const auto &IE : DDG->getInEdges(maxHeight)) {
SUnit *SU = IE.getSrc();
if (!IE.isAntiDep())
continue;
if (Nodes.count(SU) == 0)
continue;
if (NodeOrder.contains(SU))
continue;
R.insert(SU);
}
}
Order = BottomUp;
LLVM_DEBUG(dbgs() << "\n Switching order to bottom up ");
SmallSetVector<SUnit *, 8> N;
if (pred_L(NodeOrder, N, DDG.get(), &Nodes))
R.insert_range(N);
} 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 << " ");
R.remove(maxDepth);
if (Nodes.isExceedSU(maxDepth)) {
Order = TopDown;
R.clear();
R.insert(Nodes.getNode(0));
break;
}
for (const auto &IE : DDG->getInEdges(maxDepth)) {
SUnit *SU = IE.getSrc();
if (Nodes.count(SU) == 0)
continue;
if (NodeOrder.contains(SU))
continue;
R.insert(SU);
}
// FIXME: The following loop-carried dependencies may also need to be
// considered.
// - Physical register dependnecies (true-dependnece and WAW).
// - Memory dependencies.
for (const auto &OE : DDG->getOutEdges(maxDepth)) {
SUnit *SU = OE.getDst();
if (!OE.isAntiDep())
continue;
if (Nodes.count(SU) == 0)
continue;
if (NodeOrder.contains(SU))
continue;
R.insert(SU);
}
}
Order = TopDown;
LLVM_DEBUG(dbgs() << "\n Switching order to top down ");
SmallSetVector<SUnit *, 8> N;
if (succ_L(NodeOrder, N, DDG.get(), &Nodes))
R.insert_range(N);
}
}
LLVM_DEBUG(dbgs() << "\nDone with Nodeset\n");
}
LLVM_DEBUG({
dbgs() << "Node order: ";
for (SUnit *I : NodeOrder)
dbgs() << " " << *I << " ";
dbgs() << "\n";
});
}
/// Set the policy for this loop, allowing the target to override it.
void SwingSchedulerDAG::initPolicy() {
MF.getSubtarget().overridePipelinerPolicy(Policy);
// After subtarget overrides, apply command line options.
if (LimitRegPressure.getNumOccurrences())
Policy.ShouldLimitRegPressure = LimitRegPressure;
}
/// 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()){
LLVM_DEBUG(dbgs() << "NodeOrder is empty! abort scheduling\n" );
return false;
}
bool scheduleFound = false;
std::unique_ptr<HighRegisterPressureDetector> HRPDetector;
if (Policy.ShouldLimitRegPressure) {
HRPDetector =
std::make_unique<HighRegisterPressureDetector>(Loop.getHeader(), MF);
HRPDetector->init(RegClassInfo);
}
// Keep increasing II until a valid schedule is found.
for (unsigned II = MII; II <= MAX_II && !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;
Schedule.computeStart(SU, &EarlyStart, &LateStart, II, this);
LLVM_DEBUG({
dbgs() << "\n";
dbgs() << *SU << " ";
SU->getInstr()->dump();
dbgs() << "\n";
});
LLVM_DEBUG(
dbgs() << format("\tes: %8x ls: %8x\n", EarlyStart, LateStart));
if (EarlyStart > LateStart)
scheduleFound = false;
else if (EarlyStart != INT_MIN && LateStart == INT_MAX)
scheduleFound =
Schedule.insert(SU, EarlyStart, EarlyStart + (int)II - 1, II);
else if (EarlyStart == INT_MIN && LateStart != INT_MAX)
scheduleFound =
Schedule.insert(SU, LateStart, LateStart - (int)II + 1, II);
else if (EarlyStart != INT_MIN && LateStart != INT_MAX) {
LateStart = 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.
// Also, do backward search when all scheduled predecessors are
// loop-carried output/order dependencies. Empirically, there are also
// cases where scheduling becomes possible with backward search.
if (SU->getInstr()->isPHI() ||
Schedule.onlyHasLoopCarriedOutputOrOrderPreds(SU, this->getDDG()))
scheduleFound = Schedule.insert(SU, LateStart, EarlyStart, II);
else
scheduleFound = Schedule.insert(SU, EarlyStart, LateStart, 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, validate it against the validation-only
// dependencies.
if (scheduleFound)
scheduleFound = DDG->isValidSchedule(Schedule);
// If a schedule is found, ensure non-pipelined instructions are in stage 0
if (scheduleFound)
scheduleFound =
Schedule.normalizeNonPipelinedInstructions(this, LoopPipelinerInfo);
// If a schedule is found, check if it is a valid schedule too.
if (scheduleFound)
scheduleFound = Schedule.isValidSchedule(this);
// If a schedule was found and the detector is enabled, check if the
// schedule might generate additional register spills/fills.
if (scheduleFound && HRPDetector)
scheduleFound =
!HRPDetector->detect(this, Schedule, Schedule.getMaxStageCount());
}
LLVM_DEBUG(dbgs() << "Schedule Found? " << scheduleFound
<< " (II=" << Schedule.getInitiationInterval()
<< ")\n");
if (scheduleFound) {
scheduleFound = LoopPipelinerInfo->shouldUseSchedule(*this, Schedule);
if (!scheduleFound)
LLVM_DEBUG(dbgs() << "Target rejected schedule\n");
}
if (scheduleFound) {
Schedule.finalizeSchedule(this);
ORE->emit([&]() {
return MachineOptimizationRemarkAnalysis(
DEBUG_TYPE, "schedule", Loop.getStartLoc(), Loop.getHeader())
<< "Schedule found with Initiation Interval: "
<< ore::NV("II", Schedule.getInitiationInterval())
<< ", MaxStageCount: "
<< ore::NV("MaxStageCount", Schedule.getMaxStageCount());
});
} else
Schedule.reset();
return scheduleFound && Schedule.getMaxStageCount() > 0;
}
static Register findUniqueOperandDefinedInLoop(const MachineInstr &MI) {
const MachineRegisterInfo &MRI = MI.getParent()->getParent()->getRegInfo();
Register Result;
for (const MachineOperand &Use : MI.all_uses()) {
Register Reg = Use.getReg();
if (!Reg.isVirtual())
return Register();
if (MRI.getDefBlock(Reg) != MI.getParent())
continue;
if (Result)
return Register();
Result = Reg;
}
return Result;
}
/// When Op is a value that is incremented recursively in a loop and there is a
/// unique instruction that increments it, returns true and sets Value.
static bool findLoopIncrementValue(const MachineInstr &MI,
const MachineOperand &Op, int &Value) {
if (!Op.isReg() || !Op.getReg().isVirtual())
return false;
Register OrgReg = Op.getReg();
Register CurReg = OrgReg;
const MachineBasicBlock *LoopBB = MI.getParent();
const MachineRegisterInfo &MRI = LoopBB->getParent()->getRegInfo();
const TargetInstrInfo *TII =
LoopBB->getParent()->getSubtarget().getInstrInfo();
MachineInstr *Phi = nullptr;
MachineInstr *Increment = nullptr;
// Traverse definitions until it reaches Op or an instruction that does not
// satisfy the condition.
// Acceptable example:
// bb.0:
// %0 = PHI %3, %bb.0, ...
// %2 = ADD %0, Value
// ... = LOAD %2(Op)
// %3 = COPY %2
while (true) {
if (!CurReg.isValid() || !CurReg.isVirtual())
return false;
MachineInstr *Def = MRI.getVRegDef(CurReg);
if (Def->getParent() != LoopBB)
return false;
if (Def->isCopy()) {
// Ignore copy instructions unless they contain subregisters
if (Def->getOperand(0).getSubReg() || Def->getOperand(1).getSubReg())
return false;
CurReg = Def->getOperand(1).getReg();
} else if (Def->isPHI()) {
// There must be just one Phi
if (Phi)
return false;
Phi = Def;
CurReg = getLoopPhiReg(*Def, LoopBB);
} else if (TII->getIncrementValue(*Def, Value)) {
// Potentially a unique increment
if (Increment)
// Multiple increments exist
return false;
const MachineOperand *BaseOp;
int64_t Offset;
bool OffsetIsScalable;
if (TII->getMemOperandWithOffset(*Def, BaseOp, Offset,
OffsetIsScalable)) {
// Pre/post increment instruction
CurReg = BaseOp->getReg();
} else {
// If only one of the operands is defined within the loop, it is assumed
// to be an incremented value.
CurReg = findUniqueOperandDefinedInLoop(*Def);
if (!CurReg.isValid())
return false;
}
Increment = Def;
} else {
return false;
}
if (CurReg == OrgReg)
break;
}
if (!Phi || !Increment)
return false;
return true;
}
/// Return true if we can compute the amount the instruction changes
/// during each iteration. Set Delta to the amount of the change.
bool SwingSchedulerDAG::computeDelta(const MachineInstr &MI, int &Delta) const {
const MachineOperand *BaseOp;
int64_t Offset;
bool OffsetIsScalable;
if (!TII->getMemOperandWithOffset(MI, BaseOp, Offset, OffsetIsScalable))
return false;
// FIXME: This algorithm assumes instructions have fixed-size offsets.
if (OffsetIsScalable)
return false;
if (!BaseOp->isReg())
return false;
return findLoopIncrementValue(MI, *BaseOp, Delta);
}
/// 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.
bool SwingSchedulerDAG::canUseLastOffsetValue(MachineInstr *MI,
unsigned &BasePos,
unsigned &OffsetPos,
Register &NewBase,
int64_t &Offset) {
// Get the load instruction.
if (TII->isPostIncrement(*MI))
return false;
unsigned BasePosLd, OffsetPosLd;
if (!TII->getBaseAndOffsetPosition(*MI, BasePosLd, OffsetPosLd))
return false;
Register BaseReg = MI->getOperand(BasePosLd).getReg();
// Look for the Phi instruction.
MachineRegisterInfo &MRI = MI->getMF()->getRegInfo();
MachineInstr *Phi = MRI.getVRegDef(BaseReg);
if (!Phi || !Phi->isPHI())
return false;
// Get the register defined in the loop block.
Register PrevReg = getLoopPhiReg(*Phi, MI->getParent());
if (!PrevReg)
return false;
// Check for the post-increment load/store instruction.
MachineInstr *PrevDef = MRI.getVRegDef(PrevReg);
if (!PrevDef || PrevDef == MI)
return false;
if (!TII->isPostIncrement(*PrevDef))
return false;
unsigned BasePos1 = 0, OffsetPos1 = 0;
if (!TII->getBaseAndOffsetPosition(*PrevDef, BasePos1, OffsetPos1))
return false;
// Make sure that the instructions do not access the same memory location in
// the next iteration.
int64_t LoadOffset = MI->getOperand(OffsetPosLd).getImm();
int64_t StoreOffset = PrevDef->getOperand(OffsetPos1).getImm();
MachineInstr *NewMI = MF.CloneMachineInstr(MI);
NewMI->getOperand(OffsetPosLd).setImm(LoadOffset + StoreOffset);
bool Disjoint = TII->areMemAccessesTriviallyDisjoint(*NewMI, *PrevDef);
MF.deleteMachineInstr(NewMI);
if (!Disjoint)
return false;
// Set the return value once we determine that we return true.
BasePos = BasePosLd;
OffsetPos = OffsetPosLd;
NewBase = PrevReg;
Offset = StoreOffset;
return true;
}
/// Apply changes to the instruction if needed. The changes are need
/// to improve the scheduling and depend up on the final schedule.
void SwingSchedulerDAG::applyInstrChange(MachineInstr *MI,
SMSchedule &Schedule) {
SUnit *SU = getSUnit(MI);
DenseMap<SUnit *, std::pair<Register, int64_t>>::iterator It =
InstrChanges.find(SU);
if (It != InstrChanges.end()) {
std::pair<Register, int64_t> RegAndOffset = It->second;
unsigned BasePos, OffsetPos;
if (!TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
return;
Register BaseReg = MI->getOperand(BasePos).getReg();
MachineInstr *LoopDef = findDefInLoop(BaseReg);
int DefStageNum = Schedule.stageScheduled(getSUnit(LoopDef));
int DefCycleNum = Schedule.cycleScheduled(getSUnit(LoopDef));
int BaseStageNum = Schedule.stageScheduled(SU);
int BaseCycleNum = Schedule.cycleScheduled(SU);
if (BaseStageNum < DefStageNum) {
MachineInstr *NewMI = MF.CloneMachineInstr(MI);
int OffsetDiff = DefStageNum - BaseStageNum;
if (DefCycleNum < BaseCycleNum) {
NewMI->getOperand(BasePos).setReg(RegAndOffset.first);
if (OffsetDiff > 0)
--OffsetDiff;
}
int64_t NewOffset =
MI->getOperand(OffsetPos).getImm() + RegAndOffset.second * OffsetDiff;
NewMI->getOperand(OffsetPos).setImm(NewOffset);
SU->setInstr(NewMI);
MISUnitMap[NewMI] = SU;
NewMIs[MI] = NewMI;
}
}
}
/// 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.
MachineInstr *SwingSchedulerDAG::findDefInLoop(Register Reg) {
SmallPtrSet<MachineInstr *, 8> Visited;
MachineInstr *Def = MRI.getVRegDef(Reg);
while (Def->isPHI()) {
if (!Visited.insert(Def).second)
break;
for (unsigned i = 1, e = Def->getNumOperands(); i < e; i += 2)
if (Def->getOperand(i + 1).getMBB() == BB) {
Def = MRI.getVRegDef(Def->getOperand(i).getReg());
break;
}
}
return Def;
}
/// Return false if there is no overlap between the region accessed by BaseMI in
/// an iteration and the region accessed by OtherMI in subsequent iterations.
bool SwingSchedulerDAG::mayOverlapInLaterIter(
const MachineInstr *BaseMI, const MachineInstr *OtherMI) const {
int DeltaB, DeltaO, Delta;
if (!computeDelta(*BaseMI, DeltaB) || !computeDelta(*OtherMI, DeltaO) ||
DeltaB != DeltaO)
return true;
Delta = DeltaB;
const MachineOperand *BaseOpB, *BaseOpO;
int64_t OffsetB, OffsetO;
bool OffsetBIsScalable, OffsetOIsScalable;
if (!TII->getMemOperandWithOffset(*BaseMI, BaseOpB, OffsetB,
OffsetBIsScalable) ||
!TII->getMemOperandWithOffset(*OtherMI, BaseOpO, OffsetO,
OffsetOIsScalable))
return true;
if (OffsetBIsScalable || OffsetOIsScalable)
return true;
if (!BaseOpB->isIdenticalTo(*BaseOpO)) {
// Pass cases with different base operands but same initial values.
// Typically for when pre/post increment is used.
if (!BaseOpB->isReg() || !BaseOpO->isReg())
return true;
Register RegB = BaseOpB->getReg(), RegO = BaseOpO->getReg();
if (!RegB.isVirtual() || !RegO.isVirtual())
return true;
MachineInstr *DefB = MRI.getVRegDef(BaseOpB->getReg());
MachineInstr *DefO = MRI.getVRegDef(BaseOpO->getReg());
if (!DefB || !DefO || !DefB->isPHI() || !DefO->isPHI())
return true;
Register InitValB;
Register LoopValB;
Register InitValO;
Register LoopValO;
getPhiRegs(*DefB, BB, InitValB, LoopValB);
getPhiRegs(*DefO, BB, InitValO, LoopValO);
MachineInstr *InitDefB = MRI.getVRegDef(InitValB);
MachineInstr *InitDefO = MRI.getVRegDef(InitValO);
if (!InitDefB->isIdenticalTo(*InitDefO))
return true;
}
LocationSize AccessSizeB = (*BaseMI->memoperands_begin())->getSize();
LocationSize AccessSizeO = (*OtherMI->memoperands_begin())->getSize();
// This is the main test, which checks the offset values and the loop
// increment value to determine if the accesses may be loop carried.
if (!AccessSizeB.hasValue() || !AccessSizeO.hasValue())
return true;
LLVM_DEBUG({
dbgs() << "Overlap check:\n";
dbgs() << " BaseMI: ";
BaseMI->dump();
dbgs() << " Base + " << OffsetB << " + I * " << Delta
<< ", Len: " << AccessSizeB.getValue() << "\n";
dbgs() << " OtherMI: ";
OtherMI->dump();
dbgs() << " Base + " << OffsetO << " + I * " << Delta
<< ", Len: " << AccessSizeO.getValue() << "\n";
});
// Excessive overlap may be detected in strided patterns.
// For example, the memory addresses of the store and the load in
// for (i=0; i<n; i+=2) a[i+1] = a[i];
// are assumed to overlap.
if (Delta < 0) {
int64_t BaseMinAddr = OffsetB;
int64_t OhterNextIterMaxAddr = OffsetO + Delta + AccessSizeO.getValue() - 1;
if (BaseMinAddr > OhterNextIterMaxAddr) {
LLVM_DEBUG(dbgs() << " Result: No overlap\n");
return false;
}
} else {
int64_t BaseMaxAddr = OffsetB + AccessSizeB.getValue() - 1;
int64_t OtherNextIterMinAddr = OffsetO + Delta;
if (BaseMaxAddr < OtherNextIterMinAddr) {
LLVM_DEBUG(dbgs() << " Result: No overlap\n");
return false;
}
}
LLVM_DEBUG(dbgs() << " Result: Overlap\n");
return true;
}
void SwingSchedulerDAG::postProcessDAG() {
for (auto &M : Mutations)
M->apply(this);
}
/// Try to schedule the node at the specified StartCycle and continue
/// until the node is schedule or the EndCycle is reached. This function
/// returns true if the node is scheduled. This routine may search either
/// forward or backward for a place to insert the instruction based upon
/// the relative values of StartCycle and EndCycle.
bool SMSchedule::insert(SUnit *SU, int StartCycle, int EndCycle, int II) {
bool forward = true;
LLVM_DEBUG({
dbgs() << "Trying to insert node between " << StartCycle << " and "
<< EndCycle << " II: " << II << "\n";
});
if (StartCycle > EndCycle)
forward = false;
// The terminating condition depends on the direction.
int termCycle = forward ? EndCycle + 1 : EndCycle - 1;
for (int curCycle = StartCycle; curCycle != termCycle;
forward ? ++curCycle : --curCycle) {
if (ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()) ||
ProcItinResources.canReserveResources(*SU, curCycle)) {
LLVM_DEBUG({
dbgs() << "\tinsert at cycle " << curCycle << " ";
SU->getInstr()->dump();
});
if (!ST.getInstrInfo()->isZeroCost(SU->getInstr()->getOpcode()))
ProcItinResources.reserveResources(*SU, curCycle);
ScheduledInstrs[curCycle].push_back(SU);
InstrToCycle.insert(std::make_pair(SU, curCycle));
if (curCycle > LastCycle)
LastCycle = curCycle;
if (curCycle < FirstCycle)
FirstCycle = curCycle;
return true;
}
LLVM_DEBUG({
dbgs() << "\tfailed to insert at cycle " << curCycle << " ";
SU->getInstr()->dump();
});
}
return false;
}
/// If an instruction has a use that spans multiple iterations, then
/// return true. These instructions are characterized by having a back-ege
/// to a Phi, which contains a reference to another Phi.
static SUnit *multipleIterations(SUnit *SU, SwingSchedulerDAG *DAG) {
for (auto &P : SU->Preds)
if (P.getKind() == SDep::Anti && P.getSUnit()->getInstr()->isPHI())
for (auto &S : P.getSUnit()->Succs)
if (S.getKind() == SDep::Data && S.getSUnit()->getInstr()->isPHI())
return P.getSUnit();
return nullptr;
}
/// Compute the scheduling start slot for the instruction. The start slot
/// depends on any predecessor or successor nodes scheduled already.
void SMSchedule::computeStart(SUnit *SU, int *MaxEarlyStart, int *MinLateStart,
int II, SwingSchedulerDAG *DAG) {
const SwingSchedulerDDG *DDG = DAG->getDDG();
// Iterate over each instruction that has been scheduled already. The start
// slot computation depends on whether the previously scheduled instruction
// is a predecessor or successor of the specified instruction.
for (int cycle = getFirstCycle(); cycle <= LastCycle; ++cycle) {
for (SUnit *I : getInstructions(cycle)) {
for (const auto &IE : DDG->getInEdges(SU)) {
if (IE.getSrc() == I) {
int EarlyStart = cycle + IE.getLatency() - IE.getDistance() * II;
*MaxEarlyStart = std::max(*MaxEarlyStart, EarlyStart);
}
}
for (const auto &OE : DDG->getOutEdges(SU)) {
if (OE.getDst() == I) {
int LateStart = cycle - OE.getLatency() + OE.getDistance() * II;
*MinLateStart = std::min(*MinLateStart, LateStart);
}
}
SUnit *BE = multipleIterations(I, DAG);
for (const auto &Dep : SU->Preds) {
// For instruction that requires multiple iterations, make sure that
// the dependent instruction is not scheduled past the definition.
if (BE && Dep.getSUnit() == BE && !SU->getInstr()->isPHI() &&
!SU->isPred(I))
*MinLateStart = std::min(*MinLateStart, cycle);
}
}
}
}
/// Order the instructions within a cycle so that the definitions occur
/// before the uses. Returns true if the instruction is added to the start
/// of the list, or false if added to the end.
void SMSchedule::orderDependence(const SwingSchedulerDAG *SSD, SUnit *SU,
std::deque<SUnit *> &Insts) const {
MachineInstr *MI = SU->getInstr();
bool OrderBeforeUse = false;
bool OrderAfterDef = false;
bool OrderBeforeDef = false;
unsigned MoveDef = 0;
unsigned MoveUse = 0;
int StageInst1 = stageScheduled(SU);
const SwingSchedulerDDG *DDG = SSD->getDDG();
unsigned Pos = 0;
for (std::deque<SUnit *>::iterator I = Insts.begin(), E = Insts.end(); I != E;
++I, ++Pos) {
for (MachineOperand &MO : MI->operands()) {
if (!MO.isReg() || !MO.getReg().isVirtual())
continue;
Register Reg = MO.getReg();
unsigned BasePos, OffsetPos;
if (ST.getInstrInfo()->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos))
if (MI->getOperand(BasePos).getReg() == Reg)
if (Register NewReg = SSD->getInstrBaseReg(SU))
Reg = NewReg;
bool Reads, Writes;
std::tie(Reads, Writes) =
(*I)->getInstr()->readsWritesVirtualRegister(Reg);
if (MO.isDef() && Reads && stageScheduled(*I) <= StageInst1) {
OrderBeforeUse = true;
if (MoveUse == 0)
MoveUse = Pos;
} else if (MO.isDef() && Reads && stageScheduled(*I) > StageInst1) {
// Add the instruction after the scheduled instruction.
OrderAfterDef = true;
MoveDef = Pos;
} else if (MO.isUse() && Writes && stageScheduled(*I) == StageInst1) {
if (cycleScheduled(*I) == cycleScheduled(SU) && !(*I)->isSucc(SU)) {
OrderBeforeUse = true;
if (MoveUse == 0)
MoveUse = Pos;
} else {
OrderAfterDef = true;
MoveDef = Pos;
}
} else if (MO.isUse() && Writes && stageScheduled(*I) > StageInst1) {
OrderBeforeUse = true;
if (MoveUse == 0)
MoveUse = Pos;
if (MoveUse != 0) {
OrderAfterDef = true;
MoveDef = Pos - 1;
}
} else if (MO.isUse() && Writes && stageScheduled(*I) < StageInst1) {
// Add the instruction before the scheduled instruction.
OrderBeforeUse = true;
if (MoveUse == 0)
MoveUse = Pos;
} else if (MO.isUse() && stageScheduled(*I) == StageInst1 &&
isLoopCarriedDefOfUse(SSD, (*I)->getInstr(), MO)) {
if (MoveUse == 0) {
OrderBeforeDef = true;
MoveUse = Pos;
}
}
}
// Check for order dependences between instructions. Make sure the source
// is ordered before the destination.
for (auto &OE : DDG->getOutEdges(SU)) {
if (OE.getDst() != *I)
continue;
if (OE.isOrderDep() && stageScheduled(*I) == StageInst1) {
OrderBeforeUse = true;
if (Pos < MoveUse)
MoveUse = Pos;
}
// We did not handle HW dependences in previous for loop,
// and we normally set Latency = 0 for Anti/Output deps,
// so may have nodes in same cycle with Anti/Output dependent on HW regs.
else if ((OE.isAntiDep() || OE.isOutputDep()) &&
stageScheduled(*I) == StageInst1) {
OrderBeforeUse = true;
if ((MoveUse == 0) || (Pos < MoveUse))
MoveUse = Pos;
}
}
for (auto &IE : DDG->getInEdges(SU)) {
if (IE.getSrc() != *I)
continue;
if ((IE.isAntiDep() || IE.isOutputDep() || IE.isOrderDep()) &&
stageScheduled(*I) == StageInst1) {
OrderAfterDef = true;
MoveDef = Pos;
}
}
}
// A circular dependence.
if (OrderAfterDef && OrderBeforeUse && MoveUse == MoveDef)
OrderBeforeUse = false;
// OrderAfterDef takes precedences over OrderBeforeDef. The latter is due
// to a loop-carried dependence.
if (OrderBeforeDef)
OrderBeforeUse = !OrderAfterDef || (MoveUse > MoveDef);
// The uncommon case when the instruction order needs to be updated because
// there is both a use and def.
if (OrderBeforeUse && OrderAfterDef) {
SUnit *UseSU = Insts.at(MoveUse);
SUnit *DefSU = Insts.at(MoveDef);
if (MoveUse > MoveDef) {
Insts.erase(Insts.begin() + MoveUse);
Insts.erase(Insts.begin() + MoveDef);
} else {
Insts.erase(Insts.begin() + MoveDef);
Insts.erase(Insts.begin() + MoveUse);
}
orderDependence(SSD, UseSU, Insts);
orderDependence(SSD, SU, Insts);
orderDependence(SSD, DefSU, Insts);
return;
}
// Put the new instruction first if there is a use in the list. Otherwise,
// put it at the end of the list.
if (OrderBeforeUse)
Insts.push_front(SU);
else
Insts.push_back(SU);
}
/// Return true if the scheduled Phi has a loop carried operand.
bool SMSchedule::isLoopCarried(const SwingSchedulerDAG *SSD,
MachineInstr &Phi) const {
if (!Phi.isPHI())
return false;
assert(Phi.isPHI() && "Expecting a Phi.");
SUnit *DefSU = SSD->getSUnit(&Phi);
unsigned DefCycle = cycleScheduled(DefSU);
int DefStage = stageScheduled(DefSU);
Register InitVal;
Register LoopVal;
getPhiRegs(Phi, Phi.getParent(), InitVal, LoopVal);
SUnit *UseSU = SSD->getSUnit(MRI.getVRegDef(LoopVal));
if (!UseSU)
return true;
if (UseSU->getInstr()->isPHI())
return true;
unsigned LoopCycle = cycleScheduled(UseSU);
int LoopStage = stageScheduled(UseSU);
return (LoopCycle > DefCycle) || (LoopStage <= DefStage);
}
/// Return true if the instruction is a definition that is loop carried
/// and defines the use on the next iteration.
/// v1 = phi(v2, v3)
/// (Def) v3 = op v1
/// (MO) = v1
/// If MO appears before Def, then v1 and v3 may get assigned to the same
/// register.
bool SMSchedule::isLoopCarriedDefOfUse(const SwingSchedulerDAG *SSD,
MachineInstr *Def,
MachineOperand &MO) const {
if (!MO.isReg())
return false;
if (Def->isPHI())
return false;
MachineInstr *Phi = MRI.getVRegDef(MO.getReg());
if (!Phi || !Phi->isPHI() || Phi->getParent() != Def->getParent())
return false;
if (!isLoopCarried(SSD, *Phi))
return false;
Register LoopReg = getLoopPhiReg(*Phi, Phi->getParent());
for (MachineOperand &DMO : Def->all_defs()) {
if (DMO.getReg() == LoopReg)
return true;
}
return false;
}
/// Return true if all scheduled predecessors are loop-carried output/order
/// dependencies.
bool SMSchedule::onlyHasLoopCarriedOutputOrOrderPreds(
SUnit *SU, const SwingSchedulerDDG *DDG) const {
for (const auto &IE : DDG->getInEdges(SU))
if (InstrToCycle.count(IE.getSrc()))
return false;
return true;
}
/// Determine transitive dependences of unpipelineable instructions
SmallPtrSet<SUnit *, 8> SMSchedule::computeUnpipelineableNodes(
SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI) {
SmallPtrSet<SUnit *, 8> DoNotPipeline;
SmallVector<SUnit *, 8> Worklist;
for (auto &SU : SSD->SUnits)
if (SU.isInstr() && PLI->shouldIgnoreForPipelining(SU.getInstr()))
Worklist.push_back(&SU);
const SwingSchedulerDDG *DDG = SSD->getDDG();
while (!Worklist.empty()) {
auto SU = Worklist.pop_back_val();
if (DoNotPipeline.count(SU))
continue;
LLVM_DEBUG(dbgs() << "Do not pipeline SU(" << SU->NodeNum << ")\n");
DoNotPipeline.insert(SU);
for (const auto &IE : DDG->getInEdges(SU))
Worklist.push_back(IE.getSrc());
// To preserve previous behavior and prevent regression
// FIXME: Remove if this doesn't have significant impact on
for (const auto &OE : DDG->getOutEdges(SU))
if (OE.getDistance() == 1)
Worklist.push_back(OE.getDst());
}
return DoNotPipeline;
}
// Determine all instructions upon which any unpipelineable instruction depends
// and ensure that they are in stage 0. If unable to do so, return false.
bool SMSchedule::normalizeNonPipelinedInstructions(
SwingSchedulerDAG *SSD, TargetInstrInfo::PipelinerLoopInfo *PLI) {
SmallPtrSet<SUnit *, 8> DNP = computeUnpipelineableNodes(SSD, PLI);
int NewLastCycle = INT_MIN;
for (SUnit &SU : SSD->SUnits) {
if (!SU.isInstr())
continue;
if (!DNP.contains(&SU) || stageScheduled(&SU) == 0) {
NewLastCycle = std::max(NewLastCycle, InstrToCycle[&SU]);
continue;
}
// Put the non-pipelined instruction as early as possible in the schedule
int NewCycle = getFirstCycle();
for (const auto &IE : SSD->getDDG()->getInEdges(&SU))
if (IE.getDistance() == 0)
NewCycle = std::max(InstrToCycle[IE.getSrc()], NewCycle);
// To preserve previous behavior and prevent regression
// FIXME: Remove if this doesn't have significant impact on performance
for (auto &OE : SSD->getDDG()->getOutEdges(&SU))
if (OE.getDistance() == 1)
NewCycle = std::max(InstrToCycle[OE.getDst()], NewCycle);
int OldCycle = InstrToCycle[&SU];
if (OldCycle != NewCycle) {
InstrToCycle[&SU] = NewCycle;
auto &OldS = getInstructions(OldCycle);
llvm::erase(OldS, &SU);
getInstructions(NewCycle).emplace_back(&SU);
LLVM_DEBUG(dbgs() << SU << " is not pipelined; moving from cycle "
<< OldCycle << " to " << NewCycle
<< " Instr:" << *SU.getInstr());
}
// We traverse the SUs in the order of the original basic block. Computing
// NewCycle in this order normally works fine because all dependencies
// (except for loop-carried dependencies) don't violate the original order.
// However, an artificial dependency (e.g., added by CopyToPhiMutation) can
// break it. That is, there may be exist an artificial dependency from
// bottom to top. In such a case, NewCycle may become too large to be
// scheduled in Stage 0. For example, assume that Inst0 is in DNP in the
// following case:
//
// | Inst0 <-+
// SU order | | artificial dep
// | Inst1 --+
// v
//
// If Inst1 is scheduled at cycle N and is not at Stage 0, then NewCycle of
// Inst0 must be greater than or equal to N so that Inst0 is not be
// scheduled at Stage 0. In such cases, we reject this schedule at this
// time.
// FIXME: The reason for this is the existence of artificial dependencies
// that are contradict to the original SU order. If ignoring artificial
// dependencies does not affect correctness, then it is better to ignore
// them.
if (FirstCycle + InitiationInterval <= NewCycle)
return false;
NewLastCycle = std::max(NewLastCycle, NewCycle);
}
LastCycle = NewLastCycle;
return true;
}
// Check if the generated schedule is valid. This function checks if
// an instruction that uses a physical register is scheduled in a
// different stage than the definition. The pipeliner does not handle
// physical register values that may cross a basic block boundary.
// Furthermore, if a physical def/use pair is assigned to the same
// cycle, orderDependence does not guarantee def/use ordering, so that
// case should be considered invalid. (The test checks for both
// earlier and same-cycle use to be more robust.)
bool SMSchedule::isValidSchedule(SwingSchedulerDAG *SSD) {
for (SUnit &SU : SSD->SUnits) {
if (!SU.hasPhysRegDefs)
continue;
int StageDef = stageScheduled(&SU);
int CycleDef = InstrToCycle[&SU];
assert(StageDef != -1 && "Instruction should have been scheduled.");
for (auto &OE : SSD->getDDG()->getOutEdges(&SU)) {
SUnit *Dst = OE.getDst();
if (OE.isAssignedRegDep() && !Dst->isBoundaryNode())
if (OE.getReg().isPhysical()) {
if (stageScheduled(Dst) != StageDef)
return false;
if (InstrToCycle[Dst] <= CycleDef)
return false;
}
}
}
return true;
}
/// 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 order may prevent
/// the pipeliner from finding a pipelined schedule for arbitrary II,
/// it does not lead to the generation of incorrect code.
void SwingSchedulerDAG::checkValidNodeOrder(const NodeSetType &Circuits) const {
// a sorted vector that maps each SUnit to its index in the NodeOrder
typedef std::pair<SUnit *, unsigned> UnitIndex;
std::vector<UnitIndex> Indices(NodeOrder.size(), std::make_pair(nullptr, 0));
for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i)
Indices.push_back(std::make_pair(NodeOrder[i], i));
auto CompareKey = [](UnitIndex i1, UnitIndex i2) {
return std::get<0>(i1) < std::get<0>(i2);
};
// sort, so that we can perform a binary search
llvm::sort(Indices, CompareKey);
bool Valid = true;
(void)Valid;
// for each SUnit in the NodeOrder, check whether
// it appears after both a successor and a predecessor
// of the SUnit. If this is the case, and the SUnit
// is not part of circuit, then the NodeOrder is not
// valid.
for (unsigned i = 0, s = NodeOrder.size(); i < s; ++i) {
SUnit *SU = NodeOrder[i];
unsigned Index = i;
bool PredBefore = false;
bool SuccBefore = false;
SUnit *Succ;
SUnit *Pred;
(void)Succ;
(void)Pred;
for (const auto &IE : DDG->getInEdges(SU)) {
SUnit *PredSU = IE.getSrc();
unsigned PredIndex = std::get<1>(
*llvm::lower_bound(Indices, std::make_pair(PredSU, 0), CompareKey));
if (!PredSU->getInstr()->isPHI() && PredIndex < Index) {
PredBefore = true;
Pred = PredSU;
break;
}
}
for (const auto &OE : DDG->getOutEdges(SU)) {
SUnit *SuccSU = OE.getDst();
// Do not process a boundary node, it was not included in NodeOrder,
// hence not in Indices either, call to std::lower_bound() below will
// return Indices.end().
if (SuccSU->isBoundaryNode())
continue;
unsigned SuccIndex = std::get<1>(
*llvm::lower_bound(Indices, std::make_pair(SuccSU, 0), CompareKey));
if (!SuccSU->getInstr()->isPHI() && SuccIndex < Index) {
SuccBefore = true;
Succ = SuccSU;
break;
}
}
if (PredBefore && SuccBefore && !SU->getInstr()->isPHI()) {
// instructions in circuits are allowed to be scheduled
// after both a successor and predecessor.
bool InCircuit = llvm::any_of(
Circuits, [SU](const NodeSet &Circuit) { return Circuit.count(SU); });
if (InCircuit)
LLVM_DEBUG(dbgs() << "In a circuit, predecessor ");
else {
Valid = false;
NumNodeOrderIssues++;
LLVM_DEBUG(dbgs() << "Predecessor ");
}
LLVM_DEBUG(dbgs() << *Pred << " and successor " << *Succ
<< " are scheduled before node " << *SU << "\n");
}
}
LLVM_DEBUG({
if (!Valid)
dbgs() << "Invalid node order found!\n";
});
}
/// 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.
void SwingSchedulerDAG::fixupRegisterOverlaps(std::deque<SUnit *> &Instrs) {
Register OverlapReg;
Register NewBaseReg;
for (SUnit *SU : Instrs) {
MachineInstr *MI = SU->getInstr();
for (unsigned i = 0, e = MI->getNumOperands(); i < e; ++i) {
const MachineOperand &MO = MI->getOperand(i);
// Look for an instruction that uses p. The instruction occurs in the
// same cycle but occurs later in the serialized order.
if (MO.isReg() && MO.isUse() && MO.getReg() == OverlapReg) {
// Check that the instruction appears in the InstrChanges structure,
// which contains instructions that can have the offset updated.
DenseMap<SUnit *, std::pair<Register, int64_t>>::iterator It =
InstrChanges.find(SU);
if (It != InstrChanges.end()) {
unsigned BasePos, OffsetPos;
// Update the base register and adjust the offset.
if (TII->getBaseAndOffsetPosition(*MI, BasePos, OffsetPos)) {
MachineInstr *NewMI = MF.CloneMachineInstr(MI);
NewMI->getOperand(BasePos).setReg(NewBaseReg);
int64_t NewOffset =
MI->getOperand(OffsetPos).getImm() - It->second.second;
NewMI->getOperand(OffsetPos).setImm(NewOffset);
SU->setInstr(NewMI);
MISUnitMap[NewMI] = SU;
NewMIs[MI] = NewMI;
}
}
OverlapReg = Register();
NewBaseReg = Register();
break;
}
// Look for an instruction of the form p' = op(p), which uses and defines
// two virtual registers that get allocated to the same physical register.
unsigned TiedUseIdx = 0;
if (MI->isRegTiedToUseOperand(i, &TiedUseIdx)) {
// OverlapReg is p in the example above.
OverlapReg = MI->getOperand(TiedUseIdx).getReg();
// NewBaseReg is p' in the example above.
NewBaseReg = MI->getOperand(i).getReg();
break;
}
}
}
}
std::deque<SUnit *>
SMSchedule::reorderInstructions(const SwingSchedulerDAG *SSD,
const std::deque<SUnit *> &Instrs) const {
std::deque<SUnit *> NewOrderPhi;
for (SUnit *SU : Instrs) {
if (SU->getInstr()->isPHI())
NewOrderPhi.push_back(SU);
}
std::deque<SUnit *> NewOrderI;
for (SUnit *SU : Instrs) {
if (!SU->getInstr()->isPHI())
orderDependence(SSD, SU, NewOrderI);
}
llvm::append_range(NewOrderPhi, NewOrderI);
return NewOrderPhi;
}
/// After the schedule has been formed, call this function to combine
/// the instructions from the different stages/cycles. That is, this
/// function creates a schedule that represents a single iteration.
void SMSchedule::finalizeSchedule(SwingSchedulerDAG *SSD) {
// Move all instructions to the first stage from later stages.
for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
for (int stage = 1, lastStage = getMaxStageCount(); stage <= lastStage;
++stage) {
std::deque<SUnit *> &cycleInstrs =
ScheduledInstrs[cycle + (stage * InitiationInterval)];
for (SUnit *SU : llvm::reverse(cycleInstrs))
ScheduledInstrs[cycle].push_front(SU);
}
}
// Erase all the elements in the later stages. Only one iteration should
// remain in the scheduled list, and it contains all the instructions.
for (int cycle = getFinalCycle() + 1; cycle <= LastCycle; ++cycle)
ScheduledInstrs.erase(cycle);
// Change the registers in instruction as specified in the InstrChanges
// map. We need to use the new registers to create the correct order.
for (const SUnit &SU : SSD->SUnits)
SSD->applyInstrChange(SU.getInstr(), *this);
// Reorder the instructions in each cycle to fix and improve the
// generated code.
for (int Cycle = getFirstCycle(), E = getFinalCycle(); Cycle <= E; ++Cycle) {
std::deque<SUnit *> &cycleInstrs = ScheduledInstrs[Cycle];
cycleInstrs = reorderInstructions(SSD, cycleInstrs);
SSD->fixupRegisterOverlaps(cycleInstrs);
}
LLVM_DEBUG(dump(););
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
void NodeSet::print(raw_ostream &os) const {
os << "Num nodes " << size() << " rec " << RecMII << " mov " << MaxMOV
<< " depth " << MaxDepth << " col " << Colocate << "\n";
for (const auto &I : Nodes)
os << " " << *I << " " << *(I->getInstr());
os << "\n";
}
/// Print the schedule information to the given output.
void SMSchedule::print(raw_ostream &os) const {
// Iterate over each cycle.
for (int cycle = getFirstCycle(); cycle <= getFinalCycle(); ++cycle) {
// Iterate over each instruction in the cycle.
const_sched_iterator cycleInstrs = ScheduledInstrs.find(cycle);
for (SUnit *CI : cycleInstrs->second) {
os << "cycle " << cycle << " (" << stageScheduled(CI) << ") ";
os << *CI << " ";
CI->getInstr()->print(os);
os << "\n";
}
}
}
/// Utility function used for debugging to print the schedule.
LLVM_DUMP_METHOD void SMSchedule::dump() const { print(dbgs()); }
LLVM_DUMP_METHOD void NodeSet::dump() const { print(dbgs()); }
void ResourceManager::dumpMRT() const {
LLVM_DEBUG({
if (UseDFA)
return;
std::stringstream SS;
SS << "MRT:\n";
SS << std::setw(4) << "Slot";
for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I)
SS << std::setw(3) << I;
SS << std::setw(7) << "#Mops"
<< "\n";
for (int Slot = 0; Slot < InitiationInterval; ++Slot) {
SS << std::setw(4) << Slot;
for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I)
SS << std::setw(3) << MRT[Slot][I];
SS << std::setw(7) << NumScheduledMops[Slot] << "\n";
}
dbgs() << SS.str();
});
}
#endif
ResourceManager::ResourceManager(const TargetSubtargetInfo *ST,
ScheduleDAGInstrs *DAG)
: STI(ST), SM(ST->getSchedModel()), ST(ST), TII(ST->getInstrInfo()),
DAG(DAG), UseDFA(ST->useDFAforSMS()),
ProcResourceMasks(SM.getNumProcResourceKinds(), 0),
IssueWidth(SM.IssueWidth) {
initProcResourceVectors(SM, ProcResourceMasks);
if (IssueWidth <= 0)
// If IssueWidth is not specified, set a sufficiently large value
IssueWidth = 100;
if (SwpForceIssueWidth > 0)
IssueWidth = SwpForceIssueWidth;
}
void ResourceManager::initProcResourceVectors(
const MCSchedModel &SM, SmallVectorImpl<uint64_t> &Masks) {
unsigned ProcResourceID = 0;
// We currently limit the resource kinds to 64 and below so that we can use
// uint64_t for Masks
assert(SM.getNumProcResourceKinds() < 64 &&
"Too many kinds of resources, unsupported");
// Create a unique bitmask for every processor resource unit.
// Skip resource at index 0, since it always references 'InvalidUnit'.
Masks.resize(SM.getNumProcResourceKinds());
for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
const MCProcResourceDesc &Desc = *SM.getProcResource(I);
if (Desc.SubUnitsIdxBegin)
continue;
Masks[I] = 1ULL << ProcResourceID;
ProcResourceID++;
}
// Create a unique bitmask for every processor resource group.
for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
const MCProcResourceDesc &Desc = *SM.getProcResource(I);
if (!Desc.SubUnitsIdxBegin)
continue;
Masks[I] = 1ULL << ProcResourceID;
for (unsigned U = 0; U < Desc.NumUnits; ++U)
Masks[I] |= Masks[Desc.SubUnitsIdxBegin[U]];
ProcResourceID++;
}
LLVM_DEBUG({
if (SwpShowResMask) {
dbgs() << "ProcResourceDesc:\n";
for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
const MCProcResourceDesc *ProcResource = SM.getProcResource(I);
dbgs() << format(" %16s(%2d): Mask: 0x%08x, NumUnits:%2d\n",
ProcResource->Name, I, Masks[I],
ProcResource->NumUnits);
}
dbgs() << " -----------------\n";
}
});
}
bool ResourceManager::canReserveResources(SUnit &SU, int Cycle) {
LLVM_DEBUG({
if (SwpDebugResource)
dbgs() << "canReserveResources:\n";
});
if (UseDFA)
return DFAResources[positiveModulo(Cycle, InitiationInterval)]
->canReserveResources(&SU.getInstr()->getDesc());
const MCSchedClassDesc *SCDesc = DAG->getSchedClass(&SU);
if (!SCDesc->isValid()) {
LLVM_DEBUG({
dbgs() << "No valid Schedule Class Desc for schedClass!\n";
dbgs() << "isPseudo:" << SU.getInstr()->isPseudo() << "\n";
});
return true;
}
reserveResources(SCDesc, Cycle);
bool Result = !isOverbooked();
unreserveResources(SCDesc, Cycle);
LLVM_DEBUG(if (SwpDebugResource) dbgs() << "return " << Result << "\n\n");
return Result;
}
void ResourceManager::reserveResources(SUnit &SU, int Cycle) {
LLVM_DEBUG({
if (SwpDebugResource)
dbgs() << "reserveResources:\n";
});
if (UseDFA)
return DFAResources[positiveModulo(Cycle, InitiationInterval)]
->reserveResources(&SU.getInstr()->getDesc());
const MCSchedClassDesc *SCDesc = DAG->getSchedClass(&SU);
if (!SCDesc->isValid()) {
LLVM_DEBUG({
dbgs() << "No valid Schedule Class Desc for schedClass!\n";
dbgs() << "isPseudo:" << SU.getInstr()->isPseudo() << "\n";
});
return;
}
reserveResources(SCDesc, Cycle);
LLVM_DEBUG({
if (SwpDebugResource) {
dumpMRT();
dbgs() << "reserveResources: done!\n\n";
}
});
}
void ResourceManager::reserveResources(const MCSchedClassDesc *SCDesc,
int Cycle) {
assert(!UseDFA);
for (const MCWriteProcResEntry &PRE : make_range(
STI->getWriteProcResBegin(SCDesc), STI->getWriteProcResEnd(SCDesc)))
for (int C = Cycle; C < Cycle + PRE.ReleaseAtCycle; ++C)
++MRT[positiveModulo(C, InitiationInterval)][PRE.ProcResourceIdx];
for (int C = Cycle; C < Cycle + SCDesc->NumMicroOps; ++C)
++NumScheduledMops[positiveModulo(C, InitiationInterval)];
}
void ResourceManager::unreserveResources(const MCSchedClassDesc *SCDesc,
int Cycle) {
assert(!UseDFA);
for (const MCWriteProcResEntry &PRE : make_range(
STI->getWriteProcResBegin(SCDesc), STI->getWriteProcResEnd(SCDesc)))
for (int C = Cycle; C < Cycle + PRE.ReleaseAtCycle; ++C)
--MRT[positiveModulo(C, InitiationInterval)][PRE.ProcResourceIdx];
for (int C = Cycle; C < Cycle + SCDesc->NumMicroOps; ++C)
--NumScheduledMops[positiveModulo(C, InitiationInterval)];
}
bool ResourceManager::isOverbooked() const {
assert(!UseDFA);
for (int Slot = 0; Slot < InitiationInterval; ++Slot) {
for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
const MCProcResourceDesc *Desc = SM.getProcResource(I);
if (MRT[Slot][I] > Desc->NumUnits)
return true;
}
if (NumScheduledMops[Slot] > IssueWidth)
return true;
}
return false;
}
int ResourceManager::calculateResMIIDFA() const {
assert(UseDFA);
// 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(*ST);
for (SUnit &SU : DAG->SUnits)
FUS.calcCriticalResources(*SU.getInstr());
PriorityQueue<MachineInstr *, std::vector<MachineInstr *>, FuncUnitSorter>
FuncUnitOrder(FUS);
for (SUnit &SU : DAG->SUnits)
FuncUnitOrder.push(SU.getInstr());
SmallVector<std::unique_ptr<DFAPacketizer>, 8> Resources;
Resources.push_back(
std::unique_ptr<DFAPacketizer>(TII->CreateTargetScheduleState(*ST)));
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 = DAG->getSUnit(MI)->Latency;
unsigned ReservedCycles = 0;
auto *RI = Resources.begin();
auto *RE = Resources.end();
LLVM_DEBUG({
dbgs() << "Trying to reserve resource for " << NumCycles
<< " cycles for \n";
MI->dump();
});
for (unsigned C = 0; C < NumCycles; ++C)
while (RI != RE) {
if ((*RI)->canReserveResources(*MI)) {
(*RI)->reserveResources(*MI);
++ReservedCycles;
break;
}
RI++;
}
LLVM_DEBUG(dbgs() << "ReservedCycles:" << ReservedCycles
<< ", NumCycles:" << NumCycles << "\n");
// Add new DFAs, if needed, to reserve resources.
for (unsigned C = ReservedCycles; C < NumCycles; ++C) {
LLVM_DEBUG(if (SwpDebugResource) dbgs()
<< "NewResource created to reserve resources"
<< "\n");
auto *NewResource = TII->CreateTargetScheduleState(*ST);
assert(NewResource->canReserveResources(*MI) && "Reserve error.");
NewResource->reserveResources(*MI);
Resources.push_back(std::unique_ptr<DFAPacketizer>(NewResource));
}
}
int Resmii = Resources.size();
LLVM_DEBUG(dbgs() << "Return Res MII:" << Resmii << "\n");
return Resmii;
}
int ResourceManager::calculateResMII() const {
if (UseDFA)
return calculateResMIIDFA();
// Count each resource consumption and divide it by the number of units.
// ResMII is the max value among them.
int NumMops = 0;
SmallVector<uint64_t> ResourceCount(SM.getNumProcResourceKinds());
for (SUnit &SU : DAG->SUnits) {
if (TII->isZeroCost(SU.getInstr()->getOpcode()))
continue;
const MCSchedClassDesc *SCDesc = DAG->getSchedClass(&SU);
if (!SCDesc->isValid())
continue;
LLVM_DEBUG({
if (SwpDebugResource) {
DAG->dumpNode(SU);
dbgs() << " #Mops: " << SCDesc->NumMicroOps << "\n"
<< " WriteProcRes: ";
}
});
NumMops += SCDesc->NumMicroOps;
for (const MCWriteProcResEntry &PRE :
make_range(STI->getWriteProcResBegin(SCDesc),
STI->getWriteProcResEnd(SCDesc))) {
LLVM_DEBUG({
if (SwpDebugResource) {
const MCProcResourceDesc *Desc =
SM.getProcResource(PRE.ProcResourceIdx);
dbgs() << Desc->Name << ": " << PRE.ReleaseAtCycle << ", ";
}
});
ResourceCount[PRE.ProcResourceIdx] += PRE.ReleaseAtCycle;
}
LLVM_DEBUG(if (SwpDebugResource) dbgs() << "\n");
}
int Result = (NumMops + IssueWidth - 1) / IssueWidth;
LLVM_DEBUG({
if (SwpDebugResource)
dbgs() << "#Mops: " << NumMops << ", "
<< "IssueWidth: " << IssueWidth << ", "
<< "Cycles: " << Result << "\n";
});
LLVM_DEBUG({
if (SwpDebugResource) {
std::stringstream SS;
SS << std::setw(2) << "ID" << std::setw(16) << "Name" << std::setw(10)
<< "Units" << std::setw(10) << "Consumed" << std::setw(10) << "Cycles"
<< "\n";
dbgs() << SS.str();
}
});
for (unsigned I = 1, E = SM.getNumProcResourceKinds(); I < E; ++I) {
const MCProcResourceDesc *Desc = SM.getProcResource(I);
int Cycles = (ResourceCount[I] + Desc->NumUnits - 1) / Desc->NumUnits;
LLVM_DEBUG({
if (SwpDebugResource) {
std::stringstream SS;
SS << std::setw(2) << I << std::setw(16) << Desc->Name << std::setw(10)
<< Desc->NumUnits << std::setw(10) << ResourceCount[I]
<< std::setw(10) << Cycles << "\n";
dbgs() << SS.str();
}
});
if (Cycles > Result)
Result = Cycles;
}
return Result;
}
void ResourceManager::init(int II) {
InitiationInterval = II;
DFAResources.clear();
DFAResources.resize(II);
for (auto &I : DFAResources)
I.reset(ST->getInstrInfo()->CreateTargetScheduleState(*ST));
MRT.clear();
MRT.resize(II, SmallVector<uint64_t>(SM.getNumProcResourceKinds()));
NumScheduledMops.clear();
NumScheduledMops.resize(II);
}
bool SwingSchedulerDDGEdge::ignoreDependence(bool IgnoreAnti) const {
if (Pred.isArtificial() || Dst->isBoundaryNode())
return true;
// Currently, dependence that is an anti-dependences but not a loop-carried is
// also ignored. This behavior is preserved to prevent regression.
// FIXME: Remove if this doesn't have significant impact on performance
return IgnoreAnti && (Pred.getKind() == SDep::Kind::Anti || Distance != 0);
}
SwingSchedulerDDG::SwingSchedulerDDGEdges &
SwingSchedulerDDG::getEdges(const SUnit *SU) {
if (SU == EntrySU)
return EntrySUEdges;
if (SU == ExitSU)
return ExitSUEdges;
return EdgesVec[SU->NodeNum];
}
const SwingSchedulerDDG::SwingSchedulerDDGEdges &
SwingSchedulerDDG::getEdges(const SUnit *SU) const {
if (SU == EntrySU)
return EntrySUEdges;
if (SU == ExitSU)
return ExitSUEdges;
return EdgesVec[SU->NodeNum];
}
void SwingSchedulerDDG::addEdge(const SUnit *SU,
const SwingSchedulerDDGEdge &Edge) {
assert(!Edge.isValidationOnly() &&
"Validation-only edges are not expected here.");
auto &Edges = getEdges(SU);
if (Edge.getSrc() == SU)
Edges.Succs.push_back(Edge);
else
Edges.Preds.push_back(Edge);
}
void SwingSchedulerDDG::initEdges(SUnit *SU) {
for (const auto &PI : SU->Preds) {
SwingSchedulerDDGEdge Edge(SU, PI, /*IsSucc=*/false,
/*IsValidationOnly=*/false);
addEdge(SU, Edge);
}
for (const auto &SI : SU->Succs) {
SwingSchedulerDDGEdge Edge(SU, SI, /*IsSucc=*/true,
/*IsValidationOnly=*/false);
addEdge(SU, Edge);
}
}
SwingSchedulerDDG::SwingSchedulerDDG(std::vector<SUnit> &SUnits, SUnit *EntrySU,
SUnit *ExitSU, const LoopCarriedEdges &LCE)
: EntrySU(EntrySU), ExitSU(ExitSU) {
EdgesVec.resize(SUnits.size());
// Add non-loop-carried edges based on the DAG.
initEdges(EntrySU);
initEdges(ExitSU);
for (auto &SU : SUnits)
initEdges(&SU);
// Add loop-carried edges, which are not represented in the DAG.
for (SUnit &SU : SUnits) {
SUnit *Src = &SU;
if (const LoopCarriedEdges::OrderDep *OD = LCE.getOrderDepOrNull(Src)) {
SDep Base(Src, SDep::Barrier);
Base.setLatency(1);
for (SUnit *Dst : *OD) {
SwingSchedulerDDGEdge Edge(Dst, Base, /*IsSucc=*/false,
/*IsValidationOnly=*/true);
Edge.setDistance(1);
ValidationOnlyEdges.push_back(Edge);
// Store the edge as an extra edge if it meets the following conditions:
//
// - The edge is a loop-carried order dependency.
// - The edge is a back edge in terms of the original instruction
// order.
// - The destination instruction may load.
// - The source instruction may store but does not load.
//
// These conditions are inherited from a previous implementation to
// preserve the existing behavior and avoid regressions.
bool UseAsExtraEdge = [&]() {
if (Edge.getDistance() == 0 || !Edge.isOrderDep())
return false;
SUnit *Src = Edge.getSrc();
SUnit *Dst = Edge.getDst();
if (Src->NodeNum < Dst->NodeNum)
return false;
MachineInstr *SrcMI = Src->getInstr();
MachineInstr *DstMI = Dst->getInstr();
return DstMI->mayLoad() && !SrcMI->mayLoad() && SrcMI->mayStore();
}();
if (UseAsExtraEdge)
getEdges(Edge.getSrc()).ExtraSuccs.push_back(Edge.getDst());
}
}
}
}
const SwingSchedulerDDG::EdgesType &
SwingSchedulerDDG::getInEdges(const SUnit *SU) const {
return getEdges(SU).Preds;
}
const SwingSchedulerDDG::EdgesType &
SwingSchedulerDDG::getOutEdges(const SUnit *SU) const {
return getEdges(SU).Succs;
}
ArrayRef<SUnit *> SwingSchedulerDDG::getExtraOutEdges(const SUnit *SU) const {
return getEdges(SU).ExtraSuccs;
}
/// Check if \p Schedule doesn't violate the validation-only dependencies.
bool SwingSchedulerDDG::isValidSchedule(const SMSchedule &Schedule) const {
unsigned II = Schedule.getInitiationInterval();
auto ExpandCycle = [&](SUnit *SU) {
int Stage = Schedule.stageScheduled(SU);
int Cycle = Schedule.cycleScheduled(SU);
return Cycle + (Stage * II);
};
for (const SwingSchedulerDDGEdge &Edge : ValidationOnlyEdges) {
SUnit *Src = Edge.getSrc();
SUnit *Dst = Edge.getDst();
if (!Src->isInstr() || !Dst->isInstr())
continue;
int CycleSrc = ExpandCycle(Src);
int CycleDst = ExpandCycle(Dst);
int MaxLateStart = CycleDst + Edge.getDistance() * II - Edge.getLatency();
if (CycleSrc > MaxLateStart) {
LLVM_DEBUG({
dbgs() << "Validation failed for edge from " << *Src << " to " << *Dst
<< "\n";
});
return false;
}
}
return true;
}
void LoopCarriedEdges::modifySUnits(std::vector<SUnit> &SUnits,
const TargetInstrInfo *TII) {
for (SUnit &SU : SUnits) {
SUnit *Src = &SU;
if (auto *OrderDep = getOrderDepOrNull(Src)) {
SDep Dep(Src, SDep::Barrier);
Dep.setLatency(1);
for (SUnit *Dst : *OrderDep) {
SUnit *From = Src;
SUnit *To = Dst;
if (From->NodeNum > To->NodeNum)
std::swap(From, To);
// Add a forward edge if the following conditions are met:
//
// - The instruction of the source node (FromMI) may read memory.
// - The instruction of the target node (ToMI) may modify memory, but
// does not read it.
// - Neither instruction is a global barrier.
// - The load appears before the store in the original basic block.
// - There are no barrier or store instructions between the two nodes.
// - The target node is unreachable from the source node in the current
// DAG.
//
// TODO: These conditions are inherited from a previous implementation,
// and some may no longer be necessary. For now, we conservatively
// retain all of them to avoid regressions, but the logic could
// potentially be simplified
MachineInstr *FromMI = From->getInstr();
MachineInstr *ToMI = To->getInstr();
if (FromMI->mayLoad() && !ToMI->mayLoad() && ToMI->mayStore() &&
!TII->isGlobalMemoryObject(FromMI) &&
!TII->isGlobalMemoryObject(ToMI) && !isSuccOrder(From, To)) {
SDep Pred = Dep;
Pred.setSUnit(From);
To->addPred(Pred);
}
}
}
}
}
#if !defined(NDEBUG) || defined(LLVM_ENABLE_DUMP)
LLVM_DUMP_METHOD void
LoopCarriedEdges::dump(SUnit *SU, const TargetRegisterInfo *TRI,
const MachineRegisterInfo *MRI) const {
const auto *Order = getOrderDepOrNull(SU);
if (!Order)
return;
const auto DumpSU = [](const SUnit *SU) {
std::string S;
raw_string_ostream OS(S);
OS << *SU;
return S;
};
dbgs() << " Loop carried edges from " << DumpSU(SU) << "\n"
<< " Order\n";
for (SUnit *Dst : *Order)
dbgs() << " " << DumpSU(Dst) << "\n";
}
#endif