Home | History | Annotate | Download | only in Scalar 
      1 //===- LoopInstSimplify.cpp - Loop Instruction Simplification Pass --------===//
      2 //
      3 //                     The LLVM Compiler Infrastructure
      4 //
      5 // This file is distributed under the University of Illinois Open Source
      6 // License. See LICENSE.TXT for details.
      7 //
      8 //===----------------------------------------------------------------------===//
      9 //
     10 // This pass performs lightweight instruction simplification on loop bodies.
     11 //
     12 //===----------------------------------------------------------------------===//
     13 
     14 #define DEBUG_TYPE "loop-instsimplify"
     15 #include "llvm/Transforms/Scalar.h"
     16 #include "llvm/ADT/Statistic.h"
     17 #include "llvm/ADT/STLExtras.h"
     18 #include "llvm/Analysis/Dominators.h"
     19 #include "llvm/Analysis/InstructionSimplify.h"
     20 #include "llvm/Analysis/LoopInfo.h"
     21 #include "llvm/Analysis/LoopPass.h"
     22 #include "llvm/IR/DataLayout.h"
     23 #include "llvm/IR/Instructions.h"
     24 #include "llvm/Support/Debug.h"
     25 #include "llvm/Target/TargetLibraryInfo.h"
     26 #include "llvm/Transforms/Utils/Local.h"
     27 using namespace llvm;
     28 
     29 STATISTIC(NumSimplified, "Number of redundant instructions simplified");
     30 
     31 namespace {
     32   class LoopInstSimplify : public LoopPass {
     33   public:
     34     static char ID; // Pass ID, replacement for typeid
     35     LoopInstSimplify() : LoopPass(ID) {
     36       initializeLoopInstSimplifyPass(*PassRegistry::getPassRegistry());
     37     }
     38 
     39     bool runOnLoop(Loop*, LPPassManager&);
     40 
     41     virtual void getAnalysisUsage(AnalysisUsage &AU) const {
     42       AU.setPreservesCFG();
     43       AU.addRequired<LoopInfo>();
     44       AU.addRequiredID(LoopSimplifyID);
     45       AU.addPreservedID(LoopSimplifyID);
     46       AU.addPreservedID(LCSSAID);
     47       AU.addPreserved("scalar-evolution");
     48       AU.addRequired<TargetLibraryInfo>();
     49     }
     50   };
     51 }
     52 
     53 char LoopInstSimplify::ID = 0;
     54 INITIALIZE_PASS_BEGIN(LoopInstSimplify, "loop-instsimplify",
     55                 "Simplify instructions in loops", false, false)
     56 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
     57 INITIALIZE_PASS_DEPENDENCY(DominatorTree)
     58 INITIALIZE_PASS_DEPENDENCY(LoopInfo)
     59 INITIALIZE_PASS_DEPENDENCY(LCSSA)
     60 INITIALIZE_PASS_END(LoopInstSimplify, "loop-instsimplify",
     61                 "Simplify instructions in loops", false, false)
     62 
     63 Pass *llvm::createLoopInstSimplifyPass() {
     64   return new LoopInstSimplify();
     65 }
     66 
     67 bool LoopInstSimplify::runOnLoop(Loop *L, LPPassManager &LPM) {
     68   DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>();
     69   LoopInfo *LI = &getAnalysis<LoopInfo>();
     70   const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
     71   const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>();
     72 
     73   SmallVector<BasicBlock*, 8> ExitBlocks;
     74   L->getUniqueExitBlocks(ExitBlocks);
     75   array_pod_sort(ExitBlocks.begin(), ExitBlocks.end());
     76 
     77   SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
     78 
     79   // The bit we are stealing from the pointer represents whether this basic
     80   // block is the header of a subloop, in which case we only process its phis.
     81   typedef PointerIntPair<BasicBlock*, 1> WorklistItem;
     82   SmallVector<WorklistItem, 16> VisitStack;
     83   SmallPtrSet<BasicBlock*, 32> Visited;
     84 
     85   bool Changed = false;
     86   bool LocalChanged;
     87   do {
     88     LocalChanged = false;
     89 
     90     VisitStack.clear();
     91     Visited.clear();
     92 
     93     VisitStack.push_back(WorklistItem(L->getHeader(), false));
     94 
     95     while (!VisitStack.empty()) {
     96       WorklistItem Item = VisitStack.pop_back_val();
     97       BasicBlock *BB = Item.getPointer();
     98       bool IsSubloopHeader = Item.getInt();
     99 
    100       // Simplify instructions in the current basic block.
    101       for (BasicBlock::iterator BI = BB->begin(), BE = BB->end(); BI != BE;) {
    102         Instruction *I = BI++;
    103 
    104         // The first time through the loop ToSimplify is empty and we try to
    105         // simplify all instructions. On later iterations ToSimplify is not
    106         // empty and we only bother simplifying instructions that are in it.
    107         if (!ToSimplify->empty() && !ToSimplify->count(I))
    108           continue;
    109 
    110         // Don't bother simplifying unused instructions.
    111         if (!I->use_empty()) {
    112           Value *V = SimplifyInstruction(I, TD, TLI, DT);
    113           if (V && LI->replacementPreservesLCSSAForm(I, V)) {
    114             // Mark all uses for resimplification next time round the loop.
    115             for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
    116                  UI != UE; ++UI)
    117               Next->insert(cast<Instruction>(*UI));
    118 
    119             I->replaceAllUsesWith(V);
    120             LocalChanged = true;
    121             ++NumSimplified;
    122           }
    123         }
    124         LocalChanged |= RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
    125 
    126         if (IsSubloopHeader && !isa<PHINode>(I))
    127           break;
    128       }
    129 
    130       // Add all successors to the worklist, except for loop exit blocks and the
    131       // bodies of subloops. We visit the headers of loops so that we can process
    132       // their phis, but we contract the rest of the subloop body and only follow
    133       // edges leading back to the original loop.
    134       for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE;
    135            ++SI) {
    136         BasicBlock *SuccBB = *SI;
    137         if (!Visited.insert(SuccBB))
    138           continue;
    139 
    140         const Loop *SuccLoop = LI->getLoopFor(SuccBB);
    141         if (SuccLoop && SuccLoop->getHeader() == SuccBB
    142                      && L->contains(SuccLoop)) {
    143           VisitStack.push_back(WorklistItem(SuccBB, true));
    144 
    145           SmallVector<BasicBlock*, 8> SubLoopExitBlocks;
    146           SuccLoop->getExitBlocks(SubLoopExitBlocks);
    147 
    148           for (unsigned i = 0; i < SubLoopExitBlocks.size(); ++i) {
    149             BasicBlock *ExitBB = SubLoopExitBlocks[i];
    150             if (LI->getLoopFor(ExitBB) == L && Visited.insert(ExitBB))
    151               VisitStack.push_back(WorklistItem(ExitBB, false));
    152           }
    153 
    154           continue;
    155         }
    156 
    157         bool IsExitBlock = std::binary_search(ExitBlocks.begin(),
    158                                               ExitBlocks.end(), SuccBB);
    159         if (IsExitBlock)
    160           continue;
    161 
    162         VisitStack.push_back(WorklistItem(SuccBB, false));
    163       }
    164     }
    165 
    166     // Place the list of instructions to simplify on the next loop iteration
    167     // into ToSimplify.
    168     std::swap(ToSimplify, Next);
    169     Next->clear();
    170 
    171     Changed |= LocalChanged;
    172   } while (LocalChanged);
    173 
    174   return Changed;
    175 }
    176