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