Page MenuHomePhabricator

[SLP] PR45269 Fix getVectorElementSize() is slow
ClosedPublic

Authored by dtemirbulatov on May 19 2020, 1:58 PM.

Details

Summary

The algorithm inside getVectorElementSize() is almost O(x^2) complexity and when, for example, we compile MultiSource/Applications/ClamAV/shared_sha256.c with 1k instructions inside sha256_transform() function that resulted in almost ~800k iterations. The following change improves the algorithm with a map to a liner complexity. Also, I added a check for the root instruction basic block belongings to avoid any instruction from a different basic block.

Diff Detail

Event Timeline

dtemirbulatov created this revision.May 19 2020, 1:58 PM
Herald added a project: Restricted Project. · View Herald TranscriptMay 19 2020, 1:58 PM
Herald added a subscriber: hiraditya. · View Herald Transcript
ABataev added inline comments.May 19 2020, 2:35 PM
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
5349–5351

This code can be moved out of the if statement. Make InstrElementSize to use Value * as a key and check if V is processed already before the declaration of Worklist and Visited vars.

5374

Why do you need this change?

dtemirbulatov marked 2 inline comments as done.May 20 2020, 7:04 AM
dtemirbulatov added inline comments.
llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
5349–5351

ok

5374

eh, yes, Instructions from a different basic block is the rear case here, I will remove this change.

dtemirbulatov updated this revision to Diff 265254.EditedMay 20 2020, 8:08 AM

Addressed comments.

llvm/lib/Transforms/Vectorize/SLPVectorizer.cpp
5380

Could we add this deleted comment to the comment above ("If we didn't encounter...")?

Restoring accidentally removed comment.

This revision is now accepted and ready to land.May 20 2020, 12:06 PM
This revision was automatically updated to reflect the committed changes.