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
InstSimplifier__anon646ff0de0111::InstSimplifier36 InstSimplifier() : FunctionPass(ID) {
37 initializeInstSimplifierPass(*PassRegistry::getPassRegistry());
38 }
39
getAnalysisUsage__anon646ff0de0111::InstSimplifier40 void getAnalysisUsage(AnalysisUsage &AU) const {
41 AU.setPreservesCFG();
42 }
43
44 /// runOnFunction - Remove instructions that simplify.
runOnFunction__anon646ff0de0111::InstSimplifier45 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.
createInstructionSimplifierPass()92 FunctionPass *llvm::createInstructionSimplifierPass() {
93 return new InstSimplifier();
94 }
95