[SDAG] Teach Chain Analysis about BaseIndexOffset addressing.

[niravd]

Summary

While we use BaseIndexOffset in FindBetterNeighborChains to appropriately realize they're almost the same address and should be improved concurrently we do not use it in isAlias using the non-index understanding FindBaseOffset instead. Adding a BaseIndexOffset check in isAlias like should allow indexed stores to be merged.

Once this is in we should be able to excise FindBaseOffset.

[niravd]

Rebasing to showoff test change with now committed testcase

[niravd]

Added a few more reviewers as jyknight is on vacation.

[spatel]

I had not looked at this code before, so I'll need help reviewing. As part of trying to understand what this function is doing, I tried to improve it with some cleanups:
rL300850
rL300854
rL300860

This patch says that if BaseIndexOffset::match() returns matching base pointers, then we don't need to go through all of the checks below it. In that case, can we remove some/all of the code in findBaseOffset()?

[niravd]

In D31987#732435, @spatel wrote:

I had not looked at this code before, so I'll need help reviewing. As part of trying to understand what this function is doing, I tried to improve it with some cleanups:
rL300850
rL300854
rL300860

Nice!

This patch says that if BaseIndexOffset::match() returns matching base pointers, then we don't need to go through all of the checks below it. In that case, can we remove some/all of the code in findBaseOffset()?

Yes. This should fully encompass the Base check and we should be able to repoint the relevant additional checks for globals/constants and framepointers to the baseindex check. I have a follow up patch that should completely remove findBaseOffset and do the incremental checks for FramePointers etc. off of the BaseIndexOffset match which should be correct (though I need to do a more thorough check to be more sure). I kept if off here to make it clearer that this is just adding the BaseIndexOffset case analysis to our current BaseOffset check and not dropping any cases.

[niravd]

Update past Sanjay's cleanups in trunk.

[spatel]

In D31987#732491, @niravd wrote:

Yes. This should fully encompass the Base check and we should be able to repoint the relevant additional checks for globals/constants and framepointers to the baseindex check. I have a follow up patch that should completely remove findBaseOffset and do the incremental checks for FramePointers etc. off of the BaseIndexOffset match which should be correct (though I need to do a more thorough check to be more sure). I kept if off here to make it clearer that this is just adding the BaseIndexOffset case analysis to our current BaseOffset check and not dropping any cases.

In that case, can you add a 'FIXME' comment describing this plan as part of this patch. Just in case the follow-ups are delayed for some reason, we don't want to leave this code in a confusing state.
Given that, LGTM. But if anyone else can also give this a look, that would be best since I'm not that familiar with all of the aliasing possibilities.

llvm/trunk/lib/CodeGen/SelectionDAG/DAGCombiner.cpp

