Coverage Report

Created: 2018-06-21 18:56

/home/travis/build/MoarVM/MoarVM/src/jit/expr.c
Line
Count
Source (jump to first uncovered line)
1
#include "moar.h"
2
3
/* Mathematical min and max macro's */
4
#ifndef MAX
5
291k
#define MAX(a,b) ((a) > (b) ? (a) : (b));
6
#endif
7
8
#ifndef MIN
9
#define MIN(a,b) ((a) < (b) ? (a) : (b));
10
#endif
11
12
13
/* macros used in the expression list templates, defined here so they
14
   don't overwrite other definitions */
15
#define CONST_PTR(x) ((uintptr_t)(x))
16
#define QUOTE(x) (x)
17
#define MSG(...) CONST_PTR(#__VA_ARGS__)
18
#define SIZEOF_MEMBER(type, member) sizeof(((type*)0)->member)
19
20
#include "jit/core_templates.h"
21
22
23
static const MVMJitExprOpInfo expr_op_info[] = {
24
#define OP_INFO(name, nchild, nargs, vtype, cast) { #name, nchild, nargs, MVM_JIT_ ## vtype, MVM_JIT_ ## cast }
25
    MVM_JIT_EXPR_OPS(OP_INFO)
26
#undef OP_INFO
27
};
28
29
30
39.1M
const MVMJitExprOpInfo * MVM_jit_expr_op_info(MVMThreadContext *tc, MVMint32 op) {
31
39.1M
    if (op < 0 || op >= MVM_JIT_MAX_NODES) {
32
0
        MVM_oops(tc, "JIT: Expr op index out of bounds: %d", op);
33
0
    }
34
39.1M
    return &expr_op_info[op];
35
39.1M
}
36
37
/* Record the node that defines a value */
38
struct ValueDefinition {
39
    MVMint32 node;
40
    MVMint32 root;
41
    MVMint32 addr;
42
};
43
44
45
46
/* Logical negation of MVMJitExprOp flags. */
47
361k
MVMint32 MVM_jit_expr_op_negate_flag(MVMThreadContext *tc, MVMint32 op) {
48
361k
    switch(op) {
49
0
    case MVM_JIT_LT:
50
0
        return MVM_JIT_GE;
51
0
    case MVM_JIT_LE:
52
0
        return MVM_JIT_GT;
53
573
    case MVM_JIT_EQ:
54
573
        return MVM_JIT_NE;
55
16.9k
    case MVM_JIT_NE:
56
16.9k
        return MVM_JIT_EQ;
57
0
    case MVM_JIT_GE:
58
0
        return MVM_JIT_LT;
59
0
    case MVM_JIT_GT:
60
0
        return MVM_JIT_LE;
61
260k
    case MVM_JIT_NZ:
62
260k
        return MVM_JIT_ZR;
63
83.6k
    case MVM_JIT_ZR:
64
83.6k
        return MVM_JIT_NZ;
65
0
    default:
66
0
        break;
67
361k
    }
68
0
    return -1; /* not a flag */
69
361k
}
70
71
0
MVMint32 MVM_jit_expr_op_is_binary_noncommutative(MVMThreadContext *tc, MVMint32 op) {
72
0
    switch (op) {
73
0
    case MVM_JIT_SUB:
74
0
    case MVM_JIT_XOR:
75
0
        /* and DIV, SHIFT, etc */
76
0
        return 1;
77
0
    default:
78
0
        /* ADD, MUL, AND, OR, etc. are commutative */
79
0
        return 0;
80
0
    }
81
0
}
82
83
84
static MVMint32 MVM_jit_expr_add_regaddr(MVMThreadContext *tc, MVMJitExprTree *tree,
85
832k
                                         MVMuint16 reg) {
86
832k
    MVMint32 num  = tree->nodes_num;
87
832k
    MVMJitExprNode template[] = { MVM_JIT_LOCAL,
88
832k
                                  MVM_JIT_ADDR, num, reg * MVM_JIT_REG_SZ };
89
832k
    MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(MVMJitExprNode));
90
832k
    return num + 1;
91
832k
}
92
93
32
static MVMint32 MVM_jit_expr_add_loadframe(MVMThreadContext *tc, MVMJitExprTree *tree) {
94
32
    MVMint32 num = tree->nodes_num;
95
32
    MVMJitExprNode template[] = { MVM_JIT_TC,
96
32
                                  MVM_JIT_ADDR, num, offsetof(MVMThreadContext, cur_frame),
97
32
                                  MVM_JIT_LOAD, num + 1, sizeof(MVMFrame*) };
98
32
    MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(MVMJitExprNode));
99
32
    return num + 4;
100
32
}
101
102
103
104
static MVMint32 MVM_jit_expr_add_load(MVMThreadContext *tc, MVMJitExprTree *tree,
105
307k
                                      MVMint32 addr) {
106
307k
    MVMint32 num        = tree->nodes_num;
107
307k
    MVMJitExprNode template[] = { MVM_JIT_LOAD, addr, MVM_JIT_REG_SZ };
108
307k
    MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(MVMJitExprNode));
109
307k
    return num;
110
307k
}
111
112
113
static MVMint32 MVM_jit_expr_add_store(MVMThreadContext *tc, MVMJitExprTree *tree,
114
386k
                                       MVMint32 addr, MVMint32 val, MVMint32 sz) {
115
386k
    MVMint32 num = tree->nodes_num;
116
386k
    MVMJitExprNode template[] = { MVM_JIT_STORE, addr, val, sz };
117
386k
    MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(MVMJitExprNode));
118
386k
    return num;
119
386k
}
120
121
122
4.08k
static MVMint32 MVM_jit_expr_add_cast(MVMThreadContext *tc, MVMJitExprTree *tree, MVMint32 node, MVMint32 to_size, MVMint32 from_size, MVMint32 is_signed) {
123
4.08k
    MVMint32 num = tree->nodes_num;
124
4.08k
    MVMJitExprNode template[] = { MVM_JIT_CAST, node, to_size, from_size, is_signed };
125
4.08k
    MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(MVMJitExprNode));
126
4.08k
    return num;
127
4.08k
}
128
129
5.44k
static MVMint32 MVM_jit_expr_add_label(MVMThreadContext *tc, MVMJitExprTree *tree, MVMint32 label) {
130
5.44k
    MVMint32 num = tree->nodes_num;
131
5.44k
    MVMJitExprNode template[] = { MVM_JIT_MARK, label };
132
5.44k
    MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(template[0]));
133
5.44k
    return num;
