blob: 6659c5ad1c239c82c7061250cdb4d9d5a7e394a0 [file] [log] [blame]
Chris Lattner6ec05f52002-05-10 22:44:58 +00001//===-- LICM.cpp - Loop Invariant Code Motion Pass ------------------------===//
Misha Brukmanb1c93172005-04-21 23:48:37 +00002//
John Criswell482202a2003-10-20 19:43:21 +00003// The LLVM Compiler Infrastructure
4//
Chris Lattnerf3ebc3f2007-12-29 20:36:04 +00005// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
Misha Brukmanb1c93172005-04-21 23:48:37 +00007//
John Criswell482202a2003-10-20 19:43:21 +00008//===----------------------------------------------------------------------===//
Chris Lattner6ec05f52002-05-10 22:44:58 +00009//
Chris Lattnerc0517682003-12-09 17:18:00 +000010// 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
Chris Lattner547192d62003-12-19 07:22:45 +000014// live in registers, thus hoisting and sinking "invariant" loads and stores.
Chris Lattnerc0517682003-12-09 17:18:00 +000015//
16// This pass uses alias analysis for two purposes:
Chris Lattner45d67d62003-02-24 03:52:32 +000017//
Chris Lattner289ba2a2004-05-23 21:20:19 +000018// 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.
Chris Lattner45d67d62003-02-24 03:52:32 +000021// 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
Chris Lattner1dc98b42010-08-29 06:43:52 +000029// the SSAUpdater to construct the appropriate SSA form for the value.
Chris Lattner6ec05f52002-05-10 22:44:58 +000030//
Chris Lattner6ec05f52002-05-10 22:44:58 +000031//===----------------------------------------------------------------------===//
32
Dehao Chen9cba1f42016-07-12 22:37:48 +000033#include "llvm/Transforms/Scalar/LICM.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000034#include "llvm/ADT/Statistic.h"
Chris Lattnera51fa882002-08-22 21:39:55 +000035#include "llvm/Analysis/AliasAnalysis.h"
Chris Lattner0592bb72003-03-03 23:32:45 +000036#include "llvm/Analysis/AliasSetTracker.h"
Chandler Carruth7b560d42015-09-09 17:55:00 +000037#include "llvm/Analysis/BasicAliasAnalysis.h"
Philip Reamesb54c8e62016-03-09 22:59:30 +000038#include "llvm/Analysis/CaptureTracking.h"
Chris Lattner030f0202010-08-31 23:00:16 +000039#include "llvm/Analysis/ConstantFolding.h"
Chandler Carruth7b560d42015-09-09 17:55:00 +000040#include "llvm/Analysis/GlobalsModRef.h"
Philip Reamese0a54542016-03-09 23:07:53 +000041#include "llvm/Analysis/Loads.h"
Chris Lattner030f0202010-08-31 23:00:16 +000042#include "llvm/Analysis/LoopInfo.h"
43#include "llvm/Analysis/LoopPass.h"
Dehao Chen9cba1f42016-07-12 22:37:48 +000044#include "llvm/Analysis/LoopPassManager.h"
Philip Reamesb54c8e62016-03-09 22:59:30 +000045#include "llvm/Analysis/MemoryBuiltins.h"
Chandler Carruthabfa3e52014-01-24 01:59:49 +000046#include "llvm/Analysis/ScalarEvolution.h"
Chandler Carruth7b560d42015-09-09 17:55:00 +000047#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000048#include "llvm/Analysis/TargetLibraryInfo.h"
Dan Gohman75d7d5e2011-12-14 23:49:11 +000049#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth1305dc32014-03-04 11:45:46 +000050#include "llvm/IR/CFG.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000051#include "llvm/IR/Constants.h"
52#include "llvm/IR/DataLayout.h"
53#include "llvm/IR/DerivedTypes.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000054#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000055#include "llvm/IR/Instructions.h"
56#include "llvm/IR/IntrinsicInst.h"
57#include "llvm/IR/LLVMContext.h"
Chris Lattner473988c2013-01-05 16:44:07 +000058#include "llvm/IR/Metadata.h"
Chandler Carruthaa0ab632014-03-04 12:09:19 +000059#include "llvm/IR/PredIteratorCache.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000060#include "llvm/Support/CommandLine.h"
61#include "llvm/Support/Debug.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000062#include "llvm/Support/raw_ostream.h"
Dehao Chend55bc4c2016-05-05 00:54:54 +000063#include "llvm/Transforms/Scalar.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000064#include "llvm/Transforms/Utils/Local.h"
Chandler Carruth8765cf72014-01-25 04:07:24 +000065#include "llvm/Transforms/Utils/LoopUtils.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000066#include "llvm/Transforms/Utils/SSAUpdater.h"
Chris Lattner6ec05f52002-05-10 22:44:58 +000067#include <algorithm>
Benjamin Kramer82de7d32016-05-27 14:27:24 +000068#include <utility>
Chris Lattnerc0517682003-12-09 17:18:00 +000069using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000070
Chandler Carruth964daaa2014-04-22 02:55:47 +000071#define DEBUG_TYPE "licm"
72
Dehao Chend55bc4c2016-05-05 00:54:54 +000073STATISTIC(NumSunk, "Number of instructions sunk out of loop");
74STATISTIC(NumHoisted, "Number of instructions hoisted out of loop");
Chris Lattner79a42ac2006-12-19 21:40:18 +000075STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
76STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
Dehao Chend55bc4c2016-05-05 00:54:54 +000077STATISTIC(NumPromoted, "Number of memory locations promoted to registers");
Chris Lattner79a42ac2006-12-19 21:40:18 +000078
Dan Gohmand78c4002008-05-13 00:00:25 +000079static cl::opt<bool>
Dehao Chend55bc4c2016-05-05 00:54:54 +000080 DisablePromotion("disable-licm-promotion", cl::Hidden,
81 cl::desc("Disable memory promotion in LICM pass"));
Chris Lattner45d67d62003-02-24 03:52:32 +000082
Hal Finkel3d4269a2015-02-22 18:35:32 +000083static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
David Majnemer42a07302016-01-04 03:37:39 +000084static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +000085 const LoopSafetyInfo *SafetyInfo);
Sanjoy Das7a2e2be2016-01-28 15:51:58 +000086static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +000087 const LoopSafetyInfo *SafetyInfo);
Pete Cooper0cabcf22015-05-13 01:12:18 +000088static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
David Majnemer42a07302016-01-04 03:37:39 +000089 const Loop *CurLoop, AliasSetTracker *CurAST,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +000090 const LoopSafetyInfo *SafetyInfo);
Pete Cooper0cabcf22015-05-13 01:12:18 +000091static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
92 const DominatorTree *DT,
93 const Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +000094 const LoopSafetyInfo *SafetyInfo,
Philip Reamesb47b9c22015-05-22 02:14:05 +000095 const Instruction *CtxI = nullptr);
Hal Finkel3d4269a2015-02-22 18:35:32 +000096static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
Dehao Chend55bc4c2016-05-05 00:54:54 +000097 const AAMDNodes &AAInfo,
Hal Finkel3d4269a2015-02-22 18:35:32 +000098 AliasSetTracker *CurAST);
David Majnemer42a07302016-01-04 03:37:39 +000099static Instruction *
100CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
101 const LoopInfo *LI,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000102 const LoopSafetyInfo *SafetyInfo);
Dehao Chen4b5e7f72016-09-02 01:59:27 +0000103static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
Dehao Chen92abc7e2016-10-03 18:52:08 +0000104 DominatorTree *DT,
Dehao Chen4b5e7f72016-09-02 01:59:27 +0000105 Loop *CurLoop, AliasSetTracker *CurAST,
106 LoopSafetyInfo *SafetyInfo);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000107
Dan Gohmand78c4002008-05-13 00:00:25 +0000108namespace {
Dehao Chen9cba1f42016-07-12 22:37:48 +0000109struct LoopInvariantCodeMotion {
110 bool runOnLoop(Loop *L, AliasAnalysis *AA, LoopInfo *LI, DominatorTree *DT,
111 TargetLibraryInfo *TLI, ScalarEvolution *SE, bool DeleteAST);
112
113 DenseMap<Loop *, AliasSetTracker *> &getLoopToAliasSetMap() {
114 return LoopToAliasSetMap;
Dehao Chen7ef58202016-07-11 22:45:24 +0000115 }
116
Dehao Chen9cba1f42016-07-12 22:37:48 +0000117private:
118 DenseMap<Loop *, AliasSetTracker *> LoopToAliasSetMap;
119
120 AliasSetTracker *collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
121 AliasAnalysis *AA);
122};
123
124struct LegacyLICMPass : public LoopPass {
125 static char ID; // Pass identification, replacement for typeid
126 LegacyLICMPass() : LoopPass(ID) {
127 initializeLegacyLICMPassPass(*PassRegistry::getPassRegistry());
128 }
129
130 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 }
Chris Lattner6ec05f52002-05-10 22:44:58 +0000142
Dehao Chend55bc4c2016-05-05 00:54:54 +0000143 /// This transformation requires natural loop information & requires that
144 /// loop preheaders be inserted into the CFG...
145 ///
146 void getAnalysisUsage(AnalysisUsage &AU) const override {
147 AU.setPreservesCFG();
148 AU.addRequired<TargetLibraryInfoWrapperPass>();
149 getLoopAnalysisUsage(AU);
150 }
Chris Lattner6ec05f52002-05-10 22:44:58 +0000151
Dehao Chend55bc4c2016-05-05 00:54:54 +0000152 using llvm::Pass::doFinalization;
Matt Beaumont-Gayabfc4462012-12-04 05:41:27 +0000153
Dehao Chend55bc4c2016-05-05 00:54:54 +0000154 bool doFinalization() override {
Dehao Chen9cba1f42016-07-12 22:37:48 +0000155 assert(LICM.getLoopToAliasSetMap().empty() &&
156 "Didn't free loop alias sets");
Dehao Chend55bc4c2016-05-05 00:54:54 +0000157 return false;
158 }
Devang Patel69730c92007-03-07 04:41:30 +0000159
Dehao Chend55bc4c2016-05-05 00:54:54 +0000160private:
Dehao Chen9cba1f42016-07-12 22:37:48 +0000161 LoopInvariantCodeMotion LICM;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000162
Dehao Chend55bc4c2016-05-05 00:54:54 +0000163 /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
164 void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
165 Loop *L) override;
Devang Patelb98a0972007-07-31 08:01:41 +0000166
Dehao Chend55bc4c2016-05-05 00:54:54 +0000167 /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
168 /// set.
169 void deleteAnalysisValue(Value *V, Loop *L) override;
Devang Patelb98a0972007-07-31 08:01:41 +0000170
Dehao Chend55bc4c2016-05-05 00:54:54 +0000171 /// Simple Analysis hook. Delete loop L from alias set map.
172 void deleteAnalysisLoop(Loop *L) override;
Dehao Chend55bc4c2016-05-05 00:54:54 +0000173};
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000174}
Chris Lattner6ec05f52002-05-10 22:44:58 +0000175
Sean Silva0746f3b2016-08-09 00:28:52 +0000176PreservedAnalyses LICMPass::run(Loop &L, LoopAnalysisManager &AM) {
Dehao Chen9cba1f42016-07-12 22:37:48 +0000177 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
198char LegacyLICMPass::ID = 0;
199INITIALIZE_PASS_BEGIN(LegacyLICMPass, "licm", "Loop Invariant Code Motion",
200 false, false)
Chandler Carruth31088a92016-02-19 10:45:18 +0000201INITIALIZE_PASS_DEPENDENCY(LoopPass)
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000202INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
Dehao Chen9cba1f42016-07-12 22:37:48 +0000203INITIALIZE_PASS_END(LegacyLICMPass, "licm", "Loop Invariant Code Motion", false,
204 false)
Dan Gohmand78c4002008-05-13 00:00:25 +0000205
Dehao Chen9cba1f42016-07-12 22:37:48 +0000206Pass *llvm::createLICMPass() { return new LegacyLICMPass(); }
Chris Lattner6ec05f52002-05-10 22:44:58 +0000207
Devang Pateld8b1ceb2007-07-31 16:52:25 +0000208/// Hoist expressions out of the specified loop. Note, alias info for inner
Tobias Grossera3928f52011-07-06 19:20:02 +0000209/// loop is not preserved so it is not a good idea to run LICM multiple
Devang Pateld8b1ceb2007-07-31 16:52:25 +0000210/// times on one loop.
Dehao Chen9cba1f42016-07-12 22:37:48 +0000211/// We should delete AST for inner loops in the new pass manager to avoid
212/// memory leak.
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000213///
Dehao Chen9cba1f42016-07-12 22:37:48 +0000214bool LoopInvariantCodeMotion::runOnLoop(Loop *L, AliasAnalysis *AA,
215 LoopInfo *LI, DominatorTree *DT,
216 TargetLibraryInfo *TLI,
217 ScalarEvolution *SE, bool DeleteAST) {
218 bool Changed = false;
Chad Rosier43a33062011-12-02 01:26:24 +0000219
Chandler Carruthfc258542014-02-11 12:52:27 +0000220 assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
221
Dehao Chen9cba1f42016-07-12 22:37:48 +0000222 AliasSetTracker *CurAST = collectAliasInfoForLoop(L, LI, AA);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000223
Chris Lattnerd57f3f52002-09-26 19:40:25 +0000224 // Get the preheader block to move instructions into...
Dehao Chen9cba1f42016-07-12 22:37:48 +0000225 BasicBlock *Preheader = L->getLoopPreheader();
Chris Lattnerd57f3f52002-09-26 19:40:25 +0000226
Hal Finkel3d4269a2015-02-22 18:35:32 +0000227 // Compute loop safety information.
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000228 LoopSafetyInfo SafetyInfo;
Dehao Chen9cba1f42016-07-12 22:37:48 +0000229 computeLoopSafetyInfo(&SafetyInfo, L);
Nadav Rotem03dcd852012-09-04 10:25:04 +0000230
Chris Lattner6ec05f52002-05-10 22:44:58 +0000231 // 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 //
Chris Lattner64437692002-09-29 21:46:09 +0000236 // 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
Nick Lewyckya0d49da2007-08-18 15:08:56 +0000238 // us to sink instructions in one pass, without iteration. After sinking
Chris Lattner547192d62003-12-19 07:22:45 +0000239 // instructions, we perform another pass to hoist them out of the loop.
Chris Lattner64437692002-09-29 21:46:09 +0000240 //
Dan Gohmana83ac2d2009-11-05 21:11:53 +0000241 if (L->hasDedicatedExits())
Dehao Chen9cba1f42016-07-12 22:37:48 +0000242 Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000243 CurAST, &SafetyInfo);
Dan Gohmana83ac2d2009-11-05 21:11:53 +0000244 if (Preheader)
Dehao Chen9cba1f42016-07-12 22:37:48 +0000245 Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, L,
246 CurAST, &SafetyInfo);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000247
Chris Lattner45d67d62003-02-24 03:52:32 +0000248 // Now that all loop invariants have been removed from the loop, promote any
Chris Lattner1dc98b42010-08-29 06:43:52 +0000249 // memory references to scalars that we can.
Chandler Carruthcc497b62014-01-24 02:24:47 +0000250 if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
Dan Gohmanb9487362012-08-08 00:00:26 +0000251 SmallVector<BasicBlock *, 8> ExitBlocks;
252 SmallVector<Instruction *, 8> InsertPts;
Chandler Carruthfc258542014-02-11 12:52:27 +0000253 PredIteratorCache PIC;
Dan Gohmanb9487362012-08-08 00:00:26 +0000254
Chris Lattner1dc98b42010-08-29 06:43:52 +0000255 // Loop over all of the alias sets in the tracker object.
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000256 for (AliasSet &AS : *CurAST)
Dehao Chen9cba1f42016-07-12 22:37:48 +0000257 Changed |= promoteLoopAccessesToScalars(
258 AS, ExitBlocks, InsertPts, PIC, LI, DT, TLI, L, CurAST, &SafetyInfo);
Chandler Carruth16651522014-02-01 13:35:14 +0000259
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.
Chandler Carruth2f1fd162015-08-17 02:08:17 +0000266 if (Changed) {
Dehao Chen9cba1f42016-07-12 22:37:48 +0000267 formLCSSARecursively(*L, *DT, LI, SE);
Chandler Carruth2f1fd162015-08-17 02:08:17 +0000268 }
Chris Lattner1dc98b42010-08-29 06:43:52 +0000269 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000270
Chandler Carruthfc258542014-02-11 12:52:27 +0000271 // 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!");
Chandler Carruth8765cf72014-01-25 04:07:24 +0000277
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000278 // If this loop is nested inside of another one, save the alias information
279 // for when we process the outer loop.
Dehao Chen9cba1f42016-07-12 22:37:48 +0000280 if (L->getParentLoop() && !DeleteAST)
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000281 LoopToAliasSetMap[L] = CurAST;
282 else
283 delete CurAST;
Sanjoy Das4ae39202016-05-03 17:50:11 +0000284
Dehao Chen9cba1f42016-07-12 22:37:48 +0000285 if (Changed && SE)
286 SE->forgetLoopDispositions(L);
Devang Patel69730c92007-03-07 04:41:30 +0000287 return Changed;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000288}
289
Hal Finkel3d4269a2015-02-22 18:35:32 +0000290/// Walk the specified region of the CFG (defined by all blocks dominated by
Dehao Chend55bc4c2016-05-05 00:54:54 +0000291/// the specified block, and that are in the current loop) in reverse depth
Hal Finkel3d4269a2015-02-22 18:35:32 +0000292/// 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.
Chris Lattner547192d62003-12-19 07:22:45 +0000294///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000295bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
296 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000297 AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
Chris Lattner547192d62003-12-19 07:22:45 +0000298
Hal Finkel3d4269a2015-02-22 18:35:32 +0000299 // Verify inputs.
Dehao Chend55bc4c2016-05-05 00:54:54 +0000300 assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
301 CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
302 "Unexpected input to sinkRegion");
Hal Finkel3d4269a2015-02-22 18:35:32 +0000303
Hal Finkel3d4269a2015-02-22 18:35:32 +0000304 BasicBlock *BB = N->getBlock();
Chris Lattner547192d62003-12-19 07:22:45 +0000305 // If this subregion is not in the top level loop at all, exit.
Dehao Chend55bc4c2016-05-05 00:54:54 +0000306 if (!CurLoop->contains(BB))
307 return false;
Chris Lattner547192d62003-12-19 07:22:45 +0000308
Chris Lattner263f8042010-08-29 18:22:25 +0000309 // We are processing blocks in reverse dfo, so process children first.
Sanjay Patel99133222016-01-13 23:01:57 +0000310 bool Changed = false;
Dehao Chend55bc4c2016-05-05 00:54:54 +0000311 const std::vector<DomTreeNode *> &Children = N->getChildren();
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000312 for (DomTreeNode *Child : Children)
313 Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
314
Chris Lattner547192d62003-12-19 07:22:45 +0000315 // Only need to process the contents of this block if it is not part of a
316 // subloop (which would already have been processed).
Dehao Chend55bc4c2016-05-05 00:54:54 +0000317 if (inSubLoop(BB, CurLoop, LI))
318 return Changed;
Chris Lattner547192d62003-12-19 07:22:45 +0000319
Dehao Chend55bc4c2016-05-05 00:54:54 +0000320 for (BasicBlock::iterator II = BB->end(); II != BB->begin();) {
Chris Lattner91846012003-12-19 08:18:16 +0000321 Instruction &I = *--II;
Tobias Grossera3928f52011-07-06 19:20:02 +0000322
Chris Lattner263f8042010-08-29 18:22:25 +0000323 // If the instruction is dead, we would try to sink it because it isn't used
324 // in the loop, instead, just delete it.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000325 if (isInstructionTriviallyDead(&I, TLI)) {
Chris Lattnerf58382e2010-08-29 18:42:23 +0000326 DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
Chris Lattner263f8042010-08-29 18:22:25 +0000327 ++II;
328 CurAST->deleteValue(&I);
329 I.eraseFromParent();
330 Changed = true;
331 continue;
332 }
Misha Brukmanb1c93172005-04-21 23:48:37 +0000333
Chris Lattner547192d62003-12-19 07:22:45 +0000334 // 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 //
David Majnemer42a07302016-01-04 03:37:39 +0000339 if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
Dehao Chen92abc7e2016-10-03 18:52:08 +0000340 canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo)) {
Chris Lattner91846012003-12-19 08:18:16 +0000341 ++II;
David Majnemer42a07302016-01-04 03:37:39 +0000342 Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo);
Chris Lattner91846012003-12-19 08:18:16 +0000343 }
Chris Lattner547192d62003-12-19 07:22:45 +0000344 }
Hal Finkel3d4269a2015-02-22 18:35:32 +0000345 return Changed;
Chris Lattner547192d62003-12-19 07:22:45 +0000346}
347
Hal Finkel3d4269a2015-02-22 18:35:32 +0000348/// 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.
Chris Lattner64437692002-09-29 21:46:09 +0000352///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000353bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
354 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000355 AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
Hal Finkel3d4269a2015-02-22 18:35:32 +0000356 // Verify inputs.
Dehao Chend55bc4c2016-05-05 00:54:54 +0000357 assert(N != nullptr && AA != nullptr && LI != nullptr && DT != nullptr &&
358 CurLoop != nullptr && CurAST != nullptr && SafetyInfo != nullptr &&
359 "Unexpected input to hoistRegion");
Sanjay Patel99133222016-01-13 23:01:57 +0000360
Owen Andersonc24701e2007-04-24 06:40:39 +0000361 BasicBlock *BB = N->getBlock();
Sanjay Patel99133222016-01-13 23:01:57 +0000362
Chris Lattner05e86302002-09-29 22:26:07 +0000363 // If this subregion is not in the top level loop at all, exit.
Dehao Chend55bc4c2016-05-05 00:54:54 +0000364 if (!CurLoop->contains(BB))
365 return false;
Sanjay Patel99133222016-01-13 23:01:57 +0000366
Chris Lattneraaaea512003-12-10 06:41:05 +0000367 // Only need to process the contents of this block if it is not part of a
368 // subloop (which would already have been processed).
Sanjay Patel99133222016-01-13 23:01:57 +0000369 bool Changed = false;
Hal Finkel3d4269a2015-02-22 18:35:32 +0000370 if (!inSubLoop(BB, CurLoop, LI))
Dehao Chend55bc4c2016-05-05 00:54:54 +0000371 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E;) {
Chris Lattneraaaea512003-12-10 06:41:05 +0000372 Instruction &I = *II++;
Chris Lattner030f0202010-08-31 23:00:16 +0000373 // 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.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000376 if (Constant *C = ConstantFoldInstruction(
377 &I, I.getModule()->getDataLayout(), TLI)) {
Chris Lattner030f0202010-08-31 23:00:16 +0000378 DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n');
379 CurAST->copyValue(&I, C);
Chris Lattner030f0202010-08-31 23:00:16 +0000380 I.replaceAllUsesWith(C);
David Majnemer522a9112016-07-22 04:54:44 +0000381 if (isInstructionTriviallyDead(&I, TLI)) {
382 CurAST->deleteValue(&I);
383 I.eraseFromParent();
384 }
Chris Lattner030f0202010-08-31 23:00:16 +0000385 continue;
386 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000387
Chris Lattner547192d62003-12-19 07:22:45 +0000388 // Try hoisting the instruction out to the preheader. We can only do this
389 // if all of the operands of the instruction are loop invariant and if it
390 // is safe to hoist the instruction.
391 //
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000392 if (CurLoop->hasLoopInvariantOperands(&I) &&
Dehao Chen92abc7e2016-10-03 18:52:08 +0000393 canSinkOrHoistInst(I, AA, DT, CurLoop, CurAST, SafetyInfo) &&
Dehao Chend55bc4c2016-05-05 00:54:54 +0000394 isSafeToExecuteUnconditionally(
Sean Silva45835e72016-07-02 23:47:27 +0000395 I, DT, CurLoop, SafetyInfo,
Dehao Chend55bc4c2016-05-05 00:54:54 +0000396 CurLoop->getLoopPreheader()->getTerminator()))
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000397 Changed |= hoist(I, DT, CurLoop, SafetyInfo);
Chris Lattner030f0202010-08-31 23:00:16 +0000398 }
Chris Lattner64437692002-09-29 21:46:09 +0000399
Dehao Chend55bc4c2016-05-05 00:54:54 +0000400 const std::vector<DomTreeNode *> &Children = N->getChildren();
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000401 for (DomTreeNode *Child : Children)
402 Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000403 return Changed;
404}
405
406/// Computes loop safety information, checks loop body & header
Benjamin Kramerdf005cb2015-08-08 18:27:36 +0000407/// for the possibility of may throw exception.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000408///
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000409void llvm::computeLoopSafetyInfo(LoopSafetyInfo *SafetyInfo, Loop *CurLoop) {
Hal Finkel3d4269a2015-02-22 18:35:32 +0000410 assert(CurLoop != nullptr && "CurLoop cant be null");
411 BasicBlock *Header = CurLoop->getHeader();
412 // Setting default safety values.
413 SafetyInfo->MayThrow = false;
414 SafetyInfo->HeaderMayThrow = false;
Benjamin Kramerdf005cb2015-08-08 18:27:36 +0000415 // Iterate over header and compute safety info.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000416 for (BasicBlock::iterator I = Header->begin(), E = Header->end();
417 (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
Dehao Chen9cba1f42016-07-12 22:37:48 +0000418 SafetyInfo->HeaderMayThrow |=
419 !isGuaranteedToTransferExecutionToSuccessor(&*I);
Dehao Chend55bc4c2016-05-05 00:54:54 +0000420
Hal Finkel3d4269a2015-02-22 18:35:32 +0000421 SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
Dehao Chend55bc4c2016-05-05 00:54:54 +0000422 // Iterate over loop instructions and compute safety info.
423 for (Loop::block_iterator BB = CurLoop->block_begin(),
424 BBE = CurLoop->block_end();
425 (BB != BBE) && !SafetyInfo->MayThrow; ++BB)
Hal Finkel3d4269a2015-02-22 18:35:32 +0000426 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
427 (I != E) && !SafetyInfo->MayThrow; ++I)
Eli Friedmanf1da33e2016-06-11 21:48:25 +0000428 SafetyInfo->MayThrow |= !isGuaranteedToTransferExecutionToSuccessor(&*I);
David Majnemer42a07302016-01-04 03:37:39 +0000429
430 // Compute funclet colors if we might sink/hoist in a function with a funclet
431 // personality routine.
432 Function *Fn = CurLoop->getHeader()->getParent();
433 if (Fn->hasPersonalityFn())
434 if (Constant *PersonalityFn = Fn->getPersonalityFn())
435 if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
436 SafetyInfo->BlockColors = colorEHFunclets(*Fn);
Chris Lattner64437692002-09-29 21:46:09 +0000437}
438
Dehao Chen92abc7e2016-10-03 18:52:08 +0000439/// Returns true if the hoister and sinker can handle this instruction.
440/// If SafetyInfo is nullptr, we are checking for sinking instructions from
441/// preheader to loop body (no speculation).
442/// If SafetyInfo is not nullptr, we are checking for hoisting/sinking
443/// instructions from loop body to preheader/exit. Check if the instruction
444/// can execute specultatively.
Chris Lattneraaaea512003-12-10 06:41:05 +0000445///
Dehao Chen92abc7e2016-10-03 18:52:08 +0000446bool canSinkOrHoistInst(Instruction &I, AAResults *AA, DominatorTree *DT,
447 Loop *CurLoop, AliasSetTracker *CurAST,
448 LoopSafetyInfo *SafetyInfo) {
Chris Lattner65c11932003-12-09 19:32:44 +0000449 // Loads have extra constraints we have to verify before we can hoist them.
450 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
Eli Friedman91386c72011-08-15 20:52:09 +0000451 if (!LI->isUnordered())
Dehao Chend55bc4c2016-05-05 00:54:54 +0000452 return false; // Don't hoist volatile/atomic loads!
Chris Lattner65c11932003-12-09 19:32:44 +0000453
Chris Lattner8a8fb902008-07-23 05:06:28 +0000454 // Loads from constant memory are always safe to move, even if they end up
455 // in the same alias set as something that ends up being modified.
Dan Gohmancbc6ebb2009-11-19 19:00:10 +0000456 if (AA->pointsToConstantMemory(LI->getOperand(0)))
Chris Lattner8a8fb902008-07-23 05:06:28 +0000457 return true;
Philip Reames5a3f5f72014-10-21 00:13:20 +0000458 if (LI->getMetadata(LLVMContext::MD_invariant_load))
Pete Cooper9ee22092011-11-08 19:30:00 +0000459 return true;
Tobias Grossera3928f52011-07-06 19:20:02 +0000460
Chris Lattner65c11932003-12-09 19:32:44 +0000461 // Don't hoist loads which have may-aliased stores in loop.
Dan Gohmanf372cf82010-10-19 22:54:46 +0000462 uint64_t Size = 0;
Chris Lattnerb1374092004-11-26 21:20:09 +0000463 if (LI->getType()->isSized())
Dehao Chen4b5e7f72016-09-02 01:59:27 +0000464 Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
Hal Finkelcc39b672014-07-24 12:16:19 +0000465
466 AAMDNodes AAInfo;
467 LI->getAAMetadata(AAInfo);
468
Hal Finkel3d4269a2015-02-22 18:35:32 +0000469 return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
Chris Lattner20cda262004-03-15 04:11:30 +0000470 } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
Eli Friedman942e1c12011-05-27 18:37:52 +0000471 // Don't sink or hoist dbg info; it's legal, but not useful.
Dehao Chen4b5e7f72016-09-02 01:59:27 +0000472 if (isa<DbgInfoIntrinsic>(I))
Eli Friedman942e1c12011-05-27 18:37:52 +0000473 return false;
474
David Majnemer42a07302016-01-04 03:37:39 +0000475 // Don't sink calls which can throw.
476 if (CI->mayThrow())
477 return false;
478
Eli Friedman942e1c12011-05-27 18:37:52 +0000479 // Handle simple cases by querying alias analysis.
Chandler Carruth194f59c2015-07-22 23:15:57 +0000480 FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
481 if (Behavior == FMRB_DoesNotAccessMemory)
Duncan Sands68b6f502007-12-01 07:51:45 +0000482 return true;
Dan Gohman0f175072010-11-09 19:58:21 +0000483 if (AliasAnalysis::onlyReadsMemory(Behavior)) {
Philip Reames5f994232015-09-21 22:27:59 +0000484 // A readonly argmemonly function only reads from memory pointed to by
485 // it's arguments with arbitrary offsets. If we can prove there are no
486 // writes to this memory in the loop, we can hoist or sink.
487 if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
488 for (Value *Op : CI->arg_operands())
489 if (Op->getType()->isPointerTy() &&
490 pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize,
491 AAMDNodes(), CurAST))
492 return false;
493 return true;
494 }
Duncan Sands68b6f502007-12-01 07:51:45 +0000495 // If this call only reads from memory and there are no writes to memory
496 // in the loop, we can hoist or sink the call as appropriate.
497 bool FoundMod = false;
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000498 for (AliasSet &AS : *CurAST) {
Duncan Sands68b6f502007-12-01 07:51:45 +0000499 if (!AS.isForwardingAliasSet() && AS.isMod()) {
500 FoundMod = true;
501 break;
Chris Lattner20cda262004-03-15 04:11:30 +0000502 }
Chris Lattner20cda262004-03-15 04:11:30 +0000503 }
Dehao Chend55bc4c2016-05-05 00:54:54 +0000504 if (!FoundMod)
505 return true;
Chris Lattner20cda262004-03-15 04:11:30 +0000506 }
507
Nadav Rotem03dcd852012-09-04 10:25:04 +0000508 // FIXME: This should use mod/ref information to see if we can hoist or
509 // sink the call.
Dehao Chen4b5e7f72016-09-02 01:59:27 +0000510
Chris Lattner20cda262004-03-15 04:11:30 +0000511 return false;
Chris Lattner65c11932003-12-09 19:32:44 +0000512 }
513
Dehao Chen4b5e7f72016-09-02 01:59:27 +0000514 // Only these instructions are hoistable/sinkable.
515 if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
516 !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
517 !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
518 !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
519 !isa<InsertValueInst>(I))
520 return false;
521
Dehao Chen92abc7e2016-10-03 18:52:08 +0000522 // SafetyInfo is nullptr if we are checking for sinking from preheader to
523 // loop body. It will be always safe as there is no speculative execution.
524 if (!SafetyInfo)
525 return true;
526
Dehao Chen4b5e7f72016-09-02 01:59:27 +0000527 // TODO: Plumb the context instruction through to make hoisting and sinking
528 // more powerful. Hoisting of loads already works due to the special casing
529 // above.
530 return isSafeToExecuteUnconditionally(I, DT, CurLoop, SafetyInfo, nullptr);
Chris Lattneraaaea512003-12-10 06:41:05 +0000531}
532
Hal Finkel3d4269a2015-02-22 18:35:32 +0000533/// Returns true if a PHINode is a trivially replaceable with an
Chandler Carruth8765cf72014-01-25 04:07:24 +0000534/// Instruction.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000535/// This is true when all incoming values are that instruction.
536/// This pattern occurs most often with LCSSA PHI nodes.
Chandler Carruth8765cf72014-01-25 04:07:24 +0000537///
Pete Cooper47e80cd2015-05-12 20:05:20 +0000538static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
Pete Cooper833f34d2015-05-12 20:05:31 +0000539 for (const Value *IncValue : PN.incoming_values())
540 if (IncValue != &I)
Chandler Carruth8765cf72014-01-25 04:07:24 +0000541 return false;
542
543 return true;
544}
545
Hal Finkel3d4269a2015-02-22 18:35:32 +0000546/// Return true if the only users of this instruction are outside of
547/// the loop. If this is true, we can sink the instruction to the exit
548/// blocks of the loop.
Chris Lattneraaaea512003-12-10 06:41:05 +0000549///
David Majnemer42a07302016-01-04 03:37:39 +0000550static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000551 const LoopSafetyInfo *SafetyInfo) {
David Majnemer42a07302016-01-04 03:37:39 +0000552 const auto &BlockColors = SafetyInfo->BlockColors;
Pete Cooper0cabcf22015-05-13 01:12:18 +0000553 for (const User *U : I.users()) {
554 const Instruction *UI = cast<Instruction>(U);
555 if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
David Majnemer42a07302016-01-04 03:37:39 +0000556 const BasicBlock *BB = PN->getParent();
557 // We cannot sink uses in catchswitches.
558 if (isa<CatchSwitchInst>(BB->getTerminator()))
559 return false;
560
561 // We need to sink a callsite to a unique funclet. Avoid sinking if the
562 // phi use is too muddled.
563 if (isa<CallInst>(I))
564 if (!BlockColors.empty() &&
565 BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
566 return false;
567
Chandler Carruth8765cf72014-01-25 04:07:24 +0000568 // A PHI node where all of the incoming values are this instruction are
569 // special -- they can just be RAUW'ed with the instruction and thus
570 // don't require a use in the predecessor. This is a particular important
571 // special case because it is the pattern found in LCSSA form.
572 if (isTriviallyReplacablePHI(*PN, I)) {
573 if (CurLoop->contains(PN))
574 return false;
575 else
576 continue;
577 }
578
579 // Otherwise, PHI node uses occur in predecessor blocks if the incoming
580 // values. Check for such a use being inside the loop.
Chris Lattner34399dd2003-12-11 22:23:32 +0000581 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
582 if (PN->getIncomingValue(i) == &I)
583 if (CurLoop->contains(PN->getIncomingBlock(i)))
584 return false;
Chandler Carruth8765cf72014-01-25 04:07:24 +0000585
586 continue;
Chris Lattner34399dd2003-12-11 22:23:32 +0000587 }
Chandler Carruth8765cf72014-01-25 04:07:24 +0000588
Chandler Carruthcdf47882014-03-09 03:16:01 +0000589 if (CurLoop->contains(UI))
Chandler Carruth8765cf72014-01-25 04:07:24 +0000590 return false;
Chris Lattner34399dd2003-12-11 22:23:32 +0000591 }
Chris Lattneraaaea512003-12-10 06:41:05 +0000592 return true;
593}
594
David Majnemer42a07302016-01-04 03:37:39 +0000595static Instruction *
596CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
597 const LoopInfo *LI,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000598 const LoopSafetyInfo *SafetyInfo) {
David Majnemer42a07302016-01-04 03:37:39 +0000599 Instruction *New;
600 if (auto *CI = dyn_cast<CallInst>(&I)) {
601 const auto &BlockColors = SafetyInfo->BlockColors;
602
603 // Sinking call-sites need to be handled differently from other
604 // instructions. The cloned call-site needs a funclet bundle operand
605 // appropriate for it's location in the CFG.
606 SmallVector<OperandBundleDef, 1> OpBundles;
607 for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
608 BundleIdx != BundleEnd; ++BundleIdx) {
609 OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
610 if (Bundle.getTagID() == LLVMContext::OB_funclet)
611 continue;
612
613 OpBundles.emplace_back(Bundle);
614 }
615
616 if (!BlockColors.empty()) {
617 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
618 assert(CV.size() == 1 && "non-unique color for exit block!");
619 BasicBlock *BBColor = CV.front();
620 Instruction *EHPad = BBColor->getFirstNonPHI();
621 if (EHPad->isEHPad())
622 OpBundles.emplace_back("funclet", EHPad);
623 }
624
625 New = CallInst::Create(CI, OpBundles);
626 } else {
627 New = I.clone();
628 }
629
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000630 ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
Dehao Chend55bc4c2016-05-05 00:54:54 +0000631 if (!I.getName().empty())
632 New->setName(I.getName() + ".le");
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000633
634 // Build LCSSA PHI nodes for any in-loop operands. Note that this is
635 // particularly cheap because we can rip off the PHI node that we're
636 // replacing for the number and blocks of the predecessors.
637 // OPT: If this shows up in a profile, we can instead finish sinking all
638 // invariant instructions, and then walk their operands to re-establish
639 // LCSSA. That will eliminate creating PHI nodes just to nuke them when
640 // sinking bottom-up.
641 for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
642 ++OI)
643 if (Instruction *OInst = dyn_cast<Instruction>(*OI))
644 if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
645 if (!OLoop->contains(&PN)) {
646 PHINode *OpPN =
647 PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000648 OInst->getName() + ".lcssa", &ExitBlock.front());
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000649 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
650 OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
651 *OI = OpPN;
652 }
653 return New;
654}
655
Hal Finkel3d4269a2015-02-22 18:35:32 +0000656/// When an instruction is found to only be used outside of the loop, this
657/// function moves it to the exit blocks and patches up SSA form as needed.
Chris Lattner91846012003-12-19 08:18:16 +0000658/// This method is guaranteed to remove the original instruction from its
659/// position, and may either delete it or move it to outside of the loop.
Chris Lattneraaaea512003-12-10 06:41:05 +0000660///
Pete Cooper0cabcf22015-05-13 01:12:18 +0000661static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
David Majnemer42a07302016-01-04 03:37:39 +0000662 const Loop *CurLoop, AliasSetTracker *CurAST,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000663 const LoopSafetyInfo *SafetyInfo) {
Nick Lewycky299c6df2010-07-30 20:27:01 +0000664 DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
Hal Finkel3d4269a2015-02-22 18:35:32 +0000665 bool Changed = false;
Dehao Chend55bc4c2016-05-05 00:54:54 +0000666 if (isa<LoadInst>(I))
667 ++NumMovedLoads;
668 else if (isa<CallInst>(I))
669 ++NumMovedCalls;
Chris Lattner55c21132003-12-10 20:43:29 +0000670 ++NumSunk;
671 Changed = true;
672
Chandler Carruthfc258542014-02-11 12:52:27 +0000673#ifndef NDEBUG
674 SmallVector<BasicBlock *, 32> ExitBlocks;
675 CurLoop->getUniqueExitBlocks(ExitBlocks);
Dehao Chend55bc4c2016-05-05 00:54:54 +0000676 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
Hal Finkel3d4269a2015-02-22 18:35:32 +0000677 ExitBlocks.end());
Chandler Carruthfc258542014-02-11 12:52:27 +0000678#endif
Chandler Carruth8765cf72014-01-25 04:07:24 +0000679
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000680 // Clones of this instruction. Don't create more than one per exit block!
681 SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
682
Chandler Carruthfc258542014-02-11 12:52:27 +0000683 // If this instruction is only used outside of the loop, then all users are
684 // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
685 // the instruction.
686 while (!I.use_empty()) {
David Majnemer6bc83e02015-07-12 03:53:05 +0000687 Value::user_iterator UI = I.user_begin();
688 auto *User = cast<Instruction>(*UI);
David Majnemer49428102014-09-02 16:22:00 +0000689 if (!DT->isReachableFromEntry(User->getParent())) {
690 User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
691 continue;
692 }
Chandler Carruthfc258542014-02-11 12:52:27 +0000693 // The user must be a PHI node.
David Majnemer49428102014-09-02 16:22:00 +0000694 PHINode *PN = cast<PHINode>(User);
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000695
David Majnemer6bc83e02015-07-12 03:53:05 +0000696 // Surprisingly, instructions can be used outside of loops without any
697 // exits. This can only happen in PHI nodes if the incoming block is
698 // unreachable.
699 Use &U = UI.getUse();
700 BasicBlock *BB = PN->getIncomingBlock(U);
701 if (!DT->isReachableFromEntry(BB)) {
702 U = UndefValue::get(I.getType());
703 continue;
704 }
705
Chandler Carruthfc258542014-02-11 12:52:27 +0000706 BasicBlock *ExitBlock = PN->getParent();
707 assert(ExitBlockSet.count(ExitBlock) &&
708 "The LCSSA PHI is not in an exit block!");
709
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000710 Instruction *New;
711 auto It = SunkCopies.find(ExitBlock);
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000712 if (It != SunkCopies.end())
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000713 New = It->second;
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000714 else
715 New = SunkCopies[ExitBlock] =
David Majnemer42a07302016-01-04 03:37:39 +0000716 CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
Chandler Carruthfc258542014-02-11 12:52:27 +0000717
718 PN->replaceAllUsesWith(New);
719 PN->eraseFromParent();
Chris Lattnercd96b4d2010-08-29 04:28:20 +0000720 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000721
Chris Lattner1a1ed692010-08-29 18:00:00 +0000722 CurAST->deleteValue(&I);
Chandler Carruthfc258542014-02-11 12:52:27 +0000723 I.eraseFromParent();
Hal Finkel3d4269a2015-02-22 18:35:32 +0000724 return Changed;
Chris Lattneraaaea512003-12-10 06:41:05 +0000725}
Chris Lattner64437692002-09-29 21:46:09 +0000726
Hal Finkel3d4269a2015-02-22 18:35:32 +0000727/// When an instruction is found to only use loop invariant operands that
728/// is safe to hoist, this instruction is called to do the dirty work.
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000729///
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000730static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000731 const LoopSafetyInfo *SafetyInfo) {
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000732 auto *Preheader = CurLoop->getLoopPreheader();
Dehao Chend55bc4c2016-05-05 00:54:54 +0000733 DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": " << I
734 << "\n");
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000735
736 // Metadata can be dependent on conditions we are hoisting above.
737 // Conservatively strip all metadata on the instruction unless we were
738 // guaranteed to execute I if we entered the loop, in which case the metadata
739 // is valid in the loop preheader.
740 if (I.hasMetadataOtherThanDebugLoc() &&
741 // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
742 // time in isGuaranteedToExecute if we don't actually have anything to
743 // drop. It is a compile time optimization, not required for correctness.
744 !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
745 I.dropUnknownNonDebugMetadata();
746
Chris Lattner6ac06592010-08-29 18:18:40 +0000747 // Move the new node to the Preheader, before its terminator.
748 I.moveBefore(Preheader->getTerminator());
Misha Brukmanb1c93172005-04-21 23:48:37 +0000749
Dehao Chend55bc4c2016-05-05 00:54:54 +0000750 if (isa<LoadInst>(I))
751 ++NumMovedLoads;
752 else if (isa<CallInst>(I))
753 ++NumMovedCalls;
Chris Lattner718b2212002-09-26 16:38:03 +0000754 ++NumHoisted;
Hal Finkel3d4269a2015-02-22 18:35:32 +0000755 return true;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000756}
757
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000758/// Only sink or hoist an instruction if it is not a trapping instruction,
759/// or if the instruction is known not to trap when moved to the preheader.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000760/// or if it is a trapping instruction and is guaranteed to execute.
Dehao Chend55bc4c2016-05-05 00:54:54 +0000761static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
Pete Cooper0cabcf22015-05-13 01:12:18 +0000762 const DominatorTree *DT,
763 const Loop *CurLoop,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000764 const LoopSafetyInfo *SafetyInfo,
Philip Reamesb47b9c22015-05-22 02:14:05 +0000765 const Instruction *CtxI) {
Sean Silva45835e72016-07-02 23:47:27 +0000766 if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT))
Eli Friedmanb8f6a4f2009-07-17 04:28:42 +0000767 return true;
Misha Brukmanb1c93172005-04-21 23:48:37 +0000768
Hal Finkel3d4269a2015-02-22 18:35:32 +0000769 return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
Eli Friedman0cdc1482011-07-20 21:37:47 +0000770}
771
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000772namespace {
Dehao Chend55bc4c2016-05-05 00:54:54 +0000773class LoopPromoter : public LoadAndStorePromoter {
774 Value *SomePtr; // Designated pointer to store to.
775 SmallPtrSetImpl<Value *> &PointerMustAliases;
776 SmallVectorImpl<BasicBlock *> &LoopExitBlocks;
777 SmallVectorImpl<Instruction *> &LoopInsertPts;
778 PredIteratorCache &PredCache;
779 AliasSetTracker &AST;
780 LoopInfo &LI;
781 DebugLoc DL;
782 int Alignment;
783 AAMDNodes AATags;
Chandler Carruthfc258542014-02-11 12:52:27 +0000784
Dehao Chend55bc4c2016-05-05 00:54:54 +0000785 Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
786 if (Instruction *I = dyn_cast<Instruction>(V))
787 if (Loop *L = LI.getLoopFor(I->getParent()))
788 if (!L->contains(BB)) {
789 // We need to create an LCSSA PHI node for the incoming value and
790 // store that.
791 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(BB),
792 I->getName() + ".lcssa", &BB->front());
793 for (BasicBlock *Pred : PredCache.get(BB))
794 PN->addIncoming(I, Pred);
795 return PN;
796 }
797 return V;
798 }
Chandler Carruthfc258542014-02-11 12:52:27 +0000799
Dehao Chend55bc4c2016-05-05 00:54:54 +0000800public:
801 LoopPromoter(Value *SP, ArrayRef<const Instruction *> Insts, SSAUpdater &S,
802 SmallPtrSetImpl<Value *> &PMA,
803 SmallVectorImpl<BasicBlock *> &LEB,
804 SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
805 AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
806 const AAMDNodes &AATags)
807 : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
808 LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
Benjamin Kramer82de7d32016-05-27 14:27:24 +0000809 LI(li), DL(std::move(dl)), Alignment(alignment), AATags(AATags) {}
Tobias Grossera3928f52011-07-06 19:20:02 +0000810
Dehao Chend55bc4c2016-05-05 00:54:54 +0000811 bool isInstInList(Instruction *I,
812 const SmallVectorImpl<Instruction *> &) const override {
813 Value *Ptr;
814 if (LoadInst *LI = dyn_cast<LoadInst>(I))
815 Ptr = LI->getOperand(0);
816 else
817 Ptr = cast<StoreInst>(I)->getPointerOperand();
818 return PointerMustAliases.count(Ptr);
819 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000820
Dehao Chend55bc4c2016-05-05 00:54:54 +0000821 void doExtraRewritesBeforeFinalDeletion() const override {
822 // Insert stores after in the loop exit blocks. Each exit block gets a
823 // store of the live-out values that feed them. Since we've already told
824 // the SSA updater about the defs in the loop and the preheader
825 // definition, it is all set and we can start using it.
826 for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
827 BasicBlock *ExitBlock = LoopExitBlocks[i];
828 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
829 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
830 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
831 Instruction *InsertPos = LoopInsertPts[i];
832 StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
833 NewSI->setAlignment(Alignment);
834 NewSI->setDebugLoc(DL);
835 if (AATags)
836 NewSI->setAAMetadata(AATags);
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000837 }
Dehao Chend55bc4c2016-05-05 00:54:54 +0000838 }
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000839
Dehao Chend55bc4c2016-05-05 00:54:54 +0000840 void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
841 // Update alias analysis.
842 AST.copyValue(LI, V);
843 }
844 void instructionDeleted(Instruction *I) const override { AST.deleteValue(I); }
845};
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000846} // end anon namespace
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000847
Hal Finkel3d4269a2015-02-22 18:35:32 +0000848/// Try to promote memory values to scalars by sinking stores out of the
849/// loop and moving loads to before the loop. We do this by looping over
850/// the stores in the loop, looking for stores to Must pointers which are
851/// loop invariant.
Chris Lattner45d67d62003-02-24 03:52:32 +0000852///
Dehao Chend55bc4c2016-05-05 00:54:54 +0000853bool llvm::promoteLoopAccessesToScalars(
854 AliasSet &AS, SmallVectorImpl<BasicBlock *> &ExitBlocks,
855 SmallVectorImpl<Instruction *> &InsertPts, PredIteratorCache &PIC,
856 LoopInfo *LI, DominatorTree *DT, const TargetLibraryInfo *TLI,
Evgeniy Stepanov122f9842016-06-10 20:03:17 +0000857 Loop *CurLoop, AliasSetTracker *CurAST, LoopSafetyInfo *SafetyInfo) {
Hal Finkel3d4269a2015-02-22 18:35:32 +0000858 // Verify inputs.
Dehao Chend55bc4c2016-05-05 00:54:54 +0000859 assert(LI != nullptr && DT != nullptr && CurLoop != nullptr &&
860 CurAST != nullptr && SafetyInfo != nullptr &&
Hal Finkel3d4269a2015-02-22 18:35:32 +0000861 "Unexpected Input to promoteLoopAccessesToScalars");
Sanjay Patel99133222016-01-13 23:01:57 +0000862
Chris Lattner1dc98b42010-08-29 06:43:52 +0000863 // We can promote this alias set if it has a store, if it is a "Must" alias
864 // set, if the pointer is loop invariant, and if we are not eliminating any
865 // volatile loads or stores.
866 if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
867 AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
Sanjay Patel99133222016-01-13 23:01:57 +0000868 return false;
Tobias Grossera3928f52011-07-06 19:20:02 +0000869
Chris Lattner1dc98b42010-08-29 06:43:52 +0000870 assert(!AS.empty() &&
871 "Must alias set should have at least one pointer element in it!");
Hal Finkel3d4269a2015-02-22 18:35:32 +0000872
Chris Lattner1dc98b42010-08-29 06:43:52 +0000873 Value *SomePtr = AS.begin()->getValue();
Dehao Chend55bc4c2016-05-05 00:54:54 +0000874 BasicBlock *Preheader = CurLoop->getLoopPreheader();
Chris Lattner45d67d62003-02-24 03:52:32 +0000875
Chris Lattner1dc98b42010-08-29 06:43:52 +0000876 // It isn't safe to promote a load/store from the loop if the load/store is
877 // conditional. For example, turning:
Chris Lattner45d67d62003-02-24 03:52:32 +0000878 //
Chris Lattner1dc98b42010-08-29 06:43:52 +0000879 // for () { if (c) *P += 1; }
Chris Lattner45d67d62003-02-24 03:52:32 +0000880 //
Chris Lattner1dc98b42010-08-29 06:43:52 +0000881 // into:
882 //
883 // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
884 //
885 // is not safe, because *P may only be valid to access if 'c' is true.
Tobias Grossera3928f52011-07-06 19:20:02 +0000886 //
Philip Reamesb54c8e62016-03-09 22:59:30 +0000887 // The safety property divides into two parts:
888 // 1) The memory may not be dereferenceable on entry to the loop. In this
889 // case, we can't insert the required load in the preheader.
890 // 2) The memory model does not allow us to insert a store along any dynamic
891 // path which did not originally have one.
892 //
Chris Lattner1dc98b42010-08-29 06:43:52 +0000893 // It is safe to promote P if all uses are direct load/stores and if at
894 // least one is guaranteed to be executed.
895 bool GuaranteedToExecute = false;
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000896
Philip Reamesb54c8e62016-03-09 22:59:30 +0000897 // It is also safe to promote P if we can prove that speculating a load into
898 // the preheader is safe (i.e. proving dereferenceability on all
899 // paths through the loop), and that the memory can be proven thread local
900 // (so that the memory model requirement doesn't apply.) We first establish
901 // the former, and then run a capture analysis below to establish the later.
902 // We can use any access within the alias set to prove dereferenceability
903 // since they're all must alias.
904 bool CanSpeculateLoad = false;
905
Dehao Chend55bc4c2016-05-05 00:54:54 +0000906 SmallVector<Instruction *, 64> LoopUses;
907 SmallPtrSet<Value *, 4> PointerMustAliases;
Chris Lattner45d67d62003-02-24 03:52:32 +0000908
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000909 // We start with an alignment of one and try to find instructions that allow
910 // us to prove better alignment.
911 unsigned Alignment = 1;
Hal Finkelcc39b672014-07-24 12:16:19 +0000912 AAMDNodes AATags;
Bruno Cardoso Lopes46d5bf22014-11-28 19:47:46 +0000913 bool HasDedicatedExits = CurLoop->hasDedicatedExits();
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000914
Philip Reamesb54c8e62016-03-09 22:59:30 +0000915 // Don't sink stores from loops without dedicated block exits. Exits
916 // containing indirect branches are not transformed by loop simplify,
917 // make sure we catch that. An additional load may be generated in the
918 // preheader for SSA updater, so also avoid sinking when no preheader
919 // is available.
920 if (!HasDedicatedExits || !Preheader)
921 return false;
Dehao Chend55bc4c2016-05-05 00:54:54 +0000922
Philip Reamesb54c8e62016-03-09 22:59:30 +0000923 const DataLayout &MDL = Preheader->getModule()->getDataLayout();
924
Eli Friedmanee895052016-06-05 22:13:52 +0000925 if (SafetyInfo->MayThrow) {
926 // If a loop can throw, we have to insert a store along each unwind edge.
927 // That said, we can't actually make the unwind edge explicit. Therefore,
928 // we have to prove that the store is dead along the unwind edge.
929 //
930 // Currently, this code just special-cases alloca instructions.
931 if (!isa<AllocaInst>(GetUnderlyingObject(SomePtr, MDL)))
932 return false;
933 }
934
Chris Lattner1dc98b42010-08-29 06:43:52 +0000935 // Check that all of the pointers in the alias set have the same type. We
936 // cannot (yet) promote a memory location that is loaded and stored in
Hal Finkelcc39b672014-07-24 12:16:19 +0000937 // different sizes. While we are at it, collect alignment and AA info.
Sanjay Patel99133222016-01-13 23:01:57 +0000938 bool Changed = false;
Benjamin Kramer135f7352016-06-26 12:28:59 +0000939 for (const auto &ASI : AS) {
940 Value *ASIV = ASI.getValue();
Chris Lattner1dc98b42010-08-29 06:43:52 +0000941 PointerMustAliases.insert(ASIV);
Tobias Grossera3928f52011-07-06 19:20:02 +0000942
Chris Lattnerf12c08d2008-05-22 00:53:38 +0000943 // Check that all of the pointers in the alias set have the same type. We
944 // cannot (yet) promote a memory location that is loaded and stored in
945 // different sizes.
Chris Lattner1dc98b42010-08-29 06:43:52 +0000946 if (SomePtr->getType() != ASIV->getType())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000947 return Changed;
Tobias Grossera3928f52011-07-06 19:20:02 +0000948
Chandler Carruthcdf47882014-03-09 03:16:01 +0000949 for (User *U : ASIV->users()) {
Chris Lattner1dc98b42010-08-29 06:43:52 +0000950 // Ignore instructions that are outside the loop.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000951 Instruction *UI = dyn_cast<Instruction>(U);
952 if (!UI || !CurLoop->contains(UI))
Chris Lattnerf12c08d2008-05-22 00:53:38 +0000953 continue;
Tobias Grossera3928f52011-07-06 19:20:02 +0000954
Chris Lattner1dc98b42010-08-29 06:43:52 +0000955 // If there is an non-load/store instruction in the loop, we can't promote
956 // it.
Sanjay Patel9f49b682016-01-08 22:05:03 +0000957 if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {
958 assert(!Load->isVolatile() && "AST broken");
959 if (!Load->isSimple())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000960 return Changed;
Philip Reamesb54c8e62016-03-09 22:59:30 +0000961
962 if (!GuaranteedToExecute && !CanSpeculateLoad)
Dehao Chend55bc4c2016-05-05 00:54:54 +0000963 CanSpeculateLoad = isSafeToExecuteUnconditionally(
Sean Silva45835e72016-07-02 23:47:27 +0000964 *Load, DT, CurLoop, SafetyInfo, Preheader->getTerminator());
Sanjay Patel9f49b682016-01-08 22:05:03 +0000965 } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
Chris Lattner408a6842010-12-19 05:57:25 +0000966 // Stores *of* the pointer are not interesting, only stores *to* the
967 // pointer.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000968 if (UI->getOperand(1) != ASIV)
Chris Lattner408a6842010-12-19 05:57:25 +0000969 continue;
Sanjay Patel9f49b682016-01-08 22:05:03 +0000970 assert(!Store->isVolatile() && "AST broken");
971 if (!Store->isSimple())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000972 return Changed;
Eli Friedman0cdc1482011-07-20 21:37:47 +0000973
974 // Note that we only check GuaranteedToExecute inside the store case
975 // so that we do not introduce stores where they did not exist before
976 // (which would break the LLVM concurrency model).
977
978 // If the alignment of this instruction allows us to specify a more
979 // restrictive (and performant) alignment and if we are sure this
980 // instruction will be executed, update the alignment.
981 // Larger is better, with the exception of 0 being the best alignment.
Sanjay Patel9f49b682016-01-08 22:05:03 +0000982 unsigned InstAlignment = Store->getAlignment();
Anna Thomas67151352016-06-24 12:38:45 +0000983 if ((InstAlignment > Alignment || InstAlignment == 0) &&
984 Alignment != 0) {
Hal Finkel3d4269a2015-02-22 18:35:32 +0000985 if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
Eli Friedman0cdc1482011-07-20 21:37:47 +0000986 GuaranteedToExecute = true;
987 Alignment = InstAlignment;
988 }
Anna Thomas67151352016-06-24 12:38:45 +0000989 } else if (!GuaranteedToExecute) {
Dehao Chend55bc4c2016-05-05 00:54:54 +0000990 GuaranteedToExecute =
991 isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo);
Anna Thomas67151352016-06-24 12:38:45 +0000992 }
Philip Reamesb54c8e62016-03-09 22:59:30 +0000993
994 if (!GuaranteedToExecute && !CanSpeculateLoad) {
Dehao Chend55bc4c2016-05-05 00:54:54 +0000995 CanSpeculateLoad = isDereferenceableAndAlignedPointer(
996 Store->getPointerOperand(), Store->getAlignment(), MDL,
Sean Silva45835e72016-07-02 23:47:27 +0000997 Preheader->getTerminator(), DT);
Philip Reamesb54c8e62016-03-09 22:59:30 +0000998 }
Chris Lattnerbe901902010-09-06 05:11:24 +0000999 } else
Hal Finkel3d4269a2015-02-22 18:35:32 +00001000 return Changed; // Not a load or store.
Tobias Grosser4a5d9a92011-07-06 19:19:55 +00001001
Hal Finkelcc39b672014-07-24 12:16:19 +00001002 // Merge the AA tags.
Chris Lattnerf5cca682012-12-31 08:37:17 +00001003 if (LoopUses.empty()) {
Hal Finkelcc39b672014-07-24 12:16:19 +00001004 // On the first load/store, just take its AA tags.
1005 UI->getAAMetadata(AATags);
1006 } else if (AATags) {
1007 UI->getAAMetadata(AATags, /* Merge = */ true);
Chris Lattnerf5cca682012-12-31 08:37:17 +00001008 }
Chandler Carruthcdf47882014-03-09 03:16:01 +00001009
1010 LoopUses.push_back(UI);
Chris Lattner1dc98b42010-08-29 06:43:52 +00001011 }
1012 }
Tobias Grosser4a5d9a92011-07-06 19:19:55 +00001013
Philip Reamesb54c8e62016-03-09 22:59:30 +00001014 // Check legality per comment above. Otherwise, we can't promote.
1015 bool PromotionIsLegal = GuaranteedToExecute;
1016 if (!PromotionIsLegal && CanSpeculateLoad) {
1017 // If this is a thread local location, then we can insert stores along
1018 // paths which originally didn't have them without violating the memory
Dehao Chend55bc4c2016-05-05 00:54:54 +00001019 // model.
Philip Reamesb54c8e62016-03-09 22:59:30 +00001020 Value *Object = GetUnderlyingObject(SomePtr, MDL);
Dehao Chend55bc4c2016-05-05 00:54:54 +00001021 PromotionIsLegal =
1022 isAllocLikeFn(Object, TLI) && !PointerMayBeCaptured(Object, true, true);
Philip Reamesb54c8e62016-03-09 22:59:30 +00001023 }
1024 if (!PromotionIsLegal)
Hal Finkel3d4269a2015-02-22 18:35:32 +00001025 return Changed;
Tobias Grossera3928f52011-07-06 19:20:02 +00001026
David Majnemer219055f2016-01-04 17:42:19 +00001027 // Figure out the loop exits and their insertion points, if this is the
1028 // first promotion.
1029 if (ExitBlocks.empty()) {
1030 CurLoop->getUniqueExitBlocks(ExitBlocks);
1031 InsertPts.clear();
1032 InsertPts.reserve(ExitBlocks.size());
David Majnemerb33f3a22016-01-04 23:16:22 +00001033 for (BasicBlock *ExitBlock : ExitBlocks)
David Majnemer219055f2016-01-04 17:42:19 +00001034 InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
David Majnemer219055f2016-01-04 17:42:19 +00001035 }
1036
David Majnemerb33f3a22016-01-04 23:16:22 +00001037 // Can't insert into a catchswitch.
1038 for (BasicBlock *ExitBlock : ExitBlocks)
1039 if (isa<CatchSwitchInst>(ExitBlock->getTerminator()))
1040 return Changed;
1041
Chris Lattner1dc98b42010-08-29 06:43:52 +00001042 // Otherwise, this is safe to promote, lets do it!
Dehao Chend55bc4c2016-05-05 00:54:54 +00001043 DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " << *SomePtr
1044 << '\n');
Chris Lattner1dc98b42010-08-29 06:43:52 +00001045 Changed = true;
1046 ++NumPromoted;
1047
Eli Friedmanddf7f552011-05-27 20:31:51 +00001048 // Grab a debug location for the inserted loads/stores; given that the
1049 // inserted loads/stores have little relation to the original loads/stores,
1050 // this code just arbitrarily picks a location from one, since any debug
1051 // location is better than none.
1052 DebugLoc DL = LoopUses[0]->getDebugLoc();
1053
Chris Lattner1dc98b42010-08-29 06:43:52 +00001054 // We use the SSAUpdater interface to insert phi nodes as required.
Dehao Chend55bc4c2016-05-05 00:54:54 +00001055 SmallVector<PHINode *, 16> NewPHIs;
Chris Lattner1dc98b42010-08-29 06:43:52 +00001056 SSAUpdater SSA(&NewPHIs);
Dehao Chend55bc4c2016-05-05 00:54:54 +00001057 LoopPromoter Promoter(SomePtr, LoopUses, SSA, PointerMustAliases, ExitBlocks,
Hal Finkelcc39b672014-07-24 12:16:19 +00001058 InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags);
Tobias Grossera3928f52011-07-06 19:20:02 +00001059
Chris Lattnerb68ec5c2011-01-15 00:12:35 +00001060 // Set up the preheader to have a definition of the value. It is the live-out
1061 // value from the preheader that uses in the loop will use.
Dehao Chend55bc4c2016-05-05 00:54:54 +00001062 LoadInst *PreheaderLoad = new LoadInst(
1063 SomePtr, SomePtr->getName() + ".promoted", Preheader->getTerminator());
Tobias Grosser4a5d9a92011-07-06 19:19:55 +00001064 PreheaderLoad->setAlignment(Alignment);
Eli Friedmanddf7f552011-05-27 20:31:51 +00001065 PreheaderLoad->setDebugLoc(DL);
Dehao Chend55bc4c2016-05-05 00:54:54 +00001066 if (AATags)
1067 PreheaderLoad->setAAMetadata(AATags);
Chris Lattner1dc98b42010-08-29 06:43:52 +00001068 SSA.AddAvailableValue(Preheader, PreheaderLoad);
1069
Chris Lattnerb68ec5c2011-01-15 00:12:35 +00001070 // Rewrite all the loads in the loop and remember all the definitions from
1071 // stores in the loop.
1072 Promoter.run(LoopUses);
Eli Friedmanc5f22a72011-04-07 01:35:06 +00001073
1074 // If the SSAUpdater didn't use the load in the preheader, just zap it now.
1075 if (PreheaderLoad->use_empty())
1076 PreheaderLoad->eraseFromParent();
Hal Finkel3d4269a2015-02-22 18:35:32 +00001077
1078 return Changed;
Chris Lattnera51fa882002-08-22 21:39:55 +00001079}
Devang Patelb98a0972007-07-31 08:01:41 +00001080
Roman Gareev036c0882016-02-15 14:48:50 +00001081/// Returns an owning pointer to an alias set which incorporates aliasing info
Chandler Carruthad8cb382016-02-27 04:34:07 +00001082/// from L and all subloops of L.
Xinliang David Licbb5e022016-08-11 22:34:00 +00001083/// FIXME: In new pass manager, there is no helper function to handle loop
1084/// analysis such as cloneBasicBlockAnalysis, so the AST needs to be recomputed
Dehao Chen9cba1f42016-07-12 22:37:48 +00001085/// from scratch for every loop. Hook up with the helper functions when
1086/// available in the new pass manager to avoid redundant computation.
1087AliasSetTracker *
1088LoopInvariantCodeMotion::collectAliasInfoForLoop(Loop *L, LoopInfo *LI,
1089 AliasAnalysis *AA) {
Roman Gareev036c0882016-02-15 14:48:50 +00001090 AliasSetTracker *CurAST = nullptr;
Chandler Carruthad8cb382016-02-27 04:34:07 +00001091 SmallVector<Loop *, 4> RecomputeLoops;
Roman Gareev036c0882016-02-15 14:48:50 +00001092 for (Loop *InnerL : L->getSubLoops()) {
Chandler Carruthad8cb382016-02-27 04:34:07 +00001093 auto MapI = LoopToAliasSetMap.find(InnerL);
1094 // If the AST for this inner loop is missing it may have been merged into
1095 // some other loop's AST and then that loop unrolled, and so we need to
1096 // recompute it.
1097 if (MapI == LoopToAliasSetMap.end()) {
1098 RecomputeLoops.push_back(InnerL);
1099 continue;
1100 }
1101 AliasSetTracker *InnerAST = MapI->second;
Roman Gareev036c0882016-02-15 14:48:50 +00001102
1103 if (CurAST != nullptr) {
1104 // What if InnerLoop was modified by other passes ?
1105 CurAST->add(*InnerAST);
1106
1107 // Once we've incorporated the inner loop's AST into ours, we don't need
1108 // the subloop's anymore.
1109 delete InnerAST;
1110 } else {
1111 CurAST = InnerAST;
1112 }
Chandler Carruthad8cb382016-02-27 04:34:07 +00001113 LoopToAliasSetMap.erase(MapI);
Roman Gareev036c0882016-02-15 14:48:50 +00001114 }
1115 if (CurAST == nullptr)
1116 CurAST = new AliasSetTracker(*AA);
Chandler Carruthad8cb382016-02-27 04:34:07 +00001117
1118 auto mergeLoop = [&](Loop *L) {
1119 // Loop over the body of this loop, looking for calls, invokes, and stores.
1120 // Because subloops have already been incorporated into AST, we skip blocks
1121 // in subloops.
1122 for (BasicBlock *BB : L->blocks())
1123 if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops.
1124 CurAST->add(*BB); // Incorporate the specified basic block
1125 };
1126
1127 // Add everything from the sub loops that are no longer directly available.
1128 for (Loop *InnerL : RecomputeLoops)
1129 mergeLoop(InnerL);
1130
1131 // And merge in this loop.
1132 mergeLoop(L);
1133
Roman Gareev036c0882016-02-15 14:48:50 +00001134 return CurAST;
1135}
1136
Ashutosh Nema47802622015-08-13 11:18:35 +00001137/// Simple analysis hook. Clone alias set info.
Hal Finkel3d4269a2015-02-22 18:35:32 +00001138///
Dehao Chen9cba1f42016-07-12 22:37:48 +00001139void LegacyLICMPass::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
1140 Loop *L) {
1141 AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
Devang Patelb98a0972007-07-31 08:01:41 +00001142 if (!AST)
1143 return;
1144
1145 AST->copyValue(From, To);
1146}
1147
Hal Finkel3d4269a2015-02-22 18:35:32 +00001148/// Simple Analysis hook. Delete value V from alias set
1149///
Dehao Chen9cba1f42016-07-12 22:37:48 +00001150void LegacyLICMPass::deleteAnalysisValue(Value *V, Loop *L) {
1151 AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
Devang Patelb98a0972007-07-31 08:01:41 +00001152 if (!AST)
1153 return;
1154
1155 AST->deleteValue(V);
1156}
David Peixotto0d4d5e62014-09-24 16:48:31 +00001157
1158/// Simple Analysis hook. Delete value L from alias set map.
Hal Finkel3d4269a2015-02-22 18:35:32 +00001159///
Dehao Chen9cba1f42016-07-12 22:37:48 +00001160void LegacyLICMPass::deleteAnalysisLoop(Loop *L) {
1161 AliasSetTracker *AST = LICM.getLoopToAliasSetMap().lookup(L);
David Peixotto0d4d5e62014-09-24 16:48:31 +00001162 if (!AST)
1163 return;
1164
1165 delete AST;
Dehao Chen9cba1f42016-07-12 22:37:48 +00001166 LICM.getLoopToAliasSetMap().erase(L);
David Peixotto0d4d5e62014-09-24 16:48:31 +00001167}
Hal Finkel3d4269a2015-02-22 18:35:32 +00001168
Hal Finkel3d4269a2015-02-22 18:35:32 +00001169/// Return true if the body of this loop may store into the memory
1170/// location pointed to by V.
1171///
1172static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
Dehao Chend55bc4c2016-05-05 00:54:54 +00001173 const AAMDNodes &AAInfo,
Hal Finkel3d4269a2015-02-22 18:35:32 +00001174 AliasSetTracker *CurAST) {
1175 // Check to see if any of the basic blocks in CurLoop invalidate *V.
1176 return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
1177}
1178
1179/// Little predicate that returns true if the specified basic block is in
1180/// a subloop of the current one, not the current one itself.
1181///
1182static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1183 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
1184 return LI->getLoopFor(BB) != CurLoop;
1185}