LCSSA.cpp revision 11f510b577878e61e62a3a9c5c8d86483961d20c
111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ------===// 211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// The LLVM Compiler Infrastructure 411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// This file was developed by Owen Anderson and is distributed under the 611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// University of Illinois Open Source License. See LICENSE.TXT for details. 711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson//===----------------------------------------------------------------------===// 911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 1011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// This pass transforms loops by placing phi nodes at the end of the loops for 1111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// all values that are live across the loop boundary. For example, it turns 1211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// the left into the right code: 1311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 1411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// for (...) for (...) 1511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// if (c) if(c) 1611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// X1 = ... X1 = ... 1711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// else else 1811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// X2 = ... X2 = ... 1911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// X3 = phi(X1, X2) X3 = phi(X1, X2) 2011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// ... = X3 + 4 X4 = phi(X3) 2111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// ... = X4 + 4 2211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 2311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// This is still valid LLVM; the extra phi nodes are purely redundant, and will 2411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// be trivially eliminated by InstCombine. The major benefit of this 2511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// transformation is that it makes many other loop optimizations, such as 2611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// LoopUnswitching, simpler. 2711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 2811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson//===----------------------------------------------------------------------===// 2911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 3011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Pass.h" 3111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Function.h" 3211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Instructions.h" 3311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Analysis/LoopInfo.h" 3411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Support/CFG.h" 3511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Transforms/Scalar.h" 3611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include "llvm/Transforms/Utils/BasicBlockUtils.h" 3711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include <iostream> 3811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include <set> 3911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson#include <vector> 4011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 4111f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 4311f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonnamespace { 4411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson class LCSSA : public FunctionPass { 4511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson public: 4611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LoopInfo *LI; // Loop information 4711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 4811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson // LoopProcessWorklist - List of loops we need to process. 4911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::vector<Loop*> LoopProcessWorklist; 5011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 5111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual bool runOnFunction(Function &F); 5211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 5311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson bool visitLoop(Loop *L, Value *V); 5411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 5511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// This transformation requires natural loop information & requires that 5611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// loop preheaders be inserted into the CFG... 5711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson /// 5811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson virtual void getAnalysisUsage(AnalysisUsage &AU) const { 5911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequiredID(LoopSimplifyID); 6011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addPreservedID(LoopSimplifyID); 6111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addRequired<LoopInfo>(); 6211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AU.addPreserved<LoopInfo>(); 6311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 6411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson private: 6511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson void addSubloopsToWorklist(Loop* L); 6611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::set<Value*> loopValuesUsedOutsideLoop(Loop *L); 6711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson }; 6811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 6911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson RegisterOpt<LCSSA> X("lcssa", "Loop-Closed SSA Form Pass"); 7011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 7111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 7211f510b577878e61e62a3a9c5c8d86483961d20cOwen AndersonFunctionPass *llvm::createLCSSAPass() { return new LCSSA(); } 7311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 7411f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonbool LCSSA::runOnFunction(Function &F) { 7511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson bool changed = false; 7611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LI = &getAnalysis<LoopInfo>(); 7711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 7811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) { 7911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson addSubloopsToWorklist(*I); 8011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LoopProcessWorklist.push_back(*I); 8111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 8211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 8311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (std::vector<Loop*>::iterator I = LoopProcessWorklist.begin(), 8411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson E = LoopProcessWorklist.end(); I != E; ++I) { 8511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::set<Value*> AffectedValues = loopValuesUsedOutsideLoop(*I); 8611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson if (!AffectedValues.empty()) { 8711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (std::set<Value*>::iterator VI = AffectedValues.begin(), 8811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson VE = AffectedValues.end(); VI != VE; ++VI) 8911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson changed |= visitLoop(*I, *VI); 9011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 9111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 9211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 9311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return changed; 9411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 9511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 9611f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonbool LCSSA::visitLoop(Loop *L, Value* V) { 9711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson // We will be doing lots of "loop contains block" queries. Loop::contains is 9811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson // linear time, use a set to speed this up. 9911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::set<BasicBlock*> LoopBlocks; 10011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 10111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 10211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BB != E; ++BB) 10311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LoopBlocks.insert(*BB); 10411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 10511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::vector<BasicBlock*> exitBlocks; 10611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson L->getExitBlocks(exitBlocks); 10711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 10811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (std::vector<BasicBlock*>::iterator BBI = exitBlocks.begin(), 10911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BBE = exitBlocks.end(); BBI != BBE; ++BBI) { 11011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson PHINode *phi = new PHINode(V->getType(), "lcssa"); 11111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson (*BBI)->getInstList().insert((*BBI)->front(), phi); 11211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 11311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (pred_iterator PI = pred_begin(*BBI), PE = pred_end(*BBI); PI != PE; 11411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ++PI) 11511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson phi->addIncoming(V, *PI); 11611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 11711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 11811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Value::use_iterator UI = V->use_begin(), UE = V->use_end(); UI != UE; 11911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ++UI) { 12011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 12111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson if (!LoopBlocks.count(UserBB)) 12211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ; // FIXME: This should update the SSA form through the rest of the graph. 12311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 12411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 12511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return false; 12611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 12711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 12811f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonvoid LCSSA::addSubloopsToWorklist(Loop* L) { 12911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::iterator I = L->begin(), E = L->end(); I != E; ++I) { 13011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson addSubloopsToWorklist(*I); 13111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LoopProcessWorklist.push_back(*I); 13211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 13311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson} 13411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 13511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson/// loopValuesUsedOutsideLoop - Return true if there are any values defined in 13611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson/// the loop that are used by instructions outside of it. 13711f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonstd::set<Value*> LCSSA::loopValuesUsedOutsideLoop(Loop *L) { 13811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::set<Value*> AffectedValues; 13911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 14011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson // We will be doing lots of "loop contains block" queries. Loop::contains is 14111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson // linear time, use a set to speed this up. 14211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson std::set<BasicBlock*> LoopBlocks; 14311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 14411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 14511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BB != E; ++BB) 14611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson LoopBlocks.insert(*BB); 14711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 14811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Loop::block_iterator BB = L->block_begin(), E = L->block_end(); 14911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BB != E; ++BB) { 15011f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (BasicBlock::iterator I = (*BB)->begin(), E = (*BB)->end(); I != E; ++I) 15111f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson for (Value::use_iterator UI = I->use_begin(), E = I->use_end(); UI != E; 15211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson ++UI) { 15311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson BasicBlock *UserBB = cast<Instruction>(*UI)->getParent(); 15411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson if (!LoopBlocks.count(UserBB)) 15511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson AffectedValues.insert(I); 15611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 15711f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson } 15811f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson return AffectedValues; 15911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson}