[InstCombine] Simplify pointer difference subtractions (GEP-GEP) where GEPs have other uses and one non-constant index

[hjyamauchi]

Summary

Pointer difference simplifications currently happen only if input GEPs don't have other uses or their indexes are all constants, to avoid duplicating indexing arithmetic.

This patch enables cases with exactly one non-constant index among input GEPs to happen where there is no duplicated arithmetic or code size increase even if input GEPs have other uses.

For example, this patch allows "(&A[42][i]-&A[42][0])" --> "i", which didn't happen previously, if the input GEP(s) have other uses.

[sanjoy]

lgtm with minor nits

include/llvm/IR/Operator.h

475

I'd call this countNonConstantIndices.

477

You can use llvm::count_if here.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1490

Please add a full sentence here, or remove it.

[mcrosier]

lib/Transforms/InstCombine/InstCombineAddSub.cpp

1468–1469

!GEP1 is the preferred condition style and you don't need the extra curly brackets.

if (!GEP1)
  return nullptr;

1473

Similarly, !GEP2 is preferred.

[hjyamauchi]

Addressed the comments.

[hjyamauchi]

Addressed one more comment.

[hjyamauchi]

include/llvm/IR/Operator.h

477

I used std::count_if instead as llvm::count_if seems to use the standard begin/end instead of the idx_begin/idx_end required here.

[hjyamauchi]

Now using llvm::count_if + make_range.

include/llvm/IR/Operator.h

477

Now using llvm::count_if + make_range.

include/llvm/IR/Operator.h

public:
   bool hasAllConstantIndices() const {
     for (const_op_iterator I = idx_begin(), E = idx_end(); I != E; ++I) {
       if (!isa<ConstantInt>(I))
         return false;
     }
     return true;
   }
 
+  unsigned countNonConstantIndices() const {
+    return count_if(make_range(idx_begin(), idx_end()), [](const Use& use) {
+        return !isa<ConstantInt>(*use);
+      });
+  }
+
   /// \brief Accumulate the constant address offset of this GEP if possible.
   ///
   /// This routine accepts an APInt into which it will accumulate the constant
   /// offset of this GEP if the GEP is in fact constant. If the GEP is not
   /// all-constant, it returns false and the value of the offset APInt is
   /// undefined (it is *not* preserved!). The APInt passed into this routine
   /// must be at exactly as wide as the IntPtr type for the address space of the
   /// base GEP pointer.

lib/Transforms/InstCombine/InstCombineAddSub.cpp

if (RHSGEP->getOperand(0) == LHS) {
             LHSGEP->getOperand(0)->stripPointerCasts()) {
         GEP2 = LHSGEP;
         GEP1 = RHSGEP;
         Swapped = true;
       }
     }
   }
 
-  // Avoid duplicating the arithmetic if GEP2 has non-constant indices and
-  // multiple users.
-  if (!GEP1 ||
-      (GEP2 && !GEP2->hasAllConstantIndices() && !GEP2->hasOneUse()))
+  if (!GEP1)
+    // No GEP found.
     return nullptr;
 
