ptrtoint/ptrtoaddr should not unconditionally capture pointers if the capture is not externally observable

[zitongzhoueric]

This C program encounters miscompilation in LoopVectorize when compiled with -O3 It is said this is a known issue, but I cannot find an open issue relating it.

void conflicting_loops ( int * a , int * b , int n ) {
   for ( int i = 0 ; i < n ; i ++ ) { 
       a [ i ] = b [ i ] + i ; 
   }
   for ( int i = 0 ; i < n ; i ++ ) {
       a [ i ] = a [ i ] + i ;
   }
}

Note that the online alive-tv cannot reproduce this yet because of a bug. You can reproduce this using either running alivecc -O3 on the C program, or a very recent build of alive-tv that includes the bug fix.
alive-tv -passes=loop-vectorize -always-verify test.bc: before and after the optimization.

----------------------------------------
define void @conflicting_loops(ptr nocapture noundef %a, ptr nocapture nowrite noundef %b, i32 noundef %n) nofree memory(argmem: readwrite) {
entry:
  %cmp27 = icmp sgt i32 noundef %n, 0
  br i1 %cmp27, label %for.body.preheader, label %for.cond.cleanup6

for.body.preheader:
  %wide.trip.count = zext nneg i32 noundef %n to i64
  br label %for.body

for.body:
  %indvars.iv = phi i64 [ 0, %for.body.preheader ], [ %indvars.iv.next, %for.body ]
  %arrayidx = gep inbounds nuw ptr nocapture nowrite noundef %b, 4 x i64 %indvars.iv
  %#0 = load i32, ptr %arrayidx, align 4
  %#1 = trunc nsw nuw i64 %indvars.iv to i32
  %add = add nsw i32 %#0, %#1
  %arrayidx2 = gep inbounds nuw ptr nocapture noundef %a, 4 x i64 %indvars.iv
  store i32 %add, ptr %arrayidx2, align 4
  %indvars.iv.next = add nsw nuw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
  br i1 %exitcond.not, label %for.body7.preheader, label %for.body

for.body7.preheader:
  %wide.trip.count35 = zext nneg i32 noundef %n to i64
  br label %for.body7

for.body7:
  %indvars.iv32 = phi i64 [ 0, %for.body7.preheader ], [ %indvars.iv.next33, %for.body7 ]
  %arrayidx9 = gep inbounds nuw ptr nocapture noundef %a, 4 x i64 %indvars.iv32
  %#2 = load i32, ptr %arrayidx9, align 4
  %#3 = trunc nsw nuw i64 %indvars.iv32 to i32
  %add10 = add nsw i32 %#2, %#3
  store i32 %add10, ptr %arrayidx9, align 4
  %indvars.iv.next33 = add nsw nuw i64 %indvars.iv32, 1
  %exitcond36.not = icmp eq i64 %indvars.iv.next33, %wide.trip.count35
  br i1 %exitcond36.not, label %for.cond.cleanup6, label %for.body7

for.cond.cleanup6:
  ret void
}
=>
define void @conflicting_loops(ptr nocapture noundef %a, ptr nocapture nowrite noundef %b, i32 noundef %n) nofree memory(argmem: readwrite) {
entry:
  %b2 = ptrtoint ptr nocapture nowrite noundef %b to i64
  %a1 = ptrtoint ptr nocapture noundef %a to i64
  %cmp27 = icmp sgt i32 noundef %n, 0
  br i1 %cmp27, label %for.body.preheader, label %for.cond.cleanup6

for.body.preheader:
  %wide.trip.count = zext nneg i32 noundef %n to i64
  %min.iters.check = icmp ult i64 %wide.trip.count, 8
  br i1 %min.iters.check, label %scalar.ph, label %vector.memcheck

vector.memcheck:
  %#0 = sub i64 %a1, %b2
  %diff.check = icmp ult i64 %#0, 32
  br i1 %diff.check, label %scalar.ph, label %vector.ph

vector.ph:
  %n.mod.vf = urem i64 %wide.trip.count, 8
  %n.vec = sub i64 %wide.trip.count, %n.mod.vf
  br label %vector.body

vector.body:
  %index = phi i64 [ 0, %vector.ph ], [ %index.next, %vector.body ]
  %vec.ind = phi <4 x i32> [ { 0, 1, 2, 3 }, %vector.ph ], [ %vec.ind.next, %vector.body ]
  %step.add = add <4 x i32> %vec.ind, { 4, 4, 4, 4 }
  %#1 = gep inbounds nuw ptr nocapture nowrite noundef %b, 4 x i64 %index
  %#2 = gep inbounds nuw ptr %#1, 4 x i32 4
  %wide.load = load <4 x i32>, ptr %#1, align 4
  %wide.load3 = load <4 x i32>, ptr %#2, align 4
  %#3 = add nsw <4 x i32> %wide.load, %vec.ind
  %#4 = add nsw <4 x i32> %wide.load3, %step.add
  %#5 = gep inbounds nuw ptr nocapture noundef %a, 4 x i64 %index
  %#6 = gep inbounds nuw ptr %#5, 4 x i32 4
  store <4 x i32> %#3, ptr %#5, align 4
  store <4 x i32> %#4, ptr %#6, align 4
  %index.next = add nuw i64 %index, 8
  %vec.ind.next = add <4 x i32> %step.add, { 4, 4, 4, 4 }
  %#7 = icmp eq i64 %index.next, %n.vec
  br i1 %#7, label %middle.block, label %vector.body

middle.block:
  %cmp.n = icmp eq i64 %wide.trip.count, %n.vec
  br i1 %cmp.n, label %for.body7.preheader, label %scalar.ph

scalar.ph:
  %bc.resume.val = phi i64 [ %n.vec, %middle.block ], [ 0, %for.body.preheader ], [ 0, %vector.memcheck ]
  br label %for.body

for.body:
  %indvars.iv = phi i64 [ %bc.resume.val, %scalar.ph ], [ %indvars.iv.next, %for.body ]
  %arrayidx = gep inbounds nuw ptr nocapture nowrite noundef %b, 4 x i64 %indvars.iv
  %#8 = load i32, ptr %arrayidx, align 4
  %#9 = trunc nsw nuw i64 %indvars.iv to i32
  %add = add nsw i32 %#8, %#9
  %arrayidx2 = gep inbounds nuw ptr nocapture noundef %a, 4 x i64 %indvars.iv
  store i32 %add, ptr %arrayidx2, align 4
  %indvars.iv.next = add nsw nuw i64 %indvars.iv, 1
  %exitcond.not = icmp eq i64 %indvars.iv.next, %wide.trip.count
  br i1 %exitcond.not, label %for.body7.preheader, label %for.body

for.body7.preheader:
  %wide.trip.count35 = zext nneg i32 noundef %n to i64
  %min.iters.check5 = icmp ult i64 %wide.trip.count, 8
  br i1 %min.iters.check5, label %scalar.ph4, label %vector.ph6

vector.ph6:
  %n.mod.vf7 = urem i64 %wide.trip.count, 8
  %n.vec8 = sub i64 %wide.trip.count, %n.mod.vf7
  br label %vector.body9

vector.body9:
  %index10 = phi i64 [ 0, %vector.ph6 ], [ %index.next15, %vector.body9 ]
  %vec.ind11 = phi <4 x i32> [ { 0, 1, 2, 3 }, %vector.ph6 ], [ %vec.ind.next16, %vector.body9 ]
  %step.add12 = add <4 x i32> %vec.ind11, { 4, 4, 4, 4 }
  %#10 = gep inbounds nuw ptr nocapture noundef %a, 4 x i64 %index10
  %#11 = gep inbounds nuw ptr %#10, 4 x i32 4
  %wide.load13 = load <4 x i32>, ptr %#10, align 4
  %wide.load14 = load <4 x i32>, ptr %#11, align 4
  %#12 = add nsw <4 x i32> %wide.load13, %vec.ind11
  %#13 = add nsw <4 x i32> %wide.load14, %step.add12
  store <4 x i32> %#12, ptr %#10, align 4
  store <4 x i32> %#13, ptr %#11, align 4
  %index.next15 = add nuw i64 %index10, 8
  %vec.ind.next16 = add <4 x i32> %step.add12, { 4, 4, 4, 4 }
  %#14 = icmp eq i64 %index.next15, %n.vec8
  br i1 %#14, label %middle.block17, label %vector.body9

middle.block17:
  %cmp.n18 = icmp eq i64 %wide.trip.count, %n.vec8
  br i1 %cmp.n18, label %for.cond.cleanup6.loopexit, label %scalar.ph4

scalar.ph4:
  %bc.resume.val19 = phi i64 [ %n.vec8, %middle.block17 ], [ 0, %for.body7.preheader ]
  br label %for.body7

for.body7:
  %indvars.iv32 = phi i64 [ %bc.resume.val19, %scalar.ph4 ], [ %indvars.iv.next33, %for.body7 ]
  %arrayidx9 = gep inbounds nuw ptr nocapture noundef %a, 4 x i64 %indvars.iv32
  %#15 = load i32, ptr %arrayidx9, align 4
  %#16 = trunc nsw nuw i64 %indvars.iv32 to i32
  %add10 = add nsw i32 %#15, %#16
  store i32 %add10, ptr %arrayidx9, align 4
  %indvars.iv.next33 = add nsw nuw i64 %indvars.iv32, 1
  %exitcond36.not = icmp eq i64 %indvars.iv.next33, %wide.trip.count35
  br i1 %exitcond36.not, label %for.cond.cleanup6.loopexit, label %for.body7

for.cond.cleanup6.loopexit:
  br label %for.cond.cleanup6

for.cond.cleanup6:
  ret void
}
Transformation doesn't verify!

