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/TargetLibraryInfo.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/Support/CommandLine.h"
39 #include "llvm/Support/Debug.h"
40 #include "llvm/Transforms/Scalar.h"
41 #include "llvm/Transforms/Utils.h"
42 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
43 #include "llvm/Transforms/Utils/Local.h"
44 #include "llvm/Transforms/Utils/LoopUtils.h"
45 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.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 bool AnyChanged = false;
250 AnyChanged |= TryConvertLoop(SL);
252 reportHWLoopFailure("nested hardware-loops not supported", "HWLoopNested",
254 return true; // Stop search.
257 LLVM_DEBUG(dbgs() << "HWLoops: Loop " << L->getHeader()->getName() << "\n");
259 HardwareLoopInfo HWLoopInfo(L);
260 if (!HWLoopInfo.canAnalyze(*LI)) {
261 reportHWLoopFailure("cannot analyze loop, irreducible control flow",
262 "HWLoopCannotAnalyze", ORE, L);
266 if (!ForceHardwareLoops &&
267 !TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo)) {
268 reportHWLoopFailure("it's not profitable to create a hardware-loop",
269 "HWLoopNotProfitable", ORE, L);
273 // Allow overriding of the counter width and loop decrement value.
274 if (CounterBitWidth.getNumOccurrences())
275 HWLoopInfo.CountType =
276 IntegerType::get(M->getContext(), CounterBitWidth);
278 if (LoopDecrement.getNumOccurrences())
279 HWLoopInfo.LoopDecrement =
280 ConstantInt::get(HWLoopInfo.CountType, LoopDecrement);
282 MadeChange |= TryConvertLoop(HWLoopInfo);
283 return MadeChange && (!HWLoopInfo.IsNestingLegal && !ForceNestedLoop);
286 bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
288 Loop *L = HWLoopInfo.L;
289 LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
291 if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop,
292 ForceHardwareLoopPHI)) {
293 // TODO: there can be many reasons a loop is not considered a
294 // candidate, so we should let isHardwareLoopCandidate fill in the
295 // reason and then report a better message here.
296 reportHWLoopFailure("loop is not a candidate", "HWLoopNoCandidate", ORE, L);
301 (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
302 "Hardware Loop must have set exit info.");
304 BasicBlock *Preheader = L->getLoopPreheader();
306 // If we don't have a preheader, then insert one.
308 Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
312 HardwareLoop HWLoop(HWLoopInfo, *SE, *DL, ORE);
318 void HardwareLoop::Create() {
319 LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
321 Value *LoopCountInit = InitLoopCount();
322 if (!LoopCountInit) {
323 reportHWLoopFailure("could not safely create a loop count expression",
324 "HWLoopNotSafe", ORE, L);
328 InsertIterationSetup(LoopCountInit);
330 if (UsePHICounter || ForceHardwareLoopPHI) {
331 Instruction *LoopDec = InsertLoopRegDec(LoopCountInit);
332 Value *EltsRem = InsertPHICounter(LoopCountInit, LoopDec);
333 LoopDec->setOperand(0, EltsRem);
334 UpdateBranch(LoopDec);
338 // Run through the basic blocks of the loop and see if any of them have dead
339 // PHIs that can be removed.
340 for (auto I : L->blocks())
344 static bool CanGenerateTest(Loop *L, Value *Count) {
345 BasicBlock *Preheader = L->getLoopPreheader();
346 if (!Preheader->getSinglePredecessor())
349 BasicBlock *Pred = Preheader->getSinglePredecessor();
350 if (!isa<BranchInst>(Pred->getTerminator()))
353 auto *BI = cast<BranchInst>(Pred->getTerminator());
354 if (BI->isUnconditional() || !isa<ICmpInst>(BI->getCondition()))
357 // Check that the icmp is checking for equality of Count and zero and that
358 // a non-zero value results in entering the loop.
359 auto ICmp = cast<ICmpInst>(BI->getCondition());
360 LLVM_DEBUG(dbgs() << " - Found condition: " << *ICmp << "\n");
361 if (!ICmp->isEquality())
364 auto IsCompareZero = [](ICmpInst *ICmp, Value *Count, unsigned OpIdx) {
365 if (auto *Const = dyn_cast<ConstantInt>(ICmp->getOperand(OpIdx)))
366 return Const->isZero() && ICmp->getOperand(OpIdx ^ 1) == Count;
370 if (!IsCompareZero(ICmp, Count, 0) && !IsCompareZero(ICmp, Count, 1))
373 unsigned SuccIdx = ICmp->getPredicate() == ICmpInst::ICMP_NE ? 0 : 1;
374 if (BI->getSuccessor(SuccIdx) != Preheader)
380 Value *HardwareLoop::InitLoopCount() {
381 LLVM_DEBUG(dbgs() << "HWLoops: Initialising loop counter value:\n");
382 // Can we replace a conditional branch with an intrinsic that sets the
383 // loop counter and tests that is not zero?
385 SCEVExpander SCEVE(SE, DL, "loopcnt");
386 if (!ExitCount->getType()->isPointerTy() &&
387 ExitCount->getType() != CountType)
388 ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);
390 ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));
392 // If we're trying to use the 'test and set' form of the intrinsic, we need
393 // to replace a conditional branch that is controlling entry to the loop. It
394 // is likely (guaranteed?) that the preheader has an unconditional branch to
395 // the loop header, so also check if it has a single predecessor.
396 if (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, ExitCount,
397 SE.getZero(ExitCount->getType()))) {
398 LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
399 UseLoopGuard |= ForceGuardLoopEntry;
401 UseLoopGuard = false;
403 BasicBlock *BB = L->getLoopPreheader();
404 if (UseLoopGuard && BB->getSinglePredecessor() &&
405 cast<BranchInst>(BB->getTerminator())->isUnconditional())
406 BB = BB->getSinglePredecessor();
408 if (!isSafeToExpandAt(ExitCount, BB->getTerminator(), SE)) {
409 LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
410 << *ExitCount << "\n");
414 Value *Count = SCEVE.expandCodeFor(ExitCount, CountType,
415 BB->getTerminator());
417 // FIXME: We've expanded Count where we hope to insert the counter setting
418 // intrinsic. But, in the case of the 'test and set' form, we may fallback to
419 // the just 'set' form and in which case the insertion block is most likely
420 // different. It means there will be instruction(s) in a block that possibly
421 // aren't needed. The isLoopEntryGuardedByCond is trying to avoid this issue,
422 // but it's doesn't appear to work in all cases.
424 UseLoopGuard = UseLoopGuard && CanGenerateTest(L, Count);
425 BeginBB = UseLoopGuard ? BB : L->getLoopPreheader();
426 LLVM_DEBUG(dbgs() << " - Loop Count: " << *Count << "\n"
427 << " - Expanded Count in " << BB->getName() << "\n"
428 << " - Will insert set counter intrinsic into: "
429 << BeginBB->getName() << "\n");
433 void HardwareLoop::InsertIterationSetup(Value *LoopCountInit) {
434 IRBuilder<> Builder(BeginBB->getTerminator());
435 Type *Ty = LoopCountInit->getType();
436 Intrinsic::ID ID = UseLoopGuard ?
437 Intrinsic::test_set_loop_iterations : Intrinsic::set_loop_iterations;
438 Function *LoopIter = Intrinsic::getDeclaration(M, ID, Ty);
439 Value *SetCount = Builder.CreateCall(LoopIter, LoopCountInit);
441 // Use the return value of the intrinsic to control the entry of the loop.
443 assert((isa<BranchInst>(BeginBB->getTerminator()) &&
444 cast<BranchInst>(BeginBB->getTerminator())->isConditional()) &&
445 "Expected conditional branch");
446 auto *LoopGuard = cast<BranchInst>(BeginBB->getTerminator());
447 LoopGuard->setCondition(SetCount);
448 if (LoopGuard->getSuccessor(0) != L->getLoopPreheader())
449 LoopGuard->swapSuccessors();
451 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop counter: "
452 << *SetCount << "\n");
455 void HardwareLoop::InsertLoopDec() {
456 IRBuilder<> CondBuilder(ExitBranch);
459 Intrinsic::getDeclaration(M, Intrinsic::loop_decrement,
460 LoopDecrement->getType());
461 Value *Ops[] = { LoopDecrement };
462 Value *NewCond = CondBuilder.CreateCall(DecFunc, Ops);
463 Value *OldCond = ExitBranch->getCondition();
464 ExitBranch->setCondition(NewCond);
466 // The false branch must exit the loop.
467 if (!L->contains(ExitBranch->getSuccessor(0)))
468 ExitBranch->swapSuccessors();
470 // The old condition may be dead now, and may have even created a dead PHI
471 // (the original induction variable).
472 RecursivelyDeleteTriviallyDeadInstructions(OldCond);
474 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *NewCond << "\n");
477 Instruction* HardwareLoop::InsertLoopRegDec(Value *EltsRem) {
478 IRBuilder<> CondBuilder(ExitBranch);
481 Intrinsic::getDeclaration(M, Intrinsic::loop_decrement_reg,
482 { EltsRem->getType() });
483 Value *Ops[] = { EltsRem, LoopDecrement };
484 Value *Call = CondBuilder.CreateCall(DecFunc, Ops);
486 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *Call << "\n");
487 return cast<Instruction>(Call);
490 PHINode* HardwareLoop::InsertPHICounter(Value *NumElts, Value *EltsRem) {
491 BasicBlock *Preheader = L->getLoopPreheader();
492 BasicBlock *Header = L->getHeader();
493 BasicBlock *Latch = ExitBranch->getParent();
494 IRBuilder<> Builder(Header->getFirstNonPHI());
495 PHINode *Index = Builder.CreatePHI(NumElts->getType(), 2);
496 Index->addIncoming(NumElts, Preheader);
497 Index->addIncoming(EltsRem, Latch);
498 LLVM_DEBUG(dbgs() << "HWLoops: PHI Counter: " << *Index << "\n");
502 void HardwareLoop::UpdateBranch(Value *EltsRem) {
503 IRBuilder<> CondBuilder(ExitBranch);
505 CondBuilder.CreateICmpNE(EltsRem, ConstantInt::get(EltsRem->getType(), 0));
506 Value *OldCond = ExitBranch->getCondition();
507 ExitBranch->setCondition(NewCond);
509 // The false branch must exit the loop.
510 if (!L->contains(ExitBranch->getSuccessor(0)))
511 ExitBranch->swapSuccessors();
513 // The old condition may be dead now, and may have even created a dead PHI
514 // (the original induction variable).
515 RecursivelyDeleteTriviallyDeadInstructions(OldCond);
518 INITIALIZE_PASS_BEGIN(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
519 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
520 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
521 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
522 INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
523 INITIALIZE_PASS_END(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
525 FunctionPass *llvm::createHardwareLoopsPass() { return new HardwareLoops(); }