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