Simplify gep (gep p, a), (b-a)

[ranma42]

Summary

This patch extends the patterns recognised by InstCombine to also optimise gep (gep p, a), (b-a) into gep p, b.
Some minor refactoring was done in order to make the various optimisation/shortcut cases share the same code structure.

The missing optimisation was found investigating why LLVM did not optimise away pointer computations in Rust slices: https://github.com/rust-lang/rust/pull/37921

[ranma42]

Should I ping somebody to get started with the review?

[efriedma]

Can we make this code a bit more general? Something like if (Value* Simplified = SimplifyAddInst(GO1, SO1, ...).

[ranma42]

The new patch extends the patterns recognised by InstCombine as suggested by Eli Friedman.
It can now optimise any gep (gep p, a), b which can be represented as gep p, a+b whenever the a+b operation is folded or simplified away by InstSimplify.
This strictly extends the patterns that are captured, because the previous code only simplified the addition when one operand was 0 or both were constant.

[davide]

In D27413#623355, @ranma42 wrote:

The new patch extends the patterns recognised by InstCombine as suggested by Eli Friedman.
It can now optimise any gep (gep p, a), b which can be represented as gep p, a+b whenever the a+b operation is folded or simplified away by InstSimplify.
This strictly extends the patterns that are captured, because the previous code only simplified the addition when one operand was 0 or both were constant.

Is it possible to add a test to show the generalized behaviour?

[ranma42]

The const+const pattern is already tested by test3 in test/Transforms/InstCombine/getelementptr.ll
Are there any other specific patterns that might be important to include in the patch?

I can write tests for more patterns, but I have no clue on how to check that any instcombine-able pattern will be folded away. Is it possible to do that? Any hints on how it could be achieved?

[davide]

In D27413#623414, @ranma42 wrote:

The const+const pattern is already tested by test3 in test/Transforms/InstCombine/getelementptr.ll
Are there any other specific patterns that might be important to include in the patch?

I can write tests for more patterns, but I have no clue on how to check that any instcombine-able pattern will be folded away. Is it possible to do that? Any hints on how it could be achieved?

Showing that any pattern will be folded may be hard, but if you can add some more patterns, that will be nice.

[ranma42]

Added tests for more add simplification cases.

[davide]

lib/Transforms/InstCombine/InstructionCombining.cpp

1588–1592

You can fold the SimplifyAddInst inside the if, no?

[davide]

test/Transforms/InstCombine/getelementptr.ll

886–893

My understanding of the transform is that the first gep will be removed right?
So, maybe add
CHECK-NOT: getelementptr i32, i32* %I, i64 %C
here and in the other tests?

[efriedma]

I'm not really a fan of CHECK-NOT in most cases; tests using it have a tendency to bitrot over time. Better to use CHECK-NEXT to make sure there aren't any unexpected instructions in the optimized function.

[davide]

In D27413#625375, @efriedma wrote:

I'm not really a fan of CHECK-NOT in most cases; tests using it have a tendency to bitrot over time. Better to use CHECK-NEXT to make sure there aren't any unexpected instructions in the optimized function.

Sure, CHECK-NEXT is probably better.

[ranma42]

lib/Transforms/InstCombine/InstructionCombining.cpp

1588–1592

As in

if (!(Sum = SimplifyAddInst(GO1, SO1, false, false, DL, &TLI, &DT, &AC)))

?
I was afraid that it was less readable, but I can definitely do that :)

[davide]

lib/Transforms/InstCombine/InstructionCombining.cpp

1588–1592

up to you. The API is actually quite verbose already because it takes a lot of arguments. Anyway, I'm OK with this but please wait for others to comment.

[ranma42]

Use CHECK-NEXT as suggested

[ranma42]

lib/Transforms/InstCombine/InstructionCombining.cpp

1588–1592

I received no other comments on this. Should I proceed with your suggestion?

[ranma42]

Ping?

[efriedma]

LGTM.

[davide]

lg. Do you need somebody to commit this on your behalf?

[ranma42]

Awesome!

Yes, I need someone to commit the patch on my behalf.
Thank you for your suggestions and help :)

[davide]

In D27413#650236, @ranma42 wrote:

Awesome!

Yes, I need someone to commit the patch on my behalf.
Thank you for your suggestions and help :)

Committing this for you after a round of ninja check-all. Thanks!

