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   // TODO: Handle these without failing verifier.
  49   if (isa<CatchSwitchInst>(Term))
  50     return;
  51
  52   bool IsBranch = isa<BranchInst>(Term);
  53   if (InvokeInst *Invoke = dyn_cast<InvokeInst>(Term)) {
  54     BasicBlock *UnwindDest = Invoke->getUnwindDest();
  55     Instruction *LP = UnwindDest->getFirstNonPHI();
  56
  57     // Remove landingpad instruction if the containing block isn't used by other
  58     // invokes.
  59
  60     // TODO: Handle catchswitch, catchpad, catchret, and cleanupret
  61     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 chunk
  70       // successors to avoid creating a regular branch to the landing pad which
  71       // 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 being
 105 /// uninteresting, the switch is replaced with a void return (since it has to be
 106 /// replace with something)
 107 static void
 108 removeUninterestingBBsFromSwitch(SwitchInst &SwInst,
 109                                  const DenseSet<BasicBlock *> &BBsToDelete) {
 110   for (int I = 0, E = SwInst.getNumCases(); I != E; ++I) {
 111     auto Case = SwInst.case_begin() + I;
 112     if (BBsToDelete.count(Case->getCaseSuccessor())) {
 113       SwInst.removeCase(Case);
 114       --I;
 115       --E;
 116     }
 117   }
 118
 119   if (BBsToDelete.count(SwInst.getDefaultDest())) {
 120     if (SwInst.getNumCases() == 0) {
 121       auto *FnRetTy = SwInst.getParent()->getParent()->getReturnType();
 122       Value *RetValue =
 123           FnRetTy->isVoidTy() ? nullptr : getDefaultValue(FnRetTy);
 124       ReturnInst::Create(SwInst.getContext(), RetValue, SwInst.getParent());
 125       SwInst.eraseFromParent();
 126       return;
 127     }
 128
 129     // Replace the default dest with one of the other cases
 130     auto Case = SwInst.case_begin();
 131
 132     BasicBlock *NewDefault = Case->getCaseSuccessor();
 133     SwInst.setDefaultDest(NewDefault);
 134
 135     for (PHINode &SuccPHI : NewDefault->phis()) {
 136       SuccPHI.addIncoming(SuccPHI.getIncomingValueForBlock(SwInst.getParent()),
 137                           SwInst.getParent());
 138     }
 139   }
 140 }
 141
 142 /// Removes out-of-chunk arguments from functions, and modifies their calls
 143 /// accordingly. It also removes allocations of out-of-chunk arguments.
 144 static void extractBasicBlocksFromModule(Oracle &O, ReducerWorkItem &WorkItem) {
 145   DenseSet<BasicBlock *> BBsToDelete;
 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 to
 157     // avoid producing invalid IR without deleting them.
 158     //
 159     // We also do not want to unconditionally delete them, as doing so would
 160     // 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 BBs
 176     for (BasicBlock &BB : F) {
 177       if (auto *SwInst = dyn_cast<SwitchInst>(BB.getTerminator()))
 178         removeUninterestingBBsFromSwitch(*SwInst, BBsToDelete);
 179       else
 180         replaceBranchTerminator(BB, BBsToDelete);
 181     }
 182
 183     // Cleanup any blocks that are now dead after eliminating this set. This
 184     // will likely be larger than the number of blocks the oracle told us to
 185     // delete.
 186     EliminateUnreachableBlocks(F);
 187     BBsToDelete.clear();
 188   }
 189 }
 190
 191 void llvm::reduceBasicBlocksDeltaPass(TestRunner &Test) {
 192   runDeltaPass(Test, extractBasicBlocksFromModule, "Reducing Basic Blocks");
 193 }
 194
 195 static void removeUnreachableBasicBlocksFromModule(Oracle &O,
 196                                                    ReducerWorkItem &WorkItem) {
 197   std::vector<BasicBlock *> DeadBlocks;
 198   df_iterator_default_set<BasicBlock *> Reachable;
 199
 200   for (Function &F : WorkItem.getModule()) {
 201     if (F.empty())
 202       continue;
 203
 204     // Mark all reachable blocks.
 205     for (BasicBlock *BB : depth_first_ext(&F, Reachable))
 206       (void)BB;
 207
 208     if (Reachable.size() != F.size() && !O.shouldKeep()) {
 209       for (BasicBlock &BB : F) {
 210         if (!Reachable.count(&BB))
 211           DeadBlocks.push_back(&BB);
 212       }
 213
 214       // Delete the dead blocks.
 215       DeleteDeadBlocks(DeadBlocks, nullptr, /*KeepOneInputPHIs*/ false);
 216       DeadBlocks.clear();
 217     }
 218
 219     Reachable.clear();
 220   }
 221 }
 222
 223 void llvm::reduceUnreachableBasicBlocksDeltaPass(TestRunner &Test) {
 224   runDeltaPass(Test, removeUnreachableBasicBlocksFromModule,
 225                "Removing Unreachable Basic Blocks");
 226 }