219 lines · cpp
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file implements a function which calls the Generic Delta pass in order10// 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 30using namespace llvm;31 32using BlockSet = SetVector<BasicBlock *>;33 34/// Replaces BB Terminator with one that only contains Chunk BBs35static 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 BBs45 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 other58 // invokes.59 60 // TODO: Handle catchswitch, catchpad, catchret, and cleanupret61 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 chunk70 // successors to avoid creating a regular branch to the landing pad which71 // 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 being105/// uninteresting, the switch is replaced with a void return (since it has to be106/// replace with something)107static 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 cases129 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 calls142/// accordingly. It also removes allocations of out-of-chunk arguments.143void 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 to157 // avoid producing invalid IR without deleting them.158 //159 // We also do not want to unconditionally delete them, as doing so would160 // 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 BBs176 for (BasicBlock &BB : F) {177 if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))178 removeUninterestingBBsFromSwitch(*SwInst, BBsToDelete);179 else180 replaceBranchTerminator(BB, BBsToDelete);181 }182 183 // Cleanup any blocks that are now dead after eliminating this set. This184 // will likely be larger than the number of blocks the oracle told us to185 // delete.186 simpleSimplifyCFG(F, BBsToDelete.getArrayRef());187 188 BBsToDelete.clear();189 }190}191 192void 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}219