[InstCombine] Don't fold a GEP into itself through a PHI node

[djasper]

Summary

This can only occur (I think) through the back-edge of the loop.

However, folding a GEP into itself means that the value of the previous iteration needs to be stored in the meantime, thus requiring an additional register variable to be live, but not actually achieving anything (the gep still needs to be executed once per loop iteration).

The attached test case is derived from:

typedef unsigned uint32;
typedef unsigned char uint8;
inline uint8 *f(uint32 value, uint8 *target) {
  while (value >= 0x80) {
    value >>= 7;
    ++target;
  }
  ++target;
  return target;
}
uint8 *g(uint32 b, uint8 *target) {
  target = f(b, f(42, target));
  return target;
}

What happens is that the GEP stored in incptr2 is folded into itself through the loop's back-edge and the phi-node stored in loopptr, effectively incrementing the ptr by "2" in each iteration instead of "1".

In this case, it is actually increasing the number of GEPs required as the GEP before the loop can't be folded away anymore. For comparison:

With this patch:

define i8* @test4(i32 %value, i8* %buffer) {
entry:
  %cmp = icmp ugt i32 %value, 127
  br i1 %cmp, label %loop.header, label %exit

loop.header:                                      ; preds = %entry
  br label %loop.body

loop.body:                                        ; preds = %loop.body, %loop.header
  %buffer.pn = phi i8* [ %buffer, %loop.header ], [ %loopptr, %loop.body ]
  %newval = phi i32 [ %value, %loop.header ], [ %shr, %loop.body ]
  %loopptr = getelementptr inbounds i8, i8* %buffer.pn, i64 1
  %shr = lshr i32 %newval, 7
  %cmp2 = icmp ugt i32 %newval, 16383
  br i1 %cmp2, label %loop.body, label %loop.exit

loop.exit:                                        ; preds = %loop.body
  br label %exit

exit:                                             ; preds = %loop.exit, %entry
  %0 = phi i8* [ %loopptr, %loop.exit ], [ %buffer, %entry ]
  %incptr3 = getelementptr inbounds i8, i8* %0, i64 2
  ret i8* %incptr3
}

Without this patch:

define i8* @test4(i32 %value, i8* %buffer) {
entry:
  %incptr = getelementptr inbounds i8, i8* %buffer, i64 1
  %cmp = icmp ugt i32 %value, 127
  br i1 %cmp, label %loop.header, label %exit

loop.header:                                      ; preds = %entry
  br label %loop.body

loop.body:                                        ; preds = %loop.body, %loop.header
  %0 = phi i8* [ %buffer, %loop.header ], [ %loopptr, %loop.body ]
  %loopptr = phi i8* [ %incptr, %loop.header ], [ %incptr2, %loop.body ]
  %newval = phi i32 [ %value, %loop.header ], [ %shr, %loop.body ]
  %shr = lshr i32 %newval, 7
  %incptr2 = getelementptr inbounds i8, i8* %0, i64 2
  %cmp2 = icmp ugt i32 %newval, 16383
  br i1 %cmp2, label %loop.body, label %loop.exit

loop.exit:                                        ; preds = %loop.body
  br label %exit

exit:                                             ; preds = %loop.exit, %entry
  %ptr2 = phi i8* [ %incptr2, %loop.exit ], [ %incptr, %entry ]
  %incptr3 = getelementptr inbounds i8, i8* %ptr2, i64 1
  ret i8* %incptr3
}

[hfinkel]

Your patch summary does a good job of explaining the problem and what you're doing. The patch, however, adds no comments. Please add some explaining why the restrictions in the code are there.

[djasper]

Properly documented the reasoning in source code comments.

[djasper]

Forgot to update one of the ifs.

[djasper]

Ping?

[nicholas]

Daniel Jasper wrote:

Ping?

if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands())
  return nullptr;

​
+ // As for Op1 above, don't try to fold a GEP into itself.
+ if (Op2 == &GEP)
+ return nullptr;

Consider folding that into the check above.

