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
30using namespace llvm;
31
32using BlockSet = SetVector<BasicBlock *>;
33
34/// Replaces BB Terminator with one that only contains Chunk BBs
35static void replaceBranchTerminator(BasicBlock &BB,
36 const BlockSet &BBsToDelete) {
37 auto *Term = BB.getTerminator();
38 std::vector<BasicBlock *> ChunkSuccessors;
39 for (auto *Succ : successors(BB: &BB)) {
40 if (!BBsToDelete.count(key: Succ))
41 ChunkSuccessors.push_back(x: 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>(Val: Term))
50 return;
51
52 bool IsBranch = isa<BranchInst>(Val: Term);
53 if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Val: 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>(Val: LP) &&
62 none_of(Range: UnwindDest->users(), P: [Invoke](User *U) {
63 return U != Invoke && isa<InvokeInst>(Val: U);
64 })) {
65 LP->replaceAllUsesWith(V: getDefaultValue(T: 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>(Val: Term))
79 Address = IndBI->getAddress();
80
81 Term->replaceAllUsesWith(V: getDefaultValue(T: 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(C&: BB.getContext(),
88 retVal: FnRetTy->isVoidTy() ? nullptr : getDefaultValue(T: FnRetTy),
89 InsertBefore: &BB);
90 return;
91 }
92
93 if (IsBranch)
94 BranchInst::Create(IfTrue: ChunkSuccessors[0], InsertBefore: &BB);
95
96 if (Address) {
97 auto *NewIndBI =
98 IndirectBrInst::Create(Address, NumDests: ChunkSuccessors.size(), InsertBefore: &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)
107static 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(key: Case->getCaseSuccessor())) {
112 SwInst.removeCase(I: Case);
113 --I;
114 --E;
115 }
116 }
117
118 if (BBsToDelete.count(key: SwInst.getDefaultDest())) {
119 if (SwInst.getNumCases() == 0) {
120 auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
121 Value *RetValue =
122 FnRetTy->isVoidTy() ? nullptr : getDefaultValue(T: FnRetTy);
123 ReturnInst::Create(C&: SwInst.getContext(), retVal: RetValue, InsertBefore: 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(V: SuccPHI.getIncomingValueForBlock(BB: SwInst.getParent()),
136 BB: 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.
143void 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(G: &Entry, S&: 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(X: &BB);
173 }
174
175 // Replace terminators that reference out-of-chunk BBs
176 for (BasicBlock &BB : F) {
177 if (auto *SwInst = dyn_cast<SwitchInst>(Val: BB.getTerminator()))
178 removeUninterestingBBsFromSwitch(SwInst&: *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, BBs: BBsToDelete.getArrayRef());
187
188 BBsToDelete.clear();
189 }
190}
191
192void 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(G: &F, S&: Reachable))
203 (void)BB;
204
205 if (Reachable.size() != F.size() && !O.shouldKeep()) {
206 for (BasicBlock &BB : F) {
207 if (!Reachable.count(Ptr: &BB))
208 DeadBlocks.push_back(x: &BB);
209 }
210
211 // Delete the dead blocks.
212 DeleteDeadBlocks(BBs: DeadBlocks, DTU: nullptr, /*KeepOneInputPHIs*/ false);
213 DeadBlocks.clear();
214 }
215
216 Reachable.clear();
217 }
218}
219