- User Since
- Oct 3 2013, 11:31 AM (339 w, 5 d)
Sun, Apr 5
Yes, introducing branches on a variable that may be undef/poison is not legal. However, you can use freeze to make it safe.
I think @aqjune fixed loop unswitching already. (don't recall if that was the reverted patch). It's true there a couple more places left to fix.
Sun, Mar 29
Sat, Mar 28
Feb 29 2020
LGTM (modulo the style fix).
assume poison is UB.
Feb 23 2020
Feb 21 2020
I agree with @aqjune that stating clearly the definition of object in this context.
See this example in the C spec:
For example, the second call of f in g has undefined behavior because each of d through d is accessed through both p and q.
Feb 17 2020
Feb 14 2020
LGTM overall, just some nitpicks.
Something I would add is a link to the list of attributes (is this function-attributes?).
Feb 7 2020
Jan 24 2020
I'm not familiar with the code of this pass, but is there a cheap way of identifying that the two operations are in the same basic block?
If so, you could take the intersection of the aliasing information rather than the union. Because if both ops are guaranteed to execute then the tightest aliasing still has to hold.
(being in the same BB doesn't imply that both instructions are executed, but there's code in ValueTracking perhaps that can check that)
Jan 11 2020
Jan 9 2020
The patch & semantics look good to me, but I'm not a backend expert. I'll leave the final LGTM to someone else.
It would be awesome if we could get this in for 10.0 so that we have complete support for freeze.
Jan 3 2020
@lebedev.ri I agree with you that the semantics of these alignment builtins should only return a pointer that is of the same object as the one given as input.
Otherwise, these builtins would be even worst that ptr2int/int2ptr, since their result could alias with any other pointer in the program, not just the escaped pointers.
Jan 2 2020
Dec 10 2019
LGTM. The table you provided was very interesting to see, thanks!
Dec 4 2019
Dec 1 2019
Nov 29 2019
I think it's clear that dead arg elimination is incorrect in replacing a valid pointer with null in an attributed with non-null tag. Changing the semantics on non-respecting the tags from UB to poison doesn't help either.
The problem with dropping attributes is that a given function call site, the attributes to be considered are the union of the attributes in the function call and in the callee declaration. We can't rely drop attributes from the callee since some linking later may add them back.
Reference to the discussion: http://lists.llvm.org/pipermail/llvm-dev/2019-November/137243.html
Nov 24 2019
The first bit looks ok to me, thanks!
Interesting question :)
Nov 18 2019
Let me give my 2c: eliminating this transformation is a good thing, since it's incorrect (end-to-end miscompilation testcase in the cited bug report).
It can be re-instated if/when we switch from initializing vectors with undef with poison, but I don't know when that will happen. We'll try to push for the poison patches soonish, but it will take time.
Anyway, thanks Sanjay for handling this :)
Nov 11 2019
Nov 6 2019
Nov 5 2019
Nov 2 2019
Oct 30 2019
Oct 28 2019
Oct 25 2019
Oct 20 2019
Oct 16 2019
(there's only a typo in the comment "singned")
Oct 15 2019
The patch looks good to me. Actually I had reported this bug a while back as well: https://bugs.llvm.org/show_bug.cgi?id=42699
I agree we can't have objects larger than half of the address space.
Oct 7 2019
Clarify semantics for pointers.
Oct 5 2019
Sep 17 2019
Sep 16 2019
Made it explicit re one vs multiple calls to freeze.
Updated with an example with vectors and add more references to freeze section.
Reflect comments & clarify immediate UB when branching on poison.
Aug 31 2019
Jul 10 2019
Jul 9 2019
Jul 6 2019
Jul 5 2019
Just a shameless plug :)
We've been half secretly working on Alive2 (https://github.com/AliveToolkit/alive2), which includes a plugin for opt that can check if an optimization is correct or not. Alive2 also has a standalone tool that accepts 2 IR files instead.
This tool implements the semantics of poison for many LLVM instructions, and already has some support for memory (which is quite hard to handle).
Of course, what this patch does is not the same. This patch is more executable, while Alive2 requires Z3 to reason about the semantics (though it can also execute code very slowly).
Jun 10 2019
LGTM, thank you!
Jun 9 2019
Sounds great! Just 1 comment inline.
Mar 30 2019
Minor: you have a typo in the comment: "return return"
Mar 29 2019
I believe the contains function I wrote is correct. It says that an integer n belongs to interval I iff n >= lower(I) and n < upper(I) is there's no wrapping.
BTW, function isWrappedSet() just changed recently, so that needs tweaking in the Z3 model I sent (https://github.com/llvm-mirror/llvm/blob/master/lib/IR/ConstantRange.cpp#L347)
Mar 3 2019
This patch is not correct for this input:
lhs = FullSet
rhs = [0, 1)
Feb 6 2019
Dec 31 2018
Dec 30 2018
As a justification why it doesn't matter whether it's undef or poison, clang emits__builtin_ffs as:
ffs(x) -> x ? cttz(x) + 1 : 0
Dec 29 2018
Dec 2 2018
Dec 1 2018
Nov 8 2018
Sep 10 2018
Sure, adding nsw/nuw brings in poison. I didn't study all the MI transformations going on, so I can't comment on whether this is a big burden or not, but without such a study introducing poison is dangerous.
SDAG already has nsw/nuw IIRC, though. But I don't think there was a thorough study of the implications at the time either.
Jul 17 2018
Jul 9 2018
Jul 8 2018
BTW, I couldn't figure if this case is possible, but mentioning it just in case: it's also not legal to introduce 'sdiv undef, ..', since 'sdiv INT_MIN, -1' is UB. Same for srem. So we need to be careful when folding the shuffle on LHS as well.
Jul 6 2018
Jul 5 2018
Jul 4 2018
shl %x, undef is poison; we don't want more undefs :)
So this transformation for shifts is not correct. The way to make it correct would be to introduce a poison value and use it in the shuffle instructions instead of undef. I suggest we finally go ahead and do that.
Jul 3 2018
Jun 17 2018
Jun 12 2018
Jun 11 2018
Jun 9 2018
Jun 7 2018
Yes, although hopefully align(4) would have also been specified on the function argument. As the reference must have been bound to a valid object, from C++ semantics, we should know that it's properly aligned. Do we do that now?
I just got a scary ah-ah moment..
Take this code:
The C++ standard defines this as UB: http://eel.is/c++draft/conv.fpint#1
"A prvalue of a floating-point type can be converted to a prvalue of an integer type. The conversion truncates; that is, the fractional part is discarded.
The behavior is undefined if the truncated value cannot be represented in the destination type."
Jun 5 2018
Eli, thanks a lot for kicking off the discussion. I think this patch is a bit too big since there are a few things that are not trivial.
For example, I would rather not introduce more functions returning undef, but rather return poison instead. If there's no good motivation for undef, poison should be used by default from now on, since it's much easier to handle than undef.
This patch also introduces a lot of UB with metadata tags, which is a departure from how we handle things like nsw/nuw which make the instructions yield poison instead of UB. Why is it more important to preserve nsw when hoisting an add than preserving !nonnull when hoisting a load? I really don't know; hence I'm asking.
I think it would help to split this patch a bit.
Jun 4 2018
May 28 2018
The optimization looks good to me.
May 13 2018
Apr 5 2018
Mar 31 2018
LGTM, but I would wait for another review due to the size of the change.
Mar 26 2018
I like the direction in general. I've reviewed this patch and it LGTM (as well as the overall plan).
There are still a few corner cases we need to fix regarding the meaning of size -1, but I guess it's an orthogonal fix. Right now I don't know exactly what -1 size is: does it mean potentially access the whole object, or access the object from the current offset and potentially until the end?
Please don't remove non-functional changes from this patch. It contains dozens of indentation changes which are completely unrelated with the intended change and make the review more difficult. There are also debug printfs included that need to be removed :)
This document may be useful: http://llvm.org/docs/Contributing.html