This is an archive of the discontinued LLVM Phabricator instance.

Fixup PHI nodes in LowerSwitch
ClosedPublic

Authored by kariddi on Jun 25 2014, 2:17 PM.

Details

Reviewers
kariddi
Summary

Because of the recent change in r211038 there is the possibility of avoiding the creation of Leaf blocks in LowerSwitch when it is detected that they are not needed.

This is ok until there are no PHI nodes involved, but if PHI nodes are involved in target blocks they need to be updated.

This is done by the newLeafBlock method, but this is not called if the optimization implemented in r211038 triggers.

This patch solves this problem.
Thanks to Qwertyuiop

Original discussion about this bug:

http://llvm.org/bugs/show_bug.cgi?id=20103

Diff Detail

Event Timeline

kariddi updated this revision to Diff 10857.Jun 25 2014, 2:17 PM
kariddi retitled this revision from to Fixup PHI nodes in LowerSwitch.
kariddi updated this object.
kariddi edited the test plan for this revision. (Show Details)
kariddi set the repository for this revision to rL LLVM.
kariddi added a project: deleted.
kariddi added a subscriber: Unknown Object (MLST).Jun 25 2014, 4:17 PM

Added llvm-commits as subscriber

kariddi set the repository for this revision to rL LLVM.

Jim, I added you as a reviewer of this, because you have made the original commit of my patch that introduced this bug :)

reames added a subscriber: reames.Jul 2 2014, 11:29 AM

I think I convinced myself this is correct code wise. The test diffs needs cleaned up.

lib/Transforms/Utils/LowerSwitch.cpp
137

You could use firstNonPHI as the end iterator here rather than is isa<PHINode> check if desired. Either is functionally correct.

test/Transforms/LowerSwitch/feature.ll
26 ↗(On Diff #10857)

Figuring out what actually change in this test is really hard. Please separate the whitespace changes into another change set.

kariddi updated this revision to Diff 11049.Jul 3 2014, 5:14 AM

Hi Philip,

thanks for your help!
I implemented your tip on the iterator and I changed the algorithm to emit the same exact BB naming and order in the final output as the previous algorithm, such that it is not needed anymore to change the feature.ll test.

If nobody has comments on this can I commit it? :)

pete added a subscriber: pete.Jul 8 2014, 5:51 AM
pete added inline comments.
lib/Transforms/Utils/LowerSwitch.cpp
137

I don't think this will work when debugging is enabled as phi's aren't always the first instructions in a BB, or even contiguous.

I think you'll need getFirstNonPHIOrDbgOrLifetime(), and then to have the loop skip anything which isn't a phi.

kariddi added inline comments.Jul 8 2014, 6:16 AM
lib/Transforms/Utils/LowerSwitch.cpp
137

Thank you pete, I didn't know this :)

I'm fixing this in a new revision.

kariddi updated this revision to Diff 11163.Jul 8 2014, 6:24 AM

Fixed loop to loop over all possibile PHI instructions using getFirstNonPHIOrDbgOrLifetime() instead of getFirstNonPHI().

pete added a comment.Jul 8 2014, 6:46 AM

LGTM with the comment here. Best to wait for an ok from Philip too before committing.

lib/Transforms/Utils/LowerSwitch.cpp
142

This can just be (!PN)

kariddi updated this revision to Diff 11164.Jul 8 2014, 7:31 AM

Thanks Pete! I'll wait for Philip and commit :)

I spotted another issue on this read through, but generally looking good. Once you've made this change, ping me directly and I'll give it a final read through before giving a LGTM.

lib/Transforms/Utils/LowerSwitch.cpp
138

I know this was discussed in another review, but I'm pretty sure this is not necessary. I have no objection to you using this construct - i.e. go ahead and submit - but it would be good to clarify on llvm-dev and revisit if need be. If this construct is actually required, I have quite a bit of out of tree code to fix. :)

145

Oh, I just noticed this. A single basic block can reach a successor with different values. (e.g. consider a switch which simply forwards the case value, before that's optimized away)

The getBasicBlockIndex will return the first such edge, not all edges. You probably want to write:
for each incoming edge: update if bb == predecessor

It would be good to add a test case for this if possible. If you believe this is not possible, add a comment and assert that checks that. (i.e. after the update, no remaining incoming edge from OrigBlock.)

test/Transforms/LowerSwitch/2014-06-23-PHIlowering.ll
3

Please add a check-label or otherwise give context here. Where are these phis expected? What should be around them?

Also, could you place them in the body of the test function? That way, we can add more tests to this file. You'll need to add a CHECK: test

Thank you very much Philip for your very useful comments as always :)

