Page MenuHomePhabricator

[DSE] Preserve basic block ordering using OrderedBasicBlock.
ClosedPublic

Authored by fhahn on Mar 25 2019, 11:19 AM.

Details

Summary

By extending OrderedBB to allow removing and replacing cached
instructions, we can preserve OrderedBBs in DSE easily. This eliminates
one source of quadratic compile time in DSE.

Fixes PR38829.

Diff Detail

Repository
rL LLVM

Event Timeline

fhahn created this revision.Mar 25 2019, 11:19 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 25 2019, 11:19 AM
efriedma added inline comments.Mar 25 2019, 12:55 PM
llvm/lib/Analysis/OrderedBasicBlock.cpp
92 ↗(On Diff #192167)

Can you just set "LastInstFound = BB->end()", instead of actually numbering the new first instruction?

fhahn updated this revision to Diff 192207.Mar 25 2019, 2:26 PM

Thanks Eli. In the case LastInstFound == BB->begin(), we have to renumber all
instructions after removing LastInstFound, so there is no need to manually number
the next instruction with 0.

fhahn marked an inline comment as done.Mar 25 2019, 2:27 PM
This revision is now accepted and ready to land.Mar 25 2019, 2:48 PM
This revision was automatically updated to reflect the committed changes.