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         SE->forgetValue(PN);
142         break;
143       }
144     }
145     // If not create it.
146     if (!PN) {
147       PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
148                            &PHIBlock->front());
149       SmallVector<User*, 8> UsersToUpdate;
150       for (User *U : Inst->users())
151         if (!VersionedLoop->contains(cast<Instruction>(U)->getParent()))
152           UsersToUpdate.push_back(U);
153       for (User *U : UsersToUpdate)
154         U->replaceUsesOfWith(Inst, PN);
155       PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
156     }
157   }
158 
159   // Then for each PHI add the operand for the edge from the cloned loop.
160   for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
161     assert(PN->getNumOperands() == 1 &&
162            "Exit block should only have on predecessor");
163 
164     // If the definition was cloned used that otherwise use the same value.
165     Value *ClonedValue = PN->getIncomingValue(0);
166     auto Mapped = VMap.find(ClonedValue);
167     if (Mapped != VMap.end())
168       ClonedValue = Mapped->second;
169 
170     PN->addIncoming(ClonedValue, NonVersionedLoop->getExitingBlock());
171   }
172 }
173 
174 void LoopVersioning::prepareNoAliasMetadata() {
175   // We need to turn the no-alias relation between pointer checking groups into
176   // no-aliasing annotations between instructions.
177   //
178   // We accomplish this by mapping each pointer checking group (a set of
179   // pointers memchecked together) to an alias scope and then also mapping each
180   // group to the list of scopes it can't alias.
181 
182   const RuntimePointerChecking *RtPtrChecking = LAI.getRuntimePointerChecking();
183   LLVMContext &Context = VersionedLoop->getHeader()->getContext();
184 
185   // First allocate an aliasing scope for each pointer checking group.
186   //
187   // While traversing through the checking groups in the loop, also create a
188   // reverse map from pointers to the pointer checking group they were assigned
189   // to.
190   MDBuilder MDB(Context);
191   MDNode *Domain = MDB.createAnonymousAliasScopeDomain("LVerDomain");
192 
193   for (const auto &Group : RtPtrChecking->CheckingGroups) {
194     GroupToScope[&Group] = MDB.createAnonymousAliasScope(Domain);
195 
196     for (unsigned PtrIdx : Group.Members)
197       PtrToGroup[RtPtrChecking->getPointerInfo(PtrIdx).PointerValue] = &Group;
198   }
199 
200   // Go through the checks and for each pointer group, collect the scopes for
201   // each non-aliasing pointer group.
202   DenseMap<const RuntimeCheckingPtrGroup *, SmallVector<Metadata *, 4>>
203       GroupToNonAliasingScopes;
204 
205   for (const auto &Check : AliasChecks)
206     GroupToNonAliasingScopes[Check.first].push_back(GroupToScope[Check.second]);
207 
208   // Finally, transform the above to actually map to scope list which is what
209   // the metadata uses.
210 
211   for (auto Pair : GroupToNonAliasingScopes)
212     GroupToNonAliasingScopeList[Pair.first] = MDNode::get(Context, Pair.second);
213 }
214 
215 void LoopVersioning::annotateLoopWithNoAlias() {
216   if (!AnnotateNoAlias)
217     return;
218 
219   // First prepare the maps.
220   prepareNoAliasMetadata();
221 
222   // Add the scope and no-alias metadata to the instructions.
223   for (Instruction *I : LAI.getDepChecker().getMemoryInstructions()) {
224     annotateInstWithNoAlias(I);
225   }
226 }
227 
228 void LoopVersioning::annotateInstWithNoAlias(Instruction *VersionedInst,
229                                              const Instruction *OrigInst) {
230   if (!AnnotateNoAlias)
231     return;
232 
233   LLVMContext &Context = VersionedLoop->getHeader()->getContext();
234   const Value *Ptr = isa<LoadInst>(OrigInst)
235                          ? cast<LoadInst>(OrigInst)->getPointerOperand()
236                          : cast<StoreInst>(OrigInst)->getPointerOperand();
237 
238   // Find the group for the pointer and then add the scope metadata.
239   auto Group = PtrToGroup.find(Ptr);
240   if (Group != PtrToGroup.end()) {
241     VersionedInst->setMetadata(
242         LLVMContext::MD_alias_scope,
243         MDNode::concatenate(
244             VersionedInst->getMetadata(LLVMContext::MD_alias_scope),
245             MDNode::get(Context, GroupToScope[Group->second])));
246 
247     // Add the no-alias metadata.
248     auto NonAliasingScopeList = GroupToNonAliasingScopeList.find(Group->second);
249     if (NonAliasingScopeList != GroupToNonAliasingScopeList.end())
250       VersionedInst->setMetadata(
251           LLVMContext::MD_noalias,
252           MDNode::concatenate(
253               VersionedInst->getMetadata(LLVMContext::MD_noalias),
254               NonAliasingScopeList->second));
255   }
256 }
257 
258 namespace {
259 bool runImpl(LoopInfo *LI, function_ref<const LoopAccessInfo &(Loop &)> GetLAA,
260              DominatorTree *DT, ScalarEvolution *SE) {
261   // Build up a worklist of inner-loops to version. This is necessary as the
262   // act of versioning a loop creates new loops and can invalidate iterators
263   // across the loops.
264   SmallVector<Loop *, 8> Worklist;
265 
266   for (Loop *TopLevelLoop : *LI)
267     for (Loop *L : depth_first(TopLevelLoop))
268       // We only handle inner-most loops.
269       if (L->isInnermost())
270         Worklist.push_back(L);
271 
272   // Now walk the identified inner loops.
273   bool Changed = false;
274   for (Loop *L : Worklist) {
275     if (!L->isLoopSimplifyForm() || !L->isRotatedForm() ||
276         !L->getExitingBlock())
277       continue;
278     const LoopAccessInfo &LAI = GetLAA(*L);
279     if (!LAI.hasConvergentOp() &&
280         (LAI.getNumRuntimePointerChecks() ||
281          !LAI.getPSE().getPredicate().isAlwaysTrue())) {
282       LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
283                           LI, DT, SE);
284       LVer.versionLoop();
285       LVer.annotateLoopWithNoAlias();
286       Changed = true;
287     }
288   }
289 
290   return Changed;
291 }
292 
293 /// Also expose this is a pass.  Currently this is only used for
294 /// unit-testing.  It adds all memchecks necessary to remove all may-aliasing
295 /// array accesses from the loop.
296 class LoopVersioningLegacyPass : public FunctionPass {
297 public:
298   LoopVersioningLegacyPass() : FunctionPass(ID) {
299     initializeLoopVersioningLegacyPassPass(*PassRegistry::getPassRegistry());
300   }
301 
302   bool runOnFunction(Function &F) override {
303     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
304     auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
305       return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(&L);
306     };
307 
308     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
309     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
310 
311     return runImpl(LI, GetLAA, DT, SE);
312   }
313 
314   void getAnalysisUsage(AnalysisUsage &AU) const override {
315     AU.addRequired<LoopInfoWrapperPass>();
316     AU.addPreserved<LoopInfoWrapperPass>();
317     AU.addRequired<LoopAccessLegacyAnalysis>();
318     AU.addRequired<DominatorTreeWrapperPass>();
319     AU.addPreserved<DominatorTreeWrapperPass>();
320     AU.addRequired<ScalarEvolutionWrapperPass>();
321   }
322 
323   static char ID;
324 };
325 }
326 
327 #define LVER_OPTION "loop-versioning"
328 #define DEBUG_TYPE LVER_OPTION
329 
330 char LoopVersioningLegacyPass::ID;
331 static const char LVer_name[] = "Loop Versioning";
332 
333 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
334                       false)
335 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
336 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
337 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
338 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
339 INITIALIZE_PASS_END(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
340                     false)
341 
342 namespace llvm {
343 FunctionPass *createLoopVersioningLegacyPass() {
344   return new LoopVersioningLegacyPass();
345 }
346 
347 PreservedAnalyses LoopVersioningPass::run(Function &F,
348                                           FunctionAnalysisManager &AM) {
349   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
350   auto &LI = AM.getResult<LoopAnalysis>(F);
351   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
352   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
353   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
354   auto &AA = AM.getResult<AAManager>(F);
355   auto &AC = AM.getResult<AssumptionAnalysis>(F);
356 
357   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
358   auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
359     LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,      SE,
360                                       TLI, TTI, nullptr, nullptr, nullptr};
361     return LAM.getResult<LoopAccessAnalysis>(L, AR);
362   };
363 
364   if (runImpl(&LI, GetLAA, &DT, &SE))
365     return PreservedAnalyses::none();
366   return PreservedAnalyses::all();
367 }
368 } // namespace llvm
369