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

[dendibakh]

Summary

BasicBlock::removePredecessor replaces phi nodes with single entry even if it will generate self-referencing instructions and break SSA form. This patch fixes this behavior.

Logic regarding the change in CloneFunction.cpp:

• We prevent replacing phi nodes in BasicBlock::removePredecessor only in the cases where it will break SSA form.
• Since it was working before, i.e. verifier did not complain, it means that the code was dead. Then, it shouldn't matter if we skip blocks that still have phi nodes.

See example in the lit test in this patch.

[jdoerfert]

I doubt this is actually fixing anything. Unreachable code is generally allowed to be in non-SSA form. As noted in https://bugs.llvm.org/show_bug.cgi?id=27065, it is load-combine that is broken to look at unreachable code.

[dendibakh]

In D69865#1736280, @jdoerfert wrote:

Unreachable code is generally allowed to be in non-SSA form.

Is it documented somewhere?
I think it adds certain limitations to the usage of some LLVM functionality. For example, if someone decide to link in detached blocks (after removePredecessor) again, (s)he will be surprised to find broken SSA code in there. It limits room for hacking certainly.

[jdoerfert]

In D69865#1736296, @dendibakh wrote:

In D69865#1736280, @jdoerfert wrote:

Unreachable code is generally allowed to be in non-SSA form.

Is it documented somewhere?

Probably is, I don't have a reference handy though.

I think it adds certain limitations to the usage of some LLVM functionality. For example, if someone decide to link in detached blocks (after removePredecessor) again, (s)he will be surprised to find broken SSA code in there. It limits room for hacking certainly.

While that is not untrue, there is a very simple solution: run trivial dead code removal first. What you are trying to do, prevent generation of degenerated unreachable IR, is an uphill battle on more fronts than you would imagine.

[spatel]

In D69865#1736308, @jdoerfert wrote:

In D69865#1736296, @dendibakh wrote:

In D69865#1736280, @jdoerfert wrote:

Unreachable code is generally allowed to be in non-SSA form.

Is it documented somewhere?

Probably is, I don't have a reference handy though.

I think it adds certain limitations to the usage of some LLVM functionality. For example, if someone decide to link in detached blocks (after removePredecessor) again, (s)he will be surprised to find broken SSA code in there. It limits room for hacking certainly.

While that is not untrue, there is a very simple solution: run trivial dead code removal first. What you are trying to do, prevent generation of degenerated unreachable IR, is an uphill battle on more fronts than you would imagine.

A same/similar question about this code in BasicBlock was raised on llvm-dev here:
http://lists.llvm.org/pipermail/llvm-dev/2015-August/089091.html

Unfortunately, I don't think the legality of the invalid SSA is documented anywhere. But as we can see, it passes the IR verifier.

As noted in D69823, I've made several patches to other passes to work-around the issue. It would be great if we didn't have to do that, but AFAIK, we're stuck.

[dendibakh]

A same/similar question about this code in BasicBlock was raised on llvm-dev here:
http://lists.llvm.org/pipermail/llvm-dev/2015-August/089091.html

Unfortunately, I don't think the legality of the invalid SSA is documented anywhere. But as we can see, it passes the IR verifier.

As noted in D69823, I've made several patches to other passes to work-around the issue. It would be great if we didn't have to do that, but AFAIK, we're stuck.

Thanks for the link Sanjay,
However, it's still not clear to me why broken unreachable code is better than valid unreachable code? Is it a hidden way to test that passes do not look into unreachable code?

[jdoerfert]

In D69865#1737198, @dendibakh wrote:

A same/similar question about this code in BasicBlock was raised on llvm-dev here:
http://lists.llvm.org/pipermail/llvm-dev/2015-August/089091.html

Unfortunately, I don't think the legality of the invalid SSA is documented anywhere. But as we can see, it passes the IR verifier.

As noted in D69823, I've made several patches to other passes to work-around the issue. It would be great if we didn't have to do that, but AFAIK, we're stuck.

