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/Transforms/Scalar.h"
28 #include "llvm/Transforms/Utils/Local.h"
29 using namespace llvm;
30 
31 STATISTIC(NumSimplified, "Number of redundant instructions removed");
32 
33 namespace {
34   struct InstSimplifier : public FunctionPass {
35     static char ID; // Pass identification, replacement for typeid
36     InstSimplifier() : FunctionPass(ID) {
37       initializeInstSimplifierPass(*PassRegistry::getPassRegistry());
38     }
39 
40     void getAnalysisUsage(AnalysisUsage &AU) const {
41       AU.setPreservesCFG();
42     }
43 
44     /// runOnFunction - Remove instructions that simplify.
45     bool runOnFunction(Function &F) {
46       const DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>();
47       const TargetData *TD = getAnalysisIfAvailable<TargetData>();
48       SmallPtrSet<const Instruction*, 8> S1, S2, *ToSimplify = &S1, *Next = &S2;
49       bool Changed = false;
50 
51       do {
52         for (df_iterator<BasicBlock*> DI = df_begin(&F.getEntryBlock()),
53              DE = df_end(&F.getEntryBlock()); DI != DE; ++DI)
54           for (BasicBlock::iterator BI = DI->begin(), BE = DI->end(); BI != BE;) {
55             Instruction *I = BI++;
56             // The first time through the loop ToSimplify is empty and we try to
57             // simplify all instructions.  On later iterations ToSimplify is not
58             // empty and we only bother simplifying instructions that are in it.
59             if (!ToSimplify->empty() && !ToSimplify->count(I))
60               continue;
61             // Don't waste time simplifying unused instructions.
62             if (!I->use_empty())
63               if (Value *V = SimplifyInstruction(I, TD, DT)) {
64                 // Mark all uses for resimplification next time round the loop.
65                 for (Value::use_iterator UI = I->use_begin(), UE = I->use_end();
66                      UI != UE; ++UI)
67                   Next->insert(cast<Instruction>(*UI));
68                 I->replaceAllUsesWith(V);
69                 ++NumSimplified;
70                 Changed = true;
71               }
72             Changed |= RecursivelyDeleteTriviallyDeadInstructions(I);
73           }
74 
75         // Place the list of instructions to simplify on the next loop iteration
76         // into ToSimplify.
77         std::swap(ToSimplify, Next);
78         Next->clear();
79       } while (!ToSimplify->empty());
80 
81       return Changed;
82     }
83   };
84 }
85 
86 char InstSimplifier::ID = 0;
87 INITIALIZE_PASS(InstSimplifier, "instsimplify", "Remove redundant instructions",
88                 false, false)
89 char &llvm::InstructionSimplifierID = InstSimplifier::ID;
90 
91 // Public interface to the simplify instructions pass.
92 FunctionPass *llvm::createInstructionSimplifierPass() {
93   return new InstSimplifier();
94 }
95