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