blob: 331cd2d0a60746d81c1da065f2250bbbf92e97d8 [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
33#include "llvm/Transforms/Scalar.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"
Philip Reamesb54c8e62016-03-09 22:59:30 +000044#include "llvm/Analysis/MemoryBuiltins.h"
Chandler Carruthabfa3e52014-01-24 01:59:49 +000045#include "llvm/Analysis/ScalarEvolution.h"
Chandler Carruth7b560d42015-09-09 17:55:00 +000046#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000047#include "llvm/Analysis/TargetLibraryInfo.h"
Dan Gohman75d7d5e2011-12-14 23:49:11 +000048#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth1305dc32014-03-04 11:45:46 +000049#include "llvm/IR/CFG.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000050#include "llvm/IR/Constants.h"
51#include "llvm/IR/DataLayout.h"
52#include "llvm/IR/DerivedTypes.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000053#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000054#include "llvm/IR/Instructions.h"
55#include "llvm/IR/IntrinsicInst.h"
56#include "llvm/IR/LLVMContext.h"
Chris Lattner473988c2013-01-05 16:44:07 +000057#include "llvm/IR/Metadata.h"
Chandler Carruthaa0ab632014-03-04 12:09:19 +000058#include "llvm/IR/PredIteratorCache.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000059#include "llvm/Support/CommandLine.h"
60#include "llvm/Support/Debug.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000061#include "llvm/Support/raw_ostream.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000062#include "llvm/Transforms/Utils/Local.h"
Chandler Carruth8765cf72014-01-25 04:07:24 +000063#include "llvm/Transforms/Utils/LoopUtils.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000064#include "llvm/Transforms/Utils/SSAUpdater.h"
Chris Lattner6ec05f52002-05-10 22:44:58 +000065#include <algorithm>
Chris Lattnerc0517682003-12-09 17:18:00 +000066using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000067
Chandler Carruth964daaa2014-04-22 02:55:47 +000068#define DEBUG_TYPE "licm"
69
Chris Lattner79a42ac2006-12-19 21:40:18 +000070STATISTIC(NumSunk , "Number of instructions sunk out of loop");
71STATISTIC(NumHoisted , "Number of instructions hoisted out of loop");
72STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
73STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
74STATISTIC(NumPromoted , "Number of memory locations promoted to registers");
75
Dan Gohmand78c4002008-05-13 00:00:25 +000076static cl::opt<bool>
77DisablePromotion("disable-licm-promotion", cl::Hidden,
78 cl::desc("Disable memory promotion in LICM pass"));
Chris Lattner45d67d62003-02-24 03:52:32 +000079
Hal Finkel3d4269a2015-02-22 18:35:32 +000080static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
David Majnemer42a07302016-01-04 03:37:39 +000081static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
82 const LICMSafetyInfo *SafetyInfo);
Sanjoy Das7a2e2be2016-01-28 15:51:58 +000083static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
84 const LICMSafetyInfo *SafetyInfo);
Pete Cooper0cabcf22015-05-13 01:12:18 +000085static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
David Majnemer42a07302016-01-04 03:37:39 +000086 const Loop *CurLoop, AliasSetTracker *CurAST,
87 const LICMSafetyInfo *SafetyInfo);
Pete Cooper0cabcf22015-05-13 01:12:18 +000088static bool isGuaranteedToExecute(const Instruction &Inst,
89 const DominatorTree *DT,
90 const Loop *CurLoop,
91 const LICMSafetyInfo *SafetyInfo);
92static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
93 const DominatorTree *DT,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +000094 const TargetLibraryInfo *TLI,
Pete Cooper0cabcf22015-05-13 01:12:18 +000095 const Loop *CurLoop,
Philip Reamesb47b9c22015-05-22 02:14:05 +000096 const LICMSafetyInfo *SafetyInfo,
97 const Instruction *CtxI = nullptr);
Hal Finkel3d4269a2015-02-22 18:35:32 +000098static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
99 const AAMDNodes &AAInfo,
100 AliasSetTracker *CurAST);
David Majnemer42a07302016-01-04 03:37:39 +0000101static Instruction *
102CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
103 const LoopInfo *LI,
104 const LICMSafetyInfo *SafetyInfo);
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000105static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000106 DominatorTree *DT, TargetLibraryInfo *TLI,
107 Loop *CurLoop, AliasSetTracker *CurAST,
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000108 LICMSafetyInfo *SafetyInfo);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000109
Dan Gohmand78c4002008-05-13 00:00:25 +0000110namespace {
Chris Lattner2dd09db2009-09-02 06:11:42 +0000111 struct LICM : public LoopPass {
Nick Lewyckye7da2d62007-05-06 13:37:16 +0000112 static char ID; // Pass identification, replacement for typeid
Owen Anderson6c18d1a2010-10-19 17:21:58 +0000113 LICM() : LoopPass(ID) {
114 initializeLICMPass(*PassRegistry::getPassRegistry());
115 }
Devang Patel09f162c2007-05-01 21:15:47 +0000116
Craig Topper3e4c6972014-03-05 09:10:37 +0000117 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000118
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000119 /// This transformation requires natural loop information & requires that
120 /// loop preheaders be inserted into the CFG...
121 ///
Craig Topper3e4c6972014-03-05 09:10:37 +0000122 void getAnalysisUsage(AnalysisUsage &AU) const override {
Chris Lattner820d9712002-10-21 20:00:28 +0000123 AU.setPreservesCFG();
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000124 AU.addRequired<TargetLibraryInfoWrapperPass>();
Chandler Carruth31088a92016-02-19 10:45:18 +0000125 getLoopAnalysisUsage(AU);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000126 }
127
Matt Beaumont-Gayabfc4462012-12-04 05:41:27 +0000128 using llvm::Pass::doFinalization;
129
Craig Topper3e4c6972014-03-05 09:10:37 +0000130 bool doFinalization() override {
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000131 assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
Devang Patel69730c92007-03-07 04:41:30 +0000132 return false;
133 }
134
Chris Lattner6ec05f52002-05-10 22:44:58 +0000135 private:
Chris Lattner45d67d62003-02-24 03:52:32 +0000136 AliasAnalysis *AA; // Current AliasAnalysis information
Chris Lattnerc0517682003-12-09 17:18:00 +0000137 LoopInfo *LI; // Current LoopInfo
Chris Lattnerabe61ef2010-08-29 06:49:44 +0000138 DominatorTree *DT; // Dominator Tree for the current Loop.
Chris Lattnerc0517682003-12-09 17:18:00 +0000139
Chad Rosier43a33062011-12-02 01:26:24 +0000140 TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding.
141
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000142 // State that is updated as we process loops.
Chris Lattner45d67d62003-02-24 03:52:32 +0000143 bool Changed; // Set to true when we change anything.
144 BasicBlock *Preheader; // The preheader block of the current loop...
145 Loop *CurLoop; // The current loop we are working on...
Chris Lattner0592bb72003-03-03 23:32:45 +0000146 AliasSetTracker *CurAST; // AliasSet information for the current loop...
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000147 DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000148
Devang Patelb98a0972007-07-31 08:01:41 +0000149 /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
Craig Topper3e4c6972014-03-05 09:10:37 +0000150 void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
151 Loop *L) override;
Devang Patelb98a0972007-07-31 08:01:41 +0000152
153 /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
154 /// set.
Craig Topper3e4c6972014-03-05 09:10:37 +0000155 void deleteAnalysisValue(Value *V, Loop *L) override;
Devang Patelb98a0972007-07-31 08:01:41 +0000156
David Peixotto0d4d5e62014-09-24 16:48:31 +0000157 /// Simple Analysis hook. Delete loop L from alias set map.
158 void deleteAnalysisLoop(Loop *L) override;
Roman Gareev036c0882016-02-15 14:48:50 +0000159
Chandler Carruthad8cb382016-02-27 04:34:07 +0000160 AliasSetTracker *collectAliasInfoForLoop(Loop *L);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000161 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000162}
Chris Lattner6ec05f52002-05-10 22:44:58 +0000163
Dan Gohmand78c4002008-05-13 00:00:25 +0000164char LICM::ID = 0;
Owen Anderson8ac477f2010-10-12 19:48:12 +0000165INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
Chandler Carruth31088a92016-02-19 10:45:18 +0000166INITIALIZE_PASS_DEPENDENCY(LoopPass)
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000167INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
Owen Anderson8ac477f2010-10-12 19:48:12 +0000168INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
Dan Gohmand78c4002008-05-13 00:00:25 +0000169
Daniel Dunbar7f39e2d2008-10-22 23:32:42 +0000170Pass *llvm::createLICMPass() { return new LICM(); }
Chris Lattner6ec05f52002-05-10 22:44:58 +0000171
Devang Pateld8b1ceb2007-07-31 16:52:25 +0000172/// Hoist expressions out of the specified loop. Note, alias info for inner
Tobias Grossera3928f52011-07-06 19:20:02 +0000173/// loop is not preserved so it is not a good idea to run LICM multiple
Devang Pateld8b1ceb2007-07-31 16:52:25 +0000174/// times on one loop.
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000175///
Devang Patel69730c92007-03-07 04:41:30 +0000176bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
Paul Robinsonaf4e64d2014-02-06 00:07:05 +0000177 if (skipOptnoneFunction(L))
178 return false;
179
Chris Lattner45d67d62003-02-24 03:52:32 +0000180 Changed = false;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000181
Chris Lattner45d67d62003-02-24 03:52:32 +0000182 // Get our Loop and Alias Analysis information...
Chandler Carruth4f8f3072015-01-17 14:16:18 +0000183 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000184 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Chandler Carruth73523022014-01-13 13:07:17 +0000185 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
Chris Lattnera51fa882002-08-22 21:39:55 +0000186
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000187 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
Chad Rosier43a33062011-12-02 01:26:24 +0000188
Chandler Carruthfc258542014-02-11 12:52:27 +0000189 assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
190
Chandler Carruthad8cb382016-02-27 04:34:07 +0000191 CurAST = collectAliasInfoForLoop(L);
Tobias Grossera3928f52011-07-06 19:20:02 +0000192
Chris Lattner6ec05f52002-05-10 22:44:58 +0000193 CurLoop = L;
194
Chris Lattnerd57f3f52002-09-26 19:40:25 +0000195 // Get the preheader block to move instructions into...
196 Preheader = L->getLoopPreheader();
Chris Lattnerd57f3f52002-09-26 19:40:25 +0000197
Hal Finkel3d4269a2015-02-22 18:35:32 +0000198 // Compute loop safety information.
199 LICMSafetyInfo SafetyInfo;
200 computeLICMSafetyInfo(&SafetyInfo, CurLoop);
Nadav Rotem03dcd852012-09-04 10:25:04 +0000201
Chris Lattner6ec05f52002-05-10 22:44:58 +0000202 // We want to visit all of the instructions in this loop... that are not parts
203 // of our subloops (they have already had their invariants hoisted out of
204 // their loop, into this loop, so there is no need to process the BODIES of
205 // the subloops).
206 //
Chris Lattner64437692002-09-29 21:46:09 +0000207 // Traverse the body of the loop in depth first order on the dominator tree so
208 // that we are guaranteed to see definitions before we see uses. This allows
Nick Lewyckya0d49da2007-08-18 15:08:56 +0000209 // us to sink instructions in one pass, without iteration. After sinking
Chris Lattner547192d62003-12-19 07:22:45 +0000210 // instructions, we perform another pass to hoist them out of the loop.
Chris Lattner64437692002-09-29 21:46:09 +0000211 //
Dan Gohmana83ac2d2009-11-05 21:11:53 +0000212 if (L->hasDedicatedExits())
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000213 Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop,
214 CurAST, &SafetyInfo);
Dan Gohmana83ac2d2009-11-05 21:11:53 +0000215 if (Preheader)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000216 Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
Hal Finkel3d4269a2015-02-22 18:35:32 +0000217 CurLoop, CurAST, &SafetyInfo);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000218
Chris Lattner45d67d62003-02-24 03:52:32 +0000219 // Now that all loop invariants have been removed from the loop, promote any
Chris Lattner1dc98b42010-08-29 06:43:52 +0000220 // memory references to scalars that we can.
Chandler Carruthcc497b62014-01-24 02:24:47 +0000221 if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
Dan Gohmanb9487362012-08-08 00:00:26 +0000222 SmallVector<BasicBlock *, 8> ExitBlocks;
223 SmallVector<Instruction *, 8> InsertPts;
Chandler Carruthfc258542014-02-11 12:52:27 +0000224 PredIteratorCache PIC;
Dan Gohmanb9487362012-08-08 00:00:26 +0000225
Chris Lattner1dc98b42010-08-29 06:43:52 +0000226 // Loop over all of the alias sets in the tracker object.
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000227 for (AliasSet &AS : *CurAST)
228 Changed |= promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts,
Philip Reamesb54c8e62016-03-09 22:59:30 +0000229 PIC, LI, DT, TLI, CurLoop,
Hal Finkel3d4269a2015-02-22 18:35:32 +0000230 CurAST, &SafetyInfo);
Chandler Carruth16651522014-02-01 13:35:14 +0000231
232 // Once we have promoted values across the loop body we have to recursively
233 // reform LCSSA as any nested loop may now have values defined within the
234 // loop used in the outer loop.
235 // FIXME: This is really heavy handed. It would be a bit better to use an
236 // SSAUpdater strategy during promotion that was LCSSA aware and reformed
237 // it as it went.
Chandler Carruth2f1fd162015-08-17 02:08:17 +0000238 if (Changed) {
239 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
240 formLCSSARecursively(*L, *DT, LI, SEWP ? &SEWP->getSE() : nullptr);
241 }
Chris Lattner1dc98b42010-08-29 06:43:52 +0000242 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000243
Chandler Carruthfc258542014-02-11 12:52:27 +0000244 // Check that neither this loop nor its parent have had LCSSA broken. LICM is
245 // specifically moving instructions across the loop boundary and so it is
246 // especially in need of sanity checking here.
247 assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
248 assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
249 "Parent loop not left in LCSSA form after LICM!");
Chandler Carruth8765cf72014-01-25 04:07:24 +0000250
Chris Lattner6ec05f52002-05-10 22:44:58 +0000251 // Clear out loops state information for the next iteration
Craig Topperf40110f2014-04-25 05:29:35 +0000252 CurLoop = nullptr;
253 Preheader = nullptr;
Devang Patel69730c92007-03-07 04:41:30 +0000254
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000255 // If this loop is nested inside of another one, save the alias information
256 // for when we process the outer loop.
257 if (L->getParentLoop())
258 LoopToAliasSetMap[L] = CurAST;
259 else
260 delete CurAST;
Devang Patel69730c92007-03-07 04:41:30 +0000261 return Changed;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000262}
263
Hal Finkel3d4269a2015-02-22 18:35:32 +0000264/// Walk the specified region of the CFG (defined by all blocks dominated by
265/// the specified block, and that are in the current loop) in reverse depth
266/// first order w.r.t the DominatorTree. This allows us to visit uses before
267/// definitions, allowing us to sink a loop body in one pass without iteration.
Chris Lattner547192d62003-12-19 07:22:45 +0000268///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000269bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
270 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
271 AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
Chris Lattner547192d62003-12-19 07:22:45 +0000272
Hal Finkel3d4269a2015-02-22 18:35:32 +0000273 // Verify inputs.
274 assert(N != nullptr && AA != nullptr && LI != nullptr &&
275 DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
276 SafetyInfo != nullptr && "Unexpected input to sinkRegion");
277
Hal Finkel3d4269a2015-02-22 18:35:32 +0000278 BasicBlock *BB = N->getBlock();
Chris Lattner547192d62003-12-19 07:22:45 +0000279 // If this subregion is not in the top level loop at all, exit.
Sanjay Patel99133222016-01-13 23:01:57 +0000280 if (!CurLoop->contains(BB)) return false;
Chris Lattner547192d62003-12-19 07:22:45 +0000281
Chris Lattner263f8042010-08-29 18:22:25 +0000282 // We are processing blocks in reverse dfo, so process children first.
Sanjay Patel99133222016-01-13 23:01:57 +0000283 bool Changed = false;
Devang Patelbdd1aae2007-06-04 00:32:22 +0000284 const std::vector<DomTreeNode*> &Children = N->getChildren();
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000285 for (DomTreeNode *Child : Children)
286 Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
287
Chris Lattner547192d62003-12-19 07:22:45 +0000288 // Only need to process the contents of this block if it is not part of a
289 // subloop (which would already have been processed).
Hal Finkel3d4269a2015-02-22 18:35:32 +0000290 if (inSubLoop(BB,CurLoop,LI)) return Changed;
Chris Lattner547192d62003-12-19 07:22:45 +0000291
Chris Lattner91846012003-12-19 08:18:16 +0000292 for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) {
293 Instruction &I = *--II;
Tobias Grossera3928f52011-07-06 19:20:02 +0000294
Chris Lattner263f8042010-08-29 18:22:25 +0000295 // If the instruction is dead, we would try to sink it because it isn't used
296 // in the loop, instead, just delete it.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000297 if (isInstructionTriviallyDead(&I, TLI)) {
Chris Lattnerf58382e2010-08-29 18:42:23 +0000298 DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
Chris Lattner263f8042010-08-29 18:22:25 +0000299 ++II;
300 CurAST->deleteValue(&I);
301 I.eraseFromParent();
302 Changed = true;
303 continue;
304 }
Misha Brukmanb1c93172005-04-21 23:48:37 +0000305
Chris Lattner547192d62003-12-19 07:22:45 +0000306 // Check to see if we can sink this instruction to the exit blocks
307 // of the loop. We can do this if the all users of the instruction are
308 // outside of the loop. In this case, it doesn't even matter if the
309 // operands of the instruction are loop invariant.
310 //
David Majnemer42a07302016-01-04 03:37:39 +0000311 if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000312 canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
Chris Lattner91846012003-12-19 08:18:16 +0000313 ++II;
David Majnemer42a07302016-01-04 03:37:39 +0000314 Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo);
Chris Lattner91846012003-12-19 08:18:16 +0000315 }
Chris Lattner547192d62003-12-19 07:22:45 +0000316 }
Hal Finkel3d4269a2015-02-22 18:35:32 +0000317 return Changed;
Chris Lattner547192d62003-12-19 07:22:45 +0000318}
319
Hal Finkel3d4269a2015-02-22 18:35:32 +0000320/// Walk the specified region of the CFG (defined by all blocks dominated by
321/// the specified block, and that are in the current loop) in depth first
322/// order w.r.t the DominatorTree. This allows us to visit definitions before
323/// uses, allowing us to hoist a loop body in one pass without iteration.
Chris Lattner64437692002-09-29 21:46:09 +0000324///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000325bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
326 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
327 AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
Hal Finkel3d4269a2015-02-22 18:35:32 +0000328 // Verify inputs.
329 assert(N != nullptr && AA != nullptr && LI != nullptr &&
330 DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
331 SafetyInfo != nullptr && "Unexpected input to hoistRegion");
Sanjay Patel99133222016-01-13 23:01:57 +0000332
Owen Andersonc24701e2007-04-24 06:40:39 +0000333 BasicBlock *BB = N->getBlock();
Sanjay Patel99133222016-01-13 23:01:57 +0000334
Chris Lattner05e86302002-09-29 22:26:07 +0000335 // If this subregion is not in the top level loop at all, exit.
Sanjay Patel99133222016-01-13 23:01:57 +0000336 if (!CurLoop->contains(BB)) return false;
337
Chris Lattneraaaea512003-12-10 06:41:05 +0000338 // Only need to process the contents of this block if it is not part of a
339 // subloop (which would already have been processed).
Sanjay Patel99133222016-01-13 23:01:57 +0000340 bool Changed = false;
Hal Finkel3d4269a2015-02-22 18:35:32 +0000341 if (!inSubLoop(BB, CurLoop, LI))
Chris Lattneraaaea512003-12-10 06:41:05 +0000342 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
343 Instruction &I = *II++;
Chris Lattner030f0202010-08-31 23:00:16 +0000344 // Try constant folding this instruction. If all the operands are
345 // constants, it is technically hoistable, but it would be better to just
346 // fold it.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000347 if (Constant *C = ConstantFoldInstruction(
348 &I, I.getModule()->getDataLayout(), TLI)) {
Chris Lattner030f0202010-08-31 23:00:16 +0000349 DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n');
350 CurAST->copyValue(&I, C);
351 CurAST->deleteValue(&I);
352 I.replaceAllUsesWith(C);
353 I.eraseFromParent();
354 continue;
355 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000356
Chris Lattner547192d62003-12-19 07:22:45 +0000357 // Try hoisting the instruction out to the preheader. We can only do this
358 // if all of the operands of the instruction are loop invariant and if it
359 // is safe to hoist the instruction.
360 //
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000361 if (CurLoop->hasLoopInvariantOperands(&I) &&
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000362 canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
Philip Reamesb47b9c22015-05-22 02:14:05 +0000363 isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
364 CurLoop->getLoopPreheader()->getTerminator()))
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000365 Changed |= hoist(I, DT, CurLoop, SafetyInfo);
Chris Lattner030f0202010-08-31 23:00:16 +0000366 }
Chris Lattner64437692002-09-29 21:46:09 +0000367
Devang Patelbdd1aae2007-06-04 00:32:22 +0000368 const std::vector<DomTreeNode*> &Children = N->getChildren();
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000369 for (DomTreeNode *Child : Children)
370 Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000371 return Changed;
372}
373
374/// Computes loop safety information, checks loop body & header
Benjamin Kramerdf005cb2015-08-08 18:27:36 +0000375/// for the possibility of may throw exception.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000376///
377void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) {
378 assert(CurLoop != nullptr && "CurLoop cant be null");
379 BasicBlock *Header = CurLoop->getHeader();
380 // Setting default safety values.
381 SafetyInfo->MayThrow = false;
382 SafetyInfo->HeaderMayThrow = false;
Benjamin Kramerdf005cb2015-08-08 18:27:36 +0000383 // Iterate over header and compute safety info.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000384 for (BasicBlock::iterator I = Header->begin(), E = Header->end();
385 (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
386 SafetyInfo->HeaderMayThrow |= I->mayThrow();
387
388 SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
389 // Iterate over loop instructions and compute safety info.
390 for (Loop::block_iterator BB = CurLoop->block_begin(),
391 BBE = CurLoop->block_end(); (BB != BBE) && !SafetyInfo->MayThrow ; ++BB)
392 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
393 (I != E) && !SafetyInfo->MayThrow; ++I)
394 SafetyInfo->MayThrow |= I->mayThrow();
David Majnemer42a07302016-01-04 03:37:39 +0000395
396 // Compute funclet colors if we might sink/hoist in a function with a funclet
397 // personality routine.
398 Function *Fn = CurLoop->getHeader()->getParent();
399 if (Fn->hasPersonalityFn())
400 if (Constant *PersonalityFn = Fn->getPersonalityFn())
401 if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
402 SafetyInfo->BlockColors = colorEHFunclets(*Fn);
Chris Lattner64437692002-09-29 21:46:09 +0000403}
404
Chris Lattneraaaea512003-12-10 06:41:05 +0000405/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this
406/// instruction.
407///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000408bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000409 TargetLibraryInfo *TLI, Loop *CurLoop,
410 AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
Chris Lattner65c11932003-12-09 19:32:44 +0000411 // Loads have extra constraints we have to verify before we can hoist them.
412 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
Eli Friedman91386c72011-08-15 20:52:09 +0000413 if (!LI->isUnordered())
414 return false; // Don't hoist volatile/atomic loads!
Chris Lattner65c11932003-12-09 19:32:44 +0000415
Chris Lattner8a8fb902008-07-23 05:06:28 +0000416 // Loads from constant memory are always safe to move, even if they end up
417 // in the same alias set as something that ends up being modified.
Dan Gohmancbc6ebb2009-11-19 19:00:10 +0000418 if (AA->pointsToConstantMemory(LI->getOperand(0)))
Chris Lattner8a8fb902008-07-23 05:06:28 +0000419 return true;
Philip Reames5a3f5f72014-10-21 00:13:20 +0000420 if (LI->getMetadata(LLVMContext::MD_invariant_load))
Pete Cooper9ee22092011-11-08 19:30:00 +0000421 return true;
Tobias Grossera3928f52011-07-06 19:20:02 +0000422
Chris Lattner65c11932003-12-09 19:32:44 +0000423 // Don't hoist loads which have may-aliased stores in loop.
Dan Gohmanf372cf82010-10-19 22:54:46 +0000424 uint64_t Size = 0;
Chris Lattnerb1374092004-11-26 21:20:09 +0000425 if (LI->getType()->isSized())
Chandler Carruth50fee932015-08-06 02:05:46 +0000426 Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
Hal Finkelcc39b672014-07-24 12:16:19 +0000427
428 AAMDNodes AAInfo;
429 LI->getAAMetadata(AAInfo);
430
Hal Finkel3d4269a2015-02-22 18:35:32 +0000431 return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
Chris Lattner20cda262004-03-15 04:11:30 +0000432 } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
Eli Friedman942e1c12011-05-27 18:37:52 +0000433 // Don't sink or hoist dbg info; it's legal, but not useful.
434 if (isa<DbgInfoIntrinsic>(I))
435 return false;
436
David Majnemer42a07302016-01-04 03:37:39 +0000437 // Don't sink calls which can throw.
438 if (CI->mayThrow())
439 return false;
440
Eli Friedman942e1c12011-05-27 18:37:52 +0000441 // Handle simple cases by querying alias analysis.
Chandler Carruth194f59c2015-07-22 23:15:57 +0000442 FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
443 if (Behavior == FMRB_DoesNotAccessMemory)
Duncan Sands68b6f502007-12-01 07:51:45 +0000444 return true;
Dan Gohman0f175072010-11-09 19:58:21 +0000445 if (AliasAnalysis::onlyReadsMemory(Behavior)) {
Philip Reames5f994232015-09-21 22:27:59 +0000446 // A readonly argmemonly function only reads from memory pointed to by
447 // it's arguments with arbitrary offsets. If we can prove there are no
448 // writes to this memory in the loop, we can hoist or sink.
449 if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
450 for (Value *Op : CI->arg_operands())
451 if (Op->getType()->isPointerTy() &&
452 pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize,
453 AAMDNodes(), CurAST))
454 return false;
455 return true;
456 }
Duncan Sands68b6f502007-12-01 07:51:45 +0000457 // If this call only reads from memory and there are no writes to memory
458 // in the loop, we can hoist or sink the call as appropriate.
459 bool FoundMod = false;
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000460 for (AliasSet &AS : *CurAST) {
Duncan Sands68b6f502007-12-01 07:51:45 +0000461 if (!AS.isForwardingAliasSet() && AS.isMod()) {
462 FoundMod = true;
463 break;
Chris Lattner20cda262004-03-15 04:11:30 +0000464 }
Chris Lattner20cda262004-03-15 04:11:30 +0000465 }
Duncan Sands68b6f502007-12-01 07:51:45 +0000466 if (!FoundMod) return true;
Chris Lattner20cda262004-03-15 04:11:30 +0000467 }
468
Nadav Rotem03dcd852012-09-04 10:25:04 +0000469 // FIXME: This should use mod/ref information to see if we can hoist or
470 // sink the call.
Misha Brukmanb1c93172005-04-21 23:48:37 +0000471
Chris Lattner20cda262004-03-15 04:11:30 +0000472 return false;
Chris Lattner65c11932003-12-09 19:32:44 +0000473 }
474
Nadav Rotem03dcd852012-09-04 10:25:04 +0000475 // Only these instructions are hoistable/sinkable.
Benjamin Kramer130fcde2013-01-09 18:12:03 +0000476 if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
477 !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
478 !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
479 !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
480 !isa<InsertValueInst>(I))
481 return false;
Nadav Rotem03dcd852012-09-04 10:25:04 +0000482
Philip Reamesb47b9c22015-05-22 02:14:05 +0000483 // TODO: Plumb the context instruction through to make hoisting and sinking
484 // more powerful. Hoisting of loads already works due to the special casing
485 // above.
486 return isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
487 nullptr);
Chris Lattneraaaea512003-12-10 06:41:05 +0000488}
489
Hal Finkel3d4269a2015-02-22 18:35:32 +0000490/// Returns true if a PHINode is a trivially replaceable with an
Chandler Carruth8765cf72014-01-25 04:07:24 +0000491/// Instruction.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000492/// This is true when all incoming values are that instruction.
493/// This pattern occurs most often with LCSSA PHI nodes.
Chandler Carruth8765cf72014-01-25 04:07:24 +0000494///
Pete Cooper47e80cd2015-05-12 20:05:20 +0000495static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
Pete Cooper833f34d2015-05-12 20:05:31 +0000496 for (const Value *IncValue : PN.incoming_values())
497 if (IncValue != &I)
Chandler Carruth8765cf72014-01-25 04:07:24 +0000498 return false;
499
500 return true;
501}
502
Hal Finkel3d4269a2015-02-22 18:35:32 +0000503/// Return true if the only users of this instruction are outside of
504/// the loop. If this is true, we can sink the instruction to the exit
505/// blocks of the loop.
Chris Lattneraaaea512003-12-10 06:41:05 +0000506///
David Majnemer42a07302016-01-04 03:37:39 +0000507static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
508 const LICMSafetyInfo *SafetyInfo) {
509 const auto &BlockColors = SafetyInfo->BlockColors;
Pete Cooper0cabcf22015-05-13 01:12:18 +0000510 for (const User *U : I.users()) {
511 const Instruction *UI = cast<Instruction>(U);
512 if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
David Majnemer42a07302016-01-04 03:37:39 +0000513 const BasicBlock *BB = PN->getParent();
514 // We cannot sink uses in catchswitches.
515 if (isa<CatchSwitchInst>(BB->getTerminator()))
516 return false;
517
518 // We need to sink a callsite to a unique funclet. Avoid sinking if the
519 // phi use is too muddled.
520 if (isa<CallInst>(I))
521 if (!BlockColors.empty() &&
522 BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
523 return false;
524
Chandler Carruth8765cf72014-01-25 04:07:24 +0000525 // A PHI node where all of the incoming values are this instruction are
526 // special -- they can just be RAUW'ed with the instruction and thus
527 // don't require a use in the predecessor. This is a particular important
528 // special case because it is the pattern found in LCSSA form.
529 if (isTriviallyReplacablePHI(*PN, I)) {
530 if (CurLoop->contains(PN))
531 return false;
532 else
533 continue;
534 }
535
536 // Otherwise, PHI node uses occur in predecessor blocks if the incoming
537 // values. Check for such a use being inside the loop.
Chris Lattner34399dd2003-12-11 22:23:32 +0000538 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
539 if (PN->getIncomingValue(i) == &I)
540 if (CurLoop->contains(PN->getIncomingBlock(i)))
541 return false;
Chandler Carruth8765cf72014-01-25 04:07:24 +0000542
543 continue;
Chris Lattner34399dd2003-12-11 22:23:32 +0000544 }
Chandler Carruth8765cf72014-01-25 04:07:24 +0000545
Chandler Carruthcdf47882014-03-09 03:16:01 +0000546 if (CurLoop->contains(UI))
Chandler Carruth8765cf72014-01-25 04:07:24 +0000547 return false;
Chris Lattner34399dd2003-12-11 22:23:32 +0000548 }
Chris Lattneraaaea512003-12-10 06:41:05 +0000549 return true;
550}
551
David Majnemer42a07302016-01-04 03:37:39 +0000552static Instruction *
553CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
554 const LoopInfo *LI,
555 const LICMSafetyInfo *SafetyInfo) {
556 Instruction *New;
557 if (auto *CI = dyn_cast<CallInst>(&I)) {
558 const auto &BlockColors = SafetyInfo->BlockColors;
559
560 // Sinking call-sites need to be handled differently from other
561 // instructions. The cloned call-site needs a funclet bundle operand
562 // appropriate for it's location in the CFG.
563 SmallVector<OperandBundleDef, 1> OpBundles;
564 for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
565 BundleIdx != BundleEnd; ++BundleIdx) {
566 OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
567 if (Bundle.getTagID() == LLVMContext::OB_funclet)
568 continue;
569
570 OpBundles.emplace_back(Bundle);
571 }
572
573 if (!BlockColors.empty()) {
574 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
575 assert(CV.size() == 1 && "non-unique color for exit block!");
576 BasicBlock *BBColor = CV.front();
577 Instruction *EHPad = BBColor->getFirstNonPHI();
578 if (EHPad->isEHPad())
579 OpBundles.emplace_back("funclet", EHPad);
580 }
581
582 New = CallInst::Create(CI, OpBundles);
583 } else {
584 New = I.clone();
585 }
586
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000587 ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
588 if (!I.getName().empty()) New->setName(I.getName() + ".le");
589
590 // Build LCSSA PHI nodes for any in-loop operands. Note that this is
591 // particularly cheap because we can rip off the PHI node that we're
592 // replacing for the number and blocks of the predecessors.
593 // OPT: If this shows up in a profile, we can instead finish sinking all
594 // invariant instructions, and then walk their operands to re-establish
595 // LCSSA. That will eliminate creating PHI nodes just to nuke them when
596 // sinking bottom-up.
597 for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
598 ++OI)
599 if (Instruction *OInst = dyn_cast<Instruction>(*OI))
600 if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
601 if (!OLoop->contains(&PN)) {
602 PHINode *OpPN =
603 PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000604 OInst->getName() + ".lcssa", &ExitBlock.front());
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000605 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
606 OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
607 *OI = OpPN;
608 }
609 return New;
610}
611
Hal Finkel3d4269a2015-02-22 18:35:32 +0000612/// When an instruction is found to only be used outside of the loop, this
613/// function moves it to the exit blocks and patches up SSA form as needed.
Chris Lattner91846012003-12-19 08:18:16 +0000614/// This method is guaranteed to remove the original instruction from its
615/// position, and may either delete it or move it to outside of the loop.
Chris Lattneraaaea512003-12-10 06:41:05 +0000616///
Pete Cooper0cabcf22015-05-13 01:12:18 +0000617static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
David Majnemer42a07302016-01-04 03:37:39 +0000618 const Loop *CurLoop, AliasSetTracker *CurAST,
619 const LICMSafetyInfo *SafetyInfo) {
Nick Lewycky299c6df2010-07-30 20:27:01 +0000620 DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
Hal Finkel3d4269a2015-02-22 18:35:32 +0000621 bool Changed = false;
Chris Lattner55c21132003-12-10 20:43:29 +0000622 if (isa<LoadInst>(I)) ++NumMovedLoads;
Chris Lattner20cda262004-03-15 04:11:30 +0000623 else if (isa<CallInst>(I)) ++NumMovedCalls;
Chris Lattner55c21132003-12-10 20:43:29 +0000624 ++NumSunk;
625 Changed = true;
626
Chandler Carruthfc258542014-02-11 12:52:27 +0000627#ifndef NDEBUG
628 SmallVector<BasicBlock *, 32> ExitBlocks;
629 CurLoop->getUniqueExitBlocks(ExitBlocks);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000630 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
631 ExitBlocks.end());
Chandler Carruthfc258542014-02-11 12:52:27 +0000632#endif
Chandler Carruth8765cf72014-01-25 04:07:24 +0000633
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000634 // Clones of this instruction. Don't create more than one per exit block!
635 SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
636
Chandler Carruthfc258542014-02-11 12:52:27 +0000637 // If this instruction is only used outside of the loop, then all users are
638 // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
639 // the instruction.
640 while (!I.use_empty()) {
David Majnemer6bc83e02015-07-12 03:53:05 +0000641 Value::user_iterator UI = I.user_begin();
642 auto *User = cast<Instruction>(*UI);
David Majnemer49428102014-09-02 16:22:00 +0000643 if (!DT->isReachableFromEntry(User->getParent())) {
644 User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
645 continue;
646 }
Chandler Carruthfc258542014-02-11 12:52:27 +0000647 // The user must be a PHI node.
David Majnemer49428102014-09-02 16:22:00 +0000648 PHINode *PN = cast<PHINode>(User);
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000649
David Majnemer6bc83e02015-07-12 03:53:05 +0000650 // Surprisingly, instructions can be used outside of loops without any
651 // exits. This can only happen in PHI nodes if the incoming block is
652 // unreachable.
653 Use &U = UI.getUse();
654 BasicBlock *BB = PN->getIncomingBlock(U);
655 if (!DT->isReachableFromEntry(BB)) {
656 U = UndefValue::get(I.getType());
657 continue;
658 }
659
Chandler Carruthfc258542014-02-11 12:52:27 +0000660 BasicBlock *ExitBlock = PN->getParent();
661 assert(ExitBlockSet.count(ExitBlock) &&
662 "The LCSSA PHI is not in an exit block!");
663
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000664 Instruction *New;
665 auto It = SunkCopies.find(ExitBlock);
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000666 if (It != SunkCopies.end())
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000667 New = It->second;
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000668 else
669 New = SunkCopies[ExitBlock] =
David Majnemer42a07302016-01-04 03:37:39 +0000670 CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
Chandler Carruthfc258542014-02-11 12:52:27 +0000671
672 PN->replaceAllUsesWith(New);
673 PN->eraseFromParent();
Chris Lattnercd96b4d2010-08-29 04:28:20 +0000674 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000675
Chris Lattner1a1ed692010-08-29 18:00:00 +0000676 CurAST->deleteValue(&I);
Chandler Carruthfc258542014-02-11 12:52:27 +0000677 I.eraseFromParent();
Hal Finkel3d4269a2015-02-22 18:35:32 +0000678 return Changed;
Chris Lattneraaaea512003-12-10 06:41:05 +0000679}
Chris Lattner64437692002-09-29 21:46:09 +0000680
Hal Finkel3d4269a2015-02-22 18:35:32 +0000681/// When an instruction is found to only use loop invariant operands that
682/// is safe to hoist, this instruction is called to do the dirty work.
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000683///
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000684static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
685 const LICMSafetyInfo *SafetyInfo) {
686 auto *Preheader = CurLoop->getLoopPreheader();
David Greene0fd86222010-01-05 01:27:30 +0000687 DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": "
Evan Chengf8158612009-10-12 22:25:23 +0000688 << I << "\n");
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000689
690 // Metadata can be dependent on conditions we are hoisting above.
691 // Conservatively strip all metadata on the instruction unless we were
692 // guaranteed to execute I if we entered the loop, in which case the metadata
693 // is valid in the loop preheader.
694 if (I.hasMetadataOtherThanDebugLoc() &&
695 // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
696 // time in isGuaranteedToExecute if we don't actually have anything to
697 // drop. It is a compile time optimization, not required for correctness.
698 !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
699 I.dropUnknownNonDebugMetadata();
700
Chris Lattner6ac06592010-08-29 18:18:40 +0000701 // Move the new node to the Preheader, before its terminator.
702 I.moveBefore(Preheader->getTerminator());
Misha Brukmanb1c93172005-04-21 23:48:37 +0000703
Chris Lattneraaaea512003-12-10 06:41:05 +0000704 if (isa<LoadInst>(I)) ++NumMovedLoads;
Chris Lattner20cda262004-03-15 04:11:30 +0000705 else if (isa<CallInst>(I)) ++NumMovedCalls;
Chris Lattner718b2212002-09-26 16:38:03 +0000706 ++NumHoisted;
Hal Finkel3d4269a2015-02-22 18:35:32 +0000707 return true;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000708}
709
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000710/// Only sink or hoist an instruction if it is not a trapping instruction,
711/// or if the instruction is known not to trap when moved to the preheader.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000712/// or if it is a trapping instruction and is guaranteed to execute.
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000713static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
Pete Cooper0cabcf22015-05-13 01:12:18 +0000714 const DominatorTree *DT,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000715 const TargetLibraryInfo *TLI,
Pete Cooper0cabcf22015-05-13 01:12:18 +0000716 const Loop *CurLoop,
Philip Reamesb47b9c22015-05-22 02:14:05 +0000717 const LICMSafetyInfo *SafetyInfo,
718 const Instruction *CtxI) {
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000719 if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
Eli Friedmanb8f6a4f2009-07-17 04:28:42 +0000720 return true;
Misha Brukmanb1c93172005-04-21 23:48:37 +0000721
Hal Finkel3d4269a2015-02-22 18:35:32 +0000722 return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
Eli Friedman0cdc1482011-07-20 21:37:47 +0000723}
724
Pete Cooper0cabcf22015-05-13 01:12:18 +0000725static bool isGuaranteedToExecute(const Instruction &Inst,
726 const DominatorTree *DT,
727 const Loop *CurLoop,
728 const LICMSafetyInfo * SafetyInfo) {
Nadav Rotem03dcd852012-09-04 10:25:04 +0000729
Philip Reamesb35f46c2014-12-29 23:00:57 +0000730 // We have to check to make sure that the instruction dominates all
Chris Lattnerc0517682003-12-09 17:18:00 +0000731 // of the exit blocks. If it doesn't, then there is a path out of the loop
732 // which does not execute this instruction, so we can't hoist it.
Tanya Lattner57c03df2003-08-05 18:45:46 +0000733
Chris Lattnerc0517682003-12-09 17:18:00 +0000734 // If the instruction is in the header block for the loop (which is very
735 // common), it is always guaranteed to dominate the exit blocks. Since this
736 // is a common case, and can save some work, check it now.
Chris Lattneraaaea512003-12-10 06:41:05 +0000737 if (Inst.getParent() == CurLoop->getHeader())
Philip Reamesb35f46c2014-12-29 23:00:57 +0000738 // If there's a throw in the header block, we can't guarantee we'll reach
739 // Inst.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000740 return !SafetyInfo->HeaderMayThrow;
Philip Reamesb35f46c2014-12-29 23:00:57 +0000741
742 // Somewhere in this loop there is an instruction which may throw and make us
743 // exit the loop.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000744 if (SafetyInfo->MayThrow)
Philip Reamesb35f46c2014-12-29 23:00:57 +0000745 return false;
Tanya Lattner57c03df2003-08-05 18:45:46 +0000746
Chris Lattnerc0517682003-12-09 17:18:00 +0000747 // Get the exit blocks for the current loop.
Devang Patelb5933bb2007-08-21 00:31:24 +0000748 SmallVector<BasicBlock*, 8> ExitBlocks;
Chris Lattner35eaa552004-04-18 22:15:13 +0000749 CurLoop->getExitBlocks(ExitBlocks);
Chris Lattnerc0517682003-12-09 17:18:00 +0000750
Chris Lattner27497ec2011-01-02 18:45:39 +0000751 // Verify that the block dominates each of the exit blocks of the loop.
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000752 for (BasicBlock *ExitBlock : ExitBlocks)
753 if (!DT->dominates(Inst.getParent(), ExitBlock))
Chris Lattneraaaea512003-12-10 06:41:05 +0000754 return false;
Misha Brukmanb1c93172005-04-21 23:48:37 +0000755
Nick Lewycky78ee67e2012-05-01 04:03:01 +0000756 // As a degenerate case, if the loop is statically infinite then we haven't
757 // proven anything since there are no exit blocks.
758 if (ExitBlocks.empty())
759 return false;
760
Tanya Lattner57c03df2003-08-05 18:45:46 +0000761 return true;
762}
763
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000764namespace {
765 class LoopPromoter : public LoadAndStorePromoter {
766 Value *SomePtr; // Designated pointer to store to.
Craig Topper71b7b682014-08-21 05:55:13 +0000767 SmallPtrSetImpl<Value*> &PointerMustAliases;
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000768 SmallVectorImpl<BasicBlock*> &LoopExitBlocks;
Dan Gohmanb9487362012-08-08 00:00:26 +0000769 SmallVectorImpl<Instruction*> &LoopInsertPts;
Chandler Carruthfc258542014-02-11 12:52:27 +0000770 PredIteratorCache &PredCache;
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000771 AliasSetTracker &AST;
Chandler Carruthfc258542014-02-11 12:52:27 +0000772 LoopInfo &LI;
Eli Friedmanddf7f552011-05-27 20:31:51 +0000773 DebugLoc DL;
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000774 int Alignment;
Hal Finkelcc39b672014-07-24 12:16:19 +0000775 AAMDNodes AATags;
Chandler Carruthfc258542014-02-11 12:52:27 +0000776
777 Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
778 if (Instruction *I = dyn_cast<Instruction>(V))
779 if (Loop *L = LI.getLoopFor(I->getParent()))
780 if (!L->contains(BB)) {
781 // We need to create an LCSSA PHI node for the incoming value and
782 // store that.
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000783 PHINode *PN =
784 PHINode::Create(I->getType(), PredCache.size(BB),
785 I->getName() + ".lcssa", &BB->front());
Daniel Berlinb4e7a4a2015-04-21 21:11:50 +0000786 for (BasicBlock *Pred : PredCache.get(BB))
787 PN->addIncoming(I, Pred);
Chandler Carruthfc258542014-02-11 12:52:27 +0000788 return PN;
789 }
790 return V;
791 }
792
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000793 public:
Pete Cooper41e0ee32015-05-13 01:12:16 +0000794 LoopPromoter(Value *SP,
795 ArrayRef<const Instruction *> Insts,
Craig Topper71b7b682014-08-21 05:55:13 +0000796 SSAUpdater &S, SmallPtrSetImpl<Value *> &PMA,
Chandler Carruthfc258542014-02-11 12:52:27 +0000797 SmallVectorImpl<BasicBlock *> &LEB,
798 SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
799 AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
Hal Finkelcc39b672014-07-24 12:16:19 +0000800 const AAMDNodes &AATags)
Chandler Carruthfc258542014-02-11 12:52:27 +0000801 : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
802 LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
Hal Finkelcc39b672014-07-24 12:16:19 +0000803 LI(li), DL(dl), Alignment(alignment), AATags(AATags) {}
Tobias Grossera3928f52011-07-06 19:20:02 +0000804
Craig Topper3e4c6972014-03-05 09:10:37 +0000805 bool isInstInList(Instruction *I,
806 const SmallVectorImpl<Instruction*> &) const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000807 Value *Ptr;
808 if (LoadInst *LI = dyn_cast<LoadInst>(I))
809 Ptr = LI->getOperand(0);
810 else
811 Ptr = cast<StoreInst>(I)->getPointerOperand();
812 return PointerMustAliases.count(Ptr);
813 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000814
Craig Topper3e4c6972014-03-05 09:10:37 +0000815 void doExtraRewritesBeforeFinalDeletion() const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000816 // Insert stores after in the loop exit blocks. Each exit block gets a
817 // store of the live-out values that feed them. Since we've already told
818 // the SSA updater about the defs in the loop and the preheader
819 // definition, it is all set and we can start using it.
820 for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
821 BasicBlock *ExitBlock = LoopExitBlocks[i];
822 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
Chandler Carruthfc258542014-02-11 12:52:27 +0000823 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
824 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
Dan Gohmanb9487362012-08-08 00:00:26 +0000825 Instruction *InsertPos = LoopInsertPts[i];
Chandler Carruthfc258542014-02-11 12:52:27 +0000826 StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000827 NewSI->setAlignment(Alignment);
Eli Friedmanddf7f552011-05-27 20:31:51 +0000828 NewSI->setDebugLoc(DL);
Hal Finkelcc39b672014-07-24 12:16:19 +0000829 if (AATags) NewSI->setAAMetadata(AATags);
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000830 }
831 }
832
Craig Topper3e4c6972014-03-05 09:10:37 +0000833 void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000834 // Update alias analysis.
835 AST.copyValue(LI, V);
836 }
Craig Topper3e4c6972014-03-05 09:10:37 +0000837 void instructionDeleted(Instruction *I) const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000838 AST.deleteValue(I);
839 }
840 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000841} // end anon namespace
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000842
Hal Finkel3d4269a2015-02-22 18:35:32 +0000843/// Try to promote memory values to scalars by sinking stores out of the
844/// loop and moving loads to before the loop. We do this by looping over
845/// the stores in the loop, looking for stores to Must pointers which are
846/// loop invariant.
Chris Lattner45d67d62003-02-24 03:52:32 +0000847///
Hal Finkel3d4269a2015-02-22 18:35:32 +0000848bool llvm::promoteLoopAccessesToScalars(AliasSet &AS,
849 SmallVectorImpl<BasicBlock*>&ExitBlocks,
850 SmallVectorImpl<Instruction*>&InsertPts,
851 PredIteratorCache &PIC, LoopInfo *LI,
Philip Reamesb54c8e62016-03-09 22:59:30 +0000852 DominatorTree *DT,
853 const TargetLibraryInfo *TLI,
854 Loop *CurLoop,
Hal Finkel3d4269a2015-02-22 18:35:32 +0000855 AliasSetTracker *CurAST,
856 LICMSafetyInfo * SafetyInfo) {
857 // Verify inputs.
858 assert(LI != nullptr && DT != nullptr &&
859 CurLoop != nullptr && CurAST != nullptr &&
860 SafetyInfo != nullptr &&
861 "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();
Hal Finkel3d4269a2015-02-22 18:35:32 +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
Chris Lattner1dc98b42010-08-29 06:43:52 +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;
922
923 const DataLayout &MDL = Preheader->getModule()->getDataLayout();
924
Chris Lattner1dc98b42010-08-29 06:43:52 +0000925 // Check that all of the pointers in the alias set have the same type. We
926 // cannot (yet) promote a memory location that is loaded and stored in
Hal Finkelcc39b672014-07-24 12:16:19 +0000927 // different sizes. While we are at it, collect alignment and AA info.
Sanjay Patel99133222016-01-13 23:01:57 +0000928 bool Changed = false;
Chris Lattner1dc98b42010-08-29 06:43:52 +0000929 for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
930 Value *ASIV = ASI->getValue();
931 PointerMustAliases.insert(ASIV);
Tobias Grossera3928f52011-07-06 19:20:02 +0000932
Chris Lattnerf12c08d2008-05-22 00:53:38 +0000933 // Check that all of the pointers in the alias set have the same type. We
934 // cannot (yet) promote a memory location that is loaded and stored in
935 // different sizes.
Chris Lattner1dc98b42010-08-29 06:43:52 +0000936 if (SomePtr->getType() != ASIV->getType())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000937 return Changed;
Tobias Grossera3928f52011-07-06 19:20:02 +0000938
Chandler Carruthcdf47882014-03-09 03:16:01 +0000939 for (User *U : ASIV->users()) {
Chris Lattner1dc98b42010-08-29 06:43:52 +0000940 // Ignore instructions that are outside the loop.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000941 Instruction *UI = dyn_cast<Instruction>(U);
942 if (!UI || !CurLoop->contains(UI))
Chris Lattnerf12c08d2008-05-22 00:53:38 +0000943 continue;
Tobias Grossera3928f52011-07-06 19:20:02 +0000944
Chris Lattner1dc98b42010-08-29 06:43:52 +0000945 // If there is an non-load/store instruction in the loop, we can't promote
946 // it.
Sanjay Patel9f49b682016-01-08 22:05:03 +0000947 if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {
948 assert(!Load->isVolatile() && "AST broken");
949 if (!Load->isSimple())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000950 return Changed;
Philip Reamesb54c8e62016-03-09 22:59:30 +0000951
952 if (!GuaranteedToExecute && !CanSpeculateLoad)
953 CanSpeculateLoad =
954 isSafeToExecuteUnconditionally(*Load, DT, TLI, CurLoop,
955 SafetyInfo,
956 Preheader->getTerminator());
Sanjay Patel9f49b682016-01-08 22:05:03 +0000957 } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
Chris Lattner408a6842010-12-19 05:57:25 +0000958 // Stores *of* the pointer are not interesting, only stores *to* the
959 // pointer.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000960 if (UI->getOperand(1) != ASIV)
Chris Lattner408a6842010-12-19 05:57:25 +0000961 continue;
Sanjay Patel9f49b682016-01-08 22:05:03 +0000962 assert(!Store->isVolatile() && "AST broken");
963 if (!Store->isSimple())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000964 return Changed;
Eli Friedman0cdc1482011-07-20 21:37:47 +0000965
966 // Note that we only check GuaranteedToExecute inside the store case
967 // so that we do not introduce stores where they did not exist before
968 // (which would break the LLVM concurrency model).
969
970 // If the alignment of this instruction allows us to specify a more
971 // restrictive (and performant) alignment and if we are sure this
972 // instruction will be executed, update the alignment.
973 // Larger is better, with the exception of 0 being the best alignment.
Sanjay Patel9f49b682016-01-08 22:05:03 +0000974 unsigned InstAlignment = Store->getAlignment();
Chris Lattnerf5cca682012-12-31 08:37:17 +0000975 if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0)
Hal Finkel3d4269a2015-02-22 18:35:32 +0000976 if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
Eli Friedman0cdc1482011-07-20 21:37:47 +0000977 GuaranteedToExecute = true;
978 Alignment = InstAlignment;
979 }
980
981 if (!GuaranteedToExecute)
Hal Finkel3d4269a2015-02-22 18:35:32 +0000982 GuaranteedToExecute = isGuaranteedToExecute(*UI, DT,
983 CurLoop, SafetyInfo);
Eli Friedman0cdc1482011-07-20 21:37:47 +0000984
Philip Reamesb54c8e62016-03-09 22:59:30 +0000985
986 if (!GuaranteedToExecute && !CanSpeculateLoad) {
987 CanSpeculateLoad =
988 isDereferenceableAndAlignedPointer(Store->getPointerOperand(),
989 Store->getAlignment(), MDL,
990 Preheader->getTerminator(),
991 DT, TLI);
992 }
Chris Lattnerbe901902010-09-06 05:11:24 +0000993 } else
Hal Finkel3d4269a2015-02-22 18:35:32 +0000994 return Changed; // Not a load or store.
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000995
Hal Finkelcc39b672014-07-24 12:16:19 +0000996 // Merge the AA tags.
Chris Lattnerf5cca682012-12-31 08:37:17 +0000997 if (LoopUses.empty()) {
Hal Finkelcc39b672014-07-24 12:16:19 +0000998 // On the first load/store, just take its AA tags.
999 UI->getAAMetadata(AATags);
1000 } else if (AATags) {
1001 UI->getAAMetadata(AATags, /* Merge = */ true);
Chris Lattnerf5cca682012-12-31 08:37:17 +00001002 }
Chandler Carruthcdf47882014-03-09 03:16:01 +00001003
1004 LoopUses.push_back(UI);
Chris Lattner1dc98b42010-08-29 06:43:52 +00001005 }
1006 }
Tobias Grosser4a5d9a92011-07-06 19:19:55 +00001007
Philip Reamesb54c8e62016-03-09 22:59:30 +00001008 // Check legality per comment above. Otherwise, we can't promote.
1009 bool PromotionIsLegal = GuaranteedToExecute;
1010 if (!PromotionIsLegal && CanSpeculateLoad) {
1011 // If this is a thread local location, then we can insert stores along
1012 // paths which originally didn't have them without violating the memory
1013 // model.
1014 Value *Object = GetUnderlyingObject(SomePtr, MDL);
1015 PromotionIsLegal = isAllocLikeFn(Object, TLI) &&
1016 !PointerMayBeCaptured(Object, true, true);
1017 }
1018 if (!PromotionIsLegal)
Hal Finkel3d4269a2015-02-22 18:35:32 +00001019 return Changed;
Tobias Grossera3928f52011-07-06 19:20:02 +00001020
David Majnemer219055f2016-01-04 17:42:19 +00001021 // Figure out the loop exits and their insertion points, if this is the
1022 // first promotion.
1023 if (ExitBlocks.empty()) {
1024 CurLoop->getUniqueExitBlocks(ExitBlocks);
1025 InsertPts.clear();
1026 InsertPts.reserve(ExitBlocks.size());
David Majnemerb33f3a22016-01-04 23:16:22 +00001027 for (BasicBlock *ExitBlock : ExitBlocks)
David Majnemer219055f2016-01-04 17:42:19 +00001028 InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
David Majnemer219055f2016-01-04 17:42:19 +00001029 }
1030
David Majnemerb33f3a22016-01-04 23:16:22 +00001031 // Can't insert into a catchswitch.
1032 for (BasicBlock *ExitBlock : ExitBlocks)
1033 if (isa<CatchSwitchInst>(ExitBlock->getTerminator()))
1034 return Changed;
1035
Chris Lattner1dc98b42010-08-29 06:43:52 +00001036 // Otherwise, this is safe to promote, lets do it!
Tobias Grossera3928f52011-07-06 19:20:02 +00001037 DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n');
Chris Lattner1dc98b42010-08-29 06:43:52 +00001038 Changed = true;
1039 ++NumPromoted;
1040
Eli Friedmanddf7f552011-05-27 20:31:51 +00001041 // Grab a debug location for the inserted loads/stores; given that the
1042 // inserted loads/stores have little relation to the original loads/stores,
1043 // this code just arbitrarily picks a location from one, since any debug
1044 // location is better than none.
1045 DebugLoc DL = LoopUses[0]->getDebugLoc();
1046
Chris Lattner1dc98b42010-08-29 06:43:52 +00001047 // We use the SSAUpdater interface to insert phi nodes as required.
1048 SmallVector<PHINode*, 16> NewPHIs;
1049 SSAUpdater SSA(&NewPHIs);
Pete Cooper7c4d7b82015-05-13 22:43:09 +00001050 LoopPromoter Promoter(SomePtr, LoopUses, SSA,
Pete Cooper41e0ee32015-05-13 01:12:16 +00001051 PointerMustAliases, ExitBlocks,
Hal Finkelcc39b672014-07-24 12:16:19 +00001052 InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags);
Tobias Grossera3928f52011-07-06 19:20:02 +00001053
Chris Lattnerb68ec5c2011-01-15 00:12:35 +00001054 // Set up the preheader to have a definition of the value. It is the live-out
1055 // value from the preheader that uses in the loop will use.
1056 LoadInst *PreheaderLoad =
1057 new LoadInst(SomePtr, SomePtr->getName()+".promoted",
1058 Preheader->getTerminator());
Tobias Grosser4a5d9a92011-07-06 19:19:55 +00001059 PreheaderLoad->setAlignment(Alignment);
Eli Friedmanddf7f552011-05-27 20:31:51 +00001060 PreheaderLoad->setDebugLoc(DL);
Hal Finkelcc39b672014-07-24 12:16:19 +00001061 if (AATags) PreheaderLoad->setAAMetadata(AATags);
Chris Lattner1dc98b42010-08-29 06:43:52 +00001062 SSA.AddAvailableValue(Preheader, PreheaderLoad);
1063
Chris Lattnerb68ec5c2011-01-15 00:12:35 +00001064 // Rewrite all the loads in the loop and remember all the definitions from
1065 // stores in the loop.
1066 Promoter.run(LoopUses);
Eli Friedmanc5f22a72011-04-07 01:35:06 +00001067
1068 // If the SSAUpdater didn't use the load in the preheader, just zap it now.
1069 if (PreheaderLoad->use_empty())
1070 PreheaderLoad->eraseFromParent();
Hal Finkel3d4269a2015-02-22 18:35:32 +00001071
1072 return Changed;
Chris Lattnera51fa882002-08-22 21:39:55 +00001073}
Devang Patelb98a0972007-07-31 08:01:41 +00001074
Roman Gareev036c0882016-02-15 14:48:50 +00001075/// Returns an owning pointer to an alias set which incorporates aliasing info
Chandler Carruthad8cb382016-02-27 04:34:07 +00001076/// from L and all subloops of L.
1077AliasSetTracker *LICM::collectAliasInfoForLoop(Loop *L) {
Roman Gareev036c0882016-02-15 14:48:50 +00001078 AliasSetTracker *CurAST = nullptr;
Chandler Carruthad8cb382016-02-27 04:34:07 +00001079 SmallVector<Loop *, 4> RecomputeLoops;
Roman Gareev036c0882016-02-15 14:48:50 +00001080 for (Loop *InnerL : L->getSubLoops()) {
Chandler Carruthad8cb382016-02-27 04:34:07 +00001081 auto MapI = LoopToAliasSetMap.find(InnerL);
1082 // If the AST for this inner loop is missing it may have been merged into
1083 // some other loop's AST and then that loop unrolled, and so we need to
1084 // recompute it.
1085 if (MapI == LoopToAliasSetMap.end()) {
1086 RecomputeLoops.push_back(InnerL);
1087 continue;
1088 }
1089 AliasSetTracker *InnerAST = MapI->second;
Roman Gareev036c0882016-02-15 14:48:50 +00001090
1091 if (CurAST != nullptr) {
1092 // What if InnerLoop was modified by other passes ?
1093 CurAST->add(*InnerAST);
1094
1095 // Once we've incorporated the inner loop's AST into ours, we don't need
1096 // the subloop's anymore.
1097 delete InnerAST;
1098 } else {
1099 CurAST = InnerAST;
1100 }
Chandler Carruthad8cb382016-02-27 04:34:07 +00001101 LoopToAliasSetMap.erase(MapI);
Roman Gareev036c0882016-02-15 14:48:50 +00001102 }
1103 if (CurAST == nullptr)
1104 CurAST = new AliasSetTracker(*AA);
Chandler Carruthad8cb382016-02-27 04:34:07 +00001105
1106 auto mergeLoop = [&](Loop *L) {
1107 // Loop over the body of this loop, looking for calls, invokes, and stores.
1108 // Because subloops have already been incorporated into AST, we skip blocks
1109 // in subloops.
1110 for (BasicBlock *BB : L->blocks())
1111 if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops.
1112 CurAST->add(*BB); // Incorporate the specified basic block
1113 };
1114
1115 // Add everything from the sub loops that are no longer directly available.
1116 for (Loop *InnerL : RecomputeLoops)
1117 mergeLoop(InnerL);
1118
1119 // And merge in this loop.
1120 mergeLoop(L);
1121
Roman Gareev036c0882016-02-15 14:48:50 +00001122 return CurAST;
1123}
1124
Ashutosh Nema47802622015-08-13 11:18:35 +00001125/// Simple analysis hook. Clone alias set info.
Hal Finkel3d4269a2015-02-22 18:35:32 +00001126///
Devang Patelb98a0972007-07-31 08:01:41 +00001127void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
Chris Lattnercc9cbc62010-08-29 17:46:00 +00001128 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
Devang Patelb98a0972007-07-31 08:01:41 +00001129 if (!AST)
1130 return;
1131
1132 AST->copyValue(From, To);
1133}
1134
Hal Finkel3d4269a2015-02-22 18:35:32 +00001135/// Simple Analysis hook. Delete value V from alias set
1136///
Devang Patelb98a0972007-07-31 08:01:41 +00001137void LICM::deleteAnalysisValue(Value *V, Loop *L) {
Chris Lattnercc9cbc62010-08-29 17:46:00 +00001138 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
Devang Patelb98a0972007-07-31 08:01:41 +00001139 if (!AST)
1140 return;
1141
1142 AST->deleteValue(V);
1143}
David Peixotto0d4d5e62014-09-24 16:48:31 +00001144
1145/// Simple Analysis hook. Delete value L from alias set map.
Hal Finkel3d4269a2015-02-22 18:35:32 +00001146///
David Peixotto0d4d5e62014-09-24 16:48:31 +00001147void LICM::deleteAnalysisLoop(Loop *L) {
1148 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
1149 if (!AST)
1150 return;
1151
1152 delete AST;
1153 LoopToAliasSetMap.erase(L);
1154}
Hal Finkel3d4269a2015-02-22 18:35:32 +00001155
1156
1157/// Return true if the body of this loop may store into the memory
1158/// location pointed to by V.
1159///
1160static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
1161 const AAMDNodes &AAInfo,
1162 AliasSetTracker *CurAST) {
1163 // Check to see if any of the basic blocks in CurLoop invalidate *V.
1164 return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
1165}
1166
1167/// Little predicate that returns true if the specified basic block is in
1168/// a subloop of the current one, not the current one itself.
1169///
1170static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1171 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
1172 return LI->getLoopFor(BB) != CurLoop;
1173}
1174