134 lines · plain
1==============================2FaultMaps and implicit checks3==============================4 5.. contents::6 :local:7 :depth: 28 9Motivation10==========11 12Code generated by managed language runtimes tends to have checks that13are required for safety but never fail in practice. In such cases, it14is profitable to make the non-failing case cheaper even if it makes15the failing case significantly more expensive. This asymmetry can be16exploited by folding such safety checks into operations that can be17made to fault reliably if the check would have failed, and recovering18from such a fault by using a signal handler.19 20For example, Java requires null checks on objects before they are read21from or written to. If the object is ``null`` then a22``NullPointerException`` has to be thrown, interrupting normal23execution. In practice, however, dereferencing a ``null`` pointer is24extremely rare in well-behaved Java programs, and typically the null25check can be folded into a nearby memory operation that operates on26the same memory location.27 28The Fault Map Section29=====================30 31Information about implicit checks generated by LLVM is put in a32special "fault map" section. On Darwin this section is named33``__llvm_faultmaps``.34 35The format of this section is36 37.. code-block:: none38 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 : NumFunctions45 FunctionInfo[NumFunctions] {46 uint64 : FunctionAddress47 uint32 : NumFaultingPCs48 uint32 : Reserved (expected to be 0)49 FunctionFaultInfo[NumFaultingPCs] {50 uint32 : FaultKind51 uint32 : FaultingPCOffset52 uint32 : HandlerPCOffset53 }54 }55 56FailtKind describes the reason of expected fault. Currently three kind57of 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 63The ``ImplicitNullChecks`` pass64===============================65 66The ``ImplicitNullChecks`` pass transforms explicit control flow for67checking if a pointer is ``null``, like:68 69.. code-block:: llvm70 71 %ptr = call i32* @get_ptr()72 %ptr_is_null = icmp i32* %ptr, null73 br i1 %ptr_is_null, label %is_null, label %not_null, !make.implicit !074 75 not_null:76 %t = load i32, i32* %ptr77 br label %do_something_with_t78 79 is_null:80 call void @HFC()81 unreachable82 83 !0 = !{}84 85to control flow implicit in the instruction loading or storing through86the pointer being null checked:87 88.. code-block:: llvm89 90 %ptr = call i32* @get_ptr()91 %t = load i32, i32* %ptr ;; handler-pc = label %is_null92 br label %do_something_with_t93 94 is_null:95 call void @HFC()96 unreachable97 98This transform happens at the ``MachineInstr`` level, not the LLVM IR99level (so the above example is only representative, not literal). The100``ImplicitNullChecks`` pass runs during codegen, if101``-enable-implicit-null-checks`` is passed to ``llc``.102 103The ``ImplicitNullChecks`` pass adds entries to the104``__llvm_faultmaps`` section described above as needed.105 106``make.implicit`` metadata107--------------------------108 109Making null checks implicit is an aggressive optimization, and it can110be a net performance pessimization if too many memory operations end111up faulting because of it. A language runtime typically needs to112ensure that only a negligible number of implicit null checks actually113fault once the application has reached a steady state. A standard way114of doing this is by healing failed implicit null checks into explicit115null checks via code patching or recompilation. It follows that there116are two requirements an explicit null check needs to satisfy for it to117be 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 explicit123 null check so that the application does not repeatedly page124 fault.125 126The frontend is expected to mark branches that satisfy (1) and (2)127using a ``!make.implicit`` metadata node (the actual content of the128metadata node is ignored). Only branches that are marked with129``!make.implicit`` metadata are considered as candidates for130conversion into implicit null checks.131 132(Note that while we could deal with (1) using profiling data, dealing133with (2) requires some information not present in branch profiles.)134