1 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===//
3 // The LLVM Compiler Infrastructure
5 // This file was developed by Owen Anderson and is distributed under the
6 // University of Illinois Open Source License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
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:
14 // for (...) for (...)
19 // X3 = phi(X1, X2) X3 = phi(X1, X2)
20 // ... = X3 + 4 X4 = phi(X3)
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.
28 //===----------------------------------------------------------------------===//
30 #include "llvm/Transforms/Scalar.h"
31 #include "llvm/Pass.h"
32 #include "llvm/Function.h"
33 #include "llvm/Instructions.h"
34 #include "llvm/Analysis/Dominators.h"
35 #include "llvm/Analysis/LoopInfo.h"
36 #include "llvm/Support/CFG.h"
44 class LCSSA : public FunctionPass {
46 LoopInfo *LI; // Loop information
47 DominatorTree *DT; // Dominator Tree for the current Loop...
48 DominanceFrontier *DF; // Current Dominance Frontier
50 virtual bool runOnFunction(Function &F);
51 bool LCSSA::visitSubloop(Loop* L);
53 /// This transformation requires natural loop information & requires that
54 /// loop preheaders be inserted into the CFG...
56 virtual void getAnalysisUsage(AnalysisUsage &AU) const {
58 AU.addRequiredID(LoopSimplifyID);
59 AU.addPreservedID(LoopSimplifyID);
60 AU.addRequired<LoopInfo>();
61 AU.addPreserved<LoopInfo>();
62 AU.addRequired<DominatorTree>(); // Not sure if this one will actually
64 AU.addRequired<DominanceFrontier>();
67 std::set<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L,
68 std::vector<BasicBlock*> LoopBlocks);
71 RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass");
74 FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); }
76 bool LCSSA::runOnFunction(Function &F) {
78 LI = &getAnalysis<LoopInfo>();
79 DF = &getAnalysis<DominanceFrontier>();
80 DT = &getAnalysis<DominatorTree>();
82 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) {
83 changed |= visitSubloop(*I);
89 bool LCSSA::visitSubloop(Loop* L) {
90 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I)
93 // Speed up queries by creating a sorted list of blocks
94 std::vector<BasicBlock*> LoopBlocks(L->block_begin(), L->block_end());
95 std::sort(LoopBlocks.begin(), LoopBlocks.end());
97 std::set<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L,
100 std::vector<BasicBlock*> exitBlocks;
101 L->getExitBlocks(exitBlocks);
103 for (std::set<Instruction*>::iterator I = AffectedValues.begin(),
104 E = AffectedValues.end(); I != E; ++I) {
105 for (std::vector<BasicBlock*>::iterator BBI = exitBlocks.begin(),
106 BBE = exitBlocks.end(); BBI != BBE; ++BBI) {
107 PHINode *phi = new PHINode((*I)->getType(), "lcssa");
108 (*BBI)->getInstList().insert((*BBI)->front(), phi);
110 for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE;
112 phi->addIncoming(*I, *PI);
115 for (Value::use_iterator UI = (*I)->use_begin(), UE = (*I)->use_end();
117 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
118 if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB))
119 ; // FIXME: This should update the SSA form.
123 return true; // FIXME: Should be more intelligent in our return value.
126 /// getLoopValuesUsedOutsideLoop - Return any values defined in the loop that
127 /// are used by instructions outside of it.
128 std::set<Instruction*> LCSSA::getLoopValuesUsedOutsideLoop(Loop *L,
129 std::vector<BasicBlock*> LoopBlocks) {
131 std::set<Instruction*> AffectedValues;
132 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end();
134 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I)
135 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E;
137 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent();
138 if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB))
139 AffectedValues.insert(I);
142 return AffectedValues;