Rebase

To prove correctness of a transformation of expressions with constants and undefs, following these steps is sufficient:
(1) Replace an undef with a set of all possible values. For example, i8 undef is {0, 1, 2, ..., 255}.
(2) Evaluate each operation by pairwisely picking elements from operands' sets.
(3) If the final result is in a subset relation, the transformation is correct.

In D85684#2208630, @jdoerfert wrote:

Why is the test not part of this?

I think this patch is straightforward. I'll accept this; could anyone have a look as well?

Does this patch need an update at llvm/test/Transforms/InstSimplify/select.ll as well? (relevant commit: https://github.com/llvm/llvm-project/commit/566a66703f020996d07191323ae8ad6f7ad827b3 )

Remove redundant check

I agree this transformation is safe modulo the pointer size check. It should be fine to fold p2i(i2p i) -> i when the size of pointer is large enough.

In D85345#2205745, @jdoerfert wrote:

In D85345#2205712, @aqjune wrote:

What about undef or poison is given to malloc? If it should raise UB, the size argument and returned pointer should be noundef.

It is unclear to me if we want to forbid undef to be passed to malloc. It makes practical sense but not from a semantic perspective.
However, even if you pass undef you should not get undef back. So the return should never be undef for sure. If it doesn, how could you ever deal with it, given that a branch on the result would be UB :D

In D85393#2205762, @jdoerfert wrote:

Let's first create the Lang Ref patch before we dive into details here. Generally, we will need verifier checks, yes. FWIW, noprogress is unrelated to willreturn and noreturn though.

Since D84940 can introduce freezes, this patch can be effective now IMO.

ping

Do we need a well-formedness check at Verifier.cpp stating that noprogress and willreturn cannot exist together?

What about undef or poison is given to malloc? If it should raise UB, the size argument and returned pointer should be noundef.

If things go well, I'll add noundef to other library functions such as utime, setenv, unsetenv, .... as well.
For malloc/calloc/realloc/free, I'll think more about them. I guess it is safe to tag noundef to free's operand, but for malloc I'm not 100% sure...

Update PR3589-freestanding-libcalls.c

ping

In D65718#2205183, @sassa.nf wrote:

the compiled program must only exhibit behaviors that were possible behaviors of the source program

That's good. Now define what the possible behaviours of the source program are. We can skip this question all the way to what causes the infinite loop to be executed before the statement following it, and not after. There needs to be some form of happens-before rule.

...
The order of execution of:

while n != 0 {n += 2;}
return 0

is harder to define, because return 0 does not depend on the computation of n. What happens-before rule would you add that should require this specific loop to be executed before this specific return of a constant, and yet not forbid other execution reorderings that the optimizer should be allowed to do?

In D85533#2203926, @spatel wrote:

Is there a reason to do this in InstCombine rather than InstSimplify? We are not creating any new instructions.

Added a missing condition which is that freeze should be used by the select instruction only.

freeze isn't needed in an output

Update msan comment

In D84250#2202791, @spatel wrote:

I don't have a preference, but others said they would like go with D84792, so let's do that.

With the last patch applied, the performance change is within a reasonable range, except 523.xalancbmk_r . However, on my machine, the result of 523.xalancbmk_r varies sometimes without clear reason.

Should we go to D84792's direction?
If it is, I think we should mention that it is a workaround for the miscompilations including PR33165, and it can still be problematic in theory but chose to do it for performance.

It may be a silly question, but can lifetime.end intrinsics be applied to global variables, too?
LangRef isn't clear about this, but it makes sense to say that lifetime.end only works for alloca/mallocs IMO.

Iterate over uses of freeze(undef) and choose the best value

In D84948#2197854, @nikic wrote:

To expand on this, if we want to handle multi-use freeze undef in the future, there's generally two ways that can work:

1. Individual folds for certain operators (as done here), but replacing the freeze itself with an advantageous value rather than just the operator.
2. Walking the uses of the freeze to find the best replacement value and replace all uses. (E.g. by counting for how many uses a certain value is favorable.)

The current patch would be the starting point for 1, my suggestion would be the starting point for 2.

I should say though that I'm also ok with your current patch.

Note that Alive2 seems to think that the replacement is valid:
https://alive2.llvm.org/ce/z/2rorhk

In D85184#2195428, @jdoerfert wrote:

In D85184#2195356, @aqjune wrote:

BuildLibCalls.cpp 's inferLibFuncAttributes seems to be the right place for this?
I'll start with adding noundef to return values of library functions.

That would be great, and yest that is the right place for most of it IIRC.

Update the comment

In D85184#2193446, @jdoerfert wrote:

Note: @aqjune, and @okura We should also seed noundef in the intrinsics and especially known library functions definitions. I mean, malloc is not returning a undef or poison value (I hope), and free is not accepting one.

Rebase

Minor fix

Update test

I merged the tests to a single file (https://github.com/llvm/llvm-project/commit/1ea84653378132091b5b6d31d4f6bf3ec7da7b56 ).
Two tests required targets that are different from x86_64-unknown-linux-gnu , so they are left unmerged.

Update the comment

In D84250#2187617, @nikic wrote:

Assuming D84792 lands, would performing the two SimplifyBinOp queries for L and R with CanUseUndef=false solve this problem as well? I would prefer that if it works.

In D84250#2187367, @aqjune wrote:

In D84250#2187305, @spatel wrote:

I tried to find other examples where this could happen, and I can't find anything else either.
So I think this just needs some minor changes.
However, Alive2 does not show the "f_dontfold" test example or my reduced candidate test as incorrect - is that a bug for Alive2?
https://alive2.llvm.org/ce/z/dbGLzN

f_dontfold simply shows that the patch prevents the folding; it is still correct to fold the expression. I'll leave TODO there.
I'll update this patch to reflect the comments.

Reflect comments

In D84250#2187305, @spatel wrote:

I tried to find other examples where this could happen, and I can't find anything else either.
So I think this just needs some minor changes.
However, Alive2 does not show the "f_dontfold" test example or my reduced candidate test as incorrect - is that a bug for Alive2?
https://alive2.llvm.org/ce/z/dbGLzN

Minor fix

Fix another failing test

Hi, sorry for delay.

Since this can be tested independent from D84940, it is landed early

Leave pre-load.ll's diff only

Remove the !InsertFreezeWhenUnfoldingSelect check

In D84940#2185603, @efriedma wrote:

I'm not sure about your plan for enabling this. You're going to get very little practical test coverage enabling this for "LTO". (Big projects are much more likely to be using ThinLTO.) And long-term, we don't to have a "please miscompile my code" argument for the JumpThreading pass.