[SimplifyCFG] Allow SimplifyCFG sinking to merge tail call kinds

[eddyz87]

Summary

This commit modifies SimplifyCFGPass to allow sinking of calls that
differ in tail call kind. Specifically if tail call kinds for sink
candidates are TCK_Tail and TCK_None it is safe to sink the call
and assign TCK_None as a kind for the merged instruction.

Could be illustrated by the following example:

c
extern void escape(void*);
extern int magic(void);
extern void tailfn(void);

void foofn() {
  int x;
  if (magic()) {
    tailfn();
  } else {
    escape(&x);
    tailfn();
  }
}

Could be rewritten as:

c
void foofn() {
  int x;
  if (!magic())
    escape(&x);
  tailfn();
}

W/o this commit such transformation does not happen, because
TailCallElimPass computes different tail call kinds for two tailfn
calls:

entry:
  %x = alloca i32, align 4
  %call = tail call i32 @magic()
  %tobool.not = icmp eq i32 %call, 0
  br i1 %tobool.not, label %if.else, label %if.then

if.then:
  tail call void @tailfn()
  br label %if.end

if.else:
  call void @escape(ptr noundef nonnull %x)
  call void @tailfn()
  br label %if.end

When SimplifyCFGPass considers what instructions to sink to a common
successor it uses the function Instruction::isSameOperationAs to
identify sink candidates. However this function returns false if call
instructions have different values of tail call kind flag.

This commit extends Instruction::isSameOperationAs with a flag to
ignore tail call kind and extends SimplifyCFGPass with logic to
compute a common tail call kind for a merged instruction.

[eddyz87]

This follows the discussion in the following thread.

[eddyz87]

Rebase + clang-format fixes

[eddyz87]

Formatting again...

llvm/include/llvm/IR/Instruction.h

public:
   /// SubclassOptionalData flags, which may specify conditions under which the
   /// instruction's result is undefined.
   bool isIdenticalToWhenDefined(const Instruction *I) const;
 
   /// When checking for operation equivalence (using isSameOperationAs) it is
   /// sometimes useful to ignore certain attributes.
   enum OperationEquivalenceFlags {
     /// Check for equivalence ignoring load/store alignment.
-    CompareIgnoringAlignment = 1<<0,
+    CompareIgnoringAlignment = 1 << 0,
     /// Check for equivalence treating a type and a vector of that type
     /// as equivalent.
-    CompareUsingScalarTypes = 1<<1
+    CompareUsingScalarTypes = 1 << 1,
+    CompareIgnoringTailCall = 1 << 2
   };
 
   /// This function determines if the specified instruction executes the same
   /// operation as the current one. This means that the opcodes, type, operand
   /// types and any other factors affecting the operation must be the same. This
   /// is similar to isIdenticalTo except the operands themselves don't have to
   /// be identical.
   /// @returns true if the specified instruction is the same operation as

llvm/lib/IR/Instruction.cpp

