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 14832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#define DEBUG_TYPE "loop-instsimplify" 158368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich#include "llvm/Instructions.h" 16832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/Analysis/Dominators.h" 17832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/Analysis/InstructionSimplify.h" 18a1cb585384f593517a9b8f48693f5e478b833fbaCameron Zwarich#include "llvm/Analysis/LoopInfo.h" 19e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich#include "llvm/Analysis/LoopPass.h" 20e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich#include "llvm/Support/Debug.h" 21832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/Target/TargetData.h" 22618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier#include "llvm/Target/TargetLibraryInfo.h" 23832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/Transforms/Scalar.h" 24832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/Transforms/Utils/Local.h" 25832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich#include "llvm/ADT/Statistic.h" 26832f61117d69019376c4aabedd4de3831279e288Cameron Zwarichusing namespace llvm; 27832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 28832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichSTATISTIC(NumSimplified, "Number of redundant instructions simplified"); 29832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 30832f61117d69019376c4aabedd4de3831279e288Cameron Zwarichnamespace { 31e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich class LoopInstSimplify : public LoopPass { 32832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich public: 33832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich static char ID; // Pass ID, replacement for typeid 34e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich LoopInstSimplify() : LoopPass(ID) { 35832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry()); 36832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 37832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 38e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich bool runOnLoop(Loop*, LPPassManager&); 39832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 4064573aecb6ee43202327e938cc42dd2c1ad0f045Cameron Zwarich virtual void getAnalysisUsage(AnalysisUsage &AU) const { 41832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich AU.setPreservesCFG(); 42832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich AU.addRequired<LoopInfo>(); 43e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich AU.addRequiredID(LoopSimplifyID); 44e7d7865bfdc26c0e9732c6a98a36289b64fdc84aCameron Zwarich AU.addPreservedID(LoopSimplifyID); 45832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich AU.addPreservedID(LCSSAID); 46fae0abe8eb0def41ee8617aea04c4f18f07d95e8Cameron Zwarich AU.addPreserved("scalar-evolution"); 47618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier AU.addRequired<TargetLibraryInfo>(); 48832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 49832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich }; 50832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich} 51a94d6e87c4c49f2e81b01d66d8bfb591277f8f96Nadav Rotem 52832f61117d69019376c4aabedd4de3831279e288Cameron Zwarichchar LoopInstSimplify::ID = 0; 53832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify", 54832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich "Simplify instructions in loops", false, false) 55618c1dbd293d15ee19f61b1156ab8086ad28311aChad RosierINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 56832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_DEPENDENCY(DominatorTree) 57832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_DEPENDENCY(LoopInfo) 58832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_DEPENDENCY(LCSSA) 59832f61117d69019376c4aabedd4de3831279e288Cameron ZwarichINITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify", 60832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich "Simplify instructions in loops", false, false) 61832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 62b434acb7beeccc34b07f30bae24664e420b1227aCameron ZwarichPass *llvm::createLoopInstSimplifyPass() { 63832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich return new LoopInstSimplify(); 64832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich} 65832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 66e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarichbool LoopInstSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 6764573aecb6ee43202327e938cc42dd2c1ad0f045Cameron Zwarich DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>(); 6864573aecb6ee43202327e938cc42dd2c1ad0f045Cameron Zwarich LoopInfo *LI = &getAnalysis<LoopInfo>(); 6964573aecb6ee43202327e938cc42dd2c1ad0f045Cameron Zwarich const TargetData *TD = getAnalysisIfAvailable<TargetData>(); 70618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>(); 71832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 72e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich SmallVector<BasicBlock*, 8> ExitBlocks; 73e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich L->getUniqueExitBlocks(ExitBlocks); 74e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich array_pod_sort(ExitBlocks.begin(), ExitBlocks.end()); 75e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 7608602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 7708602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 788368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // The bit we are stealing from the pointer represents whether this basic 798368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // block is the header of a subloop, in which case we only process its phis. 808368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich typedef PointerIntPair<BasicBlock*, 1> WorklistItem; 818368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich SmallVector<WorklistItem, 16> VisitStack; 82e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich SmallPtrSet<BasicBlock*, 32> Visited; 83e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 84832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich bool Changed = false; 85832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich bool LocalChanged; 86832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich do { 87832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich LocalChanged = false; 88832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 89e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich VisitStack.clear(); 90e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich Visited.clear(); 91e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 928368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(L->getHeader(), false)); 93e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 94e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich while (!VisitStack.empty()) { 958368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich WorklistItem Item = VisitStack.pop_back_val(); 96b434acb7beeccc34b07f30bae24664e420b1227aCameron Zwarich BasicBlock *BB = Item.getPointer(); 978368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich bool IsSubloopHeader = Item.getInt(); 98e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 99e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich // Simplify instructions in the current basic block. 100e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 10164573aecb6ee43202327e938cc42dd2c1ad0f045Cameron Zwarich Instruction *I = BI++; 10208602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 10308602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // The first time through the loop ToSimplify is empty and we try to 10408602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // simplify all instructions. On later iterations ToSimplify is not 10508602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // empty and we only bother simplifying instructions that are in it. 10608602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich if (!ToSimplify->empty() && !ToSimplify->count(I)) 10708602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich continue; 10808602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 109832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich // Don't bother simplifying unused instructions. 110832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich if (!I->use_empty()) { 111618c1dbd293d15ee19f61b1156ab8086ad28311aChad Rosier Value *V = SimplifyInstruction(I, TD, TLI, DT); 112a1cb585384f593517a9b8f48693f5e478b833fbaCameron Zwarich if (V && LI->replacementPreservesLCSSAForm(I, V)) { 11308602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // Mark all uses for resimplification next time round the loop. 11408602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 11508602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich UI != UE; ++UI) 11608602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich Next->insert(cast<Instruction>(*UI)); 11708602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 118832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich I->replaceAllUsesWith(V); 119832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich LocalChanged = true; 120832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich ++NumSimplified; 121832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 122832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 1238e0d1c03ca7fd86e6879b4e37d0d7f0e982feef6Benjamin Kramer LocalChanged |= RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 1248368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1258368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (IsSubloopHeader && !isa<PHINode>(I)) 1268368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich break; 127832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } 128832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 1298368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // Add all successors to the worklist, except for loop exit blocks and the 1308368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // bodies of subloops. We visit the headers of loops so that we can process 1318368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // their phis, but we contract the rest of the subloop body and only follow 1328368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich // edges leading back to the original loop. 133e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 134e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich ++SI) { 135e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich BasicBlock *SuccBB = *SI; 1368368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (!Visited.insert(SuccBB)) 1378368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich continue; 1388368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1398368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich const Loop *SuccLoop = LI->getLoopFor(SuccBB); 1408368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (SuccLoop && SuccLoop->getHeader() == SuccBB 1418368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich && L->contains(SuccLoop)) { 1428368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(SuccBB, true)); 1438368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1448368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich SmallVector<BasicBlock*, 8> SubLoopExitBlocks; 1458368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich SuccLoop->getExitBlocks(SubLoopExitBlocks); 1468368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1478368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) { 1488368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich BasicBlock *ExitBB = SubLoopExitBlocks[i]; 1498368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB)) 1508368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(ExitBB, false)); 1518368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich } 1528368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1538368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich continue; 1548368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich } 1558368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 156e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich bool IsExitBlock = std::binary_search(ExitBlocks.begin(), 1578368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich ExitBlocks.end(), SuccBB); 1588368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich if (IsExitBlock) 1598368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich continue; 1608368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich 1618368ac3688ccbb9f61b35a369ddc43ff90f8cdbdCameron Zwarich VisitStack.push_back(WorklistItem(SuccBB, false)); 162e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich } 163e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich } 164e389ab16f3d98c2491dd2d8649b782203590a938Cameron Zwarich 16508602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // Place the list of instructions to simplify on the next loop iteration 16608602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich // into ToSimplify. 16708602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich std::swap(ToSimplify, Next); 16808602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich Next->clear(); 16908602ab1b4b90e26d406ffb886a685c66270698cCameron Zwarich 170a1cb585384f593517a9b8f48693f5e478b833fbaCameron Zwarich Changed |= LocalChanged; 171832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich } while (LocalChanged); 172832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich 173832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich return Changed; 174832f61117d69019376c4aabedd4de3831279e288Cameron Zwarich} 175