bool DAGCombiner::isAlias(LSBaseSDNode *Op0, LSBaseSDNode *Op1) const {
   // cannot alias. These should really be checking the equivalent of mayWrite,
   // but it only matters for memory nodes other than load /store.
   if (Op0->isInvariant() && Op1->writeMem())
     return false;
 
   if (Op1->isInvariant() && Op0->writeMem())
     return false;
 
+  unsigned NumBytes0 = Op0->getMemoryVT().getSizeInBits() >> 3;
+  unsigned NumBytes1 = Op1->getMemoryVT().getSizeInBits() >> 3;
+
+  // Check for BaseIndexOffset matching.
+  BaseIndexOffset BasePtr0 = BaseIndexOffset::match(Op0->getBasePtr(), DAG);
+  BaseIndexOffset BasePtr1 = BaseIndexOffset::match(Op1->getBasePtr(), DAG);
+  if (BasePtr0.equalBaseIndex(BasePtr1))
+    return !((BasePtr0.Offset + NumBytes0 <= BasePtr1.Offset) ||
+             (BasePtr1.Offset + NumBytes1 <= BasePtr0.Offset));
+
+  // FIXME: findBaseOffset and ConstantValue/GlobalValue/FrameIndex analysis
+  // modified to use BaseIndexOffset.
+
   // Gather base node and offset information.
   SDValue Base0, Base1;
   int64_t Offset0, Offset1;
   const GlobalValue *GV0, *GV1;
   const void *CV0, *CV1;
   bool IsFrameIndex0 = findBaseOffset(Op0->getBasePtr(),
                                       Base0, Offset0, GV0, CV0);
   bool IsFrameIndex1 = findBaseOffset(Op1->getBasePtr(),
                                       Base1, Offset1, GV1, CV1);
 
   // If they have the same base address, then check to see if they overlap.
-  unsigned NumBytes0 = Op0->getMemoryVT().getSizeInBits() >> 3;
-  unsigned NumBytes1 = Op1->getMemoryVT().getSizeInBits() >> 3;
   if (Base0 == Base1 || (GV0 && (GV0 == GV1)) || (CV0 && (CV0 == CV1)))
     return !((Offset0 + NumBytes0) <= Offset1 ||
              (Offset1 + NumBytes1) <= Offset0);
 
   // It is possible for different frame indices to alias each other, mostly
   // when tail call optimization reuses return address slots for arguments.
   // To catch this case, look up the actual index of frame indices to compute
   // the real alias relationship.

llvm/trunk/test/CodeGen/X86/i256-add.ll

 ; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
 ; RUN: llc < %s -mtriple=i386-unknown | FileCheck %s --check-prefix=X32
 ; RUN: llc < %s -mtriple=x86_64-unknown | FileCheck %s --check-prefix=X64
 
 define void @add(i256* %p, i256* %q) nounwind {
 ; X32-LABEL: add:
 ; X32:       # BB#0:
 ; X32-NEXT:    pushl %ebp
 ; X32-NEXT:    pushl %ebx
 ; X32-NEXT:    pushl %edi
 ; X32-NEXT:    pushl %esi
 ; X32-NEXT:    subl $12, %esp
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %eax
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %ecx
-; X32-NEXT:    movl 8(%ecx), %edx
-; X32-NEXT:    movl (%ecx), %ebx
-; X32-NEXT:    movl 4(%ecx), %edi
+; X32-NEXT:    movl 8(%ecx), %edi
+; X32-NEXT:    movl (%ecx), %edx
+; X32-NEXT:    movl 4(%ecx), %ebx
 ; X32-NEXT:    movl 28(%eax), %esi
 ; X32-NEXT:    movl %esi, {{[0-9]+}}(%esp) # 4-byte Spill
 ; X32-NEXT:    movl 24(%eax), %ebp
-; X32-NEXT:    addl (%eax), %ebx
-; X32-NEXT:    adcl 4(%eax), %edi
-; X32-NEXT:    adcl 8(%eax), %edx
+; X32-NEXT:    addl (%eax), %edx
 ; X32-NEXT:    movl %edx, {{[0-9]+}}(%esp) # 4-byte Spill
-; X32-NEXT:    movl 20(%eax), %esi
+; X32-NEXT:    adcl 4(%eax), %ebx
+; X32-NEXT:    adcl 8(%eax), %edi
+; X32-NEXT:    movl %edi, (%esp) # 4-byte Spill
+; X32-NEXT:    movl 20(%eax), %edi
 ; X32-NEXT:    movl 12(%eax), %edx
-; X32-NEXT:    movl 16(%eax), %eax
+; X32-NEXT:    movl 16(%eax), %esi
 ; X32-NEXT:    adcl 12(%ecx), %edx
-; X32-NEXT:    adcl 16(%ecx), %eax
-; X32-NEXT:    adcl 20(%ecx), %esi
-; X32-NEXT:    adcl 24(%ecx), %ebp
-; X32-NEXT:    movl %ebp, (%esp) # 4-byte Spill
+; X32-NEXT:    adcl 16(%ecx), %esi
+; X32-NEXT:    adcl 20(%ecx), %edi
+; X32-NEXT:    movl %ebp, %eax
+; X32-NEXT:    adcl 24(%ecx), %eax
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %ebp # 4-byte Reload
 ; X32-NEXT:    adcl %ebp, 28(%ecx)
+; X32-NEXT:    movl (%esp), %ebp # 4-byte Reload
+; X32-NEXT:    movl %ebp, 8(%ecx)
+; X32-NEXT:    movl %ebx, 4(%ecx)
+; X32-NEXT:    movl {{[0-9]+}}(%esp), %ebx # 4-byte Reload
 ; X32-NEXT:    movl %ebx, (%ecx)
-; X32-NEXT:    movl %edi, 4(%ecx)
-; X32-NEXT:    movl {{[0-9]+}}(%esp), %edi # 4-byte Reload
-; X32-NEXT:    movl %edi, 8(%ecx)
 ; X32-NEXT:    movl %edx, 12(%ecx)
-; X32-NEXT:    movl %eax, 16(%ecx)
-; X32-NEXT:    movl %esi, 20(%ecx)
-; X32-NEXT:    movl (%esp), %eax # 4-byte Reload
+; X32-NEXT:    movl %esi, 16(%ecx)
+; X32-NEXT:    movl %edi, 20(%ecx)
 ; X32-NEXT:    movl %eax, 24(%ecx)
 ; X32-NEXT:    addl $12, %esp
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    popl %edi
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    popl %ebp
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: add:
 ; X64:       # BB#0:
 ; X64-NEXT:    movq 16(%rdi), %rax
 ; X64-NEXT:    movq (%rdi), %rcx
 ; X64-NEXT:    movq 8(%rdi), %rdx
 ; X64-NEXT:    movq 24(%rsi), %r8
 ; X64-NEXT:    addq (%rsi), %rcx
 ; X64-NEXT:    adcq 8(%rsi), %rdx
 ; X64-NEXT:    adcq 16(%rsi), %rax
 ; X64-NEXT:    adcq %r8, 24(%rdi)
-; X64-NEXT:    movq %rcx, (%rdi)
-; X64-NEXT:    movq %rdx, 8(%rdi)
 ; X64-NEXT:    movq %rax, 16(%rdi)
+; X64-NEXT:    movq %rdx, 8(%rdi)
+; X64-NEXT:    movq %rcx, (%rdi)
 ; X64-NEXT:    retq
   %a = load i256, i256* %p
   %b = load i256, i256* %q
   %c = add i256 %a, %b
   store i256 %c, i256* %p
   ret void
 }
 define void @sub(i256* %p, i256* %q) nounwind {

 ; X32-NEXT:    sbbl 16(%esi), %eax
 ; X32-NEXT:    movl %eax, (%esp) # 4-byte Spill
 ; X32-NEXT:    movl 20(%ecx), %edx
 ; X32-NEXT:    sbbl 20(%esi), %edx
 ; X32-NEXT:    movl 24(%ecx), %eax
 ; X32-NEXT:    sbbl 24(%esi), %eax
 ; X32-NEXT:    movl 28(%esi), %esi
 ; X32-NEXT:    sbbl %esi, 28(%ecx)
-; X32-NEXT:    movl %ebx, (%ecx)
-; X32-NEXT:    movl %ebp, 4(%ecx)
 ; X32-NEXT:    movl %edi, 8(%ecx)
+; X32-NEXT:    movl %ebp, 4(%ecx)
+; X32-NEXT:    movl %ebx, (%ecx)
 ; X32-NEXT:    movl {{[0-9]+}}(%esp), %esi # 4-byte Reload
 ; X32-NEXT:    movl %esi, 12(%ecx)
 ; X32-NEXT:    movl (%esp), %esi # 4-byte Reload
 ; X32-NEXT:    movl %esi, 16(%ecx)
 ; X32-NEXT:    movl %edx, 20(%ecx)
 ; X32-NEXT:    movl %eax, 24(%ecx)
 ; X32-NEXT:    addl $8, %esp
 ; X32-NEXT:    popl %esi
 ; X32-NEXT:    popl %edi
 ; X32-NEXT:    popl %ebx
 ; X32-NEXT:    popl %ebp
 ; X32-NEXT:    retl
 ;
 ; X64-LABEL: sub:
 ; X64:       # BB#0:
 ; X64-NEXT:    movq 16(%rdi), %rax
 ; X64-NEXT:    movq (%rdi), %rcx
 ; X64-NEXT:    movq 8(%rdi), %rdx
 ; X64-NEXT:    movq 24(%rsi), %r8
 ; X64-NEXT:    subq (%rsi), %rcx
 ; X64-NEXT:    sbbq 8(%rsi), %rdx
 ; X64-NEXT:    sbbq 16(%rsi), %rax
 ; X64-NEXT:    sbbq %r8, 24(%rdi)
-; X64-NEXT:    movq %rcx, (%rdi)
-; X64-NEXT:    movq %rdx, 8(%rdi)
 ; X64-NEXT:    movq %rax, 16(%rdi)
+; X64-NEXT:    movq %rdx, 8(%rdi)
+; X64-NEXT:    movq %rcx, (%rdi)
 ; X64-NEXT:    retq
   %a = load i256, i256* %p
   %b = load i256, i256* %q
   %c = sub i256 %a, %b
   store i256 %c, i256* %p
   ret void
 }

llvm/trunk/test/CodeGen/X86/merge_store.ll

entry:
   %3 = trunc i64 %indvars.iv.next to i32
   %cmp = icmp slt i32 %3, 1000
   br i1 %cmp, label %for.body, label %for.end
 
   for.end:
   ret void
 }
 
-
-
 ;; CHECK-LABEL: indexed-store-merge
-
-;; We should be able to merge the 4 consecutive stores.  
-;; FIXMECHECK: movl $0, 2(%rsi,%rdi)
-
-;; CHECK: movb  $0, 2(%rsi,%rdi)
-;; CHECK: movb  $0, 3(%rsi,%rdi)
-;; CHECK: movb  $0, 4(%rsi,%rdi)
-;; CHECK: movb  $0, 5(%rsi,%rdi)
+;; CHECK: movl  $0, 2(%rsi,%rdi)
 ;; CHECK: movb  $0, (%rsi)
 define void @indexed-store-merge(i64 %p, i8* %v) {
 entry:
   %p2 = add nsw i64 %p, 2
   %v2 = getelementptr i8, i8* %v, i64 %p2
   store i8 0, i8* %v2, align 2
   %p3 = add nsw i64 %p, 3
   %v3 = getelementptr i8, i8* %v, i64 %p3