1==============================
2FaultMaps and implicit checks
3==============================
4
5.. contents::
6   :local:
7   :depth: 2
8
9Motivation
10==========
11
12Code generated by managed language runtimes tend to have checks that
13are required for safety but never fail in practice.  In such cases, it
14is profitable to make the non-failing case cheaper even if it makes
15the failing case significantly more expensive.  This asymmetry can be
16exploited by folding such safety checks into operations that can be
17made to fault reliably if the check would have failed, and recovering
18from such a fault by using a signal handler.
19
20For example, Java requires null checks on objects before they are read
21from or written to.  If the object is ``null`` then a
22``NullPointerException`` has to be thrown, interrupting normal
23execution.  In practice, however, dereferencing a ``null`` pointer is
24extremely rare in well-behaved Java programs, and typically the null
25check can be folded into a nearby memory operation that operates on
26the same memory location.
27
28The Fault Map Section
29=====================
30
31Information about implicit checks generated by LLVM are put in a
32special "fault map" section.  On Darwin this section is named
33``__llvm_faultmaps``.
34
35The 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
57The ``ImplicitNullChecks`` pass
58===============================
59
60The ``ImplicitNullChecks`` pass transforms explicit control flow for
61checking 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
79to control flow implicit in the instruction loading or storing through
80the 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
92This transform happens at the ``MachineInstr`` level, not the LLVM IR
93level (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
97The ``ImplicitNullChecks`` pass adds entries to the
98``__llvm_faultmaps`` section described above as needed.
99
100``make.implicit`` metadata
101--------------------------
102
103Making null checks implicit is an aggressive optimization, and it can
104be a net performance pessimization if too many memory operations end
105up faulting because of it.  A language runtime typically needs to
106ensure that only a negligible number of implicit null checks actually
107fault once the application has reached a steady state.  A standard way
108of doing this is by healing failed implicit null checks into explicit
109null checks via code patching or recompilation.  It follows that there
110are two requirements an explicit null check needs to satisfy for it to
111be 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
120The frontend is expected to mark branches that satisfy (1) and (2)
121using a ``!make.implicit`` metadata node (the actual content of the
122metadata node is ignored).  Only branches that are marked with
123``!make.implicit`` metadata are considered as candidates for
124conversion into implicit null checks.
125
126(Note that while we could deal with (1) using profiling data, dealing
127with (2) requires some information not present in branch profiles.)
128