[SimplifyCFG] Consider cost of combining predicates.

[samparker]

Summary

Modify FoldBranchToCommonDest to consider the cost of inserting instructions when attempting to combine predicates to fold blocks. The threshold can be controlled via a new option: -simplifycfg-branch-fold-threshold which defaults to '2' to allow the insertion of a not and another logical operator.

[samparker]

I didn't see any changes for X86 or AArch64, but this can help on arm:

Metric: size..text                                                                                                                                                                                                    
                                                                                                                                                                                                                      
Program                                                                                              master  modified                                diff                                                              
                          test-suite :: SingleSource/Benchmarks/Shootout-C++/Shootout-C++-sieve.test     980     968                                -1.2%                                                             
                           test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C++/miniFE/miniFE.test   29180   28860                                -1.1%                                                             
                          test-suite :: SingleSource/Benchmarks/Shootout-C++/Shootout-C++-hash2.test    2004    1984                                -1.0%                                                             
                               test-suite :: MultiSource/Benchmarks/FreeBench/analyzer/analyzer.test    5352    5400                                 0.9%                                                             
                           test-suite :: SingleSource/Benchmarks/Shootout-C++/Shootout-C++-hash.test    1772    1760                                -0.7%                                                             
                     test-suite :: MultiSource/Benchmarks/mediabench/mpeg2/mpeg2dec/mpeg2decode.test   23016   23168                                 0.7%                                                             
                                         test-suite :: MultiSource/Applications/SIBsim4/SIBsim4.test   20120   20248                                 0.6%                                                             
                        test-suite :: SingleSource/Benchmarks/Shootout-C++/Shootout-C++-moments.test    1972    1960                                -0.6%                                                             
                                          test-suite :: SingleSource/Benchmarks/Misc-C++/bigfib.test    3328    3312                                -0.5%                                                             
                                               test-suite :: MultiSource/Benchmarks/PAQ8p/paq8p.test   40832   40636                                -0.5%                                                             
                                            test-suite :: MultiSource/Applications/kimwitu++/kc.test  242612  243640                                 0.4%                                                             
                                          test-suite :: MultiSource/Benchmarks/McCat/18-imp/imp.test    7620    7588                                -0.4%                                                             
                                             test-suite :: MultiSource/Benchmarks/Ptrdist/bc/bc.test   20736   20816                                 0.4%                                                             
                       test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C/SimpleMOC/SimpleMOC.test   14828   14772                                -0.4%                                                             
                                      test-suite :: MultiSource/Benchmarks/mafft/pairlocalalign.test  168648  168016                                -0.4%                                                             
                                     test-suite :: MultiSource/Applications/lambda-0.1.3/lambda.test   13140   13092                                -0.4%                                                             
                                      test-suite :: MultiSource/Benchmarks/VersaBench/dbms/dbms.test    8228    8204                                -0.3%                                                             
                                    test-suite :: MultiSource/Benchmarks/Prolangs-C/gnugo/gnugo.test    8520    8544                                 0.3%                                                             
                                 test-suite :: MultiSource/Benchmarks/FreeBench/distray/distray.test    3148    3140                                -0.3%                                                             
                             test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C++/HPCCG/HPCCG.test    7128    7112                                -0.2%                                                             
                 test-suite :: MultiSource/Benchmarks/MiBench/consumer-typeset/consumer-typeset.test  278308  277708                                -0.2%                                                             
                             test-suite :: MultiSource/Benchmarks/mediabench/jpeg/jpeg-6a/cjpeg.test   61936   62064                                 0.2%                                                             
                                   test-suite :: MultiSource/Benchmarks/Ptrdist/anagram/anagram.test    1940    1944                                 0.2%                                                             
                                    test-suite :: MultiSource/Benchmarks/Prolangs-C/agrep/agrep.test   23836   23788                                -0.2%                                                             
                                test-suite :: MultiSource/Benchmarks/Trimaran/enc-3des/enc-3des.test    8100    8116                                 0.2%                                                             
                                        test-suite :: MultiSource/Applications/JM/lencod/lencod.test  317548  316956                                -0.2%                                                             
                                  test-suite :: MicroBenchmarks/LoopInterchange/LoopInterchange.test   60248   60136                                -0.2%                                                             
                                  test-suite :: MicroBenchmarks/LCALS/SubsetBRawLoops/lcalsBRaw.test   87140   86980                                -0.2%                                                             
                            test-suite :: MicroBenchmarks/LCALS/SubsetBLambdaLoops/lcalsBLambda.test   87156   86996                                -0.2%                                                             
                                    test-suite :: MicroBenchmarks/ImageProcessing/Dilate/Dilate.test   61496   61384                                -0.2%                                                             
        test-suite :: MicroBenchmarks/ImageProcessing/AnisotropicDiffusion/AnisotropicDiffusion.test   61800   61688                                -0.2%                                                             
                                        test-suite :: MicroBenchmarks/ImageProcessing/Blur/blur.test   62136   62024                                -0.2%                                                             
                      test-suite :: MicroBenchmarks/ImageProcessing/Interpolation/Interpolation.test   62264   62152                                -0.2%                                                             
                                                    test-suite :: MicroBenchmarks/harris/harris.test   62584   62472                                -0.2%          
                            test-suite :: MicroBenchmarks/LCALS/SubsetALambdaLoops/lcalsALambda.test   90788   90628                                -0.2%                                                             
                                  test-suite :: MicroBenchmarks/LCALS/SubsetCRawLoops/lcalsCRaw.test   91924   91764                                -0.2%                                                             
                            test-suite :: MicroBenchmarks/LCALS/SubsetCLambdaLoops/lcalsCLambda.test   92020   91860                                -0.2%                                                             
                         test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C++/PENNANT/PENNANT.test   32516   32460                                -0.2%                                                             
                                  test-suite :: MicroBenchmarks/LCALS/SubsetARawLoops/lcalsARaw.test   89972   89828                                -0.2%                                                             
               test-suite :: MicroBenchmarks/ImageProcessing/BilateralFiltering/BilateralFilter.test   61752   61656                                -0.2%                                                             
                                    test-suite :: MicroBenchmarks/ImageProcessing/Dither/Dither.test   62424   62328                                -0.2%                                                             
                                       test-suite :: SingleSource/Benchmarks/Misc-C++-EH/spirit.test   32352   32304                                -0.1%                                                             
                                             test-suite :: MultiSource/Applications/SPASS/SPASS.test  201448  201160                                -0.1%                                                             
                       test-suite :: MultiSource/Benchmarks/MiBench/consumer-jpeg/consumer-jpeg.test   60008   60088                                 0.1%                                                             
                                             test-suite :: MultiSource/Applications/sgefa/sgefa.test    6096    6104                                 0.1%                                                             
                                             test-suite :: MultiSource/Applications/spiff/spiff.test   12200   12184                                -0.1%                                                             
                                     test-suite :: MultiSource/Benchmarks/tramp3d-v4/tramp3d-v4.test  198988  198756                                -0.1%                                                             
                                        test-suite :: MicroBenchmarks/MemFunctions/MemFunctions.test  121704  121576                                -0.1%                                                             
                                         test-suite :: MultiSource/Applications/sqlite3/sqlite3.test  168360  168184                                -0.1%                                                             
                                                 test-suite :: MultiSource/Applications/lua/lua.test   61496   61432                                -0.1%                                                             
                                test-suite :: SingleSource/Benchmarks/Adobe-C++/stepanov_vector.test    7984    7976                                -0.1%                                                             
                                           test-suite :: MultiSource/Applications/oggenc/oggenc.test   90108   90020                                -0.1%                                                             
                                    test-suite :: MultiSource/Benchmarks/Prolangs-C++/city/city.test    4208    4212                                 0.1%                                                             
                           test-suite :: MultiSource/Benchmarks/FreeBench/fourinarow/fourinarow.test    4312    4316                                 0.1%                                                             
                                          test-suite :: MultiSource/Applications/d/make_dparser.test   43964   44004                                 0.1%                                                             
                                  test-suite :: MultiSource/Benchmarks/Prolangs-C/bison/mybison.test   27552   27528                                -0.1%                                                             
                                       test-suite :: SingleSource/Benchmarks/Linpack/linpack-pc.test    4748    4752                                 0.1%                                                             
                                         test-suite :: MultiSource/Benchmarks/MallocBench/gs/gs.test   78096   78032                                -0.1%                                                             
                                         test-suite :: MultiSource/Applications/minisat/minisat.test    9948    9940                                -0.1%                                                             
                          test-suite :: MultiSource/Applications/ALAC/decode/alacconvert-decode.test   19904   19888                                -0.1%                                                             
                          test-suite :: MultiSource/Applications/ALAC/encode/alacconvert-encode.test   19904   19888                                -0.1%                                                             
                                       test-suite :: MultiSource/Benchmarks/7zip/7zip-benchmark.test  324144  323888                                -0.1%                                                             
                             test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C++/CLAMR/CLAMR.test  218644  218492                                -0.1%                                                             
                                                 test-suite :: MultiSource/Applications/hbd/hbd.test   18508   18520                                 0.1%          
                                   test-suite :: MultiSource/Benchmarks/MallocBench/cfrac/cfrac.test   12360   12368                                 0.1%                                                             
                           test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C/miniGMG/miniGMG.test   26096   26080                                -0.1%                                                             
                                        test-suite :: MultiSource/Applications/JM/ldecod/ldecod.test  128216  128288                                 0.1%                                                             
                                       test-suite :: MultiSource/Applications/hexxagon/hexxagon.test    7248    7252                                 0.1%                                                             
                           test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C/miniAMR/miniAMR.test   31676   31692                                 0.1%                                                             
                                         test-suite :: MultiSource/Applications/obsequi/Obsequi.test   17468   17460                                -0.0%                                                             
                                 test-suite :: MultiSource/Benchmarks/DOE-ProxyApps-C/CoMD/CoMD.test   20116   20108                                -0.0%                                                             
                       test-suite :: MultiSource/Benchmarks/MiBench/consumer-lame/consumer-lame.test   69620   69644                                 0.0%                                                             
                               test-suite :: MultiSource/Benchmarks/ASCI_Purple/SMG2000/smg2000.test   89568   89592                                 0.0%                                                             
                                               test-suite :: MultiSource/Applications/siod/siod.test   47108   47100                                -0.0%                                                             
                                             test-suite :: MultiSource/Benchmarks/Bullet/bullet.test  296520  296476                                -0.0%                                                             
                             test-suite :: MultiSource/Benchmarks/MallocBench/espresso/espresso.test   68272   68280                                 0.0%                                                             
                                         test-suite :: MultiSource/Applications/ClamAV/clamscan.test  246060  246084                                 0.0%
                                                                                  Geomean difference                                                -0.0%                                                             
              master  modified                                diff                                                                                                                                              