Thanks for the link Sanjay,

The most common way to make sure passes do not choke on unreachable IR is to replace the loop
for (BasicBlock &BB : Fn)
with
for (BasicBlock &BB: depth_first(Fn))
which will never visit the unreachable parts.

However, it's still not clear to me why broken unreachable code is better than valid unreachable code?

Because you have to add logic all over the place to ensure this condition.

Is it a hidden way to test that passes do not look into unreachable code?

Not that I know of. You can write a test case with really broken unreachable IR and run all passes on it. That would actually be a really cool thing to do.

[efriedma]

The general problem here is, how do you define dominance for unreachable code? LLVM makes the choice that every basic block dominates an unreachable basic block. This leads to the slightly strange result that an instruction can use itself... but there isn't really any good alternative given we allow unreachable basic blocks.

In that context, trying to avoid generating instructions that use themselves isn't really productive; you can get equally confusing results in other ways.

We could consider just saying that unreachable blocks aren't valid. Last time I looked, that didn't really seem feasible because there were a bunch of transforms that could leave around unreachable code, without any easy way to check. But there's been a bunch of work to preserve the dominator tree in more places, so maybe it's easier now.

[dendibakh]

I'm not arguing that passes should not look into unreachable code.

But in this exact case, BasicBlock::removePredecessor is pretty much general API, not limited to particular pass. We are not 100% sure that the broken code will be unreachable.
Consider this:

define i32 @f(i1 %cmp, i8 *%call) {
entry:
  br i1 %cmp, label %phi.bb, label %ret.bb
phi.bb:
  %ptr.1 = phi i8* [ %call, %entry],[ %inc.ptr1, %use.bb ]
  br label %use.bb
use.bb:
  %inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
  br i1 %cmp, label %ret.bb, label %phi.bb
ret.bb:
  ret i32 0
}

After doing:

PhiBB->removePredecessor(EntryBB);

We have:

define i32 @f(i1 %cmp, i8* %call) {
entry:
  br i1 %cmp, label %phi.bb, label %ret.bb				<== edge entry->phi.bb will be removed later
phi.bb:
  br label %use.bb
use.bb:
  %inc.ptr1 = getelementptr inbounds i8, i8* %inc.ptr1, i64 1 		<== broken
  br i1 %cmp, label %ret.bb, label %phi.bb
ret.bb:
  ret i32 0
}

User can later decide to link phi.bb into some other place (outlining, for example). Can that happen? If yes, it is not unreachable code anymore.

To summarize my point: even if we know the code is dead and noone will look into it, I don't see benefits of allowing it to be broken. In this particular case, (I hope) it will require no additional changes, since passes do not look into unreachable code and do not care if it is valid or not.

[jdoerfert]

In D69865#1737382, @dendibakh wrote:

I'm not arguing that passes should not look into unreachable code.

But in this exact case, BasicBlock::removePredecessor is pretty much general API, not limited to particular pass. We are not 100% sure that the broken code will be unreachable.
Consider this:

define i32 @f(i1 %cmp, i8 *%call) {
entry:
  br i1 %cmp, label %phi.bb, label %ret.bb
phi.bb:
  %ptr.1 = phi i8* [ %call, %entry],[ %inc.ptr1, %use.bb ]
  br label %use.bb
use.bb:
  %inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
  br i1 %cmp, label %ret.bb, label %phi.bb
ret.bb:
  ret i32 0
}

After doing:

PhiBB->removePredecessor(EntryBB);

We have:

define i32 @f(i1 %cmp, i8* %call) {
entry:
  br i1 %cmp, label %phi.bb, label %ret.bb				<== edge entry->phi.bb will be removed later
phi.bb:
  br label %use.bb
use.bb:
  %inc.ptr1 = getelementptr inbounds i8, i8* %inc.ptr1, i64 1 		<== broken
  br i1 %cmp, label %ret.bb, label %phi.bb
ret.bb:
  ret i32 0
}

