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 ↗

(On Diff #136179)

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 ↗

(On Diff #136179)

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

lib/CodeGen/CodeGenModule.h

469 ↗

(On Diff #136179)

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

[rjmccall]

include/clang/Driver/Options.td

1419 ↗

(On Diff #136179)

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 ↗

(On Diff #136179)

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!

cfe/trunk/include/clang/AST/Decl.h

 
 private:
   // FIXME: This can be packed into the bitfields in Decl.
   bool IsVariadic : 1;
   bool CapturesCXXThis : 1;
   bool BlockMissingReturnType : 1;
   bool IsConversionFromLambda : 1;
 
+  /// A bit that indicates this block is passed directly to a function as a
+  /// non-escaping parameter.
+  bool DoesNotEscape : 1;
+
   /// A new[]'d array of pointers to ParmVarDecls for the formal
   /// parameters of this function.  This is null if a prototype or if there are
   /// no formals.
   ParmVarDecl **ParamInfo = nullptr;
   unsigned NumParams = 0;
 
   Stmt *Body = nullptr;
   TypeSourceInfo *SignatureAsWritten = nullptr;
 
   const Capture *Captures = nullptr;
   unsigned NumCaptures = 0;
 
   unsigned ManglingNumber = 0;
   Decl *ManglingContextDecl = nullptr;
 
 protected:
   BlockDecl(DeclContext *DC, SourceLocation CaretLoc)
       : Decl(Block, DC, CaretLoc), DeclContext(Block), IsVariadic(false),
         CapturesCXXThis(false), BlockMissingReturnType(true),
-        IsConversionFromLambda(false) {}
+        IsConversionFromLambda(false), DoesNotEscape(false) {}
 
 public:
   static BlockDecl *Create(ASTContext &C, DeclContext *DC, SourceLocation L); 
   static BlockDecl *CreateDeserialized(ASTContext &C, unsigned ID);
   
   SourceLocation getCaretLocation() const { return getLocation(); }
 
   bool isVariadic() const { return IsVariadic; }
public:
 
   bool capturesCXXThis() const { return CapturesCXXThis; }
   bool blockMissingReturnType() const { return BlockMissingReturnType; }
   void setBlockMissingReturnType(bool val) { BlockMissingReturnType = val; }
 
   bool isConversionFromLambda() const { return IsConversionFromLambda; }
   void setIsConversionFromLambda(bool val) { IsConversionFromLambda = val; }
 
+  bool doesNotEscape() const { return DoesNotEscape; }
+  void setDoesNotEscape() { DoesNotEscape = true; }
+
   bool capturesVariable(const VarDecl *var) const;
 
   void setCaptures(ASTContext &Context, ArrayRef<Capture> Captures,
                    bool CapturesCXXThis);
 
    unsigned getBlockManglingNumber() const {
      return ManglingNumber;
    }

cfe/trunk/include/clang/Driver/Options.td

def fnoopenmp_relocatable_target : Flag<["-"], "fnoopenmp-relocatable-target">,
   Group<f_Group>, Flags<[CC1Option, NoArgumentUnused, HelpHidden]>;
 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]>;
 def fopenmp_cuda_mode : Flag<["-"], "fopenmp-cuda-mode">, Group<f_Group>, Flags<[CC1Option, NoArgumentUnused]>;
 def fno_openmp_cuda_mode : Flag<["-"], "fno-openmp-cuda-mode">, Group<f_Group>, Flags<[CC1Option, NoArgumentUnused]>;
 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_escaping_block_tail_calls : Flag<["-"], "fno-escaping-block-tail-calls">, Group<f_Group>, Flags<[CC1Option]>;
+def fescaping_block_tail_calls : Flag<["-"], "fescaping-block-tail-calls">, Group<f_Group>;
 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]>,

cfe/trunk/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(NoEscapingBlockTailCalls, 1, 0) ///< Do not emit tail calls from
+                                           ///< 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 by default or -f[no-]emulated-tls.

cfe/trunk/lib/CodeGen/CGCall.cpp

if (getLangOpts().OpenCLVersion <= 120) {
       // the work-group size specified to clEnqueueNDRangeKernel
       // (i.e. work groups are uniform).
       FuncAttrs.addAttribute("uniform-work-group-size",
                              llvm::toStringRef(CodeGenOpts.UniformWGSize));
     }
   }
 
   if (!AttrOnCallSite) {
-    bool DisableTailCalls =
-        CodeGenOpts.DisableTailCalls ||
-        (TargetDecl && (TargetDecl->hasAttr<DisableTailCallsAttr>() ||
-                        TargetDecl->hasAttr<AnyX86InterruptAttr>()));
+    bool DisableTailCalls = false;
+
+    if (CodeGenOpts.DisableTailCalls)
+      DisableTailCalls = true;
+    else if (TargetDecl) {
+      if (TargetDecl->hasAttr<DisableTailCallsAttr>() ||
+          TargetDecl->hasAttr<AnyX86InterruptAttr>())
+        DisableTailCalls = true;
+      else if (CodeGenOpts.NoEscapingBlockTailCalls) {
+        if (const auto *BD = dyn_cast<BlockDecl>(TargetDecl))
+          if (!BD->doesNotEscape())
+            DisableTailCalls = true;
+      }
+    }
+
     FuncAttrs.addAttribute("disable-tail-calls",
                            llvm::toStringRef(DisableTailCalls));
     GetCPUAndFeaturesAttributes(TargetDecl, FuncAttrs);
   }
 
   ClangToLLVMArgMapping IRFunctionArgs(getContext(), FI);
 
   QualType RetTy = FI.getReturnType();

cfe/trunk/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_fno_escaping_block_tail_calls,
+                   options::OPT_fescaping_block_tail_calls))
+    CmdArgs.push_back("-fno-escaping-block-tail-calls");
 
   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");
 