count  310.000000     310.000000                              310.000000                                                                                                                                              
mean   19696.000000   19682.335484                           -0.000258                                                                                                                                                
std    48827.048064   48790.944109                            0.001668                                                                                                                                                
min    292.000000     292.000000                             -0.012245                                                                                                                                                
25%    1089.000000    1089.000000                             0.000000                                                                                                                                                
50%    2772.000000    2772.000000                             0.000000                                                                                                                                                
75%    10185.000000   10185.000000                            0.000000                                                                                                                                                
max    324144.000000  323888.000000                           0.008969

[asbirlea]

Please clang-format

llvm/include/llvm/Transforms/Utils/Local.h

 /// and parallel-or mode to collapse if-conditions and merge if-regions with
 /// identical statements.
 bool FlattenCFG(BasicBlock *BB, AAResults *AA = nullptr);
 
 /// If this basic block is ONLY a setcc and a branch, and if a predecessor
 /// branches to us and one of our successors, fold the setcc into the
 /// predecessor and use logical operations to pick the right destination.
 bool FoldBranchToCommonDest(BranchInst *BI, MemorySSAUpdater *MSSAU = nullptr,
+                            const TargetTransformInfo *TTI = nullptr,
                             unsigned BonusInstThreshold = 1);
 
 /// This function takes a virtual register computed by an Instruction and
 /// replaces it with a slot in the stack frame, allocated via alloca.
 /// This allows the CFG to be changed around without fear of invalidating the
 /// SSA information for the value. It returns the pointer to the alloca inserted
 /// to create a stack slot for X.
 AllocaInst *DemoteRegToStack(Instruction &X,

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"));
 
+// Two is chosen to allow one negation and a logical combine.
+static cl::opt<unsigned>
+    BranchFoldThreshold("simplifycfg-branch-fold-threshold", cl::Hidden,
+                        cl::init(2),
+                        cl::desc("Maximum cost of combining conditions when "
+                                 "folding branches"));
+
 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)");
