• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 //===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
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 pass performs loop invariant code motion, attempting to remove as much
11 // code from the body of a loop as possible.  It does this by either hoisting
12 // code into the preheader block, or by sinking code to the exit blocks if it is
13 // safe.  This pass also promotes must-aliased memory locations in the loop to
14 // live in registers, thus hoisting and sinking "invariant" loads and stores.
15 //
16 // This pass uses alias analysis for two purposes:
17 //
18 //  1. Moving loop invariant loads and calls out of loops.  If we can determine
19 //     that a load or call inside of a loop never aliases anything stored to,
20 //     we can hoist it or sink it like any other instruction.
21 //  2. Scalar Promotion of Memory - If there is a store instruction inside of
22 //     the loop, we try to move the store to happen AFTER the loop instead of
23 //     inside of the loop.  This can only happen if a few conditions are true:
24 //       A. The pointer stored through is loop invariant
25 //       B. There are no stores or loads in the loop which _may_ alias the
26 //          pointer.  There are no calls in the loop which mod/ref the pointer.
27 //     If these conditions are true, we can promote the loads and stores in the
28 //     loop of the pointer to use a temporary alloca'd variable.  We then use
29 //     the SSAUpdater to construct the appropriate SSA form for the value.
30 //
31 //===----------------------------------------------------------------------===//
32 
33 #include "llvm/Transforms/Scalar/LICM.h"
34 #include "llvm/ADT/Statistic.h"
35 #include "llvm/Analysis/AliasAnalysis.h"
36 #include "llvm/Analysis/AliasSetTracker.h"
37 #include "llvm/Analysis/BasicAliasAnalysis.h"
38 #include "llvm/Analysis/CaptureTracking.h"
39 #include "llvm/Analysis/ConstantFolding.h"
40 #include "llvm/Analysis/GlobalsModRef.h"
41 #include "llvm/Analysis/Loads.h"
42 #include "llvm/Analysis/LoopInfo.h"
43 #include "llvm/Analysis/LoopPass.h"
44 #include "llvm/Analysis/LoopPassManager.h"
45 #include "llvm/Analysis/MemoryBuiltins.h"
46 #include "llvm/Analysis/ScalarEvolution.h"
47 #include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
48 #include "llvm/Analysis/TargetLibraryInfo.h"
49 #include "llvm/Analysis/ValueTracking.h"
50 #include "llvm/IR/CFG.h"
51 #include "llvm/IR/Constants.h"
52 #include "llvm/IR/DataLayout.h"
53 #include "llvm/IR/DerivedTypes.h"
54 #include "llvm/IR/Dominators.h"
55 #include "llvm/IR/Instructions.h"
56 #include "llvm/IR/IntrinsicInst.h"
57 #include "llvm/IR/LLVMContext.h"
58 #include "llvm/IR/Metadata.h"
59 #include "llvm/IR/PredIteratorCache.h"
60 #include "llvm/Support/CommandLine.h"
61 #include "llvm/Support/Debug.h"
62 #include "llvm/Support/raw_ostream.h"
63 #include "llvm/Transforms/Scalar.h"
64 #include "llvm/Transforms/Utils/Local.h"
65 #include "llvm/Transforms/Utils/LoopUtils.h"
66 #include "llvm/Transforms/Utils/SSAUpdater.h"
67 #include <algorithm>
68 #include <utility>
69 using namespace llvm;
70 
71 #define DEBUG_TYPE "licm"
72 
73 STATISTIC(NumSunk, "Number of instructions sunk out of loop");
74 STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
75 STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
76 STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
77 STATISTIC(NumPromoted, "Number of memory locations promoted to registers");
78 
79 static cl::opt<bool>
80     DisablePromotion("disable-licm-promotion", cl::Hidden,
81                      cl::desc("Disable memory promotion in LICM pass"));
82 
83 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
84 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
85                             const LoopSafetyInfo *SafetyInfo);
86 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
87                   const LoopSafetyInfo *SafetyInfo);
88 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
89                  const Loop *CurLoop, AliasSetTracker *CurAST,
90                  const LoopSafetyInfo *SafetyInfo);
91 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
92                                            const DominatorTree *DT,
93                                            const Loop *CurLoop,
94                                            const LoopSafetyInfo *SafetyInfo,
95                                            const Instruction *CtxI = nullptr);
96 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
97                                      const AAMDNodes &AAInfo,
98                                      AliasSetTracker *CurAST);
99 static Instruction *
100 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
101                             const LoopInfo *LI,
102                             const LoopSafetyInfo *SafetyInfo);
103 static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
104                                DominatorTree *DT, TargetLibraryInfo *TLI,
105                                Loop *CurLoop, AliasSetTracker *CurAST,
106                                LoopSafetyInfo *SafetyInfo);
107 
108 namespace {
109 struct LoopInvariantCodeMotion {
110   bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
111                  TargetLibraryInfo *TLI, ScalarEvolution *SE, bool DeleteAST);
112 
getLoopToAliasSetMap__anon8d593ef90111::LoopInvariantCodeMotion113   DenseMap<Loop *, AliasSetTracker *> &getLoopToAliasSetMap() {
114     return LoopToAliasSetMap;
115   }
116 
117 private:
118   DenseMap<Loop *, AliasSetTracker *> LoopToAliasSetMap;
119 
120   AliasSetTracker *collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
121                                            AliasAnalysis *AA);
122 };
123 
124 struct LegacyLICMPass : public LoopPass {
125   static char ID; // Pass identification, replacement for typeid
LegacyLICMPass__anon8d593ef90111::LegacyLICMPass126   LegacyLICMPass() : LoopPass(ID) {
127     initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());
128   }
129 
runOnLoop__anon8d593ef90111::LegacyLICMPass130   bool runOnLoop(Loop *L, LPPassManager &LPM) override {
131     if (skipLoop(L))
132       return false;
133 
134     auto *SE = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
135     return LICM.runOnLoop(L,
136                           &getAnalysis<AAResultsWrapperPass>().getAAResults(),
137                           &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(),
138                           &getAnalysis<DominatorTreeWrapperPass>().getDomTree(),
139                           &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI(),
140                           SE ? &SE->getSE() : nullptr, false);
141   }
142 
143   /// This transformation requires natural loop information & requires that
144   /// loop preheaders be inserted into the CFG...
145   ///
getAnalysisUsage__anon8d593ef90111::LegacyLICMPass146   void getAnalysisUsage(AnalysisUsage &AU) const override {
147     AU.setPreservesCFG();
148     AU.addRequired<TargetLibraryInfoWrapperPass>();
149     getLoopAnalysisUsage(AU);
150   }
151 
152   using llvm::Pass::doFinalization;
153 
doFinalization__anon8d593ef90111::LegacyLICMPass154   bool doFinalization() override {
155     assert(LICM.getLoopToAliasSetMap().empty() &&
156            "Didn't free loop alias sets");
157     return false;
158   }
159 
160 private:
161   LoopInvariantCodeMotion LICM;
162 
163   /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
164   void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
165                                Loop *L) override;
166 
167   /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
168   /// set.
169   void deleteAnalysisValue(Value *V, Loop *L) override;
170 
171   /// Simple Analysis hook. Delete loop L from alias set map.
172   void deleteAnalysisLoop(Loop *L) override;
173 };
174 }
175 
run(Loop & L,AnalysisManager<Loop> & AM)176 PreservedAnalyses LICMPass::run(Loop &L, AnalysisManager<Loop> &AM) {
177   const auto &FAM =
178       AM.getResult<FunctionAnalysisManagerLoopProxy>(L).getManager();
179   Function *F = L.getHeader()->getParent();
180 
181   auto *AA = FAM.getCachedResult<AAManager>(*F);
182   auto *LI = FAM.getCachedResult<LoopAnalysis>(*F);
183   auto *DT = FAM.getCachedResult<DominatorTreeAnalysis>(*F);
184   auto *TLI = FAM.getCachedResult<TargetLibraryAnalysis>(*F);
185   auto *SE = FAM.getCachedResult<ScalarEvolutionAnalysis>(*F);
186   assert((AA && LI && DT && TLI && SE) && "Analyses for LICM not available");
187 
188   LoopInvariantCodeMotion LICM;
189 
190   if (!LICM.runOnLoop(&L, AA, LI, DT, TLI, SE, true))
191     return PreservedAnalyses::all();
192 
193   // FIXME: There is no setPreservesCFG in the new PM. When that becomes
194   // available, it should be used here.
195   return getLoopPassPreservedAnalyses();
196 }
197 
198 char LegacyLICMPass::ID = 0;
199 INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
200                       false, false)
INITIALIZE_PASS_DEPENDENCY(LoopPass)201 INITIALIZE_PASS_DEPENDENCY(LoopPass)
202 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
203 INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
204                     false)
205 
206 Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
207 
208 /// Hoist expressions out of the specified loop. Note, alias info for inner
209 /// loop is not preserved so it is not a good idea to run LICM multiple
210 /// times on one loop.
211 /// We should delete AST for inner loops in the new pass manager to avoid
212 /// memory leak.
213 ///
runOnLoop(Loop * L,AliasAnalysis * AA,LoopInfo * LI,DominatorTree * DT,TargetLibraryInfo * TLI,ScalarEvolution * SE,bool DeleteAST)214 bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA,
215                                         LoopInfo *LI, DominatorTree *DT,
216                                         TargetLibraryInfo *TLI,
217                                         ScalarEvolution *SE, bool DeleteAST) {
218   bool Changed = false;
219 
220   assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
221 
222   AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA);
223 
224   // Get the preheader block to move instructions into...
225   BasicBlock *Preheader = L->getLoopPreheader();
226 
227   // Compute loop safety information.
228   LoopSafetyInfo SafetyInfo;
229   computeLoopSafetyInfo(&SafetyInfo, L);
230 
231   // We want to visit all of the instructions in this loop... that are not parts
232   // of our subloops (they have already had their invariants hoisted out of
233   // their loop, into this loop, so there is no need to process the BODIES of
234   // the subloops).
235   //
236   // Traverse the body of the loop in depth first order on the dominator tree so
237   // that we are guaranteed to see definitions before we see uses.  This allows
238   // us to sink instructions in one pass, without iteration.  After sinking
239   // instructions, we perform another pass to hoist them out of the loop.
240   //
241   if (L->hasDedicatedExits())
242     Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
243                           CurAST, &SafetyInfo);
244   if (Preheader)
245     Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
246                            CurAST, &SafetyInfo);
247 
248   // Now that all loop invariants have been removed from the loop, promote any
249   // memory references to scalars that we can.
250   if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
251     SmallVector<BasicBlock *, 8> ExitBlocks;
252     SmallVector<Instruction *, 8> InsertPts;
253     PredIteratorCache PIC;
254 
255     // Loop over all of the alias sets in the tracker object.
256     for (AliasSet &AS : *CurAST)
257       Changed |= promoteLoopAccessesToScalars(
258           AS, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L, CurAST, &SafetyInfo);
259 
260     // Once we have promoted values across the loop body we have to recursively
261     // reform LCSSA as any nested loop may now have values defined within the
262     // loop used in the outer loop.
263     // FIXME: This is really heavy handed. It would be a bit better to use an
264     // SSAUpdater strategy during promotion that was LCSSA aware and reformed
265     // it as it went.
266     if (Changed) {
267       formLCSSARecursively(*L, *DT, LI, SE);
268     }
269   }
270 
271   // Check that neither this loop nor its parent have had LCSSA broken. LICM is
272   // specifically moving instructions across the loop boundary and so it is
273   // especially in need of sanity checking here.
274   assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
275   assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
276          "Parent loop not left in LCSSA form after LICM!");
277 
278   // If this loop is nested inside of another one, save the alias information
279   // for when we process the outer loop.
280   if (L->getParentLoop() && !DeleteAST)
281     LoopToAliasSetMap[L] = CurAST;
282   else
283     delete CurAST;
284 
285   if (Changed && SE)
286     SE->forgetLoopDispositions(L);
287   return Changed;
288 }
289 
290 /// Walk the specified region of the CFG (defined by all blocks dominated by
291 /// the specified block, and that are in the current loop) in reverse depth
292 /// first order w.r.t the DominatorTree.  This allows us to visit uses before
293 /// definitions, allowing us to sink a loop body in one pass without iteration.
294 ///
sinkRegion(DomTreeNode * N,AliasAnalysis * AA,LoopInfo * LI,DominatorTree * DT,TargetLibraryInfo * TLI,Loop * CurLoop,AliasSetTracker * CurAST,LoopSafetyInfo * SafetyInfo)295 bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
296                       DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
297                       AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
298 
299   // Verify inputs.
300   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
301          CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
302          "Unexpected input to sinkRegion");
303 
304   BasicBlock *BB = N->getBlock();
305   // If this subregion is not in the top level loop at all, exit.
306   if (!CurLoop->contains(BB))
307     return false;
308 
309   // We are processing blocks in reverse dfo, so process children first.
310   bool Changed = false;
311   const std::vector<DomTreeNode *> &Children = N->getChildren();
312   for (DomTreeNode *Child : Children)
313     Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
314 
315   // Only need to process the contents of this block if it is not part of a
316   // subloop (which would already have been processed).
317   if (inSubLoop(BB, CurLoop, LI))
318     return Changed;
319 
320   for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
321     Instruction &I = *--II;
322 
323     // If the instruction is dead, we would try to sink it because it isn't used
324     // in the loop, instead, just delete it.
325     if (isInstructionTriviallyDead(&I, TLI)) {
326       DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
327       ++II;
328       CurAST->deleteValue(&I);
329       I.eraseFromParent();
330       Changed = true;
331       continue;
332     }
333 
334     // Check to see if we can sink this instruction to the exit blocks
335     // of the loop.  We can do this if the all users of the instruction are
336     // outside of the loop.  In this case, it doesn't even matter if the
337     // operands of the instruction are loop invariant.
338     //
339     if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
340         canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
341       ++II;
342       Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo);
343     }
344   }
345   return Changed;
346 }
347 
348 /// Walk the specified region of the CFG (defined by all blocks dominated by
349 /// the specified block, and that are in the current loop) in depth first
350 /// order w.r.t the DominatorTree.  This allows us to visit definitions before
351 /// uses, allowing us to hoist a loop body in one pass without iteration.
352 ///
hoistRegion(DomTreeNode * N,AliasAnalysis * AA,LoopInfo * LI,DominatorTree * DT,TargetLibraryInfo * TLI,Loop * CurLoop,AliasSetTracker * CurAST,LoopSafetyInfo * SafetyInfo)353 bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
354                        DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
355                        AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
356   // Verify inputs.
357   assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
358          CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
359          "Unexpected input to hoistRegion");
360 
361   BasicBlock *BB = N->getBlock();
362 
363   // If this subregion is not in the top level loop at all, exit.
364   if (!CurLoop->contains(BB))
365     return false;
366 
367   // Only need to process the contents of this block if it is not part of a
368   // subloop (which would already have been processed).
369   bool Changed = false;
370   if (!inSubLoop(BB, CurLoop, LI))
371     for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
372       Instruction &I = *II++;
373       // Try constant folding this instruction.  If all the operands are
374       // constants, it is technically hoistable, but it would be better to just
375       // fold it.
376       if (Constant *C = ConstantFoldInstruction(
377               &I, I.getModule()->getDataLayout(), TLI)) {
378         DEBUG(dbgs() << "LICM folding inst: " << I << "  --> " << *C << '\n');
379         CurAST->copyValue(&I, C);
380         CurAST->deleteValue(&I);
381         I.replaceAllUsesWith(C);
382         I.eraseFromParent();
383         continue;
384       }
385 
386       // Try hoisting the instruction out to the preheader.  We can only do this
387       // if all of the operands of the instruction are loop invariant and if it
388       // is safe to hoist the instruction.
389       //
390       if (CurLoop->hasLoopInvariantOperands(&I) &&
391           canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
392           isSafeToExecuteUnconditionally(
393               I, DT, CurLoop, SafetyInfo,
394               CurLoop->getLoopPreheader()->getTerminator()))
395         Changed |= hoist(I, DT, CurLoop, SafetyInfo);
396     }
397 
398   const std::vector<DomTreeNode *> &Children = N->getChildren();
399   for (DomTreeNode *Child : Children)
400     Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
401   return Changed;
402 }
403 
404 /// Computes loop safety information, checks loop body & header
405 /// for the possibility of may throw exception.
406 ///
computeLoopSafetyInfo(LoopSafetyInfo * SafetyInfo,Loop * CurLoop)407 void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
408   assert(CurLoop != nullptr && "CurLoop cant be null");
409   BasicBlock *Header = CurLoop->getHeader();
410   // Setting default safety values.
411   SafetyInfo->MayThrow = false;
412   SafetyInfo->HeaderMayThrow = false;
413   // Iterate over header and compute safety info.
414   for (BasicBlock::iterator I = Header->begin(), E = Header->end();
415        (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
416     SafetyInfo->HeaderMayThrow |=
417         !isGuaranteedToTransferExecutionToSuccessor(&*I);
418 
419   SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
420   // Iterate over loop instructions and compute safety info.
421   for (Loop::block_iterator BB = CurLoop->block_begin(),
422                             BBE = CurLoop->block_end();
423        (BB != BBE) && !SafetyInfo->MayThrow; ++BB)
424     for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
425          (I != E) && !SafetyInfo->MayThrow; ++I)
426       SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I);
427 
428   // Compute funclet colors if we might sink/hoist in a function with a funclet
429   // personality routine.
430   Function *Fn = CurLoop->getHeader()->getParent();
431   if (Fn->hasPersonalityFn())
432     if (Constant *PersonalityFn = Fn->getPersonalityFn())
433       if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
434         SafetyInfo->BlockColors = colorEHFunclets(*Fn);
435 }
436 
437 /// canSinkOrHoistInst - Return true if the hoister and sinker can handle this
438 /// instruction.
439 ///
canSinkOrHoistInst(Instruction & I,AliasAnalysis * AA,DominatorTree * DT,TargetLibraryInfo * TLI,Loop * CurLoop,AliasSetTracker * CurAST,LoopSafetyInfo * SafetyInfo)440 bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT,
441                         TargetLibraryInfo *TLI, Loop *CurLoop,
442                         AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
443   // Loads have extra constraints we have to verify before we can hoist them.
444   if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
445     if (!LI->isUnordered())
446       return false; // Don't hoist volatile/atomic loads!
447 
448     // Loads from constant memory are always safe to move, even if they end up
449     // in the same alias set as something that ends up being modified.
450     if (AA->pointsToConstantMemory(LI->getOperand(0)))
451       return true;
452     if (LI->getMetadata(LLVMContext::MD_invariant_load))
453       return true;
454 
455     // Don't hoist loads which have may-aliased stores in loop.
456     uint64_t Size = 0;
457     if (LI->getType()->isSized())
458       Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
459 
460     AAMDNodes AAInfo;
461     LI->getAAMetadata(AAInfo);
462 
463     return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
464   } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
465     // Don't sink or hoist dbg info; it's legal, but not useful.
466     if (isa<DbgInfoIntrinsic>(I))
467       return false;
468 
469     // Don't sink calls which can throw.
470     if (CI->mayThrow())
471       return false;
472 
473     // Handle simple cases by querying alias analysis.
474     FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
475     if (Behavior == FMRB_DoesNotAccessMemory)
476       return true;
477     if (AliasAnalysis::onlyReadsMemory(Behavior)) {
478       // A readonly argmemonly function only reads from memory pointed to by
479       // it's arguments with arbitrary offsets.  If we can prove there are no
480       // writes to this memory in the loop, we can hoist or sink.
481       if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
482         for (Value *Op : CI->arg_operands())
483           if (Op->getType()->isPointerTy() &&
484               pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize,
485                                        AAMDNodes(), CurAST))
486             return false;
487         return true;
488       }
489       // If this call only reads from memory and there are no writes to memory
490       // in the loop, we can hoist or sink the call as appropriate.
491       bool FoundMod = false;
492       for (AliasSet &AS : *CurAST) {
493         if (!AS.isForwardingAliasSet() && AS.isMod()) {
494           FoundMod = true;
495           break;
496         }
497       }
498       if (!FoundMod)
499         return true;
500     }
501 
502     // FIXME: This should use mod/ref information to see if we can hoist or
503     // sink the call.
504 
505     return false;
506   }
507 
508   // Only these instructions are hoistable/sinkable.
509   if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
510       !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
511       !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
512       !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
513       !isa<InsertValueInst>(I))
514     return false;
515 
516   // TODO: Plumb the context instruction through to make hoisting and sinking
517   // more powerful. Hoisting of loads already works due to the special casing
518   // above.
519   return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr);
520 }
521 
522 /// Returns true if a PHINode is a trivially replaceable with an
523 /// Instruction.
524 /// This is true when all incoming values are that instruction.
525 /// This pattern occurs most often with LCSSA PHI nodes.
526 ///
isTriviallyReplacablePHI(const PHINode & PN,const Instruction & I)527 static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
528   for (const Value *IncValue : PN.incoming_values())
529     if (IncValue != &I)
530       return false;
531 
532   return true;
533 }
534 
535 /// Return true if the only users of this instruction are outside of
536 /// the loop. If this is true, we can sink the instruction to the exit
537 /// blocks of the loop.
538 ///
isNotUsedInLoop(const Instruction & I,const Loop * CurLoop,const LoopSafetyInfo * SafetyInfo)539 static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
540                             const LoopSafetyInfo *SafetyInfo) {
541   const auto &BlockColors = SafetyInfo->BlockColors;
542   for (const User *U : I.users()) {
543     const Instruction *UI = cast<Instruction>(U);
544     if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
545       const BasicBlock *BB = PN->getParent();
546       // We cannot sink uses in catchswitches.
547       if (isa<CatchSwitchInst>(BB->getTerminator()))
548         return false;
549 
550       // We need to sink a callsite to a unique funclet.  Avoid sinking if the
551       // phi use is too muddled.
552       if (isa<CallInst>(I))
553         if (!BlockColors.empty() &&
554             BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
555           return false;
556 
557       // A PHI node where all of the incoming values are this instruction are
558       // special -- they can just be RAUW'ed with the instruction and thus
559       // don't require a use in the predecessor. This is a particular important
560       // special case because it is the pattern found in LCSSA form.
561       if (isTriviallyReplacablePHI(*PN, I)) {
562         if (CurLoop->contains(PN))
563           return false;
564         else
565           continue;
566       }
567 
568       // Otherwise, PHI node uses occur in predecessor blocks if the incoming
569       // values. Check for such a use being inside the loop.
570       for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
571         if (PN->getIncomingValue(i) == &I)
572           if (CurLoop->contains(PN->getIncomingBlock(i)))
573             return false;
574 
575       continue;
576     }
577 
578     if (CurLoop->contains(UI))
579       return false;
580   }
581   return true;
582 }
583 
584 static Instruction *
CloneInstructionInExitBlock(Instruction & I,BasicBlock & ExitBlock,PHINode & PN,const LoopInfo * LI,const LoopSafetyInfo * SafetyInfo)585 CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
586                             const LoopInfo *LI,
587                             const LoopSafetyInfo *SafetyInfo) {
588   Instruction *New;
589   if (auto *CI = dyn_cast<CallInst>(&I)) {
590     const auto &BlockColors = SafetyInfo->BlockColors;
591 
592     // Sinking call-sites need to be handled differently from other
593     // instructions.  The cloned call-site needs a funclet bundle operand
594     // appropriate for it's location in the CFG.
595     SmallVector<OperandBundleDef, 1> OpBundles;
596     for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
597          BundleIdx != BundleEnd; ++BundleIdx) {
598       OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
599       if (Bundle.getTagID() == LLVMContext::OB_funclet)
600         continue;
601 
602       OpBundles.emplace_back(Bundle);
603     }
604 
605     if (!BlockColors.empty()) {
606       const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
607       assert(CV.size() == 1 && "non-unique color for exit block!");
608       BasicBlock *BBColor = CV.front();
609       Instruction *EHPad = BBColor->getFirstNonPHI();
610       if (EHPad->isEHPad())
611         OpBundles.emplace_back("funclet", EHPad);
612     }
613 
614     New = CallInst::Create(CI, OpBundles);
615   } else {
616     New = I.clone();
617   }
618 
619   ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
620   if (!I.getName().empty())
621     New->setName(I.getName() + ".le");
622 
623   // Build LCSSA PHI nodes for any in-loop operands. Note that this is
624   // particularly cheap because we can rip off the PHI node that we're
625   // replacing for the number and blocks of the predecessors.
626   // OPT: If this shows up in a profile, we can instead finish sinking all
627   // invariant instructions, and then walk their operands to re-establish
628   // LCSSA. That will eliminate creating PHI nodes just to nuke them when
629   // sinking bottom-up.
630   for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
631        ++OI)
632     if (Instruction *OInst = dyn_cast<Instruction>(*OI))
633       if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
634         if (!OLoop->contains(&PN)) {
635           PHINode *OpPN =
636               PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
637                               OInst->getName() + ".lcssa", &ExitBlock.front());
638           for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
639             OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
640           *OI = OpPN;
641         }
642   return New;
643 }
644 
645 /// When an instruction is found to only be used outside of the loop, this
646 /// function moves it to the exit blocks and patches up SSA form as needed.
647 /// This method is guaranteed to remove the original instruction from its
648 /// position, and may either delete it or move it to outside of the loop.
649 ///
sink(Instruction & I,const LoopInfo * LI,const DominatorTree * DT,const Loop * CurLoop,AliasSetTracker * CurAST,const LoopSafetyInfo * SafetyInfo)650 static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
651                  const Loop *CurLoop, AliasSetTracker *CurAST,
652                  const LoopSafetyInfo *SafetyInfo) {
653   DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
654   bool Changed = false;
655   if (isa<LoadInst>(I))
656     ++NumMovedLoads;
657   else if (isa<CallInst>(I))
658     ++NumMovedCalls;
659   ++NumSunk;
660   Changed = true;
661 
662 #ifndef NDEBUG
663   SmallVector<BasicBlock *, 32> ExitBlocks;
664   CurLoop->getUniqueExitBlocks(ExitBlocks);
665   SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
666                                              ExitBlocks.end());
667 #endif
668 
669   // Clones of this instruction. Don't create more than one per exit block!
670   SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
671 
672   // If this instruction is only used outside of the loop, then all users are
673   // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
674   // the instruction.
675   while (!I.use_empty()) {
676     Value::user_iterator UI = I.user_begin();
677     auto *User = cast<Instruction>(*UI);
678     if (!DT->isReachableFromEntry(User->getParent())) {
679       User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
680       continue;
681     }
682     // The user must be a PHI node.
683     PHINode *PN = cast<PHINode>(User);
684 
685     // Surprisingly, instructions can be used outside of loops without any
686     // exits.  This can only happen in PHI nodes if the incoming block is
687     // unreachable.
688     Use &U = UI.getUse();
689     BasicBlock *BB = PN->getIncomingBlock(U);
690     if (!DT->isReachableFromEntry(BB)) {
691       U = UndefValue::get(I.getType());
692       continue;
693     }
694 
695     BasicBlock *ExitBlock = PN->getParent();
696     assert(ExitBlockSet.count(ExitBlock) &&
697            "The LCSSA PHI is not in an exit block!");
698 
699     Instruction *New;
700     auto It = SunkCopies.find(ExitBlock);
701     if (It != SunkCopies.end())
702       New = It->second;
703     else
704       New = SunkCopies[ExitBlock] =
705           CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
706 
707     PN->replaceAllUsesWith(New);
708     PN->eraseFromParent();
709   }
710 
711   CurAST->deleteValue(&I);
712   I.eraseFromParent();
713   return Changed;
714 }
715 
716 /// When an instruction is found to only use loop invariant operands that
717 /// is safe to hoist, this instruction is called to do the dirty work.
718 ///
hoist(Instruction & I,const DominatorTree * DT,const Loop * CurLoop,const LoopSafetyInfo * SafetyInfo)719 static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
720                   const LoopSafetyInfo *SafetyInfo) {
721   auto *Preheader = CurLoop->getLoopPreheader();
722   DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
723                << "\n");
724 
725   // Metadata can be dependent on conditions we are hoisting above.
726   // Conservatively strip all metadata on the instruction unless we were
727   // guaranteed to execute I if we entered the loop, in which case the metadata
728   // is valid in the loop preheader.
729   if (I.hasMetadataOtherThanDebugLoc() &&
730       // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
731       // time in isGuaranteedToExecute if we don't actually have anything to
732       // drop.  It is a compile time optimization, not required for correctness.
733       !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
734     I.dropUnknownNonDebugMetadata();
735 
736   // Move the new node to the Preheader, before its terminator.
737   I.moveBefore(Preheader->getTerminator());
738 
739   if (isa<LoadInst>(I))
740     ++NumMovedLoads;
741   else if (isa<CallInst>(I))
742     ++NumMovedCalls;
743   ++NumHoisted;
744   return true;
745 }
746 
747 /// Only sink or hoist an instruction if it is not a trapping instruction,
748 /// or if the instruction is known not to trap when moved to the preheader.
749 /// or if it is a trapping instruction and is guaranteed to execute.
isSafeToExecuteUnconditionally(const Instruction & Inst,const DominatorTree * DT,const Loop * CurLoop,const LoopSafetyInfo * SafetyInfo,const Instruction * CtxI)750 static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
751                                            const DominatorTree *DT,
752                                            const Loop *CurLoop,
753                                            const LoopSafetyInfo *SafetyInfo,
754                                            const Instruction *CtxI) {
755   if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
756     return true;
757 
758   return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
759 }
760 
761 namespace {
762 class LoopPromoter : public LoadAndStorePromoter {
763   Value *SomePtr; // Designated pointer to store to.
764   SmallPtrSetImpl<Value *> &PointerMustAliases;
765   SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
766   SmallVectorImpl<Instruction *> &LoopInsertPts;
767   PredIteratorCache &PredCache;
768   AliasSetTracker &AST;
769   LoopInfo &LI;
770   DebugLoc DL;
771   int Alignment;
772   AAMDNodes AATags;
773 
maybeInsertLCSSAPHI(Value * V,BasicBlock * BB) const774   Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
775     if (Instruction *I = dyn_cast<Instruction>(V))
776       if (Loop *L = LI.getLoopFor(I->getParent()))
777         if (!L->contains(BB)) {
778           // We need to create an LCSSA PHI node for the incoming value and
779           // store that.
780           PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
781                                         I->getName() + ".lcssa", &BB->front());
782           for (BasicBlock *Pred : PredCache.get(BB))
783             PN->addIncoming(I, Pred);
784           return PN;
785         }
786     return V;
787   }
788 
789 public:
LoopPromoter(Value * SP,ArrayRef<const Instruction * > Insts,SSAUpdater & S,SmallPtrSetImpl<Value * > & PMA,SmallVectorImpl<BasicBlock * > & LEB,SmallVectorImpl<Instruction * > & LIP,PredIteratorCache & PIC,AliasSetTracker & ast,LoopInfo & li,DebugLoc dl,int alignment,const AAMDNodes & AATags)790   LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
791                SmallPtrSetImpl<Value *> &PMA,
792                SmallVectorImpl<BasicBlock *> &LEB,
793                SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
794                AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
795                const AAMDNodes &AATags)
796       : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
797         LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
798         LI(li), DL(std::move(dl)), Alignment(alignment), AATags(AATags) {}
799 
isInstInList(Instruction * I,const SmallVectorImpl<Instruction * > &) const800   bool isInstInList(Instruction *I,
801                     const SmallVectorImpl<Instruction *> &) const override {
802     Value *Ptr;
803     if (LoadInst *LI = dyn_cast<LoadInst>(I))
804       Ptr = LI->getOperand(0);
805     else
806       Ptr = cast<StoreInst>(I)->getPointerOperand();
807     return PointerMustAliases.count(Ptr);
808   }
809 
doExtraRewritesBeforeFinalDeletion() const810   void doExtraRewritesBeforeFinalDeletion() const override {
811     // Insert stores after in the loop exit blocks.  Each exit block gets a
812     // store of the live-out values that feed them.  Since we've already told
813     // the SSA updater about the defs in the loop and the preheader
814     // definition, it is all set and we can start using it.
815     for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
816       BasicBlock *ExitBlock = LoopExitBlocks[i];
817       Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
818       LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
819       Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
820       Instruction *InsertPos = LoopInsertPts[i];
821       StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
822       NewSI->setAlignment(Alignment);
823       NewSI->setDebugLoc(DL);
824       if (AATags)
825         NewSI->setAAMetadata(AATags);
826     }
827   }
828 
replaceLoadWithValue(LoadInst * LI,Value * V) const829   void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
830     // Update alias analysis.
831     AST.copyValue(LI, V);
832   }
instructionDeleted(Instruction * I) const833   void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); }
834 };
835 } // end anon namespace
836 
837 /// Try to promote memory values to scalars by sinking stores out of the
838 /// loop and moving loads to before the loop.  We do this by looping over
839 /// the stores in the loop, looking for stores to Must pointers which are
840 /// loop invariant.
841 ///
promoteLoopAccessesToScalars(AliasSet & AS,SmallVectorImpl<BasicBlock * > & ExitBlocks,SmallVectorImpl<Instruction * > & InsertPts,PredIteratorCache & PIC,LoopInfo * LI,DominatorTree * DT,const TargetLibraryInfo * TLI,Loop * CurLoop,AliasSetTracker * CurAST,LoopSafetyInfo * SafetyInfo)842 bool llvm::promoteLoopAccessesToScalars(
843     AliasSet &AS, SmallVectorImpl<BasicBlock *> &ExitBlocks,
844     SmallVectorImpl<Instruction *> &InsertPts, PredIteratorCache &PIC,
845     LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
846     Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
847   // Verify inputs.
848   assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
849          CurAST != nullptr && SafetyInfo != nullptr &&
850          "Unexpected Input to promoteLoopAccessesToScalars");
851 
852   // We can promote this alias set if it has a store, if it is a "Must" alias
853   // set, if the pointer is loop invariant, and if we are not eliminating any
854   // volatile loads or stores.
855   if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
856       AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
857     return false;
858 
859   assert(!AS.empty() &&
860          "Must alias set should have at least one pointer element in it!");
861 
862   Value *SomePtr = AS.begin()->getValue();
863   BasicBlock *Preheader = CurLoop->getLoopPreheader();
864 
865   // It isn't safe to promote a load/store from the loop if the load/store is
866   // conditional.  For example, turning:
867   //
868   //    for () { if (c) *P += 1; }
869   //
870   // into:
871   //
872   //    tmp = *P;  for () { if (c) tmp +=1; } *P = tmp;
873   //
874   // is not safe, because *P may only be valid to access if 'c' is true.
875   //
876   // The safety property divides into two parts:
877   // 1) The memory may not be dereferenceable on entry to the loop.  In this
878   //    case, we can't insert the required load in the preheader.
879   // 2) The memory model does not allow us to insert a store along any dynamic
880   //    path which did not originally have one.
881   //
882   // It is safe to promote P if all uses are direct load/stores and if at
883   // least one is guaranteed to be executed.
884   bool GuaranteedToExecute = false;
885 
886   // It is also safe to promote P if we can prove that speculating a load into
887   // the preheader is safe (i.e. proving dereferenceability on all
888   // paths through the loop), and that the memory can be proven thread local
889   // (so that the memory model requirement doesn't apply.)  We first establish
890   // the former, and then run a capture analysis below to establish the later.
891   // We can use any access within the alias set to prove dereferenceability
892   // since they're all must alias.
893   bool CanSpeculateLoad = false;
894 
895   SmallVector<Instruction *, 64> LoopUses;
896   SmallPtrSet<Value *, 4> PointerMustAliases;
897 
898   // We start with an alignment of one and try to find instructions that allow
899   // us to prove better alignment.
900   unsigned Alignment = 1;
901   AAMDNodes AATags;
902   bool HasDedicatedExits = CurLoop->hasDedicatedExits();
903 
904   // Don't sink stores from loops without dedicated block exits. Exits
905   // containing indirect branches are not transformed by loop simplify,
906   // make sure we catch that. An additional load may be generated in the
907   // preheader for SSA updater, so also avoid sinking when no preheader
908   // is available.
909   if (!HasDedicatedExits || !Preheader)
910     return false;
911 
912   const DataLayout &MDL = Preheader->getModule()->getDataLayout();
913 
914   if (SafetyInfo->MayThrow) {
915     // If a loop can throw, we have to insert a store along each unwind edge.
916     // That said, we can't actually make the unwind edge explicit. Therefore,
917     // we have to prove that the store is dead along the unwind edge.
918     //
919     // Currently, this code just special-cases alloca instructions.
920     if (!isa<AllocaInst>(GetUnderlyingObject(SomePtr, MDL)))
921       return false;
922   }
923 
924   // Check that all of the pointers in the alias set have the same type.  We
925   // cannot (yet) promote a memory location that is loaded and stored in
926   // different sizes.  While we are at it, collect alignment and AA info.
927   bool Changed = false;
928   for (const auto &ASI : AS) {
929     Value *ASIV = ASI.getValue();
930     PointerMustAliases.insert(ASIV);
931 
932     // Check that all of the pointers in the alias set have the same type.  We
933     // cannot (yet) promote a memory location that is loaded and stored in
934     // different sizes.
935     if (SomePtr->getType() != ASIV->getType())
936       return Changed;
937 
938     for (User *U : ASIV->users()) {
939       // Ignore instructions that are outside the loop.
940       Instruction *UI = dyn_cast<Instruction>(U);
941       if (!UI || !CurLoop->contains(UI))
942         continue;
943 
944       // If there is an non-load/store instruction in the loop, we can't promote
945       // it.
946       if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {
947         assert(!Load->isVolatile() && "AST broken");
948         if (!Load->isSimple())
949           return Changed;
950 
951         if (!GuaranteedToExecute && !CanSpeculateLoad)
952           CanSpeculateLoad = isSafeToExecuteUnconditionally(
953               *Load, DT, CurLoop, SafetyInfo, Preheader->getTerminator());
954       } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
955         // Stores *of* the pointer are not interesting, only stores *to* the
956         // pointer.
957         if (UI->getOperand(1) != ASIV)
958           continue;
959         assert(!Store->isVolatile() && "AST broken");
960         if (!Store->isSimple())
961           return Changed;
962 
963         // Note that we only check GuaranteedToExecute inside the store case
964         // so that we do not introduce stores where they did not exist before
965         // (which would break the LLVM concurrency model).
966 
967         // If the alignment of this instruction allows us to specify a more
968         // restrictive (and performant) alignment and if we are sure this
969         // instruction will be executed, update the alignment.
970         // Larger is better, with the exception of 0 being the best alignment.
971         unsigned InstAlignment = Store->getAlignment();
972         if ((InstAlignment > Alignment || InstAlignment == 0) &&
973             Alignment != 0) {
974           if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
975             GuaranteedToExecute = true;
976             Alignment = InstAlignment;
977           }
978         } else if (!GuaranteedToExecute) {
979           GuaranteedToExecute =
980               isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo);
981         }
982 
983         if (!GuaranteedToExecute && !CanSpeculateLoad) {
984           CanSpeculateLoad = isDereferenceableAndAlignedPointer(
985               Store->getPointerOperand(), Store->getAlignment(), MDL,
986               Preheader->getTerminator(), DT);
987         }
988       } else
989         return Changed; // Not a load or store.
990 
991       // Merge the AA tags.
992       if (LoopUses.empty()) {
993         // On the first load/store, just take its AA tags.
994         UI->getAAMetadata(AATags);
995       } else if (AATags) {
996         UI->getAAMetadata(AATags, /* Merge = */ true);
997       }
998 
999       LoopUses.push_back(UI);
1000     }
1001   }
1002 
1003   // Check legality per comment above. Otherwise, we can't promote.
1004   bool PromotionIsLegal = GuaranteedToExecute;
1005   if (!PromotionIsLegal && CanSpeculateLoad) {
1006     // If this is a thread local location, then we can insert stores along
1007     // paths which originally didn't have them without violating the memory
1008     // model.
1009     Value *Object = GetUnderlyingObject(SomePtr, MDL);
1010     PromotionIsLegal =
1011         isAllocLikeFn(Object, TLI) && !PointerMayBeCaptured(Object, true, true);
1012   }
1013   if (!PromotionIsLegal)
1014     return Changed;
1015 
1016   // Figure out the loop exits and their insertion points, if this is the
1017   // first promotion.
1018   if (ExitBlocks.empty()) {
1019     CurLoop->getUniqueExitBlocks(ExitBlocks);
1020     InsertPts.clear();
1021     InsertPts.reserve(ExitBlocks.size());
1022     for (BasicBlock *ExitBlock : ExitBlocks)
1023       InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
1024   }
1025 
1026   // Can't insert into a catchswitch.
1027   for (BasicBlock *ExitBlock : ExitBlocks)
1028     if (isa<CatchSwitchInst>(ExitBlock->getTerminator()))
1029       return Changed;
1030 
1031   // Otherwise, this is safe to promote, lets do it!
1032   DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
1033                << '\n');
1034   Changed = true;
1035   ++NumPromoted;
1036 
1037   // Grab a debug location for the inserted loads/stores; given that the
1038   // inserted loads/stores have little relation to the original loads/stores,
1039   // this code just arbitrarily picks a location from one, since any debug
1040   // location is better than none.
1041   DebugLoc DL = LoopUses[0]->getDebugLoc();
1042 
1043   // We use the SSAUpdater interface to insert phi nodes as required.
1044   SmallVector<PHINode *, 16> NewPHIs;
1045   SSAUpdater SSA(&NewPHIs);
1046   LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
1047                         InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags);
1048 
1049   // Set up the preheader to have a definition of the value.  It is the live-out
1050   // value from the preheader that uses in the loop will use.
1051   LoadInst *PreheaderLoad = new LoadInst(
1052       SomePtr, SomePtr->getName() + ".promoted", Preheader->getTerminator());
1053   PreheaderLoad->setAlignment(Alignment);
1054   PreheaderLoad->setDebugLoc(DL);
1055   if (AATags)
1056     PreheaderLoad->setAAMetadata(AATags);
1057   SSA.AddAvailableValue(Preheader, PreheaderLoad);
1058 
1059   // Rewrite all the loads in the loop and remember all the definitions from
1060   // stores in the loop.
1061   Promoter.run(LoopUses);
1062 
1063   // If the SSAUpdater didn't use the load in the preheader, just zap it now.
1064   if (PreheaderLoad->use_empty())
1065     PreheaderLoad->eraseFromParent();
1066 
1067   return Changed;
1068 }
1069 
1070 /// Returns an owning pointer to an alias set which incorporates aliasing info
1071 /// from L and all subloops of L.
1072 /// FIXME: In new pass manager, there is no helper functions to handle loop
1073 /// analysis such as cloneBasicBlockAnalysis. So the AST needs to be recompute
1074 /// from scratch for every loop. Hook up with the helper functions when
1075 /// available in the new pass manager to avoid redundant computation.
1076 AliasSetTracker *
collectAliasInfoForLoop(Loop * L,LoopInfo * LI,AliasAnalysis * AA)1077 LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
1078                                                  AliasAnalysis *AA) {
1079   AliasSetTracker *CurAST = nullptr;
1080   SmallVector<Loop *, 4> RecomputeLoops;
1081   for (Loop *InnerL : L->getSubLoops()) {
1082     auto MapI = LoopToAliasSetMap.find(InnerL);
1083     // If the AST for this inner loop is missing it may have been merged into
1084     // some other loop's AST and then that loop unrolled, and so we need to
1085     // recompute it.
1086     if (MapI == LoopToAliasSetMap.end()) {
1087       RecomputeLoops.push_back(InnerL);
1088       continue;
1089     }
1090     AliasSetTracker *InnerAST = MapI->second;
1091 
1092     if (CurAST != nullptr) {
1093       // What if InnerLoop was modified by other passes ?
1094       CurAST->add(*InnerAST);
1095 
1096       // Once we've incorporated the inner loop's AST into ours, we don't need
1097       // the subloop's anymore.
1098       delete InnerAST;
1099     } else {
1100       CurAST = InnerAST;
1101     }
1102     LoopToAliasSetMap.erase(MapI);
1103   }
1104   if (CurAST == nullptr)
1105     CurAST = new AliasSetTracker(*AA);
1106 
1107   auto mergeLoop = [&](Loop *L) {
1108     // Loop over the body of this loop, looking for calls, invokes, and stores.
1109     // Because subloops have already been incorporated into AST, we skip blocks
1110     // in subloops.
1111     for (BasicBlock *BB : L->blocks())
1112       if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops.
1113         CurAST->add(*BB);          // Incorporate the specified basic block
1114   };
1115 
1116   // Add everything from the sub loops that are no longer directly available.
1117   for (Loop *InnerL : RecomputeLoops)
1118     mergeLoop(InnerL);
1119 
1120   // And merge in this loop.
1121   mergeLoop(L);
1122 
1123   return CurAST;
1124 }
1125 
1126 /// Simple analysis hook. Clone alias set info.
1127 ///
cloneBasicBlockAnalysis(BasicBlock * From,BasicBlock * To,Loop * L)1128 void LegacyLICMPass::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
1129                                              Loop *L) {
1130   AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
1131   if (!AST)
1132     return;
1133 
1134   AST->copyValue(From, To);
1135 }
1136 
1137 /// Simple Analysis hook. Delete value V from alias set
1138 ///
deleteAnalysisValue(Value * V,Loop * L)1139 void LegacyLICMPass::deleteAnalysisValue(Value *V, Loop *L) {
1140   AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
1141   if (!AST)
1142     return;
1143 
1144   AST->deleteValue(V);
1145 }
1146 
1147 /// Simple Analysis hook. Delete value L from alias set map.
1148 ///
deleteAnalysisLoop(Loop * L)1149 void LegacyLICMPass::deleteAnalysisLoop(Loop *L) {
1150   AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
1151   if (!AST)
1152     return;
1153 
1154   delete AST;
1155   LICM.getLoopToAliasSetMap().erase(L);
1156 }
1157 
1158 /// Return true if the body of this loop may store into the memory
1159 /// location pointed to by V.
1160 ///
pointerInvalidatedByLoop(Value * V,uint64_t Size,const AAMDNodes & AAInfo,AliasSetTracker * CurAST)1161 static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
1162                                      const AAMDNodes &AAInfo,
1163                                      AliasSetTracker *CurAST) {
1164   // Check to see if any of the basic blocks in CurLoop invalidate *V.
1165   return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
1166 }
1167 
1168 /// Little predicate that returns true if the specified basic block is in
1169 /// a subloop of the current one, not the current one itself.
1170 ///
inSubLoop(BasicBlock * BB,Loop * CurLoop,LoopInfo * LI)1171 static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1172   assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
1173   return LI->getLoopFor(BB) != CurLoop;
1174 }
1175