1218885Sdim//===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===// 2218885Sdim// 3218885Sdim// The LLVM Compiler Infrastructure 4218885Sdim// 5218885Sdim// This file is distributed under the University of Illinois Open Source 6218885Sdim// License. See LICENSE.TXT for details. 7218885Sdim// 8218885Sdim//===----------------------------------------------------------------------===// 9218885Sdim// 10218885Sdim// This pass performs lightweight instruction simplification on loop bodies. 11218885Sdim// 12218885Sdim//===----------------------------------------------------------------------===// 13218885Sdim 14218885Sdim#define DEBUG_TYPE "loop-instsimplify" 15249423Sdim#include "llvm/Transforms/Scalar.h" 16249423Sdim#include "llvm/ADT/Statistic.h" 17249423Sdim#include "llvm/ADT/STLExtras.h" 18218885Sdim#include "llvm/Analysis/Dominators.h" 19218885Sdim#include "llvm/Analysis/InstructionSimplify.h" 20218885Sdim#include "llvm/Analysis/LoopInfo.h" 21218885Sdim#include "llvm/Analysis/LoopPass.h" 22249423Sdim#include "llvm/IR/DataLayout.h" 23249423Sdim#include "llvm/IR/Instructions.h" 24218885Sdim#include "llvm/Support/Debug.h" 25234353Sdim#include "llvm/Target/TargetLibraryInfo.h" 26218885Sdim#include "llvm/Transforms/Utils/Local.h" 27218885Sdimusing namespace llvm; 28218885Sdim 29218885SdimSTATISTIC(NumSimplified, "Number of redundant instructions simplified"); 30218885Sdim 31218885Sdimnamespace { 32218885Sdim class LoopInstSimplify : public LoopPass { 33218885Sdim public: 34218885Sdim static char ID; // Pass ID, replacement for typeid 35218885Sdim LoopInstSimplify() : LoopPass(ID) { 36218885Sdim initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry()); 37218885Sdim } 38218885Sdim 39218885Sdim bool runOnLoop(Loop*, LPPassManager&); 40218885Sdim 41218885Sdim virtual void getAnalysisUsage(AnalysisUsage &AU) const { 42218885Sdim AU.setPreservesCFG(); 43218885Sdim AU.addRequired<LoopInfo>(); 44218885Sdim AU.addRequiredID(LoopSimplifyID); 45218885Sdim AU.addPreservedID(LoopSimplifyID); 46218885Sdim AU.addPreservedID(LCSSAID); 47218885Sdim AU.addPreserved("scalar-evolution"); 48234353Sdim AU.addRequired<TargetLibraryInfo>(); 49218885Sdim } 50218885Sdim }; 51218885Sdim} 52239462Sdim 53218885Sdimchar LoopInstSimplify::ID = 0; 54218885SdimINITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify", 55218885Sdim "Simplify instructions in loops", false, false) 56234353SdimINITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo) 57218885SdimINITIALIZE_PASS_DEPENDENCY(DominatorTree) 58218885SdimINITIALIZE_PASS_DEPENDENCY(LoopInfo) 59218885SdimINITIALIZE_PASS_DEPENDENCY(LCSSA) 60218885SdimINITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify", 61218885Sdim "Simplify instructions in loops", false, false) 62218885Sdim 63218885SdimPass *llvm::createLoopInstSimplifyPass() { 64218885Sdim return new LoopInstSimplify(); 65218885Sdim} 66218885Sdim 67218885Sdimbool LoopInstSimplify::runOnLoop(Loop *L, LPPassManager &LPM) { 68218885Sdim DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>(); 69218885Sdim LoopInfo *LI = &getAnalysis<LoopInfo>(); 70243830Sdim const DataLayout *TD = getAnalysisIfAvailable<DataLayout>(); 71234353Sdim const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>(); 72218885Sdim 73218885Sdim SmallVector<BasicBlock*, 8> ExitBlocks; 74218885Sdim L->getUniqueExitBlocks(ExitBlocks); 75218885Sdim array_pod_sort(ExitBlocks.begin(), ExitBlocks.end()); 76218885Sdim 77218885Sdim SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2; 78218885Sdim 79218885Sdim // The bit we are stealing from the pointer represents whether this basic 80218885Sdim // block is the header of a subloop, in which case we only process its phis. 81218885Sdim typedef PointerIntPair<BasicBlock*, 1> WorklistItem; 82218885Sdim SmallVector<WorklistItem, 16> VisitStack; 83218885Sdim SmallPtrSet<BasicBlock*, 32> Visited; 84218885Sdim 85218885Sdim bool Changed = false; 86218885Sdim bool LocalChanged; 87218885Sdim do { 88218885Sdim LocalChanged = false; 89218885Sdim 90218885Sdim VisitStack.clear(); 91218885Sdim Visited.clear(); 92218885Sdim 93218885Sdim VisitStack.push_back(WorklistItem(L->getHeader(), false)); 94218885Sdim 95218885Sdim while (!VisitStack.empty()) { 96218885Sdim WorklistItem Item = VisitStack.pop_back_val(); 97218885Sdim BasicBlock *BB = Item.getPointer(); 98218885Sdim bool IsSubloopHeader = Item.getInt(); 99218885Sdim 100218885Sdim // Simplify instructions in the current basic block. 101218885Sdim for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) { 102218885Sdim Instruction *I = BI++; 103218885Sdim 104218885Sdim // The first time through the loop ToSimplify is empty and we try to 105218885Sdim // simplify all instructions. On later iterations ToSimplify is not 106218885Sdim // empty and we only bother simplifying instructions that are in it. 107218885Sdim if (!ToSimplify->empty() && !ToSimplify->count(I)) 108218885Sdim continue; 109218885Sdim 110218885Sdim // Don't bother simplifying unused instructions. 111218885Sdim if (!I->use_empty()) { 112234353Sdim Value *V = SimplifyInstruction(I, TD, TLI, DT); 113218885Sdim if (V && LI->replacementPreservesLCSSAForm(I, V)) { 114218885Sdim // Mark all uses for resimplification next time round the loop. 115218885Sdim for (Value::use_iterator UI = I->use_begin(), UE = I->use_end(); 116218885Sdim UI != UE; ++UI) 117218885Sdim Next->insert(cast<Instruction>(*UI)); 118218885Sdim 119218885Sdim I->replaceAllUsesWith(V); 120218885Sdim LocalChanged = true; 121218885Sdim ++NumSimplified; 122218885Sdim } 123218885Sdim } 124243830Sdim LocalChanged |= RecursivelyDeleteTriviallyDeadInstructions(I, TLI); 125218885Sdim 126218885Sdim if (IsSubloopHeader && !isa<PHINode>(I)) 127218885Sdim break; 128218885Sdim } 129218885Sdim 130218885Sdim // Add all successors to the worklist, except for loop exit blocks and the 131218885Sdim // bodies of subloops. We visit the headers of loops so that we can process 132218885Sdim // their phis, but we contract the rest of the subloop body and only follow 133218885Sdim // edges leading back to the original loop. 134218885Sdim for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; 135218885Sdim ++SI) { 136218885Sdim BasicBlock *SuccBB = *SI; 137218885Sdim if (!Visited.insert(SuccBB)) 138218885Sdim continue; 139218885Sdim 140218885Sdim const Loop *SuccLoop = LI->getLoopFor(SuccBB); 141218885Sdim if (SuccLoop && SuccLoop->getHeader() == SuccBB 142218885Sdim && L->contains(SuccLoop)) { 143218885Sdim VisitStack.push_back(WorklistItem(SuccBB, true)); 144218885Sdim 145218885Sdim SmallVector<BasicBlock*, 8> SubLoopExitBlocks; 146218885Sdim SuccLoop->getExitBlocks(SubLoopExitBlocks); 147218885Sdim 148218885Sdim for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) { 149218885Sdim BasicBlock *ExitBB = SubLoopExitBlocks[i]; 150218885Sdim if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB)) 151218885Sdim VisitStack.push_back(WorklistItem(ExitBB, false)); 152218885Sdim } 153218885Sdim 154218885Sdim continue; 155218885Sdim } 156218885Sdim 157218885Sdim bool IsExitBlock = std::binary_search(ExitBlocks.begin(), 158218885Sdim ExitBlocks.end(), SuccBB); 159218885Sdim if (IsExitBlock) 160218885Sdim continue; 161218885Sdim 162218885Sdim VisitStack.push_back(WorklistItem(SuccBB, false)); 163218885Sdim } 164218885Sdim } 165218885Sdim 166218885Sdim // Place the list of instructions to simplify on the next loop iteration 167218885Sdim // into ToSimplify. 168218885Sdim std::swap(ToSimplify, Next); 169218885Sdim Next->clear(); 170218885Sdim 171218885Sdim Changed |= LocalChanged; 172218885Sdim } while (LocalChanged); 173218885Sdim 174218885Sdim return Changed; 175218885Sdim} 176