[CGP] Be less conservative about tail-duplicating a ret to allow tail calls

[mkuper]

Summary

CGP tail-duplicates rets into blocks that end with a call that feed the ret. This puts the call in tail position, potentially allowing the DAG builder to lower it as a tail call. To avoid the tail-duplication in cases where we won't form the tail call, CGP tries to predict whether this is going to be possible, and avoid doing it when lowering as a tail call will definitely fail. However, it was being too conservative by always throwing away calls to functions with a signext/zeroext attribute on the return type.

Instead, we can use the exact same logic the builder itself uses to determine whether the attributes work out.

[hans]

lgtm, nice!

[iteratee]

lib/CodeGen/CodeGenPrepare.cpp

2008

It's kind of awkward to pass this as an output parameter and not use it.
Would it be better to make it a pointer argument with a default value of nullptr?

[mkuper]

lib/CodeGen/CodeGenPrepare.cpp

2008

I agree it's awkward, I'm just not sure the other way around (having a temporary in the callee, and then setting after a null check) is less awkward, overall. Same goes for other possible solutions (returning a pair, say).

In any case, I don't feel strongly about this, and I don't think the LLVM coding standards say anything concrete about this. So if you significantly prefer a pointer, let me know, and I'll change it.

[iteratee]

lib/CodeGen/CodeGenPrepare.cpp

2008

How about this:
Use a local variable in attributesPermitTailCall.
Use make_scope_exit to set the output parameter on exit only if it isn't null.

[mkuper]

lib/CodeGen/CodeGenPrepare.cpp

2008

That'll work too (I didn't even know we had make_scope_exit!), but it seems like overkill.

Another awkward option that doesn't involve make_scope_exit, as long as we're at it:

... bool *ADS = nullptr) {
  bool TempADS;
  bool &AllowDifferingSizes = ADS ? *ADS : TempADS;
...
}

[iteratee]

lib/CodeGen/CodeGenPrepare.cpp

2008

Go with that. That's the least awkward of all of them.

include/llvm/CodeGen/Analysis.h

 /// Test if the given instruction is in a position to be optimized
 /// with a tail-call. This roughly means that it's in a block with
 /// a return and there's nothing that needs to be scheduled
 /// between it and the return.
 ///
 /// This function only tests target-independent requirements.
 bool isInTailCallPosition(ImmutableCallSite CS, const TargetMachine &TM);
 
+/// Test if given that the input instruction is in the tail call position, if
+/// there is an attribute mismatch between the caller and the callee that will
+/// inhibit tail call optimizations.
+/// \p AllowDifferingSizes is an output parameter which, if forming a tail call
+/// is permitted, determines whether it's permitted only if the size of the
+/// caller's and callee's return types match exactly.
+bool attributesPermitTailCall(const Function *F, const Instruction *I,
+                              const ReturnInst *Ret,
+                              const TargetLoweringBase &TLI,
+                              bool &AllowDifferingSizes);
+
 /// Test if given that the input instruction is in the tail call position if the
 /// return type or any attributes of the function will inhibit tail call
 /// optimization.
-bool returnTypeIsEligibleForTailCall(const Function *F,
-                                     const Instruction *I,
+bool returnTypeIsEligibleForTailCall(const Function *F, const Instruction *I,
                                      const ReturnInst *Ret,
                                      const TargetLoweringBase &TLI);
 
 // True if GV can be left out of the object symbol table. This is the case
 // for linkonce_odr values whose address is not significant. While legal, it is
 // not normally profitable to omit them from the .o symbol table. Using this
 // analysis makes sense when the information can be passed down to the linker
 // or we are in LTO.
 bool canBeOmittedFromSymbolTable(const GlobalValue *GV);
 
 DenseMap<const MachineBasicBlock *, int>
 getFuncletMembership(const MachineFunction &MF);
 
 } // End llvm namespace
 
 #endif

lib/CodeGen/Analysis.cpp

for (BasicBlock::const_iterator BBI = std::prev(ExitBB->end(), 2);; --BBI) {
         return false;
     }
 
   const Function *F = ExitBB->getParent();
   return returnTypeIsEligibleForTailCall(
       F, I, Ret, *TM.getSubtargetImpl(*F)->getTargetLowering());
 }
 
