llvm/lib/Transforms/Utils/LoopVersioning.cpp

   1 //===- LoopVersioning.cpp - Utility to version a loop ---------------------===//
   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 //
   9 // This file defines a utility class to perform loop versioning.  The versioned
  10 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
  11 // emits checks to prove this.
  12 //
  13 //===----------------------------------------------------------------------===//
  14
  15 #include "llvm/Transforms/Utils/LoopVersioning.h"
  16 #include "llvm/ADT/ArrayRef.h"
  17 #include "llvm/Analysis/AliasAnalysis.h"
  18 #include "llvm/Analysis/InstSimplifyFolder.h"
  19 #include "llvm/Analysis/LoopAccessAnalysis.h"
  20 #include "llvm/Analysis/LoopInfo.h"
  21 #include "llvm/Analysis/ScalarEvolution.h"
  22 #include "llvm/Analysis/TargetLibraryInfo.h"
  23 #include "llvm/IR/Dominators.h"
  24 #include "llvm/IR/MDBuilder.h"
  25 #include "llvm/IR/PassManager.h"
  26 #include "llvm/InitializePasses.h"
  27 #include "llvm/Support/CommandLine.h"
  28 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
  29 #include "llvm/Transforms/Utils/Cloning.h"
  30 #include "llvm/Transforms/Utils/ScalarEvolutionExpander.h"
  31
  32 using namespace llvm;
  33
  34 static cl::opt<bool>
  35     AnnotateNoAlias("loop-version-annotate-no-alias", cl::init(true),
  36                     cl::Hidden,
  37                     cl::desc("Add no-alias annotation for instructions that "
  38                              "are disambiguated by memchecks"));
  39
  40 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI,
  41                                ArrayRef<RuntimePointerCheck> Checks, Loop *L,
  42                                LoopInfo *LI, DominatorTree *DT,
  43                                ScalarEvolution *SE)
  44     : VersionedLoop(L), AliasChecks(Checks.begin(), Checks.end()),
  45       Preds(LAI.getPSE().getPredicate()), LAI(LAI), LI(LI), DT(DT),
  46       SE(SE) {
  47 }
  48
  49 void LoopVersioning::versionLoop(
  50     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
  51   assert(VersionedLoop->getUniqueExitBlock() && "No single exit block");
  52   assert(VersionedLoop->isLoopSimplifyForm() &&
  53          "Loop is not in loop-simplify form");
  54
  55   Value *MemRuntimeCheck;
  56   Value *SCEVRuntimeCheck;
  57   Value *RuntimeCheck = nullptr;
  58
  59   // Add the memcheck in the original preheader (this is empty initially).
  60   BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
  61   const auto &RtPtrChecking = *LAI.getRuntimePointerChecking();
  62
  63   SCEVExpander Exp2(*RtPtrChecking.getSE(),
  64                     VersionedLoop->getHeader()->getModule()->getDataLayout(),
  65                     "induction");
  66   MemRuntimeCheck = addRuntimeChecks(RuntimeCheckBB->getTerminator(),
  67                                      VersionedLoop, AliasChecks, Exp2);
  68
  69   SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
  70                    "scev.check");
  71   SCEVRuntimeCheck =
  72       Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());
  73
  74   IRBuilder<InstSimplifyFolder> Builder(
  75       RuntimeCheckBB->getContext(),
  76       InstSimplifyFolder(RuntimeCheckBB->getModule()->getDataLayout()));
  77   if (MemRuntimeCheck && SCEVRuntimeCheck) {
  78     Builder.SetInsertPoint(RuntimeCheckBB->getTerminator());
  79     RuntimeCheck =
  80         Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck, "lver.safe");
  81   } else
  82     RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
  83
  84   assert(RuntimeCheck && "called even though we don't need "
  85                          "any runtime checks");
  86
  87   // Rename the block to make the IR more readable.
  88   RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
  89                           ".lver.check");
  90
  91   // Create empty preheader for the loop (and after cloning for the
  92   // non-versioned loop).
  93   BasicBlock *PH =
  94       SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,
  95                  nullptr, VersionedLoop->getHeader()->getName() + ".ph");
  96
  97   // Clone the loop including the preheader.
  98   //
  99   // FIXME: This does not currently preserve SimplifyLoop because the exit
 100   // block is a join between the two loops.
 101   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
 102   NonVersionedLoop =
 103       cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
 104                              ".lver.orig", LI, DT, NonVersionedLoopBlocks);
 105   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
 106
 107   // Insert the conditional branch based on the result of the memchecks.
 108   Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
 109   Builder.SetInsertPoint(OrigTerm);
 110   Builder.CreateCondBr(RuntimeCheck, NonVersionedLoop->getLoopPreheader(),
 111                        VersionedLoop->getLoopPreheader());
 112   OrigTerm->eraseFromParent();
 113
 114   // The loops merge in the original exit block.  This is now dominated by the
 115   // memchecking block.
 116   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
 117
 118   // Adds the necessary PHI nodes for the versioned loops based on the
 119   // loop-defined values used outside of the loop.
 120   addPHINodes(DefsUsedOutside);
 121   formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
 122   formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
 123   assert(NonVersionedLoop->isLoopSimplifyForm() &&
 124          VersionedLoop->isLoopSimplifyForm() &&
 125          "The versioned loops should be in simplify form.");
 126 }
 127
 128 void LoopVersioning::addPHINodes(
 129     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
 130   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
 131   assert(PHIBlock && "No single successor to loop exit block");
 132   PHINode *PN;
 133
 134   // First add a single-operand PHI for each DefsUsedOutside if one does not
 135   // exists yet.
 136   for (auto *Inst : DefsUsedOutside) {
 137     // See if we have a single-operand PHI with the value defined by the
 138     // original loop.
 139     for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
 140       if (PN->getIncomingValue(0) == Inst)
 141         break;
 142     }
 143     // If not create it.
 144     if (!PN) {
 145       PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
 146                            &PHIBlock->front());
 147       SmallVector<User*, 8> UsersToUpdate;
 148       for (User *U : Inst->users())
 149         if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
 150           UsersToUpdate.push_back(U);
 151       for (User *U : UsersToUpdate)
 152         U->replaceUsesOfWith(Inst, PN);
 153       PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
 154     }
 155   }
 156
 157   // Then for each PHI add the operand for the edge from the cloned loop.
 158   for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
 159     assert(PN->getNumOperands() == 1 &&
 160            "Exit block should only have on predecessor");
 161
 162     // If the definition was cloned used that otherwise use the same value.
 163     Value *ClonedValue = PN->getIncomingValue(0);
 164     auto Mapped = VMap.find(ClonedValue);
 165     if (Mapped != VMap.end())
 166       ClonedValue = Mapped->second;
 167
 168     PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
 169   }
 170 }
 171
 172 void LoopVersioning::prepareNoAliasMetadata() {
 173   // We need to turn the no-alias relation between pointer checking groups into
 174   // no-aliasing annotations between instructions.
 175   //
 176   // We accomplish this by mapping each pointer checking group (a set of
 177   // pointers memchecked together) to an alias scope and then also mapping each
 178   // group to the list of scopes it can't alias.
 179
 180   const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
 181   LLVMContext &Context = VersionedLoop->getHeader()->getContext();
 182
 183   // First allocate an aliasing scope for each pointer checking group.
 184   //
 185   // While traversing through the checking groups in the loop, also create a
 186   // reverse map from pointers to the pointer checking group they were assigned
 187   // to.
 188   MDBuilder MDB(Context);
 189   MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
 190
 191   for (const auto &Group : RtPtrChecking->CheckingGroups) {
 192     GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
 193
 194     for (unsigned PtrIdx : Group.Members)
 195       PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
 196   }
 197
 198   // Go through the checks and for each pointer group, collect the scopes for
 199   // each non-aliasing pointer group.
 200   DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>>
 201       GroupToNonAliasingScopes;
 202
 203   for (const auto &Check : AliasChecks)
 204     GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
 205
 206   // Finally, transform the above to actually map to scope list which is what
 207   // the metadata uses.
 208
 209   for (auto Pair : GroupToNonAliasingScopes)
 210     GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
 211 }
 212
 213 void LoopVersioning::annotateLoopWithNoAlias() {
 214   if (!AnnotateNoAlias)
 215     return;
 216
 217   // First prepare the maps.
 218   prepareNoAliasMetadata();
 219
 220   // Add the scope and no-alias metadata to the instructions.
 221   for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) {
 222     annotateInstWithNoAlias(I);
 223   }
 224 }
 225
 226 void LoopVersioning::annotateInstWithNoAlias(Instruction *VersionedInst,
 227                                              const Instruction *OrigInst) {
 228   if (!AnnotateNoAlias)
 229     return;
 230
 231   LLVMContext &Context = VersionedLoop->getHeader()->getContext();
 232   const Value *Ptr = isa<LoadInst>(OrigInst)
 233                          ? cast<LoadInst>(OrigInst)->getPointerOperand()
 234                          : cast<StoreInst>(OrigInst)->getPointerOperand();
 235
 236   // Find the group for the pointer and then add the scope metadata.
 237   auto Group = PtrToGroup.find(Ptr);
 238   if (Group != PtrToGroup.end()) {
 239     VersionedInst->setMetadata(
 240         LLVMContext::MD_alias_scope,
 241         MDNode::concatenate(
 242             VersionedInst->getMetadata(LLVMContext::MD_alias_scope),
 243             MDNode::get(Context, GroupToScope[Group->second])));
 244
 245     // Add the no-alias metadata.
 246     auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
 247     if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
 248       VersionedInst->setMetadata(
 249           LLVMContext::MD_noalias,
 250           MDNode::concatenate(
 251               VersionedInst->getMetadata(LLVMContext::MD_noalias),
 252               NonAliasingScopeList->second));
 253   }
 254 }
 255
 256 namespace {
 257 bool runImpl(LoopInfo *LI, function_ref<const LoopAccessInfo &(Loop &)> GetLAA,
 258              DominatorTree *DT, ScalarEvolution *SE) {
 259   // Build up a worklist of inner-loops to version. This is necessary as the
 260   // act of versioning a loop creates new loops and can invalidate iterators
 261   // across the loops.
 262   SmallVector<Loop *, 8> Worklist;
 263
 264   for (Loop *TopLevelLoop : *LI)
 265     for (Loop *L : depth_first(TopLevelLoop))
 266       // We only handle inner-most loops.
 267       if (L->isInnermost())
 268         Worklist.push_back(L);
 269
 270   // Now walk the identified inner loops.
 271   bool Changed = false;
 272   for (Loop *L : Worklist) {
 273     if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
 274         !L->getExitingBlock())
 275       continue;
 276     const LoopAccessInfo &LAI = GetLAA(*L);
 277     if (!LAI.hasConvergentOp() &&
 278         (LAI.getNumRuntimePointerChecks() ||
 279          !LAI.getPSE().getPredicate().isAlwaysTrue())) {
 280       LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
 281                           LI, DT, SE);
 282       LVer.versionLoop();
 283       LVer.annotateLoopWithNoAlias();
 284       Changed = true;
 285     }
 286   }
 287
 288   return Changed;
 289 }
 290
 291 /// Also expose this is a pass.  Currently this is only used for
 292 /// unit-testing.  It adds all memchecks necessary to remove all may-aliasing
 293 /// array accesses from the loop.
 294 class LoopVersioningLegacyPass : public FunctionPass {
 295 public:
 296   LoopVersioningLegacyPass() : FunctionPass(ID) {
 297     initializeLoopVersioningLegacyPassPass(*PassRegistry::getPassRegistry());
 298   }
 299
 300   bool runOnFunction(Function &F) override {
 301     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
 302     auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
 303       return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(&L);
 304     };
 305
 306     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
 307     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
 308
 309     return runImpl(LI, GetLAA, DT, SE);
 310   }
 311
 312   void getAnalysisUsage(AnalysisUsage &AU) const override {
 313     AU.addRequired<LoopInfoWrapperPass>();
 314     AU.addPreserved<LoopInfoWrapperPass>();
 315     AU.addRequired<LoopAccessLegacyAnalysis>();
 316     AU.addRequired<DominatorTreeWrapperPass>();
 317     AU.addPreserved<DominatorTreeWrapperPass>();
 318     AU.addRequired<ScalarEvolutionWrapperPass>();
 319   }
 320
 321   static char ID;
 322 };
 323 }
 324
 325 #define LVER_OPTION "loop-versioning"
 326 #define DEBUG_TYPE LVER_OPTION
 327
 328 char LoopVersioningLegacyPass::ID;
 329 static const char LVer_name[] = "Loop Versioning";
 330
 331 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
 332                       false)
 333 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
 334 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
 335 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
 336 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
 337 INITIALIZE_PASS_END(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
 338                     false)
 339
 340 namespace llvm {
 341 FunctionPass *createLoopVersioningLegacyPass() {
 342   return new LoopVersioningLegacyPass();
 343 }
 344
 345 PreservedAnalyses LoopVersioningPass::run(Function &F,
 346                                           FunctionAnalysisManager &AM) {
 347   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
 348   auto &LI = AM.getResult<LoopAnalysis>(F);
 349   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
 350   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
 351   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
 352   auto &AA = AM.getResult<AAManager>(F);
 353   auto &AC = AM.getResult<AssumptionAnalysis>(F);
 354
 355   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
 356   auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
 357     LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,      SE,
 358                                       TLI, TTI, nullptr, nullptr, nullptr};
 359     return LAM.getResult<LoopAccessAnalysis>(L, AR);
 360   };
 361
 362   if (runImpl(&LI, GetLAA, &DT, &SE))
 363     return PreservedAnalyses::none();
 364   return PreservedAnalyses::all();
 365 }
 366 } // namespace llvm