Answers inline.

lib/Transforms/Utils/LowerSwitch.cpp
138

Does anybody have a reference to this, so that we can be sure that getFirstNonPhi() can be used 100% safe? I also like more that solution (of course) if it is correct :)

145

What do you mean exactly with this? You mean something like this?

define i32 @foo(i32 %a) nounwind uwtable readnone ssp {

switch i32 %a, label %2 [
  i32 1, label %3
  i32 2, label %1
  i32 3, label %3
]

; <label>:1 ; preds = %0

br label %3

; <label>:2 ; preds = %0

br label %3

; <label>:3 ; preds = %0, %3, %2, %1

%.0 = phi i32 [ 2, %2 ], [ 9, %0 ], [ 15, %1 ], [ 10, %0 ]
ret i32 %.0

}

If this is the case the verifier on code like this gives this error:

PHI node has multiple entries for the same basic block with different incoming values!

%.0 = phi i32 [ 2, %2 ], [ 9, %0 ], [ 15, %1 ], [ 10, %0 ]

label %0
i32 10
i32 9

You specified for different values in your comment, this seems to not be possible. With THE SAME value though I think it is (the verifier doesn't complain if i change the PHI to "%.0 = phi i32 [ 2, %2 ], [ 9, %0 ], [ 15, %1 ], [ 10, %0 ]").
I don't know if it can actually happen at the LowerSwitch phase, which is very low in the stack and after basically all IR optimizations, but considering that it is a possibility might be worth implementing it the way you specified (with the loop over all the incoming edges).

test/Transforms/LowerSwitch/2014-06-23-PHIlowering.ll
3

Will do in the next revision!

kariddi updated this revision to Diff 11204.Jul 9 2014, 9:45 AM

Updated to implement Philip suggestion of looping over all the edges
Added more context to checks in the PHILowering test + moved the checks in function context instead of global
Reverted the to the getFirstNonPHI() version waiting for more input on the matter

pete added a comment.Jul 9 2014, 10:55 AM
In D4298#25, @kariddi wrote:

Reverted the to the getFirstNonPHI() version waiting for more input on the matter

Yeah, from what David said I was wrong about this so good to proceed with the original PHI looping code.

I did take a look in Verifier::visitBasicBlock(BasicBlock &BB) and we don't actually check that PHIs are the first instructions in a BB, or contiguous, but that should be easy to add as David points out its what LangRef says already.

In D4298#27, @pete wrote:
In D4298#25, @kariddi wrote:

Reverted the to the getFirstNonPHI() version waiting for more input on the matter

Yeah, from what David said I was wrong about this so good to proceed with the original PHI looping code.

I did take a look in Verifier::visitBasicBlock(BasicBlock &BB) and we don't actually check that PHIs are the first instructions in a BB, or contiguous, but that should be easy to add as David points out its what LangRef says already.

Thanks pete for checking that! I'll keep the getFirstNonPHI() then that should be faster.

reames added a comment.Jul 9 2014, 3:29 PM

p.s. We do enforce that PHIs are at the beginning of the basic block. This is enforced by visitPHINode in the verifier. The code in question is:
1511 Ensure that the PHI nodes are all grouped together at the top of the block.
1512
This can be tested by checking whether the instruction before this is
1513 either nonexistent (because this is begin()) or is a PHI node. If not,
1514
then there is some other instruction before a PHI.
1515 Assert2(&PN == &PN.getParent()->front()||
1516 isa<PHINode>(--BasicBlock::iterator(&PN)),
1517 "PHI nodes not grouped at top of basic block!",
1518 &PN, PN.getParent());

lib/Transforms/Utils/LowerSwitch.cpp
145

Your analysis is correct. It looked like I misstated the case slightly. Having the loop is still necessary for multiple incoming edges with the same value from the same basic block.

reames added a comment.Jul 9 2014, 3:32 PM

LGTM.

Thanks for working through all the review comments.

Thanks Pete and Philip!

I'll wait one day and if I see no other comments I'll commit :)

kariddi accepted this revision.Jul 11 2014, 6:50 AM
kariddi removed a reviewer: grosbach.
kariddi added a reviewer: kariddi.

Committed with r212802 and r212803

This revision is now accepted and ready to land.Jul 11 2014, 6:51 AM
kariddi closed this revision.Jul 11 2014, 7:42 AM