[IR] Prefer not to delete blocks that have their address taken

[lebedev.ri]

Summary

Honestly, i don't know what should happen when we want to delete
a block that has their address taken.

Currently, when that happens, the i8* blockaddress(@fun, %bb)
is replaced with i8* inttoptr i32 1 to i8*. Which is obviously
no longer an address of a block, and iff the use semantically required
it to actually be an address of a block, e.g. AArch64's S constaint
in llvm/test/CodeGen/AArch64/inlineasm-S-constraint.ll,
then the IR suddenly becomes invalid.

I have only noticed this because that test starts to fail
after some SimplifyCFG changes.

So, since, the blocks practically never have their addresses taken,
i would propose to:

1. forbid DeleteDeadBlocks() from deleting blocks that have their addresses taken. This will allow to catch the precise codepath that is missing aa precondition.
2. Don't delete blocks that have their addresses taken
3. Allow to delete unreachable that have their addresses taken - taking an address does not count as block reachability.

[jrtc27]

What about something like https://godbolt.org/z/47eoabYMe? The evil address-of-label/indirect-goto GNU extension makes it possible to generate this kind of thing in C, it's not just buggy IR generation.

[jrtc27]

My inclination is to say that address of should be treated the same as branching for BB liveness.

[jrtc27]

llvm/test/CodeGen/RISCV/codemodel-lowering.ll

34

Seems this test has always highlighted the broken behaviour :( should have caught that in review...

[lebedev.ri]

In D102764#2768413, @jrtc27 wrote:

My inclination is to say that address of should be treated the same as branching for BB liveness.

I'm not really sure how that would look.
It will, for sure, require LangRef changes, and somewhat invasive changes to the code.
Here i mostly only have enough motivation to avoid encountering/creating verifier errors,
not fixing the entirety of potentially-misdesigned BlockAddress thingy.

Allow to delete unreachable that have their addresses taken - taking an address does not count as block reachability.

Though, i guess this isn't enough. We could still end up with a case
where AArch64's S constaint was expecting an address of a now-unreachable block.
So once again, i do not understand the rules.

[efriedma]

Which is obviously no longer an address of a block, and iff the use semantically required it to actually be an address of a block, e.g. AArch64's S constaint in llvm/test/CodeGen/AArch64/inlineasm-S-constraint.ll, then the IR suddenly becomes invalid.

Not completely sure what you mean by "semantically required"; you mean it has to point somewhere in the same section?

We could add support for blockaddress(@lower_blockaddress, null) or something like that, I guess. I don't think it makes sense to block the elimination of unreachable blocks; that's likely to cause other issues.

[lebedev.ri]

In D102764#2769261, @efriedma wrote:

Which is obviously no longer an address of a block, and iff the use semantically required it to actually be an address of a block, e.g. AArch64's S constaint in llvm/test/CodeGen/AArch64/inlineasm-S-constraint.ll, then the IR suddenly becomes invalid.

Not completely sure what you mean by "semantically required"; you mean it has to point somewhere in the same section?

For example, if we, for some reason, decide to delete block %loc in @test_inline_constraint_S_label(),
(i8* blockaddress(@test_inline_constraint_S_label, %loc)) will be replaced with e.g. (i8* inttoptr(i32 1 to i8*)),
and whoops: https://godbolt.org/z/Ee1Y6sbEf

We could add support for blockaddress(@lower_blockaddress, null) or something like that, I guess.

I don't think it makes sense to block the elimination of unreachable blocks; that's likely to cause other issues.

Yeah, i'm still unsure how we are supposed to deal with blockaddress thing :/

[lebedev.ri]

Ok, how about this common ground approach?
This is pretty horrible, but i'm not quite sure what alternative there is.

[efriedma]

Rather than a "zombie" BB, my suggestion is to invent a new kind of blockaddress that doesn't refer to a bb at all. The backend would then just point it at the entry block or something like that. Makes blockaddress handling a bit more complicated, but it makes CFG handling simpler, which seems more important. (Our current CFG rules are hard enough to understand.)

[lebedev.ri]

Hmm. This is looking more and more complicated by the comment.
I'm afraid i just don't have enough interest in BlockAddress to deal with this.

llvm/include/llvm/IR/BasicBlock.h

public:
   }
 
   /// Returns true if there are any uses of this basic block other than
   /// direct branches, switches, etc. to it.
   bool hasAddressTaken() const {
     return getBasicBlockBits().BlockAddressRefCount != 0;
   }
 
