[FaultMaps] Let the frontend pre-select implicit null check candidates.

[sanjoy]

Summary

This change introduces a !make.implicit metadata that allows the
frontend to pre-select the set of explicit null checks that will be
considered for transformation into implicit null checks.

The reason for not using profiling data instead of !make.implicit is
explained in the change to FaultMaps.rst.

[JosephTremoulet]

Some questions about the direction:

1 - How early/late do you expect the frontend to insert these annotations? If it's early, isn't there a very real chance that the annotations will get dropped/misplaced during optimization? Conversely, if it's late, isn't it going to be difficult for the frontend to correlate the IR to the side information you're expecting it to use?
[I understand it won't be a correctness issue either way, but the performance issue seems real.]

2 - I anticipate that for LLILC we'll want this to be profile-driven -- we don't have healing, but typically (in other .Net JITs) use machine faults anyway for the null checks that are implicit in MSIL instructions because we're comfortable assuming that their failure rate is effectively zero; so I'd expect that our reader will annotate branch profiles with that assumption, that optimizations will make a reasonable effort to propagate the branch profiles (please correct me if that's a bad assumption), and that we'll then want to consume that information for the implicit null check optimization. It seems like that approach will be perfectly compatible with this change if we simply add a pass that LLILC can opt into / you can opt out of that runs just before implicit null check optimization which annotates super-cold checks as !make-implicit. So my questions are
2a - Does that approach sound feasible to you?
2b - Was your change of direction simply because you think you'll get better performance this way, or are there any issues with using profile information that you're aware of that we'll run into if we add a pass like I just described?

[Of course, if metadata annotations are more robust than I'm imagining, #2 is a non-issue and we can just annotate branches appropriately when we initially generate LLVM IR.]

The code itself looks good to me given the direction.

[sanjoy]

This change tries to be conservative towards making null checks
implicit, the assumption being that it is okay to fail to make some
cold null checks implicit but it is not okay to accidentally make a
hot (or even lukewarm) null check implicit.

1 - How early/late do you expect the frontend to insert these annotations? If it's early, isn't there a very real chance that the annotations will get dropped/misplaced during optimization? Conversely, if it's late, isn't it going to be difficult for the frontend to correlate the IR to the side information you're expecting it to use?

Our frontend inserts these early (during IR generation) so there is a
possibility that the metadata will get dropped, and we will miss the
optimization. However, any metadata based annotation scheme faces
this same problem, and it can be fixed on a case by case basis as we
encounter optimizations that drop this metadata unnecessarily. In
practice, I think it will be adequate to add a second clause to places
within LLVM that touch the !prof metadata.

I'm also not opposed to having an '-aggressive' switch that bypasses
the check for !make.implicit metadata.

2 - I anticipate that for LLILC we'll want this to be profile-driven -- we don't have healing, but typically (in other .Net JITs) use machine faults anyway for the null checks that are implicit in MSIL instructions because we're comfortable assuming that their failure rate is effectively zero; so I'd expect that our reader will annotate branch profiles with that assumption,
that optimizations will make a reasonable effort to propagate the branch profiles (please correct me if that's a bad assumption),

I think that is reasonable. Moreover, I don't think you'll have any
trouble fixing and upstreaming fixes to optimization passes to make
them better preserve branch profiles (if you find any issues).

and that we'll then want to consume that information for the implicit null check optimization. It seems like that approach will be perfectly compatible with this change if we simply add a pass that LLILC can opt into / you can opt out of that runs just before implicit null check optimization which annotates super-cold checks as !make-implicit. So my questions are

2a - Does that approach sound feasible to you?

Yes. We can also factor the logic that selects null checks that are
to be made implicit into a separate pass if it gets too complicated.

2b - Was your change of direction simply because you think you'll get better performance this way, or are there any issues with using profile information that you're aware of that we'll run into if we add a pass like I just described?

So for us, coldness of a branch is necessary but not sufficient to
guarantee that making a null check implicit will be profitable. In
other words, even if LLVM is able to prove (I don't know if it can do
this currently) that a certain null check is very cold, it may not be
safe to make the check implicit if the failing path does not have code
to heal the null check. This is why we needed something stronger than
branch profiling data.

• Sanjoy

[JosephTremoulet]

Sounds good to me. I like the idea of an '-aggressive' switch; without it, the profile-driven pre-pass would either need to redundantly pattern-match to determine which compares precede dereferences or needlessly annotate irrelevant compares with !make-implicit.

llvm/trunk/docs/FaultMaps.rst

 
 The ``ImplicitNullChecks`` pass transforms explicit control flow for
 checking if a pointer is ``null``, like:
 
 .. code-block:: llvm
 
     %ptr = call i32* @get_ptr()
     %ptr_is_null = icmp i32* %ptr, null
-    br i1 %ptr_is_null, label %is_null, label %not_null
+    br i1 %ptr_is_null, label %is_null, label %not_null, !make.implicit !0
   
   not_null:
     %t = load i32, i32* %ptr
     br label %do_something_with_t
     
   is_null:
     call void @HFC()
     unreachable
   
+  !0 = !{}
+
 to control flow implicit in the instruction loading or storing through
 the pointer being null checked:
 
 .. code-block:: llvm
 
     %ptr = call i32* @get_ptr()
     %t = load i32, i32* %ptr  ;; handler-pc = label %is_null
     br label %do_something_with_t
     
   is_null:
     call void @HFC()
     unreachable
 
 This transform happens at the ``MachineInstr`` level, not the LLVM IR
 level (so the above example is only representative, not literal).  The
 ``ImplicitNullChecks`` pass runs during codegen, if
 ``-enable-implicit-null-checks`` is passed to ``llc``.
 
 The ``ImplicitNullChecks`` pass adds entries to the
 ``__llvm_faultmaps`` section described above as needed.
+
+``make.implicit`` metadata
+--------------------------
+
+Making null checks implicit is an aggressive optimization, and it can
+be a net performance pessimization if too many memory operations end
+up faulting because of it.  A language runtime typically needs to
+ensure that only a negligible number of implicit null checks actually
+fault once the application has reached a steady state.  A standard way
+of doing this is by healing failed implicit null checks into explicit
+null checks via code patching or recompilation.  It follows that there
+are two requirements an explicit null check needs to satisfy for it to
+be profitable to convert it to an implicit null check:
+
+  1. The case where the pointer is actually null (i.e. the "failing"
+     case) is extremely rare.
+
+  2. The failing path heals the implicit null check into an explicit
+     null check so that the application does not repeatedly page
+     fault.
+
+The frontend is expected to mark branches that satisfy (1) and (2)
+using a ``!make.implicit`` metadata node (the actual content of the
+metadata node is ignored).  Only branches that are marked with
+``!make.implicit`` metadata are considered as candidates for
+conversion into implicit null checks.
+
+(Note that while we could deal with (1) using profiling data, dealing
+with (2) requires some information not present in branch profiles.)

llvm/trunk/lib/CodeGen/ImplicitNullChecks.cpp

 
 /// Analyze MBB to check if its terminating branch can be turned into an
 /// implicit null check.  If yes, append a description of the said null check to
 /// NullCheckList and return true, else return false.
 bool ImplicitNullChecks::analyzeBlockForNullChecks(
     MachineBasicBlock &MBB, SmallVectorImpl<NullCheck> &NullCheckList) {
   typedef TargetInstrInfo::MachineBranchPredicate MachineBranchPredicate;
 
+  MDNode *BranchMD =
+      MBB.getBasicBlock()
+          ? MBB.getBasicBlock()->getTerminator()->getMetadata("make.implicit")
+          : nullptr;
+  if (!BranchMD)
+    return false;
+
   MachineBranchPredicate MBP;
 
   if (TII->AnalyzeBranchPredicate(MBB, MBP, true))
     return false;
 
   // Is the predicate comparing an integer to zero?
   if (!(MBP.LHS.isReg() && MBP.RHS.isImm() && MBP.RHS.getImm() == 0 &&
         (MBP.Predicate == MachineBranchPredicate::PRED_NE ||

llvm/trunk/test/CodeGen/X86/implicit-null-check-negative.ll

 ; RUN: llc -mtriple=x86_64-apple-macosx -O3 -debug-only=faultmaps -enable-implicit-null-checks < %s 2>&1 | FileCheck %s
 ; REQUIRES: asserts
 
 ; List cases where we should *not* be emitting implicit null checks.
 
 ; CHECK-NOT: Fault Map Output
 
 define i32 @imp_null_check_load(i32* %x, i32* %y) {
  entry:
   %c = icmp eq i32* %x, null
 ; It isn't legal to move the load from %x from "not_null" to here --
 ; the store to %y could be aliasing it.
-  br i1 %c, label %is_null, label %not_null
+  br i1 %c, label %is_null, label %not_null, !make.implicit !0
 
  is_null:
   ret i32 42
 
  not_null:
   store i32 0, i32* %y
   %t = load i32, i32* %x
   ret i32 %t
 }
 
 define i32 @imp_null_check_gep_load(i32* %x) {
  entry:
   %c = icmp eq i32* %x, null
-  br i1 %c, label %is_null, label %not_null
+  br i1 %c, label %is_null, label %not_null, !make.implicit !0
 
  is_null:
   ret i32 42
 
  not_null:
 ; null + 5000 * sizeof(i32) lies outside the null page and hence the
 ; load to %t cannot be assumed to be reliably faulting.
   %x.gep = getelementptr i32, i32* %x, i32 5000
   %t = load i32, i32* %x.gep
   ret i32 %t
 }
+
+define i32 @imp_null_check_load_no_md(i32* %x) {
+; This is fine, except it is missing the !make.implicit metadata.
+ entry:
+  %c = icmp eq i32* %x, null
+  br i1 %c, label %is_null, label %not_null
+
+ is_null:
+  ret i32 42
+
+ not_null:
+  %t = load i32, i32* %x
+  ret i32 %t
+}
+
+!0 = !{}

llvm/trunk/test/CodeGen/X86/implicit-null-check.ll

 ; CHECK: movl (%rdi), %eax
 ; CHECK: retq
 ; CHECK: Ltmp0:
 ; CHECK: movl $42, %eax
 ; CHECK: retq
 
  entry:
   %c = icmp eq i32* %x, null
-  br i1 %c, label %is_null, label %not_null
+  br i1 %c, label %is_null, label %not_null, !make.implicit !0
 
  is_null:
   ret i32 42
 
  not_null:
   %t = load i32, i32* %x
   ret i32 %t
 }
 
 define i32 @imp_null_check_gep_load(i32* %x) {
 ; CHECK-LABEL: _imp_null_check_gep_load:
 ; CHECK: Ltmp3:
 ; CHECK: movl 128(%rdi), %eax
 ; CHECK: retq
 ; CHECK: Ltmp2:
 ; CHECK: movl $42, %eax
 ; CHECK: retq
 
  entry:
   %c = icmp eq i32* %x, null
-  br i1 %c, label %is_null, label %not_null
+  br i1 %c, label %is_null, label %not_null, !make.implicit !0
 
  is_null:
   ret i32 42
 
  not_null:
   %x.gep = getelementptr i32, i32* %x, i32 32
   %t = load i32, i32* %x.gep
   ret i32 %t
 }
 
 define i32 @imp_null_check_add_result(i32* %x, i32 %p) {
 ; CHECK-LABEL: _imp_null_check_add_result:
 ; CHECK: Ltmp5:
 ; CHECK: addl (%rdi), %esi
 ; CHECK: movl %esi, %eax
 ; CHECK: retq
 ; CHECK: Ltmp4:
 ; CHECK: movl $42, %eax
 ; CHECK: retq
 
  entry:
   %c = icmp eq i32* %x, null
-  br i1 %c, label %is_null, label %not_null
+  br i1 %c, label %is_null, label %not_null, !make.implicit !0
 
  is_null:
   ret i32 42
 
  not_null:
   %t = load i32, i32* %x
   %p1 = add i32 %t, %p
   ret i32 %p1
 }
 
+!0 = !{}
+
 ; CHECK-LABEL: __LLVM_FaultMaps:
 
 ; Version:
 ; CHECK-NEXT: .byte 1
 
 ; Reserved x2
 ; CHECK-NEXT: .byte 0
 ; CHECK-NEXT: .short 0