| 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/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 "llvm/Transforms/Utils/BasicBlockUtils.h" |
| 24 |
#include "llvm/Transforms/Utils/Cloning.h" |
| 25 |
#include "llvm/Transforms/Utils/Local.h" |
| 26 |
#include <vector> |
| 27 |
|
| 28 |
#define DEBUG_TYPE "llvm-reduce" |
| 29 |
|
| 30 |
using namespace llvm; |
| 31 |
|
| 32 |
using BlockSet = SetVector<BasicBlock *>; |
| 33 |
|
| 34 |
/// Replaces BB Terminator with one that only contains Chunk BBs |
| 35 |
static void replaceBranchTerminator(BasicBlock &BB, |
| 36 |
const BlockSet &BBsToDelete) { |
| 37 |
auto *Term = BB.getTerminator(); |
| 38 |
std::vector<BasicBlock *> ChunkSuccessors; |
| 39 |
for (auto *Succ : successors(&BB)) { |
| 40 |
if (!BBsToDelete.count(Succ)) |
| 41 |
ChunkSuccessors.push_back(Succ); |
| 42 |
} |
| 43 |
|
| 44 |
// BB only references Chunk BBs |
| 45 |
if (ChunkSuccessors.size() == Term->getNumSuccessors()) |
| 46 |
return; |
| 47 |
|
| 48 |
// TODO: Handle these without failing verifier. |
| 49 |
if (isa<CatchSwitchInst>(Term)) |
| 50 |
return; |
| 51 |
|
| 52 |
bool IsBranch = isa<BranchInst>(Term) || isa<CallBrInst>(Term); |
| 53 |
if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Term)) { |
| 54 |
BasicBlock *UnwindDest = Invoke->getUnwindDest(); |
| 55 |
BasicBlock::iterator LP = UnwindDest->getFirstNonPHIIt(); |
| 56 |
|
| 57 |
// Remove landingpad instruction if the containing block isn't used by other |
| 58 |
// invokes. |
| 59 |
|
| 60 |
// TODO: Handle catchswitch, catchpad, catchret, and cleanupret |
| 61 |
if (isa<LandingPadInst>(LP) && |
| 62 |
none_of(UnwindDest->users(), [Invoke](User *U) { |
| 63 |
return U != Invoke && isa<InvokeInst>(U); |
| 64 |
})) { |
| 65 |
LP->replaceAllUsesWith(getDefaultValue(LP->getType())); |
| 66 |
LP->eraseFromParent(); |
| 67 |
} else if (!ChunkSuccessors.empty() && |
| 68 |
ChunkSuccessors[0] == LP->getParent()) { |
| 69 |
// If the selected successor is the landing pad, clear the chunk |
| 70 |
// successors to avoid creating a regular branch to the landing pad which |
| 71 |
// would result in invalid IR. |
| 72 |
ChunkSuccessors.clear(); |
| 73 |
} |
| 74 |
IsBranch = true; |
| 75 |
} |
| 76 |
|
| 77 |
Value *Address = nullptr; |
| 78 |
if (auto *IndBI = dyn_cast<IndirectBrInst>(Term)) |
| 79 |
Address = IndBI->getAddress(); |
| 80 |
|
| 81 |
Term->replaceAllUsesWith(getDefaultValue(Term->getType())); |
| 82 |
Term->eraseFromParent(); |
| 83 |
|
| 84 |
if (ChunkSuccessors.empty()) { |
| 85 |
// If that fails then resort to replacing with a ret. |
| 86 |
auto *FnRetTy = BB.getParent()->getReturnType(); |
| 87 |
ReturnInst::Create(BB.getContext(), |
| 88 |
FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy), |
| 89 |
&BB); |
| 90 |
return; |
| 91 |
} |
| 92 |
|
| 93 |
if (IsBranch) |
| 94 |
BranchInst::Create(ChunkSuccessors[0], &BB); |
| 95 |
|
| 96 |
if (Address) { |
| 97 |
auto *NewIndBI = |
| 98 |
IndirectBrInst::Create(Address, ChunkSuccessors.size(), &BB); |
| 99 |
for (auto *Dest : ChunkSuccessors) |
| 100 |
NewIndBI->addDestination(Dest); |
| 101 |
} |
| 102 |
} |
| 103 |
|
| 104 |
/// Removes uninteresting BBs from switch, if the default case ends up being |
| 105 |
/// uninteresting, the switch is replaced with a void return (since it has to be |
| 106 |
/// replace with something) |
| 107 |
static void removeUninterestingBBsFromSwitch(SwitchInst &SwInst, |
| 108 |
const BlockSet &BBsToDelete) { |
| 109 |
for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) { |
| 110 |
auto Case = SwInst.case_begin() + I; |
| 111 |
if (BBsToDelete.count(Case->getCaseSuccessor())) { |
| 112 |
SwInst.removeCase(Case); |
| 113 |
--I; |
| 114 |
--E; |
| 115 |
} |
| 116 |
} |
| 117 |
|
| 118 |
if (BBsToDelete.count(SwInst.getDefaultDest())) { |
| 119 |
if (SwInst.getNumCases() == 0) { |
| 120 |
auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType(); |
| 121 |
Value *RetValue = |
| 122 |
FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy); |
| 123 |
ReturnInst::Create(SwInst.getContext(), RetValue, SwInst.getParent()); |
| 124 |
SwInst.eraseFromParent(); |
| 125 |
return; |
| 126 |
} |
| 127 |
|
| 128 |
// Replace the default dest with one of the other cases |
| 129 |
auto Case = SwInst.case_begin(); |
| 130 |
|
| 131 |
BasicBlock *NewDefault = Case->getCaseSuccessor(); |
| 132 |
SwInst.setDefaultDest(NewDefault); |
| 133 |
|
| 134 |
for (PHINode &SuccPHI : NewDefault->phis()) { |
| 135 |
SuccPHI.addIncoming(SuccPHI.getIncomingValueForBlock(SwInst.getParent()), |
| 136 |
SwInst.getParent()); |
| 137 |
} |
| 138 |
} |
| 139 |
} |
| 140 |
|
| 141 |
/// Removes out-of-chunk arguments from functions, and modifies their calls |
| 142 |
/// accordingly. It also removes allocations of out-of-chunk arguments. |
| 143 |
void llvm::reduceBasicBlocksDeltaPass(Oracle &O, ReducerWorkItem &WorkItem) { |
| 144 |
BlockSet BBsToDelete; |
| 145 |
|
| 146 |
df_iterator_default_set<BasicBlock *> Reachable; |
| 147 |
|
| 148 |
for (auto &F : WorkItem.getModule()) { |
| 149 |
if (F.empty()) |
| 150 |
continue; |
| 151 |
|
| 152 |
BasicBlock &Entry = F.getEntryBlock(); |
| 153 |
for (auto *BB : depth_first_ext(&Entry, Reachable)) |
| 154 |
(void)BB; |
| 155 |
|
| 156 |
// Skip any function with unreachable blocks. It's somewhat difficult to |
| 157 |
// avoid producing invalid IR without deleting them. |
| 158 |
// |
| 159 |
// We also do not want to unconditionally delete them, as doing so would |
| 160 |
// break the invariant of changing the number of chunks during counting. |
| 161 |
|
| 162 |
const bool HasUnreachableBlocks = Reachable.size() != F.size(); |
| 163 |
Reachable.clear(); |
| 164 |
|
| 165 |
if (HasUnreachableBlocks) { |
| 166 |
LLVM_DEBUG(dbgs() << "Skipping function with unreachable blocks\n"); |
| 167 |
continue; |
| 168 |
} |
| 169 |
|
| 170 |
for (BasicBlock &BB : F) { |
| 171 |
if (&BB != &Entry && !O.shouldKeep()) |
| 172 |
BBsToDelete.insert(&BB); |
| 173 |
} |
| 174 |
|
| 175 |
// Replace terminators that reference out-of-chunk BBs |
| 176 |
for (BasicBlock &BB : F) { |
| 177 |
if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator())) |
| 178 |
removeUninterestingBBsFromSwitch(*SwInst, BBsToDelete); |
| 179 |
else |
| 180 |
replaceBranchTerminator(BB, BBsToDelete); |
| 181 |
} |
| 182 |
|
| 183 |
// Cleanup any blocks that are now dead after eliminating this set. This |
| 184 |
// will likely be larger than the number of blocks the oracle told us to |
| 185 |
// delete. |
| 186 |
simpleSimplifyCFG(F, BBsToDelete.getArrayRef()); |
| 187 |
|
| 188 |
BBsToDelete.clear(); |
| 189 |
} |
| 190 |
} |
| 191 |
|
| 192 |
void llvm::reduceUnreachableBasicBlocksDeltaPass(Oracle &O, |
| 193 |
ReducerWorkItem &WorkItem) { |
| 194 |
std::vector<BasicBlock *> DeadBlocks; |
| 195 |
df_iterator_default_set<BasicBlock *> Reachable; |
| 196 |
|
| 197 |
for (Function &F : WorkItem.getModule()) { |
| 198 |
if (F.empty()) |
| 199 |
continue; |
| 200 |
|
| 201 |
// Mark all reachable blocks. |
| 202 |
for (BasicBlock *BB : depth_first_ext(&F, Reachable)) |
| 203 |
(void)BB; |
| 204 |
|
| 205 |
if (Reachable.size() != F.size() && !O.shouldKeep()) { |
| 206 |
for (BasicBlock &BB : F) { |
| 207 |
if (!Reachable.count(&BB)) |
| 208 |
DeadBlocks.push_back(&BB); |
| 209 |
} |
| 210 |
|
| 211 |
// Delete the dead blocks. |
| 212 |
DeleteDeadBlocks(DeadBlocks, nullptr, /*KeepOneInputPHIs*/ false); |
| 213 |
DeadBlocks.clear(); |
| 214 |
} |
| 215 |
|
| 216 |
Reachable.clear(); |
| 217 |
} |
| 218 |
} |