diff --git a/llvm/include/llvm/CodeGen/Passes.h b/llvm/include/llvm/CodeGen/Passes.h --- a/llvm/include/llvm/CodeGen/Passes.h +++ b/llvm/include/llvm/CodeGen/Passes.h @@ -54,6 +54,13 @@ /// the entry block. FunctionPass *createUnreachableBlockEliminationPass(); + /// createGCEmptyBasicblocksPass - Empty basic blocks (basic blocks without + /// real code) appear as the result of optimization passes removing + /// instructions. These blocks confuscate profile analysis (e.g., basic block + /// sections) since they will share the address of their fallthrough blocks. + /// This pass garbage-collects such basic blocks. + MachineFunctionPass *createGCEmptyBasicBlocksPass(); + /// createBasicBlockSections Pass - This pass assigns sections to machine /// basic blocks and is enabled with -fbasic-block-sections. MachineFunctionPass *createBasicBlockSectionsPass(); diff --git a/llvm/include/llvm/InitializePasses.h b/llvm/include/llvm/InitializePasses.h --- a/llvm/include/llvm/InitializePasses.h +++ b/llvm/include/llvm/InitializePasses.h @@ -124,6 +124,7 @@ void initializeFixupStatepointCallerSavedPass(PassRegistry&); void initializeFlattenCFGLegacyPassPass(PassRegistry &); void initializeFuncletLayoutPass(PassRegistry&); +void initializeGCEmptyBasicBlocksPass(PassRegistry &); void initializeGCMachineCodeAnalysisPass(PassRegistry&); void initializeGCModuleInfoPass(PassRegistry&); void initializeGVNLegacyPassPass(PassRegistry&); diff --git a/llvm/lib/CodeGen/CMakeLists.txt b/llvm/lib/CodeGen/CMakeLists.txt --- a/llvm/lib/CodeGen/CMakeLists.txt +++ b/llvm/lib/CodeGen/CMakeLists.txt @@ -200,6 +200,7 @@ RegisterCoalescer.cpp RegisterPressure.cpp RegisterScavenging.cpp + GCEmptyBasicBlocks.cpp RemoveRedundantDebugValues.cpp RenameIndependentSubregs.cpp MachineStableHash.cpp diff --git a/llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp b/llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp new file mode 100644 --- /dev/null +++ b/llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp @@ -0,0 +1,87 @@ +#include "llvm/ADT/SmallVector.h" +#include "llvm/ADT/Statistic.h" +#include "llvm/CodeGen/MachineBasicBlock.h" +#include "llvm/CodeGen/MachineFunction.h" +#include "llvm/CodeGen/MachineFunctionPass.h" +#include "llvm/CodeGen/MachineJumpTableInfo.h" +#include "llvm/CodeGen/Passes.h" +#include "llvm/CodeGen/TargetInstrInfo.h" +#include "llvm/InitializePasses.h" + +using namespace llvm; + +#define DEBUG_TYPE "gc-empty-basic-blocks" + +STATISTIC(NumEmptyBlocksRemoved, "Number of empty blocks removed"); + +class GCEmptyBasicBlocks : public MachineFunctionPass { +public: + static char ID; + + GCEmptyBasicBlocks() : MachineFunctionPass(ID) { + initializeGCEmptyBasicBlocksPass(*PassRegistry::getPassRegistry()); + } + + StringRef getPassName() const override { + return "Remove Empty Basic Blocks."; + } + + bool runOnMachineFunction(MachineFunction &MF) override; +}; + +bool GCEmptyBasicBlocks::runOnMachineFunction(MachineFunction &MF) { + if (MF.size() < 2) + return false; + MachineJumpTableInfo *JTI = MF.getJumpTableInfo(); + int NumRemoved = 0; + + // Iterate over all blocks except the last one. We can't remove the last block + // since it has no fallthrough block to rewire its predecessors to. + for (MachineFunction::iterator MBB = MF.begin(), + LastMBB = MachineFunction::iterator(MF.back()), + NextMBB; + MBB != LastMBB; MBB = NextMBB) { + NextMBB = std::next(MBB); + // TODO If a block is an eh pad, or it has address taken, we don't remove + // it. Removing such blocks is possible, but it probably requires a more + // complex logic. + if (MBB->isEHPad() || MBB->isMachineBlockAddressTaken()) + continue; + // Skip blocks with real code. + bool HasAnyRealCode = llvm::any_of(*MBB, [](const MachineInstr &MI) { + return !MI.isPosition() && !MI.isImplicitDef() && !MI.isKill() && + !MI.isDebugInstr(); + }); + if (HasAnyRealCode) + continue; + + LLVM_DEBUG(dbgs() << "Removing basic block " << MBB->getName() + << " in function " << MF.getName() << ":\n" + << *MBB << "\n"); + SmallVector Preds(MBB->predecessors()); + // Rewire the predecessors of this block to use the next block. + for (auto &Pred : Preds) + Pred->ReplaceUsesOfBlockWith(&*MBB, &*NextMBB); + // Update the jump tables. + if (JTI) + JTI->ReplaceMBBInJumpTables(&*MBB, &*NextMBB); + // Remove this block from predecessors of all its successors. + while (!MBB->succ_empty()) + MBB->removeSuccessor(MBB->succ_end() - 1); + // Finally, remove the block from the function. + MBB->eraseFromParent(); + ++NumRemoved; + } + NumEmptyBlocksRemoved += NumRemoved; + return NumRemoved != 0; +} + +char GCEmptyBasicBlocks::ID = 0; +INITIALIZE_PASS(GCEmptyBasicBlocks, "gc-empty-basic-blocks", + "Removes empty basic blocks and redirects their uses to their " + "fallthrough blocks.", + false, false) + +MachineFunctionPass *llvm::createGCEmptyBasicBlocksPass() { + return new GCEmptyBasicBlocks(); +} diff --git a/llvm/lib/CodeGen/TargetPassConfig.cpp b/llvm/lib/CodeGen/TargetPassConfig.cpp --- a/llvm/lib/CodeGen/TargetPassConfig.cpp +++ b/llvm/lib/CodeGen/TargetPassConfig.cpp @@ -250,6 +250,11 @@ "disable-select-optimize", cl::init(true), cl::Hidden, cl::desc("Disable the select-optimization pass from running")); +/// Enable garbage-collecting empty basic blocks. +static cl::opt + GCEmptyBlocks("gc-empty-basic-blocks", cl::init(false), cl::Hidden, + cl::desc("Enable garbage-collecting empty basic blocks")); + /// Allow standard passes to be disabled by command line options. This supports /// simple binary flags that either suppress the pass or do nothing. /// i.e. -disable-mypass=false has no effect. @@ -1245,6 +1250,9 @@ addPass(createMachineOutlinerPass(RunOnAllFunctions)); } + if (GCEmptyBlocks) + addPass(llvm::createGCEmptyBasicBlocksPass()); + if (EnableFSDiscriminator) addPass(createMIRAddFSDiscriminatorsPass( sampleprof::FSDiscriminatorPass::PassLast)); diff --git a/llvm/test/CodeGen/X86/basic-block-sections-labels-empty-block.ll b/llvm/test/CodeGen/X86/basic-block-sections-labels-empty-block.ll new file mode 100644 --- /dev/null +++ b/llvm/test/CodeGen/X86/basic-block-sections-labels-empty-block.ll @@ -0,0 +1,21 @@ +;; This test verifies that with -gc-empty-basic-blocks SHT_LLVM_BB_ADDR_MAP will not include entries for empty blocks. +; RUN: llc < %s -mtriple=x86_64 -O0 -basic-block-sections=labels -gc-empty-basic-blocks | FileCheck --check-prefix=CHECK %s + +define void @foo(i1 zeroext %0) nounwind { + br i1 %0, label %2, label %empty_block + +2: ; preds = %1 + %3 = call i32 @bar() + br label %4 + +empty_block: ; preds = %1 + unreachable + +4: ; preds = %2, %empty_block + ret void +} + +declare i32 @bar() + +; CHECK: .section .llvm_bb_addr_map,"o",@llvm_bb_addr_map,.text +; CHECK: .byte 3 # number of basic blocks diff --git a/llvm/test/CodeGen/X86/gc-empty-basic-blocks.ll b/llvm/test/CodeGen/X86/gc-empty-basic-blocks.ll new file mode 100644 --- /dev/null +++ b/llvm/test/CodeGen/X86/gc-empty-basic-blocks.ll @@ -0,0 +1,36 @@ +;; This test verifies that -gc-empty-basic-blocks removes empty blocks. +; RUN: llc < %s -mtriple=x86_64 -O0 -gc-empty-basic-blocks | FileCheck -check-prefix=CHECK %s +; RUN: llc < %s -mtriple=x86_64 -stats -O0 -gc-empty-basic-blocks 2>&1 | FileCheck -check-prefix=STAT %s + +; STAT: 1 gc-empty-basic-blocks - Number of empty blocks removed + +define void @foo(i1 zeroext %0) nounwind { + br i1 %0, label %2, label %empty_block + +; CHECK: .text +; CHECK-LABEL: foo: +; CHECK: jne .LBB0_1 +; CHECK-NEXT: jmp .LBB0_3 + +2: ; preds = %1 + %3 = call i32 @bar() + br label %4 + +; CHECK-LABEL: .LBB0_1: +; CHECK: jmp .LBB0_3 + +empty_block: ; preds = %1 + unreachable + +; CHECK-NOT: %empty_block +; CHECK-NOT: .LBB0_2 + +4: ; preds = %2, %empty_block + ret void + +; CHECK-LABEL: .LBB0_3: +; CHECK: retq + +} + +declare i32 @bar()