lib/CodeGen/HardwareLoops.cpp

   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/Pass.h"
  19 #include "llvm/PassRegistry.h"
  20 #include "llvm/PassSupport.h"
  21 #include "llvm/ADT/Statistic.h"
  22 #include "llvm/Analysis/AssumptionCache.h"
  23 #include "llvm/Analysis/LoopInfo.h"
  24 #include "llvm/Analysis/ScalarEvolution.h"
  25 #include "llvm/Analysis/ScalarEvolutionExpander.h"
  26 #include "llvm/Analysis/TargetTransformInfo.h"
  27 #include "llvm/CodeGen/Passes.h"
  28 #include "llvm/CodeGen/TargetPassConfig.h"
  29 #include "llvm/IR/BasicBlock.h"
  30 #include "llvm/IR/DataLayout.h"
  31 #include "llvm/IR/Dominators.h"
  32 #include "llvm/IR/Constants.h"
  33 #include "llvm/IR/IRBuilder.h"
  34 #include "llvm/IR/Instructions.h"
  35 #include "llvm/IR/IntrinsicInst.h"
  36 #include "llvm/IR/Value.h"
  37 #include "llvm/Support/Debug.h"
  38 #include "llvm/Transforms/Scalar.h"
  39 #include "llvm/Transforms/Utils.h"
  40 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  41 #include "llvm/Transforms/Utils/Local.h"
  42 #include "llvm/Transforms/Utils/LoopUtils.h"
  43
  44 #define DEBUG_TYPE "hardware-loops"
  45
  46 #define HW_LOOPS_NAME "Hardware Loop Insertion"
  47
  48 using namespace llvm;
  49
  50 static cl::opt<bool>
  51 ForceHardwareLoops("force-hardware-loops", cl::Hidden, cl::init(false),
  52                    cl::desc("Force hardware loops intrinsics to be inserted"));
  53
  54 static cl::opt<bool>
  55 ForceHardwareLoopPHI(
  56   "force-hardware-loop-phi", cl::Hidden, cl::init(false),
  57   cl::desc("Force hardware loop counter to be updated through a phi"));
  58
  59 static cl::opt<bool>
  60 ForceNestedLoop("force-nested-hardware-loop", cl::Hidden, cl::init(false),
  61                 cl::desc("Force allowance of nested hardware loops"));
  62
  63 static cl::opt<unsigned>
  64 LoopDecrement("hardware-loop-decrement", cl::Hidden, cl::init(1),
  65             cl::desc("Set the loop decrement value"));
  66
  67 static cl::opt<unsigned>
  68 CounterBitWidth("hardware-loop-counter-bitwidth", cl::Hidden, cl::init(32),
  69                 cl::desc("Set the loop counter bitwidth"));
  70
  71 static cl::opt<bool>
  72 ForceGuardLoopEntry(
  73   "force-hardware-loop-guard", cl::Hidden, cl::init(false),
  74   cl::desc("Force generation of loop guard intrinsic"));
  75
  76 STATISTIC(NumHWLoops, "Number of loops converted to hardware loops");
  77
  78 namespace {
  79
  80   using TTI = TargetTransformInfo;
  81
  82   class HardwareLoops : public FunctionPass {
  83   public:
  84     static char ID;
  85
  86     HardwareLoops() : FunctionPass(ID) {
  87       initializeHardwareLoopsPass(*PassRegistry::getPassRegistry());
  88     }
  89
  90     bool runOnFunction(Function &F) override;
  91
  92     void getAnalysisUsage(AnalysisUsage &AU) const override {
  93       AU.addRequired<LoopInfoWrapperPass>();
  94       AU.addPreserved<LoopInfoWrapperPass>();
  95       AU.addRequired<DominatorTreeWrapperPass>();
  96       AU.addPreserved<DominatorTreeWrapperPass>();
  97       AU.addRequired<ScalarEvolutionWrapperPass>();
  98       AU.addRequired<AssumptionCacheTracker>();
  99       AU.addRequired<TargetTransformInfoWrapperPass>();
 100     }
 101
 102     // Try to convert the given Loop into a hardware loop.
 103     bool TryConvertLoop(Loop *L);
 104
 105     // Given that the target believes the loop to be profitable, try to
 106     // convert it.
 107     bool TryConvertLoop(HardwareLoopInfo &HWLoopInfo);
 108
 109   private:
 110     ScalarEvolution *SE = nullptr;
 111     LoopInfo *LI = nullptr;
 112     const DataLayout *DL = nullptr;
 113     const TargetTransformInfo *TTI = nullptr;
 114     DominatorTree *DT = nullptr;
 115     bool PreserveLCSSA = false;
 116     AssumptionCache *AC = nullptr;
 117     TargetLibraryInfo *LibInfo = nullptr;
 118     Module *M = nullptr;
 119     bool MadeChange = false;
 120   };
 121
 122   class HardwareLoop {
 123     // Expand the trip count scev into a value that we can use.
 124     Value *InitLoopCount();
 125
 126     // Insert the set_loop_iteration intrinsic.
 127     void InsertIterationSetup(Value *LoopCountInit);
 128
 129     // Insert the loop_decrement intrinsic.
 130     void InsertLoopDec();
 131
 132     // Insert the loop_decrement_reg intrinsic.
 133     Instruction *InsertLoopRegDec(Value *EltsRem);
 134
 135     // If the target requires the counter value to be updated in the loop,
 136     // insert a phi to hold the value. The intended purpose is for use by
 137     // loop_decrement_reg.
 138     PHINode *InsertPHICounter(Value *NumElts, Value *EltsRem);
 139
 140     // Create a new cmp, that checks the returned value of loop_decrement*,
 141     // and update the exit branch to use it.
 142     void UpdateBranch(Value *EltsRem);
 143
 144   public:
 145     HardwareLoop(HardwareLoopInfo &Info, ScalarEvolution &SE,
 146                  const DataLayout &DL) :
 147       SE(SE), DL(DL), L(Info.L), M(L->getHeader()->getModule()),
 148       ExitCount(Info.ExitCount),
 149       CountType(Info.CountType),
 150       ExitBranch(Info.ExitBranch),
 151       LoopDecrement(Info.LoopDecrement),
 152       UsePHICounter(Info.CounterInReg),
 153       UseLoopGuard(Info.PerformEntryTest) { }
 154
 155     void Create();
 156
 157   private:
 158     ScalarEvolution &SE;
 159     const DataLayout &DL;
 160     Loop *L                 = nullptr;
 161     Module *M               = nullptr;
 162     const SCEV *ExitCount   = nullptr;
 163     Type *CountType         = nullptr;
 164     BranchInst *ExitBranch  = nullptr;
 165     Value *LoopDecrement    = nullptr;
 166     bool UsePHICounter      = false;
 167     bool UseLoopGuard       = false;
 168     BasicBlock *BeginBB     = nullptr;
 169   };
 170 }
 171
 172 char HardwareLoops::ID = 0;
 173
 174 bool HardwareLoops::runOnFunction(Function &F) {
 175   if (skipFunction(F))
 176     return false;
 177
 178   LLVM_DEBUG(dbgs() << "HWLoops: Running on " << F.getName() << "\n");
 179
 180   LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 181   SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 182   DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 183   TTI = &getAnalysis<TargetTransformInfoWrapperPass>().getTTI(F);
 184   DL = &F.getParent()->getDataLayout();
 185   auto *TLIP = getAnalysisIfAvailable<TargetLibraryInfoWrapperPass>();
 186   LibInfo = TLIP ? &TLIP->getTLI(F) : nullptr;
 187   PreserveLCSSA = mustPreserveAnalysisID(LCSSAID);
 188   AC = &getAnalysis<AssumptionCacheTracker>().getAssumptionCache(F);
 189   M = F.getParent();
 190
 191   for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
 192     Loop *L = *I;
 193     if (!L->getParentLoop())
 194       TryConvertLoop(L);
 195   }
 196
 197   return MadeChange;
 198 }
 199
 200 // Return true if the search should stop, which will be when an inner loop is
 201 // converted and the parent loop doesn't support containing a hardware loop.
 202 bool HardwareLoops::TryConvertLoop(Loop *L) {
 203   // Process nested loops first.
 204   for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
 205     if (TryConvertLoop(*I))
 206       return true; // Stop search.
 207
 208   HardwareLoopInfo HWLoopInfo(L);
 209   if (!HWLoopInfo.canAnalyze(*LI))
 210     return false;
 211
 212   if (TTI->isHardwareLoopProfitable(L, *SE, *AC, LibInfo, HWLoopInfo) ||
 213       ForceHardwareLoops) {
 214
 215     // Allow overriding of the counter width and loop decrement value.
 216     if (CounterBitWidth.getNumOccurrences())
 217       HWLoopInfo.CountType =
 218         IntegerType::get(M->getContext(), CounterBitWidth);
 219
 220     if (LoopDecrement.getNumOccurrences())
 221       HWLoopInfo.LoopDecrement =
 222         ConstantInt::get(HWLoopInfo.CountType, LoopDecrement);
 223
 224     MadeChange |= TryConvertLoop(HWLoopInfo);
 225     return MadeChange && (!HWLoopInfo.IsNestingLegal && !ForceNestedLoop);
 226   }
 227
 228   return false;
 229 }
 230
 231 bool HardwareLoops::TryConvertLoop(HardwareLoopInfo &HWLoopInfo) {
 232
 233   Loop *L = HWLoopInfo.L;
 234   LLVM_DEBUG(dbgs() << "HWLoops: Try to convert profitable loop: " << *L);
 235
 236   if (!HWLoopInfo.isHardwareLoopCandidate(*SE, *LI, *DT, ForceNestedLoop,
 237                                           ForceHardwareLoopPHI))
 238     return false;
 239
 240   assert(
 241       (HWLoopInfo.ExitBlock && HWLoopInfo.ExitBranch && HWLoopInfo.ExitCount) &&
 242       "Hardware Loop must have set exit info.");
 243
 244   BasicBlock *Preheader = L->getLoopPreheader();
 245
 246   // If we don't have a preheader, then insert one.
 247   if (!Preheader)
 248     Preheader = InsertPreheaderForLoop(L, DT, LI, nullptr, PreserveLCSSA);
 249   if (!Preheader)
 250     return false;
 251
 252   HardwareLoop HWLoop(HWLoopInfo, *SE, *DL);
 253   HWLoop.Create();
 254   ++NumHWLoops;
 255   return true;
 256 }
 257
 258 void HardwareLoop::Create() {
 259   LLVM_DEBUG(dbgs() << "HWLoops: Converting loop..\n");
 260
 261   Value *LoopCountInit = InitLoopCount();
 262   if (!LoopCountInit)
 263     return;
 264
 265   InsertIterationSetup(LoopCountInit);
 266
 267   if (UsePHICounter || ForceHardwareLoopPHI) {
 268     Instruction *LoopDec = InsertLoopRegDec(LoopCountInit);
 269     Value *EltsRem = InsertPHICounter(LoopCountInit, LoopDec);
 270     LoopDec->setOperand(0, EltsRem);
 271     UpdateBranch(LoopDec);
 272   } else
 273     InsertLoopDec();
 274
 275   // Run through the basic blocks of the loop and see if any of them have dead
 276   // PHIs that can be removed.
 277   for (auto I : L->blocks())
 278     DeleteDeadPHIs(I);
 279 }
 280
 281 static bool CanGenerateTest(Loop *L, Value *Count) {
 282   BasicBlock *Preheader = L->getLoopPreheader();
 283   if (!Preheader->getSinglePredecessor())
 284     return false;
 285
 286   BasicBlock *Pred = Preheader->getSinglePredecessor();
 287   if (!isa<BranchInst>(Pred->getTerminator()))
 288     return false;
 289
 290   auto *BI = cast<BranchInst>(Pred->getTerminator());
 291   if (BI->isUnconditional() || !isa<ICmpInst>(BI->getCondition()))
 292     return false;
 293
 294   // Check that the icmp is checking for equality of Count and zero and that
 295   // a non-zero value results in entering the loop.
 296   auto ICmp = cast<ICmpInst>(BI->getCondition());
 297   LLVM_DEBUG(dbgs() << " - Found condition: " << *ICmp << "\n");
 298   if (!ICmp->isEquality())
 299     return false;
 300
 301   auto IsCompareZero = [](ICmpInst *ICmp, Value *Count, unsigned OpIdx) {
 302     if (auto *Const = dyn_cast<ConstantInt>(ICmp->getOperand(OpIdx)))
 303       return Const->isZero() && ICmp->getOperand(OpIdx ^ 1) == Count;
 304     return false;
 305   };
 306
 307   if (!IsCompareZero(ICmp, Count, 0) && !IsCompareZero(ICmp, Count, 1))
 308     return false;
 309
 310   unsigned SuccIdx = ICmp->getPredicate() == ICmpInst::ICMP_NE ? 0 : 1;
 311   if (BI->getSuccessor(SuccIdx) != Preheader)
 312     return false;
 313
 314   return true;
 315 }
 316
 317 Value *HardwareLoop::InitLoopCount() {
 318   LLVM_DEBUG(dbgs() << "HWLoops: Initialising loop counter value:\n");
 319   // Can we replace a conditional branch with an intrinsic that sets the
 320   // loop counter and tests that is not zero?
 321
 322   SCEVExpander SCEVE(SE, DL, "loopcnt");
 323   if (!ExitCount->getType()->isPointerTy() &&
 324       ExitCount->getType() != CountType)
 325     ExitCount = SE.getZeroExtendExpr(ExitCount, CountType);
 326
 327   ExitCount = SE.getAddExpr(ExitCount, SE.getOne(CountType));
 328
 329   // If we're trying to use the 'test and set' form of the intrinsic, we need
 330   // to replace a conditional branch that is controlling entry to the loop. It
 331   // is likely (guaranteed?) that the preheader has an unconditional branch to
 332   // the loop header, so also check if it has a single predecessor.
 333   if (SE.isLoopEntryGuardedByCond(L, ICmpInst::ICMP_NE, ExitCount,
 334                                   SE.getZero(ExitCount->getType()))) {
 335     LLVM_DEBUG(dbgs() << " - Attempting to use test.set counter.\n");
 336     UseLoopGuard |= ForceGuardLoopEntry;
 337   } else
 338     UseLoopGuard = false;
 339
 340   BasicBlock *BB = L->getLoopPreheader();
 341   if (UseLoopGuard && BB->getSinglePredecessor() &&
 342       cast<BranchInst>(BB->getTerminator())->isUnconditional())
 343     BB = BB->getSinglePredecessor();
 344
 345   if (!isSafeToExpandAt(ExitCount, BB->getTerminator(), SE)) {
 346     LLVM_DEBUG(dbgs() << "- Bailing, unsafe to expand ExitCount "
 347                << *ExitCount << "\n");
 348     return nullptr;
 349   }
 350
 351   Value *Count = SCEVE.expandCodeFor(ExitCount, CountType,
 352                                      BB->getTerminator());
 353
 354   // FIXME: We've expanded Count where we hope to insert the counter setting
 355   // intrinsic. But, in the case of the 'test and set' form, we may fallback to
 356   // the just 'set' form and in which case the insertion block is most likely
 357   // different. It means there will be instruction(s) in a block that possibly
 358   // aren't needed. The isLoopEntryGuardedByCond is trying to avoid this issue,
 359   // but it's doesn't appear to work in all cases.
 360
 361   UseLoopGuard = UseLoopGuard && CanGenerateTest(L, Count);
 362   BeginBB = UseLoopGuard ? BB : L->getLoopPreheader();
 363   LLVM_DEBUG(dbgs() << " - Loop Count: " << *Count << "\n"
 364              << " - Expanded Count in " << BB->getName() << "\n"
 365              << " - Will insert set counter intrinsic into: "
 366              << BeginBB->getName() << "\n");
 367   return Count;
 368 }
 369
 370 void HardwareLoop::InsertIterationSetup(Value *LoopCountInit) {
 371   IRBuilder<> Builder(BeginBB->getTerminator());
 372   Type *Ty = LoopCountInit->getType();
 373   Intrinsic::ID ID = UseLoopGuard ?
 374     Intrinsic::test_set_loop_iterations : Intrinsic::set_loop_iterations;
 375   Function *LoopIter = Intrinsic::getDeclaration(M, ID, Ty);
 376   Value *SetCount = Builder.CreateCall(LoopIter, LoopCountInit);
 377
 378   // Use the return value of the intrinsic to control the entry of the loop.
 379   if (UseLoopGuard) {
 380     assert((isa<BranchInst>(BeginBB->getTerminator()) &&
 381             cast<BranchInst>(BeginBB->getTerminator())->isConditional()) &&
 382            "Expected conditional branch");
 383     auto *LoopGuard = cast<BranchInst>(BeginBB->getTerminator());
 384     LoopGuard->setCondition(SetCount);
 385     if (LoopGuard->getSuccessor(0) != L->getLoopPreheader())
 386       LoopGuard->swapSuccessors();
 387   }
 388   LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop counter: "
 389              << *SetCount << "\n");
 390 }
 391
 392 void HardwareLoop::InsertLoopDec() {
 393   IRBuilder<> CondBuilder(ExitBranch);
 394
 395   Function *DecFunc =
 396     Intrinsic::getDeclaration(M, Intrinsic::loop_decrement,
 397                               LoopDecrement->getType());
 398   Value *Ops[] = { LoopDecrement };
 399   Value *NewCond = CondBuilder.CreateCall(DecFunc, Ops);
 400   Value *OldCond = ExitBranch->getCondition();
 401   ExitBranch->setCondition(NewCond);
 402
 403   // The false branch must exit the loop.
 404   if (!L->contains(ExitBranch->getSuccessor(0)))
 405     ExitBranch->swapSuccessors();
 406
 407   // The old condition may be dead now, and may have even created a dead PHI
 408   // (the original induction variable).
 409   RecursivelyDeleteTriviallyDeadInstructions(OldCond);
 410
 411   LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *NewCond << "\n");
 412 }
 413
 414 Instruction* HardwareLoop::InsertLoopRegDec(Value *EltsRem) {
 415   IRBuilder<> CondBuilder(ExitBranch);
 416
 417   Function *DecFunc =
 418       Intrinsic::getDeclaration(M, Intrinsic::loop_decrement_reg,
 419                                 { EltsRem->getType(), EltsRem->getType(),
 420                                   LoopDecrement->getType()
 421                                 });
 422   Value *Ops[] = { EltsRem, LoopDecrement };
 423   Value *Call = CondBuilder.CreateCall(DecFunc, Ops);
 424
 425   LLVM_DEBUG(dbgs() << "HWLoops: Inserted loop dec: " << *Call << "\n");
 426   return cast<Instruction>(Call);
 427 }
 428
 429 PHINode* HardwareLoop::InsertPHICounter(Value *NumElts, Value *EltsRem) {
 430   BasicBlock *Preheader = L->getLoopPreheader();
 431   BasicBlock *Header = L->getHeader();
 432   BasicBlock *Latch = ExitBranch->getParent();
 433   IRBuilder<> Builder(Header->getFirstNonPHI());
 434   PHINode *Index = Builder.CreatePHI(NumElts->getType(), 2);
 435   Index->addIncoming(NumElts, Preheader);
 436   Index->addIncoming(EltsRem, Latch);
 437   LLVM_DEBUG(dbgs() << "HWLoops: PHI Counter: " << *Index << "\n");
 438   return Index;
 439 }
 440
 441 void HardwareLoop::UpdateBranch(Value *EltsRem) {
 442   IRBuilder<> CondBuilder(ExitBranch);
 443   Value *NewCond =
 444     CondBuilder.CreateICmpNE(EltsRem, ConstantInt::get(EltsRem->getType(), 0));
 445   Value *OldCond = ExitBranch->getCondition();
 446   ExitBranch->setCondition(NewCond);
 447
 448   // The false branch must exit the loop.
 449   if (!L->contains(ExitBranch->getSuccessor(0)))
 450     ExitBranch->swapSuccessors();
 451
 452   // The old condition may be dead now, and may have even created a dead PHI
 453   // (the original induction variable).
 454   RecursivelyDeleteTriviallyDeadInstructions(OldCond);
 455 }
 456
 457 INITIALIZE_PASS_BEGIN(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
 458 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 459 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 460 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 461 INITIALIZE_PASS_END(HardwareLoops, DEBUG_TYPE, HW_LOOPS_NAME, false, false)
 462
 463 FunctionPass *llvm::createHardwareLoopsPass() { return new HardwareLoops(); }