[PatternMatch] add special-case uaddo matching for increment-by-one

[spatel]

Summary

This is the most important uaddo problem mentioned in PR31754:
https://bugs.llvm.org/show_bug.cgi?id=31754

We were failing to match the canonicalized pattern when it's an 'add 1' operation.
Pattern matching, however, shouldn't assume that we have canonicalized IR, so we match 4 commuted variants of uaddo.

There's also a test with a crazy type to show that the existing CGP transform based on this matcher is not limited by target legality checks.

[RKSimon]

LGTM

[spatel]

(Not sure what's going on with Phab updates - but I haven't seen mails for commits corresponding to this review.)

Patch updated:
I forgot to update existing regression tests for this change.
I was worried that the existing code wasn't restricted enough, and the x86 diffs show that? Ie, using add 1 rather than inc should be considered a regression. I don't know what to make of the Hexagon diff (cc @kparzysz ).

...but there's a twist: I just saw D57520 would cause the same set of extra diffs that I neglected to include here originally. What is going on here?

[spatel]

Reopening - I reverted the initial commit: rL352769

[spatel]

Re-uploading the same patch as I mentioned in the previous comment (the one with all of the affected regression tests) because Phab is showing the version that committed initially.

[RKSimon]

@craig.topper Are you OK with the INC - ADD changes?

[craig.topper]

In D57516#1379515, @RKSimon wrote:

@craig.topper Are you OK with the INC - ADD changes?

Yeah. I imagine it won't be too hard to add a combine to recover it.

[spatel]

In D57516#1379520, @craig.topper wrote:

In D57516#1379515, @RKSimon wrote:

@craig.topper Are you OK with the INC - ADD changes?

Yeah. I imagine it won't be too hard to add a combine to recover it.

Thanks - my first hack at that doesn't account for all the test diffs, but I haven't messed around with those EFLAGS combines much before, so I might've misplaced the fold.
There's still a question about the Hexagon test regardless of whether we're ok with the x86 diffs.

[RKSimon]

LGTM - if you can expand the test checks for swp-epilog-phi5.ll (not necessarily running the update script) that'd be great

llvm/trunk/include/llvm/IR/PatternMatch.h

if (Pred == ICmpInst::ICMP_ULT)
       if (AddExpr.match(ICmpLHS) && (ICmpRHS == AddLHS || ICmpRHS == AddRHS))
         return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
 
     // a >u (a + b), b >u (a + b)
     if (Pred == ICmpInst::ICMP_UGT)
       if (AddExpr.match(ICmpRHS) && (ICmpLHS == AddLHS || ICmpLHS == AddRHS))
         return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
 
+    // Match special-case for increment-by-1.
+    if (Pred == ICmpInst::ICMP_EQ) {
+      // (a + 1) == 0
+      // (1 + a) == 0
+      if (AddExpr.match(ICmpLHS) && m_ZeroInt().match(ICmpRHS) &&
+          (m_One().match(AddLHS) || m_One().match(AddRHS)))
+        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpLHS);
+      // 0 == (a + 1)
+      // 0 == (1 + a)
+      if (m_ZeroInt().match(ICmpLHS) && AddExpr.match(ICmpRHS) &&
+          (m_One().match(AddLHS) || m_One().match(AddRHS)))
+        return L.match(AddLHS) && R.match(AddRHS) && S.match(ICmpRHS);
+    }
+
     return false;
   }
 };
 
 /// Match an icmp instruction checking for unsigned overflow on addition.
 ///
 /// S is matched to the addition whose result is being checked for overflow, and
 /// L and R are matched to the LHS and RHS of S.

llvm/trunk/test/CodeGen/Hexagon/swp-epilog-phi5.ll

 ; RUN: llc -march=hexagon < %s | FileCheck %s
 
 ; Test that we use the correct name in an epilog phi for a phi value
 ; that is defined for the last time in the kernel. Previously, we
 ; used the value from kernel loop definition, but we really need
 ; to use the value from the Phi in the kernel instead.
 
 ; In this test case, the second loop is pipelined, block b5.
 
 ; CHECK: loop0
 ; CHECK: [[REG0:r([0-9]+)]] += mpyi
