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 "llvm/Transforms/Utils/BasicBlockUtils.h" 26 #include "llvm/Transforms/Utils/Local.h" 27 28 #include <vector> 29 30 #define DEBUG_TYPE "llvm-reduce" 31 32 using namespace llvm; 33 34 /// Replaces BB Terminator with one that only contains Chunk BBs 35 static void replaceBranchTerminator(BasicBlock &BB, 36 const DenseSet<BasicBlock *> &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); 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 108 removeUninterestingBBsFromSwitch(SwitchInst &SwInst, 109 const DenseSet<BasicBlock *> &BBsToDelete) { 110 for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) { 111 auto Case = SwInst.case_begin() + I; 112 if (BBsToDelete.count(Case->getCaseSuccessor())) { 113 SwInst.removeCase(Case); 114 --I; 115 --E; 116 } 117 } 118 119 if (BBsToDelete.count(SwInst.getDefaultDest())) { 120 if (SwInst.getNumCases() == 0) { 121 auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType(); 122 Value *RetValue = 123 FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy); 124 ReturnInst::Create(SwInst.getContext(), RetValue, SwInst.getParent()); 125 SwInst.eraseFromParent(); 126 return; 127 } 128 129 // Replace the default dest with one of the other cases 130 auto Case = SwInst.case_begin(); 131 132 BasicBlock *NewDefault = Case->getCaseSuccessor(); 133 SwInst.setDefaultDest(NewDefault); 134 135 for (PHINode &SuccPHI : NewDefault->phis()) { 136 SuccPHI.addIncoming(SuccPHI.getIncomingValueForBlock(SwInst.getParent()), 137 SwInst.getParent()); 138 } 139 } 140 } 141 142 /// Removes out-of-chunk arguments from functions, and modifies their calls 143 /// accordingly. It also removes allocations of out-of-chunk arguments. 144 static void extractBasicBlocksFromModule(Oracle &O, ReducerWorkItem &WorkItem) { 145 DenseSet<BasicBlock *> BBsToDelete; 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 EliminateUnreachableBlocks(F); 187 BBsToDelete.clear(); 188 } 189 } 190 191 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) { 192 runDeltaPass(Test, extractBasicBlocksFromModule, "Reducing Basic Blocks"); 193 } 194 195 static void removeUnreachableBasicBlocksFromModule(Oracle &O, 196 ReducerWorkItem &WorkItem) { 197 std::vector<BasicBlock *> DeadBlocks; 198 df_iterator_default_set<BasicBlock *> Reachable; 199 200 for (Function &F : WorkItem.getModule()) { 201 if (F.empty()) 202 continue; 203 204 // Mark all reachable blocks. 205 for (BasicBlock *BB : depth_first_ext(&F, Reachable)) 206 (void)BB; 207 208 if (Reachable.size() != F.size() && !O.shouldKeep()) { 209 for (BasicBlock &BB : F) { 210 if (!Reachable.count(&BB)) 211 DeadBlocks.push_back(&BB); 212 } 213 214 // Delete the dead blocks. 215 DeleteDeadBlocks(DeadBlocks, nullptr, /*KeepOneInputPHIs*/ false); 216 DeadBlocks.clear(); 217 } 218 219 Reachable.clear(); 220 } 221 } 222 223 void llvm::reduceUnreachableBasicBlocksDeltaPass(TestRunner &Test) { 224 runDeltaPass(Test, removeUnreachableBasicBlocksFromModule, 225 "Removing Unreachable Basic Blocks"); 226 } 227