Fix issue found by buildbot. Locs for Scalar should be requested after VectorMap.operator[] since it may invalidate those.

Dummy update to restart testing

ping @fhahn

In D102776#2772339, @MaskRay wrote:

How is it infeasible? PLT32 is moving toward the correct direction and matches most other architectures.

Branch relocation types should be different from PC-relative relocations because the former has less reliance on the semantics. PC-relative relocations can mean address taking operations and can cause issues like canonical PLT entries.

Added comment + removed useless check + replaced explicit for with llvm::any_of

Renaming

Extracted small NFC out and rebase

I think, more robust approach would be not to depend on existing instructions but create the required ones during phi translation as needed. Phi translation already does this to some extent. In D90095 (which prototypes PHI translation support in DSE) pointers are simplified by GetPointerBaseWithConstantOffset during PHI translation what effectively removes dependencies on existing GEPs and BitCasts.

In D100538#2690864, @lebedev.ri wrote:

Claiming that changes were done where none were done is a bug too?

Thanks for noting. Fixed.

In D88287#2673846, @ebrevnov wrote:

In D88287#2672928, @critson wrote:

Raising this here as well, as it seems the previous concern I raised with the commit was ignored.

Thanks for letting me know. Hadn't seen this before. I can reproduce the issue and working on the fix.

I am seeing this change go into an infinite loop attempting to example an expression, adding more and more .nary postfixes.
I have reduced the failure to the attached bugpoint.

llc -march=amdgcn -mcpu=gfx700 < bugpoint-reduced-simplified.ll

bugpoint-reduced-simplified.ll3 KBDownload

In D88287#2672928, @critson wrote:

Raising this here as well, as it seems the previous concern I raised with the commit was ignored.

Thanks for letting me know. Hadn't seen this before. I can reproduce the issue and working on the fix.

I don't really understand why we need this separate heuristic for runtime checks. Why don't we simply add cost of runtime checks (possibly with some small scaling to be safe) to total cost of vector loop and just use existing cost model to decide?

In D88287#2619803, @byronyi wrote:

This commit may cause multiple CI failures on TensorFlow/NVPTX backend. See https://github.com/tensorflow/tensorflow/commit/b1758bd553dfc2ebbfd07eec01d1e3254eda25b8#commitcomment-48080097.

I am trying to find a minimal reproducible test case here.

Update

In general this patch seems to take exactly the same direction as D90095 and is a strict subset of it. We can choose to either re-build functionality step by step or take D90095 and split it to several smaller pieces. D90095 adds the follwoing functionality:

1. Replaces main 'do-while' loop to 'for' loop in getDomMemoryDef. This is NFC and aimed at simplifying code structure and allows to minimize future changes.
2. Supports phi translation to any predecessor (not only immediate one)
3. Is able to phi translate in presence of geps and casts. In order to support this we have to track offests.

In D88287#2609126, @lebedev.ri wrote:

Fixed SCEVExpaned in b46c085d2b6d15873fb53718f0a70b3848e19e4a, please rebase/update this patch accordingly.

But, i think we may have a problem still.
Does this patch intend to reassociate only integers, or pointers too? :)

Stepped back to use SCEVExpander

I'd like to understand why you chose to go the way it is instead of taking cost of runtime checks into account in the cost model itself? To me, the cost model is the right place for that. I would expect to see something similar to what I did in https://reviews.llvm.org/D71053 for LoopVectorizationPlanner::mayDisregardRTChecksOverhead

Update

I actually think this patch should not have been reverted in the first place.
SCEV is known to be not good with undef, i don't really see why we should start blocking on that now.
So i would personally recommend to directly revert your revert.

If I'm getting it right you are OK to commit the patch in its current state. If this is the case please unblock it.

You better remove (WIP) suffix if this patch is ready for review. Otherwise people may think it still in progress...

Uhm, no? SCEV only supports integers and pointers.

I looked at the failing list one more time and indeed it was a pointer to double case.... In total, there are 54 failing tests which needs to be investigated... Roman, Are you working in this direction?
SCEV Expander should be fixed separately anyway and I don't think there is strong dependence between these pieces.

