[instsimplify] Incorrect fold of comparison involving unescaped malloc

[preames]

We currently have a miscompile in instsimplify. The problem is that we are assuming that an unescaped allocation can not be equal to a value loaded from the global. This assumption was added back in 2016 via commit 43d7e1cbffd66.

Unfortunately, this assumption does not hold. In general, the LangRef allows both "guess and check" via ptrtoint, and "crossover from nearby object" as means for an unescaped object's address to be inspected.

Given the optimizer's freedom to chose a heap layout of its choice, it would seem that we have no problem. We can simply assume that the heap layout is such that any guess made fails.

However, this has a fatal flaw. If we make two or more guesses, we must return a consistent result. The optimizer isn't allowed to both a) assume object isn't at address X, and b) assume object is at address X.

In InstCombine, we have careful handling when handling icmps of allocas for this "single use rule", but we got this wrong for heap allocations.

This is really hard to see in practice as instsimplify will iterate to a fixed point getting multiple comparisons at once (in a consistent manner). We could see this via one of the various consumers of InstructionSimplify, but I was not able to write a test case easily.

Here's the best example I've found:

@G = external global i8*

define void @init() {
  %guess = inttoptr i64 5839400 to i8*
  store i8* %guess, i8** @G
  ret void
}

define i1 @helper(i8* %p) {
  %guess = load i8*, i8** @G, align 8, !nonnull !{}
  %cmp = icmp eq i8* %p, %guess
  ret i1 %cmp
}

declare i8* @malloc(i32)

define i1 @test() {
  %p = call i8* @malloc(i32 4)
  %guess = load i8*, i8** @G, align 8, !nonnull !{}
  %cmp = icmp eq i8* %p, %guess
  %cmp2 = call i1 @helper(i8* %p)
  %res = icmp eq i1 %cmp, %cmp2
  ret i1 %res
}

This example should always return true. But if you run "./opt -S %s -function-attrs -instsimplify", and then the heap allocator does actually place the malloc at the guessed location, it will instead return false. (We fold %cmp to false without also folding the comparison inside helper or %cmp2.)

[preames]

I am planning to generalize the instcombine alloca handling to handle the mallocs as well. This bug exists mostly for exposition sake.

In addition to that change, I want to highlight that the original transform may be valid for non-integral pointers. If we see regressions from fixing this, we can explore whether the non-integral pointers disallows the two forms of guessed pointers. I haven't given that a much a thought yet, and our current LangRef wording isn't precise enough.

[preames]

Patch on review: https://reviews.llvm.org/D120371

[nikic]

https://github.com/llvm/llvm-project/commit/4d192f2d2a545c8cd51ef86f9e83209eccbe229e moves the code out of CaptureTracking into InstSimplify to limit scope.

https://reviews.llvm.org/D144410 is a slightly more limited version of Philip's patch, but see the last comment, this would still be incorrect for other reasons.