Page MenuHomePhabricator

[SLP] PR45269 Fix getVectorElementSize() is slow

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



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

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.


Why do you need this change?

dtemirbulatov marked 2 inline comments as done.May 20 2020, 7:04 AM
dtemirbulatov added inline comments.



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.


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.