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