blob: bee6e24d25a539208eb1aa080486c94afd8d6f25 [file] [log] [blame]
Owen Andersonf3dd3e22006-05-26 21:11:53 +00001//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
Owen Anderson8eca8912006-05-26 13:58:26 +00002//
3// 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.
Owen Anderson8eca8912006-05-26 13:58:26 +00007//
8//===----------------------------------------------------------------------===//
9//
10// This pass transforms loops by placing phi nodes at the end of the loops for
11// all values that are live across the loop boundary. For example, it turns
12// the left into the right code:
13//
14// for (...) for (...)
Dan Gohmanb5650eb2007-05-11 21:10:54 +000015// if (c) if (c)
Owen Anderson8eca8912006-05-26 13:58:26 +000016// X1 = ... X1 = ...
17// else else
18// X2 = ... X2 = ...
19// X3 = phi(X1, X2) X3 = phi(X1, X2)
Dan Gohman2ad7e732008-06-03 00:57:21 +000020// ... = X3 + 4 X4 = phi(X3)
21// ... = X4 + 4
Owen Anderson8eca8912006-05-26 13:58:26 +000022//
23// This is still valid LLVM; the extra phi nodes are purely redundant, and will
24// be trivially eliminated by InstCombine. The major benefit of this
25// transformation is that it makes many other loop optimizations, such as
26// LoopUnswitching, simpler.
27//
28//===----------------------------------------------------------------------===//
29
Easwaran Ramane12c4872016-06-09 19:44:46 +000030#include "llvm/Transforms/Utils/LCSSA.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000031#include "llvm/ADT/STLExtras.h"
32#include "llvm/ADT/Statistic.h"
Chandler Carruth756c22c2014-02-10 19:39:35 +000033#include "llvm/Analysis/AliasAnalysis.h"
Chandler Carruthac072702016-02-19 03:12:14 +000034#include "llvm/Analysis/BasicAliasAnalysis.h"
Chandler Carruth7b560d42015-09-09 17:55:00 +000035#include "llvm/Analysis/GlobalsModRef.h"
Devang Patel4cd14132007-07-13 23:57:11 +000036#include "llvm/Analysis/LoopPass.h"
37#include "llvm/Analysis/ScalarEvolution.h"
Chandler Carruth7b560d42015-09-09 17:55:00 +000038#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000039#include "llvm/IR/Constants.h"
Chandler Carruth5ad5f152014-01-13 09:26:24 +000040#include "llvm/IR/Dominators.h"
Chandler Carruth9fb823b2013-01-02 11:36:10 +000041#include "llvm/IR/Function.h"
42#include "llvm/IR/Instructions.h"
Chandler Carruthaa0ab632014-03-04 12:09:19 +000043#include "llvm/IR/PredIteratorCache.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000044#include "llvm/Pass.h"
Easwaran Ramane12c4872016-06-09 19:44:46 +000045#include "llvm/Transforms/Scalar.h"
Chandler Carruth8765cf72014-01-25 04:07:24 +000046#include "llvm/Transforms/Utils/LoopUtils.h"
Chandler Carruthed0881b2012-12-03 16:50:05 +000047#include "llvm/Transforms/Utils/SSAUpdater.h"
Owen Anderson8eca8912006-05-26 13:58:26 +000048using namespace llvm;
49
Chandler Carruth964daaa2014-04-22 02:55:47 +000050#define DEBUG_TYPE "lcssa"
51
Chris Lattner45f966d2006-12-19 22:17:40 +000052STATISTIC(NumLCSSA, "Number of live out of a loop variables");
53
Chandler Carruth8765cf72014-01-25 04:07:24 +000054/// Return true if the specified block is in the list.
Chris Lattner71d353d2009-10-11 02:53:37 +000055static bool isExitBlock(BasicBlock *BB,
Chandler Carruth8765cf72014-01-25 04:07:24 +000056 const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
Davide Italiano88a78922016-05-27 20:25:31 +000057 return find(ExitBlocks, BB) != ExitBlocks.end();
Chris Lattner71d353d2009-10-11 02:53:37 +000058}
59
Michael Zolotukhina78937a2016-07-15 21:08:41 +000060/// For every instruction from the worklist, check to see if it has any uses
61/// that are outside the current loop. If so, insert LCSSA PHI nodes and
62/// rewrite the uses.
63bool llvm::formLCSSAForInstructions(SmallVectorImpl<Instruction *> &Worklist,
64 DominatorTree &DT, LoopInfo &LI) {
Chandler Carruth8765cf72014-01-25 04:07:24 +000065 SmallVector<Use *, 16> UsesToRewrite;
Michael Zolotukhina78937a2016-07-15 21:08:41 +000066 SmallVector<BasicBlock *, 8> ExitBlocks;
67 PredIteratorCache PredCache;
68 bool Changed = false;
Chandler Carruth8765cf72014-01-25 04:07:24 +000069
Michael Zolotukhina78937a2016-07-15 21:08:41 +000070 while (!Worklist.empty()) {
71 UsesToRewrite.clear();
72 ExitBlocks.clear();
Andrew Kaylor123048d2015-12-18 18:12:35 +000073
Michael Zolotukhina78937a2016-07-15 21:08:41 +000074 Instruction *I = Worklist.pop_back_val();
75 BasicBlock *InstBB = I->getParent();
76 Loop *L = LI.getLoopFor(InstBB);
77 L->getExitBlocks(ExitBlocks);
Chandler Carruth8765cf72014-01-25 04:07:24 +000078
Michael Zolotukhina78937a2016-07-15 21:08:41 +000079 if (ExitBlocks.empty())
Chandler Carruth8765cf72014-01-25 04:07:24 +000080 continue;
81
Michael Zolotukhina78937a2016-07-15 21:08:41 +000082 // Tokens cannot be used in PHI nodes, so we skip over them.
83 // We can run into tokens which are live out of a loop with catchswitch
84 // instructions in Windows EH if the catchswitch has one catchpad which
85 // is inside the loop and another which is not.
86 if (I->getType()->isTokenTy())
Chandler Carruth8765cf72014-01-25 04:07:24 +000087 continue;
88
Michael Zolotukhina78937a2016-07-15 21:08:41 +000089 for (Use &U : I->uses()) {
90 Instruction *User = cast<Instruction>(U.getUser());
91 BasicBlock *UserBB = User->getParent();
92 if (PHINode *PN = dyn_cast<PHINode>(User))
93 UserBB = PN->getIncomingBlock(U);
Chris Lattner984d6e12006-10-31 18:56:48 +000094
Michael Zolotukhina78937a2016-07-15 21:08:41 +000095 if (InstBB != UserBB && !L->contains(UserBB))
96 UsesToRewrite.push_back(&U);
Dan Gohmanc146c7802009-11-09 18:28:24 +000097 }
Cameron Zwarich0b8cdfb2011-03-15 07:41:25 +000098
Michael Zolotukhina78937a2016-07-15 21:08:41 +000099 // If there are no uses outside the loop, exit with no change.
100 if (UsesToRewrite.empty())
Chris Lattner5a2bc782006-08-02 00:06:09 +0000101 continue;
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000102
103 ++NumLCSSA; // We are applying the transformation
104
105 // Invoke instructions are special in that their result value is not
106 // available along their unwind edge. The code below tests to see whether
107 // DomBB dominates the value, so adjust DomBB to the normal destination
108 // block, which is effectively where the value is first usable.
109 BasicBlock *DomBB = InstBB;
110 if (InvokeInst *Inv = dyn_cast<InvokeInst>(I))
111 DomBB = Inv->getNormalDest();
112
113 DomTreeNode *DomNode = DT.getNode(DomBB);
114
115 SmallVector<PHINode *, 16> AddedPHIs;
116 SmallVector<PHINode *, 8> PostProcessPHIs;
117
Michael Zolotukhin7a3040d2016-07-18 19:05:08 +0000118 SmallVector<PHINode *, 4> InsertedPHIs;
119 SSAUpdater SSAUpdate(&InsertedPHIs);
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000120 SSAUpdate.Initialize(I->getType(), I->getName());
121
122 // Insert the LCSSA phi's into all of the exit blocks dominated by the
123 // value, and add them to the Phi's map.
124 for (BasicBlock *ExitBB : ExitBlocks) {
125 if (!DT.dominates(DomNode, DT.getNode(ExitBB)))
126 continue;
127
128 // If we already inserted something for this BB, don't reprocess it.
129 if (SSAUpdate.HasValueForBlock(ExitBB))
130 continue;
131
132 PHINode *PN = PHINode::Create(I->getType(), PredCache.size(ExitBB),
133 I->getName() + ".lcssa", &ExitBB->front());
134
135 // Add inputs from inside the loop for this PHI.
136 for (BasicBlock *Pred : PredCache.get(ExitBB)) {
137 PN->addIncoming(I, Pred);
138
139 // If the exit block has a predecessor not within the loop, arrange for
140 // the incoming value use corresponding to that predecessor to be
141 // rewritten in terms of a different LCSSA PHI.
142 if (!L->contains(Pred))
143 UsesToRewrite.push_back(
144 &PN->getOperandUse(PN->getOperandNumForIncomingValue(
145 PN->getNumIncomingValues() - 1)));
146 }
147
148 AddedPHIs.push_back(PN);
149
150 // Remember that this phi makes the value alive in this block.
151 SSAUpdate.AddAvailableValue(ExitBB, PN);
152
153 // LoopSimplify might fail to simplify some loops (e.g. when indirect
154 // branches are involved). In such situations, it might happen that an
155 // exit for Loop L1 is the header of a disjoint Loop L2. Thus, when we
156 // create PHIs in such an exit block, we are also inserting PHIs into L2's
157 // header. This could break LCSSA form for L2 because these inserted PHIs
158 // can also have uses outside of L2. Remember all PHIs in such situation
159 // as to revisit than later on. FIXME: Remove this if indirectbr support
160 // into LoopSimplify gets improved.
161 if (auto *OtherLoop = LI.getLoopFor(ExitBB))
162 if (!L->contains(OtherLoop))
163 PostProcessPHIs.push_back(PN);
Owen Andersoncd76fa02006-06-01 06:05:47 +0000164 }
Chandler Carruth8765cf72014-01-25 04:07:24 +0000165
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000166 // Rewrite all uses outside the loop in terms of the new PHIs we just
167 // inserted.
168 for (Use *UseToRewrite : UsesToRewrite) {
169 // If this use is in an exit block, rewrite to use the newly inserted PHI.
170 // This is required for correctness because SSAUpdate doesn't handle uses
171 // in the same block. It assumes the PHI we inserted is at the end of the
172 // block.
173 Instruction *User = cast<Instruction>(UseToRewrite->getUser());
174 BasicBlock *UserBB = User->getParent();
175 if (PHINode *PN = dyn_cast<PHINode>(User))
176 UserBB = PN->getIncomingBlock(*UseToRewrite);
177
178 if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) {
179 // Tell the VHs that the uses changed. This updates SCEV's caches.
180 if (UseToRewrite->get()->hasValueHandle())
181 ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front());
182 UseToRewrite->set(&UserBB->front());
183 continue;
184 }
185
186 // Otherwise, do full PHI insertion.
187 SSAUpdate.RewriteUse(*UseToRewrite);
Michael Zolotukhin7a3040d2016-07-18 19:05:08 +0000188
189 // SSAUpdater might have inserted phi-nodes inside other loops. We'll need
190 // to post-process them to keep LCSSA form.
191 for (PHINode *InsertedPN : InsertedPHIs) {
192 if (auto *OtherLoop = LI.getLoopFor(InsertedPN->getParent()))
193 if (!L->contains(OtherLoop))
194 PostProcessPHIs.push_back(InsertedPN);
195 }
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000196 }
197
198 // Post process PHI instructions that were inserted into another disjoint
199 // loop and update their exits properly.
200 for (auto *PostProcessPN : PostProcessPHIs) {
201 if (PostProcessPN->use_empty())
202 continue;
203
204 // Reprocess each PHI instruction.
205 Worklist.push_back(PostProcessPN);
206 }
207
208 // Remove PHI nodes that did not have any uses rewritten.
209 for (PHINode *PN : AddedPHIs)
210 if (PN->use_empty())
211 PN->eraseFromParent();
212
213 Changed = true;
Chris Lattner5a2bc782006-08-02 00:06:09 +0000214 }
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000215 return Changed;
Owen Andersondad8c572006-05-31 20:55:06 +0000216}
Chris Lattner5a2bc782006-08-02 00:06:09 +0000217
Chandler Carruth8765cf72014-01-25 04:07:24 +0000218/// Return true if the specified block dominates at least
219/// one of the blocks in the specified list.
220static bool
221blockDominatesAnExit(BasicBlock *BB,
222 DominatorTree &DT,
223 const SmallVectorImpl<BasicBlock *> &ExitBlocks) {
224 DomTreeNode *DomNode = DT.getNode(BB);
Davide Italianobfe38012016-05-17 19:01:02 +0000225 return llvm::any_of(ExitBlocks, [&](BasicBlock * EB) {
Davide Italianob75b16e22016-05-17 14:24:41 +0000226 return DT.dominates(DomNode, DT.getNode(EB));
227 });
Chandler Carruth8765cf72014-01-25 04:07:24 +0000228}
229
Bruno Cardoso Lopesbad65c32014-12-22 22:35:46 +0000230bool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI,
231 ScalarEvolution *SE) {
Chandler Carruth8765cf72014-01-25 04:07:24 +0000232 bool Changed = false;
233
234 // Get the set of exiting blocks.
235 SmallVector<BasicBlock *, 8> ExitBlocks;
236 L.getExitBlocks(ExitBlocks);
237
238 if (ExitBlocks.empty())
239 return false;
240
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000241 SmallVector<Instruction *, 8> Worklist;
Chandler Carruth8765cf72014-01-25 04:07:24 +0000242
243 // Look at all the instructions in the loop, checking to see if they have uses
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000244 // outside the loop. If so, put them into the worklist to rewrite those uses.
Sanjoy Das331521c2015-10-25 19:08:32 +0000245 for (BasicBlock *BB : L.blocks()) {
Chandler Carruth8765cf72014-01-25 04:07:24 +0000246 // For large loops, avoid use-scanning by using dominance information: In
247 // particular, if a block does not dominate any of the loop exits, then none
248 // of the values defined in the block could be used outside the loop.
249 if (!blockDominatesAnExit(BB, DT, ExitBlocks))
250 continue;
251
Sanjoy Das331521c2015-10-25 19:08:32 +0000252 for (Instruction &I : *BB) {
Chandler Carruth8765cf72014-01-25 04:07:24 +0000253 // Reject two common cases fast: instructions with no uses (like stores)
254 // and instructions with one use that is in the same block as this.
Sanjoy Das331521c2015-10-25 19:08:32 +0000255 if (I.use_empty() ||
256 (I.hasOneUse() && I.user_back()->getParent() == BB &&
257 !isa<PHINode>(I.user_back())))
Chandler Carruth8765cf72014-01-25 04:07:24 +0000258 continue;
259
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000260 Worklist.push_back(&I);
Chandler Carruth8765cf72014-01-25 04:07:24 +0000261 }
262 }
Michael Zolotukhina78937a2016-07-15 21:08:41 +0000263 Changed = formLCSSAForInstructions(Worklist, DT, *LI);
Chandler Carruth8765cf72014-01-25 04:07:24 +0000264
265 // If we modified the code, remove any caches about the loop from SCEV to
266 // avoid dangling entries.
267 // FIXME: This is a big hammer, can we clear the cache more selectively?
268 if (SE && Changed)
269 SE->forgetLoop(&L);
270
271 assert(L.isLCSSAForm(DT));
272
273 return Changed;
274}
275
Chandler Carruthd84f7762014-01-28 01:25:38 +0000276/// Process a loop nest depth first.
Bruno Cardoso Lopesbad65c32014-12-22 22:35:46 +0000277bool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI,
Chandler Carruthd84f7762014-01-28 01:25:38 +0000278 ScalarEvolution *SE) {
279 bool Changed = false;
280
281 // Recurse depth-first through inner loops.
Sanjoy Das15c4c462015-10-25 19:27:17 +0000282 for (Loop *SubLoop : L.getSubLoops())
283 Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE);
Chandler Carruthd84f7762014-01-28 01:25:38 +0000284
Bruno Cardoso Lopesbad65c32014-12-22 22:35:46 +0000285 Changed |= formLCSSA(L, DT, LI, SE);
Chandler Carruthd84f7762014-01-28 01:25:38 +0000286 return Changed;
287}
288
Easwaran Ramane12c4872016-06-09 19:44:46 +0000289/// Process all loops in the function, inner-most out.
290static bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT,
291 ScalarEvolution *SE) {
292 bool Changed = false;
293 for (auto &L : *LI)
294 Changed |= formLCSSARecursively(*L, DT, LI, SE);
295 return Changed;
296}
297
Chandler Carruth8765cf72014-01-25 04:07:24 +0000298namespace {
Easwaran Ramane12c4872016-06-09 19:44:46 +0000299struct LCSSAWrapperPass : public FunctionPass {
Chandler Carruth8765cf72014-01-25 04:07:24 +0000300 static char ID; // Pass identification, replacement for typeid
Easwaran Ramane12c4872016-06-09 19:44:46 +0000301 LCSSAWrapperPass() : FunctionPass(ID) {
302 initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry());
Chandler Carruth8765cf72014-01-25 04:07:24 +0000303 }
304
305 // Cached analysis information for the current function.
306 DominatorTree *DT;
307 LoopInfo *LI;
308 ScalarEvolution *SE;
309
Craig Topper3e4c6972014-03-05 09:10:37 +0000310 bool runOnFunction(Function &F) override;
Chandler Carruth8765cf72014-01-25 04:07:24 +0000311
312 /// This transformation requires natural loop information & requires that
313 /// loop preheaders be inserted into the CFG. It maintains both of these,
314 /// as well as the CFG. It also requires dominator information.
Craig Topper3e4c6972014-03-05 09:10:37 +0000315 void getAnalysisUsage(AnalysisUsage &AU) const override {
Chandler Carruth8765cf72014-01-25 04:07:24 +0000316 AU.setPreservesCFG();
317
318 AU.addRequired<DominatorTreeWrapperPass>();
Chandler Carruth4f8f3072015-01-17 14:16:18 +0000319 AU.addRequired<LoopInfoWrapperPass>();
Chandler Carruth8765cf72014-01-25 04:07:24 +0000320 AU.addPreservedID(LoopSimplifyID);
Chandler Carruth7b560d42015-09-09 17:55:00 +0000321 AU.addPreserved<AAResultsWrapperPass>();
Chandler Carruthac072702016-02-19 03:12:14 +0000322 AU.addPreserved<BasicAAWrapperPass>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000323 AU.addPreserved<GlobalsAAWrapperPass>();
Chandler Carruth2f1fd162015-08-17 02:08:17 +0000324 AU.addPreserved<ScalarEvolutionWrapperPass>();
Chandler Carruth7b560d42015-09-09 17:55:00 +0000325 AU.addPreserved<SCEVAAWrapperPass>();
Chandler Carruth8765cf72014-01-25 04:07:24 +0000326 }
Chandler Carruth8765cf72014-01-25 04:07:24 +0000327};
Alexander Kornienkof00654e2015-06-23 09:49:53 +0000328}
Chandler Carruth8765cf72014-01-25 04:07:24 +0000329
Easwaran Ramane12c4872016-06-09 19:44:46 +0000330char LCSSAWrapperPass::ID = 0;
331INITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
332 false, false)
Chandler Carruth8765cf72014-01-25 04:07:24 +0000333INITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass)
Chandler Carruth4f8f3072015-01-17 14:16:18 +0000334INITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass)
Easwaran Ramane12c4872016-06-09 19:44:46 +0000335INITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass",
336 false, false)
Chandler Carruth8765cf72014-01-25 04:07:24 +0000337
Easwaran Ramane12c4872016-06-09 19:44:46 +0000338Pass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); }
339char &llvm::LCSSAID = LCSSAWrapperPass::ID;
Chandler Carruth8765cf72014-01-25 04:07:24 +0000340
Easwaran Ramane12c4872016-06-09 19:44:46 +0000341/// Transform \p F into loop-closed SSA form.
342bool LCSSAWrapperPass::runOnFunction(Function &F) {
Chandler Carruth4f8f3072015-01-17 14:16:18 +0000343 LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo();
Chandler Carruth8765cf72014-01-25 04:07:24 +0000344 DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree();
Chandler Carruth2f1fd162015-08-17 02:08:17 +0000345 auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>();
346 SE = SEWP ? &SEWP->getSE() : nullptr;
Chandler Carruth8765cf72014-01-25 04:07:24 +0000347
Easwaran Ramane12c4872016-06-09 19:44:46 +0000348 return formLCSSAOnAllLoops(LI, *DT, SE);
Chandler Carruth8765cf72014-01-25 04:07:24 +0000349}
350
Easwaran Ramane12c4872016-06-09 19:44:46 +0000351PreservedAnalyses LCSSAPass::run(Function &F, AnalysisManager<Function> &AM) {
352 auto &LI = AM.getResult<LoopAnalysis>(F);
353 auto &DT = AM.getResult<DominatorTreeAnalysis>(F);
354 auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F);
355 if (!formLCSSAOnAllLoops(&LI, DT, SE))
356 return PreservedAnalyses::all();
357
Michael Kuperstein835facd2016-06-28 00:54:12 +0000358 // FIXME: This should also 'preserve the CFG'.
Easwaran Ramane12c4872016-06-09 19:44:46 +0000359 PreservedAnalyses PA;
360 PA.preserve<BasicAA>();
361 PA.preserve<GlobalsAA>();
362 PA.preserve<SCEVAA>();
363 PA.preserve<ScalarEvolutionAnalysis>();
364 return PA;
365}