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