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                                     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 removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
70                                              std::set<BasicBlock *> BBsToKeep) {
71   if (!BBsToKeep.count(SwInst.getDefaultDest())) {
72     auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
73     ReturnInst::Create(SwInst.getContext(),
74                        FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
75                        SwInst.getParent());
76     SwInst.eraseFromParent();
77   } else
78     for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
79       auto Case = SwInst.case_begin() + I;
80       if (!BBsToKeep.count(Case->getCaseSuccessor())) {
81         SwInst.removeCase(Case);
82         --I;
83         --E;
84       }
85     }
86 }
87 
88 /// Removes out-of-chunk arguments from functions, and modifies their calls
89 /// accordingly. It also removes allocations of out-of-chunk arguments.
90 static void extractBasicBlocksFromModule(Oracle &O, Module &Program) {
91   std::set<BasicBlock *> BBsToKeep;
92 
93   for (auto &F : Program)
94     for (auto &BB : F)
95       if (O.shouldKeep())
96         BBsToKeep.insert(&BB);
97 
98   std::vector<BasicBlock *> BBsToDelete;
99   for (auto &F : Program)
100     for (auto &BB : F) {
101       if (!BBsToKeep.count(&BB)) {
102         BBsToDelete.push_back(&BB);
103         // Remove out-of-chunk BB from successor phi nodes
104         for (auto *Succ : successors(&BB))
105           Succ->removePredecessor(&BB);
106       }
107     }
108 
109   // Replace terminators that reference out-of-chunk BBs
110   for (auto &F : Program)
111     for (auto &BB : F) {
112       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
113         removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
114       else
115         replaceBranchTerminator(BB, BBsToKeep);
116     }
117 
118   // Replace out-of-chunk switch uses
119   for (auto &BB : BBsToDelete) {
120     // Instructions might be referenced in other BBs
121     for (auto &I : *BB)
122       I.replaceAllUsesWith(UndefValue::get(I.getType()));
123     BB->eraseFromParent();
124   }
125 }
126 
127 /// Counts the amount of basic blocks and prints their name & respective index
128 static int countBasicBlocks(Module &Program) {
129   // TODO: Silence index with --quiet flag
130   outs() << "----------------------------\n";
131   int BBCount = 0;
132   for (auto &F : Program)
133     for (auto &BB : F) {
134       if (BB.hasName())
135         outs() << "\t" << ++BBCount << ": " << BB.getName() << "\n";
136       else
137         outs() << "\t" << ++BBCount << ": Unnamed\n";
138     }
139 
140   return BBCount;
141 }
142 
143 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
144   outs() << "*** Reducing Basic Blocks...\n";
145   int BBCount = countBasicBlocks(Test.getProgram());
146   runDeltaPass(Test, BBCount, extractBasicBlocksFromModule);
147 }
148