[Inliner] Try to inline if some blocks in the callee have address taken, but not used in a meaningful.

[trentxintong]

Summary

This patch introduces the hasAddressTakenAndUsed() API for
BasicBlock and make use it in InlineCost and JumpThreading.

I can also split this into 2 patches, i.e. introduce
hasAddressTakenAndUsed() first and make InlineCost use it, then
rewrite Jumpthreading to use it in the second patch.

[davidxl]

include/llvm/IR/BasicBlock.h

390

Perhaps change this to: Return true if the basic block address is taken and used by other instructions that can not be proved to be dead.

[efriedma]

include/llvm/IR/BasicBlock.h

391

Could we just replace hasAddressTaken() with this function? I don't think anything calling hasAddressTaken() actually cares if there are dead uses.

lib/IR/BasicBlock.cpp

446

Please use isConstantUsed instead; mutating the IR in a function named "hasAddressTakenAndUsed" is confusing.

[trentxintong]

include/llvm/IR/BasicBlock.h

390

Will do so.

391

I feel this is a good way to go.

However, I feel we still need an API to only check whether getSubclassDataFromValue() is 0 or not. This is needed because BlockAddress::lookup(const BasicBlock *BB) uses it for early exit. And there are other similar uses in the code base.

I feel we should keep hasAddressTaken() as it is now and make passes use hasAddressTakenAndUsed() because they do not actually cares if there are dead uses (I suspect most passes if not all).

lib/IR/BasicBlock.cpp

446

Will do so.

include/llvm/IR/BasicBlock.h

public:
   BasicBlock *splitBasicBlock(Instruction *I, const Twine &BBName = "") {
     return splitBasicBlock(I->getIterator(), BBName);
   }
 
   /// Returns true if there are any uses of this basic block other than
   /// direct branches, switches, etc. to it.
   bool hasAddressTaken() const { return getSubclassDataFromValue() != 0; }
 
+  /// Return true if the basic block address is taken and used in a meaningful
+  /// way, i.e. non-dead way.
+  bool hasAddressTakenAndUsed();
+
   /// Update all phi nodes in this basic block's successors to refer to basic
   /// block \p New instead of to it.
   void replaceSuccessorsPhiUsesWith(BasicBlock *New);
 
   /// Return true if this basic block is an exception handling block.
   bool isEHPad() const { return getFirstNonPHI()->isEHPad(); }
 
   /// Return true if this basic block is a landing pad.

lib/Analysis/InlineCost.cpp

if (BB->empty())
       continue;
 
     // Disallow inlining a blockaddress. A blockaddress only has defined
     // behavior for an indirect branch in the same function, and we do not
     // currently support inlining indirect branches. But, the inliner may not
     // see an indirect branch that ends up being dead code at a particular call
     // site. If the blockaddress escapes the function, e.g., via a global
     // variable, inlining may lead to an invalid cross-function reference.
-    if (BB->hasAddressTaken())
+    if (BB->hasAddressTakenAndUsed())
       return false;
 
     // Analyze the cost of this block. If we blow through the threshold, this
     // returns false, and we can bail on out.
     if (!analyzeBlock(BB, EphValues))
       return false;
 
     TerminatorInst *TI = BB->getTerminator();

lib/IR/BasicBlock.cpp

for (auto &PN : Successor->phis()) {
         PN.setIncomingBlock((unsigned)Idx, New);
         Idx = PN.getBasicBlockIndex(this);
       }
     }
   }
   return New;
 }
 
+bool BasicBlock::hasAddressTakenAndUsed() {
+  if (!hasAddressTaken())
+    return false;
+
+  // If the block has its address taken, but not used in a meaningful way.
+  // then this shouldn't keep the block alive or prevent function inlining, etc.
+  BlockAddress *BA = BlockAddress::get(this);
+  BA->removeDeadConstantUsers();
+  return !BA->use_empty();
+}
+
 void BasicBlock::replaceSuccessorsPhiUsesWith(BasicBlock *New) {
   TerminatorInst *TI = getTerminator();
   if (!TI)
     // Cope with being called on a BasicBlock that doesn't have a terminator
     // yet. Clang's CodeGenFunction::EmitReturnBlock() likes to do this.
     return;
   for (BasicBlock *Succ : TI->successors()) {
     // N.B. Succ might not be a complete BasicBlock, so don't assume

lib/Transforms/Scalar/JumpThreading.cpp

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 (DDT->pendingDeletedBB(BB) ||
       (pred_empty(BB) && BB != &BB->getParent()->getEntryBlock()))
     return false;
 
   // If this block has a single predecessor, and if that pred has a single
   // successor, merge the blocks.  This encourages recursive jump threading
   // because now the condition in this block can be threaded through
   // predecessors of our predecessor block.
   if (BasicBlock *SinglePred = BB->getSinglePredecessor()) {
     const TerminatorInst *TI = SinglePred->getTerminator();
     if (!TI->isExceptional() && TI->getNumSuccessors() == 1 &&
-        SinglePred != BB && !hasAddressTakenAndUsed(BB)) {
+        SinglePred != BB && !BB->hasAddressTakenAndUsed()) {
       // If SinglePred was a loop header, BB becomes one.
       if (LoopHeaders.erase(SinglePred))
         LoopHeaders.insert(BB);
 
       LVI->eraseBlock(SinglePred);
       MergeBasicBlockIntoOnlyPred(BB, nullptr, DDT);
 
       // Now that BB is merged into SinglePred (i.e. SinglePred Code followed by

test/Transforms/Inline/blockaddress.ll

 ; RUN: opt -inline -S < %s | FileCheck %s
+; RUN: opt -dce -inline -S < %s | FileCheck %s --check-prefixes=CHECK-DCE-INLINE
 ; RUN: opt -passes='cgscc(inline)' -S < %s | FileCheck %s
+; RUN: opt -passes='function(dce),cgscc(inline)' -S < %s | FileCheck %s --check-prefixes=CHECK-DCE-INLINE
 ; PR10162
 
 ; Make sure doit is not inlined since the blockaddress is taken
 ; which could be unsafe
 ; CHECK: store i8* blockaddress(@doit, %here), i8** %pptr, align 8
 
 @i = global i32 1, align 4
 @ptr1 = common global i8* null, align 8
entry:
   store i8* blockaddress(@run, %bb), i8** getelementptr inbounds ([1 x i8*], [1 x i8*]* @run.bb, i64 0, i64 0), align 8
   ret void
 
 bb:
   unreachable
 }
 
 @run.bb = global [1 x i8*] zeroinitializer
+
+define i32 @g() {
+entry:
+  %dead = extractvalue [1 x i8*] [ i8* blockaddress(@g, %L0) ], 0
+  br label %L0
+L0:
+  ret i32 0
+}
+
+; Make sure we can inline @g into @run_g as once %dead in @g is deleted
+; the blockaddress on %L0 in @g becomes dead.
+;
+; CHECK-DCE-INLINE-LABEL: define void @run_g(
+; CHECK-DCE-INLINE-NOT: call
+; CHECK-DCE-INLINE: ret void
+define void @run_g() {
+entry:
+  call i32 @g()
+  ret void
+}