LGTM

http://reviews.llvm.org/D8245

EMAIL PREFERENCES

http://reviews.llvm.org/settings/panel/emailpreferences/

---

llvm-commits mailing list
[e-mail]
http://lists.cs.uiuc.edu/mailman/listinfo/llvm-commits

[djasper]

Patch accepted as per Nick's email.

[djasper]

Submitted as r232718.

lib/Transforms/InstCombine/InstructionCombining.cpp

if (MadeChange)
     return &GEP;
 
   // Check to see if the inputs to the PHI node are getelementptr instructions.
   if (PHINode *PN = dyn_cast<PHINode>(PtrOp)) {
     GetElementPtrInst *Op1 = dyn_cast<GetElementPtrInst>(PN->getOperand(0));
     if (!Op1)
       return nullptr;
 
+    // Don't fold a GEP into itself through a PHI node. This can only happen
+    // through the back-edge of a loop. Folding a GEP into itself means that
+    // the value of the previous iteration needs to be stored in the meantime,
+    // thus requiring an additional register variable to be live, but not
+    // actually achieving anything (the GEP still needs to be executed once per
+    // loop iteration).
+    if (Op1 == &GEP)
+      return nullptr;
+
     signed DI = -1;
 
     for (auto I = PN->op_begin()+1, E = PN->op_end(); I !=E; ++I) {
       GetElementPtrInst *Op2 = dyn_cast<GetElementPtrInst>(*I);
       if (!Op2 || Op1->getNumOperands() != Op2->getNumOperands())
         return nullptr;
 
+      // As for Op1 above, don't try to fold a GEP into itself.
+      if (Op2 == &GEP)
+        return nullptr;
+
       // Keep track of the type as we walk the GEP.
       Type *CurTy = Op1->getOperand(0)->getType()->getScalarType();
 
       for (unsigned J = 0, F = Op1->getNumOperands(); J != F; ++J) {
         if (Op1->getOperand(J)->getType() != Op2->getOperand(J)->getType())
           return nullptr;
 
         if (Op1->getOperand(J) != Op2->getOperand(J)) {

test/Transforms/InstCombine/gepphigep.ll

 ; CHECK-LABEL: @test3(
 ; CHECK: bb5:
 ; CHECK-NEXT: {{.*}}landingpad { i8*, i32 } personality i8* bitcast (i32 (...)* @__gxx_personality_v0 to i8*)
 }
 
 @_ZTIi = external constant i8*
 declare i32 @__gxx_personality_v0(...)
 declare i32 @foo1(i32)
+
+
+; Check that instcombine doesn't fold GEPs into themselves through a loop
+; back-edge.
+
+define i8* @test4(i32 %value, i8* %buffer) {
+entry:
+  %incptr = getelementptr inbounds i8, i8* %buffer, i64 1
+  %cmp = icmp ugt i32 %value, 127
+  br i1 %cmp, label %loop.header, label %exit
+
+loop.header:
+  br label %loop.body
+
+loop.body:
+  %loopptr = phi i8* [ %incptr, %loop.header ], [ %incptr2, %loop.body ]
+  %newval = phi i32 [ %value, %loop.header ], [ %shr, %loop.body ]
+  %shr = lshr i32 %newval, 7
+  %incptr2 = getelementptr inbounds i8, i8* %loopptr, i64 1
+  %cmp2 = icmp ugt i32 %shr, 127
+  br i1 %cmp2, label %loop.body, label %loop.exit
+
+loop.exit:
+  %exitptr = phi i8* [ %incptr2, %loop.body ]
+  br label %exit
+
+exit:
+  %ptr2 = phi i8* [ %exitptr, %loop.exit ], [ %incptr, %entry ]
+  %incptr3 = getelementptr inbounds i8, i8* %ptr2, i64 1
+  ret i8* %incptr3
+
+; CHECK-LABEL: @test4(
+; CHECK: loop.body:
+; CHECK: getelementptr{{.*}}i64 1
+; CHECK: exit:
+}