ERROR: Source is more defined than target

Example:
ptr nocapture noundef %a = null
ptr nocapture nowrite noundef %b = null
i32 noundef %n = #x00000000 (0)

Source:
i1 %cmp27 = #x0 (0)
  >> Jump to %for.cond.cleanup6

SOURCE MEMORY STATE
===================
NON-LOCAL BLOCKS:
Block 0 >       size: 0 align: 4        alloc type: 0   alive: false    address: #x0000000000000000
Block 1 >       size: 0 align: 1        alloc type: 0   alive: true     address: #x000000000000000d
Block 2 >       size: 0 align: 1        alloc type: 0   alive: true     address: #x0000000000000004

Target:
i64 %b2 = UB triggered!


Summary:
  0 correct transformations
  1 incorrect transformations
  0 failed-to-prove transformations
  0 Alive2 errors

[fhahn]

Thanks, will share a fix soon

[fhahn]

Hmm, I am working on a patch to add support for PtrToAddr to SCEV, but I'm not sure if using ptrtoaddr is enough to fix this, as ptrtoaddr would still caputure the address? Note that this isn't limited to LV, I think we could hit this for any loop where we xpand a trip count based on pointer differences. cc @nikic @efriedma-quic

[nikic]

Hmm, I am working on a patch to add support for PtrToAddr to SCEV,

