Index: llvm/lib/Transforms/Utils/SimplifyCFG.cpp =================================================================== --- llvm/lib/Transforms/Utils/SimplifyCFG.cpp +++ llvm/lib/Transforms/Utils/SimplifyCFG.cpp @@ -143,6 +143,11 @@ cl::desc("Max size of a block which is still considered " "small enough to thread through")); +static cl::opt + CanonicalizeBranchPredicates("simplifycfg-canonicalize-branch-predicates", + cl::Hidden, cl::init(false), + cl::desc("Canonicalize branch predicates")); + STATISTIC(NumBitMaps, "Number of switch instructions turned into bitmaps"); STATISTIC(NumLinearMaps, "Number of switch instructions turned into linear mapping"); @@ -6010,11 +6015,58 @@ return PredPred; } +/// Predicate canonicalization reduces the number of patterns that need to be +/// matched by other transforms. For example, we may swap the operands of a +/// conditional branch or select to create a compare with a canonical (inverted) +/// predicate which is then more likely to be matched with other values. +static inline bool isCanonicalPredicate(CmpInst::Predicate Pred) { + switch (Pred) { + case CmpInst::ICMP_NE: + case CmpInst::ICMP_ULE: + case CmpInst::ICMP_SLE: + case CmpInst::ICMP_UGE: + case CmpInst::ICMP_SGE: + // TODO: There are 16 FCMP predicates. Should others be (not) canonical? + case CmpInst::FCMP_ONE: + case CmpInst::FCMP_OLE: + case CmpInst::FCMP_OGE: + return false; + default: + return true; + } +} + bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) { BasicBlock *BB = BI->getParent(); if (!Options.SimplifyCondBranch) return false; + bool Changed = false; + + // Change br (not X), label True, label False to: br X, label False, True + Value *X = nullptr; + if (CanonicalizeBranchPredicates && + match(BI, m_Br(m_Not(m_Value(X)), m_BasicBlock(), m_BasicBlock())) && + !isa(X)) { + // Swap Destinations and condition... + BI->swapSuccessors(); + BI->setOperand(0, X); + Changed = true; + } + + // Canonicalize, for example, icmp_ne -> icmp_eq or fcmp_one -> fcmp_oeq. + CmpInst::Predicate Pred; + if (CanonicalizeBranchPredicates && + match(BI, m_Br(m_OneUse(m_FCmp(Pred, m_Value(), m_Value())), + m_BasicBlock(), m_BasicBlock())) && + !isCanonicalPredicate(Pred)) { + // Swap destinations and condition. + CmpInst *Cond = cast(BI->getCondition()); + Cond->setPredicate(CmpInst::getInversePredicate(Pred)); + BI->swapSuccessors(); + Changed = true; + } + // Conditional branch if (isValueEqualityComparison(BI)) { // If we only have one predecessor, and if it is a branch on this value, @@ -6110,7 +6162,7 @@ if (mergeConditionalStores(PBI, BI, DL, TTI)) return requestResimplify(); - return false; + return Changed; } /// Check if passing a value to an instruction will cause undefined behavior. Index: llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll =================================================================== --- llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll +++ llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll @@ -1,6 +1,6 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt < %s -simplifycfg -switch-to-lookup=true -keep-loops=false -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s -; RUN: opt < %s -passes='simplify-cfg' -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s +; RUN: opt < %s -simplifycfg -simplifycfg-canonicalize-branch-predicates -switch-to-lookup=true -keep-loops=false -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s +; RUN: opt < %s -passes='simplify-cfg' -simplifycfg-canonicalize-branch-predicates -S -mtriple=x86_64-unknown-linux-gnu | FileCheck %s target datalayout = "e-p:64:64:64-i1:8:8-i8:8:8-i16:16:16-i32:32:32-i64:64:64-f32:32:32-f64:64:64-v64:64:64-v128:128:128-a0:0:64-s0:64:64-f80:128:128-n8:16:32:64-S128" target triple = "x86_64-unknown-linux-gnu" @@ -1337,8 +1337,8 @@ ; CHECK-NEXT: [[SWITCH_OFFSET:%.*]] = add i32 [[X]], 10 ; CHECK-NEXT: [[R_0:%.*]] = select i1 [[TMP0]], i32 [[SWITCH_OFFSET]], i32 0 ; CHECK-NEXT: [[CMP:%.*]] = icmp eq i32 [[R_0]], 0 -; CHECK-NEXT: [[DOTR_0:%.*]] = select i1 [[INVERTED_CMP]], i32 100, i32 [[R_0]] -; CHECK-NEXT: ret i32 [[DOTR_0]] +; CHECK-NEXT: [[R_0DOT:%.*]] = select i1 [[TMP0]], i32 [[R_0]], i32 100 +; CHECK-NEXT: ret i32 [[R_0DOT]] ; entry: switch i32 %x, label %sw.default [ Index: llvm/test/Transforms/SimplifyCFG/switch_msan.ll =================================================================== --- llvm/test/Transforms/SimplifyCFG/switch_msan.ll +++ llvm/test/Transforms/SimplifyCFG/switch_msan.ll @@ -1,5 +1,5 @@ ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py -; RUN: opt -S -simplifycfg < %s | FileCheck %s +; RUN: opt -S -simplifycfg -simplifycfg-canonicalize-branch-predicates < %s | FileCheck %s declare i8 @next_char(); @@ -17,7 +17,10 @@ ; CHECK-NEXT: [[C_10_OR_13:%.*]] = or i1 [[C_10]], [[C_13]] ; CHECK-NEXT: [[NEXT_MAYBE_UNDEF]] = or i1 [[MAYBE_UNDEF]], [[C_10_OR_13]] ; CHECK-NEXT: [[C_NOT_10_OR_13:%.*]] = xor i1 [[C_10_OR_13]], true -; CHECK-NEXT: br i1 [[C_NOT_10_OR_13]], label [[WHILE_BODY_I]], label [[WHILE_BODY_I_BREAK:%.*]] +; CHECK-NEXT: switch i8 [[C]], label [[WHILE_BODY_I]] [ +; CHECK-NEXT: i8 13, label %while.body.i.break +; CHECK-NEXT: i8 10, label %while.body.i.break +; CHECK-NEXT: ] ; CHECK: while.body.i.break: ; CHECK-NEXT: br i1 [[MAYBE_UNDEF]], label [[WHILE_BODY]], label [[SWITCH_EARLY_TEST:%.*]] ; CHECK: switch.early.test: @@ -69,7 +72,10 @@ ; CHECK-NEXT: [[C_10_OR_13:%.*]] = or i1 [[C_10]], [[C_13]] ; CHECK-NEXT: [[NEXT_MAYBE_UNDEF]] = or i1 [[MAYBE_UNDEF]], [[C_10_OR_13]] ; CHECK-NEXT: [[C_NOT_10_OR_13:%.*]] = xor i1 [[C_10_OR_13]], true -; CHECK-NEXT: br i1 [[C_NOT_10_OR_13]], label [[WHILE_BODY_I]], label [[WHILE_BODY_I_BREAK:%.*]] +; CHECK-NEXT: switch i8 [[C]], label [[WHILE_BODY_I]] [ +; CHECK-NEXT: i8 13, label %while.body.i.break +; CHECK-NEXT: i8 10, label %while.body.i.break +; CHECK-NEXT: ] ; CHECK: while.body.i.break: ; CHECK-NEXT: br i1 [[NEXT_MAYBE_UNDEF]], label [[WHILE_BODY]], label [[RETURN:%.*]] ; CHECK: return: