blob: daf76218e6241023c0aa9e7a9e9d74559ecb8d1c [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"
Chris Lattner030f0202010-08-31 23:00:16 +000041#include "llvm/Analysis/LoopInfo.h"
42#include "llvm/Analysis/LoopPass.h"
Philip Reamesb54c8e62016-03-09 22:59:30 +000043#include "llvm/Analysis/MemoryBuiltins.h"
Chandler Carruthabfa3e52014-01-24 01:59:49 +000044#include "llvm/Analysis/ScalarEvolution.h"
Chandler Carruth7b560d42015-09-09 17:55:00 +000045#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
Benjamin Kramer799003b2015-03-23 19:32:43 +000046#include "llvm/Analysis/TargetLibraryInfo.h"
Dan Gohman75d7d5e2011-12-14 23:49:11 +000047#include "llvm/Analysis/ValueTracking.h"
Chandler Carruth1305dc32014-03-04 11:45:46 +000048#include "llvm/IR/CFG.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000049#include "llvm/IR/Constants.h"
50#include "llvm/IR/DataLayout.h"
51#include "llvm/IR/DerivedTypes.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000052#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000053#include "llvm/IR/Instructions.h"
54#include "llvm/IR/IntrinsicInst.h"
55#include "llvm/IR/LLVMContext.h"
Chris Lattner473988c2013-01-05 16:44:07 +000056#include "llvm/IR/Metadata.h"
Chandler Carruthaa0ab632014-03-04 12:09:19 +000057#include "llvm/IR/PredIteratorCache.h"
Reid Spencer7c16caa2004-09-01 22:55:40 +000058#include "llvm/Support/CommandLine.h"
59#include "llvm/Support/Debug.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000060#include "llvm/Support/raw_ostream.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000061#include "llvm/Transforms/Utils/Local.h"
Chandler Carruth8765cf72014-01-25 04:07:24 +000062#include "llvm/Transforms/Utils/LoopUtils.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000063#include "llvm/Transforms/Utils/SSAUpdater.h"
Chris Lattner6ec05f52002-05-10 22:44:58 +000064#include <algorithm>
Chris Lattnerc0517682003-12-09 17:18:00 +000065using namespace llvm;
Brian Gaeke960707c2003-11-11 22:41:34 +000066
Chandler Carruth964daaa2014-04-22 02:55:47 +000067#define DEBUG_TYPE "licm"
68
Chris Lattner79a42ac2006-12-19 21:40:18 +000069STATISTIC(NumSunk , "Number of instructions sunk out of loop");
70STATISTIC(NumHoisted , "Number of instructions hoisted out of loop");
71STATISTIC(NumMovedLoads, "Number of load insts hoisted or sunk");
72STATISTIC(NumMovedCalls, "Number of call insts hoisted or sunk");
73STATISTIC(NumPromoted , "Number of memory locations promoted to registers");
74
Dan Gohmand78c4002008-05-13 00:00:25 +000075static cl::opt<bool>
76DisablePromotion("disable-licm-promotion", cl::Hidden,
77 cl::desc("Disable memory promotion in LICM pass"));
Chris Lattner45d67d62003-02-24 03:52:32 +000078
Hal Finkel3d4269a2015-02-22 18:35:32 +000079static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI);
David Majnemer42a07302016-01-04 03:37:39 +000080static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
81 const LICMSafetyInfo *SafetyInfo);
Sanjoy Das7a2e2be2016-01-28 15:51:58 +000082static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
83 const LICMSafetyInfo *SafetyInfo);
Pete Cooper0cabcf22015-05-13 01:12:18 +000084static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
David Majnemer42a07302016-01-04 03:37:39 +000085 const Loop *CurLoop, AliasSetTracker *CurAST,
86 const LICMSafetyInfo *SafetyInfo);
Pete Cooper0cabcf22015-05-13 01:12:18 +000087static bool isGuaranteedToExecute(const Instruction &Inst,
88 const DominatorTree *DT,
89 const Loop *CurLoop,
90 const LICMSafetyInfo *SafetyInfo);
91static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
92 const DominatorTree *DT,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +000093 const TargetLibraryInfo *TLI,
Pete Cooper0cabcf22015-05-13 01:12:18 +000094 const Loop *CurLoop,
Philip Reamesb47b9c22015-05-22 02:14:05 +000095 const LICMSafetyInfo *SafetyInfo,
96 const Instruction *CtxI = nullptr);
Hal Finkel3d4269a2015-02-22 18:35:32 +000097static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
98 const AAMDNodes &AAInfo,
99 AliasSetTracker *CurAST);
David Majnemer42a07302016-01-04 03:37:39 +0000100static Instruction *
101CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
102 const LoopInfo *LI,
103 const LICMSafetyInfo *SafetyInfo);
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000104static bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000105 DominatorTree *DT, TargetLibraryInfo *TLI,
106 Loop *CurLoop, AliasSetTracker *CurAST,
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000107 LICMSafetyInfo *SafetyInfo);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000108
Dan Gohmand78c4002008-05-13 00:00:25 +0000109namespace {
Chris Lattner2dd09db2009-09-02 06:11:42 +0000110 struct LICM : public LoopPass {
Nick Lewyckye7da2d62007-05-06 13:37:16 +0000111 static char ID; // Pass identification, replacement for typeid
Owen Anderson6c18d1a2010-10-19 17:21:58 +0000112 LICM() : LoopPass(ID) {
113 initializeLICMPass(*PassRegistry::getPassRegistry());
114 }
Devang Patel09f162c2007-05-01 21:15:47 +0000115
Craig Topper3e4c6972014-03-05 09:10:37 +0000116 bool runOnLoop(Loop *L, LPPassManager &LPM) override;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000117
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000118 /// This transformation requires natural loop information & requires that
119 /// loop preheaders be inserted into the CFG...
120 ///
Craig Topper3e4c6972014-03-05 09:10:37 +0000121 void getAnalysisUsage(AnalysisUsage &AU) const override {
Chris Lattner820d9712002-10-21 20:00:28 +0000122 AU.setPreservesCFG();
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000123 AU.addRequired<TargetLibraryInfoWrapperPass>();
Chandler Carruth31088a92016-02-19 10:45:18 +0000124 getLoopAnalysisUsage(AU);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000125 }
126
Matt Beaumont-Gayabfc4462012-12-04 05:41:27 +0000127 using llvm::Pass::doFinalization;
128
Craig Topper3e4c6972014-03-05 09:10:37 +0000129 bool doFinalization() override {
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000130 assert(LoopToAliasSetMap.empty() && "Didn't free loop alias sets");
Devang Patel69730c92007-03-07 04:41:30 +0000131 return false;
132 }
133
Chris Lattner6ec05f52002-05-10 22:44:58 +0000134 private:
Chris Lattner45d67d62003-02-24 03:52:32 +0000135 AliasAnalysis *AA; // Current AliasAnalysis information
Chris Lattnerc0517682003-12-09 17:18:00 +0000136 LoopInfo *LI; // Current LoopInfo
Chris Lattnerabe61ef2010-08-29 06:49:44 +0000137 DominatorTree *DT; // Dominator Tree for the current Loop.
Chris Lattnerc0517682003-12-09 17:18:00 +0000138
Chad Rosier43a33062011-12-02 01:26:24 +0000139 TargetLibraryInfo *TLI; // TargetLibraryInfo for constant folding.
140
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000141 // State that is updated as we process loops.
Chris Lattner45d67d62003-02-24 03:52:32 +0000142 bool Changed; // Set to true when we change anything.
143 BasicBlock *Preheader; // The preheader block of the current loop...
144 Loop *CurLoop; // The current loop we are working on...
Chris Lattner0592bb72003-03-03 23:32:45 +0000145 AliasSetTracker *CurAST; // AliasSet information for the current loop...
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000146 DenseMap<Loop*, AliasSetTracker*> LoopToAliasSetMap;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000147
Devang Patelb98a0972007-07-31 08:01:41 +0000148 /// cloneBasicBlockAnalysis - Simple Analysis hook. Clone alias set info.
Craig Topper3e4c6972014-03-05 09:10:37 +0000149 void cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To,
150 Loop *L) override;
Devang Patelb98a0972007-07-31 08:01:41 +0000151
152 /// deleteAnalysisValue - Simple Analysis hook. Delete value V from alias
153 /// set.
Craig Topper3e4c6972014-03-05 09:10:37 +0000154 void deleteAnalysisValue(Value *V, Loop *L) override;
Devang Patelb98a0972007-07-31 08:01:41 +0000155
David Peixotto0d4d5e62014-09-24 16:48:31 +0000156 /// Simple Analysis hook. Delete loop L from alias set map.
157 void deleteAnalysisLoop(Loop *L) override;
Roman Gareev036c0882016-02-15 14:48:50 +0000158
Chandler Carruthad8cb382016-02-27 04:34:07 +0000159 AliasSetTracker *collectAliasInfoForLoop(Loop *L);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000160 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000161}
Chris Lattner6ec05f52002-05-10 22:44:58 +0000162
Dan Gohmand78c4002008-05-13 00:00:25 +0000163char LICM::ID = 0;
Owen Anderson8ac477f2010-10-12 19:48:12 +0000164INITIALIZE_PASS_BEGIN(LICM, "licm", "Loop Invariant Code Motion", false, false)
Chandler Carruth31088a92016-02-19 10:45:18 +0000165INITIALIZE_PASS_DEPENDENCY(LoopPass)
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000166INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfoWrapperPass)
Owen Anderson8ac477f2010-10-12 19:48:12 +0000167INITIALIZE_PASS_END(LICM, "licm", "Loop Invariant Code Motion", false, false)
Dan Gohmand78c4002008-05-13 00:00:25 +0000168
Daniel Dunbar7f39e2d2008-10-22 23:32:42 +0000169Pass *llvm::createLICMPass() { return new LICM(); }
Chris Lattner6ec05f52002-05-10 22:44:58 +0000170
Devang Pateld8b1ceb2007-07-31 16:52:25 +0000171/// Hoist expressions out of the specified loop. Note, alias info for inner
Tobias Grossera3928f52011-07-06 19:20:02 +0000172/// loop is not preserved so it is not a good idea to run LICM multiple
Devang Pateld8b1ceb2007-07-31 16:52:25 +0000173/// times on one loop.
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000174///
Devang Patel69730c92007-03-07 04:41:30 +0000175bool LICM::runOnLoop(Loop *L, LPPassManager &LPM) {
Paul Robinsonaf4e64d2014-02-06 00:07:05 +0000176 if (skipOptnoneFunction(L))
177 return false;
178
Chris Lattner45d67d62003-02-24 03:52:32 +0000179 Changed = false;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000180
Chris Lattner45d67d62003-02-24 03:52:32 +0000181 // Get our Loop and Alias Analysis information...
Chandler Carruth4f8f3072015-01-17 14:16:18 +0000182 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000183 AA = &getAnalysis<AAResultsWrapperPass>().getAAResults();
Chandler Carruth73523022014-01-13 13:07:17 +0000184 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
Chris Lattnera51fa882002-08-22 21:39:55 +0000185
Chandler Carruthb98f63d2015-01-15 10:41:28 +0000186 TLI = &getAnalysis<TargetLibraryInfoWrapperPass>().getTLI();
Chad Rosier43a33062011-12-02 01:26:24 +0000187
Chandler Carruthfc258542014-02-11 12:52:27 +0000188 assert(L->isLCSSAForm(*DT) && "Loop is not in LCSSA form.");
189
Chandler Carruthad8cb382016-02-27 04:34:07 +0000190 CurAST = collectAliasInfoForLoop(L);
Tobias Grossera3928f52011-07-06 19:20:02 +0000191
Chris Lattner6ec05f52002-05-10 22:44:58 +0000192 CurLoop = L;
193
Chris Lattnerd57f3f52002-09-26 19:40:25 +0000194 // Get the preheader block to move instructions into...
195 Preheader = L->getLoopPreheader();
Chris Lattnerd57f3f52002-09-26 19:40:25 +0000196
Hal Finkel3d4269a2015-02-22 18:35:32 +0000197 // Compute loop safety information.
198 LICMSafetyInfo SafetyInfo;
199 computeLICMSafetyInfo(&SafetyInfo, CurLoop);
Nadav Rotem03dcd852012-09-04 10:25:04 +0000200
Chris Lattner6ec05f52002-05-10 22:44:58 +0000201 // We want to visit all of the instructions in this loop... that are not parts
202 // of our subloops (they have already had their invariants hoisted out of
203 // their loop, into this loop, so there is no need to process the BODIES of
204 // the subloops).
205 //
Chris Lattner64437692002-09-29 21:46:09 +0000206 // Traverse the body of the loop in depth first order on the dominator tree so
207 // that we are guaranteed to see definitions before we see uses. This allows
Nick Lewyckya0d49da2007-08-18 15:08:56 +0000208 // us to sink instructions in one pass, without iteration. After sinking
Chris Lattner547192d62003-12-19 07:22:45 +0000209 // instructions, we perform another pass to hoist them out of the loop.
Chris Lattner64437692002-09-29 21:46:09 +0000210 //
Dan Gohmana83ac2d2009-11-05 21:11:53 +0000211 if (L->hasDedicatedExits())
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000212 Changed |= sinkRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI, CurLoop,
213 CurAST, &SafetyInfo);
Dan Gohmana83ac2d2009-11-05 21:11:53 +0000214 if (Preheader)
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000215 Changed |= hoistRegion(DT->getNode(L->getHeader()), AA, LI, DT, TLI,
Hal Finkel3d4269a2015-02-22 18:35:32 +0000216 CurLoop, CurAST, &SafetyInfo);
Chris Lattner6ec05f52002-05-10 22:44:58 +0000217
Chris Lattner45d67d62003-02-24 03:52:32 +0000218 // Now that all loop invariants have been removed from the loop, promote any
Chris Lattner1dc98b42010-08-29 06:43:52 +0000219 // memory references to scalars that we can.
Chandler Carruthcc497b62014-01-24 02:24:47 +0000220 if (!DisablePromotion && (Preheader || L->hasDedicatedExits())) {
Dan Gohmanb9487362012-08-08 00:00:26 +0000221 SmallVector<BasicBlock *, 8> ExitBlocks;
222 SmallVector<Instruction *, 8> InsertPts;
Chandler Carruthfc258542014-02-11 12:52:27 +0000223 PredIteratorCache PIC;
Dan Gohmanb9487362012-08-08 00:00:26 +0000224
Chris Lattner1dc98b42010-08-29 06:43:52 +0000225 // Loop over all of the alias sets in the tracker object.
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000226 for (AliasSet &AS : *CurAST)
227 Changed |= promoteLoopAccessesToScalars(AS, ExitBlocks, InsertPts,
Philip Reamesb54c8e62016-03-09 22:59:30 +0000228 PIC, LI, DT, TLI, CurLoop,
Hal Finkel3d4269a2015-02-22 18:35:32 +0000229 CurAST, &SafetyInfo);
Chandler Carruth16651522014-02-01 13:35:14 +0000230
231 // Once we have promoted values across the loop body we have to recursively
232 // reform LCSSA as any nested loop may now have values defined within the
233 // loop used in the outer loop.
234 // FIXME: This is really heavy handed. It would be a bit better to use an
235 // SSAUpdater strategy during promotion that was LCSSA aware and reformed
236 // it as it went.
Chandler Carruth2f1fd162015-08-17 02:08:17 +0000237 if (Changed) {
238 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
239 formLCSSARecursively(*L, *DT, LI, SEWP ? &SEWP->getSE() : nullptr);
240 }
Chris Lattner1dc98b42010-08-29 06:43:52 +0000241 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000242
Chandler Carruthfc258542014-02-11 12:52:27 +0000243 // Check that neither this loop nor its parent have had LCSSA broken. LICM is
244 // specifically moving instructions across the loop boundary and so it is
245 // especially in need of sanity checking here.
246 assert(L->isLCSSAForm(*DT) && "Loop not left in LCSSA form after LICM!");
247 assert((!L->getParentLoop() || L->getParentLoop()->isLCSSAForm(*DT)) &&
248 "Parent loop not left in LCSSA form after LICM!");
Chandler Carruth8765cf72014-01-25 04:07:24 +0000249
Chris Lattner6ec05f52002-05-10 22:44:58 +0000250 // Clear out loops state information for the next iteration
Craig Topperf40110f2014-04-25 05:29:35 +0000251 CurLoop = nullptr;
252 Preheader = nullptr;
Devang Patel69730c92007-03-07 04:41:30 +0000253
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000254 // If this loop is nested inside of another one, save the alias information
255 // for when we process the outer loop.
256 if (L->getParentLoop())
257 LoopToAliasSetMap[L] = CurAST;
258 else
259 delete CurAST;
Devang Patel69730c92007-03-07 04:41:30 +0000260 return Changed;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000261}
262
Hal Finkel3d4269a2015-02-22 18:35:32 +0000263/// Walk the specified region of the CFG (defined by all blocks dominated by
264/// the specified block, and that are in the current loop) in reverse depth
265/// first order w.r.t the DominatorTree. This allows us to visit uses before
266/// definitions, allowing us to sink a loop body in one pass without iteration.
Chris Lattner547192d62003-12-19 07:22:45 +0000267///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000268bool llvm::sinkRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
269 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
270 AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
Chris Lattner547192d62003-12-19 07:22:45 +0000271
Hal Finkel3d4269a2015-02-22 18:35:32 +0000272 // Verify inputs.
273 assert(N != nullptr && AA != nullptr && LI != nullptr &&
274 DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
275 SafetyInfo != nullptr && "Unexpected input to sinkRegion");
276
Hal Finkel3d4269a2015-02-22 18:35:32 +0000277 BasicBlock *BB = N->getBlock();
Chris Lattner547192d62003-12-19 07:22:45 +0000278 // If this subregion is not in the top level loop at all, exit.
Sanjay Patel99133222016-01-13 23:01:57 +0000279 if (!CurLoop->contains(BB)) return false;
Chris Lattner547192d62003-12-19 07:22:45 +0000280
Chris Lattner263f8042010-08-29 18:22:25 +0000281 // We are processing blocks in reverse dfo, so process children first.
Sanjay Patel99133222016-01-13 23:01:57 +0000282 bool Changed = false;
Devang Patelbdd1aae2007-06-04 00:32:22 +0000283 const std::vector<DomTreeNode*> &Children = N->getChildren();
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000284 for (DomTreeNode *Child : Children)
285 Changed |= sinkRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
286
Chris Lattner547192d62003-12-19 07:22:45 +0000287 // Only need to process the contents of this block if it is not part of a
288 // subloop (which would already have been processed).
Hal Finkel3d4269a2015-02-22 18:35:32 +0000289 if (inSubLoop(BB,CurLoop,LI)) return Changed;
Chris Lattner547192d62003-12-19 07:22:45 +0000290
Chris Lattner91846012003-12-19 08:18:16 +0000291 for (BasicBlock::iterator II = BB->end(); II != BB->begin(); ) {
292 Instruction &I = *--II;
Tobias Grossera3928f52011-07-06 19:20:02 +0000293
Chris Lattner263f8042010-08-29 18:22:25 +0000294 // If the instruction is dead, we would try to sink it because it isn't used
295 // in the loop, instead, just delete it.
Benjamin Kramer8bcc9712012-08-29 15:32:21 +0000296 if (isInstructionTriviallyDead(&I, TLI)) {
Chris Lattnerf58382e2010-08-29 18:42:23 +0000297 DEBUG(dbgs() << "LICM deleting dead inst: " << I << '\n');
Chris Lattner263f8042010-08-29 18:22:25 +0000298 ++II;
299 CurAST->deleteValue(&I);
300 I.eraseFromParent();
301 Changed = true;
302 continue;
303 }
Misha Brukmanb1c93172005-04-21 23:48:37 +0000304
Chris Lattner547192d62003-12-19 07:22:45 +0000305 // Check to see if we can sink this instruction to the exit blocks
306 // of the loop. We can do this if the all users of the instruction are
307 // outside of the loop. In this case, it doesn't even matter if the
308 // operands of the instruction are loop invariant.
309 //
David Majnemer42a07302016-01-04 03:37:39 +0000310 if (isNotUsedInLoop(I, CurLoop, SafetyInfo) &&
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000311 canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo)) {
Chris Lattner91846012003-12-19 08:18:16 +0000312 ++II;
David Majnemer42a07302016-01-04 03:37:39 +0000313 Changed |= sink(I, LI, DT, CurLoop, CurAST, SafetyInfo);
Chris Lattner91846012003-12-19 08:18:16 +0000314 }
Chris Lattner547192d62003-12-19 07:22:45 +0000315 }
Hal Finkel3d4269a2015-02-22 18:35:32 +0000316 return Changed;
Chris Lattner547192d62003-12-19 07:22:45 +0000317}
318
Hal Finkel3d4269a2015-02-22 18:35:32 +0000319/// Walk the specified region of the CFG (defined by all blocks dominated by
320/// the specified block, and that are in the current loop) in depth first
321/// order w.r.t the DominatorTree. This allows us to visit definitions before
322/// uses, allowing us to hoist a loop body in one pass without iteration.
Chris Lattner64437692002-09-29 21:46:09 +0000323///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000324bool llvm::hoistRegion(DomTreeNode *N, AliasAnalysis *AA, LoopInfo *LI,
325 DominatorTree *DT, TargetLibraryInfo *TLI, Loop *CurLoop,
326 AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
Hal Finkel3d4269a2015-02-22 18:35:32 +0000327 // Verify inputs.
328 assert(N != nullptr && AA != nullptr && LI != nullptr &&
329 DT != nullptr && CurLoop != nullptr && CurAST != nullptr &&
330 SafetyInfo != nullptr && "Unexpected input to hoistRegion");
Sanjay Patel99133222016-01-13 23:01:57 +0000331
Owen Andersonc24701e2007-04-24 06:40:39 +0000332 BasicBlock *BB = N->getBlock();
Sanjay Patel99133222016-01-13 23:01:57 +0000333
Chris Lattner05e86302002-09-29 22:26:07 +0000334 // If this subregion is not in the top level loop at all, exit.
Sanjay Patel99133222016-01-13 23:01:57 +0000335 if (!CurLoop->contains(BB)) return false;
336
Chris Lattneraaaea512003-12-10 06:41:05 +0000337 // Only need to process the contents of this block if it is not part of a
338 // subloop (which would already have been processed).
Sanjay Patel99133222016-01-13 23:01:57 +0000339 bool Changed = false;
Hal Finkel3d4269a2015-02-22 18:35:32 +0000340 if (!inSubLoop(BB, CurLoop, LI))
Chris Lattneraaaea512003-12-10 06:41:05 +0000341 for (BasicBlock::iterator II = BB->begin(), E = BB->end(); II != E; ) {
342 Instruction &I = *II++;
Chris Lattner030f0202010-08-31 23:00:16 +0000343 // Try constant folding this instruction. If all the operands are
344 // constants, it is technically hoistable, but it would be better to just
345 // fold it.
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000346 if (Constant *C = ConstantFoldInstruction(
347 &I, I.getModule()->getDataLayout(), TLI)) {
Chris Lattner030f0202010-08-31 23:00:16 +0000348 DEBUG(dbgs() << "LICM folding inst: " << I << " --> " << *C << '\n');
349 CurAST->copyValue(&I, C);
350 CurAST->deleteValue(&I);
351 I.replaceAllUsesWith(C);
352 I.eraseFromParent();
353 continue;
354 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000355
Chris Lattner547192d62003-12-19 07:22:45 +0000356 // Try hoisting the instruction out to the preheader. We can only do this
357 // if all of the operands of the instruction are loop invariant and if it
358 // is safe to hoist the instruction.
359 //
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000360 if (CurLoop->hasLoopInvariantOperands(&I) &&
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000361 canSinkOrHoistInst(I, AA, DT, TLI, CurLoop, CurAST, SafetyInfo) &&
Philip Reamesb47b9c22015-05-22 02:14:05 +0000362 isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
363 CurLoop->getLoopPreheader()->getTerminator()))
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000364 Changed |= hoist(I, DT, CurLoop, SafetyInfo);
Chris Lattner030f0202010-08-31 23:00:16 +0000365 }
Chris Lattner64437692002-09-29 21:46:09 +0000366
Devang Patelbdd1aae2007-06-04 00:32:22 +0000367 const std::vector<DomTreeNode*> &Children = N->getChildren();
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000368 for (DomTreeNode *Child : Children)
369 Changed |= hoistRegion(Child, AA, LI, DT, TLI, CurLoop, CurAST, SafetyInfo);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000370 return Changed;
371}
372
373/// Computes loop safety information, checks loop body & header
Benjamin Kramerdf005cb2015-08-08 18:27:36 +0000374/// for the possibility of may throw exception.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000375///
376void llvm::computeLICMSafetyInfo(LICMSafetyInfo * SafetyInfo, Loop * CurLoop) {
377 assert(CurLoop != nullptr && "CurLoop cant be null");
378 BasicBlock *Header = CurLoop->getHeader();
379 // Setting default safety values.
380 SafetyInfo->MayThrow = false;
381 SafetyInfo->HeaderMayThrow = false;
Benjamin Kramerdf005cb2015-08-08 18:27:36 +0000382 // Iterate over header and compute safety info.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000383 for (BasicBlock::iterator I = Header->begin(), E = Header->end();
384 (I != E) && !SafetyInfo->HeaderMayThrow; ++I)
385 SafetyInfo->HeaderMayThrow |= I->mayThrow();
386
387 SafetyInfo->MayThrow = SafetyInfo->HeaderMayThrow;
388 // Iterate over loop instructions and compute safety info.
389 for (Loop::block_iterator BB = CurLoop->block_begin(),
390 BBE = CurLoop->block_end(); (BB != BBE) && !SafetyInfo->MayThrow ; ++BB)
391 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end();
392 (I != E) && !SafetyInfo->MayThrow; ++I)
393 SafetyInfo->MayThrow |= I->mayThrow();
David Majnemer42a07302016-01-04 03:37:39 +0000394
395 // Compute funclet colors if we might sink/hoist in a function with a funclet
396 // personality routine.
397 Function *Fn = CurLoop->getHeader()->getParent();
398 if (Fn->hasPersonalityFn())
399 if (Constant *PersonalityFn = Fn->getPersonalityFn())
400 if (isFuncletEHPersonality(classifyEHPersonality(PersonalityFn)))
401 SafetyInfo->BlockColors = colorEHFunclets(*Fn);
Chris Lattner64437692002-09-29 21:46:09 +0000402}
403
Chris Lattneraaaea512003-12-10 06:41:05 +0000404/// canSinkOrHoistInst - Return true if the hoister and sinker can handle this
405/// instruction.
406///
Mehdi Aminia28d91d2015-03-10 02:37:25 +0000407bool canSinkOrHoistInst(Instruction &I, AliasAnalysis *AA, DominatorTree *DT,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000408 TargetLibraryInfo *TLI, Loop *CurLoop,
409 AliasSetTracker *CurAST, LICMSafetyInfo *SafetyInfo) {
Chris Lattner65c11932003-12-09 19:32:44 +0000410 // Loads have extra constraints we have to verify before we can hoist them.
411 if (LoadInst *LI = dyn_cast<LoadInst>(&I)) {
Eli Friedman91386c72011-08-15 20:52:09 +0000412 if (!LI->isUnordered())
413 return false; // Don't hoist volatile/atomic loads!
Chris Lattner65c11932003-12-09 19:32:44 +0000414
Chris Lattner8a8fb902008-07-23 05:06:28 +0000415 // Loads from constant memory are always safe to move, even if they end up
416 // in the same alias set as something that ends up being modified.
Dan Gohmancbc6ebb2009-11-19 19:00:10 +0000417 if (AA->pointsToConstantMemory(LI->getOperand(0)))
Chris Lattner8a8fb902008-07-23 05:06:28 +0000418 return true;
Philip Reames5a3f5f72014-10-21 00:13:20 +0000419 if (LI->getMetadata(LLVMContext::MD_invariant_load))
Pete Cooper9ee22092011-11-08 19:30:00 +0000420 return true;
Tobias Grossera3928f52011-07-06 19:20:02 +0000421
Chris Lattner65c11932003-12-09 19:32:44 +0000422 // Don't hoist loads which have may-aliased stores in loop.
Dan Gohmanf372cf82010-10-19 22:54:46 +0000423 uint64_t Size = 0;
Chris Lattnerb1374092004-11-26 21:20:09 +0000424 if (LI->getType()->isSized())
Chandler Carruth50fee932015-08-06 02:05:46 +0000425 Size = I.getModule()->getDataLayout().getTypeStoreSize(LI->getType());
Hal Finkelcc39b672014-07-24 12:16:19 +0000426
427 AAMDNodes AAInfo;
428 LI->getAAMetadata(AAInfo);
429
Hal Finkel3d4269a2015-02-22 18:35:32 +0000430 return !pointerInvalidatedByLoop(LI->getOperand(0), Size, AAInfo, CurAST);
Chris Lattner20cda262004-03-15 04:11:30 +0000431 } else if (CallInst *CI = dyn_cast<CallInst>(&I)) {
Eli Friedman942e1c12011-05-27 18:37:52 +0000432 // Don't sink or hoist dbg info; it's legal, but not useful.
433 if (isa<DbgInfoIntrinsic>(I))
434 return false;
435
David Majnemer42a07302016-01-04 03:37:39 +0000436 // Don't sink calls which can throw.
437 if (CI->mayThrow())
438 return false;
439
Eli Friedman942e1c12011-05-27 18:37:52 +0000440 // Handle simple cases by querying alias analysis.
Chandler Carruth194f59c2015-07-22 23:15:57 +0000441 FunctionModRefBehavior Behavior = AA->getModRefBehavior(CI);
442 if (Behavior == FMRB_DoesNotAccessMemory)
Duncan Sands68b6f502007-12-01 07:51:45 +0000443 return true;
Dan Gohman0f175072010-11-09 19:58:21 +0000444 if (AliasAnalysis::onlyReadsMemory(Behavior)) {
Philip Reames5f994232015-09-21 22:27:59 +0000445 // A readonly argmemonly function only reads from memory pointed to by
446 // it's arguments with arbitrary offsets. If we can prove there are no
447 // writes to this memory in the loop, we can hoist or sink.
448 if (AliasAnalysis::onlyAccessesArgPointees(Behavior)) {
449 for (Value *Op : CI->arg_operands())
450 if (Op->getType()->isPointerTy() &&
451 pointerInvalidatedByLoop(Op, MemoryLocation::UnknownSize,
452 AAMDNodes(), CurAST))
453 return false;
454 return true;
455 }
Duncan Sands68b6f502007-12-01 07:51:45 +0000456 // If this call only reads from memory and there are no writes to memory
457 // in the loop, we can hoist or sink the call as appropriate.
458 bool FoundMod = false;
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000459 for (AliasSet &AS : *CurAST) {
Duncan Sands68b6f502007-12-01 07:51:45 +0000460 if (!AS.isForwardingAliasSet() && AS.isMod()) {
461 FoundMod = true;
462 break;
Chris Lattner20cda262004-03-15 04:11:30 +0000463 }
Chris Lattner20cda262004-03-15 04:11:30 +0000464 }
Duncan Sands68b6f502007-12-01 07:51:45 +0000465 if (!FoundMod) return true;
Chris Lattner20cda262004-03-15 04:11:30 +0000466 }
467
Nadav Rotem03dcd852012-09-04 10:25:04 +0000468 // FIXME: This should use mod/ref information to see if we can hoist or
469 // sink the call.
Misha Brukmanb1c93172005-04-21 23:48:37 +0000470
Chris Lattner20cda262004-03-15 04:11:30 +0000471 return false;
Chris Lattner65c11932003-12-09 19:32:44 +0000472 }
473
Nadav Rotem03dcd852012-09-04 10:25:04 +0000474 // Only these instructions are hoistable/sinkable.
Benjamin Kramer130fcde2013-01-09 18:12:03 +0000475 if (!isa<BinaryOperator>(I) && !isa<CastInst>(I) && !isa<SelectInst>(I) &&
476 !isa<GetElementPtrInst>(I) && !isa<CmpInst>(I) &&
477 !isa<InsertElementInst>(I) && !isa<ExtractElementInst>(I) &&
478 !isa<ShuffleVectorInst>(I) && !isa<ExtractValueInst>(I) &&
479 !isa<InsertValueInst>(I))
480 return false;
Nadav Rotem03dcd852012-09-04 10:25:04 +0000481
Philip Reamesb47b9c22015-05-22 02:14:05 +0000482 // TODO: Plumb the context instruction through to make hoisting and sinking
483 // more powerful. Hoisting of loads already works due to the special casing
484 // above.
485 return isSafeToExecuteUnconditionally(I, DT, TLI, CurLoop, SafetyInfo,
486 nullptr);
Chris Lattneraaaea512003-12-10 06:41:05 +0000487}
488
Hal Finkel3d4269a2015-02-22 18:35:32 +0000489/// Returns true if a PHINode is a trivially replaceable with an
Chandler Carruth8765cf72014-01-25 04:07:24 +0000490/// Instruction.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000491/// This is true when all incoming values are that instruction.
492/// This pattern occurs most often with LCSSA PHI nodes.
Chandler Carruth8765cf72014-01-25 04:07:24 +0000493///
Pete Cooper47e80cd2015-05-12 20:05:20 +0000494static bool isTriviallyReplacablePHI(const PHINode &PN, const Instruction &I) {
Pete Cooper833f34d2015-05-12 20:05:31 +0000495 for (const Value *IncValue : PN.incoming_values())
496 if (IncValue != &I)
Chandler Carruth8765cf72014-01-25 04:07:24 +0000497 return false;
498
499 return true;
500}
501
Hal Finkel3d4269a2015-02-22 18:35:32 +0000502/// Return true if the only users of this instruction are outside of
503/// the loop. If this is true, we can sink the instruction to the exit
504/// blocks of the loop.
Chris Lattneraaaea512003-12-10 06:41:05 +0000505///
David Majnemer42a07302016-01-04 03:37:39 +0000506static bool isNotUsedInLoop(const Instruction &I, const Loop *CurLoop,
507 const LICMSafetyInfo *SafetyInfo) {
508 const auto &BlockColors = SafetyInfo->BlockColors;
Pete Cooper0cabcf22015-05-13 01:12:18 +0000509 for (const User *U : I.users()) {
510 const Instruction *UI = cast<Instruction>(U);
511 if (const PHINode *PN = dyn_cast<PHINode>(UI)) {
David Majnemer42a07302016-01-04 03:37:39 +0000512 const BasicBlock *BB = PN->getParent();
513 // We cannot sink uses in catchswitches.
514 if (isa<CatchSwitchInst>(BB->getTerminator()))
515 return false;
516
517 // We need to sink a callsite to a unique funclet. Avoid sinking if the
518 // phi use is too muddled.
519 if (isa<CallInst>(I))
520 if (!BlockColors.empty() &&
521 BlockColors.find(const_cast<BasicBlock *>(BB))->second.size() != 1)
522 return false;
523
Chandler Carruth8765cf72014-01-25 04:07:24 +0000524 // A PHI node where all of the incoming values are this instruction are
525 // special -- they can just be RAUW'ed with the instruction and thus
526 // don't require a use in the predecessor. This is a particular important
527 // special case because it is the pattern found in LCSSA form.
528 if (isTriviallyReplacablePHI(*PN, I)) {
529 if (CurLoop->contains(PN))
530 return false;
531 else
532 continue;
533 }
534
535 // Otherwise, PHI node uses occur in predecessor blocks if the incoming
536 // values. Check for such a use being inside the loop.
Chris Lattner34399dd2003-12-11 22:23:32 +0000537 for (unsigned i = 0, e = PN->getNumIncomingValues(); i != e; ++i)
538 if (PN->getIncomingValue(i) == &I)
539 if (CurLoop->contains(PN->getIncomingBlock(i)))
540 return false;
Chandler Carruth8765cf72014-01-25 04:07:24 +0000541
542 continue;
Chris Lattner34399dd2003-12-11 22:23:32 +0000543 }
Chandler Carruth8765cf72014-01-25 04:07:24 +0000544
Chandler Carruthcdf47882014-03-09 03:16:01 +0000545 if (CurLoop->contains(UI))
Chandler Carruth8765cf72014-01-25 04:07:24 +0000546 return false;
Chris Lattner34399dd2003-12-11 22:23:32 +0000547 }
Chris Lattneraaaea512003-12-10 06:41:05 +0000548 return true;
549}
550
David Majnemer42a07302016-01-04 03:37:39 +0000551static Instruction *
552CloneInstructionInExitBlock(Instruction &I, BasicBlock &ExitBlock, PHINode &PN,
553 const LoopInfo *LI,
554 const LICMSafetyInfo *SafetyInfo) {
555 Instruction *New;
556 if (auto *CI = dyn_cast<CallInst>(&I)) {
557 const auto &BlockColors = SafetyInfo->BlockColors;
558
559 // Sinking call-sites need to be handled differently from other
560 // instructions. The cloned call-site needs a funclet bundle operand
561 // appropriate for it's location in the CFG.
562 SmallVector<OperandBundleDef, 1> OpBundles;
563 for (unsigned BundleIdx = 0, BundleEnd = CI->getNumOperandBundles();
564 BundleIdx != BundleEnd; ++BundleIdx) {
565 OperandBundleUse Bundle = CI->getOperandBundleAt(BundleIdx);
566 if (Bundle.getTagID() == LLVMContext::OB_funclet)
567 continue;
568
569 OpBundles.emplace_back(Bundle);
570 }
571
572 if (!BlockColors.empty()) {
573 const ColorVector &CV = BlockColors.find(&ExitBlock)->second;
574 assert(CV.size() == 1 && "non-unique color for exit block!");
575 BasicBlock *BBColor = CV.front();
576 Instruction *EHPad = BBColor->getFirstNonPHI();
577 if (EHPad->isEHPad())
578 OpBundles.emplace_back("funclet", EHPad);
579 }
580
581 New = CallInst::Create(CI, OpBundles);
582 } else {
583 New = I.clone();
584 }
585
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000586 ExitBlock.getInstList().insert(ExitBlock.getFirstInsertionPt(), New);
587 if (!I.getName().empty()) New->setName(I.getName() + ".le");
588
589 // Build LCSSA PHI nodes for any in-loop operands. Note that this is
590 // particularly cheap because we can rip off the PHI node that we're
591 // replacing for the number and blocks of the predecessors.
592 // OPT: If this shows up in a profile, we can instead finish sinking all
593 // invariant instructions, and then walk their operands to re-establish
594 // LCSSA. That will eliminate creating PHI nodes just to nuke them when
595 // sinking bottom-up.
596 for (User::op_iterator OI = New->op_begin(), OE = New->op_end(); OI != OE;
597 ++OI)
598 if (Instruction *OInst = dyn_cast<Instruction>(*OI))
599 if (Loop *OLoop = LI->getLoopFor(OInst->getParent()))
600 if (!OLoop->contains(&PN)) {
601 PHINode *OpPN =
602 PHINode::Create(OInst->getType(), PN.getNumIncomingValues(),
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000603 OInst->getName() + ".lcssa", &ExitBlock.front());
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000604 for (unsigned i = 0, e = PN.getNumIncomingValues(); i != e; ++i)
605 OpPN->addIncoming(OInst, PN.getIncomingBlock(i));
606 *OI = OpPN;
607 }
608 return New;
609}
610
Hal Finkel3d4269a2015-02-22 18:35:32 +0000611/// When an instruction is found to only be used outside of the loop, this
612/// function moves it to the exit blocks and patches up SSA form as needed.
Chris Lattner91846012003-12-19 08:18:16 +0000613/// This method is guaranteed to remove the original instruction from its
614/// position, and may either delete it or move it to outside of the loop.
Chris Lattneraaaea512003-12-10 06:41:05 +0000615///
Pete Cooper0cabcf22015-05-13 01:12:18 +0000616static bool sink(Instruction &I, const LoopInfo *LI, const DominatorTree *DT,
David Majnemer42a07302016-01-04 03:37:39 +0000617 const Loop *CurLoop, AliasSetTracker *CurAST,
618 const LICMSafetyInfo *SafetyInfo) {
Nick Lewycky299c6df2010-07-30 20:27:01 +0000619 DEBUG(dbgs() << "LICM sinking instruction: " << I << "\n");
Hal Finkel3d4269a2015-02-22 18:35:32 +0000620 bool Changed = false;
Chris Lattner55c21132003-12-10 20:43:29 +0000621 if (isa<LoadInst>(I)) ++NumMovedLoads;
Chris Lattner20cda262004-03-15 04:11:30 +0000622 else if (isa<CallInst>(I)) ++NumMovedCalls;
Chris Lattner55c21132003-12-10 20:43:29 +0000623 ++NumSunk;
624 Changed = true;
625
Chandler Carruthfc258542014-02-11 12:52:27 +0000626#ifndef NDEBUG
627 SmallVector<BasicBlock *, 32> ExitBlocks;
628 CurLoop->getUniqueExitBlocks(ExitBlocks);
Hal Finkel3d4269a2015-02-22 18:35:32 +0000629 SmallPtrSet<BasicBlock *, 32> ExitBlockSet(ExitBlocks.begin(),
630 ExitBlocks.end());
Chandler Carruthfc258542014-02-11 12:52:27 +0000631#endif
Chandler Carruth8765cf72014-01-25 04:07:24 +0000632
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000633 // Clones of this instruction. Don't create more than one per exit block!
634 SmallDenseMap<BasicBlock *, Instruction *, 32> SunkCopies;
635
Chandler Carruthfc258542014-02-11 12:52:27 +0000636 // If this instruction is only used outside of the loop, then all users are
637 // PHI nodes in exit blocks due to LCSSA form. Just RAUW them with clones of
638 // the instruction.
639 while (!I.use_empty()) {
David Majnemer6bc83e02015-07-12 03:53:05 +0000640 Value::user_iterator UI = I.user_begin();
641 auto *User = cast<Instruction>(*UI);
David Majnemer49428102014-09-02 16:22:00 +0000642 if (!DT->isReachableFromEntry(User->getParent())) {
643 User->replaceUsesOfWith(&I, UndefValue::get(I.getType()));
644 continue;
645 }
Chandler Carruthfc258542014-02-11 12:52:27 +0000646 // The user must be a PHI node.
David Majnemer49428102014-09-02 16:22:00 +0000647 PHINode *PN = cast<PHINode>(User);
Chris Lattnercc9cbc62010-08-29 17:46:00 +0000648
David Majnemer6bc83e02015-07-12 03:53:05 +0000649 // Surprisingly, instructions can be used outside of loops without any
650 // exits. This can only happen in PHI nodes if the incoming block is
651 // unreachable.
652 Use &U = UI.getUse();
653 BasicBlock *BB = PN->getIncomingBlock(U);
654 if (!DT->isReachableFromEntry(BB)) {
655 U = UndefValue::get(I.getType());
656 continue;
657 }
658
Chandler Carruthfc258542014-02-11 12:52:27 +0000659 BasicBlock *ExitBlock = PN->getParent();
660 assert(ExitBlockSet.count(ExitBlock) &&
661 "The LCSSA PHI is not in an exit block!");
662
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000663 Instruction *New;
664 auto It = SunkCopies.find(ExitBlock);
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000665 if (It != SunkCopies.end())
Evgeniy Stepanov10280da2014-06-25 07:54:58 +0000666 New = It->second;
Evgeniy Stepanovd99cca22014-06-25 09:17:21 +0000667 else
668 New = SunkCopies[ExitBlock] =
David Majnemer42a07302016-01-04 03:37:39 +0000669 CloneInstructionInExitBlock(I, *ExitBlock, *PN, LI, SafetyInfo);
Chandler Carruthfc258542014-02-11 12:52:27 +0000670
671 PN->replaceAllUsesWith(New);
672 PN->eraseFromParent();
Chris Lattnercd96b4d2010-08-29 04:28:20 +0000673 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000674
Chris Lattner1a1ed692010-08-29 18:00:00 +0000675 CurAST->deleteValue(&I);
Chandler Carruthfc258542014-02-11 12:52:27 +0000676 I.eraseFromParent();
Hal Finkel3d4269a2015-02-22 18:35:32 +0000677 return Changed;
Chris Lattneraaaea512003-12-10 06:41:05 +0000678}
Chris Lattner64437692002-09-29 21:46:09 +0000679
Hal Finkel3d4269a2015-02-22 18:35:32 +0000680/// When an instruction is found to only use loop invariant operands that
681/// is safe to hoist, this instruction is called to do the dirty work.
Chris Lattnerf64f2d32002-09-26 16:52:07 +0000682///
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000683static bool hoist(Instruction &I, const DominatorTree *DT, const Loop *CurLoop,
684 const LICMSafetyInfo *SafetyInfo) {
685 auto *Preheader = CurLoop->getLoopPreheader();
David Greene0fd86222010-01-05 01:27:30 +0000686 DEBUG(dbgs() << "LICM hoisting to " << Preheader->getName() << ": "
Evan Chengf8158612009-10-12 22:25:23 +0000687 << I << "\n");
Sanjoy Das7a2e2be2016-01-28 15:51:58 +0000688
689 // Metadata can be dependent on conditions we are hoisting above.
690 // Conservatively strip all metadata on the instruction unless we were
691 // guaranteed to execute I if we entered the loop, in which case the metadata
692 // is valid in the loop preheader.
693 if (I.hasMetadataOtherThanDebugLoc() &&
694 // The check on hasMetadataOtherThanDebugLoc is to prevent us from burning
695 // time in isGuaranteedToExecute if we don't actually have anything to
696 // drop. It is a compile time optimization, not required for correctness.
697 !isGuaranteedToExecute(I, DT, CurLoop, SafetyInfo))
698 I.dropUnknownNonDebugMetadata();
699
Chris Lattner6ac06592010-08-29 18:18:40 +0000700 // Move the new node to the Preheader, before its terminator.
701 I.moveBefore(Preheader->getTerminator());
Misha Brukmanb1c93172005-04-21 23:48:37 +0000702
Chris Lattneraaaea512003-12-10 06:41:05 +0000703 if (isa<LoadInst>(I)) ++NumMovedLoads;
Chris Lattner20cda262004-03-15 04:11:30 +0000704 else if (isa<CallInst>(I)) ++NumMovedCalls;
Chris Lattner718b2212002-09-26 16:38:03 +0000705 ++NumHoisted;
Hal Finkel3d4269a2015-02-22 18:35:32 +0000706 return true;
Chris Lattner6ec05f52002-05-10 22:44:58 +0000707}
708
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000709/// Only sink or hoist an instruction if it is not a trapping instruction,
710/// or if the instruction is known not to trap when moved to the preheader.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000711/// or if it is a trapping instruction and is guaranteed to execute.
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000712static bool isSafeToExecuteUnconditionally(const Instruction &Inst,
Pete Cooper0cabcf22015-05-13 01:12:18 +0000713 const DominatorTree *DT,
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000714 const TargetLibraryInfo *TLI,
Pete Cooper0cabcf22015-05-13 01:12:18 +0000715 const Loop *CurLoop,
Philip Reamesb47b9c22015-05-22 02:14:05 +0000716 const LICMSafetyInfo *SafetyInfo,
717 const Instruction *CtxI) {
Sanjoy Dasf8a0db52015-05-18 18:07:00 +0000718 if (isSafeToSpeculativelyExecute(&Inst, CtxI, DT, TLI))
Eli Friedmanb8f6a4f2009-07-17 04:28:42 +0000719 return true;
Misha Brukmanb1c93172005-04-21 23:48:37 +0000720
Hal Finkel3d4269a2015-02-22 18:35:32 +0000721 return isGuaranteedToExecute(Inst, DT, CurLoop, SafetyInfo);
Eli Friedman0cdc1482011-07-20 21:37:47 +0000722}
723
Pete Cooper0cabcf22015-05-13 01:12:18 +0000724static bool isGuaranteedToExecute(const Instruction &Inst,
725 const DominatorTree *DT,
726 const Loop *CurLoop,
727 const LICMSafetyInfo * SafetyInfo) {
Nadav Rotem03dcd852012-09-04 10:25:04 +0000728
Philip Reamesb35f46c2014-12-29 23:00:57 +0000729 // We have to check to make sure that the instruction dominates all
Chris Lattnerc0517682003-12-09 17:18:00 +0000730 // of the exit blocks. If it doesn't, then there is a path out of the loop
731 // which does not execute this instruction, so we can't hoist it.
Tanya Lattner57c03df2003-08-05 18:45:46 +0000732
Chris Lattnerc0517682003-12-09 17:18:00 +0000733 // If the instruction is in the header block for the loop (which is very
734 // common), it is always guaranteed to dominate the exit blocks. Since this
735 // is a common case, and can save some work, check it now.
Chris Lattneraaaea512003-12-10 06:41:05 +0000736 if (Inst.getParent() == CurLoop->getHeader())
Philip Reamesb35f46c2014-12-29 23:00:57 +0000737 // If there's a throw in the header block, we can't guarantee we'll reach
738 // Inst.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000739 return !SafetyInfo->HeaderMayThrow;
Philip Reamesb35f46c2014-12-29 23:00:57 +0000740
741 // Somewhere in this loop there is an instruction which may throw and make us
742 // exit the loop.
Hal Finkel3d4269a2015-02-22 18:35:32 +0000743 if (SafetyInfo->MayThrow)
Philip Reamesb35f46c2014-12-29 23:00:57 +0000744 return false;
Tanya Lattner57c03df2003-08-05 18:45:46 +0000745
Chris Lattnerc0517682003-12-09 17:18:00 +0000746 // Get the exit blocks for the current loop.
Devang Patelb5933bb2007-08-21 00:31:24 +0000747 SmallVector<BasicBlock*, 8> ExitBlocks;
Chris Lattner35eaa552004-04-18 22:15:13 +0000748 CurLoop->getExitBlocks(ExitBlocks);
Chris Lattnerc0517682003-12-09 17:18:00 +0000749
Chris Lattner27497ec2011-01-02 18:45:39 +0000750 // Verify that the block dominates each of the exit blocks of the loop.
Sanjay Patel9f088ab2016-01-08 22:59:42 +0000751 for (BasicBlock *ExitBlock : ExitBlocks)
752 if (!DT->dominates(Inst.getParent(), ExitBlock))
Chris Lattneraaaea512003-12-10 06:41:05 +0000753 return false;
Misha Brukmanb1c93172005-04-21 23:48:37 +0000754
Nick Lewycky78ee67e2012-05-01 04:03:01 +0000755 // As a degenerate case, if the loop is statically infinite then we haven't
756 // proven anything since there are no exit blocks.
757 if (ExitBlocks.empty())
758 return false;
759
Tanya Lattner57c03df2003-08-05 18:45:46 +0000760 return true;
761}
762
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000763namespace {
764 class LoopPromoter : public LoadAndStorePromoter {
765 Value *SomePtr; // Designated pointer to store to.
Craig Topper71b7b682014-08-21 05:55:13 +0000766 SmallPtrSetImpl<Value*> &PointerMustAliases;
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000767 SmallVectorImpl<BasicBlock*> &LoopExitBlocks;
Dan Gohmanb9487362012-08-08 00:00:26 +0000768 SmallVectorImpl<Instruction*> &LoopInsertPts;
Chandler Carruthfc258542014-02-11 12:52:27 +0000769 PredIteratorCache &PredCache;
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000770 AliasSetTracker &AST;
Chandler Carruthfc258542014-02-11 12:52:27 +0000771 LoopInfo &LI;
Eli Friedmanddf7f552011-05-27 20:31:51 +0000772 DebugLoc DL;
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000773 int Alignment;
Hal Finkelcc39b672014-07-24 12:16:19 +0000774 AAMDNodes AATags;
Chandler Carruthfc258542014-02-11 12:52:27 +0000775
776 Value *maybeInsertLCSSAPHI(Value *V, BasicBlock *BB) const {
777 if (Instruction *I = dyn_cast<Instruction>(V))
778 if (Loop *L = LI.getLoopFor(I->getParent()))
779 if (!L->contains(BB)) {
780 // We need to create an LCSSA PHI node for the incoming value and
781 // store that.
Duncan P. N. Exon Smithbe4d8cb2015-10-13 19:26:58 +0000782 PHINode *PN =
783 PHINode::Create(I->getType(), PredCache.size(BB),
784 I->getName() + ".lcssa", &BB->front());
Daniel Berlinb4e7a4a2015-04-21 21:11:50 +0000785 for (BasicBlock *Pred : PredCache.get(BB))
786 PN->addIncoming(I, Pred);
Chandler Carruthfc258542014-02-11 12:52:27 +0000787 return PN;
788 }
789 return V;
790 }
791
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000792 public:
Pete Cooper41e0ee32015-05-13 01:12:16 +0000793 LoopPromoter(Value *SP,
794 ArrayRef<const Instruction *> Insts,
Craig Topper71b7b682014-08-21 05:55:13 +0000795 SSAUpdater &S, SmallPtrSetImpl<Value *> &PMA,
Chandler Carruthfc258542014-02-11 12:52:27 +0000796 SmallVectorImpl<BasicBlock *> &LEB,
797 SmallVectorImpl<Instruction *> &LIP, PredIteratorCache &PIC,
798 AliasSetTracker &ast, LoopInfo &li, DebugLoc dl, int alignment,
Hal Finkelcc39b672014-07-24 12:16:19 +0000799 const AAMDNodes &AATags)
Chandler Carruthfc258542014-02-11 12:52:27 +0000800 : LoadAndStorePromoter(Insts, S), SomePtr(SP), PointerMustAliases(PMA),
801 LoopExitBlocks(LEB), LoopInsertPts(LIP), PredCache(PIC), AST(ast),
Hal Finkelcc39b672014-07-24 12:16:19 +0000802 LI(li), DL(dl), Alignment(alignment), AATags(AATags) {}
Tobias Grossera3928f52011-07-06 19:20:02 +0000803
Craig Topper3e4c6972014-03-05 09:10:37 +0000804 bool isInstInList(Instruction *I,
805 const SmallVectorImpl<Instruction*> &) const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000806 Value *Ptr;
807 if (LoadInst *LI = dyn_cast<LoadInst>(I))
808 Ptr = LI->getOperand(0);
809 else
810 Ptr = cast<StoreInst>(I)->getPointerOperand();
811 return PointerMustAliases.count(Ptr);
812 }
Tobias Grossera3928f52011-07-06 19:20:02 +0000813
Craig Topper3e4c6972014-03-05 09:10:37 +0000814 void doExtraRewritesBeforeFinalDeletion() const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000815 // Insert stores after in the loop exit blocks. Each exit block gets a
816 // store of the live-out values that feed them. Since we've already told
817 // the SSA updater about the defs in the loop and the preheader
818 // definition, it is all set and we can start using it.
819 for (unsigned i = 0, e = LoopExitBlocks.size(); i != e; ++i) {
820 BasicBlock *ExitBlock = LoopExitBlocks[i];
821 Value *LiveInValue = SSA.GetValueInMiddleOfBlock(ExitBlock);
Chandler Carruthfc258542014-02-11 12:52:27 +0000822 LiveInValue = maybeInsertLCSSAPHI(LiveInValue, ExitBlock);
823 Value *Ptr = maybeInsertLCSSAPHI(SomePtr, ExitBlock);
Dan Gohmanb9487362012-08-08 00:00:26 +0000824 Instruction *InsertPos = LoopInsertPts[i];
Chandler Carruthfc258542014-02-11 12:52:27 +0000825 StoreInst *NewSI = new StoreInst(LiveInValue, Ptr, InsertPos);
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000826 NewSI->setAlignment(Alignment);
Eli Friedmanddf7f552011-05-27 20:31:51 +0000827 NewSI->setDebugLoc(DL);
Hal Finkelcc39b672014-07-24 12:16:19 +0000828 if (AATags) NewSI->setAAMetadata(AATags);
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000829 }
830 }
831
Craig Topper3e4c6972014-03-05 09:10:37 +0000832 void replaceLoadWithValue(LoadInst *LI, Value *V) const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000833 // Update alias analysis.
834 AST.copyValue(LI, V);
835 }
Craig Topper3e4c6972014-03-05 09:10:37 +0000836 void instructionDeleted(Instruction *I) const override {
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000837 AST.deleteValue(I);
838 }
839 };
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000840} // end anon namespace
Chris Lattnerb68ec5c2011-01-15 00:12:35 +0000841
Hal Finkel3d4269a2015-02-22 18:35:32 +0000842/// Try to promote memory values to scalars by sinking stores out of the
843/// loop and moving loads to before the loop. We do this by looping over
844/// the stores in the loop, looking for stores to Must pointers which are
845/// loop invariant.
Chris Lattner45d67d62003-02-24 03:52:32 +0000846///
Hal Finkel3d4269a2015-02-22 18:35:32 +0000847bool llvm::promoteLoopAccessesToScalars(AliasSet &AS,
848 SmallVectorImpl<BasicBlock*>&ExitBlocks,
849 SmallVectorImpl<Instruction*>&InsertPts,
850 PredIteratorCache &PIC, LoopInfo *LI,
Philip Reamesb54c8e62016-03-09 22:59:30 +0000851 DominatorTree *DT,
852 const TargetLibraryInfo *TLI,
853 Loop *CurLoop,
Hal Finkel3d4269a2015-02-22 18:35:32 +0000854 AliasSetTracker *CurAST,
855 LICMSafetyInfo * SafetyInfo) {
856 // Verify inputs.
857 assert(LI != nullptr && DT != nullptr &&
858 CurLoop != nullptr && CurAST != nullptr &&
859 SafetyInfo != nullptr &&
860 "Unexpected Input to promoteLoopAccessesToScalars");
Sanjay Patel99133222016-01-13 23:01:57 +0000861
Chris Lattner1dc98b42010-08-29 06:43:52 +0000862 // We can promote this alias set if it has a store, if it is a "Must" alias
863 // set, if the pointer is loop invariant, and if we are not eliminating any
864 // volatile loads or stores.
865 if (AS.isForwardingAliasSet() || !AS.isMod() || !AS.isMustAlias() ||
866 AS.isVolatile() || !CurLoop->isLoopInvariant(AS.begin()->getValue()))
Sanjay Patel99133222016-01-13 23:01:57 +0000867 return false;
Tobias Grossera3928f52011-07-06 19:20:02 +0000868
Chris Lattner1dc98b42010-08-29 06:43:52 +0000869 assert(!AS.empty() &&
870 "Must alias set should have at least one pointer element in it!");
Hal Finkel3d4269a2015-02-22 18:35:32 +0000871
Chris Lattner1dc98b42010-08-29 06:43:52 +0000872 Value *SomePtr = AS.begin()->getValue();
Hal Finkel3d4269a2015-02-22 18:35:32 +0000873 BasicBlock * Preheader = CurLoop->getLoopPreheader();
Chris Lattner45d67d62003-02-24 03:52:32 +0000874
Chris Lattner1dc98b42010-08-29 06:43:52 +0000875 // It isn't safe to promote a load/store from the loop if the load/store is
876 // conditional. For example, turning:
Chris Lattner45d67d62003-02-24 03:52:32 +0000877 //
Chris Lattner1dc98b42010-08-29 06:43:52 +0000878 // for () { if (c) *P += 1; }
Chris Lattner45d67d62003-02-24 03:52:32 +0000879 //
Chris Lattner1dc98b42010-08-29 06:43:52 +0000880 // into:
881 //
882 // tmp = *P; for () { if (c) tmp +=1; } *P = tmp;
883 //
884 // is not safe, because *P may only be valid to access if 'c' is true.
Tobias Grossera3928f52011-07-06 19:20:02 +0000885 //
Philip Reamesb54c8e62016-03-09 22:59:30 +0000886 // The safety property divides into two parts:
887 // 1) The memory may not be dereferenceable on entry to the loop. In this
888 // case, we can't insert the required load in the preheader.
889 // 2) The memory model does not allow us to insert a store along any dynamic
890 // path which did not originally have one.
891 //
Chris Lattner1dc98b42010-08-29 06:43:52 +0000892 // It is safe to promote P if all uses are direct load/stores and if at
893 // least one is guaranteed to be executed.
894 bool GuaranteedToExecute = false;
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000895
Philip Reamesb54c8e62016-03-09 22:59:30 +0000896 // It is also safe to promote P if we can prove that speculating a load into
897 // the preheader is safe (i.e. proving dereferenceability on all
898 // paths through the loop), and that the memory can be proven thread local
899 // (so that the memory model requirement doesn't apply.) We first establish
900 // the former, and then run a capture analysis below to establish the later.
901 // We can use any access within the alias set to prove dereferenceability
902 // since they're all must alias.
903 bool CanSpeculateLoad = false;
904
Chris Lattner1dc98b42010-08-29 06:43:52 +0000905 SmallVector<Instruction*, 64> LoopUses;
906 SmallPtrSet<Value*, 4> PointerMustAliases;
Chris Lattner45d67d62003-02-24 03:52:32 +0000907
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000908 // We start with an alignment of one and try to find instructions that allow
909 // us to prove better alignment.
910 unsigned Alignment = 1;
Hal Finkelcc39b672014-07-24 12:16:19 +0000911 AAMDNodes AATags;
Bruno Cardoso Lopes46d5bf22014-11-28 19:47:46 +0000912 bool HasDedicatedExits = CurLoop->hasDedicatedExits();
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000913
Philip Reamesb54c8e62016-03-09 22:59:30 +0000914 // Don't sink stores from loops without dedicated block exits. Exits
915 // containing indirect branches are not transformed by loop simplify,
916 // make sure we catch that. An additional load may be generated in the
917 // preheader for SSA updater, so also avoid sinking when no preheader
918 // is available.
919 if (!HasDedicatedExits || !Preheader)
920 return false;
921
922 const DataLayout &MDL = Preheader->getModule()->getDataLayout();
923
Chris Lattner1dc98b42010-08-29 06:43:52 +0000924 // Check that all of the pointers in the alias set have the same type. We
925 // cannot (yet) promote a memory location that is loaded and stored in
Hal Finkelcc39b672014-07-24 12:16:19 +0000926 // different sizes. While we are at it, collect alignment and AA info.
Sanjay Patel99133222016-01-13 23:01:57 +0000927 bool Changed = false;
Chris Lattner1dc98b42010-08-29 06:43:52 +0000928 for (AliasSet::iterator ASI = AS.begin(), E = AS.end(); ASI != E; ++ASI) {
929 Value *ASIV = ASI->getValue();
930 PointerMustAliases.insert(ASIV);
Tobias Grossera3928f52011-07-06 19:20:02 +0000931
Chris Lattnerf12c08d2008-05-22 00:53:38 +0000932 // Check that all of the pointers in the alias set have the same type. We
933 // cannot (yet) promote a memory location that is loaded and stored in
934 // different sizes.
Chris Lattner1dc98b42010-08-29 06:43:52 +0000935 if (SomePtr->getType() != ASIV->getType())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000936 return Changed;
Tobias Grossera3928f52011-07-06 19:20:02 +0000937
Chandler Carruthcdf47882014-03-09 03:16:01 +0000938 for (User *U : ASIV->users()) {
Chris Lattner1dc98b42010-08-29 06:43:52 +0000939 // Ignore instructions that are outside the loop.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000940 Instruction *UI = dyn_cast<Instruction>(U);
941 if (!UI || !CurLoop->contains(UI))
Chris Lattnerf12c08d2008-05-22 00:53:38 +0000942 continue;
Tobias Grossera3928f52011-07-06 19:20:02 +0000943
Chris Lattner1dc98b42010-08-29 06:43:52 +0000944 // If there is an non-load/store instruction in the loop, we can't promote
945 // it.
Sanjay Patel9f49b682016-01-08 22:05:03 +0000946 if (const LoadInst *Load = dyn_cast<LoadInst>(UI)) {
947 assert(!Load->isVolatile() && "AST broken");
948 if (!Load->isSimple())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000949 return Changed;
Philip Reamesb54c8e62016-03-09 22:59:30 +0000950
951 if (!GuaranteedToExecute && !CanSpeculateLoad)
952 CanSpeculateLoad =
953 isSafeToExecuteUnconditionally(*Load, DT, TLI, CurLoop,
954 SafetyInfo,
955 Preheader->getTerminator());
Sanjay Patel9f49b682016-01-08 22:05:03 +0000956 } else if (const StoreInst *Store = dyn_cast<StoreInst>(UI)) {
Chris Lattner408a6842010-12-19 05:57:25 +0000957 // Stores *of* the pointer are not interesting, only stores *to* the
958 // pointer.
Chandler Carruthcdf47882014-03-09 03:16:01 +0000959 if (UI->getOperand(1) != ASIV)
Chris Lattner408a6842010-12-19 05:57:25 +0000960 continue;
Sanjay Patel9f49b682016-01-08 22:05:03 +0000961 assert(!Store->isVolatile() && "AST broken");
962 if (!Store->isSimple())
Hal Finkel3d4269a2015-02-22 18:35:32 +0000963 return Changed;
Eli Friedman0cdc1482011-07-20 21:37:47 +0000964
965 // Note that we only check GuaranteedToExecute inside the store case
966 // so that we do not introduce stores where they did not exist before
967 // (which would break the LLVM concurrency model).
968
969 // If the alignment of this instruction allows us to specify a more
970 // restrictive (and performant) alignment and if we are sure this
971 // instruction will be executed, update the alignment.
972 // Larger is better, with the exception of 0 being the best alignment.
Sanjay Patel9f49b682016-01-08 22:05:03 +0000973 unsigned InstAlignment = Store->getAlignment();
Chris Lattnerf5cca682012-12-31 08:37:17 +0000974 if ((InstAlignment > Alignment || InstAlignment == 0) && Alignment != 0)
Hal Finkel3d4269a2015-02-22 18:35:32 +0000975 if (isGuaranteedToExecute(*UI, DT, CurLoop, SafetyInfo)) {
Eli Friedman0cdc1482011-07-20 21:37:47 +0000976 GuaranteedToExecute = true;
977 Alignment = InstAlignment;
978 }
979
980 if (!GuaranteedToExecute)
Hal Finkel3d4269a2015-02-22 18:35:32 +0000981 GuaranteedToExecute = isGuaranteedToExecute(*UI, DT,
982 CurLoop, SafetyInfo);
Eli Friedman0cdc1482011-07-20 21:37:47 +0000983
Philip Reamesb54c8e62016-03-09 22:59:30 +0000984
985 if (!GuaranteedToExecute && !CanSpeculateLoad) {
986 CanSpeculateLoad =
987 isDereferenceableAndAlignedPointer(Store->getPointerOperand(),
988 Store->getAlignment(), MDL,
989 Preheader->getTerminator(),
990 DT, TLI);
991 }
Chris Lattnerbe901902010-09-06 05:11:24 +0000992 } else
Hal Finkel3d4269a2015-02-22 18:35:32 +0000993 return Changed; // Not a load or store.
Tobias Grosser4a5d9a92011-07-06 19:19:55 +0000994
Hal Finkelcc39b672014-07-24 12:16:19 +0000995 // Merge the AA tags.
Chris Lattnerf5cca682012-12-31 08:37:17 +0000996 if (LoopUses.empty()) {
Hal Finkelcc39b672014-07-24 12:16:19 +0000997 // On the first load/store, just take its AA tags.
998 UI->getAAMetadata(AATags);
999 } else if (AATags) {
1000 UI->getAAMetadata(AATags, /* Merge = */ true);
Chris Lattnerf5cca682012-12-31 08:37:17 +00001001 }
Chandler Carruthcdf47882014-03-09 03:16:01 +00001002
1003 LoopUses.push_back(UI);
Chris Lattner1dc98b42010-08-29 06:43:52 +00001004 }
1005 }
Tobias Grosser4a5d9a92011-07-06 19:19:55 +00001006
Philip Reamesb54c8e62016-03-09 22:59:30 +00001007 // Check legality per comment above. Otherwise, we can't promote.
1008 bool PromotionIsLegal = GuaranteedToExecute;
1009 if (!PromotionIsLegal && CanSpeculateLoad) {
1010 // If this is a thread local location, then we can insert stores along
1011 // paths which originally didn't have them without violating the memory
1012 // model.
1013 Value *Object = GetUnderlyingObject(SomePtr, MDL);
1014 PromotionIsLegal = isAllocLikeFn(Object, TLI) &&
1015 !PointerMayBeCaptured(Object, true, true);
1016 }
1017 if (!PromotionIsLegal)
Hal Finkel3d4269a2015-02-22 18:35:32 +00001018 return Changed;
Tobias Grossera3928f52011-07-06 19:20:02 +00001019
David Majnemer219055f2016-01-04 17:42:19 +00001020 // Figure out the loop exits and their insertion points, if this is the
1021 // first promotion.
1022 if (ExitBlocks.empty()) {
1023 CurLoop->getUniqueExitBlocks(ExitBlocks);
1024 InsertPts.clear();
1025 InsertPts.reserve(ExitBlocks.size());
David Majnemerb33f3a22016-01-04 23:16:22 +00001026 for (BasicBlock *ExitBlock : ExitBlocks)
David Majnemer219055f2016-01-04 17:42:19 +00001027 InsertPts.push_back(&*ExitBlock->getFirstInsertionPt());
David Majnemer219055f2016-01-04 17:42:19 +00001028 }
1029
David Majnemerb33f3a22016-01-04 23:16:22 +00001030 // Can't insert into a catchswitch.
1031 for (BasicBlock *ExitBlock : ExitBlocks)
1032 if (isa<CatchSwitchInst>(ExitBlock->getTerminator()))
1033 return Changed;
1034
Chris Lattner1dc98b42010-08-29 06:43:52 +00001035 // Otherwise, this is safe to promote, lets do it!
Tobias Grossera3928f52011-07-06 19:20:02 +00001036 DEBUG(dbgs() << "LICM: Promoting value stored to in loop: " <<*SomePtr<<'\n');
Chris Lattner1dc98b42010-08-29 06:43:52 +00001037 Changed = true;
1038 ++NumPromoted;
1039
Eli Friedmanddf7f552011-05-27 20:31:51 +00001040 // Grab a debug location for the inserted loads/stores; given that the
1041 // inserted loads/stores have little relation to the original loads/stores,
1042 // this code just arbitrarily picks a location from one, since any debug
1043 // location is better than none.
1044 DebugLoc DL = LoopUses[0]->getDebugLoc();
1045
Chris Lattner1dc98b42010-08-29 06:43:52 +00001046 // We use the SSAUpdater interface to insert phi nodes as required.
1047 SmallVector<PHINode*, 16> NewPHIs;
1048 SSAUpdater SSA(&NewPHIs);
Pete Cooper7c4d7b82015-05-13 22:43:09 +00001049 LoopPromoter Promoter(SomePtr, LoopUses, SSA,
Pete Cooper41e0ee32015-05-13 01:12:16 +00001050 PointerMustAliases, ExitBlocks,
Hal Finkelcc39b672014-07-24 12:16:19 +00001051 InsertPts, PIC, *CurAST, *LI, DL, Alignment, AATags);
Tobias Grossera3928f52011-07-06 19:20:02 +00001052
Chris Lattnerb68ec5c2011-01-15 00:12:35 +00001053 // Set up the preheader to have a definition of the value. It is the live-out
1054 // value from the preheader that uses in the loop will use.
1055 LoadInst *PreheaderLoad =
1056 new LoadInst(SomePtr, SomePtr->getName()+".promoted",
1057 Preheader->getTerminator());
Tobias Grosser4a5d9a92011-07-06 19:19:55 +00001058 PreheaderLoad->setAlignment(Alignment);
Eli Friedmanddf7f552011-05-27 20:31:51 +00001059 PreheaderLoad->setDebugLoc(DL);
Hal Finkelcc39b672014-07-24 12:16:19 +00001060 if (AATags) PreheaderLoad->setAAMetadata(AATags);
Chris Lattner1dc98b42010-08-29 06:43:52 +00001061 SSA.AddAvailableValue(Preheader, PreheaderLoad);
1062
Chris Lattnerb68ec5c2011-01-15 00:12:35 +00001063 // Rewrite all the loads in the loop and remember all the definitions from
1064 // stores in the loop.
1065 Promoter.run(LoopUses);
Eli Friedmanc5f22a72011-04-07 01:35:06 +00001066
1067 // If the SSAUpdater didn't use the load in the preheader, just zap it now.
1068 if (PreheaderLoad->use_empty())
1069 PreheaderLoad->eraseFromParent();
Hal Finkel3d4269a2015-02-22 18:35:32 +00001070
1071 return Changed;
Chris Lattnera51fa882002-08-22 21:39:55 +00001072}
Devang Patelb98a0972007-07-31 08:01:41 +00001073
Roman Gareev036c0882016-02-15 14:48:50 +00001074/// Returns an owning pointer to an alias set which incorporates aliasing info
Chandler Carruthad8cb382016-02-27 04:34:07 +00001075/// from L and all subloops of L.
1076AliasSetTracker *LICM::collectAliasInfoForLoop(Loop *L) {
Roman Gareev036c0882016-02-15 14:48:50 +00001077 AliasSetTracker *CurAST = nullptr;
Chandler Carruthad8cb382016-02-27 04:34:07 +00001078 SmallVector<Loop *, 4> RecomputeLoops;
Roman Gareev036c0882016-02-15 14:48:50 +00001079 for (Loop *InnerL : L->getSubLoops()) {
Chandler Carruthad8cb382016-02-27 04:34:07 +00001080 auto MapI = LoopToAliasSetMap.find(InnerL);
1081 // If the AST for this inner loop is missing it may have been merged into
1082 // some other loop's AST and then that loop unrolled, and so we need to
1083 // recompute it.
1084 if (MapI == LoopToAliasSetMap.end()) {
1085 RecomputeLoops.push_back(InnerL);
1086 continue;
1087 }
1088 AliasSetTracker *InnerAST = MapI->second;
Roman Gareev036c0882016-02-15 14:48:50 +00001089
1090 if (CurAST != nullptr) {
1091 // What if InnerLoop was modified by other passes ?
1092 CurAST->add(*InnerAST);
1093
1094 // Once we've incorporated the inner loop's AST into ours, we don't need
1095 // the subloop's anymore.
1096 delete InnerAST;
1097 } else {
1098 CurAST = InnerAST;
1099 }
Chandler Carruthad8cb382016-02-27 04:34:07 +00001100 LoopToAliasSetMap.erase(MapI);
Roman Gareev036c0882016-02-15 14:48:50 +00001101 }
1102 if (CurAST == nullptr)
1103 CurAST = new AliasSetTracker(*AA);
Chandler Carruthad8cb382016-02-27 04:34:07 +00001104
1105 auto mergeLoop = [&](Loop *L) {
1106 // Loop over the body of this loop, looking for calls, invokes, and stores.
1107 // Because subloops have already been incorporated into AST, we skip blocks
1108 // in subloops.
1109 for (BasicBlock *BB : L->blocks())
1110 if (LI->getLoopFor(BB) == L) // Ignore blocks in subloops.
1111 CurAST->add(*BB); // Incorporate the specified basic block
1112 };
1113
1114 // Add everything from the sub loops that are no longer directly available.
1115 for (Loop *InnerL : RecomputeLoops)
1116 mergeLoop(InnerL);
1117
1118 // And merge in this loop.
1119 mergeLoop(L);
1120
Roman Gareev036c0882016-02-15 14:48:50 +00001121 return CurAST;
1122}
1123
Ashutosh Nema47802622015-08-13 11:18:35 +00001124/// Simple analysis hook. Clone alias set info.
Hal Finkel3d4269a2015-02-22 18:35:32 +00001125///
Devang Patelb98a0972007-07-31 08:01:41 +00001126void LICM::cloneBasicBlockAnalysis(BasicBlock *From, BasicBlock *To, Loop *L) {
Chris Lattnercc9cbc62010-08-29 17:46:00 +00001127 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
Devang Patelb98a0972007-07-31 08:01:41 +00001128 if (!AST)
1129 return;
1130
1131 AST->copyValue(From, To);
1132}
1133
Hal Finkel3d4269a2015-02-22 18:35:32 +00001134/// Simple Analysis hook. Delete value V from alias set
1135///
Devang Patelb98a0972007-07-31 08:01:41 +00001136void LICM::deleteAnalysisValue(Value *V, Loop *L) {
Chris Lattnercc9cbc62010-08-29 17:46:00 +00001137 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
Devang Patelb98a0972007-07-31 08:01:41 +00001138 if (!AST)
1139 return;
1140
1141 AST->deleteValue(V);
1142}
David Peixotto0d4d5e62014-09-24 16:48:31 +00001143
1144/// Simple Analysis hook. Delete value L from alias set map.
Hal Finkel3d4269a2015-02-22 18:35:32 +00001145///
David Peixotto0d4d5e62014-09-24 16:48:31 +00001146void LICM::deleteAnalysisLoop(Loop *L) {
1147 AliasSetTracker *AST = LoopToAliasSetMap.lookup(L);
1148 if (!AST)
1149 return;
1150
1151 delete AST;
1152 LoopToAliasSetMap.erase(L);
1153}
Hal Finkel3d4269a2015-02-22 18:35:32 +00001154
1155
1156/// Return true if the body of this loop may store into the memory
1157/// location pointed to by V.
1158///
1159static bool pointerInvalidatedByLoop(Value *V, uint64_t Size,
1160 const AAMDNodes &AAInfo,
1161 AliasSetTracker *CurAST) {
1162 // Check to see if any of the basic blocks in CurLoop invalidate *V.
1163 return CurAST->getAliasSetForPointer(V, Size, AAInfo).isMod();
1164}
1165
1166/// Little predicate that returns true if the specified basic block is in
1167/// a subloop of the current one, not the current one itself.
1168///
1169static bool inSubLoop(BasicBlock *BB, Loop *CurLoop, LoopInfo *LI) {
1170 assert(CurLoop->contains(BB) && "Only valid if BB is IN the loop");
1171 return LI->getLoopFor(BB) != CurLoop;
1172}
1173