This is an archive of the discontinued LLVM Phabricator instance.

Recommit "[LAA] Support pointer phis in loop by analyzing each incoming pointer."
ClosedPublic

Authored by fhahn on May 11 2021, 11:22 AM.

Details

Summary

SCEV does not look through non-header PHIs inside the loop. Such phis
can be analyzed by adding separate accesses for each incoming pointer
value.

This results in 2 more loops vectorized in SPEC2000/186.crafty and
avoids regressions when sinking instructions before vectorizing.

Fixes PR50296, PR50288.

Diff Detail

Event Timeline

fhahn created this revision.May 11 2021, 11:22 AM
fhahn requested review of this revision.May 11 2021, 11:22 AM
Herald added a project: Restricted Project. · View Herald TranscriptMay 11 2021, 11:22 AM

There's a bit of duplication that might be good to clean up separately :)

Thanks! I've verified that this fixes the crashes I saw.

The merge-bot reports the test to be failing. Can you have a look?

Should the PHINode (in addition to its incoming arguments) also marked as accessed?

What it the incoming values themselves are PHINodes?

bjope added a subscriber: bjope.May 28 2021, 12:50 AM

We still see these failures. Should we perhaps revert rG1ed7f8ede564c3b11da4fdca30c36ccbff422576 while sorting out remaining issues here?
(that was just an optimization afaict, so maybe better to have a compiler that doesn't crash on certain input, or is the loop-distribution considered as some kind of alpha-feature)

fhahn added a comment.May 28 2021, 2:46 AM

We still see these failures. Should we perhaps revert rG1ed7f8ede564c3b11da4fdca30c36ccbff422576 while sorting out remaining issues here?
(that was just an optimization afaict, so maybe better to have a compiler that doesn't crash on certain input, or is the loop-distribution considered as some kind of alpha-feature)

Fair point. Unfortunately I did not yet have time to get back to this as quickly as I hoped. Reverted the original commit for now (ec1f6f7e3f92d806d0f7e4d687173a150102ec5d)

fhahn updated this revision to Diff 370583.Sep 3 2021, 7:37 AM

Folded changes from D101286 (which got reverted) into this revision, remove duplication.

I'd appreciate another loop at the whole patch, which now handles phis in both ::addAccess and MemDepChecker.

fhahn retitled this revision from [LAA] Also handle pointer phis in ::addAccess. to Recommit "[LAA] Support pointer phis in loop by analyzing each incoming pointer.".Sep 3 2021, 7:40 AM
fhahn edited the summary of this revision. (Show Details)

Should the PHINode itself also be added to the Accesses list? Or is there a guarantee that it is never queried?

llvm/lib/Analysis/LoopAccessAnalysis.cpp
1275

Should this be recursive, the incoming value might be a PHI inside the InnermostLoop as well?

fhahn added a comment.Sep 7 2021, 11:36 AM

Should the PHINode itself also be added to the Accesses list? Or is there a guarantee that it is never queried?

I don't think it should be added, I think it's best to handle both the dependency check and runtime check cases in the same fashion. Otherwise it might get a bit confusing if the tracked pointers diverge. If there are any places that would still query the phi node, those would need to be fixed. Adding the phi node might hide such issues. WDYT?

llvm/lib/Analysis/LoopAccessAnalysis.cpp
1275

Yes, that would allow to catch more cases. I put up D109381

IMHO, this and D109381 only make sense together. Either we do register in-loop PHINodes in accesses or we do not. A PHI value might be used directly as well as indirectly giving us a mix of some PHINodes added to AddPointer while others are not. Always (also) registering the PHINode itself at least would not give use regressions. If we consider a PHINode in the accesses list a bug, could you add an assertion for it?

I'd LGTM this patch if either you promise to commit it together with D109381 or merge them.

fhahn updated this revision to Diff 372185.Sep 13 2021, 2:20 AM

IMHO, this and D109381 only make sense together. Either we do register in-loop PHINodes in accesses or we do not. A PHI value might be used directly as well as indirectly giving us a mix of some PHINodes added to AddPointer while others are not. Always (also) registering the PHINode itself at least would not give use regressions. If we consider a PHINode in the accesses list a bug, could you add an assertion for it?

Sounds good!

folded the changes from D109381 into this patch in the latest version. I also updated the code to keep track of visited values to detect cycles and added a test case with cyclic phi nodes with irreducible control flow in 4c84a0f24c10 (together with the other additonal test).

This revision is now accepted and ready to land.Sep 13 2021, 5:56 AM