While in the middle of a code rewrite, code can be broken. I don't see a way around that.

User can later decide to link phi.bb into some other place (outlining, for example). Can that happen? If yes, it is not unreachable code anymore.

Arguably, you can do that but you can do a lot of things that will result in problems. If you disconnect a block with a phi you are already at a point that does not make much sense. You argue that keeping the phi around as a "known" value that needs to be replaced once the block is reconnected, though it seems more like a workaround to me. Once disconnected, IR looses it's semantic, especially PHI nodes.

To summarize my point: even if we know the code is dead and noone will look into it, I don't see benefits of allowing it to be broken. In this particular case, (I hope) it will require no additional changes, since passes do not look into unreachable code and do not care if it is valid or not.

The benefit is we don't need special cases trying to not "break" it:

• They will probably never be complete, thus do not remove the need to deal with unreachable code appropriately.
• They will probably introduce conservative regressions and workarounds, as the one you added: https://reviews.llvm.org/D69865#C1676614NL685

[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,
   assert((hasNUsesOrMore(16)||// Reduce cost of this assertion for complex CFGs.
           find(pred_begin(this), pred_end(this), Pred) != pred_end(this)) &&
          "removePredecessor: BB is not a predecessor!");
 
   if (InstList.empty()) return;
   PHINode *APN = dyn_cast<PHINode>(&front());
   if (!APN) return;   // Quick exit.
 
+  // In the case below we can't replace use of %ptr.1 with %inc.ptr1
+  // because it will break SSA form.
+  //   phi.bb:
+  //     %ptr.1 = phi i8* [ %inc.ptr1, %use.bb ]
+  //     br label %use.bb
+  //   use.bb:
+  //     %inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
+  //     br i1 %cmp, label %ret.bb, label %phi.bb
+  auto canReplaceAllPhiUses = [](PHINode *PN) {
+    assert((PN->getNumIncomingValues() == 1 || PN->hasConstantValue()) &&
+           "PHI Node must have 1 or more than 1, but constant input value");
+    Value *ValToPropagate = PN->getIncomingValue(0);
+    assert(ValToPropagate && "Invalid value");
+    for (User *User : PN->users())
+      if (ValToPropagate == User)
+        return false;
+    return true;
+  };
+
   // If there are exactly two predecessors, then we want to nuke the PHI nodes
   // altogether.  However, we cannot do this, if this in this case:
   //
   //  Loop:
   //    %x = phi [X, Loop]
   //    %x2 = add %x, 1         ;; This would become %x2 = add %x2, 1
   //    br Loop                 ;; %x2 does not dominate all uses
   //
if (max_idx <= 2 && !KeepOneInputPHIs) {
     // Yup, loop through and nuke the PHI nodes
     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 inputs, replace PHI node with its now *single* value
-      if (AllowPhiElim && max_idx == 2) {
+      if (AllowPhiElim && max_idx == 2 && canReplaceAllPhiUses(PN)) {
         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()));
         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
     PHINode *PN;
     for (iterator II = begin(); (PN = dyn_cast<PHINode>(II)); ) {
       ++II;
       PN->removeIncomingValue(Pred, false);
       // If all incoming values to the Phi are the same, we can replace the Phi
       // with that value.
       Value* PNV = nullptr;
-      if (!KeepOneInputPHIs && (PNV = PN->hasConstantValue()))
+      if (!KeepOneInputPHIs && (PNV = PN->hasConstantValue()) &&
+          canReplaceAllPhiUses(PN))
         if (PNV != PN) {
           PN->replaceAllUsesWith(PNV);
           PN->eraseFromParent();
         }
     }
   }
 }
 

llvm/lib/Transforms/Utils/CloneFunction.cpp

