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))

In D37832#875262, @davidxl wrote:

As I have mentioned, this patch itself does *not* fold any ptrtoint/inttoptr. It simply moves the intptr across the phi node. The folding you see with the test cases is done by existing optimizations, so I am not sure what the objection is about.

Ok, so after another scan through the patch and a discussion with Gil, I must say the transformation is not fully correct.

In D37832#873621, @nlopes wrote:

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!

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!

LGTM, thanks.
You're right: the Boolean connector for the second transformation was flipped. All good now :)

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.

LGTM, with minor comments: missing the CHECK comment above, and missing a test for the assume removal.

In D35887#824426, @efriedma wrote:

isKnownNonZero was added in r124183; isKnownNonNull was originally part of BasicAA, then moved in r151446.

In D35887#823029, @efriedma wrote:

See https://reviews.llvm.org/D28026

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.

LGTM.
Seems good enough to me as a temporary hack.

This one for example (stole from Dave; I don't have my list here handy):
rewrite (1 << Y) * X into X << Y:

In D20116#710923, @mehdi_amini wrote:

In D20116#710866, @nlopes wrote:

Then we have an orthogonal concern which is what's the precondition that is sufficient to justify an optimization. For example, whether a function call can be executed speculatively is one of such preconditions. It can be derived by looking at the function attributes. For example, for speculative execution we probably need to know that the function doesn't write to memory and that it terminates.

It is not enough (for example division by zero).

Let me maybe zoom out and give a different perspective:
Right now call site and function attributes are an AND of predicates that are always guaranteed to hold for that specific call site or for all call sites, respectively.
Predicates include things like doesn't write to memory, only writes to memory that is not observable, etc. Using attributes we can state that several of these predicates hold.
In the ideal world, predicates wouldn't overlap, although since we can only state ANDs of predicates and not ORs, some overlap may be need in practice.

LGTM

In D29774#674564, @spatel wrote:

In D29774#674493, @nlopes wrote:

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Thanks! I should read some docs now. :)
It looks like I should start with the papers and presentations from previous LLVM dev confs...is there also a reference doc for the online tool?

LGTM.
The easy way to check for overflow in Alive: http://rise4fun.com/Alive/MH

Let me give just 2 more Z3-related suggestions:

• instead of re-creating the solver, it might be faster to do Z3_solver_reset
• "once in a while" it might be helpful to delete everything (all solvers, asts, context) and call Z3_reset_memory. Z3's small object pool is not very good and keeps growing /ad infinitum/, so cleaning it up once a while is a good thing (improves cache usage and reduces memory consumption).

• rebase
• add UB semantics to indirectbr and switch

Regarding incremental solving with Z3 (or with most SMT solvers in general), let me just lower the expectations a bit:
In Z3, when you do push(), there are a few things that change immediately: 1) it uses a different SAT solver (one that supports incremental reasoning), and 2) some preprocessing steps are disabled completely.
The advantage of incremental solving is that it shares the state of the SAT solver between queries. On the other hand, Z3 disables a bunch of nice preprocessors, and also it switches to eager bit-blasting. So whether going incremental pays off, it depends.. I've seen cases where it's faster to create a new solver for each query and cases where incremental is a good thing.
It's on our plans to "fix" Z3 to do better preprocessing in incremental mode, but there's no ETA at the moment to start this work..

Alive is still not great for thins kind of patch; I guess it needs some macro support.
But you can use a little more general preconditions like this: http://rise4fun.com/Alive/Tz0

Cool work Dominic!
Just a few random comments from the peanut gallery regarding the usage of Z3:

