Coverage Report

Created: 2018-06-21 18:56

/home/travis/build/MoarVM/MoarVM/src/6model/reprs/MVMMultiCache.c
Line
Count
Source (jump to first uncovered line)
1
#include "moar.h"
2
3
/* This representation's function pointer table. */
4
static const MVMREPROps MVMMultiCache_this_repr;
5
6
/* Creates a new type object of this representation, and associates it with
7
 * the given HOW. */
8
144
static MVMObject * type_object_for(MVMThreadContext *tc, MVMObject *HOW) {
9
144
    MVMSTable *st = MVM_gc_allocate_stable(tc, &MVMMultiCache_this_repr, HOW);
10
144
11
144
    MVMROOT(tc, st, {
12
144
        MVMObject *obj = MVM_gc_allocate_type_object(tc, st);
13
144
        MVM_ASSIGN_REF(tc, &(st->header), st->WHAT, obj);
14
144
        st->size = sizeof(MVMMultiCache);
15
144
    });
16
144
17
144
    return st->WHAT;
18
144
}
19
20
/* Copies the body of one object to another. */
21
0
static void copy_to(MVMThreadContext *tc, MVMSTable *st, void *src, MVMObject *dest_root, void *dest) {
22
0
    MVM_exception_throw_adhoc(tc, "Cannot copy object with representation MultiCache");
23
0
}
24
25
/* Called by the VM to mark any GCable items. */
26
175
static void gc_mark(MVMThreadContext *tc, MVMSTable *st, void *data, MVMGCWorklist *worklist) {
27
175
    MVMMultiCacheBody *mc = (MVMMultiCacheBody *)data;
28
175
    size_t i;
29
1.67k
    for (i = 0; i < mc->num_results; i++)
30
1.50k
        MVM_gc_worklist_add(tc, worklist, &(mc->results[i]));
31
175
}
32
33
/* Called by the VM in order to free memory associated with this object. */
34
0
static void gc_free(MVMThreadContext *tc, MVMObject *obj) {
35
0
    MVMMultiCache *mc = (MVMMultiCache *)obj;
36
0
    if (mc->body.node_hash_head)
37
0
        MVM_fixed_size_free(tc, tc->instance->fsa, mc->body.cache_memory_size,
38
0
            mc->body.node_hash_head);
39
0
    if (mc->body.results)
40
0
        MVM_fixed_size_free(tc, tc->instance->fsa,
41
0
            mc->body.num_results * sizeof(MVMObject *),
42
0
            mc->body.results);
43
0
}
44
45
static const MVMStorageSpec storage_spec = {
46
    MVM_STORAGE_SPEC_REFERENCE, /* inlineable */
47
    0,                          /* bits */
48
    0,                          /* align */
49
    MVM_STORAGE_SPEC_BP_NONE,   /* boxed_primitive */
50
    0,                          /* can_box */
51
    0,                          /* is_unsigned */
52
};
53
54
/* Gets the storage specification for this representation. */
55
0
static const MVMStorageSpec * get_storage_spec(MVMThreadContext *tc, MVMSTable *st) {
56
0
    return &storage_spec;
57
0
}
58
59
/* Compose the representation. */
60
0
static void compose(MVMThreadContext *tc, MVMSTable *st, MVMObject *info) {
61
0
    /* Nothing to do for this REPR. */
62
0
}
63
64
/* Calculates the non-GC-managed memory we hold on to. */
65
51
static MVMuint64 unmanaged_size(MVMThreadContext *tc, MVMSTable *st, void *data) {
66
51
    MVMMultiCacheBody *body = (MVMMultiCacheBody *)data;
67
51
    return body->num_results * sizeof(MVMObject *) + body->cache_memory_size;
68
51
}
69
70
/* Initializes the representation. */
71
144
const MVMREPROps * MVMMultiCache_initialize(MVMThreadContext *tc) {
72
144
    return &MVMMultiCache_this_repr;
73
144
}
74
75
static const MVMREPROps MVMMultiCache_this_repr = {
76
    type_object_for,
77
    MVM_gc_allocate_object,
78
    NULL, /* initialize */
79
    copy_to,
80
    MVM_REPR_DEFAULT_ATTR_FUNCS,
81
    MVM_REPR_DEFAULT_BOX_FUNCS,
82
    MVM_REPR_DEFAULT_POS_FUNCS,
83
    MVM_REPR_DEFAULT_ASS_FUNCS,
84
    MVM_REPR_DEFAULT_ELEMS,
85
    get_storage_spec,
86
    NULL, /* change_type */
87
    NULL, /* serialize */
88
    NULL, /* deserialize */
89
    NULL, /* serialize_repr_data */
90
    NULL, /* deserialize_repr_data */
91
    NULL, /* deserialize_stable_size */
92
    gc_mark,
93
    gc_free,
94
    NULL, /* gc_cleanup */
95
    NULL, /* gc_mark_repr_data */
96
    NULL, /* gc_free_repr_data */
97
    compose,
98
    NULL, /* spesh */
99
    "MVMMultiCache", /* name */
100
    MVM_REPR_ID_MVMMultiCache,
101
    unmanaged_size, /* unmanaged_size */
102
    NULL, /* describe_refs */
103
};
104
105
/* Filters for various parts of action.arg_match. */
106
777k
#define MVM_MULTICACHE_ARG_IDX_FILTER  (2 * MVM_INTERN_ARITY_LIMIT - 1)
107
366k
#define MVM_MULTICACHE_ARG_CONC_FILTER 0x10
108
357k
#define MVM_MULTICACHE_ARG_RW_FILTER   0x20
109
755k
#define MVM_MULTICACHE_TYPE_ID_FILTER  (0xFFFFFFFFFFFFFFFFULL ^ (MVM_TYPE_CACHE_ID_INCR - 1))
110
111
/* Debug support dumps the tree after each addition. */
112
#define MVM_MULTICACHE_DEBUG 0
113
#if MVM_MULTICACHE_DEBUG
114
static void dump_cache(MVMThreadContext *tc, MVMMultiCacheBody *cache) {
115
    MVMint32 num_nodes = cache->cache_memory_size / sizeof(MVMMultiCacheNode);
116
    MVMint32 i;
117
    printf("Multi cache at %p (%d nodes, %d results)\n",
118
        cache, num_nodes, cache->num_results);
119
    for (i = 0; i < num_nodes; i++)
120
        printf(" - %p -> (Y: %d, N: %d)\n",
121
            cache->node_hash_head[i].action.cs,
122
            cache->node_hash_head[i].match,
123
            cache->node_hash_head[i].no_match);
124
    printf("\n");
125
}
126
#endif
127
128
/* Big cache profiling. */
129
#define MVM_MULTICACHE_BIG_PROFILE 0
130
#if MVM_MULTICACHE_BIG_PROFILE
131
static MVMint32 is_power_of_2(MVMint32 value) {
132
    return ((value != 0) && !(value & (value - 1)));
133
}
134
#endif
135
136
/* Takes a pointer to a callsite and turns it into an index into the multi cache
137
 * keyed by callsite. We don't do anything too clever here: just shift away the
138
 * bits of the pointer we know will be zero, and the take the least significant
139
 * few bits of it. Hopefully the distribution of memory addresses over time will
140
 * be sufficient. */
