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 30de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Transforms/Utils/LCSSA.h" 31d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/STLExtras.h" 32d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/ADT/Statistic.h" 3336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Analysis/AliasAnalysis.h" 34de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Analysis/BasicAliasAnalysis.h" 35f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Analysis/GlobalsModRef.h" 36b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/LoopPass.h" 37b4559a2179bf64fa38b2cccf91b067cc6fcc8e9dDevang Patel#include "llvm/Analysis/ScalarEvolution.h" 38f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar#include "llvm/Analysis/ScalarEvolutionAliasAnalysis.h" 390b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Constants.h" 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 410b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Function.h" 420b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 4336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/PredIteratorCache.h" 44d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Pass.h" 45de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar#include "llvm/Transforms/Scalar.h" 4636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/Transforms/Utils/LoopUtils.h" 47d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Utils/SSAUpdater.h" 4811f510b577878e61e62a3a9c5c8d86483961d20cOwen Andersonusing namespace llvm; 4911f510b577878e61e62a3a9c5c8d86483961d20cOwen Anderson 50dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "lcssa" 51dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 52d216e8ba60494caacf919cbf5fef110d48f0d162Chris LattnerSTATISTIC(NumLCSSA, "Number of live out of a loop variables"); 53d216e8ba60494caacf919cbf5fef110d48f0d162Chris Lattner 5436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Return true if the specified block is in the list. 5536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool isExitBlock(BasicBlock *BB, 5636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 57de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return find(ExitBlocks, BB) != ExitBlocks.end(); 588c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner} 598c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 6036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Given an instruction in the loop, check to see if it has any uses that are 6136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// outside the current loop. If so, insert LCSSA PHI nodes and rewrite the 6236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// uses. 6336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool processInstruction(Loop &L, Instruction &Inst, DominatorTree &DT, 6436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks, 65ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PredIteratorCache &PredCache, LoopInfo *LI) { 6636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<Use *, 16> UsesToRewrite; 678c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 68f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // Tokens cannot be used in PHI nodes, so we skip over them. 69f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // We can run into tokens which are live out of a loop with catchswitch 70f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // instructions in Windows EH if the catchswitch has one catchpad which 71f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // is inside the loop and another which is not. 72f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (Inst.getType()->isTokenTy()) 73f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar return false; 74f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar 7536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *InstBB = Inst.getParent(); 7696bf524b531fd404b118fad7bbe410e9aceeaa5dDevang Patel 7736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (Use &U : Inst.uses()) { 7836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Instruction *User = cast<Instruction>(U.getUser()); 7936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *UserBB = User->getParent(); 8036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (PHINode *PN = dyn_cast<PHINode>(User)) 8136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UserBB = PN->getIncomingBlock(U); 82d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 8336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (InstBB != UserBB && !L.contains(UserBB)) 8436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines UsesToRewrite.push_back(&U); 858c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner } 86a29742df5f349771d1a2fa61602f7bad8a7840d3Gabor Greif 878c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If there are no uses outside the loop, exit with no change. 8836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (UsesToRewrite.empty()) 8936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 9036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 918c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner ++NumLCSSA; // We are applying the transformation 926b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 936b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman // Invoke instructions are special in that their result value is not available 9436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // along their unwind edge. The code below tests to see whether DomBB 95f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // dominates the value, so adjust DomBB to the normal destination block, 96f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar // which is effectively where the value is first usable. 9736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines BasicBlock *DomBB = Inst.getParent(); 9836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (InvokeInst *Inv = dyn_cast<InvokeInst>(&Inst)) 996b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman DomBB = Inv->getNormalDest(); 1006b9c959c61e77b1bc78a93ee4a6cac8eaa656a21Dan Gohman 10136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *DomNode = DT.getNode(DomBB); 102d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 10336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<PHINode *, 16> AddedPHIs; 104ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<PHINode *, 8> PostProcessPHIs; 105838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 1068c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdater SSAUpdate; 10736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SSAUpdate.Initialize(Inst.getType(), Inst.getName()); 10836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1098c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Insert the LCSSA phi's into all of the exit blocks dominated by the 110f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // value, and add them to the Phi's map. 111f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (BasicBlock *ExitBB : ExitBlocks) { 11236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!DT.dominates(DomNode, DT.getNode(ExitBB))) 11336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 11436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1158c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If we already inserted something for this BB, don't reprocess it. 11636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SSAUpdate.HasValueForBlock(ExitBB)) 11736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 11836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1196948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PHINode *PN = PHINode::Create(Inst.getType(), PredCache.size(ExitBB), 120f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Inst.getName() + ".lcssa", &ExitBB->front()); 121d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 1228c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Add inputs from inside the loop for this PHI. 1236948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar for (BasicBlock *Pred : PredCache.get(ExitBB)) { 1246948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar PN->addIncoming(&Inst, Pred); 125f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman 126f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // If the exit block has a predecessor not within the loop, arrange for 127eaa181c83ae7d6295e95753a1d6ae9a684d35fa7Dan Gohman // the incoming value use corresponding to that predecessor to be 128f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman // rewritten in terms of a different LCSSA PHI. 1296948897e478cbd66626159776a8017b3c18579b9Pirama Arumuga Nainar if (!L.contains(Pred)) 130f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman UsesToRewrite.push_back( 13136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines &PN->getOperandUse(PN->getOperandNumForIncomingValue( 13236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PN->getNumIncomingValues() - 1))); 133f6572d0aa2abb87d34afcca3e3bec89e1613b8ecDan Gohman } 134838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 135838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich AddedPHIs.push_back(PN); 13636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1378c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Remember that this phi makes the value alive in this block. 1388c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner SSAUpdate.AddAvailableValue(ExitBB, PN); 139ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 140ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // LoopSimplify might fail to simplify some loops (e.g. when indirect 141ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // branches are involved). In such situations, it might happen that an exit 142ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // for Loop L1 is the header of a disjoint Loop L2. Thus, when we create 143ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // PHIs in such an exit block, we are also inserting PHIs into L2's header. 144ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // This could break LCSSA form for L2 because these inserted PHIs can also 145ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // have uses outside of L2. Remember all PHIs in such situation as to 146ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // revisit than later on. FIXME: Remove this if indirectbr support into 147ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // LoopSimplify gets improved. 148ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (auto *OtherLoop = LI->getLoopFor(ExitBB)) 149ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (!L.contains(OtherLoop)) 150ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines PostProcessPHIs.push_back(PN); 15130019c88f4b9227460335cbafab0f770eb356083Owen Anderson } 1524ad3d981b91ac1293b8f2be29e6452d5206107b8Benjamin Kramer 1538c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Rewrite all uses outside the loop in terms of the new PHIs we just 1548c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // inserted. 155f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (Use *UseToRewrite : UsesToRewrite) { 1568c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // If this use is in an exit block, rewrite to use the newly inserted PHI. 1578c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // This is required for correctness because SSAUpdate doesn't handle uses in 1588c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // the same block. It assumes the PHI we inserted is at the end of the 1598c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // block. 160f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Instruction *User = cast<Instruction>(UseToRewrite->getUser()); 1618c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner BasicBlock *UserBB = User->getParent(); 1628c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner if (PHINode *PN = dyn_cast<PHINode>(User)) 163f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UserBB = PN->getIncomingBlock(*UseToRewrite); 1648c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner 16536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (isa<PHINode>(UserBB->begin()) && isExitBlock(UserBB, ExitBlocks)) { 166ccd492c9d6f3cb20b9eb24dc0f102544b482019bBenjamin Kramer // Tell the VHs that the uses changed. This updates SCEV's caches. 167f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (UseToRewrite->get()->hasValueHandle()) 168f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar ValueHandleBase::ValueIsRAUWd(*UseToRewrite, &UserBB->front()); 169f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar UseToRewrite->set(&UserBB->front()); 170d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner continue; 1712824da4738aba79a140ce77ccc918587ea9d534aOwen Anderson } 17236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 1738c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner // Otherwise, do full PHI insertion. 174f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SSAUpdate.RewriteUse(*UseToRewrite); 175d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner } 176838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich 177ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Post process PHI instructions that were inserted into another disjoint loop 178ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // and update their exits properly. 179ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines for (auto *I : PostProcessPHIs) { 180ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (I->use_empty()) 181ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines continue; 182ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 183ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines BasicBlock *PHIBB = I->getParent(); 184ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Loop *OtherLoop = LI->getLoopFor(PHIBB); 185ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines SmallVector<BasicBlock *, 8> EBs; 186ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines OtherLoop->getExitBlocks(EBs); 187ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines if (EBs.empty()) 188ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines continue; 189ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 190ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // Recurse and re-process each PHI instruction. FIXME: we should really 191ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // convert this entire thing to a worklist approach where we process a 192ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines // vector of instructions... 193ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines processInstruction(*OtherLoop, *I, DT, EBs, PredCache, LI); 194ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines } 195ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines 196838b97edfaf7470941d0e89ef3b9ed8867c93fc4Cameron Zwarich // Remove PHI nodes that did not have any uses rewritten. 197f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (PHINode *PN : AddedPHIs) 198f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (PN->use_empty()) 199f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar PN->eraseFromParent(); 20036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 2018c1db67a4c58fc05e41fd530129a7bc5fd8f8b20Chris Lattner return true; 202408a4061d8c119691c92fb8aa8c5dc2f9c05ccb0Owen Anderson} 203d41ae8bc0c4c3ebfd59197bccee72bb5b5c2cbfeChris Lattner 20436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Return true if the specified block dominates at least 20536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// one of the blocks in the specified list. 20636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesstatic bool 20736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesblockDominatesAnExit(BasicBlock *BB, 20836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree &DT, 20936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines const SmallVectorImpl<BasicBlock *> &ExitBlocks) { 21036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DomTreeNode *DomNode = DT.getNode(BB); 211de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return llvm::any_of(ExitBlocks, [&](BasicBlock * EB) { 212de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return DT.dominates(DomNode, DT.getNode(EB)); 213de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar }); 21436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 21536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 216ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool llvm::formLCSSA(Loop &L, DominatorTree &DT, LoopInfo *LI, 217ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines ScalarEvolution *SE) { 21836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 21936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Get the set of exiting blocks. 22136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SmallVector<BasicBlock *, 8> ExitBlocks; 22236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines L.getExitBlocks(ExitBlocks); 22336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (ExitBlocks.empty()) 22536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 22636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines PredIteratorCache PredCache; 22836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 22936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Look at all the instructions in the loop, checking to see if they have uses 23036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // outside the loop. If so, rewrite those uses. 231f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (BasicBlock *BB : L.blocks()) { 23236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // For large loops, avoid use-scanning by using dominance information: In 23336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // particular, if a block does not dominate any of the loop exits, then none 23436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // of the values defined in the block could be used outside the loop. 23536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (!blockDominatesAnExit(BB, DT, ExitBlocks)) 23636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 23736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 238f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (Instruction &I : *BB) { 23936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Reject two common cases fast: instructions with no uses (like stores) 24036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // and instructions with one use that is in the same block as this. 241f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar if (I.use_empty() || 242f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar (I.hasOneUse() && I.user_back()->getParent() == BB && 243f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar !isa<PHINode>(I.user_back()))) 24436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines continue; 24536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 246f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Changed |= processInstruction(L, I, DT, ExitBlocks, PredCache, LI); 24736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 24836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 24936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // If we modified the code, remove any caches about the loop from SCEV to 25136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // avoid dangling entries. 25236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // FIXME: This is a big hammer, can we clear the cache more selectively? 25336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (SE && Changed) 25436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines SE->forgetLoop(&L); 25536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines assert(L.isLCSSAForm(DT)); 25736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 25836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 25936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 26036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines/// Process a loop nest depth first. 262ebe69fe11e48d322045d5949c83283927a0d790bStephen Hinesbool llvm::formLCSSARecursively(Loop &L, DominatorTree &DT, LoopInfo *LI, 26336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScalarEvolution *SE) { 26436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool Changed = false; 26536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 26636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Recurse depth-first through inner loops. 267f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar for (Loop *SubLoop : L.getSubLoops()) 268f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar Changed |= formLCSSARecursively(*SubLoop, DT, LI, SE); 26936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 270ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines Changed |= formLCSSA(L, DT, LI, SE); 27136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return Changed; 27236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 27336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 274de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Process all loops in the function, inner-most out. 275de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstatic bool formLCSSAOnAllLoops(LoopInfo *LI, DominatorTree &DT, 276de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar ScalarEvolution *SE) { 277de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar bool Changed = false; 278de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar for (auto &L : *LI) 279de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar Changed |= formLCSSARecursively(*L, DT, LI, SE); 280de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return Changed; 281de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 282de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 28336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hinesnamespace { 284de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarstruct LCSSAWrapperPass : public FunctionPass { 28536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines static char ID; // Pass identification, replacement for typeid 286de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar LCSSAWrapperPass() : FunctionPass(ID) { 287de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar initializeLCSSAWrapperPassPass(*PassRegistry::getPassRegistry()); 28836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 28936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines // Cached analysis information for the current function. 29136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTree *DT; 29236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines LoopInfo *LI; 29336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines ScalarEvolution *SE; 29436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnFunction(Function &F) override; 29636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 29736b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// This transformation requires natural loop information & requires that 29836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// loop preheaders be inserted into the CFG. It maintains both of these, 29936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines /// as well as the CFG. It also requires dominator information. 30036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 30136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.setPreservesCFG(); 30236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 30336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addRequired<DominatorTreeWrapperPass>(); 304ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines AU.addRequired<LoopInfoWrapperPass>(); 30536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines AU.addPreservedID(LoopSimplifyID); 306f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addPreserved<AAResultsWrapperPass>(); 307de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar AU.addPreserved<BasicAAWrapperPass>(); 308f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addPreserved<GlobalsAAWrapperPass>(); 309f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addPreserved<ScalarEvolutionWrapperPass>(); 310f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar AU.addPreserved<SCEVAAWrapperPass>(); 31136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines } 31236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines}; 31336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 31436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 315de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarchar LCSSAWrapperPass::ID = 0; 316de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_BEGIN(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", 317de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar false, false) 31836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 319ebe69fe11e48d322045d5949c83283927a0d790bStephen HinesINITIALIZE_PASS_DEPENDENCY(LoopInfoWrapperPass) 320de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarINITIALIZE_PASS_END(LCSSAWrapperPass, "lcssa", "Loop-Closed SSA Form Pass", 321de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar false, false) 32236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 323de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarPass *llvm::createLCSSAPass() { return new LCSSAWrapperPass(); } 324de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarchar &llvm::LCSSAID = LCSSAWrapperPass::ID; 32536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 326de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar/// Transform \p F into loop-closed SSA form. 327de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainarbool LCSSAWrapperPass::runOnFunction(Function &F) { 328ebe69fe11e48d322045d5949c83283927a0d790bStephen Hines LI = &getAnalysis<LoopInfoWrapperPass>().getLoopInfo(); 32936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DT = &getAnalysis<DominatorTreeWrapperPass>().getDomTree(); 330f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar auto *SEWP = getAnalysisIfAvailable<ScalarEvolutionWrapperPass>(); 331f3ef5332fa3f4d5ec72c178a2b19dac363a19383Pirama Arumuga Nainar SE = SEWP ? &SEWP->getSE() : nullptr; 33236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 333de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return formLCSSAOnAllLoops(LI, *DT, SE); 33436b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines} 33536b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 336de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga NainarPreservedAnalyses LCSSAPass::run(Function &F, AnalysisManager<Function> &AM) { 337de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &LI = AM.getResult<LoopAnalysis>(F); 338de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto &DT = AM.getResult<DominatorTreeAnalysis>(F); 339de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar auto *SE = AM.getCachedResult<ScalarEvolutionAnalysis>(F); 340de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar if (!formLCSSAOnAllLoops(&LI, DT, SE)) 341de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return PreservedAnalyses::all(); 342de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar 343de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar // FIXME: This should also 'preserve the CFG'. 344de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PreservedAnalyses PA; 345de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PA.preserve<BasicAA>(); 346de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PA.preserve<GlobalsAA>(); 347de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PA.preserve<SCEVAA>(); 348de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar PA.preserve<ScalarEvolutionAnalysis>(); 349de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar return PA; 350de2d8694e25a814696358e95141f4b1aa4d8847ePirama Arumuga Nainar} 351