When canonicalizing gep indices, prefer zext when possible (SelectionDAGBuilder)

[reames]

Summary

This was split from http://reviews.llvm.org/D7255 and implements the SelectionDAGBuilder parts.

We eagerly canonicalize gep indices to the width of a machine register (i64 on x86_64). To do so, we insert sign extensions (sext) to promote smaller types. This change substitutes zero extensions where we know the value being extended is positive. This is motivated by the fact that zero extensions are generally cheaper on x86.

[sanjoy]

Small drop-by comment inline. I don't know enough about SelectionDAG to LGTM this.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

3465

A TODO here (definitely not this change) could be to exploit the case where you *know* that the high bit is set (i.e. KnownOne == true), and emit a bitwise OR of 0xffff0000 with a zext of the value. I don't know if that will actually be faster, even on x86, but it does remove the data dependence of the higher bits on the sign bit of the source (narrower) value.

[hfinkel]

Part of the issue is that this canonicalization already exists in DAGCombine (at the end of DAGCombiner::visitSIGN_EXTEND):

// fold (sext x) -> (zext x) if the sign bit is known zero.
if ((!LegalOperations || TLI.isOperationLegal(ISD::ZERO_EXTEND, VT)) &&
    DAG.SignBitIsZero(N0))
  return DAG.getNode(ISD::ZERO_EXTEND, SDLoc(N), VT, N0);

As a result, I'm not sure this is needed.

[reames]

In D7626#123600, @hfinkel wrote:

Part of the issue is that this canonicalization already exists in DAGCombine (at the end of DAGCombiner::visitSIGN_EXTEND):

// fold (sext x) -> (zext x) if the sign bit is known zero.
if ((!LegalOperations || TLI.isOperationLegal(ISD::ZERO_EXTEND, VT)) &&
    DAG.SignBitIsZero(N0))
  return DAG.getNode(ISD::ZERO_EXTEND, SDLoc(N), VT, N0);

As a result, I'm not sure this is needed.

I agree. Given this, I find it really odd I saw the sign extensions to start with... I suspect we're missing something here.

Until we figure out what that something is, I'm going to abandon this change for now.

lib/CodeGen/SelectionDAG/SelectionDAGBuilder.cpp

       }
 
       // N = N + Idx * ElementSize;
       APInt ElementSize =
           APInt(TLI.getPointerSizeInBits(AS), DL->getTypeAllocSize(Ty));
       SDValue IdxN = getValue(Idx);
 
       // If the index is smaller or larger than intptr_t, truncate or extend
-      // it.
-      IdxN = DAG.getSExtOrTrunc(IdxN, getCurSDLoc(), N.getValueType());
+      // it. Prefer a zext vs a sext if we can.
+      bool KnownZero, KnownOne;
+      ComputeSignBit(const_cast<Value*>(Idx), KnownZero, KnownOne, DL);
+      if (KnownZero)
+        IdxN = DAG.getZExtOrTrunc(IdxN, getCurSDLoc(), N.getValueType());
+      else
+        IdxN = DAG.getSExtOrTrunc(IdxN, getCurSDLoc(), N.getValueType());
 
       // If this is a multiply by a power of two, turn it into a shl
       // immediately.  This is a very common case.
       if (ElementSize != 1) {
         if (ElementSize.isPowerOf2()) {
           unsigned Amt = ElementSize.logBase2();
           IdxN = DAG.getNode(ISD::SHL, getCurSDLoc(),
                              N.getValueType(), IdxN,

test/CodeGen/X86/gep-sext.ll

+; RUN: llc < %s 2>&1 | FileCheck %s
+
+target datalayout = "e-p:32:32"
+target triple = "x86_64-linux-unknown"
+
+
+declare void @use(i32)
+
+; Sign extension is manditory for the gep argument
+define void @test(i32* %p, i32 %index) {
+; CHECK-LABEL: test:
+; CHECK: movslq %esi, %rax
+; CHECK: movl (%rdi,%rax,4), %edi
+  %addr = getelementptr i32* %p, i32 %index
+  %val = load i32* %addr
+  call void @use(i32 %val)
+  ret void
+}
+
+; Zero extension is manditory since the high bits of %esi
+; aren't specified
+define void @test2(i32* %p, i32 %index) {
+; CHECK-LABEL: test2
+; CHECK: movl %esi, %eax
+; CHECK: movl (%rdi,%rax,4), %edi
+  %i = zext i32 %index to i64
+  %addr = getelementptr i32* %p, i64 %i
+  %val = load i32* %addr
+  call void @use(i32 %val)
+  ret void
+}
+define void @test3(i32* %p, i32 %index) {
+; CHECK-LABEL: test3
+; CHECK-NOT: movslq
+; CHECK: movl 352(%rdi), %eax
+; CHECK: movl 160(%rdi,%rax,4), %edi
+  %addr_begin = getelementptr i32* %p, i64 40
+  %addr_fixed = getelementptr i32* %addr_begin, i64 48
+  %val_fixed = load i32* %addr_fixed, !range !0
+  %addr = getelementptr i32* %addr_begin, i32 %val_fixed
+  %val = load i32* %addr
+  call void @use(i32 %val)
+  ret void
+}
+;;  !range !0
+!0 = !{i32 0, i32 2147483647}
+
+
+