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/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"
46
47#define DEBUG_TYPE "hardware-loops"
48
49#define HW_LOOPS_NAME "Hardware Loop Insertion"
50
51using namespace llvm;
52
53static cl::opt<bool>
54ForceHardwareLoops("force-hardware-loops", cl::Hidden, cl::init(false),
55                   cl::desc("Force hardware loops intrinsics to be inserted"));
56
57static cl::opt<bool>
58ForceHardwareLoopPHI(
59  "force-hardware-loop-phi", cl::Hidden, cl::init(false),
60  cl::desc("Force hardware loop counter to be updated through a phi"));
61
62static cl::opt<bool>
63ForceNestedLoop("force-nested-hardware-loop", cl::Hidden, cl::init(false),
64                cl::desc("Force allowance of nested hardware loops"));
65
66static cl::opt<unsigned>
67LoopDecrement("hardware-loop-decrement", cl::Hidden, cl::init(1),
68            cl::desc("Set the loop decrement value"));
69
70static cl::opt<unsigned>
71CounterBitWidth("hardware-loop-counter-bitwidth", cl::Hidden, cl::init(32),
72                cl::desc("Set the loop counter bitwidth"));
73
74static cl::opt<bool>
75ForceGuardLoopEntry(
76  "force-hardware-loop-guard", cl::Hidden, cl::init(false),
77  cl::desc("Force generation of loop guard intrinsic"));
78
79STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
80
81#ifndef NDEBUG
82static void debugHWLoopFailure(const StringRef DebugMsg,
83    Instruction *I) {
84  dbgs() << "HWLoops: " << DebugMsg;
85  if (I)
86    dbgs() << ' ' << *I;
87  else
88    dbgs() << '.';
89  dbgs() << '\n';
90}
91#endif
92
93static OptimizationRemarkAnalysis
94createHWLoopAnalysis(StringRef RemarkName, Loop *L, Instruction *I) {
95  Value *CodeRegion = L->getHeader();
96  DebugLoc DL = L->getStartLoc();
97
98  if (I) {
99    CodeRegion = I->getParent();
100    // If there is no debug location attached to the instruction, revert back to
101    // using the loop's.
102    if (I->getDebugLoc())
103      DL = I->getDebugLoc();
104  }
105
106  OptimizationRemarkAnalysis R(DEBUG_TYPE, RemarkName, DL, CodeRegion);
107  R << "hardware-loop not created: ";
108  return R;
109}
110
111namespace {
112
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);
117  }
118
119  using TTI = TargetTransformInfo;
120
121  class HardwareLoops : public FunctionPass {
122  public:
123    static char ID;
124
125    HardwareLoops() : FunctionPass(ID) {
126      initializeHardwareLoopsPass(*PassRegistry::getPassRegistry());
127    }
128
129    bool runOnFunction(Function &F) override;
130
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>();
140    }
141
142    // Try to convert the given Loop into a hardware loop.
143    bool TryConvertLoop(Loop *L);
144
145    // Given that the target believes the loop to be profitable, try to
146    // convert it.
147    bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
148
149  private:
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;
159    Module *M = nullptr;
160    bool MadeChange = false;
161  };
162
163  class HardwareLoop {
164    // Expand the trip count scev into a value that we can use.
165    Value *InitLoopCount();
166
167    // Insert the set_loop_iteration intrinsic.
168    void InsertIterationSetup(Value *LoopCountInit);
169
170    // Insert the loop_decrement intrinsic.
171    void InsertLoopDec();
172
173    // Insert the loop_decrement_reg intrinsic.
174    Instruction *InsertLoopRegDec(Value *EltsRem);
175
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);
180
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);
184
185  public:
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) { }
196
197    void Create();
198
199  private:
200    ScalarEvolution &SE;
201    const DataLayout &DL;
202    OptimizationRemarkEmitter *ORE = nullptr;
203    Loop *L                 = nullptr;
204    Module *M               = 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;
212  };
213}
214
215char HardwareLoops::ID = 0;
216
217bool HardwareLoops::runOnFunction(Function &F) {
218  if (skipFunction(F))
219    return false;
220
221  LLVM_DEBUG(dbgs() << "HWLoops: Running on " << F.getName() << "\n");
222
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);
233  M = F.getParent();
234
235  for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
236    Loop *L = *I;
237    if (!L->getParentLoop())
238      TryConvertLoop(L);
239  }
240
241  return MadeChange;
242}
243
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.
246bool HardwareLoops::TryConvertLoop(Loop *L) {
247  // Process nested loops first.
248  bool AnyChanged = false;
249  for (Loop *SL : *L)
250    AnyChanged |= TryConvertLoop(SL);
251  if (AnyChanged) {
252    reportHWLoopFailure("nested hardware-loops not supported", "HWLoopNested",
253                        ORE, L);
254    return true; // Stop search.
255  }
256
257  LLVM_DEBUG(dbgs() << "HWLoops: Loop " << L->getHeader()->getName() << "\n");
258
259  HardwareLoopInfo HWLoopInfo(L);
260  if (!HWLoopInfo.canAnalyze(*LI)) {
261    reportHWLoopFailure("cannot analyze loop, irreducible control flow",
262                        "HWLoopCannotAnalyze", ORE, L);
263    return false;
264  }
265
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);
270    return false;
271  }
272
273  // Allow overriding of the counter width and loop decrement value.
274  if (CounterBitWidth.getNumOccurrences())
275    HWLoopInfo.CountType =
276      IntegerType::get(M->getContext(), CounterBitWidth);
277
278  if (LoopDecrement.getNumOccurrences())
279    HWLoopInfo.LoopDecrement =
280      ConstantInt::get(HWLoopInfo.CountType, LoopDecrement);
281
282  MadeChange |= TryConvertLoop(HWLoopInfo);
283  return MadeChange && (!HWLoopInfo.IsNestingLegal && !ForceNestedLoop);
284}
285
286bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
287
288  Loop *L = HWLoopInfo.L;
289  LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
290
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);
297    return false;
298  }
299
300  assert(
301      (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
302      "Hardware Loop must have set exit info.");
303
304  BasicBlock *Preheader = L->getLoopPreheader();
305
306  // If we don't have a preheader, then insert one.
307  if (!Preheader)
308    Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
309  if (!Preheader)
310    return false;
311
312  HardwareLoop HWLoop(HWLoopInfo, *SE, *DL, ORE);
313  HWLoop.Create();
314  ++NumHWLoops;
315  return true;
316}
317
318void HardwareLoop::Create() {
319  LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
320
321  Value *LoopCountInit = InitLoopCount();
322  if (!LoopCountInit) {
323    reportHWLoopFailure("could not safely create a loop count expression",
324                        "HWLoopNotSafe", ORE, L);
325    return;
326  }
327
328  InsertIterationSetup(LoopCountInit);
329
330  if (UsePHICounter || ForceHardwareLoopPHI) {
331    Instruction *LoopDec = InsertLoopRegDec(LoopCountInit);
332    Value *EltsRem = InsertPHICounter(LoopCountInit, LoopDec);
333    LoopDec->setOperand(0, EltsRem);
334    UpdateBranch(LoopDec);
335  } else
336    InsertLoopDec();
337
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())
341    DeleteDeadPHIs(I);
342}
343
344static bool CanGenerateTest(Loop *L, Value *Count) {
345  BasicBlock *Preheader = L->getLoopPreheader();
346  if (!Preheader->getSinglePredecessor())
347    return false;
348
349  BasicBlock *Pred = Preheader->getSinglePredecessor();
350  if (!isa<BranchInst>(Pred->getTerminator()))
351    return false;
352
353  auto *BI = cast<BranchInst>(Pred->getTerminator());
354  if (BI->isUnconditional() || !isa<ICmpInst>(BI->getCondition()))
355    return false;
356
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())
362    return false;
363
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;
367    return false;
368  };
369
370  if (!IsCompareZero(ICmp, Count, 0) && !IsCompareZero(ICmp, Count, 1))
371    return false;
372
373  unsigned SuccIdx = ICmp->getPredicate() == ICmpInst::ICMP_NE ? 0 : 1;
374  if (BI->getSuccessor(SuccIdx) != Preheader)
375    return false;
376
377  return true;
378}
379
380Value *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?
384
385  SCEVExpander SCEVE(SE, DL, "loopcnt");
386  if (!ExitCount->getType()->isPointerTy() &&
387      ExitCount->getType() != CountType)
388    ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);
389
390  ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));
391
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;
400  } else
401    UseLoopGuard = false;
402
403  BasicBlock *BB = L->getLoopPreheader();
404  if (UseLoopGuard && BB->getSinglePredecessor() &&
405      cast<BranchInst>(BB->getTerminator())->isUnconditional())
406    BB = BB->getSinglePredecessor();
407
408  if (!isSafeToExpandAt(ExitCount, BB->getTerminator(), SE)) {
409    LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
410               << *ExitCount << "\n");
411    return nullptr;
412  }
413
414  Value *Count = SCEVE.expandCodeFor(ExitCount, CountType,
415                                     BB->getTerminator());
416
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.
423
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");
430  return Count;
431}
432
433void 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);
440
441  // Use the return value of the intrinsic to control the entry of the loop.
442  if (UseLoopGuard) {
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();
450  }
451  LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop counter: "
452             << *SetCount << "\n");
453}
454
455void HardwareLoop::InsertLoopDec() {
456  IRBuilder<> CondBuilder(ExitBranch);
457
458  Function *DecFunc =
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);
465
466  // The false branch must exit the loop.
467  if (!L->contains(ExitBranch->getSuccessor(0)))
468    ExitBranch->swapSuccessors();
469
470  // The old condition may be dead now, and may have even created a dead PHI
471  // (the original induction variable).
472  RecursivelyDeleteTriviallyDeadInstructions(OldCond);
473
474  LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *NewCond << "\n");
475}
476
477Instruction* HardwareLoop::InsertLoopRegDec(Value *EltsRem) {
478  IRBuilder<> CondBuilder(ExitBranch);
479
480  Function *DecFunc =
481      Intrinsic::getDeclaration(M, Intrinsic::loop_decrement_reg,
482                                { EltsRem->getType() });
483  Value *Ops[] = { EltsRem, LoopDecrement };
484  Value *Call = CondBuilder.CreateCall(DecFunc, Ops);
485
486  LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *Call << "\n");
487  return cast<Instruction>(Call);
488}
489
490PHINode* 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");
499  return Index;
500}
501
502void HardwareLoop::UpdateBranch(Value *EltsRem) {
503  IRBuilder<> CondBuilder(ExitBranch);
504  Value *NewCond =
505    CondBuilder.CreateICmpNE(EltsRem, ConstantInt::get(EltsRem->getType(), 0));
506  Value *OldCond = ExitBranch->getCondition();
507  ExitBranch->setCondition(NewCond);
508
509  // The false branch must exit the loop.
510  if (!L->contains(ExitBranch->getSuccessor(0)))
511    ExitBranch->swapSuccessors();
512
513  // The old condition may be dead now, and may have even created a dead PHI
514  // (the original induction variable).
515  RecursivelyDeleteTriviallyDeadInstructions(OldCond);
516}
517
518INITIALIZE_PASS_BEGIN(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
519INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
520INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
521INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
522INITIALIZE_PASS_DEPENDENCY(OptimizationRemarkEmitterWrapperPass)
523INITIALIZE_PASS_END(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
524
525FunctionPass *llvm::createHardwareLoopsPass() { return new HardwareLoops(); }
526