cfe/trunk/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.NoEscapingBlockTailCalls =
+      Args.hasArg(OPT_fno_escaping_block_tail_calls);
   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));

cfe/trunk/lib/Sema/SemaExpr.cpp

if (ArgIx < Args.size()) {
           FDecl && FDecl->hasAttr<CFAuditedTransferAttr>() &&
           (!Param || !Param->hasAttr<CFConsumedAttr>()))
         Arg = stripARCUnbridgedCast(Arg);
       else if (getLangOpts().ObjCAutoRefCount &&
                FDecl && FDecl->hasAttr<CFAuditedTransferAttr>() &&
                (!Param || !Param->hasAttr<CFConsumedAttr>()))
         CFAudited = true;
 
+      if (Proto->getExtParameterInfo(i).isNoEscape())
+        if (auto *BE = dyn_cast<BlockExpr>(Arg->IgnoreParenNoopCasts(Context)))
+          BE->getBlockDecl()->setDoesNotEscape();
+
       InitializedEntity Entity =
           Param ? InitializedEntity::InitializeParameter(Context, Param,
                                                          ProtoArgType)
                 : InitializedEntity::InitializeParameter(
                       Context, ProtoArgType, Proto->isParamConsumed(i));
 
       // Remember that parameter belongs to a CF audited API.
       if (CFAudited)

cfe/trunk/lib/Sema/SemaExprObjC.cpp

for (unsigned i = 0; i < NumNamedArgs; i++) {
     if (Args[i]->isTypeDependent())
       continue;
 
     Expr *argExpr = Args[i];
 
     ParmVarDecl *param = Method->parameters()[i];
     assert(argExpr && "CheckMessageArgumentTypes(): missing expression");
 
+    if (param->hasAttr<NoEscapeAttr>())
+      if (auto *BE = dyn_cast<BlockExpr>(
+              argExpr->IgnoreParenNoopCasts(Context)))
+        BE->getBlockDecl()->setDoesNotEscape();
+
     // Strip the unbridged-cast placeholder expression off unless it's
     // a consumed argument.
     if (argExpr->hasPlaceholderType(BuiltinType::ARCUnbridgedCast) &&
         !param->hasAttr<CFConsumedAttr>())
       argExpr = stripARCUnbridgedCast(argExpr);
 
     // If the parameter is __unknown_anytype, infer its type
     // from the argument.

cfe/trunk/lib/Sema/SemaPseudoObject.cpp

 }
 
 /// objective-c subscripting-specific  behavior for doing assignments.
 ExprResult
 ObjCSubscriptOpBuilder::buildAssignmentOperation(Scope *Sc,
                                                 SourceLocation opcLoc,
                                                 BinaryOperatorKind opcode,
                                                 Expr *LHS, Expr *RHS) {
+  assert(false);
   assert(BinaryOperator::isAssignmentOp(opcode));
   // There must be a method to do the Index'ed assignment.
   if (!findAtIndexSetter())
     return ExprError();
   
   // Verify that we can do a compound assignment.
   if (opcode != BO_Assign && !findAtIndexGetter())
     return ExprError();

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

+// RUN: %clang_cc1 -triple x86_64-apple-darwin -fblocks -fno-escaping-block-tail-calls -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: store i8* bitcast (void (i8*)* @[[TEST_BLOCK_INVOKE6:.*]] 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: define internal void @[[TEST_BLOCK_INVOKE6]]({{.*}}) #[[ENABLEATTR]] {
+
+// CHECK: attributes #[[ENABLEATTR]] = {{{.*}}"disable-tail-calls"="false"{{.*}}}
+// CHECK: attributes #[[DISABLEATTR]] = {{{.*}}"disable-tail-calls"="true"{{.*}}}
+
+typedef void (^BlockTy)(void);
+typedef void (*NoEscapeFnTy)(__attribute__((noescape)) BlockTy);
+
+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
+
+NoEscapeFnTy noescapefunc;
+
+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.
+
+  noescapefunc(^{ (void)a; }); // enable tail-call optimization.
+}

cfe/trunk/test/Driver/fno-escaping-block-tail-calls.c

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