tools/llvm-reduce/deltas/ReduceBasicBlocks.cpp

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