Add an option to disable tail-call optimization for escaping blocks

[ahatanak]

Summary

This patch adds a command line option (-fdisable-tail-calls-esca
ping-blocks) that annotates escaping block invoke functions with attribute "disable-tail-calls". This is an option that helps users in debugging their code who spend a lot of time trying to figure out where a block came from.

The user who is asking for this command line option does not want to disable tail-call optimization for non-escaping blocks. For example, in the following code, we should not disable tail-call optimization for the block that is directly passed to function "noescapefunc":

void foo3(void);

void foo1() {
  noescapefunc(^{ foo3(); }); // do not disable tail-call.
  BlockTy b = ^{ foo3(); }; // disable tail-call.
  noescapefunc(b);
}

Ideally, I think we want to avoid disabling tail-call optimization for block "b" too, as it doesn't escape. However, this patch doesn't do anything to avoid disabling tail-call optimization for the block, since that would require a more complex analysis.

rdar://problem/35758207

[rjmccall]

Can you explain the rationale for limiting this to escaping blocks in more depth? That seems like an extremely orthogonal limitation; the user might be thinking about a very specific block and not really considering this in general.

[ahatanak]

This is limited to escaping blocks because disabling tail-call optimizations for all blocks might impact performance. The user is claiming that non-escaping blocks are often used in areas that are performance-sensitive (for example, dispatch_sync() and -[NSArray enumerateObjectsUsingBlock:] in a tight loop), so disabling tail-call optimization indiscriminately can cause performance degradation (and clients might decide not to use the command line option because of that).

[rjmccall]

TCO is a pretty neglible optimization; its primary advantage is slightly better locality for stack memory.

I guess the more compelling argument is that non-escaping blocks can by definition only be executed with the original block-creating code still active, so someone debugging a crash downstack of a TCO'ed block will still have a pretty strong piece of context to start from. An escaping block, meanwhile, could be executed by anything, so TCO'ing it might leave the stack trace with absolutely no hint about what's happened.

Alright, I can accept that.

include/clang/Driver/Options.td

1419

These are pretty unidiomatic option names. I would suggest one of these:

• [fixed]-fescaping-block-tail-calls[/fixed] (the default) and [fixed]-fno-escaping-block-tail-calls[/fixed]
• [fixed]-enable-escaping-block-tail-calls[/fixed] (the default) and [fixed]-disable-escaping-block-tail-calls[/fixed]

include/clang/Frontend/CodeGenOptions.def

66

"from" instead of "for" would be clearer, I think.

lib/CodeGen/CodeGenModule.h

469

This seems like something that Sema should store on the BlockDecl.

[rjmccall]

include/clang/Driver/Options.td

1419

Wow, this is not even close to Phabricator markup, I don't know what I was thinking.

[ahatanak]

Address review comments.

include/clang/Driver/Options.td

1419

I chose the first option "-fno-escaping-block-tail-calls/-fescaping-block-tail-calls".

[rjmccall]

lib/Sema/SemaExpr.cpp

4846 ↗

