Fixup PHI nodes in LowerSwitch

[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

[kariddi]

Added llvm-commits as subscriber

[kariddi]

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

[kariddi]

Bump :)

[reames]

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]

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.

[kariddi]

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

[pete]

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]

lib/Transforms/Utils/LowerSwitch.cpp

137

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

I'm fixing this in a new revision.

[kariddi]

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

[pete]

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]

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

[reames]

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

[kariddi]

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 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]

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.

[kariddi]

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]

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]

LGTM.

Thanks for working through all the review comments.

[kariddi]

Thanks Pete and Philip!

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

[kariddi]

Committed with r212802 and r212803

lib/Transforms/Utils/LowerSwitch.cpp

 
     BasicBlock *switchConvert(CaseItr Begin, CaseItr End,
                               ConstantInt *LowerBound, ConstantInt *UpperBound,
-                              Value *Val, BasicBlock *OrigBlock,
-                              BasicBlock *Default);
+                              Value *Val, BasicBlock *Predecessor,
+                              BasicBlock *OrigBlock, BasicBlock *Default);
     BasicBlock *newLeafBlock(CaseRange &Leaf, Value *Val, BasicBlock *OrigBlock,
                              BasicBlock *Default);
     unsigned Clusterify(CaseVector &Cases, SwitchInst *SI);

   return O << "]";
 }
 
+static void fixPhis(BasicBlock *Succ,
+                    BasicBlock *OrigBlock,
+                    BasicBlock *NewNode) {
+  for (BasicBlock::iterator I = Succ->begin(),
+                            E = Succ->getFirstNonPHI();
+       I != E; ++I) {
+    PHINode *PN = cast<PHINode>(I);
+ 
+    for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
+      if (PN->getIncomingBlock(I) == OrigBlock)
+        PN->setIncomingBlock(I, NewNode);
+    }
+  }
+}
+
 // switchConvert - Convert the switch statement into a binary lookup of
 // the case values. The function recursively builds this tree.
 // LowerBound and UpperBound are used to keep track of the bounds for Val

 BasicBlock *LowerSwitch::switchConvert(CaseItr Begin, CaseItr End,
                                        ConstantInt *LowerBound,
                                        ConstantInt *UpperBound, Value *Val,
+                                       BasicBlock *Predecessor,
                                        BasicBlock *OrigBlock,
                                        BasicBlock *Default) {
   unsigned Size = End - Begin;

     // emitting the code that checks if the value actually falls in the range
     // because the bounds already tell us so.
     if (Begin->Low == LowerBound && Begin->High == UpperBound) {
+      fixPhis(Begin->BB, OrigBlock, Predecessor);
       return Begin->BB;
     }
     return newLeafBlock(*Begin, Val, OrigBlock, Default);

           dbgs() << "NONE\n";
         });
 
-  BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound,
-                                      NewUpperBound, Val, OrigBlock, Default);
-  BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound,
-                                      UpperBound, Val, OrigBlock, Default);
-
   // Create a new node that checks if the value is < pivot. Go to the
   // left branch if it is and right branch if not.
   Function* F = OrigBlock->getParent();
   BasicBlock* NewNode = BasicBlock::Create(Val->getContext(), "NodeBlock");
-  Function::iterator FI = OrigBlock;
-  F->getBasicBlockList().insert(++FI, NewNode);
 
   ICmpInst* Comp = new ICmpInst(ICmpInst::ICMP_SLT,
                                 Val, Pivot.Low, "Pivot");
+
+  BasicBlock *LBranch = switchConvert(LHS.begin(), LHS.end(), LowerBound,
+                                      NewUpperBound, Val, NewNode, OrigBlock,
+                                      Default);
+  BasicBlock *RBranch = switchConvert(RHS.begin(), RHS.end(), NewLowerBound,
+                                      UpperBound, Val, NewNode, OrigBlock,
+                                      Default);
+
+  Function::iterator FI = OrigBlock;
+  F->getBasicBlockList().insert(++FI, NewNode);
   NewNode->getInstList().push_back(Comp);
+
   BranchInst::Create(LBranch, RBranch, Comp, NewNode);
   return NewNode;
 }

   }
   BasicBlock *SwitchBlock =
       switchConvert(Cases.begin(), Cases.end(), LowerBound, UpperBound, Val,
-                    OrigBlock, NewDefault);
+                    OrigBlock, OrigBlock, NewDefault);
 
   // Branch to our shiny new if-then stuff...
   BranchInst::Create(SwitchBlock, OrigBlock);

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

+; RUN: opt < %s -lowerswitch -S | FileCheck %s
+
+define i32 @test(i32 %arg) #0 {
+; CHECK-LABEL: @test
+; CHECK: ; <label>:2
+; CHECK-NEXT:  %res.0 = phi i32 [ 1, %NodeBlock ], [ 2, %1 ]
+; CHECK-NEXT:  br label %3
+; CHECK: ; <label>:5
+; CHECK-NEXT:   %res.3 = phi i32 [ 0, %NewDefault ], [ %res.2, %4 ]
+; CHECK-NEXT:   %6 = add nsw i32 %res.3, 1
+; CHECK-NEXT:   ret i32 %6
+
+  switch i32 %arg, label %5 [
+    i32 1, label %1
+    i32 2, label %2
+    i32 3, label %3
+    i32 4, label %4
+  ]
+
+; <label>:1
+  br label %2
+
+; <label>:2
+  %res.0 = phi i32 [ 1, %0 ], [ 2, %1 ]
+  br label %3
+
+; <label>:3
+  %res.1 = phi i32 [ 0, %0 ], [ %res.0, %2 ]
+  %phitmp = add nsw i32 %res.1, 2
+  br label %4
+
+; <label>:4
+  %res.2 = phi i32 [ 1, %0 ], [ %phitmp, %3 ]
+  br label %5
+
+; <label>:5
+  %res.3 = phi i32 [ 0, %0 ], [ %res.2, %4 ]
+  %6 = add nsw i32 %res.3, 1
+  ret i32 %6
+}