[IR] PR27065: Part1. Fix BasicBlock::removePredecessor to not break SSA form.

[dendibakh]

Summary

In certain cases BasicBlock::removePredecessor generates self-referencing instructions.

This patch fixes one of such cases.

[lebedev.ri]

(as per disscussion in https://reviews.llvm.org/D69865)

[lebedev.ri]

This review seems to be stuck/dead, consider abandoning if no longer relevant.

llvm/lib/IR/BasicBlock.cpp

void BasicBlock::removePredecessor(BasicBlock *Pred,
   //    br Loop                 ;; %x2 does not dominate all uses
   //
   // This is because the PHI node input is actually taken from the predecessor
   // basic block.  The only case this can happen is with a self loop, so we
   // check for this case explicitly now.
   //
   unsigned max_idx = APN->getNumIncomingValues();
   assert(max_idx != 0 && "PHI Node in block with 0 predecessors!?!?!");
+
+  bool AllowPhiElim = true;
   if (max_idx == 2) {
     BasicBlock *Other = APN->getIncomingBlock(APN->getIncomingBlock(0) == Pred);
-
-    // Disable PHI elimination!
-    if (this == Other) max_idx = 3;
+    if (this == Other)
+      AllowPhiElim = false;
   }
 
-  // <= Two predecessors BEFORE I remove one?
+  // Two predecessors BEFORE I remove one?
   if (max_idx <= 2 && !KeepOneInputPHIs) {
     // Yup, loop through and nuke the PHI nodes
-    while (PHINode *PN = dyn_cast<PHINode>(&front())) {
+    PHINode *PN;
+    for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
+      ++II;
       // Remove the predecessor first.
       PN->removeIncomingValue(Pred, !KeepOneInputPHIs);
 
-      // If the PHI _HAD_ two uses, replace PHI node with its now *single* value
-      if (max_idx == 2) {
+      // If the PHI _HAD_ two inputs, replace PHI node with its now *single* value
+      if (AllowPhiElim && max_idx == 2) {
         if (PN->getIncomingValue(0) != PN)
           PN->replaceAllUsesWith(PN->getIncomingValue(0));
         else
           // We are left with an infinite loop with no entries: kill the PHI.
           PN->replaceAllUsesWith(UndefValue::get(PN->getType()));
-        getInstList().pop_front();    // Remove the PHI node
+        PN->eraseFromParent();
       }
 
       // If the PHI node already only had one entry, it got deleted by
       // removeIncomingValue.
     }
   } else {
     // Okay, now we know that we need to remove predecessor #pred_idx from all
     // PHI nodes.  Iterate over each PHI node fixing them up

llvm/unittests/IR/BasicBlockTest.cpp

TEST(BasicBlockTest, RemovePredecessorPhiTwoInputsLoop) {
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
   Function *F = M->getFunction("f");
 
   Function::iterator FI = F->begin();
   BasicBlock *EntryBB = &*FI++;
   BasicBlock *BodyBB = &*FI++;
 
   {
-    checkFunctionIsValid(*F);
     EXPECT_EQ(BodyBB->size(), 3u);
     PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
     ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
     EXPECT_EQ(PN->getNumIncomingValues(), 2u);
   }
 
   BodyBB->removePredecessor(EntryBB);
 
   {
-    checkFunctionIsNotValid(*F);
-    // Input value was propagated into the use of %ptr.1.
-    // It broke SSA form!
-    EXPECT_EQ(BodyBB->size(), 2u);
-    GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(BodyBB->begin());
-    ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
-    EXPECT_EQ(GEP, GEP->getPointerOperand());
+    // Input value was NOT propagated into the use of %ptr.1.
+    // Otherwise it will break SSA form.
+    // In this case it's useless to verify the function, since
+    // verifier doesn't analyze dead blocks.
+    EXPECT_EQ(BodyBB->size(), 3u);
+    PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
+    ASSERT_NE(PN, nullptr) << "Expecting PHINode as a first instruction";
+    EXPECT_EQ(PN->getNumIncomingValues(), 1u);
+    EXPECT_EQ(PN->getIncomingBlock(0), BodyBB);
   }
 }
 
 TEST(BasicBlockTest, RemovePredecessorMultipleLoopPhis) {
   StringRef ModuleString = R"(
           define i32 @f(i1 %cmp, i8 *%call) {
           entry:
             br i1 %cmp, label %body, label %ret.bb
TEST(BasicBlockTest, RemovePredecessorMultipleLoopPhis) {
   std::unique_ptr<Module> M = makeLLVMModule(Context, ModuleString);
   Function *F = M->getFunction("f");
 
   Function::iterator FI = F->begin();
   BasicBlock *EntryBB = &*FI++;
   BasicBlock *BodyBB = &*FI++;
 
   {
-    checkFunctionIsValid(*F);
     EXPECT_EQ(BodyBB->size(), 5u);
     PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
     ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
     EXPECT_EQ(PN->getNumIncomingValues(), 2u);
   }
 
   BodyBB->removePredecessor(EntryBB);
 
   {
-    checkFunctionIsNotValid(*F);
-    // Input values were propagated into the use of %ptr.1.
-    // It broke SSA form!
-    EXPECT_EQ(BodyBB->size(), 3u);
-    GetElementPtrInst *GEP1 = dyn_cast<GetElementPtrInst>(BodyBB->begin());
-    ASSERT_NE(GEP1, nullptr) << "Expecting GEP as a first instruction";
-    EXPECT_EQ(GEP1, GEP1->getPointerOperand());
-    GetElementPtrInst *GEP2 = dyn_cast<GetElementPtrInst>(BodyBB->begin()++);
-    ASSERT_NE(GEP2, nullptr) << "Expecting GEP as a second instruction";
-    EXPECT_EQ(GEP2, GEP2->getPointerOperand());
+    // Input values were NOT propagated into the use of %ptr.1 and %ptr.2.
+    // Otherwise it will break SSA form.
+    // In this case it's useless to verify the function, since
+    // verifier doesn't analyze dead blocks.
+    EXPECT_EQ(BodyBB->size(), 5u);
+    PHINode *PN = dyn_cast<PHINode>(BodyBB->begin());
+    ASSERT_NE(PN, nullptr) << "Expecting PHINode as a first instruction";
+    EXPECT_EQ(PN->getNumIncomingValues(), 1u);
+    EXPECT_EQ(PN->getIncomingBlock(0), BodyBB);
+    PN = dyn_cast<PHINode>(BodyBB->begin()++);
+    ASSERT_NE(PN, nullptr) << "Expecting PHINode as a second instruction";
+    EXPECT_EQ(PN->getNumIncomingValues(), 1u);
+    EXPECT_EQ(PN->getIncomingBlock(0), BodyBB);
   }
 }
 
 TEST(BasicBlockTest, RemovePredecessorPhiTwoInputsIfElse) {
   StringRef ModuleString = R"(
           define i32 @f(i1 %cmp, i8 *%call) {
           entry:
             br i1 %cmp, label %body, label %if.bb