xref: /openbsd-src/gnu/llvm/llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp (revision d415bd752c734aee168c4ee86ff32e8cc249eb16)
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 
32 using namespace llvm;
33 
34 /// Replaces BB Terminator with one that only contains Chunk BBs
replaceBranchTerminator(BasicBlock & BB,const DenseSet<BasicBlock * > & BBsToDelete)35 static 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)) {
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   bool IsBranch = isa<BranchInst>(Term);
49   if (InvokeInst *Invoke = dyn_cast<InvokeInst>(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(LP->getParent()->users(), [Invoke](User *U) {
54           return U != Invoke && isa<InvokeInst>(U);
55         })) {
56       LP->replaceAllUsesWith(getDefaultValue(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>(Term))
70     Address = IndBI->getAddress();
71 
72   Term->replaceAllUsesWith(getDefaultValue(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(BB.getContext(),
79                        FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy),
80                        &BB);
81     return;
82   }
83 
84   if (IsBranch)
85     BranchInst::Create(ChunkSuccessors[0], &BB);
86 
87   if (Address) {
88     auto *NewIndBI =
89         IndirectBrInst::Create(Address, ChunkSuccessors.size(), &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)
98 static void
removeUninterestingBBsFromSwitch(SwitchInst & SwInst,const DenseSet<BasicBlock * > & BBsToDelete)99 removeUninterestingBBsFromSwitch(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(Case->getCaseSuccessor())) {
104       SwInst.removeCase(Case);
105       --I;
106       --E;
107     }
108   }
109 
110   if (BBsToDelete.count(SwInst.getDefaultDest())) {
111     if (SwInst.getNumCases() == 0) {
112       auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
113       Value *RetValue =
114           FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy);
115       ReturnInst::Create(SwInst.getContext(), RetValue, 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(SuccPHI.getIncomingValueForBlock(SwInst.getParent()),
128                           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.
extractBasicBlocksFromModule(Oracle & O,ReducerWorkItem & WorkItem)135 static 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(&Entry, 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(&BB);
164     }
165 
166     // Replace terminators that reference out-of-chunk BBs
167     for (BasicBlock &BB : F) {
168       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
169         removeUninterestingBBsFromSwitch(*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 
reduceBasicBlocksDeltaPass(TestRunner & Test)182 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
183   runDeltaPass(Test, extractBasicBlocksFromModule, "Reducing Basic Blocks");
184 }
185 
removeUnreachableBasicBlocksFromModule(Oracle & O,ReducerWorkItem & WorkItem)186 static 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(&F, Reachable))
197       (void)BB;
198 
199     if (Reachable.size() != F.size() && !O.shouldKeep()) {
200       for (BasicBlock &BB : F) {
201         if (!Reachable.count(&BB))
202           DeadBlocks.push_back(&BB);
203       }
204 
205       // Delete the dead blocks.
206       DeleteDeadBlocks(DeadBlocks, nullptr, /*KeepOneInputPHIs*/ false);
207       DeadBlocks.clear();
208     }
209 
210     Reachable.clear();
211   }
212 }
213 
reduceUnreachableBasicBlocksDeltaPass(TestRunner & Test)214 void llvm::reduceUnreachableBasicBlocksDeltaPass(TestRunner &Test) {
215   runDeltaPass(Test, removeUnreachableBasicBlocksFromModule,
216                "Removing Unreachable Basic Blocks");
217 }
218