134
5.44k
}
135
136
static MVMint32 MVM_jit_expr_add_lexaddr(MVMThreadContext *tc, MVMJitExprTree *tree,
137
32
                                         MVMuint16 outers, MVMuint16 idx) {
138
32
    MVMint32 i;
139
32
    /* (frame) as the root */
140
32
    MVMint32 num = MVM_jit_expr_add_loadframe(tc, tree);
141
32
    for (i = 0; i < outers; i++) {
142
0
        /* (load (addr $val (&offsetof MVMFrame outer)) (&sizeof MVMFrame*)) */
143
0
        MVMJitExprNode template[] = { MVM_JIT_ADDR, num, offsetof(MVMFrame, outer),
144
0
                                      MVM_JIT_LOAD, tree->nodes_num, sizeof(MVMFrame*) };
145
0
        MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(MVMJitExprNode));
146
0
        num = tree->nodes_num - 3;
147
0
    }
148
32
    /* (addr (load (addr $frame (&offsetof MVMFrame env)) ptr_sz) ptr_sz*idx) */
149
32
    {
150
32
        MVMJitExprNode template[] = {
151
32
            MVM_JIT_ADDR, num, offsetof(MVMFrame, env), /* (addr $frame (&offsetof MVMFrame env)) */
152
32
            MVM_JIT_LOAD, tree->nodes_num, MVM_JIT_PTR_SZ, /* (load $addr ptr_sz) */
153
32
            MVM_JIT_ADDR, tree->nodes_num + 3, idx * MVM_JIT_REG_SZ /* (addr $frame_env idx*reg_sz) */
154
32
        };
155
32
        MVM_VECTOR_APPEND(tree->nodes, template, sizeof(template)/sizeof(MVMJitExprNode));
156
32
        num = tree->nodes_num - 3;
157
32
    }
158
32
    return num;
159
32
}
160
161
162
static MVMint32 MVM_jit_expr_add_const(MVMThreadContext *tc, MVMJitExprTree *tree,
163
350k
                                       MVMSpeshOperand opr, MVMuint8 info) {
164
350k
165
350k
    MVMJitExprNode template[]  = { MVM_JIT_CONST, 0, 0 };
166
350k
    MVMint32 num               = tree->nodes_num;
167
350k
    MVMint32 size              = 3;
168
350k
    switch(info & MVM_operand_type_mask) {
169
0
    case MVM_operand_int8:
170
0
        template[1] = opr.lit_i8;
171
0
        template[2] = sizeof(MVMint8);
172
0
        break;
173
158k
    case MVM_operand_int16:
174
158k
        template[1] = opr.lit_i16;
175
158k
        template[2] = sizeof(MVMint16);
176
158k
        break;
177
444
    case MVM_operand_coderef:
178
444
        template[1] = opr.coderef_idx;
179
444
        template[2] = sizeof(MVMuint16);
180
444
        break;
181
1.42k
    case MVM_operand_int32:
182
1.42k
        template[1] = opr.lit_i32;
183
1.42k
        template[2] = sizeof(MVMint32);
184
1.42k
        break;
185
1
    case MVM_operand_int64:
186
1
        template[1] = opr.lit_i64;
187
1
        template[2] = sizeof(MVMint64);
188
1
        break;
189
0
    case MVM_operand_num32:
190
0
        /* possible endianess issue here */
191
0
        template[1] = opr.lit_i32;
192
0
        template[2] = sizeof(MVMnum32);
193
0
        break;
194
945
    case MVM_operand_num64:
195
945
        /* use i64 to get the bits */
196
945
        template[1] = opr.lit_i64;
197
945
        template[2] = sizeof(MVMnum64);
198
945
        break;
199
34.9k
    case MVM_operand_str:
200
34.9k
        /* string index really */
201
34.9k
        template[1] = opr.lit_str_idx;
202
34.9k
        template[2] = sizeof(MVMuint32);
203
34.9k
        break;
204
101k
    case MVM_operand_ins:
205
101k
        template[0] = MVM_JIT_LABEL;
206
101k
        template[1] = MVM_jit_label_before_bb(tc, tree->graph, opr.ins_bb);
207
101k
        size        = 2;
208
101k
        break;
209
0
    case MVM_operand_callsite:
210
0
        template[1] = opr.callsite_idx;
211
0
        template[2] = sizeof(MVMuint16);
212
0
        break;
213
52.5k
    case MVM_operand_spesh_slot:
214
52.5k
        template[1] = opr.lit_i16;
215
52.5k
        template[2] = sizeof(MVMuint16);
216
52.5k
        break;
217
0
    default:
218
0
        MVM_oops(tc, "Can't add constant for operand type %d\n", (info & MVM_operand_type_mask) >> 3);
219
350k
    }
220
350k
    MVM_VECTOR_APPEND(tree->nodes, template, size);
221
350k
    return num;
222
350k
}
223
224
0
static MVMint32 getlex_needs_autoviv(MVMThreadContext *tc, MVMJitGraph *jg, MVMSpeshIns *ins) {
225
0
    MVMSpeshOperand opr = ins->operands[1];
226
0
    MVMuint16 lexical_type = MVM_spesh_get_lex_type(tc, jg->sg, opr.lex.outers, opr.lex.idx);
227
0
    return lexical_type == MVM_reg_obj;
228
0
}
229
230
750
static MVMint32 bindlex_needs_write_barrier(MVMThreadContext *tc, MVMJitGraph *jg, MVMSpeshIns *ins) {
231
750
    MVMSpeshOperand opr = ins->operands[0];
232
750
    MVMuint16 lexical_type = MVM_spesh_get_lex_type(tc, jg->sg, opr.lex.outers, opr.lex.idx);
233
750
    /* need to hit a write barrier if we bindlex to a string */
234
750
    return lexical_type == MVM_reg_obj || lexical_type == MVM_reg_str;
235
750
}
236
237
238
685k
static MVMint32 ins_has_single_input_output_operand(MVMSpeshIns *ins) {
239
685k
    switch (ins->info->opcode) {
240
17.4k
    case MVM_OP_inc_i:
241
17.4k
    case MVM_OP_inc_u:
242
17.4k
    case MVM_OP_dec_i:
243
17.4k
    case MVM_OP_dec_u:
244
17.4k
        return 1;
245
668k
      default:
246
668k
          break;
247
685k
    }
248
668k
    return 0;
249
685k
}
250
251
void MVM_jit_expr_load_operands(MVMThreadContext *tc, MVMJitExprTree *tree, MVMSpeshIns *ins,
252
676k
                                struct ValueDefinition *values, MVMint32 *operands) {
253
676k
    MVMint32 i;
254
2.08M
    for (i = 0; i < ins->info->num_operands; i++) {
255
1.40M
        MVMSpeshOperand opr = ins->operands[i];
256
1.40M
        MVMint8    opr_kind = ins->info->operands[i];
257
1.40M
        switch(opr_kind & MVM_operand_rw_mask) {
258
525k
        case MVM_operand_read_reg:
259
525k
            if (values[opr.reg.orig].node >= 0) {
260
225k
                operands[i] = values[opr.reg.orig].node;
261
300k
            } else {
262
300k
                MVMint32 addr = MVM_jit_expr_add_regaddr(tc, tree, opr.reg.orig);
263
300k
                operands[i] = MVM_jit_expr_add_load(tc, tree, addr);
264
300k
                values[opr.reg.orig].node = operands[i];
265
300k
                values[opr.reg.orig].addr = addr;
266
300k
                values[opr.reg.orig].root = -1; /* load is not part of a root */
267
300k
            }
268
525k
            break;
269
531k
        case MVM_operand_write_reg:
270
531k
            /* get address of register to write */
271
531k
            operands[i] = MVM_jit_expr_add_regaddr(tc, tree, opr.reg.orig);
272
531k
            break;
273
350k
        case MVM_operand_literal:
274
350k
            operands[i] = MVM_jit_expr_add_const(tc, tree, opr, ins->info->operands[i]);
275
350k
            break;
276
0
        case MVM_operand_read_lex:
277
0
        {
278
0
            MVMint32 addr = MVM_jit_expr_add_lexaddr(tc, tree, opr.lex.outers, opr.lex.idx);
279
0
            operands[i] = MVM_jit_expr_add_load(tc, tree, addr);
280
0
            break;
281
525k
        }
282
32
        case MVM_operand_write_lex:
283
32
            operands[i] = MVM_jit_expr_add_lexaddr(tc, tree, opr.lex.outers, opr.lex.idx);
284
32
            break;
285
0
        default:
286
0
            continue;
287
1.40M
        }
288
1.40M
        if (operands[i] >= tree->nodes_num || operands[i] < 0) {
289
0
            MVM_oops(tc, "JIT: something is wrong with operand loading");
290
0
        }
291
1.40M
    }
292
676k
293
676k
    /* A HACK.
294
676k
     *
295
676k
     * dec_i and inc_i have a single operand that acts both as input and output.
296
676k
     * This is marked only as an output operand, though. Thus, we load the
297
676k
     * address here, and define the value later. However, if we have multiple of
298
676k
     * these in sequence, each will load the old value from memory, disregarding
299
676k
     * the value that an earlier operator has defined, i.e. losing the update.
300
676k
     * That's a bug, and this tries to fix it, by forcing a 'split' between the
301
676k
     * input and the output operand.
302
676k
     */
303
676k
    if (ins_has_single_input_output_operand(ins)) {
304
8.71k
        MVMuint16 reg = ins->operands[0].reg.orig;
305
8.71k
        if (values[reg].node >= 0) {
306
2.03k
            operands[1] = values[reg].node;
307
6.68k
        } else {
308
6.68k
            /* operands[0] has the address */
309
6.68k
            operands[1] = MVM_jit_expr_add_load(tc, tree, operands[0]);
310
6.68k
            /* no need to insert it in the table since it will be directly
311
6.68k
             * overwritten */
312
6.68k
        }
313
8.71k
    }
314
676k
}
315
316
/* This function is to check the internal consistency of a template
317
 * before I apply it.  I need this because I make a lot of mistakes in
318
 * writing templates, and debugging is hard. */