const char *Instruction::getOpcodeName(unsigned OpCode) {
   default: return "<Invalid operator> ";
   }
 }
 
 /// Return true if both instructions have the same special state. This must be
 /// kept in sync with FunctionComparator::cmpOperations in
 /// lib/Transforms/IPO/MergeFunctions.cpp.
 static bool haveSameSpecialState(const Instruction *I1, const Instruction *I2,
-                                 bool IgnoreAlignment = false) {
+                                 bool IgnoreAlignment = false,
+                                 bool IgnoreTailCall = false) {
   assert(I1->getOpcode() == I2->getOpcode() &&
          "Can not compare special state of different instructions");
 
   if (const AllocaInst *AI = dyn_cast<AllocaInst>(I1))
     return AI->getAllocatedType() == cast<AllocaInst>(I2)->getAllocatedType() &&
            (AI->getAlign() == cast<AllocaInst>(I2)->getAlign() ||
             IgnoreAlignment);
   if (const LoadInst *LI = dyn_cast<LoadInst>(I1))
     return LI->isVolatile() == cast<LoadInst>(I2)->isVolatile() &&
            (LI->getAlign() == cast<LoadInst>(I2)->getAlign() ||
             IgnoreAlignment) &&
            LI->getOrdering() == cast<LoadInst>(I2)->getOrdering() &&
            LI->getSyncScopeID() == cast<LoadInst>(I2)->getSyncScopeID();
   if (const StoreInst *SI = dyn_cast<StoreInst>(I1))
     return SI->isVolatile() == cast<StoreInst>(I2)->isVolatile() &&
            (SI->getAlign() == cast<StoreInst>(I2)->getAlign() ||
             IgnoreAlignment) &&
            SI->getOrdering() == cast<StoreInst>(I2)->getOrdering() &&
            SI->getSyncScopeID() == cast<StoreInst>(I2)->getSyncScopeID();
   if (const CmpInst *CI = dyn_cast<CmpInst>(I1))
     return CI->getPredicate() == cast<CmpInst>(I2)->getPredicate();
   if (const CallInst *CI = dyn_cast<CallInst>(I1))
-    return CI->isTailCall() == cast<CallInst>(I2)->isTailCall() &&
+    return (CI->isTailCall() == cast<CallInst>(I2)->isTailCall() ||
+            IgnoreTailCall) &&
            CI->getCallingConv() == cast<CallInst>(I2)->getCallingConv() &&
            CI->getAttributes() == cast<CallInst>(I2)->getAttributes() &&
            CI->hasIdenticalOperandBundleSchema(*cast<CallInst>(I2));
   if (const InvokeInst *CI = dyn_cast<InvokeInst>(I1))
     return CI->getCallingConv() == cast<InvokeInst>(I2)->getCallingConv() &&
            CI->getAttributes() == cast<InvokeInst>(I2)->getAttributes() &&
            CI->hasIdenticalOperandBundleSchema(*cast<InvokeInst>(I2));
   if (const CallBrInst *CI = dyn_cast<CallBrInst>(I1))

 }
 
 // Keep this in sync with FunctionComparator::cmpOperations in
 // lib/Transforms/IPO/MergeFunctions.cpp.
 bool Instruction::isSameOperationAs(const Instruction *I,
                                     unsigned flags) const {
   bool IgnoreAlignment = flags & CompareIgnoringAlignment;
   bool UseScalarTypes  = flags & CompareUsingScalarTypes;
+  bool IgnoreTailCall = flags & CompareIgnoringTailCall;
 
   if (getOpcode() != I->getOpcode() ||
       getNumOperands() != I->getNumOperands() ||
       (UseScalarTypes ?
        getType()->getScalarType() != I->getType()->getScalarType() :
        getType() != I->getType()))
     return false;
 
   // We have two instructions of identical opcode and #operands.  Check to see
   // if all operands are the same type
   for (unsigned i = 0, e = getNumOperands(); i != e; ++i)
     if (UseScalarTypes ?
         getOperand(i)->getType()->getScalarType() !=
           I->getOperand(i)->getType()->getScalarType() :
         getOperand(i)->getType() != I->getOperand(i)->getType())
       return false;
 
-  return haveSameSpecialState(this, I, IgnoreAlignment);
+  return haveSameSpecialState(this, I, IgnoreAlignment, IgnoreTailCall);
 }
 
 bool Instruction::isUsedOutsideOfBlock(const BasicBlock *BB) const {
   for (const Use &U : uses()) {
     // PHI nodes uses values in the corresponding predecessor block.  For other
     // instructions, just check to see whether the parent of the use matches up.
     const Instruction *I = cast<Instruction>(U.getUser());
     const PHINode *PN = dyn_cast<PHINode>(I);

llvm/lib/Transforms/Utils/SimplifyCFG.cpp

 
 // TODO: Refine this. This should avoid cases like turning constant memcpy sizes
 // into variables.
 static bool replacingOperandWithVariableIsCheap(const Instruction *I,
                                                 int OpIdx) {
   return !isa<IntrinsicInst>(I);
 }
 
+// Compute if there is a common tail call kind that could be used for
+// a merged call instruction. Assumes that all `Insts` are CallInst.
+// Allow identical tail call kinds or a mix of TCK_None and TCK_Tail.
+static Optional<CallInst::TailCallKind>
+computeCommonTailCallKind(ArrayRef<Instruction *> Insts) {
+  using TCK = CallInst::TailCallKind;
+  const auto MustTail = 1u << TCK::TCK_MustTail;
+  const auto NoTail = 1u << TCK::TCK_NoTail;
+  const auto Tail = 1u << TCK::TCK_Tail;
+  const auto TCKNone = 1u << TCK::TCK_None;
+  unsigned Present = 0u;
+  for (auto *I : Insts) {
+    auto *Call = cast<CallInst>(I);
+    Present |= 1u << Call->getTailCallKind();
+  }
+  switch (Present) {
+  case MustTail:
+    return {TCK::TCK_MustTail};
+  case NoTail:
+    return {TCK::TCK_NoTail};
+  case Tail:
+    return {TCK::TCK_Tail};
+  case TCKNone:
+    return {TCK::TCK_None};
+  case Tail | TCKNone:
+    return {TCK::TCK_None};
+  default:
+    return None;
+  }
+}
+
 // All instructions in Insts belong to different blocks that all unconditionally
 // branch to a common successor. Analyze each instruction and return true if it
 // would be possible to sink them into their successor, creating one common
 // instruction instead. For every value that would be required to be provided by
 // PHI node (because an operand varies in each input block), add to PHIOperands.
 static bool canSinkInstructions(
     ArrayRef<Instruction *> Insts,
     DenseMap<Instruction *, SmallVector<Value *, 4>> &PHIOperands) {
for (auto *I : Insts) {
     if (HasUse && !I->hasOneUse())
       return false;
     if (!HasUse && !I->user_empty())
       return false;
   }
 
   const Instruction *I0 = Insts.front();
   for (auto *I : Insts)
-    if (!I->isSameOperationAs(I0))
-      return false;
+    if (!I->isSameOperationAs(I0, Instruction::CompareIgnoringTailCall))
+      return false;
+
+  // Do not sink if tail call kinds are incompatible
+  if (isa<CallInst>(I0) && !computeCommonTailCallKind(Insts))
 
   // All instructions in Insts are known to be the same opcode. If they have a
   // use, check that the only user is a PHI or in the same block as the
   // instruction, because if a user is in the same block as an instruction we're
   // contemplating sinking, it must already be determined to be sinkable.
   if (HasUse) {
     auto *PNUse = dyn_cast<PHINode>(*I0->user_begin());
     auto *Succ = I0->getParent()->getTerminator()->getSuccessor(0);
if (I != I0) {
       // This is an N-way merge, which will be inefficient if I0 is a CallInst.
       // However, as N-way merge for CallInst is rare, so we use simplified API
       // instead of using complex API for N-way merge.
       I0->applyMergedLocation(I0->getDebugLoc(), I->getDebugLoc());
       combineMetadataForCSE(I0, I, true);
       I0->andIRFlags(I);
     }
 
+  if (auto *Call = dyn_cast<CallInst>(I0)) {
+    auto TailCallKind = computeCommonTailCallKind(Insts);
+    Call->setTailCallKind(TailCallKind.value());
+  }
+
   if (!I0->user_empty()) {
     // canSinkLastInstruction checked that all instructions were used by
     // one and only one PHI node. Find that now, RAUW it to our common
     // instruction and nuke it.
     auto *PN = cast<PHINode>(*I0->user_begin());
     PN->replaceAllUsesWith(I0);
     PN->eraseFromParent();
   }

llvm/test/Transforms/SimplifyCFG/sink-tail-call-kind.ll

+; NOTE: Assertions have been autogenerated by utils/update_test_checks.py
+; RUN: opt -opaque-pointers -simplifycfg -sink-common-insts -S %s | FileCheck %s
+
+; Verify that calls to function @tailfn are sunk when tail call kinds
+; are compatible (and correct tail call kind is specified for a sunk
+; call). Test the full matrix (not applicable for musttail, as it is
+; always followed by ret):
+
+; |        | none    | tail    | notail |
+; |--------+---------+---------+--------|
+; | none   | sink    |         |        |
+; | tail   | sink    | sink    |        |
+; | notail | no sink | no sink | sink   |
+
+declare i32 @magic()
+declare void @tailfn()
+
+define dso_local void @tail_vs_none() {
+; CHECK-LABEL: @tail_vs_none(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @magic()
+; CHECK-NEXT:    call void @tailfn()
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i32 @magic()
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  tail call void @tailfn()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void @tailfn()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define dso_local void @none_vs_none() {
+; CHECK-LABEL: @none_vs_none(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @magic()
+; CHECK-NEXT:    call void @tailfn()
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i32 @magic()
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  call void @tailfn()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void @tailfn()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define dso_local void @tail_vs_tail() {
+; CHECK-LABEL: @tail_vs_tail(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @magic()
+; CHECK-NEXT:    tail call void @tailfn()
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i32 @magic()
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  tail call void @tailfn()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void @tailfn()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define dso_local void @no_vs_no() {
+; CHECK-LABEL: @no_vs_no(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @magic()
+; CHECK-NEXT:    notail call void @tailfn()
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i32 @magic()
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  notail call void @tailfn()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  notail call void @tailfn()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define dso_local void @no_vs_none() {
+; CHECK-LABEL: @no_vs_none(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @magic()
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[CALL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    notail call void @tailfn()
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    call void @tailfn()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i32 @magic()
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  notail call void @tailfn()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  call void @tailfn()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}
+
+define dso_local void @no_vs_tail() {
+; CHECK-LABEL: @no_vs_tail(
+; CHECK-NEXT:  entry:
+; CHECK-NEXT:    [[CALL:%.*]] = call i32 @magic()
+; CHECK-NEXT:    [[TOBOOL:%.*]] = icmp ne i32 [[CALL]], 0
+; CHECK-NEXT:    br i1 [[TOBOOL]], label [[IF_THEN:%.*]], label [[IF_ELSE:%.*]]
+; CHECK:       if.then:
+; CHECK-NEXT:    notail call void @tailfn()
+; CHECK-NEXT:    br label [[IF_END:%.*]]
+; CHECK:       if.else:
+; CHECK-NEXT:    tail call void @tailfn()
+; CHECK-NEXT:    br label [[IF_END]]
+; CHECK:       if.end:
+; CHECK-NEXT:    ret void
+;
+entry:
+  %call = call i32 @magic()
+  %tobool = icmp ne i32 %call, 0
+  br i1 %tobool, label %if.then, label %if.else
+
+if.then:                                          ; preds = %entry
+  notail call void @tailfn()
+  br label %if.end
+
+if.else:                                          ; preds = %entry
+  tail call void @tailfn()
+  br label %if.end
+
+if.end:                                           ; preds = %if.else, %if.then
+  ret void
+}