- User Since
- Oct 3 2013, 11:31 AM (306 w, 5 d)
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
Feb 20 2018
Feb 18 2018
Given that the original motivation for these lifetime intrinsincs was for inlining, I don't see a reason to support multiple start/ends on the same pointer.
Or is there another new use case that I'm unaware of? Also, we don't have any transformation splitting (or even shrinking I think) these lifetimes.
Feb 11 2018
oh, wow, so many bugs in DAG combiner handling undef.. Nice table btw!
Jan 17 2018
Before accepting this patch, we really need to see benchmark results. I'm not going to change clang to start emitting non-UB divs if the perf is going to be horrible. We need data.
Otherwise I don't see the need for this poison version of division. Could you elaborate if your plan is to expose this somehow to the application developer?
Dec 13 2017
Dec 12 2017
Nov 30 2017
This change is incorrect. null can be a valid pointer in a non-0 address space, and alloca may return it.
If your target's address space guarantees that alloca doesn't return null, then we can probably make this target-dependent. But we cannot simply make it unconditional; that's not correct.
Nov 28 2017
Nov 23 2017
Nov 22 2017
This patch LGTM, except for the changes in tryFactorization(). It seems there's some code missing.
The concept looks interesting to me. I'll let the experts review the patch, though (I just skimmed over it).
Out of curiosity, what are the clients you envision could use this functionality?
I can imagine that we can do store forwarding with a mustalias MemUse if stored size >= load size. Also, a mustalias MemDef can kill the previous MemDef if it has no other uses (2 stores to same location).
Are there any other uses cases? Can it be used to simplify more complex optimizations? Even better, are there missing blocks that would be needed to simplify these optimizations? (tricky question; just wondering if you have some thoughts on that).
Nov 21 2017
Nov 9 2017
Nov 8 2017
Oct 28 2017
Sep 21 2017
Ok, mea culpa, I thought CreateBitOrPointerCast() would simply create a bitcast.
Then, what we have here is:
v = phi(ptr2int(p), ptr2int(q)) => v = ptr2int(phi(p, q))
Sep 20 2017
Sep 19 2017
Ok, so after another scan through the patch and a discussion with Gil, I must say the transformation is not fully correct.
Sep 18 2017
This transformation looks correct to me and goes in the right direction (remove unneeded int2ptr/ptr2int, since they block many optimizations). The patch can be made a bit more general later.
Before the patch goes in, please add a few negative tests; you only have positive ones. Thanks!
Sep 13 2017
You're right: the Boolean connector for the second transformation was flipped. All good now :)
Sep 12 2017
I was trying to prove this in Alive, but the proof doesn't go through.
Some corner cases are not correct: http://rise4fun.com/Alive/iVs
For example: 'INT_MIN / something' would be replaced with 0, but shouldn't.
Sep 9 2017
Sep 8 2017
Sep 6 2017
Aug 12 2017
LGTM, with minor comments: missing the CHECK comment above, and missing a test for the assume removal.
Aug 10 2017
Aug 9 2017
Aug 8 2017
Jul 29 2017
Jul 28 2017
Jul 27 2017
Just realized there's a complicated isGEPKnownNonNull() in ValueTracking.cpp, which is use solely by isKnownNonZero().
I don't believe such a thing is necessary, since the input pointer to a GEP inbounds has to be non-null in address space 0. If others agree I'll also remove that function in a subsequent patch.