-bool llvm::returnTypeIsEligibleForTailCall(const Function *F,
-                                           const Instruction *I,
-                                           const ReturnInst *Ret,
-                                           const TargetLoweringBase &TLI) {
-  // If the block ends with a void return or unreachable, it doesn't matter
-  // what the call's return type is.
-  if (!Ret || Ret->getNumOperands() == 0) return true;
-
-  // If the return value is undef, it doesn't matter what the call's
-  // return type is.
-  if (isa<UndefValue>(Ret->getOperand(0))) return true;
-
-  // Make sure the attributes attached to each return are compatible.
+bool llvm::attributesPermitTailCall(const Function *F, const Instruction *I,
+                                    const TargetLoweringBase &TLI,
+                                    bool &AllowDifferingSizes) {
   AttrBuilder CallerAttrs(F->getAttributes(),
                           AttributeSet::ReturnIndex);
   AttrBuilder CalleeAttrs(cast<CallInst>(I)->getAttributes(),
                           AttributeSet::ReturnIndex);
 
   // Noalias is completely benign as far as calling convention goes, it
   // shouldn't affect whether the call is a tail call.
   CallerAttrs = CallerAttrs.removeAttribute(Attribute::NoAlias);
   CalleeAttrs = CalleeAttrs.removeAttribute(Attribute::NoAlias);
 
-  bool AllowDifferingSizes = true;
+  AllowDifferingSizes = true;
   if (CallerAttrs.contains(Attribute::ZExt)) {
     if (!CalleeAttrs.contains(Attribute::ZExt))
       return false;
 
     AllowDifferingSizes = false;
     CallerAttrs.removeAttribute(Attribute::ZExt);
     CalleeAttrs.removeAttribute(Attribute::ZExt);
   } else if (CallerAttrs.contains(Attribute::SExt)) {
     if (!CalleeAttrs.contains(Attribute::SExt))
       return false;
 
     AllowDifferingSizes = false;
     CallerAttrs.removeAttribute(Attribute::SExt);
     CalleeAttrs.removeAttribute(Attribute::SExt);
   }
 
   // If they're still different, there's some facet we don't understand
   // (currently only "inreg", but in future who knows). It may be OK but the
   // only safe option is to reject the tail call.
-  if (CallerAttrs != CalleeAttrs)
+  return CallerAttrs == CalleeAttrs;
+}
+
+bool llvm::returnTypeIsEligibleForTailCall(const Function *F,
+                                           const Instruction *I,
+                                           const ReturnInst *Ret,
+                                           const TargetLoweringBase &TLI) {
+  // If the block ends with a void return or unreachable, it doesn't matter
+  // what the call's return type is.
+  if (!Ret || Ret->getNumOperands() == 0) return true;
+
+  // If the return value is undef, it doesn't matter what the call's
+  // return type is.
+  if (isa<UndefValue>(Ret->getOperand(0))) return true;
+
+  // Make sure the attributes attached to each return are compatible.
+  bool AllowDifferingSizes;
+  if (!attributesPermitTailCall(F, I, Ret, TLI, AllowDifferingSizes))
     return false;
 
   const Value *RetVal = Ret->getOperand(0), *CallVal = I;
   SmallVector<unsigned, 4> RetPath, CallPath;
   SmallVector<CompositeType *, 4> RetSubTypes, CallSubTypes;
 
   bool RetEmpty = !firstRealType(RetVal->getType(), RetSubTypes, RetPath);
   bool CallEmpty = !firstRealType(CallVal->getType(), CallSubTypes, CallPath);

lib/CodeGen/CodeGenPrepare.cpp

 #include "llvm/ADT/SmallSet.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/Analysis/InstructionSimplify.h"
 #include "llvm/Analysis/LoopInfo.h"
 #include "llvm/Analysis/TargetLibraryInfo.h"
 #include "llvm/Analysis/TargetTransformInfo.h"
 #include "llvm/Analysis/ValueTracking.h"
 #include "llvm/Analysis/MemoryBuiltins.h"
+#include "llvm/CodeGen/Analysis.h"
 #include "llvm/IR/CallSite.h"
 #include "llvm/IR/Constants.h"
 #include "llvm/IR/DataLayout.h"
 #include "llvm/IR/DerivedTypes.h"
 #include "llvm/IR/Dominators.h"
 #include "llvm/IR/Function.h"
 #include "llvm/IR/GetElementPtrTypeIterator.h"
 #include "llvm/IR/IRBuilder.h"
if (V) {
     PN = dyn_cast<PHINode>(V);
     if (!PN)
       return false;
   }
 
   if (PN && PN->getParent() != BB)
     return false;
 
-  // It's not safe to eliminate the sign / zero extension of the return value.
-  // See llvm::isInTailCallPosition().
-  const Function *F = BB->getParent();
-  AttributeSet CallerAttrs = F->getAttributes();
-  if (CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::ZExt) ||
-      CallerAttrs.hasAttribute(AttributeSet::ReturnIndex, Attribute::SExt))
-    return false;
-
   // Make sure there are no instructions between the PHI and return, or that the
   // return is the first instruction in the block.
   if (PN) {
     BasicBlock::iterator BI = BB->begin();
     do { ++BI; } while (isa<DbgInfoIntrinsic>(BI));
     if (&*BI == BCI)
       // Also skip over the bitcast.
       ++BI;
     if (&*BI != RetI)
       return false;
   } else {
     BasicBlock::iterator BI = BB->begin();
     while (isa<DbgInfoIntrinsic>(BI)) ++BI;
     if (&*BI != RetI)
       return false;
   }
 
   /// Only dup the ReturnInst if the CallInst is likely to be emitted as a tail
   /// call.
+  const Function *F = BB->getParent();
   SmallVector<CallInst*, 4> TailCalls;
+  bool AllowDifferingSizes;
   if (PN) {
     for (unsigned I = 0, E = PN->getNumIncomingValues(); I != E; ++I) {
       CallInst *CI = dyn_cast<CallInst>(PN->getIncomingValue(I));
       // Make sure the phi value is indeed produced by the tail call.
       if (CI && CI->hasOneUse() && CI->getParent() == PN->getIncomingBlock(I) &&
-          TLI->mayBeEmittedAsTailCall(CI))
+          TLI->mayBeEmittedAsTailCall(CI) &&
+          attributesPermitTailCall(F, CI, RetI, *TLI, AllowDifferingSizes))
         TailCalls.push_back(CI);
     }
   } else {
     SmallPtrSet<BasicBlock*, 4> VisitedBBs;
     for (pred_iterator PI = pred_begin(BB), PE = pred_end(BB); PI != PE; ++PI) {
       if (!VisitedBBs.insert(*PI).second)
         continue;
 
       BasicBlock::InstListType &InstList = (*PI)->getInstList();
       BasicBlock::InstListType::reverse_iterator RI = InstList.rbegin();
       BasicBlock::InstListType::reverse_iterator RE = InstList.rend();
       do { ++RI; } while (RI != RE && isa<DbgInfoIntrinsic>(&*RI));
       if (RI == RE)
         continue;
 
       CallInst *CI = dyn_cast<CallInst>(&*RI);
-      if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI))
+      if (CI && CI->use_empty() && TLI->mayBeEmittedAsTailCall(CI) &&
+          attributesPermitTailCall(F, CI, RetI, *TLI, AllowDifferingSizes))
         TailCalls.push_back(CI);
     }
   }
 
   bool Changed = false;
   for (unsigned i = 0, e = TailCalls.size(); i != e; ++i) {
     CallInst *CI = TailCalls[i];
     CallSite CS(CI);

test/CodeGen/X86/tailcall-cgp-dup.ll

if.else.i:                                        ; preds = %entry
   %call4.i = tail call i8* @bar(i8* undef) optsize
   br label %someThingWithValue.exit
 
 someThingWithValue.exit:                          ; preds = %if.else.i, %if.then.i
   %retval.0.in.i = phi i8* [ undef, %if.then.i ], [ %call4.i, %if.else.i ]
   %retval.0.i = bitcast i8* %retval.0.in.i to %0*
   ret %0* %retval.0.i
 }
+
+
+; Correctly handle zext returns.
+declare zeroext i1 @foo_i1()
+
+; CHECK-LABEL: zext_i1
+; CHECK: jmp _foo_i1
+define zeroext i1 @zext_i1(i1 %k) {
+entry:
+  br i1 %k, label %land.end, label %land.rhs
+
+land.rhs:                                         ; preds = %entry
+  %call1 = tail call zeroext i1 @foo_i1()
+  br label %land.end
+
+land.end:                                         ; preds = %entry, %land.rhs
+  %0 = phi i1 [ false, %entry ], [ %call1, %land.rhs ]
+  ret i1 %0
+}
+