1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
|
//===- SimplifyCFG.cpp - CFG Simplification Pass --------------------------===//
//
// The LLVM Compiler Infrastructure
//
// This file was developed by the LLVM research group and is distributed under
// the University of Illinois Open Source License. See LICENSE.TXT for details.
//
//===----------------------------------------------------------------------===//
//
// This file implements dead code elimination and basic block merging.
//
// Specifically, this:
// * removes basic blocks with no predecessors
// * merges a basic block into its predecessor if there is only one and the
// predecessor only has one successor.
// * Eliminates PHI nodes for basic blocks with a single predecessor
// * Eliminates a basic block that only contains an unconditional branch
//
//===----------------------------------------------------------------------===//
#define DEBUG_TYPE "simplifycfg"
#include "llvm/Transforms/Scalar.h"
#include "llvm/Transforms/Utils/Local.h"
#include "llvm/Constants.h"
#include "llvm/Instructions.h"
#include "llvm/Module.h"
#include "llvm/Support/CFG.h"
#include "llvm/Support/Compiler.h"
#include "llvm/Pass.h"
#include "llvm/ADT/SmallPtrSet.h"
#include "llvm/ADT/Statistic.h"
using namespace llvm;
STATISTIC(NumSimpl, "Number of blocks simplified");
namespace {
struct VISIBILITY_HIDDEN CFGSimplifyPass : public FunctionPass {
static const int ID; // Pass identifcation, replacement for typeid
CFGSimplifyPass() : FunctionPass((intptr_t)&ID) {}
virtual bool runOnFunction(Function &F);
};
const int CFGSimplifyPass::ID = 0;
RegisterPass<CFGSimplifyPass> X("simplifycfg", "Simplify the CFG");
}
// Public interface to the CFGSimplification pass
FunctionPass *llvm::createCFGSimplificationPass() {
return new CFGSimplifyPass();
}
static bool MarkAliveBlocks(BasicBlock *BB,
SmallPtrSet<BasicBlock*, 16> &Reachable) {
std::vector<BasicBlock*> Worklist;
Worklist.push_back(BB);
bool Changed = false;
while (!Worklist.empty()) {
BB = Worklist.back();
Worklist.pop_back();
if (!Reachable.insert(BB))
continue;
// Do a quick scan of the basic block, turning any obviously unreachable
// instructions into LLVM unreachable insts. The instruction combining pass
// canonnicalizes unreachable insts into stores to null or undef.
for (BasicBlock::iterator BBI = BB->begin(), E = BB->end(); BBI != E; ++BBI)
if (StoreInst *SI = dyn_cast<StoreInst>(BBI))
if (isa<ConstantPointerNull>(SI->getOperand(1)) ||
isa<UndefValue>(SI->getOperand(1))) {
// Loop over all of the successors, removing BB's entry from any PHI
// nodes.
for (succ_iterator I = succ_begin(BB), SE = succ_end(BB); I != SE;++I)
(*I)->removePredecessor(BB);
new UnreachableInst(SI);
// All instructions after this are dead.
while (BBI != E) {
if (!BBI->use_empty())
BBI->replaceAllUsesWith(UndefValue::get(BBI->getType()));
BB->getInstList().erase(BBI++);
}
break;
}
Changed |= ConstantFoldTerminator(BB);
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI != SE; ++SI)
Worklist.push_back(*SI);
}
return Changed;
}
// It is possible that we may require multiple passes over the code to fully
// simplify the CFG.
//
bool CFGSimplifyPass::runOnFunction(Function &F) {
SmallPtrSet<BasicBlock*, 16> Reachable;
bool Changed = MarkAliveBlocks(F.begin(), Reachable);
// If there are unreachable blocks in the CFG...
if (Reachable.size() != F.size()) {
assert(Reachable.size() < F.size());
NumSimpl += F.size()-Reachable.size();
// Loop over all of the basic blocks that are not reachable, dropping all of
// their internal references...
for (Function::iterator BB = ++F.begin(), E = F.end(); BB != E; ++BB)
if (!Reachable.count(BB)) {
for (succ_iterator SI = succ_begin(BB), SE = succ_end(BB); SI!=SE; ++SI)
if (Reachable.count(*SI))
(*SI)->removePredecessor(BB);
BB->dropAllReferences();
}
for (Function::iterator I = ++F.begin(); I != F.end();)
if (!Reachable.count(I))
I = F.getBasicBlockList().erase(I);
else
++I;
Changed = true;
}
bool LocalChange = true;
while (LocalChange) {
LocalChange = false;
// Loop over all of the basic blocks (except the first one) and remove them
// if they are unneeded...
//
for (Function::iterator BBIt = ++F.begin(); BBIt != F.end(); ) {
if (SimplifyCFG(BBIt++)) {
LocalChange = true;
++NumSimpl;
}
}
Changed |= LocalChange;
}
return Changed;
}
|
