docs/jit-imt

   1
   2 The mono JIT can use an IMT-style invocation system to call interface methods.
   3 This considerably reduces the runtime memory usage when many interface types
   4 are loaded, because the old system required an array in MonoVTable indexed
   5 by the interface id, which grows linearly as more interfaces are loaded.
   6
   7 IMT instead uses a fixed-size table and hashes each method in the implemented
   8 interfaces to a slot in the IMT table. To be able to resolve collisions, at each
   9 callsite we store the interface MonoMethod in a well-known register and the
  10 IMT table will contain a snippet of code that uses it to jump to the
  11 proper vtable slot. The interface invocation sequence becomes (in pseud-ocode):
  12
  13         mov magic_reg, interface_monomethod
  14         call vtable [imt_slot]
  15
  16 The IMT table is stored at negative addresses in the vtable, like the old
  17 interface array used to be.
  18
  19 In case of collisions in the IMT slot, the JIT performs a linear search if
  20 the colliding methods are few or a binary search otherwise.
  21 To make this easier for each JIT port, a sort of internal representation
  22 of the code is created: this is an array of MonoIMTCheckItem structures
  23 built in a way to allow easy generation of a bsearch, when the list of colliding
  24 methods becomes large.
  25
  26 Each item in the array represents either a direct check for a method to be invoked
  27 or a bisection check in the bsearch algorithm.
  28
  29 struct _MonoIMTCheckItem {
  30         MonoMethod       *method;
  31         int               check_target_idx;
  32         int               vtable_slot;
  33         guint8           *jmp_code;
  34         guint8           *code_target;
  35         guint8            is_equals;
  36         guint8            compare_done;
  37         guint8            chunk_size;
  38         guint8            short_branch;
  39 };
  40
  41 For a direct check, the is_equals value is non-zero and the emitted code
  42 should be equivalent to:
  43         if (magic_reg != item->method)
  44                 jump_to_item (array [item->check_target_idx]);
  45         jump_to_vtable (item->vtable_slot);
  46
  47 Note that if item->check_target_idx is 0, the jump should be omitted
  48 since this is the end of a linear sequence (you might want to insert a jump to
  49 a breakpoint, though, for debugging).
  50
  51 For a bisect check the code is even simpler:
  52
  53         if (magic_reg >= item->method)
  54                 jump_to_item (array [item->check_target_idx]);
  55
  56 In this case item->check_target_idx is always non-zero.
  57 Note that in both cases item->method becomes an immediate constant in the
  58 jitted code.
  59
  60 The other fields in the structure are there to provide to the backend
  61 common storage for data needed during emission.
  62 As each item's code is emitted, the start of it is stored in the code_target
  63 field. At the same time when a conditional branch is inserted, its address
  64 is stored in jmp_code: this way with a single forward pass on the array at
  65 the end of the emission phase the branches can be patched to point to the
  66 proper target item's code.
  67
  68 chunk_size can be used to store the size of the code generated for the item: this
  69 can be used to optimize the short/long branch instructions, together with
  70 info stored in short_branch.
  71
  72 The compare_done field can be used to avoid doing an additional compare
  73 in a is_equals item for the same MonoMethod that was just compare in a
  74 bisecting item. Suppose we have 4 methods colliding in a slot, A, B, C and D.
  75 The generated code will look like (M is the method to call):
  76
  77         compare (C, M)
  78         goto upper_sequence if bigger_equals
  79         /* linear sequence */
  80         compare (M, A)
  81         goto B_found if not_equals
  82         jump to A's slot
  83 B_found:
  84         jump to B's slot
  85
  86 upper_sequence:
  87         /* we just did a compare against C, no need to compare again */
  88         goto D_found if not_equals
  89         jump to C's slot
  90 D_found:
  91         jump to D's slot
  92
  93 This optimization is of course valid for architectures with flags registers.
  94
  95 As a further optimization to reduce memory usage, the Mono runtime sets the
  96 IMT slots initially to a single-instance magic trampoline so there is actually no
  97 memory used up by the thunks in the case of collisions. When an interface method is
  98 called the magic trampoline will fill-in the IMT slot with the proper thunk or
  99 trampoline, so later calls will use the fast path.
 100 Given that only the IMT slots that are actually used will be initialized, this saves
 101 quite a bit of memory, as it's unlikely that all the interface methods are called on
 102 all the different types.
 103