Rebase over baseline tests.

In the meantime additional users of isAssumeLikeIntrinsic() have been added, so I've switched this to call isAssumeLikeIntrinsic() from isGuaranteedToTransferExecutionToSuccessor() instead. Does this still look good?

Rebase.

Looks like this never landed...

These tests are already present higher up in the file. The transform you have in mind is unsound due to undef, see D63060.

In D64523#1583624, @vporpo wrote:

I guess it would be better if it visited all the BBs. You could traverse the VectorizableTree once and collect the BBs to be visited before you walk through them. Btw the TreeEntries now have operands, which can help you collect the BBs in the right order.

LGTM

Your current variant with the warning looks good to me.

(I defer to your judgement though. If you think having the instsimplify variant is worthwhile, I definitely don't want to block this.)

In D64285#1580922, @lebedev.ri wrote:

In D64285#1580392, @lebedev.ri wrote:

In D64285#1580359, @nikic wrote:

In D64285#1576787, @lebedev.ri wrote:

Ugly, yeah, but powerful instsimplify is nice ^^

I feel pretty strongly that this is the not the right tradeoff to make here.

Unless there's some specific evidence that we benefit from having this in instsimplify,
reducing code duplication is imho much more valuable than making sure that
one out of thousands of ad-hoc folds runs in a few more cases than it otherwise would...

Feel free to bring this up as RFC on llvm-dev.

To elaborate, i don't disagree that this is truly a death of a thousand cuts,
*all* these folds are ad-hoc. Some will do wonders for some code patterns,
some will be useless drag for most of the code.

While theoretically we could teach the peep-hole pass all about
every possible pattern, it is infeasible in reality.
(at least until instcombine-SMT is here, will that be a glorious day!).

So what is feasible is teaching it about patterns that *were* observed
in real code. This is what i'm trying to do with my patches,
and i'd guess this may be the case with this patch, @xbolva00?

As to the question in the context of this patch, whether to only have the InstCombine part,
or duplicate it in InstSimplify thus not prohibiting other passes from being smarter,
is this a question of code duplication, or redundant matching?
The former can be workarounded with some refactoring to have a single function,
former is still the same death of a thousand cuts and can't be reasonably addressed
within existing framework.

In D64285#1576787, @lebedev.ri wrote:

Ugly, yeah, but powerful instsimplify is nice ^^

In D64304#1579785, @MaskRay wrote:

Can you share a reproduce of the Rust code?

LGTM, this looks like a reasonable workaround to me.

Philip's patch in D64509 sounds related (haven't looked closely at either yet).

In D62106#1572612, @MaskRay wrote:

In D62106#1572600, @nikic wrote:

ld.bfd doesn't allow R_X86_64_GOTPCREL. You can work around the issue with:

% clang -fno-plt -fpic a.cc -Wa,-mrelax-relocations=yes -fuse-ld=bfd

Thanks, I've verified that setting RelaxELFRelocations in TargetOptions indeed works around the issue. I'm a bit concerned about what other compatibility issues this will cause though. If I understood correctly, relax relocations is a relatively recent feature and not compatible with older linkers, so may not be a suitable compiler default.

I think R_X86_64_GOTPCRELX should be usable in ld.bfd and gold since 2016. In gold, -fno-plt R_X86_64_GOTPCREL was supported in Aug 2016 (https://sourceware.org/bugzilla/show_bug.cgi?id=20216).

ld.bfd doesn't allow R_X86_64_GOTPCREL. You can work around the issue with:

% clang -fno-plt -fpic a.cc -Wa,-mrelax-relocations=yes -fuse-ld=bfd

@MaskRay Thanks for checking! Can you tell me which binutils version you are using? It looks like using plain ld works for you, but I'm seeing this error with binutils 2.30 ld (gold 1.15 works though).

I'm seeing linker failures that I suspect are related to this change:

Fall back to default legalization on add/sub mismatch of the carry generating and consuming operation.

In D63686#1563412, @nikic wrote:

Ideally we would not use post-inc form in the middle end and let LSR move to post-inc if profitable. Apart from the issues we're seeing here, this post-inc form is also non-canonical -- clearly (a + C1) == C2 should canonically be a == C2-C1, but we have hacks in InstCombine to preserve this for multi-use cases. There is some relevant discussion on D58633 and in particular some samples where using pre-inc form currently causes regressions. The first step would probably be to figure out what is going on there.

LGTM

In D63686#1562925, @reames wrote:

I'm hesitant about this. Not because your patch is wrong, but because we've ended up with a ton of complexity involving the post-increment case. I'd really like to take a step back and see if we can factor apart some code here.

Assume for the moment that we have a transform which knows how to generate the pre-increment form, can we do post increment conversion as a post processing step?

If we were willing to strip, I think we could just strip flags and add one to both sides of the comparison *in whatever bitwidth the pre-inc form chose*. Do you agree?

If so, then I think we can move the post-inc legality/stripping entirely into a separate transform which runs *after* we've formed the arguments for the new comparison. (Which is slightly different than the current patch as we'd do the pre-to-post *after* the extend/trunc decision.)

