This is an archive of the discontinued LLVM Phabricator instance.

[SimplifyCFG] Change the algorithm in SinkThenElseCodeToEnd
ClosedPublic

Authored by jmolloy on Aug 26 2016, 12:43 AM.

Details

Reviewers
spatel
hans
Summary

r279460 rewrote this function to be able to handle more than two incoming edges and took pains to ensure this didn't regress anything.

This time we change the logic for determining if an instruction should be sunk. Previously we used a single pass greedy algorithm - sink instructions until one requires more than one PHI node or we run out of instructions to sink.

This had the problem that sinking instructions that had non-identical but trivially the same operands needed extra logic so we sunk them aggressively. For example:

%a = load i32* %b          %d = load i32* %b
%c = gep i32* %a, i32 0    %e = gep i32* %d, i32 1

Sinking %c and %e would naively require two PHI merges as %a != %d. But the loads are obviously equivalent (and maybe can't be hoisted because there is no common predecessor).

This is why we implemented the fairly complex function areValuesTriviallySame(), to look through trivial differences like this. However it's just not clever enough.

Instead, throw areValuesTriviallySame away, use pointer equality to check equivalence of operands and switch to a two-stage algorithm.

In the "scan" stage, we look at every sinkable instruction in isolation from end of block to front. If it's sinkable, we keep track of all operands that required PHI merging.

In the "sink" stage, we iteratively sink the last non-terminator in the source blocks. But when calculating how many PHIs are actually required to be inserted (to work out if we should stop or not) we remove any values that have already been sunk from the set of PHI-merges required, which allows us to be more aggressive.

This turns an algorithm with potentially recursive lookahead (looking through GEPs, casts, loads and any other instruction potentially not CSE'd) to two linear scans.

Diff Detail

Repository
rL LLVM

Event Timeline

jmolloy updated this revision to Diff 69324.Aug 26 2016, 12:43 AM
jmolloy retitled this revision from to [SimplifyCFG] Change the algorithm in SinkThenElseCodeToEnd.
jmolloy updated this object.
jmolloy added reviewers: spatel, hans.
jmolloy set the repository for this revision to rL LLVM.
jmolloy added a subscriber: llvm-commits.
hans edited edge metadata.Aug 26 2016, 3:57 PM

Nice! But I had to struggle a bit to wrap my head around the code. I've left some questions hoping it's possible to make things clearer.

lib/Transforms/Utils/SimplifyCFG.cpp
1321–1322

There's no Blocks parameter anymore, so the comment needs updating.

And is it checking that all instructions in Insts can be sunk together? Maybe rename to canSinkInstructions?

1349–1352

"this" is actually referring to all instructions in Instructions right? This keeps throwing me off, maybe it can be clarified somehow.

1369

do we know that all the instructions in Insts have the same number of operands as I0?

1489

Does "the values" here refer to those n'th-last instructions or something else?

1496

Pretty tricky names here, especially ValuesNeedingPHIs and ThisValuesNeedingPHIs.

Would it help if instead of "values needing phis" these were referred to as PHI operands? And maybe store in a DenseMap from "value (instruction?) to sink" to "PHI operands"?

Anyway I wonder if this could all be made more clear somehow.

jmolloy updated this revision to Diff 69546.Aug 29 2016, 2:40 AM
jmolloy edited edge metadata.
jmolloy marked an inline comment as done.

Hi Hans,

Thanks for the comments! Yes, I had difficulty naming these the first time around. Thanks for telling me where you got confused - hopefully that's helped me make it more understandable.

Cheers,

James

hans added inline comments.Aug 29 2016, 2:32 PM
lib/Transforms/Utils/SimplifyCFG.cpp
1351

"if if"

1369

I'm still wondering how this code knows that I0 and I have the same number of operands. It looks like it assumed this before too. What am I missing?

The situation I was thinking off was calls with different number of arguments. Are we just getting lucky because of the "Don't create indirect calls" below?

If we assume the instructions have the same number of arguments, we should assert it, and otherwise we should bail. I suppose.

1489

maybe rename ValuesToSink to InstructionsToSink?

1496

calling PopulateInsts with an increasing index like this is O(n^2). Maybe it doesn't matter much in practice (since n is number of sinkable instructions, large n would be rare?)

Would it be very impractical to just do a single reverse iteration over all the blocks instead of starting over from the back each time?

jmolloy updated this revision to Diff 69707.Aug 30 2016, 9:00 AM
jmolloy removed rL LLVM as the repository for this revision.
jmolloy marked an inline comment as done.

Thanks Hans. I should have addressed all your comments now, unless I've screwed up my local git history as is frequent at 5pm... :)

hans accepted this revision.Aug 30 2016, 9:39 AM
hans edited edge metadata.

lgtm

lib/Transforms/Utils/SimplifyCFG.cpp
1484

are the extra spaces around "--" intentional? it looks odd; same for operator* below.

This revision is now accepted and ready to land.Aug 30 2016, 9:39 AM
Eugene.Zelenko closed this revision.Oct 4 2016, 3:48 PM
Eugene.Zelenko added a subscriber: Eugene.Zelenko.

Committed in rL280351.