+  if (GEP2) {
+    // (gep X, ...) - (gep X, ...)
+    //
+    // Avoid duplicating the arithmetic if there are more than one non-constant
+    // indices between the two GEPs and either GEP has a non-constant index and
+    // multiple users. If zero non-constant index, the result is a constant and
+    // there is no duplication. If one non-constant index, the result is an add
+    // or sub with a constant, which is no larger than the original code, and
+    // there's no duplicated arithmetic, even if either GEP has multiple
+    // users. If more than one non-constant indices combined, as long as the GEP
+    // with at least one non-constant index doesn't have multiple users, there
+    // is no duplication.
+    unsigned NumNonConstantIndices1 = GEP1->countNonConstantIndices();
+    unsigned NumNonConstantIndices2 = GEP2->countNonConstantIndices();
+    if (NumNonConstantIndices1 + NumNonConstantIndices2 > 1 &&
+        ((NumNonConstantIndices1 > 0 && !GEP1->hasOneUse()) ||
+         (NumNonConstantIndices2 > 0 && !GEP2->hasOneUse()))) {
+      return nullptr;
+    }
+  }
+
   // Emit the offset of the GEP and an intptr_t.
   Value *Result = EmitGEPOffset(GEP1);
 
   // If we had a constant expression GEP on the other side offsetting the
   // pointer, subtract it from the offset we have.
   if (GEP2) {
     Value *Offset = EmitGEPOffset(GEP2);
     Result = Builder.CreateSub(Result, Offset);

test/Transforms/InstCombine/sub.ll

 define i32 @test57(i32 %A, i32 %B) {
 ; CHECK-LABEL: @test57(
 ; CHECK-NEXT:    [[Y:%.*]] = sub i32 0, [[B:%.*]]
 ; CHECK-NEXT:    ret i32 [[Y]]
 ;
   %X = add i32 %B, %A
   %Y = sub i32 %A, %X
   ret i32 %Y                                                                                                                                                                                                                                             }
+
+@dummy_global1 = external global i8*
+@dummy_global2 = external global i8*
+
+define i64 @test58([100 x [100 x i8]]* %foo, i64 %i, i64 %j) {
+; CHECK-LABEL: @test58(
+; CHECK-NEXT:    [[TMP1:%.*]] = add i64 [[J:%.*]], 4200
+; CHECK-NEXT:    [[TMP2:%.*]] = add i64 [[I:%.*]], 4200
+; CHECK-NEXT:    [[TMP3:%.*]] = sub i64 [[TMP2:%.*]] [[TMP1:%.*]]
+; CHECK-NEXT:    ret i64 [[TMP3]]
+;
+; Note the reassociate pass and another instcombine pass will further optimize this to
+; "%sub = i64 %i, %j, ret i64 %sub"
+;
+; gep1 and gep2 have only one use
+  %gep1 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 %i
+  %gep2 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 %j
+  %cast1 = ptrtoint i8* %gep1 to i64
+  %cast2 = ptrtoint i8* %gep2 to i64
+  %sub = sub i64 %cast1, %cast2
+  ret i64 %sub
+}
+
+define i64 @test59([100 x [100 x i8]]* %foo, i64 %i) {
+; CHECK-LABEL: @test59(
+; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 %i
+; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 0
+; CHECK-NEXT:    store i8* [[GEP1]], i8** @dummy_global1, align 8
+; CHECK-NEXT:    store i8* [[GEP2]], i8** @dummy_global2, align 8
+; CHECK-NEXT:    ret i64 %i
+;
+; gep1 and gep2 have more than one uses
+  %gep1 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 %i
+  %gep2 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 0
+  %cast1 = ptrtoint i8* %gep1 to i64
+  %cast2 = ptrtoint i8* %gep2 to i64
+  %sub = sub i64 %cast1, %cast2
+  store i8* %gep1, i8** @dummy_global1
+  store i8* %gep2, i8** @dummy_global2
+  ret i64 %sub
+}
+
+define i64 @test60([100 x [100 x i8]]* %foo, i64 %i, i64 %j) {
+; CHECK-LABEL: @test60(
+; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 %j, i64 %i
+; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 0
+; CHECK-NEXT:    [[CAST1:%.*]] = ptrtoint i8* [[GEP1]] to i64
+; CHECK-NEXT:    [[CAST2:%.*]] = ptrtoint i8* [[GEP2]] to i64
+; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[CAST1]], [[CAST2]]
+; CHECK-NEXT:    store i8* [[GEP1]], i8** @dummy_global1, align 8
+; CHECK-NEXT:    ret i64 [[SUB]]
+;
+; gep1 has a non-constant index and more than one uses. Shouldn't duplicate the arithmetic.
+  %gep1 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 %j, i64 %i
+  %gep2 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 0
+  %cast1 = ptrtoint i8* %gep1 to i64
+  %cast2 = ptrtoint i8* %gep2 to i64
+  %sub = sub i64 %cast1, %cast2
+  store i8* %gep1, i8** @dummy_global1
+  ret i64 %sub
+}
+
+define i64 @test61([100 x [100 x i8]]* %foo, i64 %i, i64 %j) {
+; CHECK-LABEL: @test61(
+; CHECK-NEXT:    [[GEP1:%.*]] = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 0
+; CHECK-NEXT:    [[GEP2:%.*]] = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 %j, i64 %i
+; CHECK-NEXT:    [[CAST1:%.*]] = ptrtoint i8* [[GEP1]] to i64
+; CHECK-NEXT:    [[CAST2:%.*]] = ptrtoint i8* [[GEP2]] to i64
+; CHECK-NEXT:    [[SUB:%.*]] = sub i64 [[CAST1]], [[CAST2]]
+; CHECK-NEXT:    store i8* [[GEP2]], i8** @dummy_global2, align 8
+; CHECK-NEXT:    ret i64 [[SUB]]
+;
+; gep2 has a non-constant index and more than one uses. Shouldn't duplicate the arithmetic.
+  %gep1 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 42, i64 0
+  %gep2 = getelementptr inbounds [100 x [100 x i8]], [100 x [100 x i8]]* %foo, i64 0, i64 %j, i64 %i
+  %cast1 = ptrtoint i8* %gep1 to i64
+  %cast2 = ptrtoint i8* %gep2 to i64
+  %sub = sub i64 %cast1, %cast2
+  store i8* %gep2, i8** @dummy_global2
+  ret i64 %sub
+}