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/Transforms/Scalar.h"
19 #include "llvm/ADT/DepthFirstIterator.h"
20 #include "llvm/ADT/SmallPtrSet.h"
21 #include "llvm/ADT/Statistic.h"
22 #include "llvm/Analysis/Dominators.h"
23 #include "llvm/Analysis/InstructionSimplify.h"
24 #include "llvm/IR/DataLayout.h"
25 #include "llvm/IR/Function.h"
26 #include "llvm/IR/Type.h"
27 #include "llvm/Pass.h"
28 #include "llvm/Target/TargetLibraryInfo.h"
29 #include "llvm/Transforms/Utils/Local.h"
30 using namespace llvm;
31
32 STATISTIC(NumSimplified, "Number of redundant instructions removed");
33
34 namespace {
35 struct InstSimplifier : public FunctionPass {
36 static char ID; // Pass identification, replacement for typeid
InstSimplifier__anon97ba993c0111::InstSimplifier37 InstSimplifier() : FunctionPass(ID) {
38 initializeInstSimplifierPass(*PassRegistry::getPassRegistry());
39 }
40
getAnalysisUsage__anon97ba993c0111::InstSimplifier41 void getAnalysisUsage(AnalysisUsage &AU) const {
42 AU.setPreservesCFG();
43 AU.addRequired<TargetLibraryInfo>();
44 }
45
46 /// runOnFunction - Remove instructions that simplify.
runOnFunction__anon97ba993c0111::InstSimplifier47 bool runOnFunction(Function &F) {
48 const DominatorTree *DT = getAnalysisIfAvailable<DominatorTree>();
49 const DataLayout *TD = getAnalysisIfAvailable<DataLayout>();
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
89 char InstSimplifier::ID = 0;
90 INITIALIZE_PASS_BEGIN(InstSimplifier, "instsimplify",
91 "Remove redundant instructions", false, false)
92 INITIALIZE_PASS_DEPENDENCY(TargetLibraryInfo)
93 INITIALIZE_PASS_END(InstSimplifier, "instsimplify",
94 "Remove redundant instructions", false, false)
95 char &llvm::InstructionSimplifierID = InstSimplifier::ID;
96
97 // Public interface to the simplify instructions pass.
createInstructionSimplifierPass()98 FunctionPass *llvm::createInstructionSimplifierPass() {
99 return new InstSimplifier();
100 }
101