Page MenuHomePhabricator

[LoopInfo] Remove duplicates in ExitBlocks to reduce the compile time of hasDedicatedExits
ClosedPublic

Authored by wmi on Sep 26 2019, 3:08 PM.

Details

Summary

For the problem described in https://reviews.llvm.org/D67359, turns out the root cause is there are many duplicates in ExitBlocks so the algorithm complexity of hasDedicatedExits gets very high. If we remove the duplicates, the compile time issue is gone.

Thanks to Philip Reames for raising a good question and lead me to find the root cause.

But how to properly add a compile time test is still a question for me.

Diff Detail

Repository
rL LLVM

Event Timeline

wmi created this revision.Sep 26 2019, 3:08 PM
Herald added a project: Restricted Project. · View Herald TranscriptSep 26 2019, 3:08 PM
reames requested changes to this revision.Sep 26 2019, 4:05 PM
reames added inline comments.
include/llvm/Analysis/LoopInfoImpl.h
89 ↗(On Diff #222034)

Please see: getUniqueExitBlocks on Loop.

This revision now requires changes to proceed.Sep 26 2019, 4:05 PM
wmi updated this revision to Diff 222044.Sep 26 2019, 4:14 PM

Address Philip's comment.

reames accepted this revision.Sep 26 2019, 4:19 PM

LGTM

This revision is now accepted and ready to land.Sep 26 2019, 4:19 PM
This revision was automatically updated to reflect the committed changes.