1 //===-- HardwareLoops.cpp - Target Independent Hardware Loops --*- C++ -*-===//
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
7 //===----------------------------------------------------------------------===//
9 /// Insert hardware loop intrinsics into loops which are deemed profitable by
10 /// the target, by querying TargetTransformInfo. A hardware loop comprises of
11 /// two intrinsics: one, outside the loop, to set the loop iteration count and
12 /// another, in the exit block, to decrement the counter. The decremented value
13 /// can either be carried through the loop via a phi or handled in some opaque
14 /// way by the target.
16 //===----------------------------------------------------------------------===//
18 #include "llvm/ADT/Statistic.h"
19 #include "llvm/Analysis/AssumptionCache.h"
20 #include "llvm/Analysis/LoopInfo.h"
21 #include "llvm/Analysis/OptimizationRemarkEmitter.h"
22 #include "llvm/Analysis/ScalarEvolution.h"
23 #include "llvm/Analysis/ScalarEvolutionExpander.h"
24 #include "llvm/Analysis/TargetTransformInfo.h"
25 #include "llvm/CodeGen/Passes.h"
26 #include "llvm/CodeGen/TargetPassConfig.h"
27 #include "llvm/IR/BasicBlock.h"
28 #include "llvm/IR/Constants.h"
29 #include "llvm/IR/DataLayout.h"
30 #include "llvm/IR/Dominators.h"
31 #include "llvm/IR/IRBuilder.h"
32 #include "llvm/IR/Instructions.h"
33 #include "llvm/IR/IntrinsicInst.h"
34 #include "llvm/IR/Value.h"
35 #include "llvm/InitializePasses.h"
36 #include "llvm/Pass.h"
37 #include "llvm/PassRegistry.h"
38 #include "llvm/PassSupport.h"
39 #include "llvm/Support/CommandLine.h"
40 #include "llvm/Support/Debug.h"
41 #include "llvm/Transforms/Scalar.h"
42 #include "llvm/Transforms/Utils.h"
43 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
44 #include "llvm/Transforms/Utils/Local.h"
45 #include "llvm/Transforms/Utils/LoopUtils.h"
47 #define DEBUG_TYPE "hardware-loops"
49 #define HW_LOOPS_NAME "Hardware Loop Insertion"
54 ForceHardwareLoops("force-hardware-loops", cl::Hidden, cl::init(false),
55 cl::desc("Force hardware loops intrinsics to be inserted"));
59 "force-hardware-loop-phi", cl::Hidden, cl::init(false),
60 cl::desc("Force hardware loop counter to be updated through a phi"));
63 ForceNestedLoop("force-nested-hardware-loop", cl::Hidden, cl::init(false),
64 cl::desc("Force allowance of nested hardware loops"));
66 static cl::opt<unsigned>
67 LoopDecrement("hardware-loop-decrement", cl::Hidden, cl::init(1),
68 cl::desc("Set the loop decrement value"));
70 static cl::opt<unsigned>
71 CounterBitWidth("hardware-loop-counter-bitwidth", cl::Hidden, cl::init(32),
72 cl::desc("Set the loop counter bitwidth"));
76 "force-hardware-loop-guard", cl::Hidden, cl::init(false),
77 cl::desc("Force generation of loop guard intrinsic"));
79 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
82 static void debugHWLoopFailure(const StringRef DebugMsg,
84 dbgs() << "HWLoops: " << DebugMsg;
93 static OptimizationRemarkAnalysis
94 createHWLoopAnalysis(StringRef RemarkName, Loop *L, Instruction *I) {
95 Value *CodeRegion = L->getHeader();
96 DebugLoc DL = L->getStartLoc();
99 CodeRegion = I->getParent();
100 // If there is no debug location attached to the instruction, revert back to
102 if (I->getDebugLoc())
103 DL = I->getDebugLoc();
106 OptimizationRemarkAnalysis R(DEBUG_TYPE, RemarkName, DL, CodeRegion);
107 R << "hardware-loop not created: ";
113 void reportHWLoopFailure(const StringRef Msg, const StringRef ORETag,
114 OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I = nullptr) {
115 LLVM_DEBUG(debugHWLoopFailure(Msg, I));
116 ORE->emit(createHWLoopAnalysis(ORETag, TheLoop, I) << Msg);
119 using TTI = TargetTransformInfo;
121 class HardwareLoops : public FunctionPass {
125 HardwareLoops() : FunctionPass(ID) {
126 initializeHardwareLoopsPass(*PassRegistry::getPassRegistry());
129 bool runOnFunction(Function &F) override;
131 void getAnalysisUsage(AnalysisUsage &AU) const override {
132 AU.addRequired<LoopInfoWrapperPass>();
133 AU.addPreserved<LoopInfoWrapperPass>();
134 AU.addRequired<DominatorTreeWrapperPass>();
135 AU.addPreserved<DominatorTreeWrapperPass>();
136 AU.addRequired<ScalarEvolutionWrapperPass>();
137 AU.addRequired<AssumptionCacheTracker>();
138 AU.addRequired<TargetTransformInfoWrapperPass>();
139 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
142 // Try to convert the given Loop into a hardware loop.
143 bool TryConvertLoop(Loop *L);
145 // Given that the target believes the loop to be profitable, try to
147 bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
150 ScalarEvolution *SE = nullptr;
151 LoopInfo *LI = nullptr;
152 const DataLayout *DL = nullptr;
153 OptimizationRemarkEmitter *ORE = nullptr;
154 const TargetTransformInfo *TTI = nullptr;
155 DominatorTree *DT = nullptr;
156 bool PreserveLCSSA = false;
157 AssumptionCache *AC = nullptr;
158 TargetLibraryInfo *LibInfo = nullptr;
160 bool MadeChange = false;
164 // Expand the trip count scev into a value that we can use.
165 Value *InitLoopCount();
167 // Insert the set_loop_iteration intrinsic.
168 void InsertIterationSetup(Value *LoopCountInit);
170 // Insert the loop_decrement intrinsic.
171 void InsertLoopDec();
173 // Insert the loop_decrement_reg intrinsic.
174 Instruction *InsertLoopRegDec(Value *EltsRem);
176 // If the target requires the counter value to be updated in the loop,
177 // insert a phi to hold the value. The intended purpose is for use by
178 // loop_decrement_reg.
179 PHINode *InsertPHICounter(Value *NumElts, Value *EltsRem);
181 // Create a new cmp, that checks the returned value of loop_decrement*,
182 // and update the exit branch to use it.
183 void UpdateBranch(Value *EltsRem);
186 HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
187 const DataLayout &DL,
188 OptimizationRemarkEmitter *ORE) :
189 SE(SE), DL(DL), ORE(ORE), L(Info.L), M(L->getHeader()->getModule()),
190 ExitCount(Info.ExitCount),
191 CountType(Info.CountType),
192 ExitBranch(Info.ExitBranch),
193 LoopDecrement(Info.LoopDecrement),
194 UsePHICounter(Info.CounterInReg),
195 UseLoopGuard(Info.PerformEntryTest) { }
201 const DataLayout &DL;
202 OptimizationRemarkEmitter *ORE = nullptr;
205 const SCEV *ExitCount = nullptr;
206 Type *CountType = nullptr;
207 BranchInst *ExitBranch = nullptr;
208 Value *LoopDecrement = nullptr;
209 bool UsePHICounter = false;
210 bool UseLoopGuard = false;
211 BasicBlock *BeginBB = nullptr;
215 char HardwareLoops::ID = 0;
217 bool HardwareLoops::runOnFunction(Function &F) {
221 LLVM_DEBUG(dbgs() << "HWLoops: Running on " << F.getName() << "\n");
223 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
224 SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
225 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
226 TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
227 DL = &F.getParent()->getDataLayout();
228 ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
229 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
230 LibInfo = TLIP ? &TLIP->getTLI(F) : nullptr;
231 PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
232 AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
235 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
237 if (!L->getParentLoop())
244 // Return true if the search should stop, which will be when an inner loop is
245 // converted and the parent loop doesn't support containing a hardware loop.
246 bool HardwareLoops::TryConvertLoop(Loop *L) {
247 // Process nested loops first.
248 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) {
249 if (TryConvertLoop(*I)) {
250 reportHWLoopFailure("nested hardware-loops not supported", "HWLoopNested",
252 return true; // Stop search.
256 HardwareLoopInfo HWLoopInfo(L);
257 if (!HWLoopInfo.canAnalyze(*LI)) {
258 reportHWLoopFailure("cannot analyze loop, irreducible control flow",
259 "HWLoopCannotAnalyze", ORE, L);
263 if (!ForceHardwareLoops &&
264 !TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo)) {
265 reportHWLoopFailure("it's not profitable to create a hardware-loop",
266 "HWLoopNotProfitable", ORE, L);
270 // Allow overriding of the counter width and loop decrement value.
271 if (CounterBitWidth.getNumOccurrences())
272 HWLoopInfo.CountType =
273 IntegerType::get(M->getContext(), CounterBitWidth);
275 if (LoopDecrement.getNumOccurrences())
276 HWLoopInfo.LoopDecrement =
277 ConstantInt::get(HWLoopInfo.CountType, LoopDecrement);
279 MadeChange |= TryConvertLoop(HWLoopInfo);
280 return MadeChange && (!HWLoopInfo.IsNestingLegal && !ForceNestedLoop);
283 bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
285 Loop *L = HWLoopInfo.L;
286 LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
288 if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop,
289 ForceHardwareLoopPHI)) {
290 // TODO: there can be many reasons a loop is not considered a
291 // candidate, so we should let isHardwareLoopCandidate fill in the
292 // reason and then report a better message here.
293 reportHWLoopFailure("loop is not a candidate", "HWLoopNoCandidate", ORE, L);
298 (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
299 "Hardware Loop must have set exit info.");
301 BasicBlock *Preheader = L->getLoopPreheader();
303 // If we don't have a preheader, then insert one.
305 Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
309 HardwareLoop HWLoop(HWLoopInfo, *SE, *DL, ORE);
315 void HardwareLoop::Create() {
316 LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
318 Value *LoopCountInit = InitLoopCount();
319 if (!LoopCountInit) {
320 reportHWLoopFailure("could not safely create a loop count expression",
321 "HWLoopNotSafe", ORE, L);
325 InsertIterationSetup(LoopCountInit);
327 if (UsePHICounter || ForceHardwareLoopPHI) {
328 Instruction *LoopDec = InsertLoopRegDec(LoopCountInit);
329 Value *EltsRem = InsertPHICounter(LoopCountInit, LoopDec);
330 LoopDec->setOperand(0, EltsRem);
331 UpdateBranch(LoopDec);
335 // Run through the basic blocks of the loop and see if any of them have dead
336 // PHIs that can be removed.
337 for (auto I : L->blocks())
341 static bool CanGenerateTest(Loop *L, Value *Count) {
342 BasicBlock *Preheader = L->getLoopPreheader();
343 if (!Preheader->getSinglePredecessor())
346 BasicBlock *Pred = Preheader->getSinglePredecessor();
347 if (!isa<BranchInst>(Pred->getTerminator()))
350 auto *BI = cast<BranchInst>(Pred->getTerminator());
351 if (BI->isUnconditional() || !isa<ICmpInst>(BI->getCondition()))
354 // Check that the icmp is checking for equality of Count and zero and that
355 // a non-zero value results in entering the loop.
356 auto ICmp = cast<ICmpInst>(BI->getCondition());
357 LLVM_DEBUG(dbgs() << " - Found condition: " << *ICmp << "\n");
358 if (!ICmp->isEquality())
361 auto IsCompareZero = [](ICmpInst *ICmp, Value *Count, unsigned OpIdx) {
362 if (auto *Const = dyn_cast<ConstantInt>(ICmp->getOperand(OpIdx)))
363 return Const->isZero() && ICmp->getOperand(OpIdx ^ 1) == Count;
367 if (!IsCompareZero(ICmp, Count, 0) && !IsCompareZero(ICmp, Count, 1))
370 unsigned SuccIdx = ICmp->getPredicate() == ICmpInst::ICMP_NE ? 0 : 1;
371 if (BI->getSuccessor(SuccIdx) != Preheader)
377 Value *HardwareLoop::InitLoopCount() {
378 LLVM_DEBUG(dbgs() << "HWLoops: Initialising loop counter value:\n");
379 // Can we replace a conditional branch with an intrinsic that sets the
380 // loop counter and tests that is not zero?
382 SCEVExpander SCEVE(SE, DL, "loopcnt");
383 if (!ExitCount->getType()->isPointerTy() &&
384 ExitCount->getType() != CountType)
385 ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);
387 ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));
389 // If we're trying to use the 'test and set' form of the intrinsic, we need
390 // to replace a conditional branch that is controlling entry to the loop. It
391 // is likely (guaranteed?) that the preheader has an unconditional branch to
392 // the loop header, so also check if it has a single predecessor.
393 if (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, ExitCount,
394 SE.getZero(ExitCount->getType()))) {
395 LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
396 UseLoopGuard |= ForceGuardLoopEntry;
398 UseLoopGuard = false;
400 BasicBlock *BB = L->getLoopPreheader();
401 if (UseLoopGuard && BB->getSinglePredecessor() &&
402 cast<BranchInst>(BB->getTerminator())->isUnconditional())
403 BB = BB->getSinglePredecessor();
405 if (!isSafeToExpandAt(ExitCount, BB->getTerminator(), SE)) {
406 LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
407 << *ExitCount << "\n");
411 Value *Count = SCEVE.expandCodeFor(ExitCount, CountType,
412 BB->getTerminator());
414 // FIXME: We've expanded Count where we hope to insert the counter setting
415 // intrinsic. But, in the case of the 'test and set' form, we may fallback to
416 // the just 'set' form and in which case the insertion block is most likely
417 // different. It means there will be instruction(s) in a block that possibly
418 // aren't needed. The isLoopEntryGuardedByCond is trying to avoid this issue,
419 // but it's doesn't appear to work in all cases.
421 UseLoopGuard = UseLoopGuard && CanGenerateTest(L, Count);
422 BeginBB = UseLoopGuard ? BB : L->getLoopPreheader();
423 LLVM_DEBUG(dbgs() << " - Loop Count: " << *Count << "\n"
424 << " - Expanded Count in " << BB->getName() << "\n"
425 << " - Will insert set counter intrinsic into: "
426 << BeginBB->getName() << "\n");
430 void HardwareLoop::InsertIterationSetup(Value *LoopCountInit) {
431 IRBuilder<> Builder(BeginBB->getTerminator());
432 Type *Ty = LoopCountInit->getType();
433 Intrinsic::ID ID = UseLoopGuard ?
434 Intrinsic::test_set_loop_iterations : Intrinsic::set_loop_iterations;
435 Function *LoopIter = Intrinsic::getDeclaration(M, ID, Ty);
436 Value *SetCount = Builder.CreateCall(LoopIter, LoopCountInit);
438 // Use the return value of the intrinsic to control the entry of the loop.
440 assert((isa<BranchInst>(BeginBB->getTerminator()) &&
441 cast<BranchInst>(BeginBB->getTerminator())->isConditional()) &&
442 "Expected conditional branch");
443 auto *LoopGuard = cast<BranchInst>(BeginBB->getTerminator());
444 LoopGuard->setCondition(SetCount);
445 if (LoopGuard->getSuccessor(0) != L->getLoopPreheader())
446 LoopGuard->swapSuccessors();
448 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop counter: "
449 << *SetCount << "\n");
452 void HardwareLoop::InsertLoopDec() {
453 IRBuilder<> CondBuilder(ExitBranch);
456 Intrinsic::getDeclaration(M, Intrinsic::loop_decrement,
457 LoopDecrement->getType());
458 Value *Ops[] = { LoopDecrement };
459 Value *NewCond = CondBuilder.CreateCall(DecFunc, Ops);
460 Value *OldCond = ExitBranch->getCondition();
461 ExitBranch->setCondition(NewCond);
463 // The false branch must exit the loop.
464 if (!L->contains(ExitBranch->getSuccessor(0)))
465 ExitBranch->swapSuccessors();
467 // The old condition may be dead now, and may have even created a dead PHI
468 // (the original induction variable).
469 RecursivelyDeleteTriviallyDeadInstructions(OldCond);
471 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *NewCond << "\n");
474 Instruction* HardwareLoop::InsertLoopRegDec(Value *EltsRem) {
475 IRBuilder<> CondBuilder(ExitBranch);
478 Intrinsic::getDeclaration(M, Intrinsic::loop_decrement_reg,
479 { EltsRem->getType(), EltsRem->getType(),
480 LoopDecrement->getType()
482 Value *Ops[] = { EltsRem, LoopDecrement };
483 Value *Call = CondBuilder.CreateCall(DecFunc, Ops);
485 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *Call << "\n");
486 return cast<Instruction>(Call);
489 PHINode* HardwareLoop::InsertPHICounter(Value *NumElts, Value *EltsRem) {
490 BasicBlock *Preheader = L->getLoopPreheader();
491 BasicBlock *Header = L->getHeader();
492 BasicBlock *Latch = ExitBranch->getParent();
493 IRBuilder<> Builder(Header->getFirstNonPHI());
494 PHINode *Index = Builder.CreatePHI(NumElts->getType(), 2);
495 Index->addIncoming(NumElts, Preheader);
496 Index->addIncoming(EltsRem, Latch);
497 LLVM_DEBUG(dbgs() << "HWLoops: PHI Counter: " << *Index << "\n");
501 void HardwareLoop::UpdateBranch(Value *EltsRem) {
502 IRBuilder<> CondBuilder(ExitBranch);
504 CondBuilder.CreateICmpNE(EltsRem, ConstantInt::get(EltsRem->getType(), 0));
505 Value *OldCond = ExitBranch->getCondition();
506 ExitBranch->setCondition(NewCond);
508 // The false branch must exit the loop.
509 if (!L->contains(ExitBranch->getSuccessor(0)))
510 ExitBranch->swapSuccessors();
512 // The old condition may be dead now, and may have even created a dead PHI
513 // (the original induction variable).
514 RecursivelyDeleteTriviallyDeadInstructions(OldCond);
517 INITIALIZE_PASS_BEGIN(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
518 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
519 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
520 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
521 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
522 INITIALIZE_PASS_END(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
524 FunctionPass *llvm::createHardwareLoopsPass() { return new HardwareLoops(); }