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