llvm-reduce: add a pass for cleaning up branches

[regehr]

Summary

I'm doing a lot of reductions starting with full-sized IR modules,
trying to find minimal triggers for random issues detected by alive2.
Even after llvm-reduce reaches a fixpoint, there's often some
control-flow-related junk, often towards the end of the module, that
isn't getting cleaned up by existing passes that we have.

This patch adds three reduction passes. The first one tries to make
every conditional branch into an unconditional branch to the original
branch's true target. The second pass does the same thing, but uses the
false target. The third pass targets unconditional branches. For a BB
terminated by an unconditional branch, all instructions in the BB are
sunk to the start of the successor block and all branches targeting
the original block are pointed to the successor. Then we delete the
block.

On a collection of 53 IR files that I'm using to benchmark
llvm-reduce, this patch changes the average final file size from 710
bytes to 615 bytes, about a 15% improvement.

[arsenm]

llvm/tools/llvm-reduce/deltas/ReduceBranches.cpp

25–33

I was looking at doing this by calling simplifyCFG on each block rather than reimplementing the transform

[regehr]

llvm/tools/llvm-reduce/deltas/ReduceBranches.cpp

25–33

since the code here is pretty short and simple, how about we just add that onto what I've done here?

none of the transforms here is strictly subsumed by anything in simplifyCFG because that pass has to be semantics-preserving, whereas none of these three are

[arsenm]

llvm/tools/llvm-reduce/deltas/ReduceBranches.cpp

73

Do you need to call replaceSuccessorsPhiUsesWith or replacePhiUsesWith to avoid breaking those?

[regehr]

llvm/tools/llvm-reduce/deltas/ReduceBranches.cpp

73

let me look into it, thanks.

overall I'm not impressed with the elegance of the code in this function, all suggestions appreciated.

llvm/test/tools/llvm-reduce/remove-cond-branches-false.ll

+; RUN: llvm-reduce --delta-passes=cond-branches-false --test %python --test-arg %p/Inputs/remove-bbs.py -abort-on-invalid-reduction %s -o %t
+
+; RUN: FileCheck --check-prefix=CHECK-FINAL %s --input-file=%t
+; CHECK-FINAL-NOT: br i1
+; CHECK-FINAL: br label %x12
+
+define void @f1(ptr %interesting3, i32 %interesting2, i1 %b) {
+  %x3 = alloca ptr, i32 0, align 8
+  store ptr %interesting3, ptr %interesting3, align 8
+  switch i32 %interesting2, label %interesting1 [
+    i32 0, label %x6
+    i32 1, label %x11
+  ]
+
+x4:
+  %x5 = call ptr @f2()
+  br label %x10
+
+x10:
+  br label %x6
+
+x6:
+  br i1 %b, label %x11, label %x12
+
+x11:
+  br label %interesting1
+
+x12:
+  br label %interesting1
+
+interesting1:
+  ret void
+}
+
+declare ptr @f2()

llvm/test/tools/llvm-reduce/remove-cond-branches-true.ll

+; RUN: llvm-reduce --delta-passes=cond-branches-true --test %python --test-arg %p/Inputs/remove-bbs.py -abort-on-invalid-reduction %s -o %t
+
+; RUN: FileCheck --check-prefix=CHECK-FINAL %s --input-file=%t
+; CHECK-FINAL-NOT: br i1
+; CHECK-FINAL: br label %x11
+
+define void @f1(ptr %interesting3, i32 %interesting2, i1 %b) {
+  %x3 = alloca ptr, i32 0, align 8
+  store ptr %interesting3, ptr %interesting3, align 8
+  switch i32 %interesting2, label %interesting1 [
+    i32 0, label %x6
+    i32 1, label %x11
+  ]
+
+x4:
+  %x5 = call ptr @f2()
+  br label %x10
+
+x10:
+  br label %x6
+
+x6:
+  br i1 %b, label %x11, label %x12
+
+x11:
+  br label %interesting1
+
+x12:
+  br label %interesting1
+
+interesting1:
+  ret void
+}
+
+declare ptr @f2()

llvm/test/tools/llvm-reduce/remove-uncond-branches.ll

