HomePhabricator

[SimplifyCFG] Common code sinking: fix application of profitability check

Authored by lebedev.ri on Apr 29 2021, 9:20 AM.

Description

[SimplifyCFG] Common code sinking: fix application of profitability check

The profitability check is: we don't want to create more than a single PHI
per instruction sunk. We need to create the PHI unless we'll sink
all of it's would-be incoming values.

But there is a caveat there.
This profitability check doesn't converge on the first iteration!
If we first decide that we want to sink 10 instructions,
but then determine that 5'th one is unprofitable to sink,
that may result in us not sinking some instructions that
resulted in determining that some other instruction
we've determined to be profitable to sink becoming unprofitable.

So we need to iterate until we converge, as in determine
that all leftover instructions are profitable to sink.

But, the direct approach of just re-iterating seems dumb,
because in the worst case we'd find that the last instruction
is unprofitable, which would result in revisiting instructions
many many times.

Instead, i think we can get away with just two passes - forward and backward.
However then it isn't obvious what is the most performant way to update
InstructionsToSink.

Details

Committed
lebedev.riApr 29 2021, 11:11 AM
Parents
rGa6f406480a22: [lld][WebAssembly] Add `--export-if-defined`
Branches
Unknown
Tags
Unknown

Event Timeline

RKSimon added inline comments.
/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2061

@lebedev.ri We're already checking that ScanIdx == 0 at line 2036 - coverity is complaining that this is dead code.

lebedev.ri marked an inline comment as done.Sun, Jun 6, 6:10 AM
lebedev.ri added inline comments.
/llvm/lib/Transforms/Utils/SimplifyCFG.cpp
2061

Yes, looks like this specific block can be deleted, feel free to do so.
Thank you.