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