llvm-reduce: Add conditional reduction passes

[arsenm]

Summary

Copy this technique from bugpoint. Before trying to blindly
delete blocks, try to fold branch conditions. This intuitively
makes more sense for a faster reduction, since you can find
dead paths in the function to prune out before trying to bisect
blocks in source order.

Seems to provide some speedup on my multi-hour reduction samples.

This does have the potential to produce testcases with unreachable
blocks. This is already a problem with the existing block
reduction pass. I'm struggling dealing with invalid reductions
in these cases, so in the future this should probably start
deleting those. However, I do sometimes try to reduce failures
in code that becomes unreachable, so I'm not totally sure
what to do here.

[arsenm]

08d1c43c7023a2e955c43fbf4c3f1635f91521e0

llvm/test/tools/llvm-reduce/reduce-conditionals.ll

+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=simplify-conditionals-true --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: FileCheck --check-prefixes=RESULT-TRUE %s < %t
+
+; RUN: llvm-reduce --abort-on-invalid-reduction --delta-passes=simplify-conditionals-false --test FileCheck --test-arg --check-prefixes=CHECK-INTERESTINGNESS --test-arg %s --test-arg --input-file %s -o %t
+; RUN: FileCheck --check-prefixes=RESULT-FALSE %s < %t
+
+; CHECK-INTERESTINGNESS-LABEL: @func(
+; CHECK-INTERESTINGNESS: store i32 1,
+
+; RESULT-TRUE: bb0:
+; RESULT-TRUE: store i32 0, ptr null, align 4
+; RESULT-TRUE-NEXT: store i32 1, ptr null, align 4
+; RESULT-TRUE-NEXT: br label %bb2
+; RESULT-TRUE-NOT: bb1
+
+
+; RESULT-FALSE: bb0:
+; RESULT-FALSE: store i32 0, ptr null, align 4
+; RESULT-FALSE-NEXT: br label %bb2
+
+; RESULT-FALSE: bb1: ; No predecessors!
+; RESULT-FALSE-NEXT: store i32 1, ptr null, align 4
+; RESULT-FALSE-NEXT: br label %bb3
+define void @func(i1 %cond0, i1 %cond1) {
+bb0:
+  store i32 0, ptr null
+  br i1 %cond0, label %bb1, label %bb2
+
+bb1:
+  store i32 1, ptr null
+  br i1 %cond1, label %bb2, label %bb3
+
+bb2:
+  store i32 2, ptr null
+  br label %bb3
+
+bb3:
+  ret void
+}

llvm/tools/llvm-reduce/DeltaManager.cpp

SkipDeltaPasses("skip-delta-passes",
                     cl::cat(LLVMReduceOptions), cl::CommaSeparated);
 
 #define DELTA_PASSES                                                           \
   do {                                                                         \
     DELTA_PASS("functions", reduceFunctionsDeltaPass)                          \
     DELTA_PASS("function-bodies", reduceFunctionBodiesDeltaPass)               \
     DELTA_PASS("special-globals", reduceSpecialGlobalsDeltaPass)               \
     DELTA_PASS("aliases", reduceAliasesDeltaPass)                              \
+    DELTA_PASS("simplify-conditionals-true", reduceConditionalsTrueDeltaPass)  \
+    DELTA_PASS("simplify-conditionals-false", reduceConditionalsFalseDeltaPass)\
     DELTA_PASS("basic-blocks", reduceBasicBlocksDeltaPass)                     \
     DELTA_PASS("global-values", reduceGlobalValuesDeltaPass)                   \
     DELTA_PASS("global-objects", reduceGlobalObjectsDeltaPass)                 \
     DELTA_PASS("global-initializers", reduceGlobalsInitializersDeltaPass)      \
     DELTA_PASS("global-variables", reduceGlobalsDeltaPass)                     \
     DELTA_PASS("di-metadata", reduceDIMetadataDeltaPass)                       \
     DELTA_PASS("metadata", reduceMetadataDeltaPass)                            \
     DELTA_PASS("arguments", reduceArgumentsDeltaPass)                          \

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

 
 #ifndef LLVM_TOOLS_LLVM_REDUCE_DELTAS_SIMPLIFYCFG_H
 #define LLVM_TOOLS_LLVM_REDUCE_DELTAS_SIMPLIFYCFG_H
 
 #include "Delta.h"
 
 namespace llvm {
 void reduceUsingSimplifyCFGDeltaPass(TestRunner &Test);
+void reduceConditionalsTrueDeltaPass(TestRunner &Test);
+void reduceConditionalsFalseDeltaPass(TestRunner &Test);
 } // namespace llvm
 
 #endif

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

 //===- ReduceUsingSimplifyCFG.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 call SimplifyCFG on individual basic blocks.
 //
 //===----------------------------------------------------------------------===//
 
 #include "ReduceUsingSimplifyCFG.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
+#include "llvm/IR/Constants.h"
+#include "llvm/IR/Instructions.h"
 #include "llvm/Transforms/Utils/Local.h"
 
 using namespace llvm;
 
 static void reduceUsingSimplifyCFG(Oracle &O, Module &Program) {
   SmallVector<BasicBlock *, 16> ToSimplify;
   for (auto &F : Program)
     for (auto &BB : F)
       if (!O.shouldKeep())
         ToSimplify.push_back(&BB);
   TargetTransformInfo TTI(Program.getDataLayout());
   for (auto *BB : ToSimplify)
     simplifyCFG(BB, TTI);
 }
 
 void llvm::reduceUsingSimplifyCFGDeltaPass(TestRunner &Test) {
   outs() << "*** Reducing using SimplifyCFG...\n";
   runDeltaPass(Test, reduceUsingSimplifyCFG);
 }
+static void reduceConditionals(Oracle &O, Module &M, bool Direction) {
+  SmallVector<BasicBlock *, 16> ToSimplify;
+
+  for (auto &F : M) {
+    for (auto &BB : F) {
+      auto *BR = dyn_cast<BranchInst>(BB.getTerminator());
+      if (!BR || !BR->isConditional() || O.shouldKeep())
+        continue;
+
+      if (Direction)
+        BR->setCondition(ConstantInt::getTrue(BR->getContext()));
+      else
+        BR->setCondition(ConstantInt::getFalse(BR->getContext()));
+
+      ToSimplify.push_back(&BB);
+    }
+  }
+
+  TargetTransformInfo TTI(M.getDataLayout());
+  for (auto *BB : ToSimplify)
+    simplifyCFG(BB, TTI);
+}
+
+void llvm::reduceConditionalsTrueDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing conditional branches to true...\n";
+  runDeltaPass(Test, [](Oracle &O, Module &M) { reduceConditionals(O, M, true); });
+}
+
+void llvm::reduceConditionalsFalseDeltaPass(TestRunner &Test) {
+  outs() << "*** Reducing conditional branches to false...\n";
+  runDeltaPass(Test, [](Oracle &O, Module &M) { reduceConditionals(O, M, false); });
+}