/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.49k | 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 | 367k | #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 | 155k | MVM_STATIC_INLINE size_t hash_callsite(MVMThreadContext *tc, MVMCallsite *cs) { |
142 | 155k | return ((size_t)cs >> 3) & MVM_MULTICACHE_HASH_FILTER; |
143 | 155k | } |
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 | 446 | MVMROOT2(tc, capture, result, { |
162 | 446 | cache_obj = MVM_repr_alloc_init(tc, tc->instance->boot_types.BOOTMultiCache); |
163 | 446 | }); |
164 | 446 | } |
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.71k | MVMMultiCacheNode *tree = cache->node_hash_head; |
223 | 3.71k | MVMint32 cur_node = tweak_node; |
224 | 3.71k | have_head = 1; |
225 | 3.71k | if (tree[cur_node].action.cs) |
226 | 3.56k | have_tree = 1; |
227 | 3.71k | |
228 | 3.71k | /* Now see if we already have this callsite. */ |
229 | 3.71k | do { |
230 | 3.71k | if (tree[cur_node].action.cs == cs) { |
231 | 3.56k | have_callsite = 1; |
232 | 3.56k | cur_node = tree[cur_node].match; |
233 | 3.56k | break; |
234 | 3.56k | } |
235 | 152 | tweak_node = cur_node; |
236 | 152 | cur_node = tree[cur_node].no_match; |
237 | 152 | } while (cur_node > 0); |
238 | 3.71k | |
239 | 3.71k | /* 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.05k | matched_args++; |
246 | 4.05k | unmatched_arg = 0; |
247 | 4.05k | cur_node = tree[cur_node].match; |
248 | 4.05k | } |
249 | 17.7k | else { |
250 | 17.7k | unmatched_arg = 1; |
251 | 17.7k | cur_node = tree[cur_node].no_match; |
252 | 17.7k | } |
253 | 21.7k | } |
254 | 3.71k | |
255 | 3.71k | /* If we found a candidate, something inconsistent, as we |
256 | 3.71k | * checked for non-entry above. */ |
257 | 3.71k | if (cur_node != 0) |
258 | 0 | MVM_panic(1, "Corrupt multi dispatch cache: cur_node == 0"); |
259 | 3.71k | } |
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 | 445 | new_size += MVM_MULTICACHE_HASH_SIZE * sizeof(MVMMultiCacheNode); |
265 | 3.71k | 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 | 445 | 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.71k | ? cache->cache_memory_size / sizeof(MVMMultiCacheNode) |
280 | 445 | : 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 | 597 | if (!have_tree) { |
285 | 597 | /* We'll put it in the tree root. */ |
286 | 597 | new_head[tweak_node].action.cs = cs; |
287 | 597 | } |
288 | 0 | else { |
289 | 0 | /* We'll insert a new node and chain it from the tweak node. */ |
290 | 0 | new_head[insert_node].action.cs = cs; |
291 | 0 | new_head[insert_node].no_match = 0; |
292 | 0 | new_head[tweak_node].no_match = insert_node; |
293 | 0 | tweak_node = insert_node; |
294 | 0 | insert_node++; |
295 | 0 | } |
296 | 597 | } |
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.21k | MVMuint32 arg_idx = match_arg_idx[i]; |
301 | 6.21k | new_head[insert_node].action.arg_match = match_flags[arg_idx] | arg_idx; |
302 | 6.21k | new_head[insert_node].no_match = 0; |
303 | 6.21k | if (unmatched_arg) { |
304 | 3.56k | new_head[tweak_node].no_match = insert_node; |
305 | 3.56k | unmatched_arg = 0; |
306 | 3.56k | } |
307 | 2.65k | else { |
308 | 2.65k | new_head[tweak_node].match = insert_node; |
309 | 2.65k | } |
310 | 6.21k | tweak_node = insert_node; |
311 | 6.21k | insert_node++; |
312 | 6.21k | } |
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.71k | new_results = MVM_fixed_size_alloc(tc, tc->instance->fsa, |
318 | 3.71k | (cache->num_results + 1) * sizeof(MVMObject *)); |
319 | 3.71k | memcpy(new_results, cache->results, cache->num_results * sizeof(MVMObject *)); |
320 | 3.71k | MVM_ASSIGN_REF(tc, &(cache_obj->header), new_results[cache->num_results], result); |
321 | 3.71k | MVM_fixed_size_free_at_safepoint(tc, tc->instance->fsa, |
322 | 3.71k | cache->num_results * sizeof(MVMObject *), cache->results); |
323 | 3.71k | cache->results = new_results; |
324 | 3.71k | cache->num_results++; |
325 | 3.71k | } |
326 | 445 | else { |
327 | 445 | new_results = MVM_fixed_size_alloc(tc, tc->instance->fsa, |
328 | 445 | 2 * sizeof(MVMObject *)); |
329 | 445 | new_results[0] = NULL; /* Sentinel */ |
330 | 445 | MVM_ASSIGN_REF(tc, &(cache_obj->header), new_results[1], result); |
331 | 445 | cache->results = new_results; |
332 | 445 | cache->num_results = 2; |
333 | 445 | } |
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.71k | MVM_fixed_size_free_at_safepoint(tc, tc->instance->fsa, |
342 | 3.71k | 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.32k | MVMObject * MVM_multi_cache_find(MVMThreadContext *tc, MVMObject *cache_obj, MVMObject *capture) { |
369 | 8.32k | if (REPR(capture)->ID == MVM_REPR_ID_MVMCallCapture) { |
370 | 8.32k | MVMArgProcContext *apc = ((MVMCallCapture *)capture)->body.apc; |
371 | 8.32k | MVMCallsite *cs = apc->callsite; |
372 | 8.32k | return MVM_multi_cache_find_callsite_args(tc, cache_obj, cs, apc->args); |
373 | 8.32k | } |
374 | 0 | else { |
375 | 0 | MVM_exception_throw_adhoc(tc, "Multi cache lookup requires an MVMCallCapture"); |
376 | 0 | } |
377 | 8.32k | } |
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 | 442 | return NULL; |
393 | 151k | cache = &((MVMMultiCache *)cache_obj)->body; |
394 | 151k | if (!cache->node_hash_head) |
395 | 449 | return NULL; |
396 | 151k | |
397 | 151k | /* 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 | 150k | cur_node = tree[cur_node].match; |
405 | 150k | break; |
406 | 150k | } |
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 | 905k | 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 | 357k | MVMuint32 need_concrete = (arg_match & MVM_MULTICACHE_ARG_CONC_FILTER) ? 1 : 0; |
432 | 357k | if (IS_CONCRETE(arg.o) == need_concrete) { |
433 | 357k | MVMuint32 need_rw = (arg_match & MVM_MULTICACHE_ARG_RW_FILTER) ? 1 : 0; |
434 | 357k | if (need_rw == is_rw) { |
435 | 357k | cur_node = tree[cur_node].match; |
436 | 357k | continue; |
437 | 357k | } |
438 | 357k | } |
439 | 357k | } |
440 | 396k | cur_node = tree[cur_node].no_match; |
441 | 396k | } |
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.27k | while (cur_node > 0) { |
482 | 1.07k | MVMuint64 arg_match = tree[cur_node].action.arg_match; |
483 | 1.07k | MVMuint64 arg_idx = arg_match & MVM_MULTICACHE_ARG_IDX_FILTER; |
484 | 1.07k | MVMuint64 type_id = arg_match & MVM_MULTICACHE_TYPE_ID_FILTER; |
485 | 1.07k | MVMSpeshFacts *facts = arg_idx < MAX_ARGS_FOR_OPT |
486 | 1.07k | ? arg_info->arg_facts[arg_idx] |
487 | 1.07k | : NULL; |
488 | 1.07k | if (type_tuple) { |
489 | 843 | MVMuint64 tt_offset = arg_idx >= arg_info->cs->num_pos |
490 | 115 | ? (arg_idx - arg_info->cs->num_pos) / 2 |
491 | 728 | : arg_idx; |
492 | 843 | MVMuint32 is_rw = type_tuple[tt_offset].rw_cont; |
493 | 843 | MVMSTable *known_type_st = NULL; |
494 | 843 | MVMuint32 is_conc; |
495 | 843 | 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 | 843 | else if (type_tuple[tt_offset].type) { /* FIXME: tuples with neither decont_type nor type shouldn't appear */ |
500 | 843 | known_type_st = type_tuple[tt_offset].type->st; |
501 | 843 | is_conc = type_tuple[tt_offset].type_concrete; |
502 | 843 | } |
503 | 843 | |
504 | 843 | /* Now check if what we have matches what we need. */ |
505 | 843 | if (known_type_st && known_type_st->type_cache_id == type_id) { |
506 | 386 | MVMuint32 need_concrete = (arg_match & MVM_MULTICACHE_ARG_CONC_FILTER) ? 1 : 0; |
507 | 386 | if (is_conc == need_concrete) { |
508 | 386 | MVMuint32 need_rw = (arg_match & MVM_MULTICACHE_ARG_RW_FILTER) ? 1 : 0; |
509 | 386 | if (need_rw == is_rw) { |
510 | 386 | cur_node = tree[cur_node].match; |
511 | 386 | continue; |
512 | 386 | } |
513 | 386 | } |
514 | 386 | } |
515 | 457 | cur_node = tree[cur_node].no_match; |
516 | 457 | } |
517 | 230 | else if (facts) { |
518 | 230 | /* Figure out type, concreteness, and rw-ness from facts. */ |
519 | 230 | MVMSTable *known_type_st = NULL; |
520 | 230 | MVMuint32 is_conc; |
521 | 230 | MVMuint32 is_rw; |
522 | 230 | |
523 | 230 | /* Must know type. */ |
524 | 230 | if (!(facts->flags & MVM_SPESH_FACT_KNOWN_TYPE)) |
525 | 12 | return NULL; |
526 | 230 | |
527 | 230 | /* Must know if it's concrete or not. */ |
528 | 218 | if (!(facts->flags & (MVM_SPESH_FACT_CONCRETE | MVM_SPESH_FACT_TYPEOBJ))) |
529 | 25 | return NULL; |
530 | 218 | |
531 | 218 | /* If it's a container, must know what's inside it. Otherwise, |
532 | 218 | * we're already good on type info. */ |
533 | 193 | 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 | 193 | else { |
544 | 193 | known_type_st = STABLE(facts->type); |
545 | 193 | is_conc = (facts->flags & MVM_SPESH_FACT_CONCRETE) ? 1 : 0; |
546 | 179 | is_rw = is_conc && REPR(facts->type)->ID == MVM_REPR_ID_NativeRef; |
547 | 193 | } |
548 | 193 | |
549 | 193 | /* Now check if what we have matches what we need. */ |
550 | 193 | if (known_type_st->type_cache_id == type_id) { |
551 | 75 | MVMuint32 need_concrete = (arg_match & MVM_MULTICACHE_ARG_CONC_FILTER) ? 1 : 0; |
552 | 75 | if (is_conc == need_concrete) { |
553 | 75 | MVMuint32 need_rw = (arg_match & MVM_MULTICACHE_ARG_RW_FILTER) ? 1 : 0; |
554 | 75 | if (need_rw == is_rw) { |
555 | 75 | cur_node = tree[cur_node].match; |
556 | 75 | continue; |
557 | 75 | } |
558 | 75 | } |
559 | 75 | } |
560 | 118 | cur_node = tree[cur_node].no_match; |
561 | 118 | } |
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.07k | } |
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 | } |