In D88287#2596538, @lebedev.ri wrote:

I don't think we should reinvent SCEV Expander.
I was looking at fixing this properly, but got sidetracked by having to first fix the isHighCostExpansion().

Fix found verification issue

commit 13a5cac2ba919b4d02a296428b58919231e08569 (HEAD -> main, origin/main)
Author: Evgeniy Brevnov <ybrevnov@azul.com>
Date: Fri Feb 26 19:23:32 2021 +0700

I think it's better to revert it for now. Looks like the topic is not that trivial and we should first agree on the fix. There is no need to hurry.

No.

Like i have already said, the fix is https://alive2.llvm.org/ce/z/RkBWxC.
Let me just fix this then.

I think the solution is to use >= instead of > when we do min/max reassociation. In other words, originally we had 'any' > MAX_INT which is known to be false. If we want semantically equal but reassociated expression we should invert the comparison logic. In other words we should check MAX_INT >= 'any' which is known to be true and MAX_INT will be selected.

Just to add to what Roman wrote, thinking of the code as max(,) is misleading. The code is doing icmp sgt INT_MAX, undef which can evaluate to true or false. But we cannot assume that undef from now on is equal to INT_MAX just because the comparison evaluated to true.

I think I understand the problem now. 'any'>max_int is known to be false (first case), while max_int >'any' is unknown (second case)....so this is not verification issue....

In D88287#2589590, @lebedev.ri wrote:

In D88287#2589378, @ebrevnov wrote:

I think this is an issue of verification itself. In the first case max(0, undef)=>any and max(any, max_int)=>max_int. In the second case max(max_int, undef)=>x03002006. I believe the behavior of the verifier is inconsistent in these two cases and max(max_int, undef) should be evaluated to max_int as well. We can do the following trivial transformations to prove that: max(max_int, undef) is trivially equal to max(max_int, max(undef, undef)) and max(undef, undef) should be evaluated to 'any' since max(0, undef) is evaluated to 'any' in the first case. Thus we get max(max_int, any) which is evaluated to 'max_int' in the first case. So max(max_int, undef) should be evaluated to 'max_int' but not 'x03002006'.

Makes sense?

Note that given

%a = undef
%b = %a

, %a and %b have undefined values, and there are no guarantees that they are equal/not equal.
Since you emitted icmp+select, you 'read' from undefined %c twice, and you are free to get different result each time.

I think this is an issue of verification itself. In the first case max(0, undef)=>any and max(any, max_int)=>max_int. In the second case max(max_int, undef)=>x03002006. I believe the behavior of the verifier is inconsistent in these two cases and max(max_int, undef) should be evaluated to max_int as well. We can do the following trivial transformations to prove that: max(max_int, undef) is trivially equal to max(max_int, max(undef, undef)) and max(undef, undef) should be evaluated to 'any' since max(0, undef) is evaluated to 'any' in the first case. Thus we get max(max_int, any) which is evaluated to 'max_int' in the first case. So max(max_int, undef) should be evaluated to 'max_int' but not 'x03002006'.

Update

Addressed comments

LGTM.

Thanks for doing the changes. Overall this version looks fine to me. Please go ahead with some final cleanups.

I appreciate your time to review and experimenting with the patch. I agree it's kind of unexpected to see less stores get removed. Would it be possible for you to share an IR where that happens (not reduced one is fine)? I'm asking for this because I don't have access to those SPECs.

I started looking into this... Hopefully, will be able to provide my feedback by tomorrow.

I'm going to take a look next week if nobody outstrip me...

ping

Yes. Please review proposed fix https://reviews.llvm.org/D93803. Evgeniy

Thanks for letting me know. Looking now...

Updated test case due to https://reviews.llvm.org/D79485 has landed.

Rebase

Rebase

Addressed comments

Added test case.

Addressed comments

I had already tried to measure performance with the test-suite previously with out success. This time again I observe big variation. I'm using dedicated performance machine which runs only my process. I've build test-suite as follows:

Initial update

Updated comments

Rebase

Rebase

Rebase

Rebase

Rebase