Am Di., 12. Jan. 2021 um 12:33 Uhr schrieb Ralf Jung via llvm-dev <llvm-dev at lists.llvm.org>:> I hope this question has not been answered yet, but I don't see how that fold > could be legal. I asked the same question on Phabricator but it seems you prefer > to have the discussion here. Taking your example from there and adjusting it: > > p = malloc(1) > q = malloc(1) > %c = icmp eq %p, %q > free(q) > free(p) > > I think there is a guarantee that c will always be "false". Every operational > model of allocation that I have ever seen will guarantee this, and the same for > every program logic that I can imagine. So if the compiler may fold this to > "false", then as far as I can see, pointer comparison becomes entirely > unpredictable. The only consistent model I can think of is "icmp on pointers may > spuriously return 'true' at any time", which I doubt anyone wants. ;)In my understanding of https://timsong-cpp.github.io/cppwp/n3337/expr.rel#2.2 or http://eel.is/c++draft/expr.rel#4.3 the result of this is unspecified. While this does not necessarily extend to LLVM-IR, LLVM-IR usually assumes C/C++ semantics unless defined otherwise. Optimizations such as https://reviews.llvm.org/D53362 and https://reviews.llvm.org/D65408 assume the equivalence of alloca and malloc+free. I assume that such optimizations are the reason for this unspecifiedness, i.e. I think someone might want this. Johannes's proposal A1 however, seems to forbid StackColoring to exploit lifetime markers, which it currently does and I am not sure we can afford to do that. Michael
Hi Michael, On 12.01.21 23:11, Michael Kruse wrote:> Am Di., 12. Jan. 2021 um 12:33 Uhr schrieb Ralf Jung via llvm-dev > <llvm-dev at lists.llvm.org>: >> I hope this question has not been answered yet, but I don't see how that fold >> could be legal. I asked the same question on Phabricator but it seems you prefer >> to have the discussion here. Taking your example from there and adjusting it: >> >> p = malloc(1) >> q = malloc(1) >> %c = icmp eq %p, %q >> free(q) >> free(p) >> >> I think there is a guarantee that c will always be "false". Every operational >> model of allocation that I have ever seen will guarantee this, and the same for >> every program logic that I can imagine. So if the compiler may fold this to >> "false", then as far as I can see, pointer comparison becomes entirely >> unpredictable. The only consistent model I can think of is "icmp on pointers may >> spuriously return 'true' at any time", which I doubt anyone wants. ;) > > In my understanding of > https://timsong-cpp.github.io/cppwp/n3337/expr.rel#2.2 or > http://eel.is/c++draft/expr.rel#4.3 the result of this is unspecified. > While this does not necessarily extend to LLVM-IR, LLVM-IR usually > assumes C/C++ semantics unless defined otherwise.The part of the standard you quoted is about "Relational operators", i.a. < <= > >=. The code above is using ==, so I do not think these parts of the standard apply. https://timsong-cpp.github.io/cppwp/n3337/expr.eq seems to govern == and !=, and it says> Two pointers of the same type compare equal if and only if they are both null, both point to the same function, or both represent the same address ([basic.compound]).So now the question is if "p" and "q" 'represent the same address', but given that they point to the beginning of different allocated objects, I would say they definitely do not represent the same address. Kind regards, Ralf> > Optimizations such as https://reviews.llvm.org/D53362 and > https://reviews.llvm.org/D65408 assume the equivalence of alloca and > malloc+free. I assume that such optimizations are the reason for this > unspecifiedness, i.e. I think someone might want this. Johannes's > proposal A1 however, seems to forbid StackColoring to exploit lifetime > markers, which it currently does and I am not sure we can afford to do > that. > > Michael >
On 1/12/21 4:11 PM, Michael Kruse wrote:> Am Di., 12. Jan. 2021 um 12:33 Uhr schrieb Ralf Jung via llvm-dev > <llvm-dev at lists.llvm.org>: >> I hope this question has not been answered yet, but I don't see how that fold >> could be legal. I asked the same question on Phabricator but it seems you prefer >> to have the discussion here. Taking your example from there and adjusting it: >> >> p = malloc(1) >> q = malloc(1) >> %c = icmp eq %p, %q >> free(q) >> free(p) >> >> I think there is a guarantee that c will always be "false". Every operational >> model of allocation that I have ever seen will guarantee this, and the same for >> every program logic that I can imagine. So if the compiler may fold this to >> "false", then as far as I can see, pointer comparison becomes entirely >> unpredictable. The only consistent model I can think of is "icmp on pointers may >> spuriously return 'true' at any time", which I doubt anyone wants. ;) > In my understanding of > https://timsong-cpp.github.io/cppwp/n3337/expr.rel#2.2 or > http://eel.is/c++draft/expr.rel#4.3 the result of this is unspecified. > While this does not necessarily extend to LLVM-IR, LLVM-IR usually > assumes C/C++ semantics unless defined otherwise.I also thought the above is fine.> Optimizations such as https://reviews.llvm.org/D53362 and > https://reviews.llvm.org/D65408 assume the equivalence of alloca and > malloc+free. I assume that such optimizations are the reason for this > unspecifiedness, i.e. I think someone might want this. Johannes's > proposal A1 however, seems to forbid StackColoring to exploit lifetime > markers, which it currently does and I am not sure we can afford to do > that.It's not that A1 "forbid[s] StackColoring to exploit lifetime markers", but A1 says that you cannot use lifetime markers to argue about the address. So you can still use them for reasoning but only as far as they tell you the content is undef. If you want to do coalescing, you need to verify more things, especially that the addresses are not (both) observed. If they are, which they can be with lifetime markers in place as well, you end up with inconsistent views. That said, if we want to preserve the property that you cannot access outside of lifetime ranges, you could "fix" StackColoring by simply verifying one of the two allocas is not escaping. You'd still need to fix InstCombine but the fix is the same. I'm not sure we want to declare accesses outside of lifetime ranges UB or not. I imagine in practice this makes little difference anyway, given that escaping uses are a problem on their own. ~ Johannes> Michael