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), NonVersionedLoop(nullptr),
45       AliasChecks(Checks.begin(), Checks.end()),
46       Preds(LAI.getPSE().getUnionPredicate()), LAI(LAI), LI(LI), DT(DT),
47       SE(SE) {
48 }
49 
50 void LoopVersioning::versionLoop(
51     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
52   assert(VersionedLoop->getUniqueExitBlock() && "No single exit block");
53   assert(VersionedLoop->isLoopSimplifyForm() &&
54          "Loop is not in loop-simplify form");
55 
56   Value *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   MemRuntimeCheck = addRuntimeChecks(RuntimeCheckBB->getTerminator(),
68                                      VersionedLoop, AliasChecks, Exp2);
69 
70   SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
71                    "scev.check");
72   SCEVRuntimeCheck =
73       Exp.expandCodeForPredicate(&Preds, RuntimeCheckBB->getTerminator());
74 
75   IRBuilder<InstSimplifyFolder> Builder(
76       RuntimeCheckBB->getContext(),
77       InstSimplifyFolder(RuntimeCheckBB->getModule()->getDataLayout()));
78   if (MemRuntimeCheck && SCEVRuntimeCheck) {
79     Builder.SetInsertPoint(RuntimeCheckBB->getTerminator());
80     RuntimeCheck =
81         Builder.CreateOr(MemRuntimeCheck, SCEVRuntimeCheck, "lver.safe");
82   } else
83     RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
84 
85   assert(RuntimeCheck && "called even though we don't need "
86                          "any runtime checks");
87 
88   // Rename the block to make the IR more readable.
89   RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
90                           ".lver.check");
91 
92   // Create empty preheader for the loop (and after cloning for the
93   // non-versioned loop).
94   BasicBlock *PH =
95       SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI,
96                  nullptr, VersionedLoop->getHeader()->getName() + ".ph");
97 
98   // Clone the loop including the preheader.
99   //
100   // FIXME: This does not currently preserve SimplifyLoop because the exit
101   // block is a join between the two loops.
102   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
103   NonVersionedLoop =
104       cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
105                              ".lver.orig", LI, DT, NonVersionedLoopBlocks);
106   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
107 
108   // Insert the conditional branch based on the result of the memchecks.
109   Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
110   Builder.SetInsertPoint(OrigTerm);
111   Builder.CreateCondBr(RuntimeCheck, NonVersionedLoop->getLoopPreheader(),
112                        VersionedLoop->getLoopPreheader());
113   OrigTerm->eraseFromParent();
114 
115   // The loops merge in the original exit block.  This is now dominated by the
116   // memchecking block.
117   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
118 
119   // Adds the necessary PHI nodes for the versioned loops based on the
120   // loop-defined values used outside of the loop.
121   addPHINodes(DefsUsedOutside);
122   formDedicatedExitBlocks(NonVersionedLoop, DT, LI, nullptr, true);
123   formDedicatedExitBlocks(VersionedLoop, DT, LI, nullptr, true);
124   assert(NonVersionedLoop->isLoopSimplifyForm() &&
125          VersionedLoop->isLoopSimplifyForm() &&
126          "The versioned loops should be in simplify form.");
127 }
128 
129 void LoopVersioning::addPHINodes(
130     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
131   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
132   assert(PHIBlock && "No single successor to loop exit block");
133   PHINode *PN;
134 
135   // First add a single-operand PHI for each DefsUsedOutside if one does not
136   // exists yet.
137   for (auto *Inst : DefsUsedOutside) {
138     // See if we have a single-operand PHI with the value defined by the
139     // original loop.
140     for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
141       if (PN->getIncomingValue(0) == Inst)
142         break;
143     }
144     // If not create it.
145     if (!PN) {
146       PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
147                            &PHIBlock->front());
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 (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, function_ref<const LoopAccessInfo &(Loop &)> GetLAA,
259              DominatorTree *DT, 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 = GetLAA(*L);
278     if (!LAI.hasConvergentOp() &&
279         (LAI.getNumRuntimePointerChecks() ||
280          !LAI.getPSE().getUnionPredicate().isAlwaysTrue())) {
281       LoopVersioning LVer(LAI, LAI.getRuntimePointerChecking()->getChecks(), L,
282                           LI, DT, SE);
283       LVer.versionLoop();
284       LVer.annotateLoopWithNoAlias();
285       Changed = true;
286     }
287   }
288 
289   return Changed;
290 }
291 
292 /// Also expose this is a pass.  Currently this is only used for
293 /// unit-testing.  It adds all memchecks necessary to remove all may-aliasing
294 /// array accesses from the loop.
295 class LoopVersioningLegacyPass : public FunctionPass {
296 public:
297   LoopVersioningLegacyPass() : FunctionPass(ID) {
298     initializeLoopVersioningLegacyPassPass(*PassRegistry::getPassRegistry());
299   }
300 
301   bool runOnFunction(Function &F) override {
302     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
303     auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
304       return getAnalysis<LoopAccessLegacyAnalysis>().getInfo(&L);
305     };
306 
307     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
308     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
309 
310     return runImpl(LI, GetLAA, DT, SE);
311   }
312 
313   void getAnalysisUsage(AnalysisUsage &AU) const override {
314     AU.addRequired<LoopInfoWrapperPass>();
315     AU.addPreserved<LoopInfoWrapperPass>();
316     AU.addRequired<LoopAccessLegacyAnalysis>();
317     AU.addRequired<DominatorTreeWrapperPass>();
318     AU.addPreserved<DominatorTreeWrapperPass>();
319     AU.addRequired<ScalarEvolutionWrapperPass>();
320   }
321 
322   static char ID;
323 };
324 }
325 
326 #define LVER_OPTION "loop-versioning"
327 #define DEBUG_TYPE LVER_OPTION
328 
329 char LoopVersioningLegacyPass::ID;
330 static const char LVer_name[] = "Loop Versioning";
331 
332 INITIALIZE_PASS_BEGIN(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
333                       false)
334 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
335 INITIALIZE_PASS_DEPENDENCY(LoopAccessLegacyAnalysis)
336 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
337 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
338 INITIALIZE_PASS_END(LoopVersioningLegacyPass, LVER_OPTION, LVer_name, false,
339                     false)
340 
341 namespace llvm {
342 FunctionPass *createLoopVersioningLegacyPass() {
343   return new LoopVersioningLegacyPass();
344 }
345 
346 PreservedAnalyses LoopVersioningPass::run(Function &F,
347                                           FunctionAnalysisManager &AM) {
348   auto &SE = AM.getResult<ScalarEvolutionAnalysis>(F);
349   auto &LI = AM.getResult<LoopAnalysis>(F);
350   auto &TTI = AM.getResult<TargetIRAnalysis>(F);
351   auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
352   auto &TLI = AM.getResult<TargetLibraryAnalysis>(F);
353   auto &AA = AM.getResult<AAManager>(F);
354   auto &AC = AM.getResult<AssumptionAnalysis>(F);
355 
356   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
357   auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
358     LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,      SE,
359                                       TLI, TTI, nullptr, nullptr, nullptr};
360     return LAM.getResult<LoopAccessAnalysis>(L, AR);
361   };
362 
363   if (runImpl(&LI, GetLAA, &DT, &SE))
364     return PreservedAnalyses::none();
365   return PreservedAnalyses::all();
366 }
367 } // namespace llvm
368