Home | History | Annotate | Download | only in docs 
      1 ==============================
      2 FaultMaps and implicit checks
      3 ==============================
      4 
      5 .. contents::
      6    :local:
      7    :depth: 2
      8 
      9 Motivation
     10 ==========
     11 
     12 Code generated by managed language runtimes tend to have checks that
     13 are required for safety but never fail in practice.  In such cases, it
     14 is profitable to make the non-failing case cheaper even if it makes
     15 the failing case significantly more expensive.  This asymmetry can be
     16 exploited by folding such safety checks into operations that can be
     17 made to fault reliably if the check would have failed, and recovering
     18 from such a fault by using a signal handler.
     19 
     20 For example, Java requires null checks on objects before they are read
     21 from or written to.  If the object is ``null`` then a
     22 ``NullPointerException`` has to be thrown, interrupting normal
     23 execution.  In practice, however, dereferencing a ``null`` pointer is
     24 extremely rare in well-behaved Java programs, and typically the null
     25 check can be folded into a nearby memory operation that operates on
     26 the same memory location.
     27 
     28 The Fault Map Section
     29 =====================
     30 
     31 Information about implicit checks generated by LLVM are put in a
     32 special "fault map" section.  On Darwin this section is named
     33 ``__llvm_faultmaps``.
     34 
     35 The format of this section is
     36 
     37 .. code-block:: none
     38 
     39   Header {
     40     uint8  : Fault Map Version (current version is 1)
     41     uint8  : Reserved (expected to be 0)
     42     uint16 : Reserved (expected to be 0)
     43   }
     44   uint32 : NumFunctions
     45   FunctionInfo[NumFunctions] {
     46     uint64 : FunctionAddress
     47     uint32 : NumFaultingPCs
     48     uint32 : Reserved (expected to be 0)
     49     FunctionFaultInfo[NumFaultingPCs] {
     50       uint32  : FaultKind = FaultMaps::FaultingLoad (only legal value currently)
     51       uint32  : FaultingPCOffset
     52       uint32  : HandlerPCOffset
     53     }
     54   }
     55 
     56 
     57 The ``ImplicitNullChecks`` pass
     58 ===============================
     59 
     60 The ``ImplicitNullChecks`` pass transforms explicit control flow for
     61 checking if a pointer is ``null``, like:
     62 
     63 .. code-block:: llvm
     64 
     65     %ptr = call i32* @get_ptr()
     66     %ptr_is_null = icmp i32* %ptr, null
     67     br i1 %ptr_is_null, label %is_null, label %not_null, !make.implicit !0
     68   
     69   not_null:
     70     %t = load i32, i32* %ptr
     71     br label %do_something_with_t
     72     
     73   is_null:
     74     call void @HFC()
     75     unreachable
     76   
     77   !0 = !{}
     78 
     79 to control flow implicit in the instruction loading or storing through
     80 the pointer being null checked:
     81 
     82 .. code-block:: llvm
     83 
     84     %ptr = call i32* @get_ptr()
     85     %t = load i32, i32* %ptr  ;; handler-pc = label %is_null
     86     br label %do_something_with_t
     87     
     88   is_null:
     89     call void @HFC()
     90     unreachable
     91 
     92 This transform happens at the ``MachineInstr`` level, not the LLVM IR
     93 level (so the above example is only representative, not literal).  The
     94 ``ImplicitNullChecks`` pass runs during codegen, if
     95 ``-enable-implicit-null-checks`` is passed to ``llc``.
     96 
     97 The ``ImplicitNullChecks`` pass adds entries to the
     98 ``__llvm_faultmaps`` section described above as needed.
     99 
    100 ``make.implicit`` metadata
    101 --------------------------
    102 
    103 Making null checks implicit is an aggressive optimization, and it can
    104 be a net performance pessimization if too many memory operations end
    105 up faulting because of it.  A language runtime typically needs to
    106 ensure that only a negligible number of implicit null checks actually
    107 fault once the application has reached a steady state.  A standard way
    108 of doing this is by healing failed implicit null checks into explicit
    109 null checks via code patching or recompilation.  It follows that there
    110 are two requirements an explicit null check needs to satisfy for it to
    111 be profitable to convert it to an implicit null check:
    112 
    113   1. The case where the pointer is actually null (i.e. the "failing"
    114      case) is extremely rare.
    115 
    116   2. The failing path heals the implicit null check into an explicit
    117      null check so that the application does not repeatedly page
    118      fault.
    119 
    120 The frontend is expected to mark branches that satisfy (1) and (2)
    121 using a ``!make.implicit`` metadata node (the actual content of the
    122 metadata node is ignored).  Only branches that are marked with
    123 ``!make.implicit`` metadata are considered as candidates for
    124 conversion into implicit null checks.
    125 
    126 (Note that while we could deal with (1) using profiling data, dealing
    127 with (2) requires some information not present in branch profiles.)
    128