Page MenuHomePhabricator

New pass to produce more easily-read IR.
Needs ReviewPublic

Authored by arnt on Fri, Apr 12, 8:27 AM.

Details

Summary

This doesn't change the compiled output, merely reorders the basic blocks.
Frontends tend to create basic blocks in the order they discover that they
need the blocks, which is often not a great order for reading and
understanding the IR output.

The new pass is never called by default, but can be invoked with opt:

opt -S -passes improve-reading-order somefile.bc | less

Diff Detail

Event Timeline

arnt created this revision.Fri, Apr 12, 8:27 AM
Herald added a project: Restricted Project. · View Herald TranscriptFri, Apr 12, 8:27 AM
arnt added a comment.Fri, Apr 12, 8:31 AM

This patch's reviewer selection algorithm: Those who have changed two or more files in the same directory recently. I hope you don't mind.

MaskRay added inline comments.Sat, Apr 13, 3:34 AM
llvm/lib/Passes/PassBuilder.cpp
1700

Good catch! This is irrelevant to this revision. You may commit it separately.

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp
52

BasicBlock * lastSoFar = nullptr; -> BasicBlock *LastSoFar = nullptr;
for( -> for (

https://llvm.org/docs/CodingStandards.html
docs/Proposals/VariableNames.rst (lower_case vs lowerCase is still a debate; (I prefer snake_case :) ))

llvm/test/Transforms/Util/improve-reading-order.ll
2

Missing -S

MaskRay added inline comments.Sat, Apr 13, 5:33 AM
llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp
53

For a not-necessarily-sorted set, you may use SmallPtrSet or DenseSet.

57

This can be a SetVector (since we want determinism but set::set is slow)

135

In some pessimistic cases, preferredNextBlock is of O(|input|^2) and this while loop is cubic..

Do you want to rewrite the loop to use a worklist?

if (condition) {
  complex   /////// I believe the current algorithm only reorders the 'then' part
} else {
  complex    /////// this is not touched
}
arnt updated this revision to Diff 195175.Mon, Apr 15, 6:45 AM
arnt marked 3 inline comments as done.

Reworked based on good comments from maskray; thanks.

arnt added a comment.Mon, Apr 15, 6:46 AM

I pushed an update now. Will this comment submit the unsubmitted drafts?

llvm/lib/Passes/PassBuilder.cpp
1700

Can do, but I'll do it at the same time, OK? Haven't figured out how to push from my git monorepo to the svn source of truth yet.

llvm/lib/Transforms/Utils/ImproveReadingOrder.cpp
135

The while loop exits as soon as preferredNextBlock() returns non-null, so it's quadratic, not cubic.

I'm not sure whether a rewrite for speed is worthwhile. It'll help if a function has very many dead blocks, exception handlers or targets for a single switch, but it's not clear to me whether it'll ever make such a function readable. Sucking quickly instead of slowly isn't worth much effort.

On the other hand, if a function has, say, a thousand dead blocks, then one may have a particularly strong reason to inspect that function, and printing it shouldn't take thirty minutes.

So I'm on the fence.

I rewrote. You pointed me to SetVector and SetVector wants to be used ;) The new version's weak point is a thousands-wide switch where half the branches fall through to the other half, and the fallen-through-to branches contain many basic blocks and loops and so on. I'll upload a new revision later today.

llvm/test/Transforms/Util/improve-reading-order.ll
2

Ooops, fixed. Why did the tests pass without? It seems I've been running check-llvm-unit instead of check-llvm.

arnt updated this revision to Diff 195182.Mon, Apr 15, 7:51 AM

Ran clang-format.