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