docs/jit-imt

   1
   2                 IMT-based interface invocation support
   3
   4 The mono JIT can use an IMT-style invocation system to call interface methods.
   5 This considerably reduces the runtime memory usage when many interface types
   6 are loaded, because the old system required an array in MonoVTable indexed
   7 by the interface id, which grows linearly as more interfaces are loaded.
   8 In some cases there are also speedups, since an interface call can reduce to
   9 a virtual call automatically.
  10
  11 IMT instead uses a fixed-size table and hashes each method in the implemented
  12 interfaces to a slot in the IMT table. To be able to resolve collisions, at each
  13 callsite we store the interface MonoMethod to be called in a well-known register and
  14 the IMT table will contain a snippet of code that uses it to jump to the
  15 proper vtable slot. The interface invocation sequence becomes (in pseudo-code):
  16
  17         mov magic_reg, interface_monomethod
  18         call vtable [imt_slot]
  19
  20 The IMT table is stored at negative addresses in the vtable, like the old
  21 interface array used to be.
  22
  23 A small note on the choice of magic_reg for different JIT backends: the IMT
  24 method identifier doesn't necessarily need to be stored in a register, though
  25 doing so is fast and the JIT code has already the infrastructure to handle this
  26 case in an arch-independent way. A JIT porter just needs to #define
  27 MONO_ARCH_IMT_REG to the chosen register. Note that this register should be
  28 part of the MONO_ARCH_CALLEE_REGS set as it will be handled by the local register
  29 allocator (see mini/inssel.brg) and it must not be part of the registers used for
  30 argument passing as you'd overwrite an argument in that case.
  31 Also note that the method-specific trampoline code should make sure to preserve
  32 this register (but it should already if it's in MONO_ARCH_CALLEE_REGS as
  33 it could have been used for a vtable indirect call).
  34
  35 Note that in the case of a nono-colliding IMT slot, the interface call
  36 instruction sequence becomes equivalent to a virtual call, as the IMT slot
  37 will contain the direct trampoline for the method and the magic trampoline will
  38 set the slot to the method's native code address once it is compiled.
  39
  40 In case of collisions in the IMT slot, the JIT performs a linear search if
  41 the colliding methods are few or a binary search otherwise.
  42 To make this easier for each JIT port, a sort of internal representation
  43 of the code is created: this is an array of MonoIMTCheckItem structures
  44 built in a way to allow easy generation of a bsearch, when the list of colliding
  45 methods becomes large.
  46
  47 Each item in the array represents either a direct check for a method to be invoked
  48 or a bisection check in the bsearch algorithm.
  49
  50 struct _MonoIMTCheckItem {
  51         MonoMethod       *method;
  52         int               check_target_idx;
  53         int               vtable_slot;
  54         guint8           *jmp_code;
  55         guint8           *code_target;
  56         guint8            is_equals;
  57         guint8            compare_done;
  58         guint8            chunk_size;
  59         guint8            short_branch;
  60 };
  61
  62 For a direct check, the is_equals value is non-zero and the emitted code
  63 should be equivalent to:
  64         if (magic_reg != item->method)
  65                 jump_to_item (array [item->check_target_idx]);
  66         jump_to_vtable (item->vtable_slot);
  67
  68 Note that if item->check_target_idx is 0, the jump should be omitted
  69 since this is the end of a linear sequence (you might want to insert a jump to
  70 a breakpoint, though, for debugging) and this would mean that we have an error:
  71 the IMT slot was asked to execute an interface method that the type doesn't implement.
  72 In the future we might want to handle this case not with a breakpoint or assert, but
  73 by either throwing an InvalidCast exception or by going into the runtime and
  74 adding support for the interface automagically to the type/vtable: this could be used
  75 both for transparent proxies and for the implicit interfaces that vectors in 2.0
  76 provide.
  77
  78 For a bisect check the code is even simpler:
  79
  80         if (magic_reg >= item->method)
  81                 jump_to_item (array [item->check_target_idx]);
  82
  83 In this case item->check_target_idx is always non-zero.
  84 Note that in both cases item->method becomes an immediate constant in the
  85 jitted code.
  86
  87 The other fields in the structure are there to provide to the backend
  88 common storage for data needed during emission.
  89 As each item's code is emitted, the start of it is stored in the code_target
  90 field. At the same time when a conditional branch is inserted, its address
  91 is stored in jmp_code: this way with a single forward pass on the array at
  92 the end of the emission phase the branches can be patched to point to the
  93 proper target item's code (this process would patch the jump_to_item pseudo
  94 instructions described above).
  95
  96 chunk_size can be used to store the size of the code generated for the item: this
  97 can be used to optimize the short/long branch instructions, together with
  98 info stored in short_branch. It is also used to calculate the size of the
  99 code to allocate for the whole IMT thunk.
 100
 101 The compare_done field can be used to avoid doing an additional compare
 102 in a is_equals item for the same MonoMethod that was just compared in a
 103 bisecting item. Suppose we have 4 methods colliding in a slot, A, B, C and D.
 104 The arch-independent code already took care of sorting them, so that:
 105         A < B < C < D
 106
 107 The generated code will look like (M is the method to call):
 108
 109         compare (C, M)
 110         goto upper_sequence if bigger_equals
 111         /* linear sequence */
 112         compare (M, A)
 113         goto B_found if not_equals
 114         jump to A's slot
 115 B_found:
 116         jump to B's slot
 117
 118 upper_sequence:
 119         /* we just did a compare against C, no need to compare again */
 120         goto D_found if not_equals
 121         jump to C's slot
 122 D_found:
 123         jump to D's slot
 124
 125 This optimization is of course valid for architectures with flags registers.
 126
 127 As a further optimization to reduce memory usage, the Mono runtime sets the
 128 IMT slots initially to a single-instance magic trampoline so there is actually no
 129 memory used up by the thunks in the case of collisions. When an interface method is
 130 called the magic trampoline will fill-in the IMT slot with the proper thunk or
 131 trampoline, so later calls will use the fast path.
 132 This single-instance trampoline will use MONO_FAKE_IMT_METHOD as the method
 133 it's asking to be compiled and executed: the trampoline code does recognize
 134 this special value and retrieves the interface method to call from the usual
 135 MONO_ARCH_IMT_REG saved by the trampoline code.
 136 Given that only the IMT slots that are actually used will be initialized, this saves
 137 quite a bit of memory, as it's unlikely that all the interface methods are called on
 138 all the different types.
 139