Index: llvm/test/tools/llvm-reduce/remove-cond-branches-false.ll =================================================================== --- /dev/null +++ llvm/test/tools/llvm-reduce/remove-cond-branches-false.ll @@ -0,0 +1,35 @@ +; 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() Index: llvm/test/tools/llvm-reduce/remove-cond-branches-true.ll =================================================================== --- /dev/null +++ llvm/test/tools/llvm-reduce/remove-cond-branches-true.ll @@ -0,0 +1,35 @@ +; 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() Index: llvm/test/tools/llvm-reduce/remove-uncond-branches.ll =================================================================== --- /dev/null +++ llvm/test/tools/llvm-reduce/remove-uncond-branches.ll @@ -0,0 +1,34 @@ +; 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() Index: llvm/tools/llvm-reduce/CMakeLists.txt =================================================================== --- llvm/tools/llvm-reduce/CMakeLists.txt +++ llvm/tools/llvm-reduce/CMakeLists.txt @@ -27,6 +27,7 @@ deltas/ReduceArguments.cpp deltas/ReduceAttributes.cpp deltas/ReduceBasicBlocks.cpp + deltas/ReduceBranches.cpp deltas/ReduceFunctionBodies.cpp deltas/ReduceFunctions.cpp deltas/ReduceGlobalObjects.cpp Index: llvm/tools/llvm-reduce/DeltaManager.cpp =================================================================== --- llvm/tools/llvm-reduce/DeltaManager.cpp +++ llvm/tools/llvm-reduce/DeltaManager.cpp @@ -19,6 +19,7 @@ #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" @@ -73,6 +74,9 @@ 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) Index: llvm/tools/llvm-reduce/deltas/ReduceBranches.h =================================================================== --- /dev/null +++ llvm/tools/llvm-reduce/deltas/ReduceBranches.h @@ -0,0 +1,24 @@ +//===- 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 Index: llvm/tools/llvm-reduce/deltas/ReduceBranches.cpp =================================================================== --- /dev/null +++ llvm/tools/llvm-reduce/deltas/ReduceBranches.cpp @@ -0,0 +1,128 @@ +//===- 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(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(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(TI) && !isa(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(Pred->getTerminator()); + if (BI) { + unsigned index = 0; + for (BasicBlock *TBB : successors(BI)) { + if (TBB == BB) + BI->setSuccessor(index, NewTarget); + ++index; + } + } + SwitchInst *SI = dyn_cast(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 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 ToDelete; + for (auto &F : Program) { + for (auto &BB : F) { + BranchInst *BI = dyn_cast(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); +}