Add a pass to garbage-collect empty basic blocks after code generation.

[rahmanl]

Summary

Propeller and pseudo-probes map profiles back to Machine IR via basic block addresses that are stored in metadata sections.
Empty basic blocks (basic blocks without real code) obfuscate the profile mapping because their addresses collide with their next basic blocks.
For instance, the fallthrough block of an empty block should always be adjacent to it. Otherwise, a completely unnecessary jump would be added.
This patch adds a MachineFunction pass named GCEmptyBasicBlocks which attempts to garbage-collect the empty blocks before the BasicBlockSections and pass.
This pass removes each empty basic block after redirecting its incoming edges to its fall-through block.
The garbage-collection is not complete. We keep the empty block in 4 cases:

1. The empty block is an exception handling pad.
2. The empty block has its address taken.
3. The empty block is the last block of the function and it has predecessors.
4. The empty block is the only block of the function.

The first three cases are extremely rare in normal code (no cases for the clang binary). Removing the blocks under the first two cases requires modifying exception handling structures and operands of non-terminator instructions -- which is doable but not worth the additional complexity in the pass.

[rahmanl]

Add comments.

[rahmanl]

Add comments.

[rahmanl]

rebase.

[rahmanl]

Revert unrelated changes.

[rahmanl]

Update and rebase the patch.

[rahmanl]

Add one more test.

[rahmanl]

Remove unwanted change.

[JestrTulip]

LGTM

[rahmanl]

Omit empty basic blocks which have their address taken, and EH pad blocks.

[rahmanl]

clang-format.

[tmsriram]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

54

If the block has no real instructions but debug instructions, is it correct to nuke it?

59

If it is the last block it must have predecessors or you couldn't get to it, so !Preds.empty() is redundant.

71

Should we add the non-real instructions in this block to the beginning of the next block too?

[wenlei]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

54

For debuggbility, probably not. Relatedly the current implementation also keep the block if it contains pseudo-probe, which is what we want.

[rahmanl]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

54

I am guessing debug-info instructions in a basic block with zero binary size is never used. Any ideas @dblaikie ?

@wenlei My initial idea was to GC all empty blocks before inserting pseudo probes. Now I realize pseudo probes may be inserted anytime. But I still think we can remove empty blocks with pseudo probes at this point of CodeGen. WDYT?

59

I found one case of a function with a single empty basic block which prompted me to add this check.

71

I am not sure we can. For example, a register kill instruction cannot be safely moved into the new block, if that block has other predecessors.

[rahmanl]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

59

To be more precise, if I do remove the single empty basic block in that function, the compilation later breaks (during CFI-insertion) because the function becomes empty. I will take a look to see if I can mitigate the breakage.

[wenlei]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

54

pseudo-probes are inserted very early - similar to where IRPGO probes are inserted. If a block has pseudo-probe in it, we should not remove that block, because the purpose of pseudo-probe is to preserve control flow (branches) so profile can be mapped to unoptimized IR more accurately.

[rahmanl]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

54

Thanks for the explanation. I got a bit confused looking at where PseudoProbeInserter is added in TargetPassConfig.cpp, which is only for callsites.

[dblaikie]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

54

@jmorse for debug location intrinsic functions - but my guess would be deleting an unreachable block would be fine. I'd guess SimplifyCFG already does this? (you could try it -and if it does just delete the block, despite the presence of debug location intrinsics, it's probably a good sign you can do that too)

[rahmanl]

Remove redundant check, refactor, rebase.

[rahmanl]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

54

Here, we are deleting basic blocks with no real instructions (even if they are reachable). These basic blocks manifest in the binary as blocks which have the same begin address as their next block. So debuggers can use the debug-info from their next block instead.

59

Turns out my check if (MF.size() < 2) guards against this case already. Applied your suggestion and then refactored a bit.

[rahmanl]

Remove unused variable.

[tmsriram]

I am approving this change as it looks like all concerns have resolutions. Further, this is not the default.

[rahmanl]

• Add check for stats.
• Change the option name to -gc-empty-basic-blocks.
• Rebase

[lkail]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

1

It's missing a file header. https://llvm.org/docs/CodingStandards.html#id9.

[rahmanl]

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

1

Thanks. Done in 7dc65662730c4d156d08a26a64f5d353ad9bbd08

[nickdesaulniers]

Does this work with -mllvm -trap-unreachable?

[rahmanl]

In D107534#4622487, @nickdesaulniers wrote:

Does this work with -mllvm -trap-unreachable?

It should. What are these trap instructions lowered to in MIR?