lib/Transforms/InstCombine/InstructionCombining.cpp

if (GEPOperator *Src = dyn_cast<GEPOperator>(PtrOp)) {
     // Can we combine the two pointer arithmetics offsets?
     if (EndsWithSequential) {
       // Replace: gep (gep %P, long B), long A, ...
       // With:    T = long A+B; gep %P, T, ...
       //
       Value *Sum;
       Value *SO1 = Src->getOperand(Src->getNumOperands()-1);
       Value *GO1 = GEP.getOperand(1);
+
+      // Only do the combine when we are sure the cost after the
+      // merge is never more than that before the merge.
       if (SO1 == Constant::getNullValue(SO1->getType())) {
         Sum = GO1;
       } else if (GO1 == Constant::getNullValue(GO1->getType())) {
         Sum = SO1;
-      } else {
+      } else if (SO1->getType() != GO1->getType()) {
         // If they aren't the same type, then the input hasn't been processed
         // by the loop above yet (which canonicalizes sequential index types to
         // intptr_t).  Just avoid transforming this until the input has been
         // normalized.
-        if (SO1->getType() != GO1->getType())
-          return nullptr;
-        // Only do the combine when GO1 and SO1 are both constants. Only in
-        // this case, we are sure the cost after the merge is never more than
-        // that before the merge.
-        if (!isa<Constant>(GO1) || !isa<Constant>(SO1))
-          return nullptr;
+      } else if (isa<Constant>(GO1) && isa<Constant>(SO1)) {
+        // GO1 and SO1 are both constants, combine them
         Sum = Builder->CreateAdd(SO1, GO1, PtrOp->getName()+".sum");
+      } else if (match(GO1, m_Sub(m_Value(Sum), m_Specific(SO1)))) {
+        // GO1 = V - SO1, combine them
+        // Sum = GO1 + SO1 = (V - SO1) + SO1 = V (captured by the match)
+      } else {
+        return nullptr;
       }
 
       // Update the GEP in place if possible.
       if (Src->getNumOperands() == 2) {
         GEP.setOperand(0, Src->getOperand(0));
         GEP.setOperand(1, Sum);
         return &GEP;
       }
       Indices.append(Src->op_begin()+1, Src->op_end()-1);
       Indices.push_back(Sum);
       Indices.append(GEP.op_begin()+2, GEP.op_end());
     } else if (isa<Constant>(*GEP.idx_begin()) &&
                cast<Constant>(*GEP.idx_begin())->isNullValue() &&
                Src->getNumOperands() != 1) {
       // Otherwise we can do the fold if the first index of the GEP is a zero
       Indices.append(Src->op_begin()+1, Src->op_end());
       Indices.append(GEP.idx_begin()+1, GEP.idx_end());
     }
 
     if (!Indices.empty())
       return GEP.isInBounds() && Src->isInBounds()

test/Transforms/InstCombine/getelementptr.ll

 ; CHECK-LABEL: @test46(
 ; CHECK-NEXT:  [[PTRTOINT:%.*]] = ptrtoint %struct.C* %c1 to i64
 ; CHECK-NEXT:  [[SUB:%.*]] = sub i64 0, [[PTRTOINT]]
 ; CHECK-NEXT:  [[SDIV:%.*]] = sdiv i64 [[SUB]], %N
 ; CHECK-NEXT:  [[GEP:%.*]] = getelementptr inbounds %struct.C, %struct.C* %c2, i64 %sdiv
 ; CHECK-NEXT:  ret %struct.C* [[GEP]]
 }
 
+define i32* @test47(i32* %I, i64 %C, i64 %D) {
+  %A = getelementptr i32, i32* %I, i64 %C
+  %sub = sub i64 %D, %C
+  %B = getelementptr i32, i32* %A, i64 %sub
+  ret i32* %B
+; CHECK-LABEL: @test47(
+; CHECK: %B = getelementptr i32, i32* %I, i64 %D
+}
+
 define i32 addrspace(1)* @ascast_0_gep(i32* %p) nounwind {
 ; CHECK-LABEL: @ascast_0_gep(
 ; CHECK-NOT: getelementptr
 ; CHECK: ret
   %gep = getelementptr i32, i32* %p, i32 0
   %x = addrspacecast i32* %gep to i32 addrspace(1)*
   ret i32 addrspace(1)* %x
 }