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