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/ADT/DenseSet.h"
16 #include "llvm/IR/BasicBlock.h"
17 #include "llvm/IR/Instruction.h"
18 #include "llvm/IR/Instructions.h"
19 #include "llvm/IR/LLVMContext.h"
20 #include "llvm/IR/Value.h"
21 #include "llvm/Support/Casting.h"
22 #include "llvm/Support/raw_ostream.h"
23 #include <vector>
24 
25 using namespace llvm;
26 
27 /// Replaces BB Terminator with one that only contains Chunk BBs
28 static void replaceBranchTerminator(BasicBlock &BB,
29                                     const DenseSet<BasicBlock *> &BBsToKeep) {
30   auto *Term = BB.getTerminator();
31   std::vector<BasicBlock *> ChunkSucessors;
32   for (auto *Succ : successors(&BB))
33     if (BBsToKeep.count(Succ))
34       ChunkSucessors.push_back(Succ);
35 
36   // BB only references Chunk BBs
37   if (ChunkSucessors.size() == Term->getNumSuccessors())
38     return;
39 
40   bool IsBranch = isa<BranchInst>(Term) || isa<InvokeInst>(Term);
41   Value *Address = nullptr;
42   if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
43     Address = IndBI->getAddress();
44 
45   Term->replaceAllUsesWith(UndefValue::get(Term->getType()));
46   Term->eraseFromParent();
47 
48   if (ChunkSucessors.empty()) {
49     auto *FnRetTy = BB.getParent()->getReturnType();
50     ReturnInst::Create(BB.getContext(),
51                        FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
52                        &BB);
53     return;
54   }
55 
56   if (IsBranch)
57     BranchInst::Create(ChunkSucessors[0], &BB);
58 
59   if (Address) {
60     auto *NewIndBI =
61         IndirectBrInst::Create(Address, ChunkSucessors.size(), &BB);
62     for (auto *Dest : ChunkSucessors)
63       NewIndBI->addDestination(Dest);
64   }
65 }
66 
67 /// Removes uninteresting BBs from switch, if the default case ends up being
68 /// uninteresting, the switch is replaced with a void return (since it has to be
69 /// replace with something)
70 static void
71 removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
72                                  const DenseSet<BasicBlock *> &BBsToKeep) {
73   if (!BBsToKeep.count(SwInst.getDefaultDest())) {
74     auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
75     ReturnInst::Create(SwInst.getContext(),
76                        FnRetTy->isVoidTy() ? nullptr : UndefValue::get(FnRetTy),
77                        SwInst.getParent());
78     SwInst.eraseFromParent();
79   } else
80     for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
81       auto Case = SwInst.case_begin() + I;
82       if (!BBsToKeep.count(Case->getCaseSuccessor())) {
83         SwInst.removeCase(Case);
84         --I;
85         --E;
86       }
87     }
88 }
89 
90 /// Removes out-of-chunk arguments from functions, and modifies their calls
91 /// accordingly. It also removes allocations of out-of-chunk arguments.
92 static void extractBasicBlocksFromModule(Oracle &O, Module &Program) {
93   std::vector<BasicBlock *> InitBBsToKeep;
94 
95   for (auto &F : Program)
96     for (auto &BB : F)
97       if (O.shouldKeep())
98         InitBBsToKeep.push_back(&BB);
99 
100   // We create a vector first, then convert it to a set, so that we don't have
101   // to pay the cost of rebalancing the set frequently if the order we insert
102   // the elements doesn't match the order they should appear inside the set.
103   DenseSet<BasicBlock *> BBsToKeep(InitBBsToKeep.begin(), InitBBsToKeep.end());
104 
105   std::vector<BasicBlock *> BBsToDelete;
106   for (auto &F : Program)
107     for (auto &BB : F) {
108       if (!BBsToKeep.count(&BB)) {
109         BBsToDelete.push_back(&BB);
110         // Remove out-of-chunk BB from successor phi nodes
111         for (auto *Succ : successors(&BB))
112           Succ->removePredecessor(&BB);
113       }
114     }
115 
116   // Replace terminators that reference out-of-chunk BBs
117   for (auto &F : Program)
118     for (auto &BB : F) {
119       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
120         removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
121       else
122         replaceBranchTerminator(BB, BBsToKeep);
123     }
124 
125   // Replace out-of-chunk switch uses
126   for (auto &BB : BBsToDelete) {
127     // Instructions might be referenced in other BBs
128     for (auto &I : *BB)
129       I.replaceAllUsesWith(UndefValue::get(I.getType()));
130     if (BB->getParent()->size() == 1) {
131       // this is the last basic block of the function, thus we must also make
132       // sure to remove comdat and set linkage to external
133       auto F = BB->getParent();
134       F->deleteBody();
135       F->setComdat(nullptr);
136     } else {
137       BB->eraseFromParent();
138     }
139   }
140 }
141 
142 /// Counts the amount of basic blocks and prints their name & respective index
143 static int countBasicBlocks(Module &Program) {
144   // TODO: Silence index with --quiet flag
145   outs() << "----------------------------\n";
146   int BBCount = 0;
147   for (auto &F : Program)
148     for (auto &BB : F) {
149       if (BB.hasName())
150         outs() << "\t" << ++BBCount << ": " << BB.getName() << "\n";
151       else
152         outs() << "\t" << ++BBCount << ": Unnamed\n";
153     }
154 
155   return BBCount;
156 }
157 
158 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
159   outs() << "*** Reducing Basic Blocks...\n";
160   int BBCount = countBasicBlocks(Test.getProgram());
161   runDeltaPass(Test, BBCount, extractBasicBlocksFromModule);
162 }
163