1 //===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 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. 7 // 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 (...) 15 // if (c) if(c) 16 // X1 = ... X1 = ... 17 // else else 18 // X2 = ... X2 = ... 19 // X3 = phi(X1, X2) X3 = phi(X1, X2) 20 // ... = X3 + 4 X4 = phi(X3) 21 // ... = X4 + 4 22 // 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 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" 37 #include <algorithm> 38 #include <set> 39 #include <vector> 40 41 using namespace llvm; 42 43 namespace { 44 class LCSSA : public FunctionPass { 45 public: 46 LoopInfo *LI; // Loop information 47 DominatorTree *DT; // Dominator Tree for the current Loop... 48 DominanceFrontier *DF; // Current Dominance Frontier 49 50 virtual bool runOnFunction(Function &F); 51 bool visitSubloop(Loop* L); 52 53 /// This transformation requires natural loop information & requires that 54 /// loop preheaders be inserted into the CFG... 55 /// 56 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 57 AU.setPreservesCFG(); 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 63 // be needed. 64 AU.addRequired<DominanceFrontier>(); 65 } 66 private: 67 std::set<Instruction*> getLoopValuesUsedOutsideLoop(Loop *L, 68 std::vector<BasicBlock*> LoopBlocks); 69 }; 70 71 RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 72 } 73 74 FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 75 76 bool LCSSA::runOnFunction(Function &F) { 77 bool changed = false; 78 LI = &getAnalysis<LoopInfo>(); 79 DF = &getAnalysis<DominanceFrontier>(); 80 DT = &getAnalysis<DominatorTree>(); 81 82 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 83 changed |= visitSubloop(*I); 84 } 85 86 return changed; 87 } 88 89 bool LCSSA::visitSubloop(Loop* L) { 90 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) 91 visitSubloop(*I); 92 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()); 96 97 std::set<Instruction*> AffectedValues = getLoopValuesUsedOutsideLoop(L, 98 LoopBlocks); 99 100 std::vector<BasicBlock*> exitBlocks; 101 L->getExitBlocks(exitBlocks); 102 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); 109 110 for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE; 111 ++PI) 112 phi->addIncoming(*I, *PI); 113 } 114 115 for (Value::use_iterator UI = (*I)->use_begin(), UE = (*I)->use_end(); 116 UI != UE; ++UI) { 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. 120 } 121 } 122 123 return true; // FIXME: Should be more intelligent in our return value. 124 } 125 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) { 130 131 std::set<Instruction*> AffectedValues; 132 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 133 BB != E; ++BB) { 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; 136 ++UI) { 137 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 138 if (!std::binary_search(LoopBlocks.begin(), LoopBlocks.end(), UserBB)) 139 AffectedValues.insert(I); 140 } 141 } 142 return AffectedValues; 143 } 144