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 "llvm/ADT/DenseSet.h"
16 #include "llvm/IR/BasicBlock.h"
17 #include "llvm/IR/Constants.h"
18 #include "llvm/IR/Instruction.h"
19 #include "llvm/IR/Instructions.h"
20 #include "llvm/IR/LLVMContext.h"
21 #include "llvm/IR/Value.h"
22 #include "llvm/Support/Casting.h"
23 #include "llvm/Support/raw_ostream.h"
24 #include <vector>
25 
26 using namespace llvm;
27 
28 /// Replaces BB Terminator with one that only contains Chunk BBs
29 static void replaceBranchTerminator(BasicBlock &BB,
30                                     const DenseSet<BasicBlock *> &BBsToKeep) {
31   auto *Term = BB.getTerminator();
32   std::vector<BasicBlock *> ChunkSuccessors;
33   for (auto *Succ : successors(&BB))
34     if (BBsToKeep.count(Succ))
35       ChunkSuccessors.push_back(Succ);
36 
37   // BB only references Chunk BBs
38   if (ChunkSuccessors.size() == Term->getNumSuccessors())
39     return;
40 
41   bool IsBranch = isa<BranchInst>(Term) || isa<InvokeInst>(Term);
42   Value *Address = nullptr;
43   if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
44     Address = IndBI->getAddress();
45 
46   Term->replaceAllUsesWith(UndefValue::get(Term->getType()));
47   Term->eraseFromParent();
48 
49   if (ChunkSuccessors.empty()) {
50     // Scan forward in BB list to try find a block that is kept.
51     Function &F = *BB.getParent();
52     Function::iterator FI = BB.getIterator();
53     FI++;
54     while (FI != F.end()) {
55       auto &FIB = *FI;
56       if (BBsToKeep.count(&FIB) && !isa<PHINode>(FIB.begin())) {
57         BranchInst::Create(&FIB, &BB);
58         return;
59       }
60       FI++;
61     }
62     // If that fails then resort to replacing with a ret.
63     auto *FnRetTy = BB.getParent()->getReturnType();
64     ReturnInst::Create(BB.getContext(),
65                        FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
66                        &BB);
67     return;
68   }
69 
70   if (IsBranch)
71     BranchInst::Create(ChunkSuccessors[0], &BB);
72 
73   if (Address) {
74     auto *NewIndBI =
75         IndirectBrInst::Create(Address, ChunkSuccessors.size(), &BB);
76     for (auto *Dest : ChunkSuccessors)
77       NewIndBI->addDestination(Dest);
78   }
79 }
80 
81 /// Removes uninteresting BBs from switch, if the default case ends up being
82 /// uninteresting, the switch is replaced with a void return (since it has to be
83 /// replace with something)
84 static void
85 removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
86                                  const DenseSet<BasicBlock *> &BBsToKeep) {
87   if (!BBsToKeep.count(SwInst.getDefaultDest())) {
88     auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
89     ReturnInst::Create(SwInst.getContext(),
90                        FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
91                        SwInst.getParent());
92     SwInst.eraseFromParent();
93   } else
94     for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
95       auto Case = SwInst.case_begin() + I;
96       if (!BBsToKeep.count(Case->getCaseSuccessor())) {
97         SwInst.removeCase(Case);
98         --I;
99         --E;
100       }
101     }
102 }
103 
104 /// Removes out-of-chunk arguments from functions, and modifies their calls
105 /// accordingly. It also removes allocations of out-of-chunk arguments.
106 static void extractBasicBlocksFromModule(Oracle &O, Module &Program) {
107   DenseSet<BasicBlock *> BBsToKeep;
108 
109   SmallVector<BasicBlock *> BBsToDelete;
110   for (auto &F : Program) {
111     for (auto &BB : F) {
112       if (O.shouldKeep())
113         BBsToKeep.insert(&BB);
114       else {
115         BBsToDelete.push_back(&BB);
116         // Remove out-of-chunk BB from successor phi nodes
117         for (auto *Succ : successors(&BB))
118           Succ->removePredecessor(&BB);
119       }
120     }
121   }
122 
123   // Replace terminators that reference out-of-chunk BBs
124   for (auto &F : Program)
125     for (auto &BB : F) {
126       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
127         removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
128       else
129         replaceBranchTerminator(BB, BBsToKeep);
130     }
131 
132   // Replace out-of-chunk switch uses
133   for (auto &BB : BBsToDelete) {
134     // Instructions might be referenced in other BBs
135     for (auto &I : *BB)
136       I.replaceAllUsesWith(UndefValue::get(I.getType()));
137     if (BB->getParent()->size() == 1) {
138       // this is the last basic block of the function, thus we must also make
139       // sure to remove comdat and set linkage to external
140       auto F = BB->getParent();
141       F->deleteBody();
142       F->setComdat(nullptr);
143     } else {
144       BB->eraseFromParent();
145     }
146   }
147 }
148 
149 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
150   outs() << "*** Reducing Basic Blocks...\n";
151   runDeltaPass(Test, extractBasicBlocksFromModule);
152 }
153