llvm/tools/llvm-reduce/deltas/ReduceBasicBlocks.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-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   bool IsBranch = isa<BranchInst>(Term);
  49   if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Term)) {
  50     LandingPadInst *LP = Invoke->getLandingPadInst();
  51     // Remove landingpad instruction if the containing block isn't used by other
  52     // invokes.
  53     if (none_of(LP->getParent()->users(), [Invoke](User *U) {
  54           return U != Invoke && isa<InvokeInst>(U);
  55         })) {
  56       LP->replaceAllUsesWith(getDefaultValue(LP->getType()));
  57       LP->eraseFromParent();
  58     } else if (!ChunkSuccessors.empty() &&
  59                ChunkSuccessors[0] == LP->getParent()) {
  60       // If the selected successor is the landing pad, clear the chunk
  61       // successors to avoid creating a regular branch to the landing pad which
  62       // would result in invalid IR.
  63       ChunkSuccessors.clear();
  64     }
  65     IsBranch = true;
  66   }
  67
  68   Value *Address = nullptr;
  69   if (auto *IndBI = dyn_cast<IndirectBrInst>(Term))
  70     Address = IndBI->getAddress();
  71
  72   Term->replaceAllUsesWith(getDefaultValue(Term->getType()));
  73   Term->eraseFromParent();
  74
  75   if (ChunkSuccessors.empty()) {
  76     // If that fails then resort to replacing with a ret.
  77     auto *FnRetTy = BB.getParent()->getReturnType();
  78     ReturnInst::Create(BB.getContext(),
  79                        FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy),
  80                        &BB);
  81     return;
  82   }
  83
  84   if (IsBranch)
  85     BranchInst::Create(ChunkSuccessors[0], &BB);
  86
  87   if (Address) {
  88     auto *NewIndBI =
  89         IndirectBrInst::Create(Address, ChunkSuccessors.size(), &BB);
  90     for (auto *Dest : ChunkSuccessors)
  91       NewIndBI->addDestination(Dest);
  92   }
  93 }
  94
  95 /// Removes uninteresting BBs from switch, if the default case ends up being
  96 /// uninteresting, the switch is replaced with a void return (since it has to be
  97 /// replace with something)
  98 static void
  99 removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
 100                                  const DenseSet<BasicBlock *> &BBsToDelete) {
 101   for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
 102     auto Case = SwInst.case_begin() + I;
 103     if (BBsToDelete.count(Case->getCaseSuccessor())) {
 104       SwInst.removeCase(Case);
 105       --I;
 106       --E;
 107     }
 108   }
 109
 110   if (BBsToDelete.count(SwInst.getDefaultDest())) {
 111     if (SwInst.getNumCases() == 0) {
 112       auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
 113       Value *RetValue =
 114           FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy);
 115       ReturnInst::Create(SwInst.getContext(), RetValue, SwInst.getParent());
 116       SwInst.eraseFromParent();
 117       return;
 118     }
 119
 120     // Replace the default dest with one of the other cases
 121     auto Case = SwInst.case_begin();
 122
 123     BasicBlock *NewDefault = Case->getCaseSuccessor();
 124     SwInst.setDefaultDest(NewDefault);
 125
 126     for (PHINode &SuccPHI : NewDefault->phis()) {
 127       SuccPHI.addIncoming(SuccPHI.getIncomingValueForBlock(SwInst.getParent()),
 128                           SwInst.getParent());
 129     }
 130   }
 131 }
 132
 133 /// Removes out-of-chunk arguments from functions, and modifies their calls
 134 /// accordingly. It also removes allocations of out-of-chunk arguments.
 135 static void extractBasicBlocksFromModule(Oracle &O, ReducerWorkItem &WorkItem) {
 136   DenseSet<BasicBlock *> BBsToDelete;
 137   df_iterator_default_set<BasicBlock *> Reachable;
 138
 139   for (auto &F : WorkItem.getModule()) {
 140     if (F.empty())
 141       continue;
 142
 143     BasicBlock &Entry = F.getEntryBlock();
 144     for (auto *BB : depth_first_ext(&Entry, Reachable))
 145       (void)BB;
 146
 147     // Skip any function with unreachable blocks. It's somewhat difficult to
 148     // avoid producing invalid IR without deleting them.
 149     //
 150     // We also do not want to unconditionally delete them, as doing so would
 151     // break the invariant of changing the number of chunks during counting.
 152
 153     const bool HasUnreachableBlocks = Reachable.size() != F.size();
 154     Reachable.clear();
 155
 156     if (HasUnreachableBlocks) {
 157       LLVM_DEBUG(dbgs() << "Skipping function with unreachable blocks\n");
 158       continue;
 159     }
 160
 161     for (BasicBlock &BB : F) {
 162       if (&BB != &Entry && !O.shouldKeep())
 163         BBsToDelete.insert(&BB);
 164     }
 165
 166     // Replace terminators that reference out-of-chunk BBs
 167     for (BasicBlock &BB : F) {
 168       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
 169         removeUninterestingBBsFromSwitch(*SwInst, BBsToDelete);
 170       else
 171         replaceBranchTerminator(BB, BBsToDelete);
 172     }
 173
 174     // Cleanup any blocks that are now dead after eliminating this set. This
 175     // will likely be larger than the number of blocks the oracle told us to
 176     // delete.
 177     EliminateUnreachableBlocks(F);
 178     BBsToDelete.clear();
 179   }
 180 }
 181
 182 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
 183   runDeltaPass(Test, extractBasicBlocksFromModule, "Reducing Basic Blocks");
 184 }
 185
 186 static void removeUnreachableBasicBlocksFromModule(Oracle &O,
 187                                                    ReducerWorkItem &WorkItem) {
 188   std::vector<BasicBlock *> DeadBlocks;
 189   df_iterator_default_set<BasicBlock *> Reachable;
 190
 191   for (Function &F : WorkItem.getModule()) {
 192     if (F.empty())
 193       continue;
 194
 195     // Mark all reachable blocks.
 196     for (BasicBlock *BB : depth_first_ext(&F, Reachable))
 197       (void)BB;
 198
 199     if (Reachable.size() != F.size() && !O.shouldKeep()) {
 200       for (BasicBlock &BB : F) {
 201         if (!Reachable.count(&BB))
 202           DeadBlocks.push_back(&BB);
 203       }
 204
 205       // Delete the dead blocks.
 206       DeleteDeadBlocks(DeadBlocks, nullptr, /*KeepOneInputPHIs*/ false);
 207       DeadBlocks.clear();
 208     }
 209
 210     Reachable.clear();
 211   }
 212 }
 213
 214 void llvm::reduceUnreachableBasicBlocksDeltaPass(TestRunner &Test) {
 215   runDeltaPass(Test, removeUnreachableBasicBlocksFromModule,
 216                "Removing Unreachable Basic Blocks");
 217 }