if (PredHasWeights || SuccHasWeights) {
     return false;
   }
 }
 
 /// If this basic block is simple enough, and if a predecessor branches to us
 /// and one of our successors, fold the block into the predecessor and use
 /// logical operations to pick the right destination.
 bool llvm::FoldBranchToCommonDest(BranchInst *BI, MemorySSAUpdater *MSSAU,
+                                  const TargetTransformInfo *TTI,
                                   unsigned BonusInstThreshold) {
   BasicBlock *BB = BI->getParent();
 
   const unsigned PredCount = pred_size(BB);
 
   bool Changed = false;
+  TargetTransformInfo::TargetCostKind CostKind =
+    BB->getParent()->hasMinSize() ? TargetTransformInfo::TCK_CodeSize
+                                  : TargetTransformInfo::TCK_SizeAndLatency;
 
   Instruction *Cond = nullptr;
   if (BI->isConditional())
     Cond = dyn_cast<Instruction>(BI->getCondition());
   else {
     // For unconditional branch, check for a simple CFG pattern, where
     // BB has a single predecessor and BB's successor is also its predecessor's
     // successor. If such pattern exists, check for CSE between BB and its
if (BI->isConditional()) {
       } else {
         continue;
       }
     } else {
       if (PBI->getSuccessor(0) != TrueDest && PBI->getSuccessor(1) != TrueDest)
         continue;
     }
 
+    // Check the cost of inserting the necessary logic before performing the
+    // transformation.
+    if (TTI && Opc != Instruction::BinaryOpsEnd) {
+      Type *Ty = BI->getCondition()->getType();
+      unsigned Cost = TTI->getArithmeticInstrCost(Opc, Ty, CostKind);
+      if (InvertPredCond && (!PBI->getCondition()->hasOneUse() ||
+          !isa<CmpInst>(PBI->getCondition())))
+        Cost += TTI->getArithmeticInstrCost(Instruction::Xor, Ty, CostKind);
+
+      if (Cost > BranchFoldThreshold)
+        continue;
+    }
+
     LLVM_DEBUG(dbgs() << "FOLDING BRANCH TO COMMON DEST:\n" << *PBI << *BB);
     Changed = true;
 
     IRBuilder<> Builder(PBI);
 
     // If we need to invert the condition in the pred block to match, do so now.
     if (InvertPredCond) {
       Value *NewCond = PBI->getCondition();
if (LandingPadInst *LPad = dyn_cast<LandingPadInst>(I)) {
     if (I->isTerminator() && TryToMergeLandingPad(LPad, BI, BB))
       return true;
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and our successor, fold the comparison into the
   // predecessor and use logical operations to update the incoming value
   // for PHI nodes in common successor.
-  if (FoldBranchToCommonDest(BI, nullptr, Options.BonusInstThreshold))
+  if (FoldBranchToCommonDest(BI, nullptr, &TTI, Options.BonusInstThreshold))
     return requestResimplify();
   return false;
 }
 
 static BasicBlock *allPredecessorsComeFromSameSource(BasicBlock *BB) {
   BasicBlock *PredPred = nullptr;
   for (auto *P : predecessors(BB)) {
     BasicBlock *PPred = P->getSinglePredecessor();
if (Imp) {
     BI->setCondition(TorF);
     RecursivelyDeleteTriviallyDeadInstructions(OldCond);
     return requestResimplify();
   }
 
   // If this basic block is ONLY a compare and a branch, and if a predecessor
   // branches to us and one of our successors, fold the comparison into the
   // predecessor and use logical operations to pick the right destination.
-  if (FoldBranchToCommonDest(BI, nullptr, Options.BonusInstThreshold))
+  if (FoldBranchToCommonDest(BI, nullptr, &TTI, Options.BonusInstThreshold))
     return requestResimplify();
 
   // We have a conditional branch to two blocks that are only reachable
   // from BI.  We know that the condbr dominates the two blocks, so see if
   // there is any identical code in the "then" and "else" blocks.  If so, we
   // can hoist it up to the branching block.
   if (BI->getSuccessor(0)->getSinglePredecessor()) {
     if (BI->getSuccessor(1)->getSinglePredecessor()) {

llvm/test/Transforms/SimplifyCFG/ARM/branch-fold-threshold.ll

cond.false:
   br label %cond.end
 
 cond.end:
   %cond = phi i32 [ %0, %cond.false ], [ 0, %lor.lhs.false ], [ 0, %entry ]
   ret i32 %cond
 }
 
 define i32 @or_predicate_minsize(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input) #0 {
-; CHECK-LABEL: @or_predicate_minsize(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[D:%.*]], 3
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
-; CHECK:       cond.false:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
-; CHECK-NEXT:    br label [[COND_END]]
-; CHECK:       cond.end:
-; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[COND]]
+; THUMB-LABEL: @or_predicate_minsize(
+; THUMB-NEXT:  entry:
+; THUMB-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[D:%.*]], 3
+; THUMB-NEXT:    br i1 [[CMP]], label [[COND_END:%.*]], label [[LOR_LHS_FALSE:%.*]]
+; THUMB:       lor.lhs.false:
+; THUMB-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; THUMB-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; THUMB-NEXT:    br i1 [[CMP1]], label [[COND_END]], label [[COND_FALSE:%.*]]
+; THUMB:       cond.false:
+; THUMB-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; THUMB-NEXT:    br label [[COND_END]]
+; THUMB:       cond.end:
+; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; THUMB-NEXT:    ret i32 [[COND]]
+;
+; ARM-LABEL: @or_predicate_minsize(
+; ARM-NEXT:  entry:
+; ARM-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[D:%.*]], 3
+; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; ARM-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
+; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
+; ARM:       cond.false:
+; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; ARM-NEXT:    br label [[COND_END]]
+; ARM:       cond.end:
+; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; ARM-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %cmp = icmp sgt i32 %d, 3
   br i1 %cmp, label %cond.end, label %lor.lhs.false
 
 lor.lhs.false:
   %add = add nsw i32 %c, %a
   %cmp1 = icmp slt i32 %add, %b
   br i1 %cmp1, label %cond.end, label %cond.false
 
 cond.false:
   %0 = load i32, i32* %input, align 4
   br label %cond.end
 
 cond.end:
   %cond = phi i32 [ %0, %cond.false ], [ 0, %lor.lhs.false ], [ 0, %entry ]
   ret i32 %cond
 }
 
 define i32 @or_invert_predicate_minsize(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input) #0 {
-; CHECK-LABEL: @or_invert_predicate_minsize(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP:%.*]] = icmp sle i32 [[D:%.*]], 3
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
-; CHECK:       cond.false:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
-; CHECK-NEXT:    br label [[COND_END]]
-; CHECK:       cond.end:
-; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[COND]]
+; THUMB-LABEL: @or_invert_predicate_minsize(
+; THUMB-NEXT:  entry:
+; THUMB-NEXT:    [[CMP:%.*]] = icmp sgt i32 [[D:%.*]], 3
+; THUMB-NEXT:    br i1 [[CMP]], label [[LOR_LHS_FALSE:%.*]], label [[COND_END:%.*]]
+; THUMB:       lor.lhs.false:
+; THUMB-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; THUMB-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; THUMB-NEXT:    br i1 [[CMP1]], label [[COND_END]], label [[COND_FALSE:%.*]]
+; THUMB:       cond.false:
+; THUMB-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; THUMB-NEXT:    br label [[COND_END]]
+; THUMB:       cond.end:
+; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; THUMB-NEXT:    ret i32 [[COND]]
+;
+; ARM-LABEL: @or_invert_predicate_minsize(
+; ARM-NEXT:  entry:
+; ARM-NEXT:    [[CMP:%.*]] = icmp sle i32 [[D:%.*]], 3
+; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; ARM-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP]], [[CMP1]]
+; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
+; ARM:       cond.false:
+; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; ARM-NEXT:    br label [[COND_END]]
+; ARM:       cond.end:
+; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; ARM-NEXT:    ret i32 [[COND]]
 ;
 entry:
   %cmp = icmp sgt i32 %d, 3
   br i1 %cmp, label %lor.lhs.false, label %cond.end
 
 lor.lhs.false:
   %add = add nsw i32 %c, %a
   %cmp1 = icmp slt i32 %add, %b
cond.false:
   br label %cond.end
 
 cond.end:
   %cond = phi i32 [ %0, %cond.false ], [ 0, %lor.lhs.false ], [ 0, %entry ]
   ret i32 %cond
 }
 
 define i32 @or_xor_predicate_minsize(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input, i1 %cmp) #0 {
