1//===------ SimplifyInstructions.cpp - Remove redundant instructions ------===//
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 is a utility pass used for testing the InstructionSimplify analysis.
11// The analysis is applied to every instruction, and if it simplifies then the
12// instruction is replaced by the simplification.  If you are looking for a pass
13// that performs serious instruction folding, use the instcombine pass instead.
14//
15//===----------------------------------------------------------------------===//
16
17#define DEBUG_TYPE "instsimplify"
18#include "llvm/Function.h"
19#include "llvm/Pass.h"
20#include "llvm/Type.h"
21#include "llvm/ADT/DepthFirstIterator.h"
22#include "llvm/ADT/SmallPtrSet.h"
23#include "llvm/ADT/Statistic.h"
24#include "llvm/Analysis/Dominators.h"
25#include "llvm/Analysis/InstructionSimplify.h"
26#include "llvm/Target/TargetData.h"
27#include "llvm/Target/TargetLibraryInfo.h"
28#include "llvm/Transforms/Scalar.h"
29#include "llvm/Transforms/Utils/Local.h"
30using namespace llvm;
31
32STATISTIC(NumSimplified, "Number of redundant instructions removed");
33
34namespace {
35  struct InstSimplifier : public FunctionPass {
36    static char ID; // Pass identification, replacement for typeid
37    InstSimplifier() : FunctionPass(ID) {
38      initializeInstSimplifierPass(*PassRegistry::getPassRegistry());
39    }
40
41    void getAnalysisUsage(AnalysisUsage &AU) const {
42      AU.setPreservesCFG();
43      AU.addRequired<TargetLibraryInfo>();
44    }
45
46    /// runOnFunction - Remove instructions that simplify.
47    bool runOnFunction(Function &F) {
48      const DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>();
49      const TargetData *TD = getAnalysisIfAvailable<TargetData>();
50      const TargetLibraryInfo *TLI = &getAnalysis<TargetLibraryInfo>();
51      SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
52      bool Changed = false;
53
54      do {
55        for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
56             DE = df_end(&F.getEntryBlock()); DI != DE; ++DI)
57          for (BasicBlock::iterator BI = DI->begin(), BE = DI->end(); BI != BE;) {
58            Instruction *I = BI++;
59            // The first time through the loop ToSimplify is empty and we try to
60            // simplify all instructions.  On later iterations ToSimplify is not
61            // empty and we only bother simplifying instructions that are in it.
62            if (!ToSimplify->empty() && !ToSimplify->count(I))
63              continue;
64            // Don't waste time simplifying unused instructions.
65            if (!I->use_empty())
66              if (Value *V = SimplifyInstruction(I, TD, TLI, DT)) {
67                // Mark all uses for resimplification next time round the loop.
68                for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
69                     UI != UE; ++UI)
70                  Next->insert(cast<Instruction>(*UI));
71                I->replaceAllUsesWith(V);
72                ++NumSimplified;
73                Changed = true;
74              }
75            Changed |= RecursivelyDeleteTriviallyDeadInstructions(I, TLI);
76          }
77
78        // Place the list of instructions to simplify on the next loop iteration
79        // into ToSimplify.
80        std::swap(ToSimplify, Next);
81        Next->clear();
82      } while (!ToSimplify->empty());
83
84      return Changed;
85    }
86  };
87}
88
89char InstSimplifier::ID = 0;
90INITIALIZE_PASS_BEGIN(InstSimplifier, "instsimplify",
91                      "Remove redundant instructions", false, false)
92INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
93INITIALIZE_PASS_END(InstSimplifier, "instsimplify",
94                    "Remove redundant instructions", false, false)
95char &llvm::InstructionSimplifierID = InstSimplifier::ID;
96
97// Public interface to the simplify instructions pass.
98FunctionPass *llvm::createInstructionSimplifierPass() {
99  return new InstSimplifier();
100}
101