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