[LowerSwitch] Fixed faulty PHI node in switch default block

[Ka-Ka]

Summary

When lowerswitch find out that the switch default branch is not
reachable it remove the old default and replace it with the most
popular block from the cases, but it forget to update the PHI
nodes in the default block.

[Ka-Ka]

Reduced the size of the testcase.

[Ka-Ka]

Ping?

[arsenm]

Shouldn't there be a removePredecessor call somewhere that takes care of this?

[Ka-Ka]

In D47203#1120655, @arsenm wrote:

Shouldn't there be a removePredecessor call somewhere that takes care of this?

Correct. Patch updated with call to removePredecessor.

[Ka-Ka]

Fixed another case when PHI nodes are not correctly updated.
This time it is when switch is replaced with a single branch.

[arsenm]

LGTM with nit

lib/Transforms/Utils/LowerSwitch.cpp

531

i should be capitalized

lib/Transforms/Utils/LowerSwitch.cpp

namespace {
   /// Replace all SwitchInst instructions with chained branch instructions.
   class LowerSwitch : public FunctionPass {
   public:
     // Pass identification, replacement for typeid
     static char ID;
 
     LowerSwitch() : FunctionPass(ID) {
       initializeLowerSwitchPass(*PassRegistry::getPassRegistry());
-    } 
+    }
 
     bool runOnFunction(Function &F) override;
 
     struct CaseRange {
       ConstantInt* Low;
       ConstantInt* High;
       BasicBlock* BB;
 
for (++Idx; LocalNumMergedCases > 0 && Idx < E; ++Idx)
       }
     // Remove incoming values in the reverse order to prevent invalidating
     // *successive* index.
     for (unsigned III : llvm::reverse(Indices))
       PN->removeIncomingValue(III);
   }
 }
 
+/// Remove the first occurrence of the "switch statement" BB in the PHI
+/// nodes
+static void removeEntryFromPhis(BasicBlock *SuccBB, BasicBlock *OrigBB) {
+  for (BasicBlock::iterator I = SuccBB->begin(),
+                            IE = SuccBB->getFirstNonPHI()->getIterator();
+       I != IE;) {
+    PHINode *PN = cast<PHINode>(I);
+    ++I; // To avoid invalid iterator if PHI node are removed below
+    int BlockIdx = PN->getBasicBlockIndex(OrigBB);
+    assert(BlockIdx != -1 && "Switch didn't go to this successor??");
+    PN->removeIncomingValue((unsigned)BlockIdx, true);
+  }
+}
+
 /// 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 that have already been checked by
 /// a block emitted by one of the previous calls to switchConvert in the call
 /// stack.
 BasicBlock *
 LowerSwitch::switchConvert(CaseItr Begin, CaseItr End, ConstantInt *LowerBound,
                            ConstantInt *UpperBound, Value *Val,
if (Leaf.Low == Leaf.High) {
     // Make range comparison
     if (Leaf.Low->isMinValue(true /*isSigned*/)) {
       // Val >= Min && Val <= Hi --> Val <= Hi
       Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_SLE, Val, Leaf.High,
                           "SwitchLeaf");
     } else if (Leaf.Low->isZero()) {
       // Val >= 0 && Val <= Hi --> Val <=u Hi
       Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Val, Leaf.High,
-                          "SwitchLeaf");      
+                          "SwitchLeaf");
     } else {
       // Emit V-Lo <=u Hi-Lo
       Constant* NegLo = ConstantExpr::getNeg(Leaf.Low);
       Instruction* Add = BinaryOperator::CreateAdd(Val, NegLo,
                                                    Val->getName()+".off",
                                                    NewLeaf);
       Constant *UpperBound = ConstantExpr::getAdd(NegLo, Leaf.High);
       Comp = new ICmpInst(*NewLeaf, ICmpInst::ICMP_ULE, Add, UpperBound,
BasicBlock* LowerSwitch::newLeafBlock(CaseRange& Leaf, Value* Val,
   for (BasicBlock::iterator I = Succ->begin(); isa<PHINode>(I); ++I) {
     PHINode* PN = cast<PHINode>(I);
     // Remove all but one incoming entries from the cluster
     uint64_t Range = Leaf.High->getSExtValue() -
                      Leaf.Low->getSExtValue();
     for (uint64_t j = 0; j < Range; ++j) {
       PN->removeIncomingValue(OrigBlock);
     }
-    
     int BlockIdx = PN->getBasicBlockIndex(OrigBlock);
     assert(BlockIdx != -1 && "Switch didn't go to this successor??");
     PN->setIncomingBlock((unsigned)BlockIdx, NewLeaf);
   }
 
   return NewLeaf;
 }
 
for (auto I = UnreachableRanges.begin(), E = UnreachableRanges.end();
       assert(I->Low <= I->High);
       auto Next = I + 1;
       if (Next != E) {
         assert(Next->Low > I->High);
       }
     }
 #endif
 
+    // As the default block in the switch is unreachable, update the PHI nodes
+    // (remove the entry to the default block) to reflect this.
+    removeEntryFromPhis(Default, OrigBlock);
+
     // Use the most popular block as the new default, reducing the number of
     // cases.
     assert(MaxPop > 0 && PopSucc);
     Default = PopSucc;
     Cases.erase(
         llvm::remove_if(
             Cases, [PopSucc](const CaseRange &R) { return R.BB == PopSucc; }),
         Cases.end());
 
     // If there are no cases left, just branch.
     if (Cases.empty()) {
       BranchInst::Create(Default, CurBlock);
       SI->eraseFromParent();
       return;
     }
   }
 
   unsigned NrOfDefaults = (SI->getDefaultDest() == Default) ? 1 : 0;
   for (const auto &Case : SI->cases())
     if (Case.getCaseSuccessor() == Default)
       NrOfDefaults++;
 
   // Create a new, empty default block so that the new hierarchy of
   // if-then statements go to this and the PHI nodes are happy.

test/Transforms/Util/lowerswitch.ll

switch i32 undef, label %unreachable [
     i32 2, label %lbl1
     i32 5, label %for.cond
     i32 3, label %lbl2
   ]
 
 unreachable:                                      ; preds = %cleanup
   unreachable
 }
+
+; Test that the PHI node in cleanup17 is removed as the switch default block is
+; not reachable.
+define void @test4() {
+; CHECK-LABEL: @test4
+entry:
+  br label %for.cond
+
+for.cond:
+  br label %for.cond1
+
+for.cond1:
+  br i1 undef, label %for.end20, label %for.end20
+
+for.cond3:
+  br label %for.cond3
+
+for.cond5:
+  br i1 undef, label %cleanup.thread, label %if.end9
+
+if.end9:
+  br i1 undef, label %cleanup.thread, label %cleanup13
+
+cleanup.thread:
+  br label %cleanup13
+
+cleanup13:
+  switch i32 undef, label %cleanup17 [
+    i32 0, label %for.cond5
+    i32 9, label %for.cond5
+  ]
+
+cleanup17:
+; CHECK: cleanup17:
+; CHECK-NOT: phi i16 [ undef, %cleanup13 ]
+; CHECK: for.end20:
+
+  %retval.4 = phi i16 [ undef, %cleanup13 ]
+  unreachable
+
+for.end20:
+  br label %for.cond
+
+return:
+  ret void
+
+unreachable:
+  unreachable
+}