[LLParser] Allow zero-input phi nodes

[nikic]

Summary

Zero-input phi nodes are accepted by the verifier and bitcode reader, but currently rejected by the IR parser. Allow them there as well.

Because phi nodes must have one entry for each predecessor, such phis can only occur in blocks without predecessors, aka unreachable code.

Usually, when removing the last predecessor from a block, we also remove phi nodes in it. However, this is not possible for invalidation reasons sometimes, which is why we ended up allowing zero-entry phis at some point in the past.

I've dropped the verifier unit test, because this is now covered by the regular IR test.

This fixes at least part of https://github.com/llvm/llvm-project/issues/57446.

[spatel]

LGTM - I drafted a similar patch. :)

For reference, the verifier change was 9eb2c0113dfe, and that was a follow-up to D92247 which tried to fix https://llvm.org/PR48296.

llvm/lib/AsmParser/LLParser.cpp

7011–7013

Move this error check directly after parse of Ty? That could be an independent change. It doesn't appear to have any testing currently, but I think we can trigger it with something like:

%r = phi i8* ()

llvm/lib/AsmParser/LLParser.cpp

 }
 
 /// parsePHI
 ///   ::= 'phi' Type '[' Value ',' Value ']' (',' '[' Value ',' Value ']')*
 int LLParser::parsePHI(Instruction *&Inst, PerFunctionState &PFS) {
   Type *Ty = nullptr;  LocTy TypeLoc;
   Value *Op0, *Op1;
 
-  if (parseType(Ty, TypeLoc) ||
-      parseToken(lltok::lsquare, "expected '[' in phi value list") ||
-      parseValue(Ty, Op0, PFS) ||
-      parseToken(lltok::comma, "expected ',' after insertelement value") ||
-      parseValue(Type::getLabelTy(Context), Op1, PFS) ||
-      parseToken(lltok::rsquare, "expected ']' in phi value list"))
+  if (parseType(Ty, TypeLoc))
     return true;
 
+  if (!Ty->isFirstClassType())
+    return error(TypeLoc, "phi node must have first class type");
+
+  bool First = true;
   bool AteExtraComma = false;
   SmallVector<std::pair<Value*, BasicBlock*>, 16> PHIVals;
 
   while (true) {
-    PHIVals.push_back(std::make_pair(Op0, cast<BasicBlock>(Op1)));
-
-    if (!EatIfPresent(lltok::comma))
+    if (First) {
+      if (Lex.getKind() != lltok::lsquare)
+        break;
+      First = false;
+    } else if (!EatIfPresent(lltok::comma))
       break;
 
     if (Lex.getKind() == lltok::MetadataVar) {
       AteExtraComma = true;
       break;
     }
 
     if (parseToken(lltok::lsquare, "expected '[' in phi value list") ||
         parseValue(Ty, Op0, PFS) ||
         parseToken(lltok::comma, "expected ',' after insertelement value") ||
         parseValue(Type::getLabelTy(Context), Op1, PFS) ||
         parseToken(lltok::rsquare, "expected ']' in phi value list"))
       return true;
-  }
 
-  if (!Ty->isFirstClassType())
-    return error(TypeLoc, "phi node must have first class type");
+    PHIVals.push_back(std::make_pair(Op0, cast<BasicBlock>(Op1)));
+  }
 
   PHINode *PN = PHINode::Create(Ty, PHIVals.size());
   for (unsigned i = 0, e = PHIVals.size(); i != e; ++i)
     PN->addIncoming(PHIVals[i].first, PHIVals[i].second);
   Inst = PN;
   return AteExtraComma ? InstExtraComma : InstNormal;
 }
 

llvm/test/Assembler/zero-input-phi.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -S < %s | FileCheck %s
+; RUN: llvm-as < %s | llvm-dis | FileCheck %s
+
+define void @dead_phi() {
+; CHECK-LABEL: @dead_phi(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    ret void
+; CHECK:       return:
+; CHECK-NEXT:    [[R:%.*]] = phi i32
+; CHECK-NEXT:    ret void
+;
+entry:
+  ret void
+
+return:
+  %r = phi i32
+  ret void
+}

llvm/unittests/IR/BasicBlockTest.cpp

TEST(BasicBlockTest, ComesBefore) {
   BB.invalidateOrders();
   EXPECT_FALSE(Ret->comesBefore(Add));
   EXPECT_FALSE(Ret->comesBefore(Add));
   BB.invalidateOrders();
   EXPECT_FALSE(Ret->comesBefore(Ret));
   EXPECT_FALSE(Ret->comesBefore(Ret));
 }
 
-TEST(BasicBlockTest, EmptyPhi) {
-  LLVMContext Ctx;
-
-  Module *M = new Module("MyModule", Ctx);
-  FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
-  Function *F = Function::Create(FT, Function::ExternalLinkage, "", M);
-
-  BasicBlock *BB1 = BasicBlock::Create(Ctx, "", F);
-  ReturnInst::Create(Ctx, BB1);
-
-  Type *Ty = Type::getInt32PtrTy(Ctx);
-  BasicBlock *BB2 = BasicBlock::Create(Ctx, "", F);
-  PHINode::Create(Ty, 0, "", BB2);
-  ReturnInst::Create(Ctx, BB2);
-  EXPECT_FALSE(verifyModule(*M, &errs()));
-}
-
 class InstrOrderInvalidationTest : public ::testing::Test {
 protected:
   void SetUp() override {
     M.reset(new Module("MyModule", Ctx));
     Nop = Intrinsic::getDeclaration(M.get(), Intrinsic::donothing);
     FunctionType *FT = FunctionType::get(Type::getVoidTy(Ctx), {}, false);
     Function *F = Function::Create(FT, Function::ExternalLinkage, "foo", *M);
     BB = BasicBlock::Create(Ctx, "entry", F);