-; CHECK-LABEL: @or_xor_predicate_minsize(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP_NOT]], [[CMP1]]
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
-; CHECK:       cond.false:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
-; CHECK-NEXT:    br label [[COND_END]]
-; CHECK:       cond.end:
-; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[COND]]
+; THUMB-LABEL: @or_xor_predicate_minsize(
+; THUMB-NEXT:  entry:
+; THUMB-NEXT:    br i1 [[CMP:%.*]], label [[LOR_LHS_FALSE:%.*]], label [[COND_END:%.*]]
+; THUMB:       lor.lhs.false:
+; THUMB-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; THUMB-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; THUMB-NEXT:    br i1 [[CMP1]], label [[COND_END]], label [[COND_FALSE:%.*]]
+; THUMB:       cond.false:
+; THUMB-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; THUMB-NEXT:    br label [[COND_END]]
+; THUMB:       cond.end:
+; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; THUMB-NEXT:    ret i32 [[COND]]
+;
+; ARM-LABEL: @or_xor_predicate_minsize(
+; ARM-NEXT:  entry:
+; ARM-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
+; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; ARM-NEXT:    [[OR_COND:%.*]] = or i1 [[CMP_NOT]], [[CMP1]]
+; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_END:%.*]], label [[COND_FALSE:%.*]]
+; ARM:       cond.false:
+; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; ARM-NEXT:    br label [[COND_END]]
+; ARM:       cond.end:
+; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; ARM-NEXT:    ret i32 [[COND]]
 ;
 entry:
   br i1 %cmp, label %lor.lhs.false, label %cond.end
 
 lor.lhs.false:
   %add = add nsw i32 %c, %a
   %cmp1 = icmp slt i32 %add, %b
   br i1 %cmp1, label %cond.end, label %cond.false
