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);
40   Value *Address = nullptr;
41   if (auto IndBI = dyn_cast<IndirectBrInst>(Term))
42     Address = IndBI->getAddress();
43 
44   Term->eraseFromParent();
45 
46   if (ChunkSucessors.empty()) {
47     ReturnInst::Create(BB.getContext(), nullptr, &BB);
48     return;
49   }
50 
51   if (IsBranch)
52     BranchInst::Create(ChunkSucessors[0], &BB);
53 
54   if (Address) {
55     auto NewIndBI =
56         IndirectBrInst::Create(Address, ChunkSucessors.size(), &BB);
57     for (auto Dest : ChunkSucessors)
58       NewIndBI->addDestination(Dest);
59   }
60 }
61 
62 /// Removes uninteresting BBs from switch, if the default case ends up being
63 /// uninteresting, the switch is replaced with a void return (since it has to be
64 /// replace with something)
65 static void removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
66                                              std::set<BasicBlock *> BBsToKeep) {
67   if (!BBsToKeep.count(SwInst.getDefaultDest())) {
68     ReturnInst::Create(SwInst.getContext(), nullptr, SwInst.getParent());
69     SwInst.eraseFromParent();
70   } else
71     for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
72       auto Case = SwInst.case_begin() + I;
73       if (!BBsToKeep.count(Case->getCaseSuccessor())) {
74         SwInst.removeCase(Case);
75         --I;
76         --E;
77       }
78     }
79 }
80 
81 /// Removes out-of-chunk arguments from functions, and modifies their calls
82 /// accordingly. It also removes allocations of out-of-chunk arguments.
83 static void extractBasicBlocksFromModule(std::vector<Chunk> ChunksToKeep,
84                                          Module *Program) {
85   Oracle O(ChunksToKeep);
86 
87   std::set<BasicBlock *> BBsToKeep;
88 
89   for (auto &F : *Program)
90     for (auto &BB : F)
91       if (O.shouldKeep())
92         BBsToKeep.insert(&BB);
93 
94   std::vector<BasicBlock *> BBsToDelete;
95   for (auto &F : *Program)
96     for (auto &BB : F) {
97       if (!BBsToKeep.count(&BB)) {
98         BBsToDelete.push_back(&BB);
99         // Remove out-of-chunk BB from successor phi nodes
100         for (auto *Succ : successors(&BB))
101           Succ->removePredecessor(&BB);
102       }
103     }
104 
105   // Replace terminators that reference out-of-chunk BBs
106   for (auto &F : *Program)
107     for (auto &BB : F) {
108       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
109         removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
110       else
111         replaceBranchTerminator(BB, BBsToKeep);
112     }
113 
114   // Replace out-of-chunk switch uses
115   for (auto &BB : BBsToDelete) {
116     // Instructions might be referenced in other BBs
117     for (auto &I : *BB)
118       I.replaceAllUsesWith(UndefValue::get(I.getType()));
119     BB->eraseFromParent();
120   }
121 }
122 
123 /// Counts the amount of basic blocks and prints their name & respective index
124 static int countBasicBlocks(Module *Program) {
125   // TODO: Silence index with --quiet flag
126   outs() << "----------------------------\n";
127   int BBCount = 0;
128   for (auto &F : *Program)
129     for (auto &BB : F) {
130       if (BB.hasName())
131         outs() << "\t" << ++BBCount << ": " << BB.getName() << "\n";
132       else
133         outs() << "\t" << ++BBCount << ": Unnamed\n";
134     }
135 
136   return BBCount;
137 }
138 
139 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
140   outs() << "*** Reducing Basic Blocks...\n";
141   int BBCount = countBasicBlocks(Test.getProgram());
142   runDeltaPass(Test, BBCount, extractBasicBlocksFromModule);
143 }
144