From 93ca12299f3210e300c9ac4f0fd8d6ce5b7d7d60 Mon Sep 17 00:00:00 2001 From: Pete Cooper Date: Sat, 17 Dec 2011 06:32:38 +0000 Subject: [PATCH] SimplifyCFG now predicts some conditional branches to true or false depending on previous branch on same comparison operands. For example, if (a == b) { if (a > b) // this is false Fixes some of the issues on git-svn-id: https://llvm.org/svn/llvm-project/llvm/trunk@146822 91177308-0d34-0410-b5e6-96231b3b80d8 --- lib/Transforms/Utils/SimplifyCFG.cpp | 42 +++++ .../SimplifyCFG/PredictNestedBranch.ll | 152 ++++++++++++++++++ 2 files changed, 194 insertions(+) create mode 100644 test/Transforms/SimplifyCFG/PredictNestedBranch.ll diff --git a/lib/Transforms/Utils/SimplifyCFG.cpp b/lib/Transforms/Utils/SimplifyCFG.cpp index bf2cb49bdcd..d20e5a54762 100644 --- a/lib/Transforms/Utils/SimplifyCFG.cpp +++ b/lib/Transforms/Utils/SimplifyCFG.cpp @@ -12,6 +12,7 @@ //===----------------------------------------------------------------------===// #define DEBUG_TYPE "simplifycfg" +#include "llvm/Transforms/Utils/CmpInstAnalysis.h" #include "llvm/Transforms/Utils/Local.h" #include "llvm/Constants.h" #include "llvm/Instructions.h" @@ -1702,6 +1703,47 @@ static bool SimplifyCondBranchToCondBranch(BranchInst *PBI, BranchInst *BI) { } } + // Treat "if (cond1) { if (cond2) {} }" as "cond1 & cond2" and fold. + // This gives us the value of what cond2 is given cond1 is already known to + // be true. + if (ICmpInst *LHS = dyn_cast(PBI->getCondition())) { + if (ICmpInst *RHS = dyn_cast(BI->getCondition())) { + ICmpInst::Predicate LHSCC = LHS->getPredicate(), + RHSCC = RHS->getPredicate(); + if (PredicatesFoldable(LHSCC, RHSCC)) { + if (LHS->getOperand(0) == RHS->getOperand(1) && + LHS->getOperand(1) == RHS->getOperand(0)) + LHS->swapOperands(); + if (LHS->getOperand(0) == RHS->getOperand(0) && + LHS->getOperand(1) == RHS->getOperand(1) && + BB->getSinglePredecessor()) { + Value *Op0 = LHS->getOperand(0), *Op1 = LHS->getOperand(1); + bool CondIsTrue = PBI->getSuccessor(0) == BB; + unsigned LHSCode = getICmpCode(LHS, !CondIsTrue); + unsigned RHSCode = getICmpCode(RHS); + unsigned Code = LHSCode & RHSCode; + + Value *ConstantCondition = NULL; + // If the resultant code is the same as the LHS code then as that + // code is known to be true we can make RHS now be true. + if (Code == LHSCode) + ConstantCondition = ConstantInt::get( + CmpInst::makeCmpResultType(LHS->getType()), 1); + else { + bool isSigned = LHS->isSigned() || RHS->isSigned(); + CmpInst::Predicate IgnoredNewPred; + ConstantCondition = getICmpValue(isSigned, Code, Op0, Op1, + IgnoredNewPred); + } + if (ConstantCondition) { + RHS->replaceAllUsesWith(ConstantCondition); + return true; + } + } + } + } + } + // If this is a conditional branch in an empty block, and if any // predecessors is a conditional branch to one of our destinations, // fold the conditions into logical ops and one cond br. diff --git a/test/Transforms/SimplifyCFG/PredictNestedBranch.ll b/test/Transforms/SimplifyCFG/PredictNestedBranch.ll new file mode 100644 index 00000000000..dd854ec4988 --- /dev/null +++ b/test/Transforms/SimplifyCFG/PredictNestedBranch.ll @@ -0,0 +1,152 @@ + +; RUN: opt < %s -simplifycfg -dce -S | FileCheck %s + +; Test that when == is true, all 6 comparisons evaluate to true or false +; ie, a == b implies a > b is false, but a >= b is true, and so on +define void @testEqTrue(i32 %a, i32 %b) { +; CHECK: @testEqTrue +; CHECK: icmp eq i32 %a, %b +; CHECK: call void @_Z1gi(i32 0) +; a == b implies a == b +; CHECK-NEXT: call void @_Z1gi(i32 1) +; a == b implies a >= b +; CHECK-NEXT: call void @_Z1gi(i32 3) +; a == b implies a <= b +; CHECK-NEXT: call void @_Z1gi(i32 4) +; CHECK: ret void +entry: + %cmp = icmp eq i32 %a, %b + br i1 %cmp, label %if.then, label %if.end18 + +if.then: ; preds = %entry + call void @_Z1gi(i32 0) + %cmp1 = icmp eq i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: ; preds = %if.then + call void @_Z1gi(i32 1) + br label %if.end + +if.end: ; preds = %if.then2, %if.then + %cmp3 = icmp ne i32 %a, %b + br i1 %cmp3, label %if.then4, label %if.end5 + +if.then4: ; preds = %if.end + call void @_Z1gi(i32 2) + br label %if.end5 + +if.end5: ; preds = %if.then4, %if.end + %cmp6 = icmp sge i32 %a, %b + br i1 %cmp6, label %if.then7, label %if.end8 + +if.then7: ; preds = %if.end5 + call void @_Z1gi(i32 3) + br label %if.end8 + +if.end8: ; preds = %if.then7, %if.end5 + %cmp9 = icmp sle i32 %a, %b + br i1 %cmp9, label %if.then10, label %if.end11 + +if.then10: ; preds = %if.end8 + call void @_Z1gi(i32 4) + br label %if.end11 + +if.end11: ; preds = %if.then10, %if.end8 + %cmp12 = icmp sgt i32 %a, %b + br i1 %cmp12, label %if.then13, label %if.end14 + +if.then13: ; preds = %if.end11 + call void @_Z1gi(i32 5) + br label %if.end14 + +if.end14: ; preds = %if.then13, %if.end11 + %cmp15 = icmp slt i32 %a, %b + br i1 %cmp15, label %if.then16, label %if.end18 + +if.then16: ; preds = %if.end14 + call void @_Z1gi(i32 6) + br label %if.end18 + +if.end18: ; preds = %if.end14, %if.then16, %entry + ret void +} + +; Test that when == is false, all 6 comparisons evaluate to true or false +; ie, a == b implies a > b is false, but a >= b is true, and so on +define void @testEqFalse(i32 %a, i32 %b) { +; CHECK: @testEqFalse +; CHECK: icmp eq i32 %a, %b +; CHECK: call void @_Z1gi(i32 0) +; CHECK-NOT: call void @_Z1gi(i32 1) +; CHECK-NOT: icmp ne +; CHECK: call void @_Z1gi(i32 2) +; CHECK: icmp sge +; CHECK: call void @_Z1gi(i32 3) +; CHECK: icmp sle +; CHECK: call void @_Z1gi(i32 4) +; CHECK: icmp sgt +; CHECK: call void @_Z1gi(i32 5) +; CHECK: icmp slt +; CHECK: call void @_Z1gi(i32 6) +; CHECK: ret void +entry: + %cmp = icmp eq i32 %a, %b + br i1 %cmp, label %if.then, label %if.else + +if.then: ; preds = %entry + call void @_Z1gi(i32 0) + br label %if.end18 + +if.else: + %cmp1 = icmp eq i32 %a, %b + br i1 %cmp1, label %if.then2, label %if.end + +if.then2: ; preds = %if.then + call void @_Z1gi(i32 1) + br label %if.end + +if.end: ; preds = %if.then2, %if.then + %cmp3 = icmp ne i32 %a, %b + br i1 %cmp3, label %if.then4, label %if.end5 + +if.then4: ; preds = %if.end + call void @_Z1gi(i32 2) + br label %if.end5 + +if.end5: ; preds = %if.then4, %if.end + %cmp6 = icmp sge i32 %a, %b + br i1 %cmp6, label %if.then7, label %if.end8 + +if.then7: ; preds = %if.end5 + call void @_Z1gi(i32 3) + br label %if.end8 + +if.end8: ; preds = %if.then7, %if.end5 + %cmp9 = icmp sle i32 %a, %b + br i1 %cmp9, label %if.then10, label %if.end11 + +if.then10: ; preds = %if.end8 + call void @_Z1gi(i32 4) + br label %if.end11 + +if.end11: ; preds = %if.then10, %if.end8 + %cmp12 = icmp sgt i32 %a, %b + br i1 %cmp12, label %if.then13, label %if.end14 + +if.then13: ; preds = %if.end11 + call void @_Z1gi(i32 5) + br label %if.end14 + +if.end14: ; preds = %if.then13, %if.end11 + %cmp15 = icmp slt i32 %a, %b + br i1 %cmp15, label %if.then16, label %if.end18 + +if.then16: ; preds = %if.end14 + call void @_Z1gi(i32 6) + br label %if.end18 + +if.end18: ; preds = %if.end14, %if.then16, %entry + ret void +} + +declare void @_Z1gi(i32) -- 2.34.1