1 //===- ReduceArguments.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 Arguments from defined functions.
11 //
12 //===----------------------------------------------------------------------===//
13 
14 #include "ReduceBasicBlocks.h"
15 #include "llvm/IR/BasicBlock.h"
16 #include "llvm/IR/Instruction.h"
17 #include "llvm/IR/Instructions.h"
18 #include "llvm/IR/LLVMContext.h"
19 #include "llvm/IR/Value.h"
20 #include "llvm/Support/Casting.h"
21 #include "llvm/Support/raw_ostream.h"
22 #include <vector>
23 
24 using namespace llvm;
25 
26 /// Replaces BB Terminator with one that only contains Chunk BBs
27 static void replaceBranchTerminator(BasicBlock &BB,
28                                     const std::set<BasicBlock *> &BBsToKeep) {
29   auto *Term = BB.getTerminator();
30   std::vector<BasicBlock *> ChunkSucessors;
31   for (auto *Succ : successors(&BB))
32     if (BBsToKeep.count(Succ))
33       ChunkSucessors.push_back(Succ);
34 
35   // BB only references Chunk BBs
36   if (ChunkSucessors.size() == Term->getNumSuccessors())
37     return;
38 
39   bool IsBranch = isa<BranchInst>(Term) || isa<InvokeInst>(Term);
40   Value *Address = nullptr;
41   if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
42     Address = IndBI->getAddress();
43 
44   Term->replaceAllUsesWith(UndefValue::get(Term->getType()));
45   Term->eraseFromParent();
46 
47   if (ChunkSucessors.empty()) {
48     auto *FnRetTy = BB.getParent()->getReturnType();
49     ReturnInst::Create(BB.getContext(),
50                        FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
51                        &BB);
52     return;
53   }
54 
55   if (IsBranch)
56     BranchInst::Create(ChunkSucessors[0], &BB);
57 
58   if (Address) {
59     auto *NewIndBI =
60         IndirectBrInst::Create(Address, ChunkSucessors.size(), &BB);
61     for (auto *Dest : ChunkSucessors)
62       NewIndBI->addDestination(Dest);
63   }
64 }
65 
66 /// Removes uninteresting BBs from switch, if the default case ends up being
67 /// uninteresting, the switch is replaced with a void return (since it has to be
68 /// replace with something)
69 static void
70 removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
71                                  const std::set<BasicBlock *> &BBsToKeep) {
72   if (!BBsToKeep.count(SwInst.getDefaultDest())) {
73     auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
74     ReturnInst::Create(SwInst.getContext(),
75                        FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
76                        SwInst.getParent());
77     SwInst.eraseFromParent();
78   } else
79     for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
80       auto Case = SwInst.case_begin() + I;
81       if (!BBsToKeep.count(Case->getCaseSuccessor())) {
82         SwInst.removeCase(Case);
83         --I;
84         --E;
85       }
86     }
87 }
88 
89 /// Removes out-of-chunk arguments from functions, and modifies their calls
90 /// accordingly. It also removes allocations of out-of-chunk arguments.
91 static void extractBasicBlocksFromModule(Oracle &O, Module &Program) {
92   std::vector<BasicBlock *> InitBBsToKeep;
93 
94   for (auto &F : Program)
95     for (auto &BB : F)
96       if (O.shouldKeep())
97         InitBBsToKeep.push_back(&BB);
98 
99   // We create a vector first, then convert it to a set, so that we don't have
100   // to pay the cost of rebalancing the set frequently if the order we insert
101   // the elements doesn't match the order they should appear inside the set.
102   std::set<BasicBlock *> BBsToKeep(InitBBsToKeep.begin(), InitBBsToKeep.end());
103 
104   std::vector<BasicBlock *> BBsToDelete;
105   for (auto &F : Program)
106     for (auto &BB : F) {
107       if (!BBsToKeep.count(&BB)) {
108         BBsToDelete.push_back(&BB);
109         // Remove out-of-chunk BB from successor phi nodes
110         for (auto *Succ : successors(&BB))
111           Succ->removePredecessor(&BB);
112       }
113     }
114 
115   // Replace terminators that reference out-of-chunk BBs
116   for (auto &F : Program)
117     for (auto &BB : F) {
118       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
119         removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
120       else
121         replaceBranchTerminator(BB, BBsToKeep);
122     }
123 
124   // Replace out-of-chunk switch uses
125   for (auto &BB : BBsToDelete) {
126     // Instructions might be referenced in other BBs
127     for (auto &I : *BB)
128       I.replaceAllUsesWith(UndefValue::get(I.getType()));
129     BB->eraseFromParent();
130   }
131 }
132 
133 /// Counts the amount of basic blocks and prints their name & respective index
134 static int countBasicBlocks(Module &Program) {
135   // TODO: Silence index with --quiet flag
136   outs() << "----------------------------\n";
137   int BBCount = 0;
138   for (auto &F : Program)
139     for (auto &BB : F) {
140       if (BB.hasName())
141         outs() << "\t" << ++BBCount << ": " << BB.getName() << "\n";
142       else
143         outs() << "\t" << ++BBCount << ": Unnamed\n";
144     }
145 
146   return BBCount;
147 }
148 
149 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
150   outs() << "*** Reducing Basic Blocks...\n";
151   int BBCount = countBasicBlocks(Test.getProgram());
152   runDeltaPass(Test, BBCount, extractBasicBlocksFromModule);
153 }
154