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