[TRE] icmp does not escape an alloca

[caojoshua]

Summary

Potentially fixes https://github.com/rust-lang/rust/issues/111603.
Marking tail calls helps MemCpyOptimizer and AliasAnalysis remove a
memcpy.

[caojoshua]

Add details to commit msg

[caojoshua]

edit commit msg

[nikic]

This should be implemented in CaptureTracking first and foremost. TRE can be adjusted afterwards, or preferably should use CaptureTracking as well, instead of doing its own, incorrect reimplementation.

Just considering all icmps non-escaping is obviously wrong. The property you are looking for here is that if you have an icmp where both sides are at some offset of the same underlying object, then the icmp will only compare the offsets and not leak any bits of the pointer, and as such is not capturing.

[caojoshua]

In D151638#4378825, @nikic wrote:

This should be implemented in CaptureTracking first and foremost. TRE can be adjusted afterwards, or preferably should use CaptureTracking as well, instead of doing its own, incorrect reimplementation.

Just considering all icmps non-escaping is obviously wrong. The property you are looking for here is that if you have an icmp where both sides are at some offset of the same underlying object, then the icmp will only compare the offsets and not leak any bits of the pointer, and as such is not capturing.

Thanks for review. I don't understand how icmp's leak bits of a pointer. I asked this in https://discord.com/channels/636084430946959380/636732535434510338/1112644263029776414 as well. Could you take a look?

[nikic]

In D151638#4378847, @caojoshua wrote:

In D151638#4378825, @nikic wrote:

This should be implemented in CaptureTracking first and foremost. TRE can be adjusted afterwards, or preferably should use CaptureTracking as well, instead of doing its own, incorrect reimplementation.

Just considering all icmps non-escaping is obviously wrong. The property you are looking for here is that if you have an icmp where both sides are at some offset of the same underlying object, then the icmp will only compare the offsets and not leak any bits of the pointer, and as such is not capturing.

Thanks for review. I don't understand how icmp's leak bits of a pointer. I asked this in https://discord.com/channels/636084430946959380/636732535434510338/1112644263029776414 as well. Could you take a look?

In the simplest case, icmp ptr eq %p, %p2 leaks whether the address of %p is the same as %p2. You could loop over all 2^64 possible %p2 to determine the address. Or more realistically, you could use inequality comparisons to bisect the address. Effectively you can implement ptrtoint with it.

That said, I've looked a bit closer at what this specific pass does, and as far as I can tell it does not actually care about address capture, only about provenance escape. So I think the legality question as far as this pass is concerned is, after determining the bits of the alloca address via a sequence of icmps, is it legal to perform an inttoptr operation and dereference the result? That is, does icmp only leak address bits, or can it also leak provenance?

If icmp does not leak provenance, then your patch is correct as-is. Otherwise we need the general reasoning about whether the icmp is capturing or not, as I described above.

I think icmp shouldn't leak provenance, but I couldn't find a definitive statement on this. Possibly this is caught up in the larger question of the provenance model around pointer/integer conversions, which icmps effectively perform.

Maybe @efriedma could comment on this.

[caojoshua]

I also think that icmp should not leak provenance. However, after looking at your example, I think TRE actually does care about address capture. If the address is captured by another pointer such as %p2 in your example, and we pass that pointer as an argument to a capturing call, %p is also captured and we can't mark tail calls. In this case, my patch is incorrect.

This should be implemented in CaptureTracking first and foremost. TRE can be adjusted afterwards, or preferably should use CaptureTracking as well, instead of doing its own, incorrect reimplementation.
Just considering all icmps non-escaping is obviously wrong. The property you are looking for here is that if you have an icmp where both sides are at some offset of the same underlying object, then the icmp will only compare the offsets and not leak any bits of the pointer, and as such is not capturing.

Extending CaptureTracking to support icmp's of pointers with the same underlying object seems like a reasonable choice. TRE's ad-hoc escape analysis has some specifics that may make it non-trivial to port to CaptureTracking, but we can look at that afterwards.

[jdoerfert]

ICMP, in general, captures. Check the tests for the capture tracker for examples.

[caojoshua]

I'm going to abandon this. This issue can be solved in other ways. CaptureTracking can be improved, and this TRE-specific escape analysis can probably be rewritten in ways that depend on capture tracking

llvm/lib/Transforms/Scalar/TailRecursionElimination.cpp

while (!Worklist.empty()) {
         callUsesLocalStack(CB, IsNocapture);
         if (IsNocapture) {
           // If the alloca-derived argument is passed in as nocapture, then it
           // can't propagate to the call's return. That would be capturing.
           continue;
         }
         break;
       }
+      case Instruction::ICmp:
       case Instruction::Load: {
         // The result of a load is not alloca-derived (unless an alloca has
         // otherwise escaped, but this is a local analysis).
         continue;
       }
       case Instruction::Store: {
         if (U->getOperandNo() == 0)
           EscapePoints.insert(I);

llvm/test/Transforms/TailCallElim/basic.ll

entry:
   call void @llvm.memcpy.p0.p0.i64(ptr %agg.tmp, ptr %f, i64 40, i1 false)
   call void @bar(ptr byval(%struct.foo) %agg.tmp)
   ret void
 }
 
 ; Test that using an alloca in a icmp does not escape it
 define void @test16() {
 ; CHECK-LABEL: @test16
-; CHECK-NOT: tail call void @noarg
+; CHECK: tail call void @noarg
 ; CHECK-NOT: tail call void @use
 entry:
   %alloca = alloca [100 x i32]
   %add.ptr = getelementptr inbounds i32, ptr %alloca, i64 200
   br label %while.cond
 
 while.cond:                                       ; preds = %while.body, %entry
   %iter.0 = phi ptr [ %alloca, %entry ], [ %add.ptr2, %while.body ]