[InstSimplify] Don't fold comparisons of non-inbounds GEPs

[LemonBoy]

Summary

The logic employed by the constant folder assumes the GEPs to be inbounds, when applied to other GEPs the result can be potentially incorrect and cause miscompilations.

[LemonBoy]

llvm/lib/IR/ConstantFold.cpp

1837

Are non-inbounds GEP common enough to implement this?

[lebedev.ri]

This seems to be correct?
https://alive2.llvm.org/ce/z/JyimAB

[nikic]

@nlopes Can you please take a look at the alive result? I don't think the transform is correct, but alive says it is. The result of the GEP is a pointer of value zero. It has different provenance from the null pointer, but icmp eq should be a pure value comparison, independent of provenance, right?

llvm/lib/IR/ConstantFold.cpp

1837

I'd generally say that we should handle inbounds precisely just for the sake of clarity -- however, after reviewing all the folds below, it looks like all of them either require inbounds, or can only work on GEPs for which we would infer inbounds anyway (e.g. the gep GV1, 0 icmp gep GV2, 0 case). Given that, the early out here should be fine, and I think you can drop the TODO as well.

1847–1850

Unrelated to this patch, but all the isSigned handling in this code looks wrong to me. This is effectively saying that GlobalValues can only appear in the lower half of the address space and not in the upper (negative) half, which is not true.

[aqjune]

I don't have a clear model for the semantics of pointer comparison ATM; Pointer comparison *sometimes* needs to take provenance into consideration because LLVM folds p1 == p2 where p1 and p2 are pointing to two different zero-size objects having the same address into false.
Also, considering provenance into account allows aggressively folding pointer comparisons. It isn't clear how *frequently* the provenance should be considered.

But, I'm rather curious about how the miscompilation happened from this optimization. A gep with such offset isn't common, unless a programmer writes a code that subtracts a pointer from null (which is already fishy)?
It would be great if I can see the input that causes miscompilation.

[aqjune]

I don't have a clear model for the semantics of pointer comparison ATM; Pointer comparison *sometimes* needs to take provenance into consideration because LLVM folds p1 == p2 where p1 and p2 are pointing to two different zero-size objects having the same address into false.
Also, considering provenance into account allows aggressively folding pointer comparisons. It isn't clear how *frequently* the provenance should be considered.

FWIW, these are a few examples and relevant links:

• A ptr comparison folding to false regardless of addresses of two possibly overlapping stack allocations: https://godbolt.org/z/ok4vFJ , bugzilla report: https://bugs.llvm.org/show_bug.cgi?id=44342
• Another example: https://godbolt.org/z/bhrsK1 (well it wasn't a zero-size object, but simply merging two identical global objects. Anyway it shows that defining ptr comparison is something non-trivial), reduced from: https://bugs.llvm.org/show_bug.cgi?id=47090 , https://github.com/rust-lang/rust/issues/73722

[nikic]

In D97665#2601852, @aqjune wrote:

I don't have a clear model for the semantics of pointer comparison ATM; Pointer comparison *sometimes* needs to take provenance into consideration because LLVM folds p1 == p2 where p1 and p2 are pointing to two different zero-size objects having the same address into false.
Also, considering provenance into account allows aggressively folding pointer comparisons. It isn't clear how *frequently* the provenance should be considered.

But, I'm rather curious about how the miscompilation happened from this optimization. A gep with such offset isn't common, unless a programmer writes a code that subtracts a pointer from null (which is already fishy)?
It would be great if I can see the input that causes miscompilation.

I'm not sure why zig generates this code, but the context here is https://github.com/ziglang/zig/issues/6408. The issue was exposed by D93820, as we previously simply folded away the GEP to null, losing provenance.

My understanding was that the current resolution on pointer comparison issues is that pointer comparison is value-only, and provenance-losing equality replacements in GVN are what we consider incorrect. But I haven't followed all the discussions.

The original case here was actually not "gep == null", but "ptrtoint gep == 0", in which case it's obviously a pure value comparison, but InstSimplify looks through that. Do you think that's the real issue?

[LemonBoy]

But, I'm rather curious about how the miscompilation happened from this optimization. A gep with such offset isn't common, unless a programmer writes a code that subtracts a pointer from null (which is already fishy)?
It would be great if I can see the input that causes miscompilation.

As stated here the gep is being generated by the SCEV pass.
A minimal test case that shows the gep being created (but not this miscompilation) is here.

llvm/lib/IR/ConstantFold.cpp

1837

Some trivial geps can still be folded such as all-zero ones vs constant or unsigned comparisons with zero. But yes, I'll drop the TODO as those cases are pretty rare.

1847–1850

Yes, that looks wrong. I guess this is unlikely to cause problems as most (every?) pointer comparisons against null are of eq/neq type.

[lebedev.ri]

In D97665#2602726, @LemonBoy wrote:

But, I'm rather curious about how the miscompilation happened from this optimization. A gep with such offset isn't common, unless a programmer writes a code that subtracts a pointer from null (which is already fishy)?
It would be great if I can see the input that causes miscompilation.

As stated here the gep is being generated by the SCEV pass.
A minimal test case that shows the gep being created (but not this miscompilation) is here.

(i've already been looking at the scev problem, maybe will post patch soon-ish)

[nikic]

Resigning here, based on past experience trying to challenge the Word Of God. It really doesn't help that someone opened an alive issue for this without cross-referencing it, so the same discussion is repeated twice.

[aqjune]

In D97665#2602696, @nikic wrote:

The original case here was actually not "gep == null", but "ptrtoint gep == 0", in which case it's obviously a pure value comparison, but InstSimplify looks through that. Do you think that's the real issue?

Actually this is indeed a problematic transformation; you said a very valid point.
Removing it has large impact (it leaves ptrtoint to an object which is conservatively considered to escape the object), so simply removing the transformation is hard ATM, but I believe it should be removed at some point.

It is bad that there were two discussions with the same topic; maybe the link was not shared here because the Alive2's side did not have a very clear solution about ptr comparison as well. If I could answer anything clear about the pointer comparison, the link must have been shared :(

In D97665#2602738, @lebedev.ri wrote:

(i've already been looking at the scev problem, maybe will post patch soon-ish)

+1, Fixing SCEV seems to be the easiest solution at this point.

[nikic]

Alive pointer icmp semantics have recently been fixed and now agree that this is a miscompile, so I think we should move forward with this patch. It will need a rebase as some additional tests have been added in the meantime. This should also fix https://bugs.llvm.org/show_bug.cgi?id=50208.

[LemonBoy]

Rebased. I've moved the test to icmp-null.ll and made it a bit nicer.

[nikic]

llvm/test/Transforms/InstSimplify/ConstProp/icmp-null.ll

203

For the tests that changed, could you please add a copy that has the inbounds keyword, so that the folding case is still covered?

[LemonBoy]

llvm/test/Transforms/InstSimplify/ConstProp/icmp-null.ll

203

There's something weird going on, SimplifyGEPInst in InstructionSimplify.cpp is silently dropping the inbounds flag thus preventing the fold from happening.

[LemonBoy]

Ping?

[nlopes]

Since we settled on pointer comparison being equivalent to address comparison (i.e., provenance is not taken into account), then the current code is correct.
See table 2 here, for example: https://web.ist.utl.pt/nuno.lopes/pubs/alive2-mem-cav21.pdf#page=10

Therefore I suggest we drop this patch.

The optimization that is wrong under this model is one in InstSimplify that folds pointer comparison between pointers of different objects to false. That is not correct for geps that aren't inbounds.

llvm/lib/IR/ConstantFold.cpp

case Instruction::SExt:
         return evaluateICmpRelation(CE1Op0,
                                     Constant::getNullValue(CE1Op0->getType()),
                                     isSigned);
       }
       break;
 
     case Instruction::GetElementPtr: {
       GEPOperator *CE1GEP = cast<GEPOperator>(CE1);
+
+      // The foldings below assume the GEP to be inbounds.
+      // TODO: Some of the logic can be applied for non-inbounds GEPs as well.
+      if (!CE1GEP->isInBounds())
+        return ICmpInst::BAD_ICMP_PREDICATE;
+
       // Ok, since this is a getelementptr, we know that the constant has a
       // pointer type.  Check the various cases.
       if (isa<ConstantPointerNull>(V2)) {
         // If we are comparing a GEP to a null pointer, check to see if the base
         // of the GEP equals the null pointer.
         if (const GlobalValue *GV = dyn_cast<GlobalValue>(CE1Op0)) {
           // If its not weak linkage, the GVal must have a non-zero address
           // so the result is greater-than
           if (!GV->hasExternalWeakLinkage())
             return ICmpInst::ICMP_UGT;
         } else if (isa<ConstantPointerNull>(CE1Op0)) {
           // If we are indexing from a null pointer, check to see if we have any
           // non-zero indices.
           for (unsigned i = 1, e = CE1->getNumOperands(); i != e; ++i)
             if (!CE1->getOperand(i)->isNullValue())
               // Offsetting from null, must not be equal.
               return ICmpInst::ICMP_UGT;
           // Only zero indexes from null, must still be zero.

llvm/test/Transforms/InstSimplify/ConstProp/icmp-null.ll

 ;
   %gep = getelementptr inbounds [2 x i32], [2 x i32]* @g, i64 1
   %cmp = icmp sgt [2 x i32]* %gep, null
   ret i1 %cmp
 }
 
 define i1 @null_gep_ne_null() {
 ; CHECK-LABEL: @null_gep_ne_null(
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 icmp ne (i8* getelementptr (i8, i8* null, i64 ptrtoint (i32* @g2 to i64)), i8* null)
 ;
   %gep = getelementptr i8, i8* null, i64 ptrtoint (i32* @g2 to i64)
   %cmp = icmp ne i8* %gep, null
   ret i1 %cmp
 }
 
 define i1 @null_gep_ugt_null() {
 ; CHECK-LABEL: @null_gep_ugt_null(
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 icmp ugt (i8* getelementptr (i8, i8* null, i64 ptrtoint (i32* @g2 to i64)), i8* null)
 ;
   %gep = getelementptr i8, i8* null, i64 ptrtoint (i32* @g2 to i64)
   %cmp = icmp ugt i8* %gep, null
   ret i1 %cmp
 }
 
 define i1 @null_gep_sgt_null() {
 ; CHECK-LABEL: @null_gep_sgt_null(
 ; CHECK-NEXT:    ret i1 icmp sgt (i8* getelementptr (i8, i8* null, i64 ptrtoint (i32* @g2 to i64)), i8* null)
 ;
   %gep = getelementptr i8, i8* null, i64 ptrtoint (i32* @g2 to i64)
   %cmp = icmp sgt i8* %gep, null
   ret i1 %cmp
 }
 
 define i1 @null_gep_ne_global() {
 ; CHECK-LABEL: @null_gep_ne_global(
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 icmp ne ([2 x i32]* getelementptr ([2 x i32], [2 x i32]* null, i64 ptrtoint (i32* @g2 to i64)), [2 x i32]* @g)
 ;
   %gep = getelementptr [2 x i32], [2 x i32]* null, i64 ptrtoint (i32* @g2 to i64)
   %cmp = icmp ne [2 x i32]* %gep, @g
   ret i1 %cmp
 }
 
 define i1 @null_gep_ult_global() {
 ; CHECK-LABEL: @null_gep_ult_global(
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 icmp ult ([2 x i32]* getelementptr ([2 x i32], [2 x i32]* null, i64 ptrtoint (i32* @g2 to i64)), [2 x i32]* @g)
 ;
   %gep = getelementptr [2 x i32], [2 x i32]* null, i64 ptrtoint (i32* @g2 to i64)
   %cmp = icmp ult [2 x i32]* %gep, @g
   ret i1 %cmp
 }
 
 define i1 @null_gep_slt_global() {
 ; CHECK-LABEL: @null_gep_slt_global(

 ;
   %gep = getelementptr inbounds [2 x i32], [2 x i32]* @g, i64 1
   %cmp = icmp sgt [2 x i32]* %gep, @g
   ret i1 %cmp
 }
 
 define i1 @global_gep_ugt_global_neg_offset() {
 ; CHECK-LABEL: @global_gep_ugt_global_neg_offset(
-; CHECK-NEXT:    ret i1 true
+; CHECK-NEXT:    ret i1 icmp ugt ([2 x i32]* getelementptr ([2 x i32], [2 x i32]* @g, i64 -1), [2 x i32]* @g)
 ;
   %gep = getelementptr [2 x i32], [2 x i32]* @g, i64 -1
   %cmp = icmp ugt [2 x i32]* %gep, @g
   ret i1 %cmp
 }
 
 define i1 @global_gep_sgt_global_neg_offset() {
 ; CHECK-LABEL: @global_gep_sgt_global_neg_offset(
 ; CHECK-NEXT:    ret i1 icmp sgt ([2 x i32]* getelementptr ([2 x i32], [2 x i32]* @g, i64 -1), [2 x i32]* @g)
 ;
   %gep = getelementptr [2 x i32], [2 x i32]* @g, i64 -1
   %cmp = icmp sgt [2 x i32]* %gep, @g
   ret i1 %cmp
 }
+
+; The offset is negative and equal to the base pointer.
+
+define i1 @global_gep_eq_global_offset_neg() {
+; CHECK-LABEL: @global_gep_eq_global_offset_neg(
+; CHECK-NEXT:    ret i1 icmp eq ([2 x i32]* getelementptr ([2 x i32], [2 x i32]* @g, i64 sub (i64 0, i64 ptrtoint ([2 x i32]* @g to i64))), [2 x i32]* null)
+;
+  %off = sub i64 0, ptrtoint ([2 x i32]* @g to i64)
+  %gep = getelementptr [2 x i32], [2 x i32]* @g, i64 %off
+  %cmp = icmp eq [2 x i32]* %gep, null
+  ret i1 %cmp
+}
+
+define i1 @global_gep_ne_global_offset_neg() {
+; CHECK-LABEL: @global_gep_ne_global_offset_neg(
+; CHECK-NEXT:    ret i1 icmp ne ([2 x i32]* getelementptr ([2 x i32], [2 x i32]* @g, i64 sub (i64 0, i64 ptrtoint ([2 x i32]* @g to i64))), [2 x i32]* null)
+;
+  %off = sub i64 0, ptrtoint ([2 x i32]* @g to i64)
+  %gep = getelementptr [2 x i32], [2 x i32]* @g, i64 %off
+  %cmp = icmp ne [2 x i32]* %gep, null
+  ret i1 %cmp
+}