+  /// Returns true if there are any uses of this basic block other than
+  /// direct branches, switches, etc. to it. Note that this will first try to
+  /// drop zombie BlockAddress'es that aren't used by anything.
+  bool hasAddressTakenAndUsed();
+
+  /// Dpes this block has it's address taken, and there are not other uses of
+  /// the block, and the block consists of a single "unreachable" instruction?
+  bool isZombieAddressTakenBlock();
+
   /// Update all phi nodes in this basic block to refer to basic block \p New
   /// instead of basic block \p Old.
   void replacePhiUsesWith(BasicBlock *Old, BasicBlock *New);
 
   /// Update all phi nodes in this basic block's successors to refer to basic
   /// block \p New instead of basic block \p Old.
   void replaceSuccessorsPhiUsesWith(BasicBlock *Old, BasicBlock *New);
 

llvm/lib/IR/BasicBlock.cpp

BasicBlock *BasicBlock::splitBasicBlockBefore(iterator I, const Twine &BBName) {
   }
   // Add a branch instruction from  "New" to "this" Block.
   BranchInst *BI = BranchInst::Create(this, New);
   BI->setDebugLoc(Loc);
 
   return New;
 }
 
+bool BasicBlock::hasAddressTakenAndUsed() {
+  if (!const_cast<const BasicBlock *>(this)->hasAddressTaken())
+    return false;
+
+  if (getParent()) {
+    // If the block has its address taken, it may be a tree of dead constants
+    // hanging off of it.  These shouldn't keep the block alive.
+    BlockAddress *BA = BlockAddress::get(this);
+    BA->removeDeadConstantUsers();
+    return !BA->use_empty();
+  }
+
+  return any_of(users(), [](const User *U) { return isa<BlockAddress>(U); });
+}
+
+bool BasicBlock::isZombieAddressTakenBlock() {
+  if (!hasAddressTakenAndUsed())
+    return false;
+
+  return sizeWithoutDebug() == 1 && hasOneUse() &&
+         isa<UnreachableInst>(getTerminator());
+}
+
 void BasicBlock::replacePhiUsesWith(BasicBlock *Old, BasicBlock *New) {
   // N.B. This might not be a complete BasicBlock, so don't assume
   // that it ends with a non-phi instruction.
   for (iterator II = begin(), IE = end(); II != IE; ++II) {
     PHINode *PN = dyn_cast<PHINode>(II);
     if (!PN)
       break;
     PN->replaceIncomingBlockWith(Old, New);

llvm/lib/Transforms/Scalar/JumpThreading.cpp

for (auto &BB : F) {
         RemoveRedundantDbgInstrs(&BB, true);
 
       // Stop processing BB if it's the entry or is now deleted. The following
       // routines attempt to eliminate BB and locating a suitable replacement
       // for the entry is non-trivial.
       if (&BB == &F.getEntryBlock() || DTU->isBBPendingDeletion(&BB))
         continue;
 
-      if (pred_empty(&BB)) {
+      if (pred_empty(&BB) && !BB.isZombieAddressTakenBlock()) {
         // When processBlock makes BB unreachable it doesn't bother to fix up
         // the instructions in it. We must remove BB to prevent invalid IR.
         LLVM_DEBUG(dbgs() << "  JT: Deleting dead block '" << BB.getName()
                           << "' with terminator: " << *BB.getTerminator()
                           << '\n');
         LoopHeaders.erase(&BB);
         LVI->eraseBlock(&BB);
         DeleteDeadBlock(&BB, DTU);
if (NumPreds < MinNumPreds) {
       MinSucc = i;
       MinNumPreds = NumPreds;
     }
   }
 
   return MinSucc;
 }
 
-static bool hasAddressTakenAndUsed(BasicBlock *BB) {
-  if (!BB->hasAddressTaken()) return false;
-
-  // If the block has its address taken, it may be a tree of dead constants
-  // hanging off of it.  These shouldn't keep the block alive.
-  BlockAddress *BA = BlockAddress::get(BB);
-  BA->removeDeadConstantUsers();
-  return !BA->use_empty();
-}
-
 /// processBlock - If there are any predecessors whose control can be threaded
 /// through to a successor, transform them now.
 bool JumpThreadingPass::processBlock(BasicBlock *BB) {
   // If the block is trivially dead, just return and let the caller nuke it.
   // This simplifies other transformations.
   if (DTU->isBBPendingDeletion(BB) ||
       (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
     return false;

 /// Merge basic block BB into its sole predecessor if possible.
 bool JumpThreadingPass::maybeMergeBasicBlockIntoOnlyPred(BasicBlock *BB) {
   BasicBlock *SinglePred = BB->getSinglePredecessor();
   if (!SinglePred)
     return false;
 
   const Instruction *TI = SinglePred->getTerminator();
   if (TI->isExceptionalTerminator() || TI->getNumSuccessors() != 1 ||
-      SinglePred == BB || hasAddressTakenAndUsed(BB))
+      SinglePred == BB || BB->hasAddressTakenAndUsed())
     return false;
 
   // If SinglePred was a loop header, BB becomes one.
   if (LoopHeaders.erase(SinglePred))
     LoopHeaders.insert(BB);
 
   LVI->eraseBlock(SinglePred);
   MergeBasicBlockIntoOnlyPred(BB, DTU);

llvm/lib/Transforms/Utils/BasicBlockUtils.cpp

 #endif
 
   SmallVector<DominatorTree::UpdateType, 4> Updates;
   DetatchDeadBlocks(BBs, DTU ? &Updates : nullptr, KeepOneInputPHIs);
 
   if (DTU)
     DTU->applyUpdates(Updates);
 
-  for (BasicBlock *BB : BBs)
+  for (BasicBlock *BB : BBs) {
+    // We can't *actually* delete blocks that have their address taken...
+    if (BB->isZombieAddressTakenBlock())
+      continue;
     if (DTU)
       DTU->deleteBB(BB);
     else
       BB->eraseFromParent();
   }
+}
 
 bool llvm::EliminateUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
                                       bool KeepOneInputPHIs) {
   df_iterator_default_set<BasicBlock*> Reachable;
 
   // Mark all reachable blocks.
   for (BasicBlock *BB : depth_first_ext(&F, Reachable))
     (void)BB/* Mark all reachable blocks */;

llvm/lib/Transforms/Utils/Local.cpp

bool llvm::removeUnreachableBlocks(Function &F, DomTreeUpdater *DTU,
   SmallSetVector<BasicBlock *, 8> BlocksToRemove;
   for (BasicBlock &BB : F) {
     // Skip reachable basic blocks
     if (Reachable.count(&BB))
       continue;
     // Skip already-deleted blocks
     if (DTU && DTU->isBBPendingDeletion(&BB))
       continue;
+    if (BB.isZombieAddressTakenBlock())
+      continue;
     BlocksToRemove.insert(&BB);
   }
 
   if (BlocksToRemove.empty())
     return Changed;
 
   Changed = true;
   NumRemoved += BlocksToRemove.size();

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

if (auto *BI = dyn_cast<BranchInst>(TI)) {
       Changed = true;
     }
   }
 
   if (DTU)
     DTU->applyUpdates(Updates);
 
   // If this block is now dead, remove it.
-  if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) {
+  if (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock() &&
+      !BB->isZombieAddressTakenBlock()) {
     DeleteDeadBlock(BB, DTU);
     return true;
   }
 
   return Changed;
 }
 
 static bool CasesAreContiguous(SmallVectorImpl<ConstantInt *> &Cases) {

 bool SimplifyCFGOpt::simplifyOnceImpl(BasicBlock *BB) {
   bool Changed = false;
 
   assert(BB && BB->getParent() && "Block not embedded in function!");
   assert(BB->getTerminator() && "Degenerate basic block encountered!");
 
   // Remove basic blocks that have no predecessors (except the entry block)...
   // or that just have themself as a predecessor.  These are unreachable.
-  if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()) ||
+  if ((pred_empty(BB) && BB != &BB->getParent()->getEntryBlock() &&
+       !BB->isZombieAddressTakenBlock()) ||
       BB->getSinglePredecessor() == BB) {
     LLVM_DEBUG(dbgs() << "Removing BB: \n" << *BB);
     DeleteDeadBlock(BB, DTU);
     return true;
   }
 
   // Check to see if we can constant propagate this terminator instruction
   // away...

llvm/test/CodeGen/RISCV/codemodel-lowering.ll

 }
 
 ; Check lowering of blockaddresses
 
 @addr = global i8* null
 
 define void @lower_blockaddress() nounwind {
 ; RV32I-SMALL-LABEL: lower_blockaddress:
 ; RV32I-SMALL:       # %bb.0:
 ; RV32I-SMALL-NEXT:    lui a0, %hi(addr)
-; RV32I-SMALL-NEXT:    addi a1, zero, 1
+; RV32I-SMALL-NEXT:    lui a1, %hi(.Ltmp0)
+; RV32I-SMALL-NEXT:    addi a1, a1, %lo(.Ltmp0)
 ; RV32I-SMALL-NEXT:    sw a1, %lo(addr)(a0)
 ; RV32I-SMALL-NEXT:    ret
+; RV32I-SMALL-NEXT:  .Ltmp0: # Address of block that was removed by CodeGen
 ;
 ; RV32I-MEDIUM-LABEL: lower_blockaddress:
 ; RV32I-MEDIUM:       # %bb.0:
 ; RV32I-MEDIUM-NEXT:  .LBB1_1: # Label of block must be emitted
 ; RV32I-MEDIUM-NEXT:    auipc a0, %pcrel_hi(addr)
 ; RV32I-MEDIUM-NEXT:    addi a0, a0, %pcrel_lo(.LBB1_1)
-; RV32I-MEDIUM-NEXT:    addi a1, zero, 1
+; RV32I-MEDIUM-NEXT:  .LBB1_2: # Label of block must be emitted
+; RV32I-MEDIUM-NEXT:    auipc a1, %pcrel_hi(.Ltmp0)
+; RV32I-MEDIUM-NEXT:    addi a1, a1, %pcrel_lo(.LBB1_2)
 ; RV32I-MEDIUM-NEXT:    sw a1, 0(a0)
 ; RV32I-MEDIUM-NEXT:    ret
+; RV32I-MEDIUM-NEXT:  .Ltmp0: # Address of block that was removed by CodeGen
   store volatile i8* blockaddress(@lower_blockaddress, %block), i8** @addr
   ret void
 
 block:
   unreachable
 }
 
 ; Check lowering of blockaddress that forces a displacement to be added
 
 define signext i32 @lower_blockaddress_displ(i32 signext %w) nounwind {
 ; RV32I-SMALL-LABEL: lower_blockaddress_displ:
 ; RV32I-SMALL:       # %bb.0: # %entry
 ; RV32I-SMALL-NEXT:    addi sp, sp, -16
-; RV32I-SMALL-NEXT:    lui a1, %hi(.Ltmp0)
-; RV32I-SMALL-NEXT:    addi a1, a1, %lo(.Ltmp0)
+; RV32I-SMALL-NEXT:    lui a1, %hi(.Ltmp1)
+; RV32I-SMALL-NEXT:    addi a1, a1, %lo(.Ltmp1)
 ; RV32I-SMALL-NEXT:    addi a2, zero, 101
 ; RV32I-SMALL-NEXT:    sw a1, 8(sp)
 ; RV32I-SMALL-NEXT:    blt a0, a2, .LBB2_3
 ; RV32I-SMALL-NEXT:  # %bb.1: # %if.then
 ; RV32I-SMALL-NEXT:    lw a0, 8(sp)
 ; RV32I-SMALL-NEXT:    jr a0
-; RV32I-SMALL-NEXT:  .Ltmp0: # Block address taken
+; RV32I-SMALL-NEXT:  .Ltmp1: # Block address taken
 ; RV32I-SMALL-NEXT:  .LBB2_2: # %return
 ; RV32I-SMALL-NEXT:    addi a0, zero, 4
 ; RV32I-SMALL-NEXT:    addi sp, sp, 16
 ; RV32I-SMALL-NEXT:    ret
 ; RV32I-SMALL-NEXT:  .LBB2_3: # %return.clone
 ; RV32I-SMALL-NEXT:    addi a0, zero, 3
 ; RV32I-SMALL-NEXT:    addi sp, sp, 16
 ; RV32I-SMALL-NEXT:    ret
 ;
 ; RV32I-MEDIUM-LABEL: lower_blockaddress_displ:
 ; RV32I-MEDIUM:       # %bb.0: # %entry
 ; RV32I-MEDIUM-NEXT:    addi sp, sp, -16
 ; RV32I-MEDIUM-NEXT:  .LBB2_4: # %entry
 ; RV32I-MEDIUM-NEXT:    # Label of block must be emitted
-; RV32I-MEDIUM-NEXT:    auipc a1, %pcrel_hi(.Ltmp0)
+; RV32I-MEDIUM-NEXT:    auipc a1, %pcrel_hi(.Ltmp1)
 ; RV32I-MEDIUM-NEXT:    addi a1, a1, %pcrel_lo(.LBB2_4)
 ; RV32I-MEDIUM-NEXT:    addi a2, zero, 101
 ; RV32I-MEDIUM-NEXT:    sw a1, 8(sp)
 ; RV32I-MEDIUM-NEXT:    blt a0, a2, .LBB2_3
 ; RV32I-MEDIUM-NEXT:  # %bb.1: # %if.then
 ; RV32I-MEDIUM-NEXT:    lw a0, 8(sp)
 ; RV32I-MEDIUM-NEXT:    jr a0
-; RV32I-MEDIUM-NEXT:  .Ltmp0: # Block address taken
+; RV32I-MEDIUM-NEXT:  .Ltmp1: # Block address taken
 ; RV32I-MEDIUM-NEXT:  .LBB2_2: # %return
 ; RV32I-MEDIUM-NEXT:    addi a0, zero, 4
 ; RV32I-MEDIUM-NEXT:    addi sp, sp, 16
 ; RV32I-MEDIUM-NEXT:    ret
 ; RV32I-MEDIUM-NEXT:  .LBB2_3: # %return.clone
 ; RV32I-MEDIUM-NEXT:    addi a0, zero, 3
 ; RV32I-MEDIUM-NEXT:    addi sp, sp, 16
 ; RV32I-MEDIUM-NEXT:    ret