1//===-- HardwareLoops.cpp - Target Independent Hardware Loops --*- C++ -*-===//
2//
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
6//
7//===----------------------------------------------------------------------===//
8/// \file
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.
15///
16//===----------------------------------------------------------------------===//
17
18#include "llvm/CodeGen/HardwareLoops.h"
19#include "llvm/ADT/Statistic.h"
20#include "llvm/Analysis/AssumptionCache.h"
21#include "llvm/Analysis/BranchProbabilityInfo.h"
22#include "llvm/Analysis/LoopInfo.h"
23#include "llvm/Analysis/OptimizationRemarkEmitter.h"
24#include "llvm/Analysis/ScalarEvolution.h"
25#include "llvm/Analysis/TargetLibraryInfo.h"
26#include "llvm/Analysis/TargetTransformInfo.h"
27#include "llvm/CodeGen/Passes.h"
28#include "llvm/IR/BasicBlock.h"
29#include "llvm/IR/Constants.h"
30#include "llvm/IR/Dominators.h"
31#include "llvm/IR/IRBuilder.h"
32#include "llvm/IR/Instructions.h"
33#include "llvm/IR/Value.h"
34#include "llvm/InitializePasses.h"
35#include "llvm/Pass.h"
36#include "llvm/Support/CommandLine.h"
37#include "llvm/Support/Debug.h"
38#include "llvm/Transforms/Utils.h"
39#include "llvm/Transforms/Utils/BasicBlockUtils.h"
40#include "llvm/Transforms/Utils/Local.h"
41#include "llvm/Transforms/Utils/LoopUtils.h"
42#include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
43
44#define DEBUG_TYPE "hardware-loops"
45
46#define HW_LOOPS_NAME "Hardware Loop Insertion"
47
48using namespace llvm;
49
50static cl::opt<bool>
51ForceHardwareLoops("force-hardware-loops", cl::Hidden, cl::init(Val: false),
52 cl::desc("Force hardware loops intrinsics to be inserted"));
53
54static cl::opt<bool>
55ForceHardwareLoopPHI(
56 "force-hardware-loop-phi", cl::Hidden, cl::init(Val: false),
57 cl::desc("Force hardware loop counter to be updated through a phi"));
58
59static cl::opt<bool>
60ForceNestedLoop("force-nested-hardware-loop", cl::Hidden, cl::init(Val: false),
61 cl::desc("Force allowance of nested hardware loops"));
62
63static cl::opt<unsigned>
64LoopDecrement("hardware-loop-decrement", cl::Hidden, cl::init(Val: 1),
65 cl::desc("Set the loop decrement value"));
66
67static cl::opt<unsigned>
68CounterBitWidth("hardware-loop-counter-bitwidth", cl::Hidden, cl::init(Val: 32),
69 cl::desc("Set the loop counter bitwidth"));
70
71static cl::opt<bool>
72ForceGuardLoopEntry(
73 "force-hardware-loop-guard", cl::Hidden, cl::init(Val: false),
74 cl::desc("Force generation of loop guard intrinsic"));
75
76STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
77
78#ifndef NDEBUG
79static void debugHWLoopFailure(const StringRef DebugMsg,
80 Instruction *I) {
81 dbgs() << "HWLoops: " << DebugMsg;
82 if (I)
83 dbgs() << ' ' << *I;
84 else
85 dbgs() << '.';
86 dbgs() << '\n';
87}
88#endif
89
90static OptimizationRemarkAnalysis
91createHWLoopAnalysis(StringRef RemarkName, Loop *L, Instruction *I) {
92 BasicBlock *CodeRegion = L->getHeader();
93 DebugLoc DL = L->getStartLoc();
94
95 if (I) {
96 CodeRegion = I->getParent();
97 // If there is no debug location attached to the instruction, revert back to
98 // using the loop's.
99 if (I->getDebugLoc())
100 DL = I->getDebugLoc();
101 }
102
103 OptimizationRemarkAnalysis R(DEBUG_TYPE, RemarkName, DL, CodeRegion);
104 R << "hardware-loop not created: ";
105 return R;
106}
107
108namespace {
109
110 void reportHWLoopFailure(const StringRef Msg, const StringRef ORETag,
111 OptimizationRemarkEmitter *ORE, Loop *TheLoop, Instruction *I = nullptr) {
112 LLVM_DEBUG(debugHWLoopFailure(Msg, I));
113 ORE->emit(OptDiag: createHWLoopAnalysis(RemarkName: ORETag, L: TheLoop, I) << Msg);
114 }
115
116 using TTI = TargetTransformInfo;
117
118 class HardwareLoopsLegacy : public FunctionPass {
119 public:
120 static char ID;
121
122 HardwareLoopsLegacy() : FunctionPass(ID) {}
123
124 bool runOnFunction(Function &F) override;
125
126 void getAnalysisUsage(AnalysisUsage &AU) const override {
127 AU.addRequired<LoopInfoWrapperPass>();
128 AU.addPreserved<LoopInfoWrapperPass>();
129 AU.addRequired<DominatorTreeWrapperPass>();
130 AU.addPreserved<DominatorTreeWrapperPass>();
131 AU.addRequired<ScalarEvolutionWrapperPass>();
132 AU.addPreserved<ScalarEvolutionWrapperPass>();
133 AU.addRequired<AssumptionCacheTracker>();
134 AU.addRequired<TargetTransformInfoWrapperPass>();
135 AU.addRequired<OptimizationRemarkEmitterWrapperPass>();
136 AU.addPreserved<BranchProbabilityInfoWrapperPass>();
137 }
138 };
139
140 class HardwareLoopsImpl {
141 public:
142 HardwareLoopsImpl(ScalarEvolution &SE, LoopInfo &LI, bool PreserveLCSSA,
143 DominatorTree &DT, const TargetTransformInfo &TTI,
144 TargetLibraryInfo *TLI, AssumptionCache &AC,
145 OptimizationRemarkEmitter *ORE, HardwareLoopOptions &Opts)
146 : SE(SE), LI(LI), PreserveLCSSA(PreserveLCSSA), DT(DT), TTI(TTI),
147 TLI(TLI), AC(AC), ORE(ORE), Opts(Opts) {}
148
149 bool run(Function &F);
150
151 private:
152 // Try to convert the given Loop into a hardware loop.
153 bool TryConvertLoop(Loop *L, LLVMContext &Ctx);
154
155 // Given that the target believes the loop to be profitable, try to
156 // convert it.
157 bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
158
159 ScalarEvolution &SE;
160 LoopInfo &LI;
161 bool PreserveLCSSA;
162 DominatorTree &DT;
163 const TargetTransformInfo &TTI;
164 TargetLibraryInfo *TLI = nullptr;
165 AssumptionCache &AC;
166 OptimizationRemarkEmitter *ORE;
167 HardwareLoopOptions &Opts;
168 bool MadeChange = false;
169 };
170
171 class HardwareLoop {
172 // Expand the trip count scev into a value that we can use.
173 Value *InitLoopCount();
174
175 // Insert the set_loop_iteration intrinsic.
176 Value *InsertIterationSetup(Value *LoopCountInit);
177
178 // Insert the loop_decrement intrinsic.
179 void InsertLoopDec();
180
181 // Insert the loop_decrement_reg intrinsic.
182 Instruction *InsertLoopRegDec(Value *EltsRem);
183
184 // If the target requires the counter value to be updated in the loop,
185 // insert a phi to hold the value. The intended purpose is for use by
186 // loop_decrement_reg.
187 PHINode *InsertPHICounter(Value *NumElts, Value *EltsRem);
188
189 // Create a new cmp, that checks the returned value of loop_decrement*,
190 // and update the exit branch to use it.
191 void UpdateBranch(Value *EltsRem);
192
193 public:
194 HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
195 OptimizationRemarkEmitter *ORE, HardwareLoopOptions &Opts)
196 : SE(SE), ORE(ORE), Opts(Opts), L(Info.L),
197 M(L->getHeader()->getModule()), ExitCount(Info.ExitCount),
198 CountType(Info.CountType), ExitBranch(Info.ExitBranch),
199 LoopDecrement(Info.LoopDecrement), UsePHICounter(Info.CounterInReg),
200 UseLoopGuard(Info.PerformEntryTest) {}
201
202 void Create();
203
204 private:
205 ScalarEvolution &SE;
206 OptimizationRemarkEmitter *ORE = nullptr;
207 HardwareLoopOptions &Opts;
208 Loop *L = nullptr;
209 Module *M = nullptr;
210 const SCEV *ExitCount = nullptr;
211 Type *CountType = nullptr;
212 CondBrInst *ExitBranch = nullptr;
213 Value *LoopDecrement = nullptr;
214 bool UsePHICounter = false;
215 bool UseLoopGuard = false;
216 BasicBlock *BeginBB = nullptr;
217 };
218}
219
220char HardwareLoopsLegacy::ID = 0;
221
222bool HardwareLoopsLegacy::runOnFunction(Function &F) {
223 if (skipFunction(F))
224 return false;
225
226 LLVM_DEBUG(dbgs() << "HWLoops: Running on " << F.getName() << "\n");
227
228 auto &LI = getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
229 auto &SE = getAnalysis<ScalarEvolutionWrapperPass>().getSE();
230 auto &DT = getAnalysis<DominatorTreeWrapperPass>().getDomTree();
231 auto &TTI = getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
232 auto *ORE = &getAnalysis<OptimizationRemarkEmitterWrapperPass>().getORE();
233 auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
234 auto *TLI = TLIP ? &TLIP->getTLI(F) : nullptr;
235 auto &AC = getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
236 bool PreserveLCSSA = mustPreserveAnalysisID(AID&: LCSSAID);
237
238 HardwareLoopOptions Opts;
239 if (ForceHardwareLoops.getNumOccurrences())
240 Opts.setForce(ForceHardwareLoops);
241 if (ForceHardwareLoopPHI.getNumOccurrences())
242 Opts.setForcePhi(ForceHardwareLoopPHI);
243 if (ForceNestedLoop.getNumOccurrences())
244 Opts.setForceNested(ForceNestedLoop);
245 if (ForceGuardLoopEntry.getNumOccurrences())
246 Opts.setForceGuard(ForceGuardLoopEntry);
247 if (LoopDecrement.getNumOccurrences())
248 Opts.setDecrement(LoopDecrement);
249 if (CounterBitWidth.getNumOccurrences())
250 Opts.setCounterBitwidth(CounterBitWidth);
251
252 HardwareLoopsImpl Impl(SE, LI, PreserveLCSSA, DT, TTI, TLI, AC, ORE, Opts);
253 return Impl.run(F);
254}
255
256PreservedAnalyses HardwareLoopsPass::run(Function &F,
257 FunctionAnalysisManager &AM) {
258 auto &LI = AM.getResult<LoopAnalysis>(IR&: F);
259 auto &SE = AM.getResult<ScalarEvolutionAnalysis>(IR&: F);
260 auto &DT = AM.getResult<DominatorTreeAnalysis>(IR&: F);
261 auto &TTI = AM.getResult<TargetIRAnalysis>(IR&: F);
262 auto *TLI = &AM.getResult<TargetLibraryAnalysis>(IR&: F);
263 auto &AC = AM.getResult<AssumptionAnalysis>(IR&: F);
264 auto *ORE = &AM.getResult<OptimizationRemarkEmitterAnalysis>(IR&: F);
265
266 HardwareLoopsImpl Impl(SE, LI, true, DT, TTI, TLI, AC, ORE, Opts);
267 bool Changed = Impl.run(F);
268 if (!Changed)
269 return PreservedAnalyses::all();
270
271 PreservedAnalyses PA;
272 PA.preserve<LoopAnalysis>();
273 PA.preserve<ScalarEvolutionAnalysis>();
274 PA.preserve<DominatorTreeAnalysis>();
275 PA.preserve<BranchProbabilityAnalysis>();
276 return PA;
277}
278
279bool HardwareLoopsImpl::run(Function &F) {
280 LLVMContext &Ctx = F.getContext();
281 for (Loop *L : LI)
282 if (L->isOutermost())
283 TryConvertLoop(L, Ctx);
284 return MadeChange;
285}
286
287// Return true if the search should stop, which will be when an inner loop is
288// converted and the parent loop doesn't support containing a hardware loop.
289bool HardwareLoopsImpl::TryConvertLoop(Loop *L, LLVMContext &Ctx) {
290 // Process nested loops first.
291 bool AnyChanged = false;
292 for (Loop *SL : *L)
293 AnyChanged |= TryConvertLoop(L: SL, Ctx);
294 if (AnyChanged) {
295 reportHWLoopFailure(Msg: "nested hardware-loops not supported", ORETag: "HWLoopNested",
296 ORE, TheLoop: L);
297 return true; // Stop search.
298 }
299
300 LLVM_DEBUG(dbgs() << "HWLoops: Loop " << L->getHeader()->getName() << "\n");
301
302 HardwareLoopInfo HWLoopInfo(L);
303 if (!HWLoopInfo.canAnalyze(LI)) {
304 reportHWLoopFailure(Msg: "cannot analyze loop, irreducible control flow",
305 ORETag: "HWLoopCannotAnalyze", ORE, TheLoop: L);
306 return false;
307 }
308
309 if (!Opts.Force &&
310 !TTI.isHardwareLoopProfitable(L, SE, AC, LibInfo: TLI, HWLoopInfo)) {
311 reportHWLoopFailure(Msg: "it's not profitable to create a hardware-loop",
312 ORETag: "HWLoopNotProfitable", ORE, TheLoop: L);
313 return false;
314 }
315
316 // Allow overriding of the counter width and loop decrement value.
317 if (Opts.Bitwidth.has_value()) {
318 HWLoopInfo.CountType = IntegerType::get(C&: Ctx, NumBits: Opts.Bitwidth.value());
319 }
320
321 if (Opts.Decrement.has_value())
322 HWLoopInfo.LoopDecrement =
323 ConstantInt::get(Ty: HWLoopInfo.CountType, V: Opts.Decrement.value());
324
325 MadeChange |= TryConvertLoop(HWLoopInfo);
326 return MadeChange && (!HWLoopInfo.IsNestingLegal && !Opts.ForceNested);
327}
328
329bool HardwareLoopsImpl::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
330
331 Loop *L = HWLoopInfo.L;
332 LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
333
334 if (!HWLoopInfo.isHardwareLoopCandidate(SE, LI, DT, ForceNestedLoop: Opts.getForceNested(),
335 ForceHardwareLoopPHI: Opts.getForcePhi())) {
336 // TODO: there can be many reasons a loop is not considered a
337 // candidate, so we should let isHardwareLoopCandidate fill in the
338 // reason and then report a better message here.
339 reportHWLoopFailure(Msg: "loop is not a candidate", ORETag: "HWLoopNoCandidate", ORE, TheLoop: L);
340 return false;
341 }
342
343 assert(
344 (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
345 "Hardware Loop must have set exit info.");
346
347 BasicBlock *Preheader = L->getLoopPreheader();
348
349 // If we don't have a preheader, then insert one.
350 if (!Preheader)
351 Preheader = InsertPreheaderForLoop(L, DT: &DT, LI: &LI, MSSAU: nullptr, PreserveLCSSA);
352 if (!Preheader)
353 return false;
354
355 HardwareLoop HWLoop(HWLoopInfo, SE, ORE, Opts);
356 HWLoop.Create();
357 ++NumHWLoops;
358 return true;
359}
360
361void HardwareLoop::Create() {
362 LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
363
364 Value *LoopCountInit = InitLoopCount();
365 if (!LoopCountInit) {
366 reportHWLoopFailure(Msg: "could not safely create a loop count expression",
367 ORETag: "HWLoopNotSafe", ORE, TheLoop: L);
368 return;
369 }
370
371 Value *Setup = InsertIterationSetup(LoopCountInit);
372
373 if (UsePHICounter || Opts.ForcePhi) {
374 Instruction *LoopDec = InsertLoopRegDec(EltsRem: LoopCountInit);
375 Value *EltsRem = InsertPHICounter(NumElts: Setup, EltsRem: LoopDec);
376 LoopDec->setOperand(i: 0, Val: EltsRem);
377 UpdateBranch(EltsRem: LoopDec);
378 } else
379 InsertLoopDec();
380
381 // Run through the basic blocks of the loop and see if any of them have dead
382 // PHIs that can be removed.
383 for (auto *I : L->blocks())
384 DeleteDeadPHIs(BB: I);
385}
386
387static bool CanGenerateTest(Loop *L, Value *Count) {
388 BasicBlock *Preheader = L->getLoopPreheader();
389 if (!Preheader->getSinglePredecessor())
390 return false;
391
392 BasicBlock *Pred = Preheader->getSinglePredecessor();
393 auto *BI = dyn_cast<CondBrInst>(Val: Pred->getTerminator());
394 if (!BI || !isa<ICmpInst>(Val: BI->getCondition()))
395 return false;
396
397 // Check that the icmp is checking for equality of Count and zero and that
398 // a non-zero value results in entering the loop.
399 auto ICmp = cast<ICmpInst>(Val: BI->getCondition());
400 LLVM_DEBUG(dbgs() << " - Found condition: " << *ICmp << "\n");
401 if (!ICmp->isEquality())
402 return false;
403
404 auto IsCompareZero = [](ICmpInst *ICmp, Value *Count, unsigned OpIdx) {
405 if (auto *Const = dyn_cast<ConstantInt>(Val: ICmp->getOperand(i_nocapture: OpIdx)))
406 return Const->isZero() && ICmp->getOperand(i_nocapture: OpIdx ^ 1) == Count;
407 return false;
408 };
409
410 // Check if Count is a zext.
411 Value *CountBefZext =
412 isa<ZExtInst>(Val: Count) ? cast<ZExtInst>(Val: Count)->getOperand(i_nocapture: 0) : nullptr;
413
414 if (!IsCompareZero(ICmp, Count, 0) && !IsCompareZero(ICmp, Count, 1) &&
415 !IsCompareZero(ICmp, CountBefZext, 0) &&
416 !IsCompareZero(ICmp, CountBefZext, 1))
417 return false;
418
419 unsigned SuccIdx = ICmp->getPredicate() == ICmpInst::ICMP_NE ? 0 : 1;
420 if (BI->getSuccessor(i: SuccIdx) != Preheader)
421 return false;
422
423 return true;
424}
425
426Value *HardwareLoop::InitLoopCount() {
427 LLVM_DEBUG(dbgs() << "HWLoops: Initialising loop counter value:\n");
428 // Can we replace a conditional branch with an intrinsic that sets the
429 // loop counter and tests that is not zero?
430
431 SCEVExpander SCEVE(SE, "loopcnt");
432 if (!ExitCount->getType()->isPointerTy() &&
433 ExitCount->getType() != CountType)
434 ExitCount = SE.getZeroExtendExpr(Op: ExitCount, Ty: CountType);
435
436 ExitCount = SE.getAddExpr(LHS: ExitCount, RHS: SE.getOne(Ty: CountType));
437
438 // If we're trying to use the 'test and set' form of the intrinsic, we need
439 // to replace a conditional branch that is controlling entry to the loop. It
440 // is likely (guaranteed?) that the preheader has an unconditional branch to
441 // the loop header, so also check if it has a single predecessor.
442 if (SE.isLoopEntryGuardedByCond(L, Pred: ICmpInst::ICMP_NE, LHS: ExitCount,
443 RHS: SE.getZero(Ty: ExitCount->getType()))) {
444 LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
445 if (Opts.ForceGuard)
446 UseLoopGuard = true;
447 } else
448 UseLoopGuard = false;
449
450 BasicBlock *BB = L->getLoopPreheader();
451 if (UseLoopGuard && BB->getSinglePredecessor() &&
452 isa<UncondBrInst>(Val: BB->getTerminator())) {
453 BasicBlock *Predecessor = BB->getSinglePredecessor();
454 // If it's not safe to create a while loop then don't force it and create a
455 // do-while loop instead
456 if (!SCEVE.isSafeToExpandAt(S: ExitCount, InsertionPoint: Predecessor->getTerminator()))
457 UseLoopGuard = false;
458 else
459 BB = Predecessor;
460 }
461
462 if (!SCEVE.isSafeToExpandAt(S: ExitCount, InsertionPoint: BB->getTerminator())) {
463 LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
464 << *ExitCount << "\n");
465 return nullptr;
466 }
467
468 Value *Count = SCEVE.expandCodeFor(SH: ExitCount, Ty: CountType,
469 I: BB->getTerminator());
470
471 // FIXME: We've expanded Count where we hope to insert the counter setting
472 // intrinsic. But, in the case of the 'test and set' form, we may fallback to
473 // the just 'set' form and in which case the insertion block is most likely
474 // different. It means there will be instruction(s) in a block that possibly
475 // aren't needed. The isLoopEntryGuardedByCond is trying to avoid this issue,
476 // but it's doesn't appear to work in all cases.
477
478 UseLoopGuard = UseLoopGuard && CanGenerateTest(L, Count);
479 BeginBB = UseLoopGuard ? BB : L->getLoopPreheader();
480 LLVM_DEBUG(dbgs() << " - Loop Count: " << *Count << "\n"
481 << " - Expanded Count in " << BB->getName() << "\n"
482 << " - Will insert set counter intrinsic into: "
483 << BeginBB->getName() << "\n");
484 return Count;
485}
486
487Value* HardwareLoop::InsertIterationSetup(Value *LoopCountInit) {
488 IRBuilder<> Builder(BeginBB->getTerminator());
489 if (BeginBB->getParent()->getAttributes().hasFnAttr(Kind: Attribute::StrictFP))
490 Builder.setIsFPConstrained(true);
491 Type *Ty = LoopCountInit->getType();
492 bool UsePhi = UsePHICounter || Opts.ForcePhi;
493 Intrinsic::ID ID = UseLoopGuard
494 ? (UsePhi ? Intrinsic::test_start_loop_iterations
495 : Intrinsic::test_set_loop_iterations)
496 : (UsePhi ? Intrinsic::start_loop_iterations
497 : Intrinsic::set_loop_iterations);
498 Value *LoopSetup = Builder.CreateIntrinsic(ID, OverloadTypes: Ty, Args: LoopCountInit);
499
500 // Use the return value of the intrinsic to control the entry of the loop.
501 if (UseLoopGuard) {
502 Value *SetCount =
503 UsePhi ? Builder.CreateExtractValue(Agg: LoopSetup, Idxs: 1) : LoopSetup;
504 auto *LoopGuard = cast<CondBrInst>(Val: BeginBB->getTerminator());
505 LoopGuard->setCondition(SetCount);
506 if (LoopGuard->getSuccessor(i: 0) != L->getLoopPreheader())
507 LoopGuard->swapSuccessors();
508 }
509 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop counter: " << *LoopSetup
510 << "\n");
511 if (UsePhi && UseLoopGuard)
512 LoopSetup = Builder.CreateExtractValue(Agg: LoopSetup, Idxs: 0);
513 return !UsePhi ? LoopCountInit : LoopSetup;
514}
515
516void HardwareLoop::InsertLoopDec() {
517 IRBuilder<> CondBuilder(ExitBranch);
518 if (ExitBranch->getParent()->getParent()->getAttributes().hasFnAttr(
519 Kind: Attribute::StrictFP))
520 CondBuilder.setIsFPConstrained(true);
521
522 Value *Ops[] = { LoopDecrement };
523 Value *NewCond = CondBuilder.CreateIntrinsic(ID: Intrinsic::loop_decrement,
524 OverloadTypes: LoopDecrement->getType(), Args: Ops);
525 Value *OldCond = ExitBranch->getCondition();
526 ExitBranch->setCondition(NewCond);
527
528 // The false branch must exit the loop.
529 if (!L->contains(BB: ExitBranch->getSuccessor(i: 0)))
530 ExitBranch->swapSuccessors();
531
532 // The old condition may be dead now, and may have even created a dead PHI
533 // (the original induction variable).
534 RecursivelyDeleteTriviallyDeadInstructions(V: OldCond);
535
536 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *NewCond << "\n");
537}
538
539Instruction* HardwareLoop::InsertLoopRegDec(Value *EltsRem) {
540 IRBuilder<> CondBuilder(ExitBranch);
541 if (ExitBranch->getParent()->getParent()->getAttributes().hasFnAttr(
542 Kind: Attribute::StrictFP))
543 CondBuilder.setIsFPConstrained(true);
544
545 Value *Ops[] = { EltsRem, LoopDecrement };
546 Value *Call = CondBuilder.CreateIntrinsic(ID: Intrinsic::loop_decrement_reg,
547 OverloadTypes: {EltsRem->getType()}, Args: Ops);
548
549 LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *Call << "\n");
550 return cast<Instruction>(Val: Call);
551}
552
553PHINode* HardwareLoop::InsertPHICounter(Value *NumElts, Value *EltsRem) {
554 BasicBlock *Preheader = L->getLoopPreheader();
555 BasicBlock *Header = L->getHeader();
556 BasicBlock *Latch = ExitBranch->getParent();
557 IRBuilder<> Builder(Header, Header->getFirstNonPHIIt());
558 PHINode *Index = Builder.CreatePHI(Ty: NumElts->getType(), NumReservedValues: 2);
559 Index->addIncoming(V: NumElts, BB: Preheader);
560 Index->addIncoming(V: EltsRem, BB: Latch);
561 LLVM_DEBUG(dbgs() << "HWLoops: PHI Counter: " << *Index << "\n");
562 return Index;
563}
564
565void HardwareLoop::UpdateBranch(Value *EltsRem) {
566 IRBuilder<> CondBuilder(ExitBranch);
567 Value *NewCond =
568 CondBuilder.CreateICmpNE(LHS: EltsRem, RHS: ConstantInt::get(Ty: EltsRem->getType(), V: 0));
569 Value *OldCond = ExitBranch->getCondition();
570 ExitBranch->setCondition(NewCond);
571
572 // The false branch must exit the loop.
573 if (!L->contains(BB: ExitBranch->getSuccessor(i: 0)))
574 ExitBranch->swapSuccessors();
575
576 // The old condition may be dead now, and may have even created a dead PHI
577 // (the original induction variable).
578 RecursivelyDeleteTriviallyDeadInstructions(V: OldCond);
579}
580
581INITIALIZE_PASS_BEGIN(HardwareLoopsLegacy, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
582INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
583INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
584INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
585INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
586INITIALIZE_PASS_END(HardwareLoopsLegacy, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
587
588FunctionPass *llvm::createHardwareLoopsLegacyPass() { return new HardwareLoopsLegacy(); }
589