(On Diff #136580)

Can this be based on the noescape parameter bit on the function type?

[ahatanak]

lib/Sema/SemaExpr.cpp

4846 ↗

(On Diff #136580)

Oh that's right. It should be able to set the DoesNotEscape bit of a block when it's passed to an indirect function call. I added an IRGen test case that checks tail-call is enabled in such cases.

[ahatanak]

Check the function prototype's noescape bit.

[rjmccall]

Alright, this looks good to me.

lib/Sema/SemaExpr.cpp

4846 ↗

(On Diff #136580)

Thanks!

include/clang/AST/DeclObjC.h

public:
 
   /// \brief Sets the method's parameters and selector source locations.
   /// If the method is implicit (not coming from source) \p SelLocs is
   /// ignored.
   void setMethodParams(ASTContext &C,
                        ArrayRef<ParmVarDecl*> Params,
                        ArrayRef<SourceLocation> SelLocs = llvm::None);
 
+  bool isNoEscapeParam(unsigned Idx) const;
+
   // Iterator access to parameter types.
   struct GetTypeFn {
     QualType operator()(const ParmVarDecl *PD) const { return PD->getType(); }
   };
 
   using param_type_iterator =
       llvm::mapped_iterator<param_const_iterator, GetTypeFn>;
 

include/clang/AST/Type.h

QualType getParamType(unsigned i) const {
     assert(i < NumParams && "invalid parameter index");
     return param_type_begin()[i];
   }
 
   ArrayRef<QualType> getParamTypes() const {
     return llvm::makeArrayRef(param_type_begin(), param_type_end());
   }
 
+  bool isNoEscapeParam(unsigned Idx) const;
+
   ExtProtoInfo getExtProtoInfo() const {
     ExtProtoInfo EPI;
     EPI.ExtInfo = getExtInfo();
     EPI.Variadic = isVariadic();
     EPI.HasTrailingReturn = hasTrailingReturn();
     EPI.ExceptionSpec.Type = getExceptionSpecType();
     EPI.TypeQuals = static_cast<unsigned char>(getTypeQuals());
     EPI.RefQualifier = getRefQualifier();

include/clang/Driver/Options.td

 def fnoopenmp_relocatable_target : Flag<["-"], "fnoopenmp-relocatable-target">, Group<f_Group>, Flags<[CC1Option, NoArgumentUnused]>,
   HelpText<"Do not compile OpenMP target code as relocatable.">;
 def fopenmp_simd : Flag<["-"], "fopenmp-simd">, Group<f_Group>, Flags<[CC1Option, NoArgumentUnused]>,
   HelpText<"Emit OpenMP code only for SIMD-based constructs.">;
 def fno_openmp_simd : Flag<["-"], "fno-openmp-simd">, Group<f_Group>, Flags<[CC1Option, NoArgumentUnused]>,
   HelpText<"Disable OpenMP code for SIMD-based constructs.">;
 def fno_optimize_sibling_calls : Flag<["-"], "fno-optimize-sibling-calls">, Group<f_Group>;
 def foptimize_sibling_calls : Flag<["-"], "foptimize-sibling-calls">, Group<f_Group>;
+def fno_disable_tail_calls_escaping_blocks : Flag<["-"], "fno-disable-tail-calls-escaping-blocks">, Group<f_Group>, Flags<[CC1Option]>;
+def fdisable_tail_calls_escaping_blocks : Flag<["-"], "fdisable-tail-calls-escaping-blocks">, Group<f_Group>, Flags<[CC1Option]>;
 def force__cpusubtype__ALL : Flag<["-"], "force_cpusubtype_ALL">;
 def force__flat__namespace : Flag<["-"], "force_flat_namespace">;
 def force__load : Separate<["-"], "force_load">;
 def force_addr : Joined<["-"], "fforce-addr">, Group<clang_ignored_f_Group>;
 def foutput_class_dir_EQ : Joined<["-"], "foutput-class-dir=">, Group<f_Group>;
 def fpack_struct : Flag<["-"], "fpack-struct">, Group<f_Group>;
 def fno_pack_struct : Flag<["-"], "fno-pack-struct">, Group<f_Group>;
 def fpack_struct_EQ : Joined<["-"], "fpack-struct=">, Group<f_Group>, Flags<[CC1Option]>,

include/clang/Frontend/CodeGenOptions.def

 CODEGENOPT(DisableLifetimeMarkers, 1, 0) ///< Don't emit any lifetime markers
 CODEGENOPT(DisableO0ImplyOptNone , 1, 0) ///< Don't annonate function with optnone at O0
 CODEGENOPT(ExperimentalNewPassManager, 1, 0) ///< Enables the new, experimental
                                              ///< pass manager.
 CODEGENOPT(DebugPassManager, 1, 0) ///< Prints debug information for the new
                                    ///< pass manager.
 CODEGENOPT(DisableRedZone    , 1, 0) ///< Set when -mno-red-zone is enabled.
 CODEGENOPT(DisableTailCalls  , 1, 0) ///< Do not emit tail calls.
+CODEGENOPT(DisableTailCallsEscapingBlocks, 1, 0) ///< Do not emit tail calls for
+                                                 ///< escaping blocks.
 CODEGENOPT(EmitDeclMetadata  , 1, 0) ///< Emit special metadata indicating what
                                      ///< Decl* various IR entities came from.
                                      ///< Only useful when running CodeGen as a
                                      ///< subroutine.
 CODEGENOPT(EmitGcovArcs      , 1, 0) ///< Emit coverage data files, aka. GCDA.
 CODEGENOPT(EmitGcovNotes     , 1, 0) ///< Emit coverage "notes" files, aka GCNO.
 CODEGENOPT(EmitOpenCLArgMetadata , 1, 0) ///< Emit OpenCL kernel arg metadata.
 CODEGENOPT(EmulatedTLS       , 1, 0) ///< Set when -femulated-tls is enabled.

lib/AST/DeclObjC.cpp

void ObjCMethodDecl::setMethodParams(ASTContext &C,
   SelLocsKind = hasStandardSelectorLocs(getSelector(), SelLocs, Params,
                                         DeclEndLoc);
   if (SelLocsKind != SelLoc_NonStandard)
     return setParamsAndSelLocs(C, Params, llvm::None);
 
   setParamsAndSelLocs(C, Params, SelLocs);
 }
 
+bool ObjCMethodDecl::isNoEscapeParam(unsigned Idx) const {
+  assert(Idx < param_size() && "Index too large");
+  return (*(param_begin() + Idx))->hasAttr<NoEscapeAttr>();
+}
+
 /// \brief A definition will return its interface declaration.
 /// An interface declaration will return its definition.
 /// Otherwise it will return itself.
 ObjCMethodDecl *ObjCMethodDecl::getNextRedeclarationImpl() {
   ASTContext &Ctx = getASTContext();
   ObjCMethodDecl *Redecl = nullptr;
   if (HasRedeclaration)
     Redecl = const_cast<ObjCMethodDecl*>(Ctx.getObjCMethodRedeclaration(this));

lib/AST/Type.cpp

FunctionProtoType::FunctionProtoType(QualType result, ArrayRef<QualType> params,
   if (epi.ExtParameterInfos) {
     ExtParameterInfo *extParamInfos =
       const_cast<ExtParameterInfo *>(getExtParameterInfosBuffer());
     for (unsigned i = 0; i != NumParams; ++i)
       extParamInfos[i] = epi.ExtParameterInfos[i];
   }
 }
 
+bool FunctionProtoType::isNoEscapeParam(unsigned Idx) const {
+  return getExtParameterInfo(Idx).isNoEscape();
+}
+
 bool FunctionProtoType::hasDependentExceptionSpec() const {
   if (Expr *NE = getNoexceptExpr())
     return NE->isValueDependent();
   for (QualType ET : exceptions())
     // A pack expansion with a non-dependent pattern is still dependent,
     // because we don't know whether the pattern is in the exception spec
     // or not (that depends on whether the pack has 0 expansions).
     if (ET->isDependentType() || ET->getAs<PackExpansionType>())

lib/CodeGen/CGCall.cpp

if (TargetDecl && CodeGenOpts.NoPLT) {
     if (auto *Fn = dyn_cast<FunctionDecl>(TargetDecl)) {
       if (!Fn->isDefined() && !AttrOnCallSite) {
         FuncAttrs.addAttribute(llvm::Attribute::NonLazyBind);
       }
     }
   }
 
   if (!AttrOnCallSite) {
-    bool DisableTailCalls =
-        CodeGenOpts.DisableTailCalls ||
-        (TargetDecl && (TargetDecl->hasAttr<DisableTailCallsAttr>() ||
-                        TargetDecl->hasAttr<AnyX86InterruptAttr>()));
+    bool DisableTailCalls = CodeGenOpts.DisableTailCalls;
+
+    if (TargetDecl &&
+        ((TargetDecl->hasAttr<DisableTailCallsAttr>() ||
+          TargetDecl->hasAttr<AnyX86InterruptAttr>()) ||
+         (CodeGenOpts.DisableTailCallsEscapingBlocks &&
+          isEscapingBlock(TargetDecl))))
+      DisableTailCalls = true;
+
     FuncAttrs.addAttribute("disable-tail-calls",
                            llvm::toStringRef(DisableTailCalls));
     GetCPUAndFeaturesAttributes(TargetDecl, FuncAttrs);
   }
 
   ClangToLLVMArgMapping IRFunctionArgs(getContext(), FI);
 
   QualType RetTy = FI.getReturnType();

lib/CodeGen/CodeGenFunction.h

void EmitCallArgs(CallArgList &Args, const T *CallArgTypeInfo,
     assert((ParamsToSkip == 0 || CallArgTypeInfo) &&
            "Can't skip parameters if type info is not provided");
     if (CallArgTypeInfo) {
 #ifndef NDEBUG
       bool isGenericMethod = isObjCMethodWithTypeParams(CallArgTypeInfo);
 #endif
 
       // First, use the argument types that the type info knows about
+      unsigned Idx = ParamsToSkip;
+
       for (auto I = CallArgTypeInfo->param_type_begin() + ParamsToSkip,
                 E = CallArgTypeInfo->param_type_end();
-           I != E; ++I, ++Arg) {
+           I != E; ++I, ++Arg, ++Idx) {
         assert(Arg != ArgRange.end() && "Running over edge of argument list!");
         assert((isGenericMethod ||
                 ((*I)->isVariablyModifiedType() ||
                  (*I).getNonReferenceType()->isObjCRetainableType() ||
                  getContext()
                          .getCanonicalType((*I).getNonReferenceType())
                          .getTypePtr() ==
                      getContext()
                          .getCanonicalType((*Arg)->getType())
                          .getTypePtr())) &&
                "type mismatch in call argument!");
         ArgTypes.push_back(*I);
+        if (CGM.getCodeGenOpts().DisableTailCallsEscapingBlocks &&
+            CallArgTypeInfo->isNoEscapeParam(Idx))
+          if (const auto *BE = dyn_cast<BlockExpr>(
+                  (*Arg)->IgnoreParenNoopCasts(getContext())))
+            CGM.addNoEscapeBlock(BE->getBlockDecl());
       }
     }
 
     // Either we've emitted all the call args, or we have a call to variadic
     // function.
     assert((Arg == ArgRange.end() || !CallArgTypeInfo ||
             CallArgTypeInfo->isVariadic()) &&
            "Extra arguments in non-variadic function!");

lib/CodeGen/CodeGenModule.h

private:
   /// Map used to be sure we don't emit the same CompoundLiteral twice.
   llvm::DenseMap<const CompoundLiteralExpr *, llvm::GlobalVariable *>
       EmittedCompoundLiterals;
 
   /// Map of the global blocks we've emitted, so that we don't have to re-emit
   /// them if the constexpr evaluator gets aggressive.
   llvm::DenseMap<const BlockExpr *, llvm::Constant *> EmittedGlobalBlocks;
 
+  llvm::SmallPtrSet<const BlockDecl *, 1> NoEscapeBlocks;
+
   /// @name Cache for Blocks Runtime Globals
   /// @{
 
   llvm::Constant *NSConcreteGlobalBlock = nullptr;
   llvm::Constant *NSConcreteStackBlock = nullptr;
 
   llvm::Constant *BlockObjectAssign = nullptr;
   llvm::Constant *BlockObjectDispose = nullptr;
CGCUDARuntime &getCUDARuntime() {
     return *CUDARuntime;
   }
 
   ObjCEntrypoints &getObjCEntrypoints() const {
     assert(ObjCData != nullptr);
     return *ObjCData;
   }
 
+  bool isEscapingBlock(const Decl *D) {
+    if (const auto *BD = dyn_cast<BlockDecl>(D))
+      return !NoEscapeBlocks.count(BD);
+    return false;
+  }
+
+  void addNoEscapeBlock(const BlockDecl *BD) {
+    NoEscapeBlocks.insert(BD);
+  }
+
   // Version checking function, used to implement ObjC's @available:
   // i32 @__isOSVersionAtLeast(i32, i32, i32)
   llvm::Constant *IsOSVersionAtLeastFn = nullptr;
 
   InstrProfStats &getPGOStats() { return PGOStats; }
   llvm::IndexedInstrProfReader *getPGOReader() const { return PGOReader.get(); }
 
   CoverageMappingModuleGen *getCoverageMapping() const {

lib/Driver/ToolChains/Clang.cpp

if (Args.hasFlag(options::OPT_fallow_editor_placeholders,
     CmdArgs.push_back("-fallow-editor-placeholders");
   if (Args.hasFlag(options::OPT_fstrict_vtable_pointers,
                    options::OPT_fno_strict_vtable_pointers,
                    false))
     CmdArgs.push_back("-fstrict-vtable-pointers");
   if (!Args.hasFlag(options::OPT_foptimize_sibling_calls,
                     options::OPT_fno_optimize_sibling_calls))
     CmdArgs.push_back("-mdisable-tail-calls");
+  if (Args.hasFlag(options::OPT_fdisable_tail_calls_escaping_blocks,
+                   options::OPT_fno_disable_tail_calls_escaping_blocks))
+    CmdArgs.push_back("-fdisable-tail-calls-escaping-blocks");
 
   Args.AddLastArg(CmdArgs, options::OPT_ffine_grained_bitfield_accesses,
                   options::OPT_fno_fine_grained_bitfield_accesses);
 
   // Handle segmented stacks.
   if (Args.hasArg(options::OPT_fsplit_stack))
     CmdArgs.push_back("-split-stacks");
 

lib/Frontend/CompilerInvocation.cpp

static bool ParseCodeGenArgs(CodeGenOptions &Opts, ArgList &Args, InputKind IK,
   Opts.CXXCtorDtorAliases = Args.hasArg(OPT_mconstructor_aliases);
   Opts.CodeModel = getCodeModel(Args, Diags);
   Opts.DebugPass = Args.getLastArgValue(OPT_mdebug_pass);
   Opts.DisableFPElim =
       (Args.hasArg(OPT_mdisable_fp_elim) || Args.hasArg(OPT_pg));
   Opts.DisableFree = Args.hasArg(OPT_disable_free);
   Opts.DiscardValueNames = Args.hasArg(OPT_discard_value_names);
   Opts.DisableTailCalls = Args.hasArg(OPT_mdisable_tail_calls);
+  Opts.DisableTailCallsEscapingBlocks =
+      Args.hasArg(OPT_fdisable_tail_calls_escaping_blocks);
   Opts.FloatABI = Args.getLastArgValue(OPT_mfloat_abi);
   Opts.LessPreciseFPMAD = Args.hasArg(OPT_cl_mad_enable) ||
                           Args.hasArg(OPT_cl_unsafe_math_optimizations) ||
                           Args.hasArg(OPT_cl_fast_relaxed_math);
   Opts.LimitFloatPrecision = Args.getLastArgValue(OPT_mlimit_float_precision);
   Opts.NoInfsFPMath = (Args.hasArg(OPT_menable_no_infinities) ||
                        Args.hasArg(OPT_cl_finite_math_only) ||
                        Args.hasArg(OPT_cl_fast_relaxed_math));

test/CodeGenObjC/disable-tail-call-escaping-block.m

+// RUN: %clang_cc1 -triple x86_64-apple-darwin -fblocks -fdisable-tail-calls-escaping-blocks -emit-llvm -o - %s | FileCheck %s
+
+// CHECK-LABEL: define void @test(
+// CHECK: store i8* bitcast (void (i8*)* @[[TEST_BLOCK_INVOKE0:.*]] to i8*)
+// CHECK: store i8* bitcast (void (i8*)* @[[TEST_BLOCK_INVOKE1:.*]] to i8*)
+// CHECK: store i8* bitcast (void (i8*)* @[[TEST_BLOCK_INVOKE2:.*]] to i8*)
+// CHECK: store i8* bitcast (void (i8*)* @[[TEST_BLOCK_INVOKE3:.*]] to i8*)
+// CHECK: store i8* bitcast (void (i8*)* @[[TEST_BLOCK_INVOKE4:.*]] to i8*)
+// CHECK: store i8* bitcast (void (i8*)* @[[TEST_BLOCK_INVOKE5:.*]] to i8*)
+
+// CHECK: define internal void @[[TEST_BLOCK_INVOKE0]]({{.*}}) #[[DISABLEATTR:.*]] {
+// CHECK: define internal void @[[TEST_BLOCK_INVOKE1]]({{.*}}) #[[ENABLEATTR:.*]] {
+// CHECK: define internal void @[[TEST_BLOCK_INVOKE2]]({{.*}}) #[[DISABLEATTR]] {
+// CHECK: define internal void @[[TEST_BLOCK_INVOKE3]]({{.*}}) #[[DISABLEATTR]] {
+// CHECK: define internal void @[[TEST_BLOCK_INVOKE4]]({{.*}}) #[[ENABLEATTR]] {
+// CHECK: define internal void @[[TEST_BLOCK_INVOKE5]]({{.*}}) #[[DISABLEATTR]] {
+
+// CHECK: attributes #[[ENABLEATTR]] = {{{.*}}"disable-tail-calls"="false"{{.*}}}
+// CHECK: attributes #[[DISABLEATTR]] = {{{.*}}"disable-tail-calls"="true"{{.*}}}
+
+typedef void (^BlockTy)(void);
+
+void callee0(__attribute__((noescape)) BlockTy);
+void callee1(BlockTy);
+
+__attribute__((objc_root_class))
+@interface C0
+-(void)m0:(__attribute__((noescape)) BlockTy)p;
+-(void)m1:(BlockTy)p;
+@end
+
+@implementation C0
+-(void)m0:(__attribute__((noescape)) BlockTy)p {}
+-(void)m1:(BlockTy)p {}
+@end
+
+void test(id a, C0 *c0) {
+  BlockTy b0 = ^{ (void)a; }; // disable tail-call optimization.
+  callee0(b0);
+  callee0(^{ (void)a; }); // enable tail-call optimization.
+  callee1(^{ (void)a; }); // disable tail-call optimization.
+
+  BlockTy b1 = ^{ (void)a; }; // disable tail-call optimization.
+  [c0 m0:b1];
+  [c0 m0:^{ (void)a; }]; // enable tail-call optimization.
+  [c0 m1:^{ (void)a; }]; // disable tail-call optimization.
+}

test/Driver/fdisable-tail-calls-escaping-blocks.c

+// RUN: %clang -### %s -fno-disable-tail-calls-escaping-blocks -fdisable-tail-calls-escaping-blocks 2> %t
+// RUN: FileCheck --check-prefix=CHECK-DISABLE < %t %s
+// CHECK-DISABLE: "-fdisable-tail-calls-escaping-blocks"
+
+// RUN: %clang -### %s -fdisable-tail-calls-escaping-blocks -fno-disable-tail-calls-escaping-blocks 2> %t
+// RUN: FileCheck --check-prefix=CHECK-NO-DISABLE < %t %s
+// CHECK-NO-DISABLE-NOT: "-fdisable-tail-calls-escaping-blocks"