When canonicalizing gep indices, prefer zext when possible

[reames]

Summary

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.

Q for reviewer: Should this be behind a target hook? If so, which and how?

On a broader topic, I don't really get why we're canonicalizing this way at all. Does anyone have a strong reason why this is right approach?

[reames]

ping

[majnemer]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1067–1074 ↗

(On Diff #18929)

This looks like it can be a separate change.

lib/Transforms/InstCombine/InstructionCombining.cpp

1326–1331 ↗

(On Diff #18929)

Isn't this change redundant with the one in InstCombineCasts? It would be nice to have this logic in one place.

[reames]

Responded to small comments inline. I'm not going to both updating the patch just yet. The high level questions I asked in the original review need to be addressed first. Rephrased:

Is canonicalizing sign extension to zero extension a good idea on all targets? It appears to work out well on x86, but do other targets have concerns? Does this need to be behind a target hook?

lib/Transforms/InstCombine/InstCombineCasts.cpp

1067–1074 ↗

(On Diff #18929)

It could yes, but the broader question of whether this transform is a good idea is global to all the locations.

When submitting, I'm happy to split this into a separate patch with it's own test.

lib/Transforms/InstCombine/InstructionCombining.cpp

1326–1331 ↗

(On Diff #18929)

Arguably, it is. I'm fine removing this.

[majnemer]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1067–1074 ↗

(On Diff #18929)

I'm of the opinion that zext should be more canonical than sext in this case because zext's are simpler to analyze. I can't immediately see why this canonicalization wouldn't be preferable except for bugs/deficiencies in other combines.

[reames]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1067–1074 ↗

(On Diff #18929)

Ok, I'll clean this up and separate the two patches. Do you want another round of review or should I just submit them?

[hfinkel]

lib/Transforms/InstCombine/InstCombineCasts.cpp

1067–1074 ↗

(On Diff #18929)

I agree; I'm in favor of doing this.

[reames]

Here's only the inst combine part

[hfinkel]

LGTM.

lib/Transforms/InstCombine/InstCombineCasts.cpp

1076 ↗

(On Diff #19933)

No need for two blank lines here.

llvm/trunk/lib/Transforms/InstCombine/InstCombineCasts.cpp

Instruction *InstCombiner::visitSExt(SExtInst &CI) {
   // See if we can simplify any instructions used by the input whose sole
   // purpose is to compute bits we don't care about.
   if (SimplifyDemandedInstructionBits(CI))
     return &CI;
 
   Value *Src = CI.getOperand(0);
   Type *SrcTy = Src->getType(), *DestTy = CI.getType();
 
+  // If we know that the value being extended is positive, we can use a zext
+  // instead. 
+  bool KnownZero, KnownOne;
+  ComputeSignBit(Src, KnownZero, KnownOne, 0, &CI);
+  if (KnownZero) {
+    Value *ZExt = Builder->CreateZExt(Src, DestTy);
+    return ReplaceInstUsesWith(CI, ZExt);
+  }
+
   // Attempt to extend the entire input expression tree to the destination
   // type.   Only do this if the dest type is a simple type, don't convert the
   // expression tree to something weird like i93 unless the source is also
   // strange.
   if ((DestTy->isVectorTy() || ShouldChangeType(SrcTy, DestTy)) &&
       CanEvaluateSExtd(Src, DestTy)) {
     // Okay, we can transform this!  Insert the new expression now.
     DEBUG(dbgs() << "ICE: EvaluateInDifferentType converting expression type"

llvm/trunk/test/Transforms/InstCombine/gep-sext.ll

+; RUN: opt < %s -instcombine -S | 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"
+target triple = "x86_64-pc-win32"
+
+declare void @use(i32) readonly
+
+; We prefer to canonicalize the machine width gep indices early
+define void @test(i32* %p, i32 %index) {
+; CHECK-LABEL: @test
+; CHECK-NEXT: %1 = sext i32 %index to i64
+; CHECK-NEXT: %addr = getelementptr i32* %p, i64 %1
+  %addr = getelementptr i32* %p, i32 %index
+  %val = load i32* %addr
+  call void @use(i32 %val)
+  ret void
+}
+; If they've already been canonicalized via zext, that's fine
+define void @test2(i32* %p, i32 %index) {
+; CHECK-LABEL: @test2
+; CHECK-NEXT: %i = zext i32 %index to i64
+; CHECK-NEXT: %addr = getelementptr i32* %p, i64 %i
+  %i = zext i32 %index to i64
+  %addr = getelementptr i32* %p, i64 %i
+  %val = load i32* %addr
+  call void @use(i32 %val)
+  ret void
+}
+; If we can use a zext, we prefer that.  This requires
+; knowing that the index is positive.
+define void @test3(i32* %p, i32 %index) {
+; CHECK-LABEL: @test3
+; CHECK:   zext
+; CHECK-NOT: sext
+  %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
+}
+; Replace sext with zext where possible
+define void @test4(i32* %p, i32 %index) {
+; CHECK-LABEL: @test4
+; CHECK:   zext
+; CHECK-NOT: sext
+  %addr_begin = getelementptr i32* %p, i64 40
+  %addr_fixed = getelementptr i32* %addr_begin, i64 48
+  %val_fixed = load i32* %addr_fixed, !range !0
+  %i = sext i32 %val_fixed to i64
+  %addr = getelementptr i32* %addr_begin, i64 %i
+  %val = load i32* %addr
+  call void @use(i32 %val)
+  ret void
+}
+
+;;  !range !0
+!0 = !{i32 0, i32 2147483647}
+
+
+