LCSSA.cpp revision 36b56886974eae4f9c5ebc96befd3e7bfe5de338
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 30d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner#define DEBUG_TYPE "lcssa" 312480737211fcb466f4f8d2c6c5a7303fd832984bOwen Anderson#include "llvm/Transforms/Scalar.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 33d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 3436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/AliasAnalysis.h" 35b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/LoopPass.h" 36b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/ScalarEvolution.h" 370b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 3836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 390b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 400b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 4136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PredIteratorCache.h" 42d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Transforms/Utils/LoopUtils.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/SSAUpdater.h" 4511f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4611f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 47d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumLCSSA, "Number of live out of a loop variables"); 48d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner 4936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Return true if the specified block is in the list. 5036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool isExitBlock(BasicBlock *BB, 5136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 528c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 5336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ExitBlocks[i] == BB) 548c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 558c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return false; 568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 578c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Given an instruction in the loop, check to see if it has any uses that are 5936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// outside the current loop. If so, insert LCSSA PHI nodes and rewrite the 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// uses. 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks, 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PredIteratorCache &PredCache) { 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<Use *, 16> UsesToRewrite; 658c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *InstBB = Inst.getParent(); 6796bf524b531fd404b118fad7bbe410e9aceeaa5dDevang Patel 6836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Use &U : Inst.uses()) { 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *User = cast<Instruction>(U.getUser()); 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *UserBB = User->getParent(); 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (PHINode *PN = dyn_cast<PHINode>(User)) 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UserBB = PN->getIncomingBlock(U); 73d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 7436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (InstBB != UserBB && !L.contains(UserBB)) 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UsesToRewrite.push_back(&U); 768c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 77a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif 788c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If there are no uses outside the loop, exit with no change. 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UsesToRewrite.empty()) 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 828c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner ++NumLCSSA; // We are applying the transformation 836b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 846b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // Invoke instructions are special in that their result value is not available 8536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // along their unwind edge. The code below tests to see whether DomBB 8636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // dominates 876b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // the value, so adjust DomBB to the normal destination block, which is 886b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // effectively where the value is first usable. 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *DomBB = Inst.getParent(); 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (InvokeInst *Inv = dyn_cast<InvokeInst>(&Inst)) 916b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman DomBB = Inv->getNormalDest(); 926b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 9336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *DomNode = DT.getNode(DomBB); 94d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 9536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<PHINode *, 16> AddedPHIs; 96838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 978c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdater SSAUpdate; 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SSAUpdate.Initialize(Inst.getType(), Inst.getName()); 9936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1008c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Insert the LCSSA phi's into all of the exit blocks dominated by the 101f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // value, and add them to the Phi's map. 10236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (SmallVectorImpl<BasicBlock *>::const_iterator BBI = ExitBlocks.begin(), 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BBE = ExitBlocks.end(); 10436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BBI != BBE; ++BBI) { 1058c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *ExitBB = *BBI; 10636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!DT.dominates(DomNode, DT.getNode(ExitBB))) 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1098c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If we already inserted something for this BB, don't reprocess it. 11036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SSAUpdate.HasValueForBlock(ExitBB)) 11136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PHINode *PN = PHINode::Create(Inst.getType(), PredCache.GetNumPreds(ExitBB), 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Inst.getName() + ".lcssa", ExitBB->begin()); 115d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 1168c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Add inputs from inside the loop for this PHI. 117f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman for (BasicBlock **PI = PredCache.GetPreds(ExitBB); *PI; ++PI) { 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PN->addIncoming(&Inst, *PI); 119f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman 120f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // If the exit block has a predecessor not within the loop, arrange for 121eaa181c83ae7d6295e95753a1d6ae9a684d35fa7Dan Gohman // the incoming value use corresponding to that predecessor to be 122f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // rewritten in terms of a different LCSSA PHI. 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!L.contains(*PI)) 124f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman UsesToRewrite.push_back( 12536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines &PN->getOperandUse(PN->getOperandNumForIncomingValue( 12636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PN->getNumIncomingValues() - 1))); 127f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman } 128838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 129838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich AddedPHIs.push_back(PN); 13036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1318c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Remember that this phi makes the value alive in this block. 1328c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.AddAvailableValue(ExitBB, PN); 13330019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 1344ad3d981b91ac1293b8f2be29e6452d5206107b8Benjamin Kramer 1358c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Rewrite all uses outside the loop in terms of the new PHIs we just 1368c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // inserted. 1378c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner for (unsigned i = 0, e = UsesToRewrite.size(); i != e; ++i) { 1388c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If this use is in an exit block, rewrite to use the newly inserted PHI. 1398c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // This is required for correctness because SSAUpdate doesn't handle uses in 1408c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // the same block. It assumes the PHI we inserted is at the end of the 1418c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // block. 1428c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner Instruction *User = cast<Instruction>(UsesToRewrite[i]->getUser()); 1438c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *UserBB = User->getParent(); 1448c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) 1458c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UserBB = PN->getIncomingBlock(*UsesToRewrite[i]); 1468c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 14736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { 148ccd492c9d6f3cb20b9eb24dc0f102544b482019bBenjamin Kramer // Tell the VHs that the uses changed. This updates SCEV's caches. 149ccd492c9d6f3cb20b9eb24dc0f102544b482019bBenjamin Kramer if (UsesToRewrite[i]->get()->hasValueHandle()) 150ccd492c9d6f3cb20b9eb24dc0f102544b482019bBenjamin Kramer ValueHandleBase::ValueIsRAUWd(*UsesToRewrite[i], UserBB->begin()); 1518c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner UsesToRewrite[i]->set(UserBB->begin()); 152d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner continue; 1532824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 15436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1558c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Otherwise, do full PHI insertion. 1568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.RewriteUse(*UsesToRewrite[i]); 157d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner } 158838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 159838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich // Remove PHI nodes that did not have any uses rewritten. 160838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich for (unsigned i = 0, e = AddedPHIs.size(); i != e; ++i) { 1616e51c6ad9d9c3c02c7b7692e21645beb68408281Cameron Zwarich if (AddedPHIs[i]->use_empty()) 162838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich AddedPHIs[i]->eraseFromParent(); 163838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich } 16436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1658c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 166408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 167d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 16836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Return true if the specified block dominates at least 16936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// one of the blocks in the specified list. 17036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool 17136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesblockDominatesAnExit(BasicBlock *BB, 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT, 17336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 17436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *DomNode = DT.getNode(BB); 17536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (unsigned i = 0, e = ExitBlocks.size(); i != e; ++i) 17636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (DT.dominates(DomNode, DT.getNode(ExitBlocks[i]))) 17736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return true; 17836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 17936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 18036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 18136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool llvm::formLCSSA(Loop &L, DominatorTree &DT, ScalarEvolution *SE) { 18336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 18436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Get the set of exiting blocks. 18636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<BasicBlock *, 8> ExitBlocks; 18736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines L.getExitBlocks(ExitBlocks); 18836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 18936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ExitBlocks.empty()) 19036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 19136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PredIteratorCache PredCache; 19336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 19436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Look at all the instructions in the loop, checking to see if they have uses 19536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // outside the loop. If so, rewrite those uses. 19636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Loop::block_iterator BBI = L.block_begin(), BBE = L.block_end(); 19736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BBI != BBE; ++BBI) { 19836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *BB = *BBI; 19936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // For large loops, avoid use-scanning by using dominance information: In 20136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // particular, if a block does not dominate any of the loop exits, then none 20236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // of the values defined in the block could be used outside the loop. 20336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!blockDominatesAnExit(BB, DT, ExitBlocks)) 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 20536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (BasicBlock::iterator I = BB->begin(), E = BB->end(); I != E; ++I) { 20736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Reject two common cases fast: instructions with no uses (like stores) 20836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // and instructions with one use that is in the same block as this. 20936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (I->use_empty() || 21036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines (I->hasOneUse() && I->user_back()->getParent() == BB && 21136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines !isa<PHINode>(I->user_back()))) 21236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 21336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= processInstruction(L, *I, DT, ExitBlocks, PredCache); 21536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 21636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 21736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 21836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If we modified the code, remove any caches about the loop from SCEV to 21936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // avoid dangling entries. 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: This is a big hammer, can we clear the cache more selectively? 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SE && Changed) 22236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SE->forgetLoop(&L); 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(L.isLCSSAForm(DT)); 22536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 22736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 22836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Process a loop nest depth first. 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, 23136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScalarEvolution *SE) { 23236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Recurse depth-first through inner loops. 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= formLCSSARecursively(**LI, DT, SE); 23736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 23836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= formLCSSA(L, DT, SE); 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 24136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace { 24336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstruct LCSSA : public FunctionPass { 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static char ID; // Pass identification, replacement for typeid 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LCSSA() : FunctionPass(ID) { 24636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines initializeLCSSAPass(*PassRegistry::getPassRegistry()); 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Cached analysis information for the current function. 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree *DT; 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopInfo *LI; 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScalarEvolution *SE; 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// This transformation requires natural loop information & requires that 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// loop preheaders be inserted into the CFG. It maintains both of these, 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// as well as the CFG. It also requires dominator information. 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.setPreservesCFG(); 26136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<LoopInfo>(); 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreservedID(LoopSimplifyID); 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<AliasAnalysis>(); 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreserved<ScalarEvolution>(); 26736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 26836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesprivate: 27036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool processLoop(Loop &L); 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void verifyAnalysis() const override; 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 27436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 27536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 27636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar LCSSA::ID = 0; 27736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_BEGIN(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) 27836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 27936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(LoopInfo) 28036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_END(LCSSA, "lcssa", "Loop-Closed SSA Form Pass", false, false) 28136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesPass *llvm::createLCSSAPass() { return new LCSSA(); } 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hineschar &llvm::LCSSAID = LCSSA::ID; 28436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 28636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Process all loops in the function, inner-most out. 28736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesbool LCSSA::runOnFunction(Function &F) { 28836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 28936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LI = &getAnalysis<LoopInfo>(); 29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SE = getAnalysisIfAvailable<ScalarEvolution>(); 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Simplify each loop nest in the function. 29436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 29536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Changed |= formLCSSARecursively(**I, *DT, SE); 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 29936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic void verifyLoop(Loop &L, DominatorTree &DT) { 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Recurse depth-first through inner loops. 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Loop::iterator LI = L.begin(), LE = L.end(); LI != LE; ++LI) 30336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines verifyLoop(**LI, DT); 30436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Check the special guarantees that LCSSA makes. 30636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines //assert(L.isLCSSAForm(DT) && "LCSSA form not preserved!"); 30736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 30836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesvoid LCSSA::verifyAnalysis() const { 31036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Verify each loop nest in the function, assuming LI still points at that 31136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // function's loop info. 31236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (LoopInfo::iterator I = LI->begin(), E = LI->end(); I != E; ++I) 31336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines verifyLoop(**I, *DT); 31436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 315