I'm also really questioning the value of doing pre-to-post conversion in the middle end at all. I'm getting increasing tempted to move that to just before codegen, and just strip all the flags without concern. :)

Rebase

ping

Applied trivial parts of this in rL364129 and rL364130. Abandoning the rest as I don't do clang bootstraps.

In D63618#1554009, @sanjoy wrote:

In D63618#1553926, @reames wrote:

In D63618#1553053, @sanjoy wrote:

it seems like there are a lot of cases where SCEV's exit count reasoning is stronger than it's isKnownPredicate reasoning.

This is somewhat surprising. For instance in @test_06 I would have expected SCEV to compute the range of %narrow.iv to be [INT32_MAX, INT32_MAX+1) (using the fact that the backedge taken count is 0), and thus figure resolve the icmp slt to false by just looking at the ranges. Any idea why that's not happening?

I haven't looked into that one specifically,

SCEV seems to compute the correct range for that specific case:

%narrow.iv = trunc i64 %iv to i32
-->  {2147483647,+,1}<%loop> U: [2147483647,-2147483648) S: [2147483647,-2147483648)          Exits: 2147483647               LoopDispositions: { %loop: Computable }

so the comparison should be folded based on constant range analysis alone. Do you mind spot checking if indvars is even _trying_ to fold the condition correctly?

LG and already landed in rL363810.

Sorry, I'm still not convinced. Alive evaluates a single atomic with_overflow operation by computing the operation result and the overflow flag independently, which is usually okay but in my eyes not right when it comes to undef modeling, because it artificially increases the number of undef users over what exists in IR. (For reference, some of the discussion is in https://github.com/AliveToolkit/alive2/issues/71.)

In D63065#1545065, @nikic wrote:

Isn't this checking exactly the transform proposed here?

In D63065#1545052, @lebedev.ri wrote:

In D63065#1545036, @nikic wrote:

@lebedev.ri Not familiar with what exactly alive proves, but assuming you're using two separate proofs for a reason: It is possible to make the result zero, yes. But only if the overflow flag is chosen as true (rather than false) at the same time. Both result & overflow need to be checked together for the result to be meaningful.

Good observarvation. Close, but nope:

$ ./src/alive2/build-Clang-release/alive -root-only /tmp/test.opt 
OMP: Info #270: omp_set_nested routine deprecated, please use omp_set_max_active_levels instead.
Processing /tmp/test.opt..

----------------------------------------
Name: uadd_overflow
  %X = uadd_overflow i8 %a, undef
  %Op = extractvalue {i8, i1} %X, 0
  %Ov = extractvalue {i8, i1} %X, 1
  %OpIsZero = icmp eq %Op, 0
  %NoOverflow = icmp eq %Ov, 0
  %Zero = and i1 %OpIsZero, %NoOverflow
  ret i1 %Zero
=>
  ret i1 1

Done: 1
Optimization is correct!

@lebedev.ri Not familiar with what exactly alive proves, but assuming you're using two separate proofs for a reason: It is possible to make the result zero, yes. But only if the overflow flag is chosen as true (rather than false) at the same time. Both result & overflow need to be checked together for the result to be meaningful.

@lebedev.ri It's not possible to fold to { i8 undef, i1 false }. As a counter-example uaddo(1, undef) can never have the value { 0, false }. Reaching the zero value would have required overflow, which is precluded by the overflow result. Similar cases exist for the other intrinsics as well.

LGTM

ping

LGTM, thanks for the extra tests.