-; CHECK-NOT: r{{[0-9]+}} += add([[REG0]],#8)
-; CHECK: endloop1
+; CHECK: [[REG2:r([0-9]+)]] = add([[REG1:r([0-9]+)]],add([[REG0]],#8
+; CHECK: endloop0
 
 %s.0 = type { %s.1*, %s.4*, %s.7*, i8*, i8, i32, %s.8*, i32, i32, i32, i8, i8, i32, i32, double, i8, i8, i8, i8, i8, i8, i8, i8, i32, i8, i8, i8, i32, i32, i32, i32, i32, i32, i8**, i32, i32, i32, i32, i32, [64 x i32]*, [4 x %s.9*], [4 x %s.10*], [4 x %s.10*], i32, %s.23*, i8, i8, [16 x i8], [16 x i8], [16 x i8], i32, i8, i8, i8, i8, i16, i16, i8, i8, i8, %s.11*, i32, i32, i32, i32, i8*, i32, [4 x %s.23*], i32, i32, i32, [10 x i32], i32, i32, i32, i32, i32, %s.12*, %s.13*, %s.14*, %s.15*, %s.16*, %s.17*, %s.18*, %s.19*, %s.20*, %s.21*, %s.22* }
 %s.1 = type { void (%s.2*)*, void (%s.2*, i32)*, void (%s.2*)*, void (%s.2*, i8*)*, void (%s.2*)*, i32, %s.3, i32, i32, i8**, i32, i8**, i32, i32 }
 %s.2 = type { %s.1*, %s.4*, %s.7*, i8*, i8, i32 }
 %s.3 = type { [8 x i32], [48 x i8] }
 %s.4 = type { i8* (%s.2*, i32, i32)*, i8* (%s.2*, i32, i32)*, i8** (%s.2*, i32, i32, i32)*, [64 x i16]** (%s.2*, i32, i32, i32)*, %s.5* (%s.2*, i32, i8, i32, i32, i32)*, %s.6* (%s.2*, i32, i8, i32, i32, i32)*, {}*, i8** (%s.2*, %s.5*, i32, i32, i8)*, [64 x i16]** (%s.2*, %s.6*, i32, i32, i8)*, void (%s.2*, i32)*, {}*, i32, i32 }
 %s.5 = type opaque
 %s.6 = type opaque

llvm/trunk/test/CodeGen/X86/copy-eflags.ll

 ; X32-NEXT:    pushl %ebx
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    incl (%eax)
 ; X32-NEXT:    setne %bl
 ; X32-NEXT:    pushl $42
 ; X32-NEXT:    calll external
 ; X32-NEXT:    addl $4, %esp
 ; X32-NEXT:    testb %bl, %bl
-; X32-NEXT:    je .LBB1_1
-; X32-NEXT:  # %bb.2: # %else
-; X32-NEXT:    xorl %eax, %eax
+; X32-NEXT:    jne .LBB1_2
+; X32-NEXT:  # %bb.1: # %then
+; X32-NEXT:    movl $64, %eax
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    retl
-; X32-NEXT:  .LBB1_1: # %then
-; X32-NEXT:    movl $64, %eax
+; X32-NEXT:  .LBB1_2: # %else
+; X32-NEXT:    xorl %eax, %eax
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: test2:
 ; X64:       # %bb.0: # %entry
 ; X64-NEXT:    pushq %rbx
 ; X64-NEXT:    incl (%rdi)
 ; X64-NEXT:    setne %bl
 ; X64-NEXT:    movl $42, %edi
 ; X64-NEXT:    callq external
 ; X64-NEXT:    testb %bl, %bl
-; X64-NEXT:    je .LBB1_1
-; X64-NEXT:  # %bb.2: # %else
-; X64-NEXT:    xorl %eax, %eax
+; X64-NEXT:    jne .LBB1_2
+; X64-NEXT:  # %bb.1: # %then
+; X64-NEXT:    movl $64, %eax
 ; X64-NEXT:    popq %rbx
 ; X64-NEXT:    retq
-; X64-NEXT:  .LBB1_1: # %then
-; X64-NEXT:    movl $64, %eax
+; X64-NEXT:  .LBB1_2: # %else
+; X64-NEXT:    xorl %eax, %eax
 ; X64-NEXT:    popq %rbx
 ; X64-NEXT:    retq
 entry:
   %val = load i32, i32* %ptr
   %inc = add i32 %val, 1
   store i32 %inc, i32* %ptr
   %cmp = icmp eq i32 %inc, 0
   call void @external(i32 42)

llvm/trunk/test/CodeGen/X86/rd-mod-wr-eflags.ll

 ; CHECK-NEXT:  # %bb.1: # %if.end
 ; CHECK-NEXT:    incl 8(%rdi)
 ; CHECK-NEXT:    jne .LBB4_4
 ; CHECK-NEXT:  # %bb.2: # %if.end1
 ; CHECK-NEXT:    incw 12(%rdi)
 ; CHECK-NEXT:    jne .LBB4_4
 ; CHECK-NEXT:  # %bb.3: # %if.end2
 ; CHECK-NEXT:    incb 14(%rdi)
-; CHECK-NEXT:    je .LBB4_5
+; CHECK-NEXT:    jne .LBB4_4
+; CHECK-NEXT:  # %bb.5: # %if.end4
+; CHECK-NEXT:    jmp other # TAILCALL
 ; CHECK-NEXT:  .LBB4_4: # %return
 ; CHECK-NEXT:    retq
-; CHECK-NEXT:  .LBB4_5: # %if.end4
-; CHECK-NEXT:    jmp other # TAILCALL
 entry:
   %s64 = getelementptr inbounds %struct.obj2, %struct.obj2* %o, i64 0, i32 0
   %0 = load i64, i64* %s64, align 8
   %inc = add i64 %0, 1
   store i64 %inc, i64* %s64, align 8
   %tobool = icmp eq i64 %inc, 0
   br i1 %tobool, label %if.end, label %return
 

llvm/trunk/test/Transforms/CodeGenPrepare/X86/overflow-intrinsics.ll

exit:
   ret i64 0
 }
 
 ; When adding 1, the general pattern for add-overflow may be different due to icmp canonicalization.
 ; PR31754: https://bugs.llvm.org/show_bug.cgi?id=31754
 
 define i1 @uaddo_i64_increment(i64 %x, i64* %p) {
 ; CHECK-LABEL: @uaddo_i64_increment(
-; CHECK-NEXT:    [[A:%.*]] = add i64 [[X:%.*]], 1
-; CHECK-NEXT:    [[OV:%.*]] = icmp eq i64 [[A]], 0
-; CHECK-NEXT:    store i64 [[A]], i64* [[P:%.*]]
-; CHECK-NEXT:    ret i1 [[OV]]
+; CHECK-NEXT:    [[UADD_OVERFLOW:%.*]] = call { i64, i1 } @llvm.uadd.with.overflow.i64(i64 [[X:%.*]], i64 1)
+; CHECK-NEXT:    [[UADD:%.*]] = extractvalue { i64, i1 } [[UADD_OVERFLOW]], 0
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i64, i1 } [[UADD_OVERFLOW]], 1
+; CHECK-NEXT:    store i64 [[UADD]], i64* [[P:%.*]]
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %a = add i64 %x, 1
   %ov = icmp eq i64 %a, 0
   store i64 %a, i64* %p
   ret i1 %ov
 }
 
 define i1 @uaddo_i8_increment_noncanonical_1(i8 %x, i8* %p) {
 ; CHECK-LABEL: @uaddo_i8_increment_noncanonical_1(
-; CHECK-NEXT:    [[A:%.*]] = add i8 1, [[X:%.*]]
-; CHECK-NEXT:    [[OV:%.*]] = icmp eq i8 [[A]], 0
-; CHECK-NEXT:    store i8 [[A]], i8* [[P:%.*]]
-; CHECK-NEXT:    ret i1 [[OV]]
+; CHECK-NEXT:    [[UADD_OVERFLOW:%.*]] = call { i8, i1 } @llvm.uadd.with.overflow.i8(i8 1, i8 [[X:%.*]])
+; CHECK-NEXT:    [[UADD:%.*]] = extractvalue { i8, i1 } [[UADD_OVERFLOW]], 0
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i8, i1 } [[UADD_OVERFLOW]], 1
+; CHECK-NEXT:    store i8 [[UADD]], i8* [[P:%.*]]
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %a = add i8 1, %x        ; commute
   %ov = icmp eq i8 %a, 0
   store i8 %a, i8* %p
   ret i1 %ov
 }
 
 define i1 @uaddo_i32_increment_noncanonical_2(i32 %x, i32* %p) {
 ; CHECK-LABEL: @uaddo_i32_increment_noncanonical_2(
-; CHECK-NEXT:    [[A:%.*]] = add i32 [[X:%.*]], 1
-; CHECK-NEXT:    [[OV:%.*]] = icmp eq i32 0, [[A]]
-; CHECK-NEXT:    store i32 [[A]], i32* [[P:%.*]]
-; CHECK-NEXT:    ret i1 [[OV]]
+; CHECK-NEXT:    [[UADD_OVERFLOW:%.*]] = call { i32, i1 } @llvm.uadd.with.overflow.i32(i32 [[X:%.*]], i32 1)
+; CHECK-NEXT:    [[UADD:%.*]] = extractvalue { i32, i1 } [[UADD_OVERFLOW]], 0
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i32, i1 } [[UADD_OVERFLOW]], 1
+; CHECK-NEXT:    store i32 [[UADD]], i32* [[P:%.*]]
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %a = add i32 %x, 1
   %ov = icmp eq i32 0, %a   ; commute
   store i32 %a, i32* %p
   ret i1 %ov
 }
 
 define i1 @uaddo_i16_increment_noncanonical_3(i16 %x, i16* %p) {
 ; CHECK-LABEL: @uaddo_i16_increment_noncanonical_3(
-; CHECK-NEXT:    [[A:%.*]] = add i16 1, [[X:%.*]]
-; CHECK-NEXT:    [[OV:%.*]] = icmp eq i16 0, [[A]]
-; CHECK-NEXT:    store i16 [[A]], i16* [[P:%.*]]
-; CHECK-NEXT:    ret i1 [[OV]]
+; CHECK-NEXT:    [[UADD_OVERFLOW:%.*]] = call { i16, i1 } @llvm.uadd.with.overflow.i16(i16 1, i16 [[X:%.*]])
+; CHECK-NEXT:    [[UADD:%.*]] = extractvalue { i16, i1 } [[UADD_OVERFLOW]], 0
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i16, i1 } [[UADD_OVERFLOW]], 1
+; CHECK-NEXT:    store i16 [[UADD]], i16* [[P:%.*]]
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %a = add i16 1, %x        ; commute
   %ov = icmp eq i16 0, %a   ; commute
   store i16 %a, i16* %p
   ret i1 %ov
 }
 
 ; TODO: Did we really intend to match this if it's not supported by the target?
 
 define i1 @uaddo_i42_increment_illegal_type(i42 %x, i42* %p) {
 ; CHECK-LABEL: @uaddo_i42_increment_illegal_type(
-; CHECK-NEXT:    [[A:%.*]] = add i42 [[X:%.*]], 1
-; CHECK-NEXT:    [[OV:%.*]] = icmp eq i42 [[A]], 0
-; CHECK-NEXT:    store i42 [[A]], i42* [[P:%.*]]
-; CHECK-NEXT:    ret i1 [[OV]]
+; CHECK-NEXT:    [[UADD_OVERFLOW:%.*]] = call { i42, i1 } @llvm.uadd.with.overflow.i42(i42 [[X:%.*]], i42 1)
+; CHECK-NEXT:    [[UADD:%.*]] = extractvalue { i42, i1 } [[UADD_OVERFLOW]], 0
+; CHECK-NEXT:    [[OVERFLOW:%.*]] = extractvalue { i42, i1 } [[UADD_OVERFLOW]], 1
+; CHECK-NEXT:    store i42 [[UADD]], i42* [[P:%.*]]
+; CHECK-NEXT:    ret i1 [[OVERFLOW]]
 ;
   %a = add i42 %x, 1
   %ov = icmp eq i42 %a, 0
   store i42 %a, i42* %p
   ret i1 %ov
 }
 
 ; Check that every instruction inserted by -codegenprepare has a debug location.
 ; DEBUG: CheckModuleDebugify: PASS