319
676k
static void check_template(MVMThreadContext *tc, const MVMJitExprTemplate *template, MVMSpeshIns *ins) {
320
676k
    MVMint32 i;
321
19.4M
    for (i = 0; i < template->len; i++) {
322
18.7M
        switch(template->info[i]) {
323
0
        case 0:
324
0
            MVM_oops(tc, "JIT: Template info shorter than template length (instruction %s)", ins->info->name);
325
0
            break;
326
6.00M
        case 'l':
327
6.00M
            if (template->code[i] >= i || template->code[i] < 0)
328
0
                MVM_oops(tc, "JIT: Template link out of bounds (instruction: %s)", ins->info->name);
329
6.00M
            break;
330
1.61M
        case 'f':
331
1.61M
            if (template->code[i] < 0 ||
332
1.61M
                (template->code[i] >= ins->info->num_operands &&
333
8.71k
                 !ins_has_single_input_output_operand(ins)))
334
0
                MVM_oops(tc, "JIT: Operand access out of bounds (instruction: %s)", ins->info->name);
335
1.61M
            break;
336
11.1M
        default:
337
11.1M
            continue;
338
18.7M
        }
339
18.7M
    }
340
676k
    if (template->info[i])
341
0
        MVM_oops(tc, "JIT: Template info longer than template length (instruction: %s)",
342
0
                 ins->info->name);
343
676k
}
344
345
/* Add template to nodes, filling in operands and linking tree nodes. Return template root */
346
MVMint32 MVM_jit_expr_apply_template(MVMThreadContext *tc, MVMJitExprTree *tree,
347
676k
                                     const MVMJitExprTemplate *template, MVMint32 *operands) {
348
676k
    MVMint32 i, num;
349
676k
    num = tree->nodes_num;
350
676k
    MVM_VECTOR_ENSURE_SPACE(tree->nodes, template->len);
351
676k
    /* Loop over string until the end */
352
19.4M
    for (i = 0; template->info[i]; i++) {
353
18.7M
        switch (template->info[i]) {
354
6.00M
        case 'l':
355
6.00M
            /* link template-relative to nodes-relative */
356
6.00M
            tree->nodes[num+i] = template->code[i] + num;
357
6.00M
            break;
358
1.61M
        case 'f':
359
1.61M
            /* add operand node into the nodes */
360
1.61M
            tree->nodes[num+i] = operands[template->code[i]];
361
1.61M
            break;
362
11.1M
        default:
363
11.1M
            /* copy from template to nodes */
364
11.1M
            tree->nodes[num+i] = template->code[i];
365
11.1M
            break;
366
18.7M
        }
367
18.7M
    }
368
676k
    tree->nodes_num = num + template->len;
369
676k
    return num + template->root; /* root relative to nodes */
370
676k
}
371
372
373
374
/* Collect tree analysis information, add stores of computed values */
375
static void analyze_node(MVMThreadContext *tc, MVMJitTreeTraverser *traverser,
376
9.02M
                         MVMJitExprTree *tree, MVMint32 node) {
377
9.02M
378
9.02M
    const MVMJitExprOpInfo   *op_info = MVM_jit_expr_op_info(tc, tree->nodes[node]);
379
9.02M
    MVMint32   first_child = node + 1;
380
8.49M
    MVMint32        nchild = op_info->nchild < 0 ? tree->nodes[first_child++] : op_info->nchild;
381
9.02M
    MVMJitExprNode   *args = tree->nodes + first_child + nchild;
382
9.02M
    MVMJitExprNodeInfo *node_info = tree->info + node;
383
9.02M
    MVMint32 i;
384
9.02M
385
9.02M
    node_info->op_info   = op_info;
386
9.02M
    /* propagate node sizes and assign labels */
387
9.02M
    switch (tree->nodes[node]) {
388
632k
    case MVM_JIT_CONST:
389
632k
        /* node size is given */
390
632k
        node_info->size        = args[1];
391
632k
        break;
392
181k
    case MVM_JIT_COPY:
393
181k
        node_info->size = tree->info[tree->nodes[first_child]].size;
394
181k
        break;
395
1.39M
    case MVM_JIT_LOAD:
396
1.39M
        node_info->size = args[0];
397
1.39M
        break;
398
4.08k
    case MVM_JIT_CAST:
399
4.08k
        node_info->size = args[0];
400
4.08k
        break;
401
3.42M
    case MVM_JIT_ADDR:
402
3.42M
    case MVM_JIT_IDX:
403
3.42M
    case MVM_JIT_LABEL:
404
3.42M
    case MVM_JIT_TC:
405
3.42M
    case MVM_JIT_CU:
406
3.42M
    case MVM_JIT_LOCAL:
407
3.42M
    case MVM_JIT_STACK:
408
3.42M
        /* addresses result in pointers */
409
3.42M
        node_info->size = MVM_JIT_PTR_SZ;
410
3.42M
        break;
411
3.42M
        /* binary operations */
412
197k
    case MVM_JIT_ADD:
413
197k
    case MVM_JIT_SUB:
414
197k
    case MVM_JIT_AND:
415
197k
    case MVM_JIT_OR:
416
197k
    case MVM_JIT_XOR:
417
197k
    case MVM_JIT_NOT:
418
197k
        /* comparisons */
419
197k
    case MVM_JIT_NE:
420
197k
    case MVM_JIT_LT:
421
197k
    case MVM_JIT_LE:
422
197k
    case MVM_JIT_EQ:
423
197k
    case MVM_JIT_GE:
424
197k
    case MVM_JIT_GT:
425
197k
        {
426
197k
            /* arithmetic nodes use their largest operand */
427
197k
            MVMint32 left  = tree->nodes[first_child];
428
197k
            MVMint32 right = tree->nodes[first_child+1];
429
197k
            node_info->size = MAX(tree->info[left].size,
430
197k
                                  tree->info[right].size);
431
197k
            break;
432
197k
        }
433
29.6k
    case MVM_JIT_FLAGVAL:
434
29.6k
        /* XXX THIS IS A HACK
435
29.6k
         *
436
29.6k
         * The true size of 'flagval' is a single byte.  But that would mean it
437
29.6k
         * had to be upcast to be used as a 64-bit word, and that subtly
438
29.6k
         * doesn't work if the value is STORE-d to memory. */
439
29.6k
        node_info->size = 4;
440
29.6k
        break;
441
104k
    case MVM_JIT_DO:
442
104k
        /* node size of last child */
443
104k
        {
444
104k
            MVMint32 last_child = tree->nodes[first_child + nchild - 1];
445
104k
            node_info->size = tree->info[last_child].size;
446
104k
            break;
447
197k
        }
448
94.0k
    case MVM_JIT_IF:
449
94.0k
        {
450
94.0k
            MVMint32 left  = tree->nodes[first_child+1];
451
94.0k
            MVMint32 right = tree->nodes[first_child+2];
452
94.0k
            node_info->size = MAX(tree->info[left].size,
453
94.0k
                                         tree->info[right].size);
454
94.0k
            break;
455
197k
        }
456
101k
    case MVM_JIT_CALL:
457
101k
        node_info->size = args[0];
458
101k
        break;
459
363k
    case MVM_JIT_NZ:
460
363k
    case MVM_JIT_ZR:
461
363k
        node_info->size = tree->info[tree->nodes[first_child]].size;
462
363k
        break;
463
2.49M
    default:
464
2.49M
        /* all other things, branches, labels, when, arglist, carg,
465
2.49M
         * comparisons, etc, have no value size */
466
2.49M
        node_info->size = 0;
467
2.49M
        break;
468
9.02M
    }
469
9.02M
470
9.02M
    /* Insert casts as necessary */
471
9.02M
    if (op_info->cast != MVM_JIT_NO_CAST) {
472
5.36M
        for (i = 0; i < nchild; i++) {
473
2.83M
            MVMint32 child = tree->nodes[first_child+i];
474
2.83M
            if (tree->nodes[child] == MVM_JIT_CONST) {
475
259k
                /* CONST nodes can always take over their target size, so they never need to be cast */
476
259k
                tree->info[child].size = tree->info[node].size;
477
2.57M
            } else if (tree->info[child].size < node_info->size) {
478
4.08k
                /* Widening casts need to be handled explicitly, shrinking casts do not */
479
4.08k
                MVMint32 cast = MVM_jit_expr_add_cast(tc, tree, child, node_info->size, tree->info[child].size, op_info->cast);
480
4.08k
                /* Because the cast may have grown the backing nodes array, the info array needs to grow as well */
481
4.08k
                MVM_VECTOR_ENSURE_SIZE(tree->info, cast);
482
4.08k
                /* And because analyze_node is called in postorder,
483
4.08k
                   the newly added cast node would be neglected by the
484
4.08k
                   traverser. So we traverse it explicitly.. */
485
4.08k
                MVM_VECTOR_ENSURE_SIZE(traverser->visits, cast);
486
4.08k
                traverser->visits[cast] = 1;
487
4.08k
                analyze_node(tc, traverser, tree, cast);
488
4.08k
                /* Finally we replace the child with its cast */
489
4.08k
                tree->nodes[first_child+i] = cast;
490
4.08k
            }
491
2.83M
        }
492
2.52M
    }
493
9.02M
}
494
495
static void assign_labels(MVMThreadContext *tc, MVMJitTreeTraverser *traverser,
496
9.01M
                          MVMJitExprTree *tree, MVMint32 node) {
497
9.01M
    /* IF has two blocks, the first I call left, the second I call right.
498
9.01M
       Regular IF is implemented by the following sequence:
499
9.01M
500
9.01M
       * test
501
9.01M
       * negated conditional jump to label 1
502
9.01M
       * left block
503
9.01M
       * unconditional jump to label 2
504
9.01M
       * label 1
505
9.01M
       * right block
506
9.01M
       * label 2
507
9.01M
508
9.01M
       The 'short-circuiting' cases of IF ALL and IF ANY require special
509
9.01M
       treatment. IF ALL simply repeats the test+negated branch for each of the
510
9.01M
       ALL's children. IF ANY on the other hand must short circuit not into the
511
9.01M
       default (right) but into the (left) conditional block. So IF ANY must be
512
9.01M
       implemented as:
513
9.01M
514
9.01M
       (* test
515
9.01M
        * conditional jump to label 3) - repeated n times
516
9.01M
       * unconditional jump to label 1
517
9.01M
       * label 3
518
9.01M
       * left block
519
9.01M
       * unconditional jump to label 2
520
9.01M
       * label 1
521
9.01M
       * right block
522
9.01M
       * label 2
523
9.01M
524
9.01M
       NB - the label before the left block has been given the number
525
9.01M
       3 for consistency with the regular case.
526
9.01M
527
9.01M
       Simpilar observations are applicable to WHEN and WHEN ANY/WHEN
528
9.01M
       ALL.  Different altogether are the cases of ANY ALL and ALL
529
9.01M
       ANY.
530
9.01M
531
9.01M
       ANY ALL can be implemented as:
532
9.01M
       ( test
533
9.01M
         negated conditional jump to label 4) - repeated for all in ALL
534
9.01M
       * unconditional jump to label 3
535
9.01M
       * label 4 (continuing the ANY)
536
9.01M
537
9.01M
       This way the 'short-circuit' jump of the ALL sequence implies
538
9.01M
       the continuation of the ANY sequence, whereas the finishing of
539
9.01M
       the ALL sequence implies it succeeded and hence the ANY needs
540
9.01M
       to short-circuit.
541
9.01M
542
9.01M
       ALL ANY can be implemented analogously as:
543
9.01M
       ( test
544
9.01M
         conditional jump to label 4) repeated for all children of ANY
545
9.01M
       * unconditional short-circuit jump to label 1
546
9.01M
       * label 4
547
9.01M
548
9.01M
       Nested ALL in ALL and ANY in ANY all have the same
549
9.01M
       short-circuiting behaviour (i.e.  a nested ALL in ALL is
550
9.01M
       indistinguishable from inserting all the children of the nested
551
9.01M
       ALL into the nesting ALL), so they don't require special
552
9.01M
       treatment.
553
9.01M
554
9.01M
       All this goes to say in that the number of labels required and
555
9.01M
       the actual labels assigned to different children depends on the
556
9.01M
       structure of the tree, which is why labels are 'pushed down'
557
9.01M
       from parents to children, at least when those children are ANY
558
9.01M
       and ALL. */
559
9.01M
560
9.01M
    switch (tree->nodes[node]) {
561
84.2k
    case MVM_JIT_WHEN:
562
84.2k
        {
563
84.2k
            /* WHEN just requires one label in the default case */
564
84.2k
            MVMint32 test = tree->nodes[node+1];
565
84.2k
            tree->info[node].label = tree->num_labels++;
566
84.2k
            if (tree->nodes[test] == MVM_JIT_ANY) {
567
0
                /* ANY requires a pre-left-block label */
568
0
                tree->info[test].label = tree->num_labels++;
569
84.2k
            } else if (tree->nodes[test] == MVM_JIT_ALL) {
570
41.3k
                /* ALL takes over the label of its parent */
571
41.3k
                tree->info[test].label = tree->info[node].label;
572
41.3k
            }
573
84.2k
        }
574
84.2k
        break;
575
147k
    case MVM_JIT_IF:
576
147k
    case MVM_JIT_IFV:
577
147k
        {
578
147k
            MVMint32 test = tree->nodes[node+1];
579
147k
            /* take two labels, one for the left block and one for the right block */
580
147k
            tree->info[node].label = tree->num_labels;
581
147k
            tree->num_labels += 2;
582
147k
            if (tree->nodes[test] == MVM_JIT_ANY) {
583
0
                /* assign 'label 3' to the ANY */
584
0
                tree->info[test].label = tree->num_labels++;
585
147k
            } else if (tree->nodes[test] == MVM_JIT_ALL) {
586
41.1k
                /* assign 'label 1' to the ALL */
587
41.1k
                tree->info[test].label = tree->info[node].label;
588
41.1k
            }
589
147k
        }
590
147k
        break;
591
82.4k
    case MVM_JIT_ALL:
592
82.4k
        {
593
82.4k
            MVMint32 nchild = tree->nodes[node+1];
594
82.4k
            MVMint32 i;
595
308k
            for (i = 0; i < nchild; i++) {
596
225k
                MVMint32 test = tree->nodes[node+2+i];
597
225k
                if (tree->nodes[test] == MVM_JIT_ALL) {
598
0
                    /* use same label for child as parent */
599
0
                    tree->info[test].label = tree->info[node].label;
600
225k
                } else if (tree->nodes[test] == MVM_JIT_ANY) {
601
0
                    /* assign an extra label for ANY to short-circuit into */
602
0
                    tree->info[test].label = tree->num_labels++;
603
0
                }
604
225k
            }
605
82.4k
        }
606
82.4k
        break;
607
0
    case MVM_JIT_ANY:
608
0
        {
609
0
            MVMint32 nchild = tree->nodes[node+1];
610
0
            MVMint32 i;
611
0
            for (i = 0; i < nchild; i++) {
612
0
                MVMint32 test = tree->nodes[node+2+i];
613
0
                if (tree->nodes[test] == MVM_JIT_ANY) {
614
0
                    tree->info[test].label = tree->info[node].label;
615
0
                } else if (tree->nodes[test] == MVM_JIT_ALL) {
616
0
                    tree->info[test].label = tree->num_labels++;
617
0
                }
618
0
            }
619
0
        }
620
0
        break;
621
8.70M
    default:
622
8.70M
        break;
623
9.01M
    }
624
9.01M
}
625
626
627
247k
void MVM_jit_expr_tree_analyze(MVMThreadContext *tc, MVMJitExprTree *tree) {
628
247k
    /* analyse the tree, calculate usage and destination information */
629
247k
    MVMJitTreeTraverser traverser;
630
247k
    MVM_VECTOR_ENSURE_SIZE(tree->info, tree->nodes_num);
631
247k
    traverser.policy    = MVM_JIT_TRAVERSER_ONCE;
632
247k
    traverser.data      = NULL;
633
247k
    traverser.preorder  = &assign_labels;
634
247k
    traverser.inorder   = NULL;
635
247k
    traverser.postorder = &analyze_node;
636
247k
    MVM_jit_expr_tree_traverse(tc, tree, &traverser);
637
247k
}
638
639
640
641
/* insert stores for all the active unstored values */
642
static void active_values_flush(MVMThreadContext *tc, MVMJitExprTree *tree,
643
330k
                                struct ValueDefinition *values, MVMint32 num_values) {
644
330k
    MVMint32 i;
645
27.4M
    for (i = 0; i < num_values; i++) {
646
27.1M
        if (values[i].root >= 0) {
647
386k
            tree->roots[values[i].root] = MVM_jit_expr_add_store(
648
386k
                tc, tree, values[i].addr,
649
386k
                values[i].node, MVM_JIT_REG_SZ
650
386k
            );
651
386k
        }
652
27.1M
        if (values[i].node >= 0) {
653
661k
            memset(values + i, -1, sizeof(struct ValueDefinition));
654
661k
        }
655
27.1M
    }
656
330k
}
657
658
659
/* TODO add labels to the expression tree */
660
280k
MVMJitExprTree * MVM_jit_expr_tree_build(MVMThreadContext *tc, MVMJitGraph *jg, MVMSpeshIterator *iter) {
661
280k
    MVMSpeshGraph *sg = jg->sg;
662
280k
    MVMSpeshIns *entry = iter->ins;
663
280k
    MVMSpeshIns *ins;
664
280k
    MVMJitExprTree *tree;
665
280k
    MVMint32 operands[MVM_MAX_OPERANDS];
666
280k
    struct ValueDefinition *values;
667
280k
    MVMint32 root, node;
668
280k
    MVMuint16 i;
669
280k
    /* No instructions, just skip */
670
280k
    if (!iter->ins)
671
0
        return NULL;
672
280k
673
280k
    /* Make the tree */
674
280k
    tree = MVM_malloc(sizeof(MVMJitExprTree));
675
280k
    MVM_VECTOR_INIT(tree->nodes, 256);
676
280k
    MVM_VECTOR_INIT(tree->info,  256);
677
280k
    MVM_VECTOR_INIT(tree->roots, 16);
678
280k
679
280k
    /* ensure that all references are nonzero */
680
280k
    MVM_VECTOR_PUSH(tree->nodes, MVM_JIT_NOOP);
681
280k
682
280k
    tree->graph      = jg;
683
280k
    tree->num_labels = 0;
684
280k
    /* Hold indices to the node that last computed a value belonging
685
280k
     * to a register. Initialized as -1 to indicate that these
686
280k
     * values are empty. */
687
280k
    values = MVM_malloc(sizeof(struct ValueDefinition)*sg->num_locals);
688
280k
    memset(values, -1, sizeof(struct ValueDefinition)*sg->num_locals);
689
280k
690
4.61M
#define BAIL(x, ...) do { if (x) { MVM_jit_log(tc, __VA_ARGS__); goto done; } } while (0)
691
280k
692
280k
    /* Generate a tree based on templates. The basic idea is to keep a
693
280k
       index to the node that last computed the value of a local.
694
280k
       Each opcode is translated to the expression using a template,
695
280k
       which is a): filled with nodes coming from operands and b):
696
280k
       internally linked together (relative to absolute indexes).
697
280k
       Afterwards stores are inserted for computed values. */
698
280k
699
1.59M
    for (ins = iter->ins; ins != NULL; ins = MVM_spesh_iterator_next_ins(tc, iter)) {
700
1.39M
        /* NB - we probably will want to involve the spesh info in selecting a
701
1.39M
           template. And for optimisation, I'd like to copy spesh facts (if any)
702
1.39M
           to the tree info */
703
1.39M
        MVMuint16 opcode = ins->info->opcode;
704
1.39M
        MVMSpeshAnn *ann;
705
1.39M
        const MVMJitExprTemplate *template;
706
1.39M
        MVMint32 before_label = -1, after_label = -1, store_directly = 0;
707
1.39M
708
1.39M
        struct ValueDefinition *defined_value = NULL;
709
1.39M
710
1.39M
        /* check if this is a getlex and if we can handle it */
711
1.39M
        BAIL(opcode == MVM_OP_getlex && getlex_needs_autoviv(tc, jg, ins), "Can't compile object getlex");
712
1.39M
        BAIL(opcode == MVM_OP_bindlex && bindlex_needs_write_barrier(tc, jg, ins), "Can't compile write-barrier bindlex");
713
1.39M
714
1.39M
        /* Check annotations that may require handling or wrapping the expression */
715
1.63M
        for (ann = ins->annotations; ann != NULL; ann = ann->next) {
716
257k
            MVMint32 idx;
717
257k
            switch (ann->type) {
718
17.1k
            case MVM_SPESH_ANN_FH_START:
719
17.1k
                /* start of a frame handler (inclusive). We need to mark this
720
17.1k
                 * instruction with a label so that we know the handler covers
721
17.1k
                 * this code */
722
17.1k
                before_label = MVM_jit_label_before_ins(tc, jg, iter->bb, ins);
723
17.1k
                jg->handlers[ann->data.frame_handler_index].start_label = before_label;
724
17.1k
                break;
725
15.3k
            case MVM_SPESH_ANN_FH_END:
726
15.3k
                /* end of the frame handler (exclusive), funnily enough not
727
15.3k
                 * necessarily the end of a basic block. */
728
15.3k
                before_label = MVM_jit_label_before_ins(tc, jg, iter->bb, ins);
729
15.3k
                jg->handlers[ann->data.frame_handler_index].end_label = before_label;
730
15.3k
                break;
731
17.1k
            case MVM_SPESH_ANN_FH_GOTO:
732
17.1k
                /* A label to jump to for when a handler catches an
733
17.1k
                 * exception. Thus, this can be a control flow entry point (and
734
17.1k
                 * should be the start of a basic block, but I'm not sure if it
735
17.1k
                 * always is).  */
736
17.1k
                before_label = MVM_jit_label_before_ins(tc, jg, iter->bb, ins);
737
17.1k
                jg->handlers[ann->data.frame_handler_index].goto_label = before_label;
738
17.1k
                active_values_flush(tc, tree, values, sg->num_locals);
739
17.1k
                break;
740
4.68k
            case MVM_SPESH_ANN_DEOPT_OSR:
741
4.68k
                /* A label the OSR can jump into to 'start running', so to
742
4.68k
                 * speak. As it breaks the basic-block assumption, arguably,
743
4.68k
                 * this should only ever be at the start of a basic block. But
744
4.68k
                 * it's not. So we have to insert the label and compute it. */
745
4.68k
                before_label = MVM_jit_label_before_ins(tc, jg, iter->bb, ins);
746
4.68k
                /* OSR reuses the deopt label mechanism */
747
4.68k
                MVM_VECTOR_ENSURE_SIZE(jg->deopts, idx = jg->deopts_num++);
748
4.68k
                jg->deopts[idx].label = before_label;
749
4.68k
                jg->deopts[idx].idx   = ann->data.deopt_idx;
750
4.68k
                /* possible entrypoint, so flush intermediates */
751
4.68k
                active_values_flush(tc, tree, values, sg->num_locals);
752
4.68k
                break;
753
8.56k
            case MVM_SPESH_ANN_INLINE_START:
754
8.56k
                /* start of an inline, used for reconstructing state when deoptimizing */
755
8.56k
                before_label = MVM_jit_label_before_ins(tc, jg, iter->bb, ins);
756
8.56k
                jg->inlines[ann->data.inline_idx].start_label = before_label;
757
8.56k
                break;
758
6.78k
            case MVM_SPESH_ANN_INLINE_END:
759
6.78k
                /* end of the inline (inclusive), so we need to add a label,
760
6.78k
                 * which should be the end of the basic block. */
761
6.78k
                after_label = MVM_jit_label_after_ins(tc, jg, iter->bb, ins);
762
6.78k
                jg->inlines[ann->data.inline_idx].end_label = after_label;
763
6.78k
                break;
764
32.5k
            case MVM_SPESH_ANN_DEOPT_INLINE:
765
32.5k
                MVM_jit_log(tc, "Not sure if we can handle DEOPT_INLINE on instruction %s\n", ins->info->name);
766
32.5k
                break;
767
118k
            case MVM_SPESH_ANN_DEOPT_ONE_INS:
768
118k
                /* we should only see this in guards, which we don't do just
769
118k
                 * yet, although we will. At the very least, this implies a flush. */
770
118k
                switch (opcode) {
771
12.0k
                case MVM_OP_sp_guard:
772
12.0k
                case MVM_OP_sp_guardconc:
773
12.0k
                case MVM_OP_sp_guardtype:
774
12.0k
                case MVM_OP_sp_guardsf:
775
12.0k
                    BAIL(1, "Cannot handle DEOPT_ONE (ins=%s)\n", ins->info->name);
776
0
                    break;
777
118k
                }
778
106k
                break;
779
0
            case MVM_SPESH_ANN_DEOPT_ALL_INS:
780
0
                /* don't expect to be handling these, either, but these also
781
0
                 * might need a label-after-the-fact */
782
0
                after_label = MVM_jit_label_after_ins(tc, jg, iter->bb, ins);
783
0
                /* ensure a consistent state for deoptimization */
784
0
                active_values_flush(tc, tree, values, sg->num_locals);
785
0
                /* add deopt idx */
786
0
                MVM_VECTOR_ENSURE_SIZE(jg->deopts, idx = jg->deopts_num++);
787
0
                jg->deopts[idx].label = after_label;
788
0
                jg->deopts[idx].idx   = ann->data.deopt_idx;
789
0
                break;
790
257k
            }
791
257k
        }
792
1.39M
793
1.39M
794
1.38M
        if (opcode == MVM_SSA_PHI || opcode == MVM_OP_no_op) {
795
641k
            /* By definition, a PHI node can only occur at the start of a basic
796
641k
             * block. (A no_op instruction only seems to happen as the very
797
641k
             * first instruction of a frame, and I'm not sure why).
798
641k
             *
799
641k
             * Thus, if it happens that we've processed annotations on those
800
641k
             * instructions (which probably means they migrated there from
801
641k
             * somewhere else), they always refer to the start of the basic
802
641k
             * block, which is already assigned a label and
803
641k
             * dynamic-control-handler.
804
641k
             *
805
641k
             * So we never need to do anything with this label and wrapper, but
806
641k
             * we do need to process the annotation to setup the frame handler
807
641k
             * correctly.
808
641k
             */
809
641k
            BAIL(after_label >= 0, "A PHI node should not have an after label");
810
641k
            continue;
811
641k
        }
812
1.38M
813
739k
        template = MVM_jit_get_template_for_opcode(opcode);
814
739k
        BAIL(template == NULL, "Cannot get template for: %s\n", ins->info->name);
815
739k
816
676k
        check_template(tc, template, ins);
817
676k
818
676k
        MVM_jit_expr_load_operands(tc, tree, ins, values, operands);
819
676k
        root = MVM_jit_expr_apply_template(tc, tree, template, operands);
820
676k
821
676k
        /* root is highest node by construction, so we don't have to check the size of info later */
822
676k
        MVM_VECTOR_ENSURE_SIZE(tree->info, root);
823
676k
        tree->info[root].spesh_ins = ins;
824
676k
825
676k
826
676k
        /* mark operand types */
827
2.08M
        for (i = 0; i < ins->info->num_operands; i++) {
828
1.40M
            MVMint8 opr_kind = ins->info->operands[i];
829
1.40M
            MVMint8 opr_type = opr_kind & MVM_operand_type_mask;
830
1.40M
            MVMSpeshOperand opr = ins->operands[i];
831
1.40M
            if (opr_type == MVM_operand_type_var) {
832
283k
                switch (opr_kind & MVM_operand_rw_mask) {
833
283k
                case MVM_operand_read_reg:
834
283k
                case MVM_operand_write_reg:
835
283k
                    opr_type = MVM_spesh_get_reg_type(tc, sg, opr.reg.orig) << 3; /* shift up 3 to match operand type */
836
283k
                    break;
837
32
                case MVM_operand_read_lex:
838
32
                case MVM_operand_write_lex:
839
32
                    opr_type = MVM_spesh_get_lex_type(tc, sg, opr.lex.outers, opr.lex.idx) << 3;
840
32
                    break;
841
283k
                }
842
283k
            }
843
1.40M
            switch(opr_kind & MVM_operand_rw_mask) {
844
525k
            case MVM_operand_read_reg:
845
525k
            case MVM_operand_read_lex:
846
525k
                tree->info[operands[i]].opr_type = opr_type;
847
525k
                break;
848
531k
            case MVM_operand_write_reg:
849
531k
                /* for write_reg and write_lex, operands[i] is the *address*,
850
531k
                 * the *value* is the root, but this is only valid if the
851
531k
                 * operand index is 0 */
852
531k
                if (template->flags & MVM_JIT_EXPR_TEMPLATE_DESTRUCTIVE) {
853
101k
                    /* overrides any earlier definition of this local variable */
854
101k
                    memset(values + opr.reg.orig, -1, sizeof(struct ValueDefinition));
855
430k
                } else {
856
430k
                    /* record this value, should be only one for the root */
857
430k
                    BAIL(i != 0, "Write reg operand %d", i);
858
430k
                    tree->info[root].opr_type  = opr_type;
859
430k
                    defined_value = values + opr.reg.orig;
860
430k
                    defined_value->addr = operands[i];
861
430k
                    defined_value->node = root;
862
430k
                    /* this overwrites any previous definition */
863
430k
                    defined_value->root = -1;
864
430k
                }
865
531k
                break;
866
32
            case MVM_operand_write_lex:
867
32
                /* does not define a value we can look up, but we may need to
868
32
                 * insert a store */
869
32
                if (!(template->flags & MVM_JIT_EXPR_TEMPLATE_DESTRUCTIVE)) {
870
0
                    BAIL(i != 0, "Write lex operand %d", i);
871
0
                    tree->info[root].opr_type = opr_type;
872
0
                    /* insert the store to lexicals directly, do not record as value */
873
0
                    root = MVM_jit_expr_add_store(tc, tree, operands[i], root, MVM_JIT_REG_SZ);
874
0
                }
875
32
                break;
876
1.40M
            }
877
1.40M
        }
878
676k
879
676k
880
676k
881
676k
882
676k
        if (ins->info->jittivity & (MVM_JIT_INFO_THROWISH | MVM_JIT_INFO_INVOKISH)) {
883
60.7k
            /* NB: we should make this a template-level flag; should be possible
884
60.7k
             * to replace an invokish version with a non-invokish version (but
885
60.7k
             * perhaps best if that is opt-in so people don't accidentally
886
60.7k
             * forget to set it). */
887
60.7k
            MVM_jit_log(tc, "EXPR: adding throwish guard to op (%s)\n", ins->info->name);
888
60.7k
            active_values_flush(tc, tree, values, sg->num_locals);
889
60.7k
            store_directly = 1;
890
60.7k
        }
891
676k
892
676k
893
676k
        /* Add root to tree to ensure source evaluation order, wrapped with
894
676k
         * labels if necessary. */
895
676k
        if (before_label >= 0 && MVM_jit_label_is_for_ins(tc, jg, before_label)) {
896
5.44k
            MVM_VECTOR_PUSH(tree->roots, MVM_jit_expr_add_label(tc, tree, before_label));
897
5.44k
        }
898
676k
899
676k
        /* NB: GUARD only wraps void nodes. Currently, we replace any
900
676k
         * value-yielding node with it's STORE (and thereby make sure it is
901
676k
         * flushed directly) */
902
676k
        if (store_directly && defined_value != NULL) {
903
0
            /* If we're wrapping this template and it defines a value, we
904
0
             * had maybe better flush it directly */
905
0
            root = MVM_jit_expr_add_store(tc, tree, defined_value->addr, root, MVM_JIT_REG_SZ);
906
0
            defined_value = NULL;
907
0
        }
908
676k
909
676k
        if (defined_value != NULL) {
910
430k
            defined_value->root = tree->roots_num;
911
430k
        }
912
676k
913
676k
        MVM_VECTOR_PUSH(tree->roots, root);
914
676k
        if (after_label >= 0 && MVM_jit_label_is_for_ins(tc, jg, after_label)) {
915
0
            MVM_VECTOR_PUSH(tree->roots, MVM_jit_expr_add_label(tc, tree, after_label));
916
0
        }
917
676k
    }
918
280k
919
280k
 done:
920
280k
    if (tree->roots_num > 0) {
921
247k
        active_values_flush(tc, tree, values, sg->num_locals);
922
247k
        MVM_jit_expr_tree_analyze(tc, tree);
923
247k
        MVM_jit_log(tc, "Build tree out of: [");
924
1.53M
        for (ins = entry; ins != iter->ins; ins = ins->next) {
925
1.28M
            if (ins->info->opcode == MVM_SSA_PHI)
926
610k
                continue;
927
676k
            MVM_jit_log(tc, "%s, ", ins->info->name);
928
676k
        }
929
247k
        MVM_jit_log(tc, "]\n");
930
32.6k
    } else {
931
32.6k
        /* Don't return empty trees, nobody wants that */
932
32.6k
        MVM_jit_expr_tree_destroy(tc, tree);
933
32.6k
        tree = NULL;
934
32.6k
    }
935
280k
    MVM_free(values);
936
280k
    return tree;
937
280k
}
938
939
269k
void MVM_jit_expr_tree_destroy(MVMThreadContext *tc, MVMJitExprTree *tree) {
940
269k
    if (tree->info)
941
269k
        MVM_free(tree->info);
942
269k
    MVM_free(tree->nodes);
943
269k
    MVM_free(tree->roots);
944
269k
    MVM_free(tree);
945
269k
}
946
947
static void walk_tree(MVMThreadContext *tc, MVMJitExprTree *tree,
948
30.1M
                 MVMJitTreeTraverser *traverser, MVMint32 node) {
949
30.1M
    const MVMJitExprOpInfo *info = MVM_jit_expr_op_info(tc, tree->nodes[node]);
950
30.1M
    MVMint32 nchild = info->nchild;
951
30.1M
    MVMint32 first_child = node + 1;
952
30.1M
    MVMint32 i;
953
30.1M
    if (traverser->policy == MVM_JIT_TRAVERSER_ONCE &&
954
30.1M
        traverser->visits[node] >= 1)
955
3.38M
        return;
956
30.1M
957
26.7M
    traverser->visits[node]++;
958
26.7M
    /* visiting on the way down - NB want to add visitation information */
959
26.7M
    if (traverser->preorder)
960
18.0M
        traverser->preorder(tc, traverser, tree, node);
961
26.7M
    if (nchild < 0) {
962
1.54M
        /* Variadic case: take first child as constant signifying the
963
1.54M
         * number of children. Increment because the 'real' children now
964
1.54M
         * start node later */
965
1.54M
        nchild = tree->nodes[first_child++];
966
1.54M
    }
967
54.8M
    for (i = 0; i < nchild; i++) {
968
28.1M
        /* Enter child node */
969
28.1M
        walk_tree(tc, tree, traverser, tree->nodes[first_child+i]);
970
28.1M
        if (traverser->inorder) {
971
9.47M
            traverser->inorder(tc, traverser, tree, node, i);
972
9.47M
        }
973
28.1M
    }
974
26.7M
    if (traverser->postorder) {
975
26.7M
        traverser->postorder(tc, traverser, tree, node);
976
26.7M
    }
977
26.7M
}
978
979
/* TODO specify revisiting policy */
980
void MVM_jit_expr_tree_traverse(MVMThreadContext *tc, MVMJitExprTree *tree,
981
721k
                                MVMJitTreeTraverser *traverser) {
982
721k
    MVMint32 i;
983
721k
    MVM_VECTOR_INIT(traverser->visits, tree->nodes_num);
984
2.71M
    for (i = 0; i < tree->roots_num; i++) {
985
1.99M
        /* TODO deal with nodes with multiple entries */
986
1.99M
        walk_tree(tc, tree, traverser, tree->roots[i]);
987
1.99M
    }
988
721k
    MVM_free(traverser->visits);
989
721k
}
990
991
992
16.5M
#define FIRST_CHILD(t,x) (t->info[x].op_info->nchild < 0 ? x + 2 : x + 1)
993
/* Walk tree to get nodes along a path */
994
MVMint32 MVM_jit_expr_tree_get_nodes(MVMThreadContext *tc, MVMJitExprTree *tree,
995
                                     MVMint32 node, const char *path,
996
4.89M
                                     MVMJitExprNode *buffer) {
997
4.89M
    MVMJitExprNode *ptr = buffer;
998
14.7M
    while (*path) {
999
9.88M
        MVMJitExprNode cur_node = node;
1000
16.5M
        do {
1001
16.5M
            MVMint32 first_child = FIRST_CHILD(tree, cur_node) - 1;
1002
16.5M
            MVMint32 child_nr    = *path++ - '0';
1003
16.5M
            cur_node = tree->nodes[first_child+child_nr];
1004
16.5M
        } while (*path != '.');
1005
9.88M
        /* regs nodes go to values, others to args */
1006
9.88M
        *ptr++ = cur_node;
1007
9.88M
        path++;
1008
9.88M
    }
1009
4.89M
    return ptr - buffer;
1010
4.89M
}
1011
#undef FIRST_CHILD