• I would definitely split the Z3Expr into expr/solver/model classes. Several advantages: plugging in new solvers becomes easier and reference counting can be handled more safely and automatically. Right now your solver+model related code handled ref-counting "by hand", which can easily lead to bugs.
• I would add an rvalue constructor to the expr class to avoid ref-counting when unneeded.
• Function z3Expr::fromData() seems to be able to create arbitrarily-sized bit-vectors. I would limit to e.g. 512 bits or something like that. Z3 is super slow with huge bit-vectors. If you feel fancy (for a following version of this feature), you could encode this information lazily (based on the model).
• Z3Expr::fromInt() -- why take a string as input and not a uin64_t?
• Why call simplify before asserting a constraint? That's usually a pretty slow thing to do (in my experience).
• You should replace Z3_mk_solver() with something fancier. If you don't feel fancy, just use Z3_mk_simple_solver() (simple is short for simplifying btw). If you know the theory of the constraints (e.g., without floats, it would be QF_BV), you should use Z3_mk_solver_for_theory() (or whatever the name was). If you feel really fancy, you could roll your own tactic (in my tools I often have a tactic class to build my own tactics; Z3 even allows you to case split on the theory after simplifications)
• Instead of asserting multiple constraints to the solver, I would and() them and assert just once (plays nicer with some preprocessors of Z3)
• Timeout: SMT solvers sometimes go crazy and take forever. I would advise to add a timeout to the solver to avoid getting caught on a trap. This timeout can be different for the two use cases: check if a path is feasible (lower timeout), or check if you actually have a bug (higher timeout)
• Also, I didn't see anything regarding memory (I might have missed yet). Are you using the array theory? If so, I would probably advise benchmarking it carefully since Z3's support for arrays is not great (even though it has improved a bit in the last year or so).

Could you please explain the motivation for this transformation?
Doesn't seem very profitable to me unless strlen(s) has already been computed before. Otherwise we end up visiting more memory positions than with the original code.

In D16986#363895, @dberlin wrote:

"I second my case that we should change TBAA instead, such that it handles
volatile stuff more conservatively."

Volatileness and aliasing are different properties.
It's completely reasonable for TBAA (and other alias analysis) to say two
pointers may or may not access different memory.
It may use any way it feels like to achieve that goal.

The volatileness of a given access is something the optimizer needs to take
into account, not TBAA.

(and yes, you can get completely inconsistent results between different
alias analysis providers, where some will say mustalias and some will say
noalias for the same thing).

TL;DR You should fix LICM or AST, depending on your viewpoint.
You also have to take into account that TBAA does not obey transitiveness
or other various nice properties,not to mention different AA levels giving
inconsistent results.

Only one result is "most correct" at the language semantic level, but both
results are correct at the IR level (ie both noalias and mustalias). It
can use or not use whatever metadata it likes.

(apropos of nothing, the lack of transitivity/etc in TBAA is one of the
reasons effective partitioning schemes for aliasing information don't
usually work out :P. Since AST is basically a partitioning scheme, you are
feeling the pain of the edge cases of TBAA)

In D16986#359209, @reames wrote:

In D16986#359180, @nlopes wrote:

