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/LoopAccessAnalysis.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/MemorySSA.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   MemorySSA *MSSA = EnableMSSALoopDependency
358                         ? &AM.getResult<MemorySSAAnalysis>(F).getMSSA()
359                         : nullptr;
360 
361   auto &LAM = AM.getResult<LoopAnalysisManagerFunctionProxy>(F).getManager();
362   auto GetLAA = [&](Loop &L) -> const LoopAccessInfo & {
363     LoopStandardAnalysisResults AR = {AA,  AC,  DT,      LI,  SE,
364                                       TLI, TTI, nullptr, MSSA};
365     return LAM.getResult<LoopAccessAnalysis>(L, AR);
366   };
367 
368   if (runImpl(&LI, GetLAA, &DT, &SE))
369     return PreservedAnalyses::none();
370   return PreservedAnalyses::all();
371 }
372 } // namespace llvm
373