cond.false:
   br label %cond.end
 
 cond.end:
   %cond = phi i32 [ %0, %cond.false ], [ 0, %lor.lhs.false ], [ 0, %entry ]
   ret i32 %cond
 }
 
 define i32 @and_xor_minsize(i32 %a, i32 %b, i32 %c, i32 %d, i32* %input, i1 %cmp) #0 {
-; CHECK-LABEL: @and_xor_minsize(
-; CHECK-NEXT:  entry:
-; CHECK-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
-; CHECK-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
-; CHECK-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
-; CHECK-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP_NOT]], [[CMP1]]
-; CHECK-NEXT:    br i1 [[OR_COND]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
-; CHECK:       cond.false:
-; CHECK-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
-; CHECK-NEXT:    br label [[COND_END]]
-; CHECK:       cond.end:
-; CHECK-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
-; CHECK-NEXT:    ret i32 [[COND]]
+; THUMB-LABEL: @and_xor_minsize(
+; THUMB-NEXT:  entry:
+; THUMB-NEXT:    br i1 [[CMP:%.*]], label [[COND_END:%.*]], label [[LOR_LHS_FALSE:%.*]]
+; THUMB:       lor.lhs.false:
+; THUMB-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; THUMB-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; THUMB-NEXT:    br i1 [[CMP1]], label [[COND_FALSE:%.*]], label [[COND_END]]
+; THUMB:       cond.false:
+; THUMB-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; THUMB-NEXT:    br label [[COND_END]]
+; THUMB:       cond.end:
+; THUMB-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[LOR_LHS_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; THUMB-NEXT:    ret i32 [[COND]]
+;
+; ARM-LABEL: @and_xor_minsize(
+; ARM-NEXT:  entry:
+; ARM-NEXT:    [[CMP_NOT:%.*]] = xor i1 [[CMP:%.*]], true
+; ARM-NEXT:    [[ADD:%.*]] = add nsw i32 [[C:%.*]], [[A:%.*]]
+; ARM-NEXT:    [[CMP1:%.*]] = icmp slt i32 [[ADD]], [[B:%.*]]
+; ARM-NEXT:    [[OR_COND:%.*]] = and i1 [[CMP_NOT]], [[CMP1]]
+; ARM-NEXT:    br i1 [[OR_COND]], label [[COND_FALSE:%.*]], label [[COND_END:%.*]]
+; ARM:       cond.false:
+; ARM-NEXT:    [[TMP0:%.*]] = load i32, i32* [[INPUT:%.*]], align 4
+; ARM-NEXT:    br label [[COND_END]]
+; ARM:       cond.end:
+; ARM-NEXT:    [[COND:%.*]] = phi i32 [ [[TMP0]], [[COND_FALSE]] ], [ 0, [[ENTRY:%.*]] ]
+; ARM-NEXT:    ret i32 [[COND]]
 ;
 entry:
   br i1 %cmp, label %cond.end, label %lor.lhs.false
 
 lor.lhs.false:
   %add = add nsw i32 %c, %a
   %cmp1 = icmp slt i32 %add, %b
   br i1 %cmp1, label %cond.false, label %cond.end