This is an archive of the discontinued LLVM Phabricator instance.

[LV][NFC] Improve complexity of fixing users of reductions

Authored by michaelmaitland on Apr 10 2023, 7:53 AM.



The original loop is O(MxN) since is_contained iterates over
all incoming values. This change makes it so only the phis
which use the value as an incoming value are iterated over so
it is now O(M).

This patch is analogous to D146999.

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptApr 10 2023, 7:53 AM
michaelmaitland requested review of this revision.Apr 10 2023, 7:53 AM

@fhahn Was there a reason why we did not use VPLiveOut in D147471? An alternative to this patch would be to take the same approach as D147471.

ABataev added inline comments.Apr 10 2023, 8:02 AM

auto *Phi


if (auto *UPhi = dyn_cast<PHINode>(U); UPhi && UPhi->getParent() == LoopExitBlock)

michaelmaitland marked 2 inline comments as done.

Use auto and dyn_cast

Use BCBlockPhi instead of PhiR

fhahn added a comment.May 1 2023, 5:31 AM

There are quite a few tests filing in the perecommit CI. Could you rebase & double check if the current version works as expected?

fhahn requested changes to this revision.May 30 2023, 10:11 AM

Marking as changed requested as per previous comment.

This revision now requires changes to proceed.May 30 2023, 10:11 AM
michaelmaitland abandoned this revision.Jul 5 2023, 11:34 AM

I am going to abandon this revision. This case is not the same as in fixFixedOrderReccurence since we do not have the LiveOut->phis() function here to check whether the LoopExistInst is contained in incoming values in an O(1) fashion.