This is an archive of the discontinued LLVM Phabricator instance.

[LV][NFC] Improve complexity of fixing users of recurrences
ClosedPublic

Authored by michaelmaitland on Mar 27 2023, 1:19 PM.

Details

Summary

The original loop has 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).

Diff Detail

Event Timeline

Herald added a project: Restricted Project. · View Herald TranscriptMar 27 2023, 1:19 PM
michaelmaitland requested review of this revision.Mar 27 2023, 1:19 PM
fhahn accepted this revision.Apr 6 2023, 8:40 AM

LGTM, thanks!

I put up a patch that uses the VPLiveOuts directly, but that can act as follow-up: D147472

llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
3894

nit: no need to use llvm:: (e.g. it is not used for other things in the namespace, like PHINode or User.

This revision is now accepted and ready to land.Apr 6 2023, 8:40 AM
fhahn added a reviewer: Ayal.Apr 6 2023, 8:40 AM
michaelmaitland marked an inline comment as done.Apr 6 2023, 4:13 PM

Remove llvm::

This revision was landed with ongoing or failed builds.Apr 6 2023, 4:16 PM
This revision was automatically updated to reflect the committed changes.
Ayal added inline comments.Apr 8 2023, 10:57 AM
llvm/lib/Transforms/Vectorize/LoopVectorize.cpp
4088

(Post-commit comment, independent of this patch:) Worth improving this case as well?