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
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
|
//===- ReduceBasicBlocks.cpp - Specialized Delta Pass ---------------------===//
//
// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
// See https://llvm.org/LICENSE.txt for license information.
// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
//
//===----------------------------------------------------------------------===//
//
// This file implements a function which calls the Generic Delta pass in order
// to reduce uninteresting BasicBlocks from defined functions.
//
//===----------------------------------------------------------------------===//
#include "ReduceBasicBlocks.h"
#include "Utils.h"
#include "llvm/ADT/DenseSet.h"
#include "llvm/IR/BasicBlock.h"
#include "llvm/IR/Constants.h"
#include "llvm/IR/Instruction.h"
#include "llvm/IR/Instructions.h"
#include "llvm/IR/LLVMContext.h"
#include "llvm/IR/Value.h"
#include "llvm/Support/Casting.h"
#include "llvm/Support/raw_ostream.h"
#include "llvm/Transforms/Utils/BasicBlockUtils.h"
#include "llvm/Transforms/Utils/Local.h"
#include <vector>
#define DEBUG_TYPE "llvm-reduce"
using namespace llvm;
/// Replaces BB Terminator with one that only contains Chunk BBs
static void replaceBranchTerminator(BasicBlock &BB,
const DenseSet<BasicBlock *> &BBsToDelete) {
auto *Term = BB.getTerminator();
std::vector<BasicBlock *> ChunkSuccessors;
for (auto *Succ : successors(&BB)) {
if (!BBsToDelete.count(Succ))
ChunkSuccessors.push_back(Succ);
}
// BB only references Chunk BBs
if (ChunkSuccessors.size() == Term->getNumSuccessors())
return;
bool IsBranch = isa<BranchInst>(Term);
if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Term)) {
LandingPadInst *LP = Invoke->getLandingPadInst();
// Remove landingpad instruction if the containing block isn't used by other
// invokes.
if (none_of(LP->getParent()->users(), [Invoke](User *U) {
return U != Invoke && isa<InvokeInst>(U);
})) {
LP->replaceAllUsesWith(getDefaultValue(LP->getType()));
LP->eraseFromParent();
} else if (!ChunkSuccessors.empty() &&
ChunkSuccessors[0] == LP->getParent()) {
// If the selected successor is the landing pad, clear the chunk
// successors to avoid creating a regular branch to the landing pad which
// would result in invalid IR.
ChunkSuccessors.clear();
}
IsBranch = true;
}
Value *Address = nullptr;
if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
Address = IndBI->getAddress();
Term->replaceAllUsesWith(getDefaultValue(Term->getType()));
Term->eraseFromParent();
if (ChunkSuccessors.empty()) {
// If that fails then resort to replacing with a ret.
auto *FnRetTy = BB.getParent()->getReturnType();
ReturnInst::Create(BB.getContext(),
FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy),
&BB);
return;
}
if (IsBranch)
BranchInst::Create(ChunkSuccessors[0], &BB);
if (Address) {
auto *NewIndBI =
IndirectBrInst::Create(Address, ChunkSuccessors.size(), &BB);
for (auto *Dest : ChunkSuccessors)
NewIndBI->addDestination(Dest);
}
}
/// Removes uninteresting BBs from switch, if the default case ends up being
/// uninteresting, the switch is replaced with a void return (since it has to be
/// replace with something)
static void
removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
const DenseSet<BasicBlock *> &BBsToDelete) {
for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
auto Case = SwInst.case_begin() + I;
if (BBsToDelete.count(Case->getCaseSuccessor())) {
SwInst.removeCase(Case);
--I;
--E;
}
}
if (BBsToDelete.count(SwInst.getDefaultDest())) {
if (SwInst.getNumCases() == 0) {
auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
Value *RetValue =
FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy);
ReturnInst::Create(SwInst.getContext(), RetValue, SwInst.getParent());
SwInst.eraseFromParent();
return;
}
// Replace the default dest with one of the other cases
auto Case = SwInst.case_begin();
BasicBlock *NewDefault = Case->getCaseSuccessor();
SwInst.setDefaultDest(NewDefault);
for (PHINode &SuccPHI : NewDefault->phis()) {
SuccPHI.addIncoming(SuccPHI.getIncomingValueForBlock(SwInst.getParent()),
SwInst.getParent());
}
}
}
/// Removes out-of-chunk arguments from functions, and modifies their calls
/// accordingly. It also removes allocations of out-of-chunk arguments.
static void extractBasicBlocksFromModule(Oracle &O, ReducerWorkItem &WorkItem) {
DenseSet<BasicBlock *> BBsToDelete;
df_iterator_default_set<BasicBlock *> Reachable;
for (auto &F : WorkItem.getModule()) {
if (F.empty())
continue;
BasicBlock &Entry = F.getEntryBlock();
for (auto *BB : depth_first_ext(&Entry, Reachable))
(void)BB;
// Skip any function with unreachable blocks. It's somewhat difficult to
// avoid producing invalid IR without deleting them.
//
// We also do not want to unconditionally delete them, as doing so would
// break the invariant of changing the number of chunks during counting.
const bool HasUnreachableBlocks = Reachable.size() != F.size();
Reachable.clear();
if (HasUnreachableBlocks) {
LLVM_DEBUG(dbgs() << "Skipping function with unreachable blocks\n");
continue;
}
for (BasicBlock &BB : F) {
if (&BB != &Entry && !O.shouldKeep())
BBsToDelete.insert(&BB);
}
// Replace terminators that reference out-of-chunk BBs
for (BasicBlock &BB : F) {
if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
removeUninterestingBBsFromSwitch(*SwInst, BBsToDelete);
else
replaceBranchTerminator(BB, BBsToDelete);
}
// Cleanup any blocks that are now dead after eliminating this set. This
// will likely be larger than the number of blocks the oracle told us to
// delete.
EliminateUnreachableBlocks(F);
BBsToDelete.clear();
}
}
void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
runDeltaPass(Test, extractBasicBlocksFromModule, "Reducing Basic Blocks");
}
static void removeUnreachableBasicBlocksFromModule(Oracle &O,
ReducerWorkItem &WorkItem) {
std::vector<BasicBlock *> DeadBlocks;
df_iterator_default_set<BasicBlock *> Reachable;
for (Function &F : WorkItem.getModule()) {
if (F.empty())
continue;
// Mark all reachable blocks.
for (BasicBlock *BB : depth_first_ext(&F, Reachable))
(void)BB;
if (Reachable.size() != F.size() && !O.shouldKeep()) {
for (BasicBlock &BB : F) {
if (!Reachable.count(&BB))
DeadBlocks.push_back(&BB);
}
// Delete the dead blocks.
DeleteDeadBlocks(DeadBlocks, nullptr, /*KeepOneInputPHIs*/ false);
DeadBlocks.clear();
}
Reachable.clear();
}
}
void llvm::reduceUnreachableBasicBlocksDeltaPass(TestRunner &Test) {
runDeltaPass(Test, removeUnreachableBasicBlocksFromModule,
"Removing Unreachable Basic Blocks");
}
|
