1 //===- LoopVersioning.cpp - Utility to version a loop ---------------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // This file defines a utility class to perform loop versioning.  The versioned
11 // loop speculates that otherwise may-aliasing memory accesses don't overlap and
12 // emits checks to prove this.
13 //
14 //===----------------------------------------------------------------------===//
15 
16 #include "llvm/Transforms/Utils/LoopVersioning.h"
17 #include "llvm/Analysis/LoopAccessAnalysis.h"
18 #include "llvm/Analysis/LoopInfo.h"
19 #include "llvm/Analysis/ScalarEvolutionExpander.h"
20 #include "llvm/IR/Dominators.h"
21 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
22 #include "llvm/Transforms/Utils/Cloning.h"
23 
24 using namespace llvm;
25 
26 LoopVersioning::LoopVersioning(const LoopAccessInfo &LAI, Loop *L, LoopInfo *LI,
27                                DominatorTree *DT, ScalarEvolution *SE,
28                                bool UseLAIChecks)
29     : VersionedLoop(L), NonVersionedLoop(nullptr), LAI(LAI), LI(LI), DT(DT),
30       SE(SE) {
31   assert(L->getExitBlock() && "No single exit block");
32   assert(L->getLoopPreheader() && "No preheader");
33   if (UseLAIChecks) {
34     setAliasChecks(LAI.getRuntimePointerChecking()->getChecks());
35     setSCEVChecks(LAI.PSE.getUnionPredicate());
36   }
37 }
38 
39 void LoopVersioning::setAliasChecks(
40     const SmallVector<RuntimePointerChecking::PointerCheck, 4> Checks) {
41   AliasChecks = std::move(Checks);
42 }
43 
44 void LoopVersioning::setSCEVChecks(SCEVUnionPredicate Check) {
45   Preds = std::move(Check);
46 }
47 
48 void LoopVersioning::versionLoop(
49     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
50   Instruction *FirstCheckInst;
51   Instruction *MemRuntimeCheck;
52   Value *SCEVRuntimeCheck;
53   Value *RuntimeCheck = nullptr;
54 
55   // Add the memcheck in the original preheader (this is empty initially).
56   BasicBlock *RuntimeCheckBB = VersionedLoop->getLoopPreheader();
57   std::tie(FirstCheckInst, MemRuntimeCheck) =
58       LAI.addRuntimeChecks(RuntimeCheckBB->getTerminator(), AliasChecks);
59   assert(MemRuntimeCheck && "called even though needsAnyChecking = false");
60 
61   const SCEVUnionPredicate &Pred = LAI.PSE.getUnionPredicate();
62   SCEVExpander Exp(*SE, RuntimeCheckBB->getModule()->getDataLayout(),
63                    "scev.check");
64   SCEVRuntimeCheck =
65       Exp.expandCodeForPredicate(&Pred, RuntimeCheckBB->getTerminator());
66   auto *CI = dyn_cast<ConstantInt>(SCEVRuntimeCheck);
67 
68   // Discard the SCEV runtime check if it is always true.
69   if (CI && CI->isZero())
70     SCEVRuntimeCheck = nullptr;
71 
72   if (MemRuntimeCheck && SCEVRuntimeCheck) {
73     RuntimeCheck = BinaryOperator::Create(Instruction::Or, MemRuntimeCheck,
74                                           SCEVRuntimeCheck, "ldist.safe");
75     if (auto *I = dyn_cast<Instruction>(RuntimeCheck))
76       I->insertBefore(RuntimeCheckBB->getTerminator());
77   } else
78     RuntimeCheck = MemRuntimeCheck ? MemRuntimeCheck : SCEVRuntimeCheck;
79 
80   assert(RuntimeCheck && "called even though we don't need "
81                          "any runtime checks");
82 
83   // Rename the block to make the IR more readable.
84   RuntimeCheckBB->setName(VersionedLoop->getHeader()->getName() +
85                           ".lver.check");
86 
87   // Create empty preheader for the loop (and after cloning for the
88   // non-versioned loop).
89   BasicBlock *PH =
90       SplitBlock(RuntimeCheckBB, RuntimeCheckBB->getTerminator(), DT, LI);
91   PH->setName(VersionedLoop->getHeader()->getName() + ".ph");
92 
93   // Clone the loop including the preheader.
94   //
95   // FIXME: This does not currently preserve SimplifyLoop because the exit
96   // block is a join between the two loops.
97   SmallVector<BasicBlock *, 8> NonVersionedLoopBlocks;
98   NonVersionedLoop =
99       cloneLoopWithPreheader(PH, RuntimeCheckBB, VersionedLoop, VMap,
100                              ".lver.orig", LI, DT, NonVersionedLoopBlocks);
101   remapInstructionsInBlocks(NonVersionedLoopBlocks, VMap);
102 
103   // Insert the conditional branch based on the result of the memchecks.
104   Instruction *OrigTerm = RuntimeCheckBB->getTerminator();
105   BranchInst::Create(NonVersionedLoop->getLoopPreheader(),
106                      VersionedLoop->getLoopPreheader(), RuntimeCheck, OrigTerm);
107   OrigTerm->eraseFromParent();
108 
109   // The loops merge in the original exit block.  This is now dominated by the
110   // memchecking block.
111   DT->changeImmediateDominator(VersionedLoop->getExitBlock(), RuntimeCheckBB);
112 
113   // Adds the necessary PHI nodes for the versioned loops based on the
114   // loop-defined values used outside of the loop.
115   addPHINodes(DefsUsedOutside);
116 }
117 
118 void LoopVersioning::addPHINodes(
119     const SmallVectorImpl<Instruction *> &DefsUsedOutside) {
120   BasicBlock *PHIBlock = VersionedLoop->getExitBlock();
121   assert(PHIBlock && "No single successor to loop exit block");
122 
123   for (auto *Inst : DefsUsedOutside) {
124     auto *NonVersionedLoopInst = cast<Instruction>(VMap[Inst]);
125     PHINode *PN;
126 
127     // First see if we have a single-operand PHI with the value defined by the
128     // original loop.
129     for (auto I = PHIBlock->begin(); (PN = dyn_cast<PHINode>(I)); ++I) {
130       assert(PN->getNumOperands() == 1 &&
131              "Exit block should only have on predecessor");
132       if (PN->getIncomingValue(0) == Inst)
133         break;
134     }
135     // If not create it.
136     if (!PN) {
137       PN = PHINode::Create(Inst->getType(), 2, Inst->getName() + ".lver",
138                            &PHIBlock->front());
139       for (auto *User : Inst->users())
140         if (!VersionedLoop->contains(cast<Instruction>(User)->getParent()))
141           User->replaceUsesOfWith(Inst, PN);
142       PN->addIncoming(Inst, VersionedLoop->getExitingBlock());
143     }
144     // Add the new incoming value from the non-versioned loop.
145     PN->addIncoming(NonVersionedLoopInst, NonVersionedLoop->getExitingBlock());
146   }
147 }
148 
149 namespace {
150 /// \brief Also expose this is a pass.  Currently this is only used for
151 /// unit-testing.  It adds all memchecks necessary to remove all may-aliasing
152 /// array accesses from the loop.
153 class LoopVersioningPass : public FunctionPass {
154 public:
155   LoopVersioningPass() : FunctionPass(ID) {
156     initializeLoopVersioningPassPass(*PassRegistry::getPassRegistry());
157   }
158 
159   bool runOnFunction(Function &F) override {
160     auto *LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
161     auto *LAA = &getAnalysis<LoopAccessAnalysis>();
162     auto *DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
163     auto *SE = &getAnalysis<ScalarEvolutionWrapperPass>().getSE();
164 
165     // Build up a worklist of inner-loops to version. This is necessary as the
166     // act of versioning a loop creates new loops and can invalidate iterators
167     // across the loops.
168     SmallVector<Loop *, 8> Worklist;
169 
170     for (Loop *TopLevelLoop : *LI)
171       for (Loop *L : depth_first(TopLevelLoop))
172         // We only handle inner-most loops.
173         if (L->empty())
174           Worklist.push_back(L);
175 
176     // Now walk the identified inner loops.
177     bool Changed = false;
178     for (Loop *L : Worklist) {
179       const LoopAccessInfo &LAI = LAA->getInfo(L, ValueToValueMap());
180       if (LAI.getNumRuntimePointerChecks() ||
181           !LAI.PSE.getUnionPredicate().isAlwaysTrue()) {
182         LoopVersioning LVer(LAI, L, LI, DT, SE);
183         LVer.versionLoop();
184         Changed = true;
185       }
186     }
187 
188     return Changed;
189   }
190 
191   void getAnalysisUsage(AnalysisUsage &AU) const override {
192     AU.addRequired<LoopInfoWrapperPass>();
193     AU.addPreserved<LoopInfoWrapperPass>();
194     AU.addRequired<LoopAccessAnalysis>();
195     AU.addRequired<DominatorTreeWrapperPass>();
196     AU.addPreserved<DominatorTreeWrapperPass>();
197     AU.addRequired<ScalarEvolutionWrapperPass>();
198   }
199 
200   static char ID;
201 };
202 }
203 
204 #define LVER_OPTION "loop-versioning"
205 #define DEBUG_TYPE LVER_OPTION
206 
207 char LoopVersioningPass::ID;
208 static const char LVer_name[] = "Loop Versioning";
209 
210 INITIALIZE_PASS_BEGIN(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
211 INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
212 INITIALIZE_PASS_DEPENDENCY(LoopAccessAnalysis)
213 INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
214 INITIALIZE_PASS_DEPENDENCY(ScalarEvolutionWrapperPass)
215 INITIALIZE_PASS_END(LoopVersioningPass, LVER_OPTION, LVer_name, false, false)
216 
217 namespace llvm {
218 FunctionPass *createLoopVersioningPass() {
219   return new LoopVersioningPass();
220 }
221 }
222