[SimplifyCFG] Canonicalize branch predicates

[yrouban]

Summary

Canonicalize branch predicates as it is done by InstCombine.
This patch is the first step to move the branch predicate canonicalization transformation from InstCombine to SimplifyCFG.
This move is needed to make InstCombine preserve CFG. Currently we have a bug 46098 which reports PostDomTree invalidation once InstCombine swaps branches in a post-order unreachable block. See discussion in D81089.

The new transformation is disabled by default (the new flag simplifycfg-canonicalize-branch-predicates). So the patch is safe but. The sensitive tests are fixed and get additional option -simplifycfg-canonicalize-branch-predicates.

[kuhar]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6047

nit: would it be possible to come up with a more descriptive name? Maybe something like newCond, conditionCandidate, etc.

6053

BI->setCondition(X)?

6064

nit: auto *Cond = ...

[yrouban]

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

6060

m_FCmp should be change to m_Cmp

[lebedev.ri]

Abandon now that D84763 has resolved the base problem?

[lebedev.ri]

@yrouban abandon patchset now that https://bugs.llvm.org/show_bug.cgi?id=46098 has been addressed?

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

static cl::opt<unsigned> MaxSpeculationDepth(
     cl::desc("Limit maximum recursion depth when calculating costs of "
              "speculatively executed instructions"));
 
 static cl::opt<int>
 MaxSmallBlockSize("simplifycfg-max-small-block-size", cl::Hidden, cl::init(10),
                   cl::desc("Max size of a block which is still considered "
                            "small enough to thread through"));
 
+static cl::opt<bool>
+    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");
 STATISTIC(NumLookupTables,
           "Number of switch instructions turned into lookup tables");
 STATISTIC(
     NumLookupTablesHoles,
     "Number of switch instructions turned into lookup tables (holes checked)");
for (auto *P : predecessors(BB)) {
     BasicBlock *PPred = P->getSinglePredecessor();
     if (!PPred || (PredPred && PredPred != PPred))
       return nullptr;
     PredPred = PPred;
   }
   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<Constant>(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<CmpInst>(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,
     // see if that predecessor totally determines the outcome of this
     // switch.
     if (BasicBlock *OnlyPred = BB->getSinglePredecessor())
       if (SimplifyEqualityComparisonWithOnlyPredecessor(BI, OnlyPred, Builder))
         return requestResimplify();
bool SimplifyCFGOpt::simplifyCondBranch(BranchInst *BI, IRBuilder<> &Builder) {
   // Look for diamond patterns.
   if (MergeCondStores)
     if (BasicBlock *PrevBB = allPredecessorsComeFromSameSource(BB))
       if (BranchInst *PBI = dyn_cast<BranchInst>(PrevBB->getTerminator()))
         if (PBI != BI && PBI->isConditional())
           if (mergeConditionalStores(PBI, BI, DL, TTI))
             return requestResimplify();
 
-  return false;
+  return Changed;
 }
 
 /// Check if passing a value to an instruction will cause undefined behavior.
 static bool passingValueIsAlwaysUndefined(Value *V, Instruction *I) {
   Constant *C = dyn_cast<Constant>(V);
   if (!C)
     return false;
 

llvm/test/Transforms/SimplifyCFG/X86/switch_to_lookup_table.ll

 ; 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<no-keep-loops;switch-to-lookup>' -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<no-keep-loops;switch-to-lookup>' -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"
 
 ; The table for @f
 ; CHECK: @switch.table.f = private unnamed_addr constant [7 x i32] [i32 55, i32 123, i32 0, i32 -1, i32 27, i32 62, i32 1], align 4
 
 ; The char table for char
 ; CHECK: @switch.table.char = private unnamed_addr constant [9 x i8] c"7{\00\FF\1B>\01!T", align 1

 define i32 @reuse_cmp1(i32 %x) {
 ; CHECK-LABEL: @reuse_cmp1(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    [[TMP0:%.*]] = icmp ult i32 [[X:%.*]], 4
 ; CHECK-NEXT:    [[INVERTED_CMP:%.*]] = xor i1 [[TMP0]], true
 ; 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 [
   i32 0, label %sw.bb
   i32 1, label %sw.bb1
   i32 2, label %sw.bb2
   i32 3, label %sw.bb3
   ]

llvm/test/Transforms/SimplifyCFG/switch_msan.ll

 ; 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();
 
 define void @test_no_msan() {
 ; CHECK-LABEL: @test_no_msan(
 ; CHECK-NEXT:  entry:
 ; CHECK-NEXT:    br label [[WHILE_BODY:%.*]]
 ; CHECK:       while.body:
 ; CHECK-NEXT:    br label [[WHILE_BODY_I:%.*]]
 ; CHECK:       while.body.i:
 ; CHECK-NEXT:    [[MAYBE_UNDEF:%.*]] = phi i1 [ undef, [[WHILE_BODY]] ], [ [[NEXT_MAYBE_UNDEF:%.*]], [[WHILE_BODY_I]] ]
 ; CHECK-NEXT:    [[C:%.*]] = call fastcc signext i8 @next_char()
 ; CHECK-NEXT:    [[C_10:%.*]] = icmp eq i8 [[C]], 10
 ; CHECK-NEXT:    [[C_13:%.*]] = icmp eq i8 [[C]], 13
 ; 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:
 ; CHECK-NEXT:    switch i8 [[C]], label [[RETURN:%.*]] [
 ; CHECK-NEXT:    i8 13, label [[WHILE_BODY]]
 ; CHECK-NEXT:    i8 10, label [[WHILE_BODY]]
 ; CHECK-NEXT:    ]
 ; CHECK:       return:

 ; CHECK:       while.body.i:
 ; CHECK-NEXT:    [[MAYBE_UNDEF:%.*]] = phi i1 [ undef, [[WHILE_BODY]] ], [ [[NEXT_MAYBE_UNDEF:%.*]], [[WHILE_BODY_I]] ]
 ; CHECK-NEXT:    [[C:%.*]] = call fastcc signext i8 @next_char()
 ; CHECK-NEXT:    [[C_10:%.*]] = icmp eq i8 [[C]], 10
 ; CHECK-NEXT:    [[C_13:%.*]] = icmp eq i8 [[C]], 13
 ; 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:
 ; CHECK-NEXT:    ret void
 ;
 
 entry:
   br label %while.body