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   DenseSet<BasicBlock *> BBsToKeep;
94 
95   SmallVector<BasicBlock *> BBsToDelete;
96   for (auto &F : Program) {
97     for (auto &BB : F) {
98       if (O.shouldKeep())
99         BBsToKeep.insert(&BB);
100       else {
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 
109   // Replace terminators that reference out-of-chunk BBs
110   for (auto &F : Program)
111     for (auto &BB : F) {
112       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
113         removeUninterestingBBsFromSwitch(*SwInst, BBsToKeep);
114       else
115         replaceBranchTerminator(BB, BBsToKeep);
116     }
117 
118   // Replace out-of-chunk switch uses
119   for (auto &BB : BBsToDelete) {
120     // Instructions might be referenced in other BBs
121     for (auto &I : *BB)
122       I.replaceAllUsesWith(UndefValue::get(I.getType()));
123     if (BB->getParent()->size() == 1) {
124       // this is the last basic block of the function, thus we must also make
125       // sure to remove comdat and set linkage to external
126       auto F = BB->getParent();
127       F->deleteBody();
128       F->setComdat(nullptr);
129     } else {
130       BB->eraseFromParent();
131     }
132   }
133 }
134 
135 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
136   outs() << "*** Reducing Basic Blocks...\n";
137   runDeltaPass(Test, extractBasicBlocksFromModule);
138 }
139