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