while (I != NewFunc->end()) {
     BranchInst *BI = dyn_cast<BranchInst>(I->getTerminator());
     if (!BI || BI->isConditional()) { ++I; continue; }
 
     BasicBlock *Dest = BI->getSuccessor(0);
     if (!Dest->getSinglePredecessor()) {
       ++I; continue;
     }
 
-    // We shouldn't be able to get single-entry PHI nodes here, as instsimplify
-    // above should have zapped all of them..
-    assert(!isa<PHINode>(Dest->begin()));
+    // There are cases when we can't replace single-entry PHI, as it will break
+    // SSA form (see PR27065). We skip such blocks.
+    if (isa<PHINode>(Dest->begin())) {
+      ++I; continue;
+    }
 
-    // We know all single-entry PHI nodes in the inlined function have been
-    // removed, so we just need to splice the blocks.
+    // There are no PHI nodes in Dest, so we just need to splice the blocks.
     BI->eraseFromParent();
 
     // Make all PHI nodes that referred to Dest now refer to I as their source.
     Dest->replaceAllUsesWith(&*I);
 
     // Move all the instructions in the succ to the pred.
     I->getInstList().splice(I->end(), Dest->getInstList());
 

llvm/test/Transforms/Inline/clone-function-no-assert-on-phis.ll

 ; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
 ; RUN: opt -S -inline < %s | FileCheck %s
 ; RUN: opt -S -passes='cgscc(inline)' < %s | FileCheck %s
 
-; This test exposes bugs in BasicBlock::removePredecessor and
-; will be fixed in further patches.
-; Take a look at this line which has invalid SSA form:
-; [[TMP81_I:%.*]] = getelementptr inbounds i8, i8* [[TMP81_I]], i64 1
-; It happens to work, because the code is dead and
-; verifier doesn't complain.
+; This test checks that no assertion happens in CloneAndPruneIntoFromInst
+; from CloneFunction.cpp.
+; As a result of the changes in BasicBlock::removePredecessor,
+; now there might be phi nodes with single entry.
 
 target datalayout = "e-m:e-i64:64-f80:128-n8:16:32:64-S128"
 target triple = "x86_64-unknown-linux-gnu"
 
 @global = external hidden unnamed_addr constant [5 x i8], align 1
 
 define i32 @main(i32 %arg, i8** %arg1) {
 ; CHECK-LABEL: @main(
 ; CHECK-NEXT:  bb:
 ; CHECK-NEXT:    [[TMP:%.*]] = alloca [5 x i8], align 1
 ; CHECK-NEXT:    [[TMP2:%.*]] = alloca i8, align 1
 ; CHECK-NEXT:    [[TMP3:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* [[TMP]], i64 0, i64 0
 ; CHECK-NEXT:    call void @llvm.memcpy.p0i8.p0i8.i64(i8* nonnull align 1 dereferenceable(5) [[TMP3]], i8* nonnull align 1 dereferenceable(5) getelementptr inbounds ([5 x i8], [5 x i8]* @global, i64 0, i64 0), i64 5, i1 false)
 ; CHECK-NEXT:    [[TMP4:%.*]] = getelementptr inbounds [5 x i8], [5 x i8]* [[TMP]], i64 0, i64 0
 ; CHECK-NEXT:    store i8 97, i8* [[TMP2]], align 1
 ; CHECK-NEXT:    [[TMP_I:%.*]] = ptrtoint i8* [[TMP4]] to i64
 ; CHECK-NEXT:    [[TMP3_I:%.*]] = ptrtoint i8* [[TMP4]] to i64
 ; CHECK-NEXT:    br label [[_ZST6REMOVEIPCCET_S1_S1_RKT0__EXIT:%.*]]
+; CHECK:       bb71.i:
+; CHECK-NEXT:    [[TMP73_I:%.*]] = phi i8* [ [[TMP81_I:%.*]], [[BB83_I:%.*]] ]
+; CHECK-NEXT:    [[TMP74_I:%.*]] = phi i8* [ [[TMP80_I:%.*]], [[BB83_I]] ]
+; CHECK-NEXT:    [[TMP75_I:%.*]] = load i8, i8* [[TMP73_I]], align 1
+; CHECK-NEXT:    [[TMP76_I:%.*]] = icmp eq i8 [[TMP75_I]], [[TMP84_I:%.*]]
+; CHECK-NEXT:    br i1 [[TMP76_I]], label [[BB79_I:%.*]], label [[BB77_I:%.*]]
 ; CHECK:       bb77.i:
-; CHECK-NEXT:    store i8 [[TMP75_I:%.*]], i8* [[TMP80_I:%.*]], align 1
-; CHECK-NEXT:    [[TMP78_I:%.*]] = getelementptr inbounds i8, i8* [[TMP80_I]], i64 1
-; CHECK-NEXT:    br label [[BB79_I:%.*]]
+; CHECK-NEXT:    store i8 [[TMP75_I]], i8* [[TMP74_I]], align 1
+; CHECK-NEXT:    [[TMP78_I:%.*]] = getelementptr inbounds i8, i8* [[TMP74_I]], i64 1
+; CHECK-NEXT:    br label [[BB79_I]]
 ; CHECK:       bb79.i:
-; CHECK-NEXT:    [[TMP80_I]] = phi i8* [ [[TMP80_I]], [[BB83_I:%.*]] ], [ [[TMP78_I]], [[BB77_I:%.*]] ]
-; CHECK-NEXT:    [[TMP81_I:%.*]] = getelementptr inbounds i8, i8* [[TMP81_I]], i64 1
+; CHECK-NEXT:    [[TMP80_I]] = phi i8* [ [[TMP74_I]], [[BB71_I:%.*]] ], [ [[TMP78_I]], [[BB77_I]] ]
+; CHECK-NEXT:    [[TMP81_I]] = getelementptr inbounds i8, i8* [[TMP73_I]], i64 1
 ; CHECK-NEXT:    [[TMP82_I:%.*]] = icmp eq i8* [[TMP81_I]], [[TMP4]]
 ; CHECK-NEXT:    br i1 [[TMP82_I]], label [[_ZST6REMOVEIPCCET_S1_S1_RKT0__EXIT]], label [[BB83_I]]
 ; CHECK:       bb83.i:
-; CHECK-NEXT:    [[TMP84_I:%.*]] = load i8, i8* [[TMP2]], align 1
-; CHECK-NEXT:    [[TMP75_I]] = load i8, i8* [[TMP81_I]], align 1
-; CHECK-NEXT:    [[TMP76_I:%.*]] = icmp eq i8 [[TMP75_I]], [[TMP84_I]]
-; CHECK-NEXT:    br i1 [[TMP76_I]], label [[BB79_I]], label [[BB77_I]]
+; CHECK-NEXT:    [[TMP84_I]] = load i8, i8* [[TMP2]], align 1
+; CHECK-NEXT:    br label [[BB71_I]]
 ; CHECK:       _ZSt6removeIPccET_S1_S1_RKT0_.exit:
 ; CHECK-NEXT:    [[TMP86_I:%.*]] = phi i8* [ [[TMP4]], [[BB:%.*]] ], [ [[TMP80_I]], [[BB79_I]] ]
 ; CHECK-NEXT:    ret i32 0
 ;
 bb:
   %tmp = alloca [5 x i8], align 1
   %tmp2 = alloca i8, align 1
   %tmp3 = getelementptr inbounds [5 x i8], [5 x i8]* %tmp, i64 0, i64 0

llvm/unittests/IR/BasicBlockTest.cpp

 
 static void checkFunctionIsValid(const Function &F) {
   std::string Error;
   raw_string_ostream ErrorOS(Error);
   EXPECT_FALSE(verifyFunction(F, &ErrorOS));
   EXPECT_STREQ(ErrorOS.str().c_str(), "");
 }
 
-static void checkFunctionIsNotValid(const Function &F) {
-  EXPECT_TRUE(verifyFunction(F));
-}
-
 TEST(BasicBlockTest, RemovePredecessorPhiOneInput) {
   StringRef ModuleString = R"(
           define i32 @f(i1 %cmp, i8 *%call) {
           entry:
             br i1 %cmp, label %body, label %ret.bb
           body:
             %ptr.1 = phi i8* [ %call, %entry]
             %inc.ptr1 = getelementptr inbounds i8, i8* %ptr.1, i64 1
TEST(BasicBlockTest, RemovePredecessorReplaceUsesOfPhiWith2Inputs) {
   Function *F = M->getFunction("f");
 
   Function::iterator FI = F->begin();
   BasicBlock *EntryBB = &*FI++;
   BasicBlock *PhiBB = &*FI++;
   BasicBlock *UseBB = &*FI++;
 
   {
-    checkFunctionIsValid(*F);
     EXPECT_EQ(PhiBB->size(), 2u);
     PHINode *PN = dyn_cast<PHINode>(PhiBB->begin());
     ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
     EXPECT_EQ(PN->getNumIncomingValues(), 2u);
   }
 
   PhiBB->removePredecessor(EntryBB);
 
   {
-    checkFunctionIsNotValid(*F);
-    // Input value %inc.ptr1 was propagated into all it's uses.
-    // Now SSA form is broken.
-    EXPECT_EQ(PhiBB->size(), 1u);
+    // Input value %inc.ptr1 was NOT propagated into all it's uses.
+    // Otherwise, SSA form would be broken.
+    EXPECT_EQ(PhiBB->size(), 2u);
+    PHINode *PN = dyn_cast<PHINode>(PhiBB->begin());
+    ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
+    EXPECT_EQ(PN->getNumIncomingValues(), 1u);
     EXPECT_EQ(UseBB->size(), 2u);
     GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UseBB->begin());
     ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
-    EXPECT_EQ(GEP, GEP->getPointerOperand());
+    EXPECT_NE(GEP, GEP->getPointerOperand());
   }
 }
 
 TEST(BasicBlockTest, RemovePredecessorReplaceUsesOfPhiWith3Inputs) {
   StringRef ModuleString = R"(
           define i32 @f(i1 %cmp, i8 *%call) {
           entry:
             br i1 %cmp, label %phi.bb, label %ret.bb
TEST(BasicBlockTest, RemovePredecessorReplaceUsesOfPhiWith3Inputs) {
   Function *F = M->getFunction("f");
 
   Function::iterator FI = F->begin();
   BasicBlock *EntryBB = &*FI++;
   BasicBlock *PhiBB = &*FI++;
   BasicBlock *UseBB = &*FI++;
 
   {
-    checkFunctionIsValid(*F);
     EXPECT_EQ(PhiBB->size(), 2u);
     PHINode *PN = dyn_cast<PHINode>(PhiBB->begin());
     ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
     EXPECT_EQ(PN->getNumIncomingValues(), 3u);
   }
 
   PhiBB->removePredecessor(EntryBB);
 
   {
-    // Input value %inc.ptr1 was propagated into all it's uses.
-    // Now SSA form is broken.
-    checkFunctionIsNotValid(*F);
-    EXPECT_EQ(PhiBB->size(), 1u);
+    // Input value %inc.ptr1 was NOT propagated into all it's uses.
+    // Otherwise, SSA form would be broken.
+    EXPECT_EQ(PhiBB->size(), 2u);
+    PHINode *PN = dyn_cast<PHINode>(PhiBB->begin());
+    ASSERT_NE(PN, nullptr) << "Couldn't get PHINode.";
+    EXPECT_EQ(PN->getNumIncomingValues(), 2u);
     EXPECT_EQ(UseBB->size(), 2u);
     GetElementPtrInst *GEP = dyn_cast<GetElementPtrInst>(UseBB->begin());
     ASSERT_NE(GEP, nullptr) << "Expecting GEP as a first instruction";
-    EXPECT_EQ(GEP, GEP->getPointerOperand());
+    EXPECT_NE(GEP, GEP->getPointerOperand());
   }
 }
 
 } // End anonymous namespace.
 } // End llvm namespace.