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
replaceBranchTerminator(BasicBlock & BB,std::set<BasicBlock * > BBsToKeep)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)
removeUninterestingBBsFromSwitch(SwitchInst & SwInst,std::set<BasicBlock * > BBsToKeep)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.
extractBasicBlocksFromModule(std::vector<Chunk> ChunksToKeep,Module * Program)90 static void extractBasicBlocksFromModule(std::vector<Chunk> ChunksToKeep,
91 Module *Program) {
92 Oracle O(ChunksToKeep);
93
94 std::set<BasicBlock *> BBsToKeep;
95
96 for (auto &F : *Program)
97 for (auto &BB : F)
98 if (O.shouldKeep())
99 BBsToKeep.insert(&BB);
100
101 std::vector<BasicBlock *> BBsToDelete;
102 for (auto &F : *Program)
103 for (auto &BB : F) {
104 if (!BBsToKeep.count(&BB)) {
105 BBsToDelete.push_back(&BB);
106 // Remove out-of-chunk BB from successor phi nodes
107 for (auto *Succ : successors(&BB))
108 Succ->removePredecessor(&BB);
109 }
110 }
111
112 // Replace terminators that reference out-of-chunk BBs
113 for (auto &F : *Program)
114 for (auto &BB : F) {
115 if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
116 removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
117 else
118 replaceBranchTerminator(BB, BBsToKeep);
119 }
120
121 // Replace out-of-chunk switch uses
122 for (auto &BB : BBsToDelete) {
123 // Instructions might be referenced in other BBs
124 for (auto &I : *BB)
125 I.replaceAllUsesWith(UndefValue::get(I.getType()));
126 BB->eraseFromParent();
127 }
128 }
129
130 /// Counts the amount of basic blocks and prints their name & respective index
countBasicBlocks(Module * Program)131 static int countBasicBlocks(Module *Program) {
132 // TODO: Silence index with --quiet flag
133 outs() << "----------------------------\n";
134 int BBCount = 0;
135 for (auto &F : *Program)
136 for (auto &BB : F) {
137 if (BB.hasName())
138 outs() << "\t" << ++BBCount << ": " << BB.getName() << "\n";
139 else
140 outs() << "\t" << ++BBCount << ": Unnamed\n";
141 }
142
143 return BBCount;
144 }
145
reduceBasicBlocksDeltaPass(TestRunner & Test)146 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
147 outs() << "*** Reducing Basic Blocks...\n";
148 int BBCount = countBasicBlocks(Test.getProgram());
149 runDeltaPass(Test, BBCount, extractBasicBlocksFromModule);
150 }
151