12480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson//===-- LCSSA.cpp - Convert loops into loop-closed SSA form ---------------===// 211f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 311f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// The LLVM Compiler Infrastructure 411f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson// 54ee451de366474b9c228b4e5fa573795a715216dChris Lattner// This file is distributed under the University of Illinois Open Source 64ee451de366474b9c228b4e5fa573795a715216dChris Lattner// 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 (...) 1523d9d27c265753da55a8ee7879820acb4d1e3a6dDan Gohman// 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) 20c702a9ed1c99fc520fa8e003f88949a74e0c269fDan Gohman// ... = X3 + 4 X4 = phi(X3) 21c702a9ed1c99fc520fa8e003f88949a74e0c269fDan Gohman// ... = 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 302480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Transforms/Scalar.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/AliasAnalysis.h" 34b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/LoopPass.h" 35b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/ScalarEvolution.h" 360b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 3736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 380b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 390b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PredIteratorCache.h" 41d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Transforms/Utils/LoopUtils.h" 43d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/SSAUpdater.h" 4411f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4511f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 46dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "lcssa" 47dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 48d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumLCSSA, "Number of live out of a loop variables"); 49d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Return true if the specified block is in the list. 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool isExitBlock(BasicBlock *BB, 5236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 538c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ExitBlocks[i] == BB) 558c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 578c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 588c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Given an instruction in the loop, check to see if it has any uses that are 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// outside the current loop. If so, insert LCSSA PHI nodes and rewrite the 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// uses. 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks, 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PredIteratorCache &PredCache) { 6536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<Use *, 16> UsesToRewrite; 668c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 6736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *InstBB = Inst.getParent(); 6896bf524b531fd404b118fad7bbe410e9aceeaa5dDevang Patel 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Use &U : Inst.uses()) { 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *User = cast<Instruction>(U.getUser()); 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *UserBB = User->getParent(); 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (PHINode *PN = dyn_cast<PHINode>(User)) 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UserBB = PN->getIncomingBlock(U); 74d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (InstBB != UserBB && !L.contains(UserBB)) 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UsesToRewrite.push_back(&U); 778c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 78a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif 798c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If there are no uses outside the loop, exit with no change. 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UsesToRewrite.empty()) 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 8236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 838c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner ++NumLCSSA; // We are applying the transformation 846b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 856b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // Invoke instructions are special in that their result value is not available 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // along their unwind edge. The code below tests to see whether DomBB 8736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // dominates 886b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // the value, so adjust DomBB to the normal destination block, which is 896b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // effectively where the value is first usable. 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *DomBB = Inst.getParent(); 9136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (InvokeInst *Inv = dyn_cast<InvokeInst>(&Inst)) 926b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman DomBB = Inv->getNormalDest(); 936b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *DomNode = DT.getNode(DomBB); 95d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 9636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<PHINode *, 16> AddedPHIs; 97838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 988c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdater SSAUpdate; 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SSAUpdate.Initialize(Inst.getType(), Inst.getName()); 10036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1018c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Insert the LCSSA phi's into all of the exit blocks dominated by the 102f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // value, and add them to the Phi's map. 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (SmallVectorImpl<BasicBlock *>::const_iterator BBI = ExitBlocks.begin(), 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BBE = ExitBlocks.end(); 10536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BBI != BBE; ++BBI) { 1068c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *ExitBB = *BBI; 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!DT.dominates(DomNode, DT.getNode(ExitBB))) 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 10936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1108c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If we already inserted something for this BB, don't reprocess it. 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SSAUpdate.HasValueForBlock(ExitBB)) 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *PN = PHINode::Create(Inst.getType(), PredCache.GetNumPreds(ExitBB), 11536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst.getName() + ".lcssa", ExitBB->begin()); 116d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 1178c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Add inputs from inside the loop for this PHI. 118f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) { 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PN->addIncoming(&Inst, *PI); 120f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman 121f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // If the exit block has a predecessor not within the loop, arrange for 122eaa181c83ae7d6295e95753a1d6ae9a684d35fa7Dan Gohman // the incoming value use corresponding to that predecessor to be 123f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // rewritten in terms of a different LCSSA PHI. 12436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!L.contains(*PI)) 125f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman UsesToRewrite.push_back( 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines &PN->getOperandUse(PN->getOperandNumForIncomingValue( 12736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PN->getNumIncomingValues() - 1))); 128f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman } 129838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 130838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich AddedPHIs.push_back(PN); 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1328c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Remember that this phi makes the value alive in this block. 1338c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.AddAvailableValue(ExitBB, PN); 13430019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 1354ad3d981b91ac1293b8f2be29e6452d5206107b8Benjamin Kramer 1368c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Rewrite all uses outside the loop in terms of the new PHIs we just 1378c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // inserted. 1388c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) { 1398c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If this use is in an exit block, rewrite to use the newly inserted PHI. 1408c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // This is required for correctness because SSAUpdate doesn't handle uses in 1418c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // the same block. It assumes the PHI we inserted is at the end of the 1428c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // block. 1438c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner Instruction *User = cast<Instruction>(UsesToRewrite[i]->getUser()); 1448c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *UserBB = User->getParent(); 1458c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) 1468c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UserBB = PN->getIncomingBlock(*UsesToRewrite[i]); 1478c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 14836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { 149ccd492c9d6f3cb20b9eb24dc0f102544b482019bBenjamin Kramer // Tell the VHs that the uses changed. This updates SCEV's caches. 150ccd492c9d6f3cb20b9eb24dc0f102544b482019bBenjamin Kramer if (UsesToRewrite[i]->get()->hasValueHandle()) 151ccd492c9d6f3cb20b9eb24dc0f102544b482019bBenjamin Kramer ValueHandleBase::ValueIsRAUWd(*UsesToRewrite[i], UserBB->begin()); 1528c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UsesToRewrite[i]->set(UserBB->begin()); 153d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner continue; 1542824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 15536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Otherwise, do full PHI insertion. 1578c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.RewriteUse(*UsesToRewrite[i]); 158d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner } 159838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 160838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich // Remove PHI nodes that did not have any uses rewritten. 161838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) { 1626e51c6ad9d9c3c02c7b7692e21645beb68408281Cameron Zwarich if (AddedPHIs[i]->use_empty()) 163838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich AddedPHIs[i]->eraseFromParent(); 164838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich } 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1668c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 167408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 168d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Return true if the specified block dominates at least 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// one of the blocks in the specified list. 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesblockDominatesAnExit(BasicBlock *BB, 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT, 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *DomNode = DT.getNode(BB); 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DT.dominates(DomNode, DT.getNode(ExitBlocks[i]))) 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) { 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Get the set of exiting blocks. 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<BasicBlock *, 8> ExitBlocks; 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines L.getExitBlocks(ExitBlocks); 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ExitBlocks.empty()) 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PredIteratorCache PredCache; 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Look at all the instructions in the loop, checking to see if they have uses 19636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // outside the loop. If so, rewrite those uses. 19736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Loop::block_iterator BBI = L.block_begin(), BBE = L.block_end(); 19836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BBI != BBE; ++BBI) { 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB = *BBI; 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // For large loops, avoid use-scanning by using dominance information: In 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // particular, if a block does not dominate any of the loop exits, then none 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // of the values defined in the block could be used outside the loop. 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!blockDominatesAnExit(BB, DT, ExitBlocks)) 20536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 20836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Reject two common cases fast: instructions with no uses (like stores) 20936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // and instructions with one use that is in the same block as this. 21036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I->use_empty() || 21136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (I->hasOneUse() && I->user_back()->getParent() == BB && 21236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines !isa<PHINode>(I->user_back()))) 21336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache); 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 21736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 21836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If we modified the code, remove any caches about the loop from SCEV to 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // avoid dangling entries. 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: This is a big hammer, can we clear the cache more selectively? 22236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SE && Changed) 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SE->forgetLoop(&L); 22436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(L.isLCSSAForm(DT)); 22636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 22836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Process a loop nest depth first. 23136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, 23236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScalarEvolution *SE) { 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Recurse depth-first through inner loops. 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 23736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= formLCSSARecursively(**LI, DT, SE); 23836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= formLCSSA(L, DT, SE); 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace { 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstruct LCSSA : public FunctionPass { 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static char ID; // Pass identification, replacement for typeid 24636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LCSSA() : FunctionPass(ID) { 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines initializeLCSSAPass(*PassRegistry::getPassRegistry()); 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Cached analysis information for the current function. 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree *DT; 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopInfo *LI; 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScalarEvolution *SE; 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// This transformation requires natural loop information & requires that 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// loop preheaders be inserted into the CFG. It maintains both of these, 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// as well as the CFG. It also requires dominator information. 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 26136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.setPreservesCFG(); 26236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<LoopInfo>(); 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreservedID(LoopSimplifyID); 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<AliasAnalysis>(); 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<ScalarEvolution>(); 26836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprivate: 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void verifyAnalysis() const override; 27236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar LCSSA::ID = 0; 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(LoopInfo) 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesPass *llvm::createLCSSAPass() { return new LCSSA(); } 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar &llvm::LCSSAID = LCSSA::ID; 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Process all loops in the function, inner-most out. 28636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool LCSSA::runOnFunction(Function &F) { 28736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 28836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LI = &getAnalysis<LoopInfo>(); 28936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SE = getAnalysisIfAvailable<ScalarEvolution>(); 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Simplify each loop nest in the function. 29336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 29436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= formLCSSARecursively(**I, *DT, SE); 29536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 29736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic void verifyLoop(Loop &L, DominatorTree &DT) { 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Recurse depth-first through inner loops. 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines verifyLoop(**LI, DT); 30336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Check the special guarantees that LCSSA makes. 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines //assert(L.isLCSSAForm(DT) && "LCSSA form not preserved!"); 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid LCSSA::verifyAnalysis() const { 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Verify each loop nest in the function, assuming LI still points at that 31036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // function's loop info. 31136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 31236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines verifyLoop(**I, *DT); 31336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 314