+; RUN: llvm-reduce --delta-passes=uncond-branches --test %python --test-arg %p/Inputs/remove-bbs.py -abort-on-invalid-reduction %s -o %t
+
+; RUN: FileCheck --check-prefix=CHECK-FINAL %s --input-file=%t
+; CHECK-FINAL-NOT: x4
+; CHECK-FINAL-NOT: x6
+; CHECK-FINAL-NOT: x10
+; CHECK-FINAL-NOT: x11
+
+define void @f1(ptr %interesting3, i32 %interesting2) {
+  %x3 = alloca ptr, i32 0, align 8
+  store ptr %interesting3, ptr %interesting3, align 8
+  switch i32 %interesting2, label %interesting1 [
+    i32 0, label %x6
+    i32 1, label %x11
+  ]
+
+x4:
+  %x5 = call ptr @f2()
+  br label %x10
+
+x10:
+  br label %interesting1
+
+x6:
+  br label %x11
+
+x11:
+  br label %interesting1
+
+interesting1:
+  ret void
+}
+
+declare ptr @f2()

llvm/tools/llvm-reduce/CMakeLists.txt

add_llvm_tool(llvm-reduce
   ReducerWorkItem.cpp
   TestRunner.cpp
   deltas/Delta.cpp
   deltas/Utils.cpp
   deltas/ReduceAliases.cpp
   deltas/ReduceArguments.cpp
   deltas/ReduceAttributes.cpp
   deltas/ReduceBasicBlocks.cpp
+  deltas/ReduceBranches.cpp
   deltas/ReduceFunctionBodies.cpp
   deltas/ReduceFunctions.cpp
   deltas/ReduceGlobalObjects.cpp
   deltas/ReduceGlobalValues.cpp
   deltas/ReduceGlobalVarInitializers.cpp
   deltas/ReduceGlobalVars.cpp
   deltas/ReduceInstructions.cpp
   deltas/ReduceMetadata.cpp

llvm/tools/llvm-reduce/DeltaManager.cpp

 #include "DeltaManager.h"
 #include "ReducerWorkItem.h"
 #include "TestRunner.h"
 #include "deltas/Delta.h"
 #include "deltas/ReduceAliases.h"
 #include "deltas/ReduceArguments.h"
 #include "deltas/ReduceAttributes.h"
 #include "deltas/ReduceBasicBlocks.h"
+#include "deltas/ReduceBranches.h"
 #include "deltas/ReduceFunctionBodies.h"
 #include "deltas/ReduceFunctions.h"
 #include "deltas/ReduceGlobalObjects.h"
 #include "deltas/ReduceGlobalValues.h"
 #include "deltas/ReduceGlobalVarInitializers.h"
 #include "deltas/ReduceGlobalVars.h"
 #include "deltas/ReduceIRReferences.h"
 #include "deltas/ReduceInstructionFlagsMIR.h"
do {                                                                         \
     DELTA_PASS("instructions", reduceInstructionsDeltaPass)                    \
     DELTA_PASS("simplify-instructions", simplifyInstructionsDeltaPass)         \
     DELTA_PASS("operands-zero", reduceOperandsZeroDeltaPass)                   \
     DELTA_PASS("operands-one", reduceOperandsOneDeltaPass)                     \
     DELTA_PASS("operands-nan", reduceOperandsNaNDeltaPass)                     \
     DELTA_PASS("operands-to-args", reduceOperandsToArgsDeltaPass)              \
     DELTA_PASS("operands-skip", reduceOperandsSkipDeltaPass)                   \
     DELTA_PASS("operand-bundles", reduceOperandBundesDeltaPass)                \
+    DELTA_PASS("cond-branches-true", reduceConditionalBranchesTrueDeltaPass)   \
+    DELTA_PASS("cond-branches-false", reduceConditionalBranchesFalseDeltaPass) \
+    DELTA_PASS("uncond-branches", reduceUnconditionalBranchesDeltaPass)        \
     DELTA_PASS("attributes", reduceAttributesDeltaPass)                        \
     DELTA_PASS("module-data", reduceModuleDataDeltaPass)                       \
   } while (false)
 
 #define DELTA_PASSES_MIR                                                       \
   do {                                                                         \
     DELTA_PASS("instructions", reduceInstructionsMIRDeltaPass)                 \
     DELTA_PASS("ir-instruction-references",                                    \

llvm/tools/llvm-reduce/deltas/ReduceBranches.h

+//===- ReduceBranches.h - Specialized Delta Pass --------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting branches from defined functions.
+//
+//===----------------------------------------------------------------------===//
+#ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEBRANCHES_H
+#define LLVM_TOOLS_LLVM_REDUCE_DELTAS_REDUCEBRANCHES_H
+
+#include "Delta.h"
+
+namespace llvm {
+void reduceConditionalBranchesTrueDeltaPass(TestRunner &Test);
+void reduceConditionalBranchesFalseDeltaPass(TestRunner &Test);
+void reduceUnconditionalBranchesDeltaPass(TestRunner &Test);
+} // namespace llvm
+
+#endif

llvm/tools/llvm-reduce/deltas/ReduceBranches.cpp

+//===- ReduceBranches.cpp - Specialized Delta Pass ------------------------===//
+//
+// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+// See https://llvm.org/LICENSE.txt for license information.
+// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+//
+//===----------------------------------------------------------------------===//
+//
+// This file implements a function which calls the Generic Delta pass in order
+// to reduce uninteresting branches from defined functions.
+//
+//===----------------------------------------------------------------------===//
+
+#include "ReduceBranches.h"
+#include "Utils.h"
+#include "llvm/IR/Instructions.h"
+#include "llvm/Transforms/Utils/BasicBlockUtils.h"
+
+using namespace llvm;
+
+/*
+ * for each conditional branch, try to turn it into an unconditional
+ * branch to its true target
+ */
+static void reduceConditionalBranchesTrue(Oracle &O, Module &Program) {
+  for (auto &F : Program) {
+    for (auto &BB : F) {
+      BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());
+      if (BI && BI->isConditional() && !O.shouldKeep())
+        ReplaceInstWithInst(BI, BranchInst::Create(BI->getSuccessor(0)));
+    }
+  }
+}
+
+/*
+ * for each conditional branch, try to turn it into an unconditional
+ * branch to its false target
+ */
+static void reduceConditionalBranchesFalse(Oracle &O, Module &Program) {
+  for (auto &F : Program) {
+    for (auto &BB : F) {
+      BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());
+      if (BI && BI->isConditional() && !O.shouldKeep())
+        ReplaceInstWithInst(BI, BranchInst::Create(BI->getSuccessor(1)));
+    }
+  }
+}
+
+///  Given a basic block terminated by an unconditional branch, move
+///  its instructions to the head of the successor BB and then update
+///  predecessors to skip over the block
+static bool pushInsnsToSuccessor(Oracle &O, BasicBlock *BB, BranchInst *BI) {
+  /// Feasibility checks before talking to the oracle
+  if (BB->isEntryBlock())
+    return false;
+  for (BasicBlock *Pred : predecessors(BB)) {
+    auto *TI = Pred->getTerminator();
+    if (!isa<BranchInst>(TI) && !isa<SwitchInst>(TI))
+      return false;
+  }
+
+  if (O.shouldKeep())
+    return false;
+
+  /// Branch around the BB we're trying to get rid of
+  BasicBlock *NewTarget = BI->getSuccessor(0);
+  for (BasicBlock *Pred : predecessors(BB)) {
+    BranchInst *BI = dyn_cast<BranchInst>(Pred->getTerminator());
+    if (BI) {
+      unsigned index = 0;
+      for (BasicBlock *TBB : successors(BI)) {
+        if (TBB == BB)
+          BI->setSuccessor(index, NewTarget);
+        ++index;
+      }
+    }
+    SwitchInst *SI = dyn_cast<SwitchInst>(Pred->getTerminator());
+    if (SI) {
+      unsigned index = 0;
+      for (BasicBlock *TBB : successors(SI)) {
+        if (TBB == BB)
+          SI->setSuccessor(index, NewTarget);
+        ++index;
+      }
+    }
+  }
+
+  /// Sink all instructions to the front of the new branch target
+  std::vector<Instruction *> Insns;
+  for (auto &I : *BB)
+    if (!I.isTerminator())
+      Insns.push_back(&I);
+  auto it = NewTarget->getFirstInsertionPt();
+  for (auto I : Insns)
+    I->moveBefore(*NewTarget, it);
+
+  return true;
+}
+
+static void reduceUnconditionalBranches(Oracle &O, Module &Program) {
+  SmallSet<BasicBlock *, 4> ToDelete;
+  for (auto &F : Program) {
+    for (auto &BB : F) {
+      BranchInst *BI = dyn_cast<BranchInst>(BB.getTerminator());
+      if (BI && BI->isUnconditional())
+        if (pushInsnsToSuccessor(O, &BB, BI))
+          ToDelete.insert(&BB);
+    }
+  }
+  for (auto *BB : ToDelete)
+    if (!BB->hasNPredecessorsOrMore(1))
+      BB->eraseFromParent();
+}
+
+void llvm::reduceConditionalBranchesTrueDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Conditional Branches to true target...\n";
+  runDeltaPass(Test, reduceConditionalBranchesTrue);
+}
+
+void llvm::reduceConditionalBranchesFalseDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Conditional Branches to false target...\n";
+  runDeltaPass(Test, reduceConditionalBranchesFalse);
+}
+
+void llvm::reduceUnconditionalBranchesDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing Unconditional Branches...\n";
+  runDeltaPass(Test, reduceUnconditionalBranches);
+}