141
154k
MVM_STATIC_INLINE size_t hash_callsite(MVMThreadContext *tc, MVMCallsite *cs) {
142
154k
    return ((size_t)cs >> 3) & MVM_MULTICACHE_HASH_FILTER;
143
154k
}
144
145
/* Adds an entry to the multi-dispatch cache. */
146
4.15k
MVMObject * MVM_multi_cache_add(MVMThreadContext *tc, MVMObject *cache_obj, MVMObject *capture, MVMObject *result) {
147
4.15k
    MVMMultiCacheBody *cache = NULL;
148
4.15k
    MVMCallsite       *cs    = NULL;
149
4.15k
    MVMArgProcContext *apc   = NULL;
150
4.15k
    MVMuint64          match_flags[2 * MVM_INTERN_ARITY_LIMIT];
151
4.15k
    size_t             match_arg_idx[MVM_INTERN_ARITY_LIMIT];
152
4.15k
    MVMuint32          flag, i, num_obj_args, have_head, have_tree,
153
4.15k
                       have_callsite, matched_args, unmatched_arg,
154
4.15k
                       tweak_node, insert_node;
155
4.15k
    size_t             new_size;
156
4.15k
    MVMMultiCacheNode *new_head    = NULL;
157
4.15k
    MVMObject        **new_results = NULL;
158
4.15k
159
4.15k
    /* Allocate a cache if needed. */
160
4.15k
    if (MVM_is_null(tc, cache_obj) || !IS_CONCRETE(cache_obj) || REPR(cache_obj)->ID != MVM_REPR_ID_MVMMultiCache) {
161
445
        MVMROOT2(tc, capture, result, {
162
445
            cache_obj = MVM_repr_alloc_init(tc, tc->instance->boot_types.BOOTMultiCache);
163
445
        });
164
445
    }
165
4.15k
    cache = &((MVMMultiCache *)cache_obj)->body;
166
4.15k
167
4.15k
    /* Ensure we got a capture in to cache on; bail if not interned. */
168
4.15k
    if (REPR(capture)->ID == MVM_REPR_ID_MVMCallCapture) {
169
4.15k
        apc        = ((MVMCallCapture *)capture)->body.apc;
170
4.15k
        cs         = apc->callsite;
171
4.15k
        if (!cs->is_interned)
172
0
            return cache_obj;
173
4.15k
    }
174
0
    else {
175
0
        MVM_exception_throw_adhoc(tc, "Multi cache addition requires an MVMCallCapture");
176
0
    }
177
4.15k
178
4.15k
    /* Calculate matcher flags for all the object arguments. */
179
4.15k
    num_obj_args = 0;
180
14.4k
    for (i = 0, flag = 0; flag < cs->flag_count; i++, flag++) {
181
10.2k
        if (cs->arg_flags[flag] & MVM_CALLSITE_ARG_NAMED)
182
1.97k
            i++;
183
10.2k
        if ((cs->arg_flags[flag] & MVM_CALLSITE_ARG_MASK) == MVM_CALLSITE_ARG_OBJ) {
184
10.2k
            MVMRegister  arg   = apc->args[i];
185
10.2k
            MVMSTable   *st    = STABLE(arg.o);
186
10.2k
            MVMuint32    is_rw = 0;
187
10.2k
            if (st->container_spec && IS_CONCRETE(arg.o)) {
188
2
                MVMContainerSpec const *contspec = st->container_spec;
189
2
                if (!contspec->fetch_never_invokes)
190
2
                    return cache_obj; /* Impossible to cache. */
191
0
                if (REPR(arg.o)->ID != MVM_REPR_ID_NativeRef) {
192
0
                    is_rw = contspec->can_store(tc, arg.o);
193
0
                    contspec->fetch(tc, arg.o, &arg);
194
0
                }
195
0
                else {
196
0
                    is_rw = 1;
197
0
                }
198
0
            }
199
10.2k
            match_flags[i] = STABLE(arg.o)->type_cache_id |
200
10.2k
                (is_rw ? MVM_MULTICACHE_ARG_RW_FILTER : 0) |
201
10.2k
                (IS_CONCRETE(arg.o) ? MVM_MULTICACHE_ARG_CONC_FILTER : 0);
202
10.2k
            match_arg_idx[num_obj_args] = i;
203
10.2k
            num_obj_args++;
204
10.2k
        }
205
10.2k
    }
206
4.15k
207
4.15k
    /* Oobtain the cache addition lock, and then do another lookup to ensure
208
4.15k
     * nobody beat us to making this entry. */
209
4.15k
    uv_mutex_lock(&(tc->instance->mutex_multi_cache_add));
210
4.15k
    if (MVM_multi_cache_find(tc, cache_obj, capture))
211
0
        goto DONE;
212
4.15k
213
4.15k
    /* We're now udner the insertion lock and know nobody else can tweak the
214
4.15k
     * cache. First, see if there's even a current version and search tree. */
215
4.15k
    have_head = 0;
216
4.15k
    have_tree = 0;
217
4.15k
    have_callsite = 0;
218
4.15k
    matched_args = 0;
219
4.15k
    unmatched_arg = 0;
220
4.15k
    tweak_node = hash_callsite(tc, cs);
221
4.15k
    if (cache->node_hash_head) {
222
3.70k
        MVMMultiCacheNode *tree = cache->node_hash_head;
223
3.70k
        MVMint32 cur_node = tweak_node;
224
3.70k
        have_head = 1;
225
3.70k
        if (tree[cur_node].action.cs)
226
3.55k
            have_tree = 1;
227
3.70k
228
3.70k
        /* Now see if we already have this callsite. */
229
3.70k
        do {
230
3.70k
            if (tree[cur_node].action.cs == cs) {
231
3.55k
                have_callsite = 1;
232
3.55k
                cur_node = tree[cur_node].match;
233
3.55k
                break;
234
3.55k
            }
235
152
            tweak_node = cur_node;
236
152
            cur_node = tree[cur_node].no_match;
237
152
        } while (cur_node > 0);
238
3.70k
239
3.70k
        /* Chase until we reach an arg we don't match. */
240
25.4k
        while (cur_node > 0) {
241
21.7k
            MVMuint64 arg_match = tree[cur_node].action.arg_match;
242
21.7k
            MVMuint64 arg_idx   = arg_match & MVM_MULTICACHE_ARG_IDX_FILTER;
243
21.7k
            tweak_node = cur_node;
244
21.7k
            if ((match_flags[arg_idx] | arg_idx) == arg_match) {
245
4.04k
                matched_args++;
246
4.04k
                unmatched_arg = 0;
247
4.04k
                cur_node = tree[cur_node].match;
248
4.04k
            }
249
17.6k
            else {
250
17.6k
                unmatched_arg = 1;
251
17.6k
                cur_node = tree[cur_node].no_match;
252
17.6k
            }
253
21.7k
        }
254
3.70k
255
3.70k
        /* If we found a candidate, something inconsistent, as we
256
3.70k
         * checked for non-entry above. */
257
3.70k
        if (cur_node != 0)
258
0
            MVM_panic(1, "Corrupt multi dispatch cache: cur_node == 0");
259
3.70k
    }
260
4.15k
261
4.15k
    /* Now calculate the new size we'll need to allocate. */
262
4.15k
    new_size = cache->cache_memory_size;
263
4.15k
    if (!have_head)
264
444
        new_size += MVM_MULTICACHE_HASH_SIZE * sizeof(MVMMultiCacheNode);
265
3.70k
    else if (!have_callsite)
266
152
        new_size += sizeof(MVMMultiCacheNode);
267
4.15k
    new_size += (num_obj_args - matched_args) * sizeof(MVMMultiCacheNode);
268
4.15k
269
4.15k
    /* Allocate and copy existing cache. */
270
4.15k
    new_head = MVM_fixed_size_alloc(tc, tc->instance->fsa, new_size);
271
4.15k
    memcpy(new_head, cache->node_hash_head, cache->cache_memory_size);
272
4.15k
273
4.15k
    /* If we had no head, set it up. */
274
4.15k
    if (!have_head)
275
444
        memset(new_head, 0, MVM_MULTICACHE_HASH_SIZE * sizeof(MVMMultiCacheNode));
276
4.15k
277
4.15k
    /* Calculate storage location of new nodes. */
278
4.15k
    insert_node = have_head
279
3.70k
        ? cache->cache_memory_size / sizeof(MVMMultiCacheNode)
280
444
        : MVM_MULTICACHE_HASH_SIZE;
281
4.15k
282
4.15k
    /* If we had no callsite, add a node for it. */
283
4.15k
    if (!have_callsite) {
284
596
        if (!have_tree) {
285
595
            /* We'll put it in the tree root. */
286
595
            new_head[tweak_node].action.cs = cs;
287
595
        }
288
1
        else {
289
1
            /* We'll insert a new node and chain it from the tweak node. */
290
1
            new_head[insert_node].action.cs = cs;
291
1
            new_head[insert_node].no_match = 0;
292
1
            new_head[tweak_node].no_match = insert_node;
293
1
            tweak_node = insert_node;
294
1
            insert_node++;
295
1
        }
296
596
    }
297
4.15k
298
4.15k
    /* Now insert any needed arg matchers. */
299
10.3k
    for (i = matched_args; i < num_obj_args; i++) {
300
6.20k
        MVMuint32 arg_idx = match_arg_idx[i];
301
6.20k
        new_head[insert_node].action.arg_match = match_flags[arg_idx] | arg_idx;
302
6.20k
        new_head[insert_node].no_match = 0;
303
6.20k
        if (unmatched_arg) {
304
3.55k
            new_head[tweak_node].no_match = insert_node;
305
3.55k
            unmatched_arg = 0;
306
3.55k
        }
307
2.64k
        else {
308
2.64k
            new_head[tweak_node].match = insert_node;
309
2.64k
        }
310
6.20k
        tweak_node = insert_node;
311
6.20k
        insert_node++;
312
6.20k
    }
313
4.15k
314
4.15k
    /* Make a copy of the results, or allocate new (first result is NULL
315
4.15k
     * always) and insert the new result. Schedule old results for freeing. */
316
4.15k
    if (cache->num_results) {
317
3.70k
        new_results = MVM_fixed_size_alloc(tc, tc->instance->fsa,
318
3.70k
            (cache->num_results + 1) * sizeof(MVMObject *));
319
3.70k
        memcpy(new_results, cache->results, cache->num_results * sizeof(MVMObject *));
320
3.70k
        MVM_ASSIGN_REF(tc, &(cache_obj->header), new_results[cache->num_results], result);
321
3.70k
        MVM_fixed_size_free_at_safepoint(tc, tc->instance->fsa,
322
3.70k
            cache->num_results * sizeof(MVMObject *), cache->results);
323
3.70k
        cache->results = new_results;
324
3.70k
        cache->num_results++;
325
3.70k
    }
326
444
    else {
327
444
        new_results = MVM_fixed_size_alloc(tc, tc->instance->fsa,
328
444
            2 * sizeof(MVMObject *));
329
444
        new_results[0] = NULL; /* Sentinel */
330
444
        MVM_ASSIGN_REF(tc, &(cache_obj->header), new_results[1], result);
331
444
        cache->results = new_results;
332
444
        cache->num_results = 2;
333
444
    }
334
4.15k
    MVM_barrier();
335
4.15k
336
4.15k
    /* Associate final node with result index. */
337
4.15k
    new_head[tweak_node].match = -(cache->num_results - 1);
338
4.15k
339
4.15k
    /* Update the rest. */
340
4.15k
    if (cache->node_hash_head)
341
3.70k
        MVM_fixed_size_free_at_safepoint(tc, tc->instance->fsa,
342
3.70k
            cache->cache_memory_size, cache->node_hash_head);
343
4.15k
    cache->node_hash_head = new_head;
344
4.15k
    cache->cache_memory_size = new_size;
345
4.15k
346
4.15k
#if MVM_MULTICACHE_DEBUG
347
    printf("Made new entry for callsite with %d object arguments\n", num_obj_args);
348
    dump_cache(tc, cache);
349
#endif
350
4.15k
#if MVM_MULTICACHE_BIG_PROFILE
351
    if (cache->num_results >= 32 && is_power_of_2(cache->num_results)) {
352
        MVMCode *code = (MVMCode *)MVM_frame_find_invokee(tc, result, NULL);
353
        char *name = MVM_string_utf8_encode_C_string(tc, code->body.sf->body.name);
354
        printf("Multi cache for %s reached %d entries\n", name, cache->num_results);
355
        MVM_free(name);
356
    }
357
#endif
358
4.15k
359
4.15k
    /* Release lock. */
360
4.15k
  DONE:
361
4.15k
    uv_mutex_unlock(&(tc->instance->mutex_multi_cache_add));
362
4.15k
363
4.15k
    /* Hand back the created/updated cache. */
364
4.15k
    return cache_obj;
365
4.15k
}
366
367
/* Does a lookup in a multi-dispatch cache using a capture. */
368
8.31k
MVMObject * MVM_multi_cache_find(MVMThreadContext *tc, MVMObject *cache_obj, MVMObject *capture) {
369
8.31k
    if (REPR(capture)->ID == MVM_REPR_ID_MVMCallCapture) {
370
8.31k
        MVMArgProcContext *apc = ((MVMCallCapture *)capture)->body.apc;
371
8.31k
        MVMCallsite       *cs  = apc->callsite;
372
8.31k
        return MVM_multi_cache_find_callsite_args(tc, cache_obj, cs, apc->args);
373
8.31k
    }
374
0
    else {
375
0
        MVM_exception_throw_adhoc(tc, "Multi cache lookup requires an MVMCallCapture");
376
0
    }
377
8.31k
}
378
379
/* Does a lookup in the multi-dispatch cache using a callsite and args. */
380
MVMObject * MVM_multi_cache_find_callsite_args(MVMThreadContext *tc, MVMObject *cache_obj,
381
151k
    MVMCallsite *cs, MVMRegister *args) {
382
151k
    MVMMultiCacheBody *cache = NULL;
383
151k
    MVMMultiCacheNode *tree  = NULL;
384
151k
    MVMint32 cur_node;
385
151k
386
151k
    /* Bail if callsite not interned. */
387
151k
    if (!cs->is_interned)
388
0
        return NULL;
389
151k
390
151k
    /* If no cache, no result. */
391
151k
    if (MVM_is_null(tc, cache_obj) || !IS_CONCRETE(cache_obj) || REPR(cache_obj)->ID != MVM_REPR_ID_MVMMultiCache)
392
441
        return NULL;
393
150k
    cache = &((MVMMultiCache *)cache_obj)->body;
394
150k
    if (!cache->node_hash_head)
395
448
        return NULL;
396
150k
397
150k
    /* Use hashed callsite to find the node to start with. */
398
150k
    cur_node = hash_callsite(tc, cs);
399
150k
400
150k
    /* Walk tree until we match callsite. */
401
150k
    tree = cache->node_hash_head;
402
150k
    do {
403
150k
        if (tree[cur_node].action.cs == cs) {
404
149k
            cur_node = tree[cur_node].match;
405
149k
            break;
406
149k
        }
407
453
        cur_node = tree[cur_node].no_match;
408
453
    } while (cur_node > 0);
409
150k
410
150k
    /* Now walk until we match argument type/concreteness/rw. */
411
904k
    while (cur_node > 0) {
412
754k
        MVMuint64    arg_match = tree[cur_node].action.arg_match;
413
754k
        MVMuint64    arg_idx   = arg_match & MVM_MULTICACHE_ARG_IDX_FILTER;
414
754k
        MVMuint64    type_id   = arg_match & MVM_MULTICACHE_TYPE_ID_FILTER;
415
754k
        MVMRegister  arg       = args[arg_idx];
416
754k
        MVMSTable   *st        = STABLE(arg.o);
417
754k
        MVMuint64    is_rw     = 0;
418
754k
        if (st->container_spec && IS_CONCRETE(arg.o)) {
419
4
            MVMContainerSpec const *contspec = st->container_spec;
420
4
            if (!contspec->fetch_never_invokes)
421
4
                return NULL;
422
0
            if (REPR(arg.o)->ID != MVM_REPR_ID_NativeRef) {
423
0
                is_rw = contspec->can_store(tc, arg.o);
424
0
                contspec->fetch(tc, arg.o, &arg);
425
0
            }
426
0
            else {
427
0
                is_rw = 1;
428
0
            }
429
0
        }
430
754k
        if (STABLE(arg.o)->type_cache_id == type_id) {
431
356k
            MVMuint32 need_concrete = (arg_match & MVM_MULTICACHE_ARG_CONC_FILTER) ? 1 : 0;
432
356k
            if (IS_CONCRETE(arg.o) == need_concrete) {
433
356k
                MVMuint32 need_rw = (arg_match & MVM_MULTICACHE_ARG_RW_FILTER) ? 1 : 0;
434
356k
                if (need_rw == is_rw) {
435
356k
                    cur_node = tree[cur_node].match;
436
356k
                    continue;
437
356k
                }
438
356k
            }
439
356k
        }
440
397k
        cur_node = tree[cur_node].no_match;
441
397k
    }
442
150k
443
150k
    /* Negate result and index into results (the first result is always NULL
444
150k
     * to save flow control around "no match"). */
445
150k
    return cache->results[-cur_node];
446
150k
}
447
448
/* Do a multi cache lookup based upon spesh arg facts. */
449
MVMObject * MVM_multi_cache_find_spesh(MVMThreadContext *tc, MVMObject *cache_obj,
450
                                       MVMSpeshCallInfo *arg_info,
451
239
                                       MVMSpeshStatsType *type_tuple) {
452
239
    MVMMultiCacheBody *cache = NULL;
453
239
    MVMMultiCacheNode *tree  = NULL;
454
239
    MVMint32 cur_node;
455
239
456
239
    /* Bail if callsite not interned. */
457
239
    if (!arg_info->cs->is_interned)
458
0
        return NULL;
459
239
460
239
    /* If no cache, no result. */
461
239
    if (MVM_is_null(tc, cache_obj) || !IS_CONCRETE(cache_obj) || REPR(cache_obj)->ID != MVM_REPR_ID_MVMMultiCache)
462
0
        return NULL;
463
239
    cache = &((MVMMultiCache *)cache_obj)->body;
464
239
    if (!cache->node_hash_head)
465
0
        return NULL;
466
239
467
239
    /* Use hashed callsite to find the node to start with. */
468
239
    cur_node = hash_callsite(tc, arg_info->cs);
469
239
470
239
    /* Walk tree until we match callsite. */
471
239
    tree = cache->node_hash_head;
472
239
    do {
473
239
        if (tree[cur_node].action.cs == arg_info->cs) {
474
239
            cur_node = tree[cur_node].match;
475
239
            break;
476
239
        }
477
0
        cur_node = tree[cur_node].no_match;
478
0
    } while (cur_node > 0);
479
239
480
239
    /* Now walk until we match argument type/concreteness/rw. */
481
1.33k
    while (cur_node > 0) {
482
1.13k
        MVMuint64      arg_match = tree[cur_node].action.arg_match;
483
1.13k
        MVMuint64      arg_idx   = arg_match & MVM_MULTICACHE_ARG_IDX_FILTER;
484
1.13k
        MVMuint64      type_id   = arg_match & MVM_MULTICACHE_TYPE_ID_FILTER;
485
1.13k
        MVMSpeshFacts *facts     = arg_idx < MAX_ARGS_FOR_OPT
486
1.13k
            ? arg_info->arg_facts[arg_idx]
487
1.13k
            : NULL;
488
1.13k
        if (type_tuple) {
489
876
            MVMuint64 tt_offset = arg_idx >= arg_info->cs->num_pos
490
119
                ? (arg_idx - arg_info->cs->num_pos) / 2
491
757
                : arg_idx;
492
876
            MVMuint32 is_rw = type_tuple[tt_offset].rw_cont;
493
876
            MVMSTable *known_type_st = NULL;
494
876
            MVMuint32 is_conc;
495
876
            if (type_tuple[tt_offset].decont_type) {
496
0
                known_type_st = type_tuple[tt_offset].decont_type->st;
497
0
                is_conc = type_tuple[tt_offset].decont_type_concrete;
498
0
            }
499
876
            else if (type_tuple[tt_offset].type) { /* FIXME: tuples with neither decont_type nor type shouldn't appear */
500
876
                known_type_st = type_tuple[tt_offset].type->st;
501
876
                is_conc = type_tuple[tt_offset].type_concrete;
502
876
            }
503
876
504
876
            /* Now check if what we have matches what we need. */
505
876
            if (known_type_st && known_type_st->type_cache_id == type_id) {
506
382
                MVMuint32 need_concrete = (arg_match & MVM_MULTICACHE_ARG_CONC_FILTER) ? 1 : 0;
507
382
                if (is_conc == need_concrete) {
508
382
                    MVMuint32 need_rw = (arg_match & MVM_MULTICACHE_ARG_RW_FILTER) ? 1 : 0;
509
382
                    if (need_rw == is_rw) {
510
382
                        cur_node = tree[cur_node].match;
511
382
                        continue;
512
382
                    }
513
382
                }
514
382
            }
515
494
            cur_node = tree[cur_node].no_match;
516
494
        }
517
258
        else if (facts) {
518
258
            /* Figure out type, concreteness, and rw-ness from facts. */
519
258
            MVMSTable *known_type_st = NULL;
520
258
            MVMuint32  is_conc;
521
258
            MVMuint32  is_rw;
522
258
523
258
            /* Must know type. */
524
258
            if (!(facts->flags & MVM_SPESH_FACT_KNOWN_TYPE))
525
11
                return NULL;
526
258
527
258
            /* Must know if it's concrete or not. */
528
247
            if (!(facts->flags & (MVM_SPESH_FACT_CONCRETE | MVM_SPESH_FACT_TYPEOBJ)))
529
26
                return NULL;
530
247
531
247
            /* If it's a container, must know what's inside it. Otherwise,
532
247
             * we're already good on type info. */
533
221
            if ((facts->flags & MVM_SPESH_FACT_CONCRETE) && STABLE(facts->type)->container_spec) {
534
0
                /* Again, need to know type and concreteness. */
535
0
                if (!(facts->flags & MVM_SPESH_FACT_KNOWN_DECONT_TYPE))
536
0
                    return NULL;
537
0
                if (!(facts->flags & (MVM_SPESH_FACT_DECONT_CONCRETE | MVM_SPESH_FACT_DECONT_TYPEOBJ)))
538
0
                    return NULL;
539
0
                known_type_st = STABLE(facts->decont_type);
540
0
                is_conc = (facts->flags & MVM_SPESH_FACT_DECONT_CONCRETE) ? 1 : 0;
541
0
                is_rw = (facts->flags & MVM_SPESH_FACT_RW_CONT) ? 1 : 0;
542
0
            }
543
221
            else {
544
221
                known_type_st = STABLE(facts->type);
545
221
                is_conc = (facts->flags & MVM_SPESH_FACT_CONCRETE) ? 1 : 0;
546
207
                is_rw = is_conc && REPR(facts->type)->ID == MVM_REPR_ID_NativeRef;
547
221
            }
548
221
549
221
            /* Now check if what we have matches what we need. */
550
221
            if (known_type_st->type_cache_id == type_id) {
551
78
                MVMuint32 need_concrete = (arg_match & MVM_MULTICACHE_ARG_CONC_FILTER) ? 1 : 0;
552
78
                if (is_conc == need_concrete) {
553
78
                    MVMuint32 need_rw = (arg_match & MVM_MULTICACHE_ARG_RW_FILTER) ? 1 : 0;
554
78
                    if (need_rw == is_rw) {
555
78
                        cur_node = tree[cur_node].match;
556
78
                        continue;
557
78
                    }
558
78
                }
559
78
            }
560
143
            cur_node = tree[cur_node].no_match;
561
143
        }
562
0
        else {
563
0
            /* No facts about this argument available from analysis, so
564
0
             * can't resolve the dispatch. */
565
0
            return NULL;
566
0
        }
567
1.13k
    }
568
239
569
239
    /* Negate result and index into results (the first result is always NULL
570
239
     * to save flow control around "no match"). */
571
202
    return cache->results[-cur_node];
572
239
}