Debian Codegraph @

llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

raw
1 //===- ReduceBasicBlocks.cpp - Specialized Delta Pass ---------------------===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // This file implements a function which calls the Generic Delta pass in order
10 // to reduce uninteresting BasicBlocks from defined functions.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "ReduceBasicBlocks.h"
15 #include "Utils.h"
16 #include "llvm/IR/BasicBlock.h"
17 #include "llvm/IR/Instruction.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/LLVMContext.h"
20 #include "llvm/IR/Value.h"
21 #include "llvm/Support/Casting.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include "llvm/Transforms/Utils/BasicBlockUtils.h"
24 #include "llvm/Transforms/Utils/Cloning.h"
25 #include "llvm/Transforms/Utils/Local.h"
26 #include <vector>
27
28 #define DEBUG_TYPE "llvm-reduce"
29
30 using namespace llvm;
31
32 using BlockSet = SetVector<BasicBlock *>;
33
34 /// Replaces BB Terminator with one that only contains Chunk BBs
35 static void replaceBranchTerminator(BasicBlock &BB,
36 const BlockSet &BBsToDelete) {
37 auto *Term = BB.getTerminator();
38 std::vector<BasicBlock *> ChunkSuccessors;
39 for (auto *Succ : successors(&BB)) {
40 if (!BBsToDelete.count(Succ))
41 ChunkSuccessors.push_back(Succ);
42 }
43
44 // BB only references Chunk BBs
45 if (ChunkSuccessors.size() == Term->getNumSuccessors())
46 return;
47
48 // TODO: Handle these without failing verifier.
49 if (isa<CatchSwitchInst>(Term))
50 return;
51
52 bool IsBranch = isa<BranchInst>(Term) || isa<CallBrInst>(Term);
53 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Term)) {
54 BasicBlock *UnwindDest = Invoke->getUnwindDest();
55 BasicBlock::iterator LP = UnwindDest->getFirstNonPHIIt();
56
57 // Remove landingpad instruction if the containing block isn't used by other
58 // invokes.
59
60 // TODO: Handle catchswitch, catchpad, catchret, and cleanupret
61 if (isa<LandingPadInst>(LP) &&
62 none_of(UnwindDest->users(), [Invoke](User *U) {
63 return U != Invoke && isa<InvokeInst>(U);
64 })) {
65 LP->replaceAllUsesWith(getDefaultValue(LP->getType()));
66 LP->eraseFromParent();
67 } else if (!ChunkSuccessors.empty() &&
68 ChunkSuccessors[0] == LP->getParent()) {
69 // If the selected successor is the landing pad, clear the chunk
70 // successors to avoid creating a regular branch to the landing pad which
71 // would result in invalid IR.
72 ChunkSuccessors.clear();
73 }
74 IsBranch = true;
75 }
76
77 Value *Address = nullptr;
78 if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
79 Address = IndBI->getAddress();
80
81 Term->replaceAllUsesWith(getDefaultValue(Term->getType()));
82 Term->eraseFromParent();
83
84 if (ChunkSuccessors.empty()) {
85 // If that fails then resort to replacing with a ret.
86 auto *FnRetTy = BB.getParent()->getReturnType();
87 ReturnInst::Create(BB.getContext(),
88 FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy),
89 &BB);
90 return;
91 }
92
93 if (IsBranch)
94 BranchInst::Create(ChunkSuccessors[0], &BB);
95
96 if (Address) {
97 auto *NewIndBI =
98 IndirectBrInst::Create(Address, ChunkSuccessors.size(), &BB);
99 for (auto *Dest : ChunkSuccessors)
100 NewIndBI->addDestination(Dest);
101 }
102 }
103
104 /// Removes uninteresting BBs from switch, if the default case ends up being
105 /// uninteresting, the switch is replaced with a void return (since it has to be
106 /// replace with something)
107 static void removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
108 const BlockSet &BBsToDelete) {
109 for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
110 auto Case = SwInst.case_begin() + I;
111 if (BBsToDelete.count(Case->getCaseSuccessor())) {
112 SwInst.removeCase(Case);
113 --I;
114 --E;
115 }
116 }
117
118 if (BBsToDelete.count(SwInst.getDefaultDest())) {
119 if (SwInst.getNumCases() == 0) {
120 auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
121 Value *RetValue =
122 FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy);
123 ReturnInst::Create(SwInst.getContext(), RetValue, SwInst.getParent());
124 SwInst.eraseFromParent();
125 return;
126 }
127
128 // Replace the default dest with one of the other cases
129 auto Case = SwInst.case_begin();
130
131 BasicBlock *NewDefault = Case->getCaseSuccessor();
132 SwInst.setDefaultDest(NewDefault);
133
134 for (PHINode &SuccPHI : NewDefault->phis()) {
135 SuccPHI.addIncoming(SuccPHI.getIncomingValueForBlock(SwInst.getParent()),
136 SwInst.getParent());
137 }
138 }
139 }
140
141 /// Removes out-of-chunk arguments from functions, and modifies their calls
142 /// accordingly. It also removes allocations of out-of-chunk arguments.
143 void llvm::reduceBasicBlocksDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) {
144 BlockSet BBsToDelete;
145
146 df_iterator_default_set<BasicBlock *> Reachable;
147
148 for (auto &F : WorkItem.getModule()) {
149 if (F.empty())
150 continue;
151
152 BasicBlock &Entry = F.getEntryBlock();
153 for (auto *BB : depth_first_ext(&Entry, Reachable))
154 (void)BB;
155
156 // Skip any function with unreachable blocks. It's somewhat difficult to
157 // avoid producing invalid IR without deleting them.
158 //
159 // We also do not want to unconditionally delete them, as doing so would
160 // break the invariant of changing the number of chunks during counting.
161
162 const bool HasUnreachableBlocks = Reachable.size() != F.size();
163 Reachable.clear();
164
165 if (HasUnreachableBlocks) {
166 LLVM_DEBUG(dbgs() << "Skipping function with unreachable blocks\n");
167 continue;
168 }
169
170 for (BasicBlock &BB : F) {
171 if (&BB != &Entry && !O.shouldKeep())
172 BBsToDelete.insert(&BB);
173 }
174
175 // Replace terminators that reference out-of-chunk BBs
176 for (BasicBlock &BB : F) {
177 if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
178 removeUninterestingBBsFromSwitch(*SwInst, BBsToDelete);
179 else
180 replaceBranchTerminator(BB, BBsToDelete);
181 }
182
183 // Cleanup any blocks that are now dead after eliminating this set. This
184 // will likely be larger than the number of blocks the oracle told us to
185 // delete.
186 simpleSimplifyCFG(F, BBsToDelete.getArrayRef());
187
188 BBsToDelete.clear();
189 }
190 }
191
192 void llvm::reduceUnreachableBasicBlocksDeltaPass(Oracle &O,
193 ReducerWorkItem &WorkItem) {
194 std::vector<BasicBlock *> DeadBlocks;
195 df_iterator_default_set<BasicBlock *> Reachable;
196
197 for (Function &F : WorkItem.getModule()) {
198 if (F.empty())
199 continue;
200
201 // Mark all reachable blocks.
202 for (BasicBlock *BB : depth_first_ext(&F, Reachable))
203 (void)BB;
204
205 if (Reachable.size() != F.size() && !O.shouldKeep()) {
206 for (BasicBlock &BB : F) {
207 if (!Reachable.count(&BB))
208 DeadBlocks.push_back(&BB);
209 }
210
211 // Delete the dead blocks.
212 DeleteDeadBlocks(DeadBlocks, nullptr, /*KeepOneInputPHIs*/ false);
213 DeadBlocks.clear();
214 }
215
216 Reachable.clear();
217 }
218 }