I haven't looked into this too deeply, but I don't think we want to add PtrToAddr to SCEV, we'd want to replace PtrToInt with it, once we have sufficient ptrtoaddr support elsewhere to allow using it at all. (SCEV ptrtoint semantics basically match IR ptrtoaddr semantics...)

but I'm not sure if using ptrtoaddr is enough to fix this, as ptrtoaddr would still caputure the address? Note that this isn't limited to LV, I think we could hit this for any loop where we xpand a trip count based on pointer differences.

Yes: I don't think there is an actual miscompilation here. Marking an argument as captures(none) should be fine as long as the capture is not externally observable, even if the address is inspected within the function. Basically foo(p) { if (p == 0xdeadbeef) return 1; else return 1; } should be captures(none) because the address inspection is unobservable. There is no capture effect.

How to define this operationally is left as an exercise to the reader :)

[nikic]

cc @nunoplopes Maybe you have an idea on how to best specify address capture semantics. What we basically need is that the behavior of the function doesn't change for any possible choice of address.

[fhahn]

Yes: I don't think there is an actual miscompilation here. Marking an argument as captures(none) should be fine as long as the capture is not externally observable, even if the address is inspected within the function. Basically foo(p) { if (p == 0xdeadbeef) return 1; else return 1; } should be captures(none) because the address inspection is unobservable. There is no capture effect.

yeah that sounds right, although it is probably indeed a bit difficult to spell this out; current LangRef says that ptrtoaddr always captures the address, which I guess would need to be refined.

[fhahn]

(anything else would also be quite impractical, as it would prevent us from vectorizing/expanding trip counts, if it would mean introducing ptrtoint/ptrtoaddr for something marks as capture(none))