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