LCSSA.cpp revision 11f510b577878e61e62a3a9c5c8d86483961d20c
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/Pass.h" 31#include "llvm/Function.h" 32#include "llvm/Instructions.h" 33#include "llvm/Analysis/LoopInfo.h" 34#include "llvm/Support/CFG.h" 35#include "llvm/Transforms/Scalar.h" 36#include "llvm/Transforms/Utils/BasicBlockUtils.h" 37#include <iostream> 38#include <set> 39#include <vector> 40 41using namespace llvm; 42 43namespace { 44 class LCSSA : public FunctionPass { 45 public: 46 LoopInfo *LI; // Loop information 47 48 // LoopProcessWorklist - List of loops we need to process. 49 std::vector<Loop*> LoopProcessWorklist; 50 51 virtual bool runOnFunction(Function &F); 52 53 bool visitLoop(Loop *L, Value *V); 54 55 /// This transformation requires natural loop information & requires that 56 /// loop preheaders be inserted into the CFG... 57 /// 58 virtual void getAnalysisUsage(AnalysisUsage &AU) const { 59 AU.addRequiredID(LoopSimplifyID); 60 AU.addPreservedID(LoopSimplifyID); 61 AU.addRequired<LoopInfo>(); 62 AU.addPreserved<LoopInfo>(); 63 } 64 private: 65 void addSubloopsToWorklist(Loop* L); 66 std::set<Value*> loopValuesUsedOutsideLoop(Loop *L); 67 }; 68 69 RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 70} 71 72FunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 73 74bool LCSSA::runOnFunction(Function &F) { 75 bool changed = false; 76 LI = &getAnalysis<LoopInfo>(); 77 78 for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 79 addSubloopsToWorklist(*I); 80 LoopProcessWorklist.push_back(*I); 81 } 82 83 for (std::vector<Loop*>::iterator I = LoopProcessWorklist.begin(), 84 E = LoopProcessWorklist.end(); I != E; ++I) { 85 std::set<Value*> AffectedValues = loopValuesUsedOutsideLoop(*I); 86 if (!AffectedValues.empty()) { 87 for (std::set<Value*>::iterator VI = AffectedValues.begin(), 88 VE = AffectedValues.end(); VI != VE; ++VI) 89 changed |= visitLoop(*I, *VI); 90 } 91 } 92 93 return changed; 94} 95 96bool LCSSA::visitLoop(Loop *L, Value* V) { 97 // We will be doing lots of "loop contains block" queries. Loop::contains is 98 // linear time, use a set to speed this up. 99 std::set<BasicBlock*> LoopBlocks; 100 101 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 102 BB != E; ++BB) 103 LoopBlocks.insert(*BB); 104 105 std::vector<BasicBlock*> exitBlocks; 106 L->getExitBlocks(exitBlocks); 107 108 for (std::vector<BasicBlock*>::iterator BBI = exitBlocks.begin(), 109 BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 110 PHINode *phi = new PHINode(V->getType(), "lcssa"); 111 (*BBI)->getInstList().insert((*BBI)->front(), phi); 112 113 for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE; 114 ++PI) 115 phi->addIncoming(V, *PI); 116 } 117 118 for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; 119 ++UI) { 120 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 121 if (!LoopBlocks.count(UserBB)) 122 ; // FIXME: This should update the SSA form through the rest of the graph. 123 } 124 125 return false; 126} 127 128void LCSSA::addSubloopsToWorklist(Loop* L) { 129 for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 130 addSubloopsToWorklist(*I); 131 LoopProcessWorklist.push_back(*I); 132 } 133} 134 135/// loopValuesUsedOutsideLoop - Return true if there are any values defined in 136/// the loop that are used by instructions outside of it. 137std::set<Value*> LCSSA::loopValuesUsedOutsideLoop(Loop *L) { 138 std::set<Value*> AffectedValues; 139 140 // We will be doing lots of "loop contains block" queries. Loop::contains is 141 // linear time, use a set to speed this up. 142 std::set<BasicBlock*> LoopBlocks; 143 144 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 145 BB != E; ++BB) 146 LoopBlocks.insert(*BB); 147 148 for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 149 BB != E; ++BB) { 150 for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 151 for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 152 ++UI) { 153 BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 154 if (!LoopBlocks.count(UserBB)) 155 AffectedValues.insert(I); 156 } 157 } 158 return AffectedValues; 159}