llvm/include/llvm/CodeGen/Passes.h

namespace llvm {
   /// createUnreachableBlockEliminationPass - The LLVM code generator does not
   /// work well with unreachable basic blocks (what live ranges make sense for a
   /// block that cannot be reached?).  As such, a code generator should either
   /// not instruction select unreachable blocks, or run this pass as its
   /// last LLVM modifying pass to clean up blocks that are not reachable from
   /// 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();
 
   /// createMachineFunctionSplitterPass - This pass splits machine functions
   /// using profile information.
   MachineFunctionPass *createMachineFunctionSplitterPass();
 

llvm/include/llvm/InitializePasses.h

 void initializeExternalAAWrapperPassPass(PassRegistry&);
 void initializeFEntryInserterPass(PassRegistry&);
 void initializeFinalizeISelPass(PassRegistry&);
 void initializeFinalizeMachineBundlesPass(PassRegistry&);
 void initializeFixIrreduciblePass(PassRegistry &);
 void initializeFixupStatepointCallerSavedPass(PassRegistry&);
 void initializeFlattenCFGLegacyPassPass(PassRegistry &);
 void initializeFuncletLayoutPass(PassRegistry&);
+void initializeGCEmptyBasicBlocksPass(PassRegistry &);
 void initializeGCMachineCodeAnalysisPass(PassRegistry&);
 void initializeGCModuleInfoPass(PassRegistry&);
 void initializeGVNLegacyPassPass(PassRegistry&);
 void initializeGlobalMergePass(PassRegistry&);
 void initializeGlobalsAAWrapperPassPass(PassRegistry&);
 void initializeGuardWideningLegacyPassPass(PassRegistry&);
 void initializeHardwareLoopsLegacyPass(PassRegistry&);
 void initializeMIRProfileLoaderPassPass(PassRegistry &);

llvm/lib/CodeGen/CMakeLists.txt

add_llvm_component_library(LLVMCodeGen
   RegAllocGreedy.cpp
   RegAllocPBQP.cpp
   RegAllocPriorityAdvisor.cpp
   RegAllocScore.cpp
   RegisterClassInfo.cpp
   RegisterCoalescer.cpp
   RegisterPressure.cpp
   RegisterScavenging.cpp
+  GCEmptyBasicBlocks.cpp
   RemoveRedundantDebugValues.cpp
   RenameIndependentSubregs.cpp
   MachineStableHash.cpp
   MIRVRegNamerUtils.cpp
   MIRNamerPass.cpp
   MIRCanonicalizerPass.cpp
   RegisterUsageInfo.cpp
   RegUsageInfoCollector.cpp

llvm/lib/CodeGen/GCEmptyBasicBlocks.cpp

+#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<MachineBasicBlock *, 8> 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();
+}

llvm/lib/CodeGen/TargetPassConfig.cpp

static cl::opt<bool> DisableExpandReductions(
     "disable-expand-reductions", cl::init(false), cl::Hidden,
     cl::desc("Disable the expand reduction intrinsics pass from running"));
 
 /// Disable the select optimization pass.
 static cl::opt<bool> DisableSelectOptimize(
     "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<bool>
+    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.
 /// These should be converted to boolOrDefault in order to use applyOverride.
 static IdentifyingPassPtr applyDisable(IdentifyingPassPtr PassID,
                                        bool Override) {
   if (Override)
     return IdentifyingPassPtr();
if (TM->Options.EnableMachineOutliner && getOptLevel() != CodeGenOpt::None &&
     bool RunOnAllFunctions =
         (EnableMachineOutliner == RunOutliner::AlwaysOutline);
     bool AddOutliner =
         RunOnAllFunctions || TM->Options.SupportsDefaultOutlining;
     if (AddOutliner)
       addPass(createMachineOutlinerPass(RunOnAllFunctions));
   }
 
+  if (GCEmptyBlocks)
+    addPass(llvm::createGCEmptyBasicBlocksPass());
+
   if (EnableFSDiscriminator)
     addPass(createMIRAddFSDiscriminatorsPass(
         sampleprof::FSDiscriminatorPass::PassLast));
 
   // Machine function splitter uses the basic block sections feature. Both
   // cannot be enabled at the same time. Basic block sections takes precedence.
   // FIXME: In principle, BasicBlockSection::Labels and splitting can used
   // together. Update this check once we have addressed any issues.

llvm/test/CodeGen/X86/basic-block-sections-labels-empty-block.ll

+;; 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

llvm/test/CodeGen/X86/gc-empty-basic-blocks.ll

+;; 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()