But then store forwarding happens and LICM realizes (or doesn't) that two of the alias sets that were said to be disjoint by TBAA in fact alias.

Can you clarify this point? AFAIK, LICM does not do store forwarding. How did store forwarding come into the picture at all?

In D16986#358822, @reames wrote:

In D16986#358193, @nlopes wrote:

Just a quick comment on this bug. We can see it from two angles:

1. TBAA is just doing its job since it is exploiting the fact that 2 pointers with different types don't alias (the metadata has 2 different type branches). So TBAA claims the pointers don't alias, while they do in practice (it's undefined behavior, though). -- in this case LICM needs patching to account for this aggressiveness.
2. Or we can say that TBAA shouldn't mess with volatile stuff since that's dangerous. In that case LICM is fine and TBAA needs patching.
   
   I'm personally more favorable of 2), since I don't think it's worth to mess with volatile stuff, since it can be dangerous for applications and probably there isn't much performance to gain there.

I disagree with your framing. Unless I misunderstood the issue, this is a clear bug in AST regardless of what TBAA returns for aliasing information. If we ended up with a volatile memory access being part of a alias set, that alias set *must* be marked volatile. It's okay to have non-volatile accesses as part of the volatile set, but not the other way around. If we required the isVolatile flag to be precise for all elements in the set, we'd essentially be requiring alias analysis to *always* get a precise no-alias result when it's possible to do so. That's not an invariant we can uphold.

Just a quick comment on this bug. We can see it from two angles:

1. TBAA is just doing its job since it is exploiting the fact that 2 pointers with different types don't alias (the metadata has 2 different type branches). So TBAA claims the pointers don't alias, while they do in practice (it's undefined behavior, though). -- in this case LICM needs patching to account for this aggressiveness.

LGTM.
I agree with you re InferFunctionAttrs. I don't see any reason why we have InferFunctionAttrs recognize all those library functions instead of having the frontend doing it. But removing it at this point may break someone's code..

In D14933#311655, @george.burgess.iv wrote:

support arbitrary expressions (like llvm.assume).

I'm fine allowing this attribute to store a Function* or Value* that LLVM tries to constant fold at each callsite, but I can't see how llvm.assume fits into the picture at all. Can you give a concrete example of what you're trying to accomplish with the addition you proposed?

I was wondering whether we could go a bit more generic and support arbitrary expressions (like llvm.assume). This design only supports allocation functions that return a pointer to the beginning of a buffer with size p1 * p2 * ... * pn, where pi are the parameters.

In D11051#204371, @hfinkel wrote:

In D11051#204369, @atrick wrote:

I don't think GEP reassociation should be done as a canonical InstCombine for two reasons
(1) the inbounds property would need to be dropped

Can you even do this if you don't have inbounds GEPs? Nuno, do you have an opinion about this?

In D9673#170543, @samsonov wrote:

In D9673#170474, @nlopes wrote:

Wait a second, won't UBSan handle this automatically if memcpy/memmove are
declared with attribute((nonnull)) in the header? Otherwise, is there
a change to the standard that imposes these additional constraints on
memcpy/memmove?

Not really. memcpy/memmove calls are handled by CGBultin and not CGCall.
It's a different code path.
Nuno

Interesting. I think that if we decide to implement such a check, we shouldn't depend on
attributes specified in the headers, so nonnull-attribute is no longer relevant. There are another
kind of compiler builtins which worth extra checks, and which don't even require headers - e.g. behavior of __builtin_ctz(0)
is undefined. I think we should implement another check kind -fsanitize=builtin that would verify arguments of
various builtin functions.

Wait a second, won't UBSan handle this automatically if memcpy/memmove are
declared with attribute((nonnull)) in the header? Otherwise, is there
a change to the standard that imposes these additional constraints on
memcpy/memmove?

LGTM.

You should use ObjectSizeOffsetVisitor instead of ObjectSizeOffsetEvaluator. The interface is the similar, but it gives up when the object size is not constant, while the later may insert new instructions in the code. ObjectSizeOffsetVisitor is well tested (it's used by alias analysis, for example).

In D5351#17, @ankur29.garg wrote:

Thanks for clarifying that. I understand now, what that undefined behavior is for.

Another thing, in these examples, all three inputs, %x, %y, & %z are known. That is, they are constants. I think such cases wouldn't make it to the transformation. When I was testing the transformation, I tested it with these inputs, the part of the code where the transformation takes place was never reached.
The transformation is useful only when some (or all) bits of any of these inputs are unknown. Otherwise, direct calculation of the expression is done. So, there should be no change in the behavior for the above input, as, in case of this input, this transformation will never be applied.

Thanks.

In D5351#15, @ankur29.garg wrote:

Hi nlopes,
Thanks for reviewing the patch.

In the example you have stated,

%x i2 = 3

since we are talking about signed integers, that is equivalent to %x i2 = -1

Similarly, %y i2 = -1 and %z i2 = -1.

I am not sure how [%6 = add %x, %y] calculates to [%6 i2 = 2]. Shouldn't it be [%6 i2 = -2] ?

Please clarify.
Thanks.

Sorry, still not correct:

This patch is incorrect: