Page MenuHomePhabricator

Simplify function llvm::removeUnreachableBlocks() to avoid (re-)computation.
ClosedPublic

Authored by rcorcs on Sep 29 2019, 4:03 AM.

Details

Summary

Two small changes in llvm::removeUnreachableBlocks() to avoid unnecessary (re-)computation.

First, replace the use of count() with find(), which has better time complexity.

Second, because we have already computed the set of dead blocks, replace the second loop over all basic blocks to a loop only over the already computed dead blocks. This simplifies the loop and avoids recomputation.

Diff Detail

Repository
rL LLVM

Event Timeline

rcorcs created this revision.Sep 29 2019, 4:03 AM
Herald added a project: Restricted Project. · View Herald TranscriptSep 29 2019, 4:03 AM
xbolva00 added a subscriber: xbolva00.
xbolva00 added inline comments.
llvm/lib/Transforms/Utils/Local.cpp
2232 ↗(On Diff #222318)

Since Reachable is SmallPtrSet, count should be as good as find()

https://github.com/llvm-mirror/llvm/blob/master/include/llvm/ADT/SmallPtrSet.h#L381

hiraditya added inline comments.Sep 29 2019, 10:59 AM
llvm/lib/Transforms/Utils/Local.cpp
2255 ↗(On Diff #222318)

With this patch, it now seems like we are iterating on DeadBlockSet twice, is it possible to merge the two loops?

rcorcs updated this revision to Diff 222428.Sep 30 2019, 10:09 AM

I have fused two loops. Now, for any execution path, only two loops over DeadBlockSet will be performed, instead of the previous worst-case of three loops.

xbolva00 added inline comments.Sep 30 2019, 10:11 AM
llvm/lib/Transforms/Utils/Local.cpp
2232 ↗(On Diff #222318)

Please “clang format” this patch

rcorcs marked an inline comment as done.Sep 30 2019, 10:11 AM
rcorcs added inline comments.
llvm/lib/Transforms/Utils/Local.cpp
2232 ↗(On Diff #222318)

Indeed they have the same complexity. I prefer find() because it conveys a better idea of what is being done and its complexity, but I don't have a strong opinion about that. If you prefer, I can roll back to using count() instead.

xbolva00 added inline comments.Sep 30 2019, 10:30 AM
llvm/lib/Transforms/Utils/Local.cpp
2232 ↗(On Diff #222318)

I am fine with this (and I like find version more than count version).

rcorcs updated this revision to Diff 222504.Sep 30 2019, 3:25 PM

This the same patch after running clang-format specifically to the llvm::removeUnreachableBlocks() function.

fhahn accepted this revision.Oct 1 2019, 3:55 AM
fhahn added a subscriber: fhahn.

Nice catch. This should be better overall, as instead of iterating over the whole function to delete dead blocks, we just iterate over the dead blocks. Even more work is skipped in case we have a DTU.

LGTM

llvm/lib/Transforms/Utils/Local.cpp
2231 ↗(On Diff #222504)

In LLVM comments tend to be sentences, i.e. capitalize Skip and add a full stop.

2276 ↗(On Diff #222504)

I think most code in LLVM tends to omit unnecessary braces for single statement blocks.

This revision is now accepted and ready to land.Oct 1 2019, 3:55 AM
rcorcs updated this revision to Diff 222591.Oct 1 2019, 4:36 AM

Addressed @fhahn 's comments.

fhahn added inline comments.Oct 1 2019, 5:44 AM
llvm/lib/Transforms/Utils/Local.cpp
2229 ↗(On Diff #222591)

This can now be just for (BasicBlock &BB : F) { I think, as we do not modify the BB list

rcorcs updated this revision to Diff 222600.Oct 1 2019, 6:14 AM

Addressed @fhahn 's comment.
Indeed. That's much better.

xbolva00 accepted this revision.Oct 1 2019, 6:49 AM
rcorcs added a comment.EditedOct 1 2019, 9:15 AM

Thanks everyone for your comments.

I don't have commit access. Unless anyone has another comment, I appreciate if one could commit this for me.

fhahn added a comment.Oct 1 2019, 2:05 PM

I can commit it tomorrow

This revision was automatically updated to reflect the committed changes.