docs/FaultMaps.rst

   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
  51       uint32  : FaultingPCOffset
  52       uint32  : HandlerPCOffset
  53     }
  54   }
  55
  56 FailtKind describes the reason of expected fault. Currently three kind
  57 of faults are supported:
  58
  59   1. ``FaultMaps::FaultingLoad`` - fault due to load from memory.
  60   2. ``FaultMaps::FaultingLoadStore`` - fault due to instruction load and store.
  61   3. ``FaultMaps::FaultingStore`` - fault due to store to memory.
  62
  63 The ``ImplicitNullChecks`` pass
  64 ===============================
  65
  66 The ``ImplicitNullChecks`` pass transforms explicit control flow for
  67 checking if a pointer is ``null``, like:
  68
  69 .. code-block:: llvm
  70
  71     %ptr = call i32* @get_ptr()
  72     %ptr_is_null = icmp i32* %ptr, null
  73     br i1 %ptr_is_null, label %is_null, label %not_null, !make.implicit !0
  74
  75   not_null:
  76     %t = load i32, i32* %ptr
  77     br label %do_something_with_t
  78
  79   is_null:
  80     call void @HFC()
  81     unreachable
  82
  83   !0 = !{}
  84
  85 to control flow implicit in the instruction loading or storing through
  86 the pointer being null checked:
  87
  88 .. code-block:: llvm
  89
  90     %ptr = call i32* @get_ptr()
  91     %t = load i32, i32* %ptr  ;; handler-pc = label %is_null
  92     br label %do_something_with_t
  93
  94   is_null:
  95     call void @HFC()
  96     unreachable
  97
  98 This transform happens at the ``MachineInstr`` level, not the LLVM IR
  99 level (so the above example is only representative, not literal).  The
 100 ``ImplicitNullChecks`` pass runs during codegen, if
 101 ``-enable-implicit-null-checks`` is passed to ``llc``.
 102
 103 The ``ImplicitNullChecks`` pass adds entries to the
 104 ``__llvm_faultmaps`` section described above as needed.
 105
 106 ``make.implicit`` metadata
 107 --------------------------
 108
 109 Making null checks implicit is an aggressive optimization, and it can
 110 be a net performance pessimization if too many memory operations end
 111 up faulting because of it.  A language runtime typically needs to
 112 ensure that only a negligible number of implicit null checks actually
 113 fault once the application has reached a steady state.  A standard way
 114 of doing this is by healing failed implicit null checks into explicit
 115 null checks via code patching or recompilation.  It follows that there
 116 are two requirements an explicit null check needs to satisfy for it to
 117 be profitable to convert it to an implicit null check:
 118
 119   1. The case where the pointer is actually null (i.e. the "failing"
 120      case) is extremely rare.
 121
 122   2. The failing path heals the implicit null check into an explicit
 123      null check so that the application does not repeatedly page
 124      fault.
 125
 126 The frontend is expected to mark branches that satisfy (1) and (2)
 127 using a ``!make.implicit`` metadata node (the actual content of the
 128 metadata node is ignored).  Only branches that are marked with
 129 ``!make.implicit`` metadata are considered as candidates for
 130 conversion into implicit null checks.
 131
 132 (Note that while we could deal with (1) using profiling data, dealing
 133 with (2) requires some information not present in branch profiles.)