44#define DEBUG_TYPE "hardware-loops"
46#define HW_LOOPS_NAME "Hardware Loop Insertion"
50STATISTIC(NumHWLoops,
"Number of loops converted to hardware loops");
55 dbgs() <<
"HWLoops: " << DebugMsg;
70 CodeRegion =
I->getParent();
74 DL =
I->getDebugLoc();
78 R <<
"hardware-loop not created: ";
94 HardwareLoopsLegacy() : FunctionPass(ID) {}
98 void getAnalysisUsage(AnalysisUsage &AU)
const override {
107 AU.
addRequired<OptimizationRemarkEmitterWrapperPass>();
112 class HardwareLoopsImpl {
114 HardwareLoopsImpl(ScalarEvolution &SE, LoopInfo &LI,
bool PreserveLCSSA,
115 DominatorTree &DT,
const TargetTransformInfo &TTI,
116 TargetLibraryInfo *TLI, AssumptionCache &AC,
117 OptimizationRemarkEmitter *ORE, HardwareLoopOptions &Opts)
118 : SE(SE), LI(LI), PreserveLCSSA(PreserveLCSSA), DT(DT), TTI(TTI),
119 TLI(TLI), AC(AC), ORE(ORE), Opts(Opts) {}
125 bool TryConvertLoop(
Loop *L, LLVMContext &Ctx);
129 bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
135 const TargetTransformInfo &TTI;
136 TargetLibraryInfo *TLI =
nullptr;
138 OptimizationRemarkEmitter *ORE;
139 HardwareLoopOptions &Opts;
140 bool MadeChange =
false;
145 Value *InitLoopCount();
148 Value *InsertIterationSetup(
Value *LoopCountInit);
151 void InsertLoopDec();
159 PHINode *InsertPHICounter(
Value *NumElts,
Value *EltsRem);
163 void UpdateBranch(
Value *EltsRem);
166 HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
167 OptimizationRemarkEmitter *ORE, HardwareLoopOptions &Opts)
168 : SE(SE), ORE(ORE), Opts(Opts), L(
Info.L),
169 M(L->getHeader()->getModule()), ExitCount(
Info.ExitCount),
170 CountType(
Info.CountType), ExitBranch(
Info.ExitBranch),
171 LoopDecrement(
Info.LoopDecrement), UsePHICounter(
Info.CounterInReg),
172 UseLoopGuard(
Info.PerformEntryTest) {}
178 OptimizationRemarkEmitter *ORE =
nullptr;
179 HardwareLoopOptions &Opts;
182 const SCEV *ExitCount =
nullptr;
183 Type *CountType =
nullptr;
184 CondBrInst *ExitBranch =
nullptr;
185 Value *LoopDecrement =
nullptr;
186 bool UsePHICounter =
false;
187 bool UseLoopGuard =
false;
192char HardwareLoopsLegacy::ID = 0;
194bool HardwareLoopsLegacy::runOnFunction(
Function &
F) {
200 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
201 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
202 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
203 auto &
TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(
F);
204 auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
205 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
206 auto *
TLI = TLIP ? &TLIP->getTLI(
F) :
nullptr;
207 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(
F);
208 bool PreserveLCSSA = mustPreserveAnalysisID(
LCSSAID);
211 HardwareLoopOptions Opts;
216 Opts.
Decrement = CGOpts.hardware_loop_decrement;
217 Opts.
Bitwidth = CGOpts.hardware_loop_counter_bitwidth;
219 HardwareLoopsImpl Impl(SE, LI, PreserveLCSSA, DT,
TTI,
TLI, AC, ORE, Opts);
233 HardwareLoopsImpl Impl(SE, LI,
true, DT,
TTI,
TLI, AC, ORE, Opts);
246bool HardwareLoopsImpl::run(
Function &
F) {
249 if (L->isOutermost())
250 TryConvertLoop(L, Ctx);
258 bool AnyChanged =
false;
260 AnyChanged |= TryConvertLoop(SL, Ctx);
262 reportHWLoopFailure(
"nested hardware-loops not supported",
"HWLoopNested",
267 LLVM_DEBUG(
dbgs() <<
"HWLoops: Loop " <<
L->getHeader()->getName() <<
"\n");
269 HardwareLoopInfo HWLoopInfo(L);
270 if (!HWLoopInfo.canAnalyze(LI)) {
271 reportHWLoopFailure(
"cannot analyze loop, irreducible control flow",
272 "HWLoopCannotAnalyze", ORE, L);
278 reportHWLoopFailure(
"it's not profitable to create a hardware-loop",
279 "HWLoopNotProfitable", ORE, L);
289 HWLoopInfo.LoopDecrement =
290 ConstantInt::get(HWLoopInfo.CountType, Opts.
Decrement.value());
292 MadeChange |= TryConvertLoop(HWLoopInfo);
293 return MadeChange && (!HWLoopInfo.IsNestingLegal && !Opts.
ForceNested);
296bool HardwareLoopsImpl::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
299 LLVM_DEBUG(
dbgs() <<
"HWLoops: Try to convert profitable loop: " << *L);
306 reportHWLoopFailure(
"loop is not a candidate",
"HWLoopNoCandidate", ORE, L);
312 "Hardware Loop must have set exit info.");
322 HardwareLoop HWLoop(HWLoopInfo, SE, ORE, Opts);
328void HardwareLoop::Create() {
331 Value *LoopCountInit = InitLoopCount();
332 if (!LoopCountInit) {
333 reportHWLoopFailure(
"could not safely create a loop count expression",
334 "HWLoopNotSafe", ORE, L);
338 Value *
Setup = InsertIterationSetup(LoopCountInit);
340 if (UsePHICounter || Opts.
ForcePhi) {
341 Instruction *LoopDec = InsertLoopRegDec(LoopCountInit);
342 Value *EltsRem = InsertPHICounter(Setup, LoopDec);
344 UpdateBranch(LoopDec);
350 for (
auto *
I :
L->blocks())
355 BasicBlock *Preheader = L->getLoopPreheader();
368 if (!ICmp->isEquality())
378 Value *CountBefZext =
381 if (!IsCompareZero(ICmp,
Count, 0) && !IsCompareZero(ICmp,
Count, 1) &&
382 !IsCompareZero(ICmp, CountBefZext, 0) &&
383 !IsCompareZero(ICmp, CountBefZext, 1))
387 if (BI->getSuccessor(SuccIdx) != Preheader)
393Value *HardwareLoop::InitLoopCount() {
394 LLVM_DEBUG(
dbgs() <<
"HWLoops: Initialising loop counter value:\n");
398 SCEVExpander SCEVE(SE,
"loopcnt");
400 ExitCount->
getType() != CountType)
415 UseLoopGuard =
false;
423 if (!SCEVE.isSafeToExpandAt(ExitCount, Predecessor->
getTerminator()))
424 UseLoopGuard =
false;
429 if (!SCEVE.isSafeToExpandAt(ExitCount, BB->
getTerminator())) {
431 << *ExitCount <<
"\n");
435 Value *
Count = SCEVE.expandCodeFor(ExitCount, CountType,
446 BeginBB = UseLoopGuard ? BB :
L->getLoopPreheader();
448 <<
" - Expanded Count in " << BB->
getName() <<
"\n"
449 <<
" - Will insert set counter intrinsic into: "
450 << BeginBB->
getName() <<
"\n");
454Value* HardwareLoop::InsertIterationSetup(
Value *LoopCountInit) {
457 Builder.setIsFPConstrained(
true);
459 bool UsePhi = UsePHICounter || Opts.
ForcePhi;
461 ? (UsePhi ? Intrinsic::test_start_loop_iterations
462 : Intrinsic::test_set_loop_iterations)
463 : (UsePhi ?
Intrinsic::start_loop_iterations
465 Value *LoopSetup = Builder.CreateIntrinsic(ID, Ty, LoopCountInit);
470 UsePhi ? Builder.CreateExtractValue(LoopSetup, 1) : LoopSetup;
472 LoopGuard->setCondition(SetCount);
473 if (LoopGuard->getSuccessor(0) !=
L->getLoopPreheader())
474 LoopGuard->swapSuccessors();
476 LLVM_DEBUG(
dbgs() <<
"HWLoops: Inserted loop counter: " << *LoopSetup
478 if (UsePhi && UseLoopGuard)
479 LoopSetup = Builder.CreateExtractValue(LoopSetup, 0);
480 return !UsePhi ? LoopCountInit : LoopSetup;
483void HardwareLoop::InsertLoopDec() {
485 if (ExitBranch->
getParent()->getParent()->getAttributes().hasFnAttr(
486 Attribute::StrictFP))
487 CondBuilder.setIsFPConstrained(
true);
490 Value *NewCond = CondBuilder.CreateIntrinsic(Intrinsic::loop_decrement,
503 LLVM_DEBUG(
dbgs() <<
"HWLoops: Inserted loop dec: " << *NewCond <<
"\n");
508 if (ExitBranch->
getParent()->getParent()->getAttributes().hasFnAttr(
509 Attribute::StrictFP))
510 CondBuilder.setIsFPConstrained(
true);
512 Value *
Ops[] = { EltsRem, LoopDecrement };
513 Value *
Call = CondBuilder.CreateIntrinsic(Intrinsic::loop_decrement_reg,
520PHINode* HardwareLoop::InsertPHICounter(
Value *NumElts,
Value *EltsRem) {
525 PHINode *
Index = Builder.CreatePHI(NumElts->
getType(), 2);
526 Index->addIncoming(NumElts, Preheader);
527 Index->addIncoming(EltsRem, Latch);
532void HardwareLoop::UpdateBranch(
Value *EltsRem) {
535 CondBuilder.CreateICmpNE(EltsRem, ConstantInt::get(EltsRem->
getType(), 0));
const TargetLowering & TLI
assert(UImm &&(UImm !=~static_cast< T >(0)) &&"Invalid immediate!")
MachineBasicBlock MachineBasicBlock::iterator DebugLoc DL
This file contains the declarations for the subclasses of Constant, which represent the different fla...
static bool runOnFunction(Function &F, bool PostInlining)
static OptimizationRemarkAnalysis createHWLoopAnalysis(StringRef RemarkName, Loop *L, Instruction *I)
static void debugHWLoopFailure(const StringRef DebugMsg, Instruction *I)
static bool CanGenerateTest(Loop *L, Value *Count)
Defines an IR pass for the creation of hardware loops.
const AbstractManglingParser< Derived, Alloc >::OperatorInfo AbstractManglingParser< Derived, Alloc >::Ops[]
#define INITIALIZE_PASS_DEPENDENCY(depName)
#define INITIALIZE_PASS_END(passName, arg, name, cfg, analysis)
#define INITIALIZE_PASS_BEGIN(passName, arg, name, cfg, analysis)
This file defines the 'Statistic' class, which is designed to be an easy way to expose various metric...
#define STATISTIC(VARNAME, DESC)
PassT::Result & getResult(IRUnitT &IR, ExtraArgTs... ExtraArgs)
Get the result of an analysis pass for a given IR unit.
AnalysisUsage & addRequired()
AnalysisUsage & addPreserved()
Add the specified Pass class to the set of analyses preserved by this pass.
A function analysis which provides an AssumptionCache.
LLVM Basic Block Representation.
const Function * getParent() const
Return the enclosing method, or null if none.
LLVM_ABI const BasicBlock * getSinglePredecessor() const
Return the predecessor of this block if it has a single predecessor block.
const Instruction * getTerminator() const LLVM_READONLY
Returns the terminator instruction; assumes that the block is well-formed.
Analysis pass which computes BranchProbabilityInfo.
Predicate getPredicate() const
Return the predicate for this instruction.
LLVM_ABI void swapSuccessors()
Swap the successors of this branch instruction.
void setCondition(Value *V)
Value * getCondition() const
BasicBlock * getSuccessor(unsigned i) const
Analysis pass which computes a DominatorTree.
FunctionPass class - This class is used to implement most global optimizations.
AttributeList getAttributes() const
Return the attribute list for this Function.
LLVM_ABI PreservedAnalyses run(Function &F, FunctionAnalysisManager &AM)
This instruction compares its operands according to the predicate given to the constructor.
static LLVM_ABI IntegerType * get(LLVMContext &C, unsigned NumBits)
This static method is the primary way of constructing an IntegerType.
This is an important class for using LLVM in a threaded context.
Analysis pass that exposes the LoopInfo for a function.
Represents a single loop in the control flow graph.
A set of analyses that are preserved following a run of a transformation pass.
static PreservedAnalyses all()
Construct a special preserved set that preserves all passes.
PreservedAnalyses & preserve()
Mark an analysis as preserved.
Type * getType() const
Return the LLVM type of this SCEV expression.
Analysis pass that exposes the ScalarEvolution for a function.
LLVM_ABI const SCEV * getZeroExtendExpr(SCEVUse Op, Type *Ty, unsigned Depth=0)
LLVM_ABI bool isLoopEntryGuardedByCond(const Loop *L, CmpPredicate Pred, const SCEV *LHS, const SCEV *RHS)
Test whether entry to the loop is protected by a conditional between LHS and RHS.
const SCEV * getZero(Type *Ty)
Return a SCEV for the constant 0 of a specific type.
const SCEV * getOne(Type *Ty)
Return a SCEV for the constant 1 of a specific type.
LLVM_ABI SCEVUse getAddExpr(SmallVectorImpl< SCEVUse > &Ops, SCEVFlagsPair Flags={}, unsigned Depth=0)
Get a canonical add expression, or something simpler if possible.
Represent a constant reference to a string, i.e.
Analysis pass providing the TargetTransformInfo.
Analysis pass providing the TargetLibraryInfo.
bool isPointerTy() const
True if this is an instance of PointerType.
void setOperand(unsigned i, Value *Val)
Value * getOperand(unsigned i) const
LLVM Value Representation.
Type * getType() const
All values are typed, get the type of this value.
LLVM_ABI StringRef getName() const
Return a constant reference to the value's name.
const ParentTy * getParent() const
@ BasicBlock
Various leaf nodes.
PointerTypeMap run(const Module &M)
Compute the PointerTypeMap for the module M.
friend class Instruction
Iterator for Instructions in a `BasicBlock.
This is an optimization pass for GlobalISel generic memory operations.
LLVM_ABI BasicBlock * InsertPreheaderForLoop(Loop *L, DominatorTree *DT, LoopInfo *LI, MemorySSAUpdater *MSSAU, bool PreserveLCSSA)
InsertPreheaderForLoop - Once we discover that a loop doesn't have a preheader, this method is called...
LLVM_ABI bool RecursivelyDeleteTriviallyDeadInstructions(Value *V, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, std::function< void(Value *)> AboutToDeleteCallback=std::function< void(Value *)>())
If the specified value is a trivially dead instruction, delete it.
decltype(auto) dyn_cast(const From &Val)
dyn_cast<X> - Return the argument parameter cast to the specified type.
LLVM_ABI bool DeleteDeadPHIs(BasicBlock *BB, const TargetLibraryInfo *TLI=nullptr, MemorySSAUpdater *MSSAU=nullptr, SmallPtrSetImpl< PHINode * > *KnownNonDeadPHIs=nullptr)
Examine each PHI in the given block and delete it if it is dead.
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Value
LLVM_ABI raw_ostream & dbgs()
dbgs() - This returns a reference to a raw_ostream for debugging messages.
IRBuilder(LLVMContext &, FolderTy, InserterTy) -> IRBuilder< FolderTy, InserterTy >
bool isa(const From &Val)
isa<X> - Return true if the parameter to the template is an instance of one of the template type argu...
RelativeUniformCounterPtr ValuesPtrExpr VTableAddr Count
constexpr std::optional< bool > toOptional(BoolOrDefault X)
decltype(auto) cast(const From &Val)
cast<X> - Return the argument parameter cast to the specified type.
AnalysisManager< Function > FunctionAnalysisManager
Convenience typedef for the Function analysis manager.
LLVM_ABI FunctionPass * createHardwareLoopsLegacyPass()
Create Hardware Loop pass.
const CodeGenOptions & getCodeGenOptions(const LLVMContext &C)
LLVM_ABI bool isHardwareLoopCandidate(ScalarEvolution &SE, LoopInfo &LI, DominatorTree &DT, bool ForceNestedLoop=false, bool ForceHardwareLoopPHI=false)
std::optional< bool > Force
std::optional< bool > ForceGuard
std::optional< unsigned > Decrement
std::optional< unsigned > Bitwidth
std::optional< bool > ForcePhi
std::optional< bool > ForceNested
bool getForceNested() const