1832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===// 2832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// 3832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// The LLVM Compiler Infrastructure 4832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// 5832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// This file is distributed under the University of Illinois Open Source 6832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// License. See LICENSE.TXT for details. 7832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// 8832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich//===----------------------------------------------------------------------===// 9832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// 10832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// This pass performs lightweight instruction simplification on loop bodies. 11832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich// 12832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich//===----------------------------------------------------------------------===// 13832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 14d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Transforms/Scalar.h" 154fa57932c7b13ec42c563e33a2e40fd04194b64eJakub Staszak#include "llvm/ADT/STLExtras.h" 1636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/ADT/Statistic.h" 17832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/Analysis/InstructionSimplify.h" 18a1cb585384f593517a9b8f48693f5e478b833fbaCameron Zwarich#include "llvm/Analysis/LoopInfo.h" 19e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich#include "llvm/Analysis/LoopPass.h" 200b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/DataLayout.h" 2136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines#include "llvm/IR/Dominators.h" 220b8c9a80f20772c3793201ab5b251d3520b9cea3Chandler Carruth#include "llvm/IR/Instructions.h" 23d04a8d4b33ff316ca4cf961e06c9e312eff8e64fChandler Carruth#include "llvm/Support/Debug.h" 24618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier#include "llvm/Target/TargetLibraryInfo.h" 25832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/Transforms/Utils/Local.h" 26832f61117d69019376c4aabedd4de3831279e288Cameron Zwarichusing namespace llvm; 27832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 28dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines#define DEBUG_TYPE "loop-instsimplify" 29dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines 30832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichSTATISTIC(NumSimplified, "Number of redundant instructions simplified"); 31832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 32832f61117d69019376c4aabedd4de3831279e288Cameron Zwarichnamespace { 33e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich class LoopInstSimplify : public LoopPass { 34832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich public: 35832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich static char ID; // Pass ID, replacement for typeid 36e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich LoopInstSimplify() : LoopPass(ID) { 37832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry()); 38832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 39832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 4036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines bool runOnLoop(Loop*, LPPassManager&) override; 41832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 4236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines void getAnalysisUsage(AnalysisUsage &AU) const override { 43832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich AU.setPreservesCFG(); 44832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich AU.addRequired<LoopInfo>(); 45e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich AU.addRequiredID(LoopSimplifyID); 46e7d7865bfdc26c0e9732c6a98a36289b64fdc84aCameron Zwarich AU.addPreservedID(LoopSimplifyID); 47832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich AU.addPreservedID(LCSSAID); 48fae0abe8eb0def41ee8617aea04c4f18f07d95e8Cameron Zwarich AU.addPreserved("scalar-evolution"); 49618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier AU.addRequired<TargetLibraryInfo>(); 50832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 51832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich }; 52832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich} 53a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 54832f61117d69019376c4aabedd4de3831279e288Cameron Zwarichchar LoopInstSimplify::ID = 0; 55832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify", 56832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich "Simplify instructions in loops", false, false) 57618c1dbd293d15ee19f61b1156ab8086ad28311aChad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 5836b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen HinesINITIALIZE_PASS_DEPENDENCY(DominatorTreeWrapperPass) 59832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_DEPENDENCY(LoopInfo) 60832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_DEPENDENCY(LCSSA) 61832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify", 62832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich "Simplify instructions in loops", false, false) 63832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 64b434acb7beeccc34b07f30bae24664e420b1227aCameron ZwarichPass *llvm::createLoopInstSimplifyPass() { 65832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich return new LoopInstSimplify(); 66832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich} 67832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 68e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarichbool LoopInstSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 6936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines if (skipOptnoneFunction(L)) 7036b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines return false; 7136b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines 7236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DominatorTreeWrapperPass *DTWP = 7336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines getAnalysisIfAvailable<DominatorTreeWrapperPass>(); 74dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines DominatorTree *DT = DTWP ? &DTWP->getDomTree() : nullptr; 7564573aecb6ee43202327e938cc42dd2c1ad0f045Cameron Zwarich LoopInfo *LI = &getAnalysis<LoopInfo>(); 7636b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines DataLayoutPass *DLP = getAnalysisIfAvailable<DataLayoutPass>(); 77dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines const DataLayout *DL = DLP ? &DLP->getDataLayout() : nullptr; 78618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>(); 79832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 80e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich SmallVector<BasicBlock*, 8> ExitBlocks; 81e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich L->getUniqueExitBlocks(ExitBlocks); 82e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich array_pod_sort(ExitBlocks.begin(), ExitBlocks.end()); 83e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 8408602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 8508602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 868368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // The bit we are stealing from the pointer represents whether this basic 878368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // block is the header of a subloop, in which case we only process its phis. 888368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich typedef PointerIntPair<BasicBlock*, 1> WorklistItem; 898368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich SmallVector<WorklistItem, 16> VisitStack; 90e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich SmallPtrSet<BasicBlock*, 32> Visited; 91e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 92832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich bool Changed = false; 93832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich bool LocalChanged; 94832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich do { 95832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich LocalChanged = false; 96832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 97e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich VisitStack.clear(); 98e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich Visited.clear(); 99e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 1008368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(L->getHeader(), false)); 101e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 102e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich while (!VisitStack.empty()) { 1038368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich WorklistItem Item = VisitStack.pop_back_val(); 104b434acb7beeccc34b07f30bae24664e420b1227aCameron Zwarich BasicBlock *BB = Item.getPointer(); 1058368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich bool IsSubloopHeader = Item.getInt(); 106e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 107e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich // Simplify instructions in the current basic block. 108e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 10964573aecb6ee43202327e938cc42dd2c1ad0f045Cameron Zwarich Instruction *I = BI++; 11008602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 11108602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // The first time through the loop ToSimplify is empty and we try to 11208602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // simplify all instructions. On later iterations ToSimplify is not 11308602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // empty and we only bother simplifying instructions that are in it. 11408602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich if (!ToSimplify->empty() && !ToSimplify->count(I)) 11508602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich continue; 11608602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 117832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich // Don't bother simplifying unused instructions. 118832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich if (!I->use_empty()) { 11936b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Value *V = SimplifyInstruction(I, DL, TLI, DT); 120a1cb585384f593517a9b8f48693f5e478b833fbaCameron Zwarich if (V && LI->replacementPreservesLCSSAForm(I, V)) { 12108602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // Mark all uses for resimplification next time round the loop. 12236b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines for (User *U : I->users()) 12336b56886974eae4f9c5ebc96befd3e7bfe5de338Stephen Hines Next->insert(cast<Instruction>(U)); 12408602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 125832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich I->replaceAllUsesWith(V); 126832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich LocalChanged = true; 127832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich ++NumSimplified; 128832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 129832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 130dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines bool res = RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 131dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines if (res) { 132dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // RecursivelyDeleteTriviallyDeadInstruction can remove 133dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // more than one instruction, so simply incrementing the 134dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // iterator does not work. When instructions get deleted 135dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines // re-iterate instead. 136dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines BI = BB->begin(); BE = BB->end(); 137dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines LocalChanged |= res; 138dce4a407a24b04eebc6a376f8e62b41aaa7b071fStephen Hines } 1398368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1408368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (IsSubloopHeader && !isa<PHINode>(I)) 1418368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich break; 142832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 143832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 1448368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // Add all successors to the worklist, except for loop exit blocks and the 1458368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // bodies of subloops. We visit the headers of loops so that we can process 1468368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // their phis, but we contract the rest of the subloop body and only follow 1478368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // edges leading back to the original loop. 148e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 149e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich ++SI) { 150e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich BasicBlock *SuccBB = *SI; 1518368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (!Visited.insert(SuccBB)) 1528368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich continue; 1538368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1548368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich const Loop *SuccLoop = LI->getLoopFor(SuccBB); 1558368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (SuccLoop && SuccLoop->getHeader() == SuccBB 1568368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich && L->contains(SuccLoop)) { 1578368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(SuccBB, true)); 1588368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1598368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich SmallVector<BasicBlock*, 8> SubLoopExitBlocks; 1608368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich SuccLoop->getExitBlocks(SubLoopExitBlocks); 1618368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1628368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) { 1638368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich BasicBlock *ExitBB = SubLoopExitBlocks[i]; 1648368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB)) 1658368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(ExitBB, false)); 1668368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich } 1678368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1688368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich continue; 1698368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich } 1708368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 171e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich bool IsExitBlock = std::binary_search(ExitBlocks.begin(), 1728368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich ExitBlocks.end(), SuccBB); 1738368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (IsExitBlock) 1748368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich continue; 1758368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1768368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(SuccBB, false)); 177e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich } 178e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich } 179e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 18008602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // Place the list of instructions to simplify on the next loop iteration 18108602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // into ToSimplify. 18208602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich std::swap(ToSimplify, Next); 18308602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich Next->clear(); 18408602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 185a1cb585384f593517a9b8f48693f5e478b833fbaCameron Zwarich Changed |= LocalChanged; 186832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } while (LocalChanged); 187832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 188832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich return Changed; 189832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich} 190