@samitouri / QOSamiQemu
Code Commits Issues Pulls Sessions CI/CD
master
master
c 3,346 lines 89.5 KB
Raw
1 /*
2 * Optimizations for Tiny Code Generator for QEMU
3 *
4 * Copyright (c) 2010 Samsung Electronics.
5 * Contributed by Kirill Batuzov <batuzovk@ispras.ru>
6 *
7 * Permission is hereby granted, free of charge, to any person obtaining a copy
8 * of this software and associated documentation files (the "Software"), to deal
9 * in the Software without restriction, including without limitation the rights
10 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
11 * copies of the Software, and to permit persons to whom the Software is
12 * furnished to do so, subject to the following conditions:
13 *
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
18 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
19 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
20 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
21 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
22 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
23 * THE SOFTWARE.
24 */
25
26 #include "qemu/osdep.h"
27 #include "qemu/int128.h"
28 #include "qemu/interval-tree.h"
29 #include "tcg/tcg-op-common.h"
30 #include "tcg-internal.h"
31 #include "tcg-has.h"
32
33
34 typedef struct MemCopyInfo {
35 IntervalTreeNode itree;
36 QSIMPLEQ_ENTRY (MemCopyInfo) next;
37 TCGTemp *ts;
38 TCGType type;
39 } MemCopyInfo;
40
41 typedef struct TempOptInfo {
42 TCGTemp *prev_copy;
43 TCGTemp *next_copy;
44 QSIMPLEQ_HEAD(, MemCopyInfo) mem_copy;
45 uint64_t z_mask; /* mask bit is 0 if and only if value bit is 0 */
46 uint64_t o_mask; /* mask bit is 1 if and only if value bit is 1 */
47 uint64_t s_mask; /* mask bit is 1 if value bit matches msb */
48 } TempOptInfo;
49
50 typedef struct OptContext {
51 TCGContext *tcg;
52 TCGOp *prev_mb;
53 TCGTempSet temps_used;
54
55 IntervalTreeRoot mem_copy;
56 QSIMPLEQ_HEAD(, MemCopyInfo) mem_free;
57
58 /* In flight values from optimization. */
59 TCGType type;
60 int carry_state; /* -1 = non-constant, {0,1} = constant carry-in */
61 } OptContext;
62
63 static inline TempOptInfo *ts_info(TCGTemp *ts)
64 {
65 return ts->state_ptr;
66 }
67
68 static inline TempOptInfo *arg_info(TCGArg arg)
69 {
70 return ts_info(arg_temp(arg));
71 }
72
73 static inline bool ti_is_const(TempOptInfo *ti)
74 {
75 /* If all bits that are not known zeros are known ones, it's constant. */
76 return ti->z_mask == ti->o_mask;
77 }
78
79 static inline uint64_t ti_const_val(TempOptInfo *ti)
80 {
81 /* If constant, both z_mask and o_mask contain the value. */
82 return ti->z_mask;
83 }
84
85 static inline bool ti_is_const_val(TempOptInfo *ti, uint64_t val)
86 {
87 return ti_is_const(ti) && ti_const_val(ti) == val;
88 }
89
90 static inline bool ts_is_const(TCGTemp *ts)
91 {
92 return ti_is_const(ts_info(ts));
93 }
94
95 static inline bool ts_is_const_val(TCGTemp *ts, uint64_t val)
96 {
97 return ti_is_const_val(ts_info(ts), val);
98 }
99
100 static inline bool arg_is_const(TCGArg arg)
101 {
102 return ts_is_const(arg_temp(arg));
103 }
104
105 static inline uint64_t arg_const_val(TCGArg arg)
106 {
107 return ti_const_val(arg_info(arg));
108 }
109
110 static inline bool arg_is_const_val(TCGArg arg, uint64_t val)
111 {
112 return ts_is_const_val(arg_temp(arg), val);
113 }
114
115 static inline bool ts_is_copy(TCGTemp *ts)
116 {
117 return ts_info(ts)->next_copy != ts;
118 }
119
120 static TCGTemp *cmp_better_copy(TCGTemp *a, TCGTemp *b)
121 {
122 return a->kind < b->kind ? b : a;
123 }
124
125 /* Initialize and activate a temporary. */
126 static void init_ts_info(OptContext *ctx, TCGTemp *ts)
127 {
128 size_t idx = temp_idx(ts);
129 TempOptInfo *ti;
130
131 if (test_bit(idx, ctx->temps_used.l)) {
132 return;
133 }
134 set_bit(idx, ctx->temps_used.l);
135
136 ti = ts->state_ptr;
137 if (ti == NULL) {
138 ti = tcg_malloc(sizeof(TempOptInfo));
139 ts->state_ptr = ti;
140 }
141
142 ti->next_copy = ts;
143 ti->prev_copy = ts;
144 QSIMPLEQ_INIT(&ti->mem_copy);
145 if (ts->kind == TEMP_CONST) {
146 ti->z_mask = ts->val;
147 ti->o_mask = ts->val;
148 ti->s_mask = INT64_MIN >> clrsb64(ts->val);
149 } else {
150 ti->z_mask = -1;
151 ti->o_mask = 0;
152 ti->s_mask = 0;
153 }
154 }
155
156 static MemCopyInfo *mem_copy_first(OptContext *ctx, intptr_t s, intptr_t l)
157 {
158 IntervalTreeNode *r = interval_tree_iter_first(&ctx->mem_copy, s, l);
159 return r ? container_of(r, MemCopyInfo, itree) : NULL;
160 }
161
162 static MemCopyInfo *mem_copy_next(MemCopyInfo *mem, intptr_t s, intptr_t l)
163 {
164 IntervalTreeNode *r = interval_tree_iter_next(&mem->itree, s, l);
165 return r ? container_of(r, MemCopyInfo, itree) : NULL;
166 }
167
168 static void remove_mem_copy(OptContext *ctx, MemCopyInfo *mc)
169 {
170 TCGTemp *ts = mc->ts;
171 TempOptInfo *ti = ts_info(ts);
172
173 interval_tree_remove(&mc->itree, &ctx->mem_copy);
174 QSIMPLEQ_REMOVE(&ti->mem_copy, mc, MemCopyInfo, next);
175 QSIMPLEQ_INSERT_TAIL(&ctx->mem_free, mc, next);
176 }
177
178 static void remove_mem_copy_in(OptContext *ctx, intptr_t s, intptr_t l)
179 {
180 while (true) {
181 MemCopyInfo *mc = mem_copy_first(ctx, s, l);
182 if (!mc) {
183 break;
184 }
185 remove_mem_copy(ctx, mc);
186 }
187 }
188
189 static void remove_mem_copy_all(OptContext *ctx)
190 {
191 remove_mem_copy_in(ctx, 0, -1);
192 tcg_debug_assert(interval_tree_is_empty(&ctx->mem_copy));
193 }
194
195 static TCGTemp *find_better_copy(TCGTemp *ts)
196 {
197 TCGTemp *i, *ret;
198
199 /* If this is already readonly, we can't do better. */
200 if (temp_readonly(ts)) {
201 return ts;
202 }
203
204 ret = ts;
205 for (i = ts_info(ts)->next_copy; i != ts; i = ts_info(i)->next_copy) {
206 ret = cmp_better_copy(ret, i);
207 }
208 return ret;
209 }
210
211 static void move_mem_copies(TCGTemp *dst_ts, TCGTemp *src_ts)
212 {
213 TempOptInfo *si = ts_info(src_ts);
214 TempOptInfo *di = ts_info(dst_ts);
215 MemCopyInfo *mc;
216
217 QSIMPLEQ_FOREACH(mc, &si->mem_copy, next) {
218 tcg_debug_assert(mc->ts == src_ts);
219 mc->ts = dst_ts;
220 }
221 QSIMPLEQ_CONCAT(&di->mem_copy, &si->mem_copy);
222 }
223
224 /* Reset TEMP's state, possibly removing the temp for the list of copies. */
225 static void reset_ts(OptContext *ctx, TCGTemp *ts)
226 {
227 TempOptInfo *ti = ts_info(ts);
228 TCGTemp *pts = ti->prev_copy;
229 TCGTemp *nts = ti->next_copy;
230 TempOptInfo *pi = ts_info(pts);
231 TempOptInfo *ni = ts_info(nts);
232
233 ni->prev_copy = ti->prev_copy;
234 pi->next_copy = ti->next_copy;
235 ti->next_copy = ts;
236 ti->prev_copy = ts;
237 ti->z_mask = -1;
238 ti->o_mask = 0;
239 ti->s_mask = 0;
240
241 if (!QSIMPLEQ_EMPTY(&ti->mem_copy)) {
242 if (ts == nts) {
243 /* Last temp copy being removed, the mem copies die. */
244 MemCopyInfo *mc;
245 QSIMPLEQ_FOREACH(mc, &ti->mem_copy, next) {
246 interval_tree_remove(&mc->itree, &ctx->mem_copy);
247 }
248 QSIMPLEQ_CONCAT(&ctx->mem_free, &ti->mem_copy);
249 } else {
250 move_mem_copies(find_better_copy(nts), ts);
251 }
252 }
253 }
254
255 static void reset_temp(OptContext *ctx, TCGArg arg)
256 {
257 reset_ts(ctx, arg_temp(arg));
258 }
259
260 static void record_mem_copy(OptContext *ctx, TCGType type,
261 TCGTemp *ts, intptr_t start, intptr_t last)
262 {
263 MemCopyInfo *mc;
264 TempOptInfo *ti;
265
266 mc = QSIMPLEQ_FIRST(&ctx->mem_free);
267 if (mc) {
268 QSIMPLEQ_REMOVE_HEAD(&ctx->mem_free, next);
269 } else {
270 mc = tcg_malloc(sizeof(*mc));
271 }
272
273 memset(mc, 0, sizeof(*mc));
274 mc->itree.start = start;
275 mc->itree.last = last;
276 mc->type = type;
277 interval_tree_insert(&mc->itree, &ctx->mem_copy);
278
279 ts = find_better_copy(ts);
280 ti = ts_info(ts);
281 mc->ts = ts;
282 QSIMPLEQ_INSERT_TAIL(&ti->mem_copy, mc, next);
283 }
284
285 static bool ts_are_copies(TCGTemp *ts1, TCGTemp *ts2)
286 {
287 TCGTemp *i;
288
289 if (ts1 == ts2) {
290 return true;
291 }
292
293 if (!ts_is_copy(ts1) || !ts_is_copy(ts2)) {
294 return false;
295 }
296
297 for (i = ts_info(ts1)->next_copy; i != ts1; i = ts_info(i)->next_copy) {
298 if (i == ts2) {
299 return true;
300 }
301 }
302
303 return false;
304 }
305
306 static bool args_are_copies(TCGArg arg1, TCGArg arg2)
307 {
308 return ts_are_copies(arg_temp(arg1), arg_temp(arg2));
309 }
310
311 static TCGTemp *find_mem_copy_for(OptContext *ctx, TCGType type, intptr_t s)
312 {
313 MemCopyInfo *mc;
314
315 for (mc = mem_copy_first(ctx, s, s); mc; mc = mem_copy_next(mc, s, s)) {
316 if (mc->itree.start == s && mc->type == type) {
317 return find_better_copy(mc->ts);
318 }
319 }
320 return NULL;
321 }
322
323 static TCGArg arg_new_constant(OptContext *ctx, uint64_t val)
324 {
325 TCGType type = ctx->type;
326 TCGTemp *ts;
327
328 if (type == TCG_TYPE_I32) {
329 val = (int32_t)val;
330 }
331
332 ts = tcg_constant_internal(type, val);
333 init_ts_info(ctx, ts);
334
335 return temp_arg(ts);
336 }
337
338 static TCGArg arg_new_temp(OptContext *ctx)
339 {
340 TCGTemp *ts = tcg_temp_new_internal(ctx->type, TEMP_EBB);
341 init_ts_info(ctx, ts);
342 return temp_arg(ts);
343 }
344
345 static TCGOp *opt_insert_after(OptContext *ctx, TCGOp *op,
346 TCGOpcode opc, unsigned narg)
347 {
348 return tcg_op_insert_after(ctx->tcg, op, opc, ctx->type, narg);
349 }
350
351 static TCGOp *opt_insert_before(OptContext *ctx, TCGOp *op,
352 TCGOpcode opc, unsigned narg)
353 {
354 return tcg_op_insert_before(ctx->tcg, op, opc, ctx->type, narg);
355 }
356
357 static bool tcg_opt_gen_mov(OptContext *ctx, TCGOp *op, TCGArg dst, TCGArg src)
358 {
359 TCGTemp *dst_ts = arg_temp(dst);
360 TCGTemp *src_ts = arg_temp(src);
361 TempOptInfo *di;
362 TempOptInfo *si;
363 TCGOpcode new_op;
364
365 if (ts_are_copies(dst_ts, src_ts)) {
366 tcg_op_remove(ctx->tcg, op);
367 return true;
368 }
369
370 reset_ts(ctx, dst_ts);
371 di = ts_info(dst_ts);
372 si = ts_info(src_ts);
373
374 switch (ctx->type) {
375 case TCG_TYPE_I32:
376 case TCG_TYPE_I64:
377 new_op = INDEX_op_mov;
378 break;
379 case TCG_TYPE_V64:
380 case TCG_TYPE_V128:
381 case TCG_TYPE_V256:
382 /* TCGOP_TYPE and TCGOP_VECE remain unchanged. */
383 new_op = INDEX_op_mov_vec;
384 break;
385 default:
386 g_assert_not_reached();
387 }
388 op->opc = new_op;
389 op->args[0] = dst;
390 op->args[1] = src;
391
392 di->z_mask = si->z_mask;
393 di->o_mask = si->o_mask;
394 di->s_mask = si->s_mask;
395
396 if (src_ts->type == dst_ts->type) {
397 TempOptInfo *ni = ts_info(si->next_copy);
398
399 di->next_copy = si->next_copy;
400 di->prev_copy = src_ts;
401 ni->prev_copy = dst_ts;
402 si->next_copy = dst_ts;
403
404 if (!QSIMPLEQ_EMPTY(&si->mem_copy)
405 && cmp_better_copy(src_ts, dst_ts) == dst_ts) {
406 move_mem_copies(dst_ts, src_ts);
407 }
408 } else if (dst_ts->type == TCG_TYPE_I32) {
409 di->z_mask = (int32_t)di->z_mask;
410 di->o_mask = (int32_t)di->o_mask;
411 di->s_mask |= INT32_MIN;
412 } else {
413 di->z_mask |= MAKE_64BIT_MASK(32, 32);
414 di->o_mask = (uint32_t)di->o_mask;
415 di->s_mask = INT64_MIN;
416 }
417 return true;
418 }
419
420 static bool tcg_opt_gen_movi(OptContext *ctx, TCGOp *op,
421 TCGArg dst, uint64_t val)
422 {
423 /* Convert movi to mov with constant temp. */
424 return tcg_opt_gen_mov(ctx, op, dst, arg_new_constant(ctx, val));
425 }
426
427 static uint64_t do_constant_folding_2(TCGOpcode op, TCGType type,
428 uint64_t x, uint64_t y)
429 {
430 uint64_t l64, h64;
431
432 switch (op) {
433 case INDEX_op_add:
434 return x + y;
435
436 case INDEX_op_sub:
437 return x - y;
438
439 case INDEX_op_mul:
440 return x * y;
441
442 case INDEX_op_and:
443 case INDEX_op_and_vec:
444 return x & y;
445
446 case INDEX_op_or:
447 case INDEX_op_or_vec:
448 return x | y;
449
450 case INDEX_op_xor:
451 case INDEX_op_xor_vec:
452 return x ^ y;
453
454 case INDEX_op_shl:
455 if (type == TCG_TYPE_I32) {
456 return (uint32_t)x << (y & 31);
457 }
458 return (uint64_t)x << (y & 63);
459
460 case INDEX_op_shr:
461 if (type == TCG_TYPE_I32) {
462 return (uint32_t)x >> (y & 31);
463 }
464 return (uint64_t)x >> (y & 63);
465
466 case INDEX_op_sar:
467 if (type == TCG_TYPE_I32) {
468 return (int32_t)x >> (y & 31);
469 }
470 return (int64_t)x >> (y & 63);
471
472 case INDEX_op_rotr:
473 if (type == TCG_TYPE_I32) {
474 return ror32(x, y & 31);
475 }
476 return ror64(x, y & 63);
477
478 case INDEX_op_rotl:
479 if (type == TCG_TYPE_I32) {
480 return rol32(x, y & 31);
481 }
482 return rol64(x, y & 63);
483
484 case INDEX_op_not:
485 case INDEX_op_not_vec:
486 return ~x;
487
488 case INDEX_op_neg:
489 return -x;
490
491 case INDEX_op_andc:
492 case INDEX_op_andc_vec:
493 return x & ~y;
494
495 case INDEX_op_orc:
496 case INDEX_op_orc_vec:
497 return x | ~y;
498
499 case INDEX_op_eqv:
500 case INDEX_op_eqv_vec:
501 return ~(x ^ y);
502
503 case INDEX_op_nand:
504 case INDEX_op_nand_vec:
505 return ~(x & y);
506
507 case INDEX_op_nor:
508 case INDEX_op_nor_vec:
509 return ~(x | y);
510
511 case INDEX_op_clz:
512 if (type == TCG_TYPE_I32) {
513 return (uint32_t)x ? clz32(x) : y;
514 }
515 return x ? clz64(x) : y;
516
517 case INDEX_op_ctz:
518 if (type == TCG_TYPE_I32) {
519 return (uint32_t)x ? ctz32(x) : y;
520 }
521 return x ? ctz64(x) : y;
522
523 case INDEX_op_ctpop:
524 return type == TCG_TYPE_I32 ? ctpop32(x) : ctpop64(x);
525
526 case INDEX_op_bswap16:
527 x = bswap16(x);
528 return y & TCG_BSWAP_OS ? (int16_t)x : x;
529
530 case INDEX_op_bswap32:
531 x = bswap32(x);
532 return y & TCG_BSWAP_OS ? (int32_t)x : x;
533
534 case INDEX_op_bswap64:
535 return bswap64(x);
536
537 case INDEX_op_revbit8:
538 /* Note the host-utils.h revbit8 operates on uint8_t. */
539 if (type == TCG_TYPE_I32) {
540 return bswap32(revbit32(x));
541 }
542 return bswap64(revbit64(x));
543
544 case INDEX_op_revbit32:
545 x = revbit32(x);
546 return y & TCG_BSWAP_OS ? (int32_t)x : x;
547
548 case INDEX_op_revbit64:
549 return revbit64(x);
550
551 case INDEX_op_ext_i32_i64:
552 return (int32_t)x;
553
554 case INDEX_op_extu_i32_i64:
555 case INDEX_op_extrl_i64_i32:
556 return (uint32_t)x;
557
558 case INDEX_op_extrh_i64_i32:
559 return (uint64_t)x >> 32;
560
561 case INDEX_op_muluh:
562 if (type == TCG_TYPE_I32) {
563 return ((uint64_t)(uint32_t)x * (uint32_t)y) >> 32;
564 }
565 mulu64(&l64, &h64, x, y);
566 return h64;
567
568 case INDEX_op_mulsh:
569 if (type == TCG_TYPE_I32) {
570 return ((int64_t)(int32_t)x * (int32_t)y) >> 32;
571 }
572 muls64(&l64, &h64, x, y);
573 return h64;
574
575 case INDEX_op_divs:
576 /* Avoid crashing on divide by zero, otherwise undefined. */
577 if (type == TCG_TYPE_I32) {
578 return (int32_t)x / ((int32_t)y ? : 1);
579 }
580 return (int64_t)x / ((int64_t)y ? : 1);
581
582 case INDEX_op_divu:
583 if (type == TCG_TYPE_I32) {
584 return (uint32_t)x / ((uint32_t)y ? : 1);
585 }
586 return (uint64_t)x / ((uint64_t)y ? : 1);
587
588 case INDEX_op_rems:
589 if (type == TCG_TYPE_I32) {
590 return (int32_t)x % ((int32_t)y ? : 1);
591 }
592 return (int64_t)x % ((int64_t)y ? : 1);
593
594 case INDEX_op_remu:
595 if (type == TCG_TYPE_I32) {
596 return (uint32_t)x % ((uint32_t)y ? : 1);
597 }
598 return (uint64_t)x % ((uint64_t)y ? : 1);
599
600 case INDEX_op_smax:
601 if (type == TCG_TYPE_I32) {
602 return MAX((int32_t)x, (int32_t)y);
603 }
604 return MAX((int64_t)x, (int64_t)y);
605
606 case INDEX_op_smin:
607 if (type == TCG_TYPE_I32) {
608 return MIN((int32_t)x, (int32_t)y);
609 }
610 return MIN((int64_t)x, (int64_t)y);
611
612 case INDEX_op_umax:
613 if (type == TCG_TYPE_I32) {
614 return MAX((uint32_t)x, (uint32_t)y);
615 }
616 return MAX((uint64_t)x, (uint64_t)y);
617
618 case INDEX_op_umin:
619 if (type == TCG_TYPE_I32) {
620 return MIN((uint32_t)x, (uint32_t)y);
621 }
622 return MIN((uint64_t)x, (uint64_t)y);
623
624 default:
625 g_assert_not_reached();
626 }
627 }
628
629 static uint64_t do_constant_folding(TCGOpcode op, TCGType type,
630 uint64_t x, uint64_t y)
631 {
632 uint64_t res = do_constant_folding_2(op, type, x, y);
633 if (type == TCG_TYPE_I32) {
634 res = (int32_t)res;
635 }
636 return res;
637 }
638
639 static bool do_constant_folding_cond_32(uint32_t x, uint32_t y, TCGCond c)
640 {
641 switch (c) {
642 case TCG_COND_EQ:
643 return x == y;
644 case TCG_COND_NE:
645 return x != y;
646 case TCG_COND_LT:
647 return (int32_t)x < (int32_t)y;
648 case TCG_COND_GE:
649 return (int32_t)x >= (int32_t)y;
650 case TCG_COND_LE:
651 return (int32_t)x <= (int32_t)y;
652 case TCG_COND_GT:
653 return (int32_t)x > (int32_t)y;
654 case TCG_COND_LTU:
655 return x < y;
656 case TCG_COND_GEU:
657 return x >= y;
658 case TCG_COND_LEU:
659 return x <= y;
660 case TCG_COND_GTU:
661 return x > y;
662 case TCG_COND_TSTEQ:
663 return (x & y) == 0;
664 case TCG_COND_TSTNE:
665 return (x & y) != 0;
666 case TCG_COND_ALWAYS:
667 case TCG_COND_NEVER:
668 break;
669 }
670 g_assert_not_reached();
671 }
672
673 static bool do_constant_folding_cond_64(uint64_t x, uint64_t y, TCGCond c)
674 {
675 switch (c) {
676 case TCG_COND_EQ:
677 return x == y;
678 case TCG_COND_NE:
679 return x != y;
680 case TCG_COND_LT:
681 return (int64_t)x < (int64_t)y;
682 case TCG_COND_GE:
683 return (int64_t)x >= (int64_t)y;
684 case TCG_COND_LE:
685 return (int64_t)x <= (int64_t)y;
686 case TCG_COND_GT:
687 return (int64_t)x > (int64_t)y;
688 case TCG_COND_LTU:
689 return x < y;
690 case TCG_COND_GEU:
691 return x >= y;
692 case TCG_COND_LEU:
693 return x <= y;
694 case TCG_COND_GTU:
695 return x > y;
696 case TCG_COND_TSTEQ:
697 return (x & y) == 0;
698 case TCG_COND_TSTNE:
699 return (x & y) != 0;
700 case TCG_COND_ALWAYS:
701 case TCG_COND_NEVER:
702 break;
703 }
704 g_assert_not_reached();
705 }
706
707 static int do_constant_folding_cond_eq(TCGCond c)
708 {
709 switch (c) {
710 case TCG_COND_GT:
711 case TCG_COND_LTU:
712 case TCG_COND_LT:
713 case TCG_COND_GTU:
714 case TCG_COND_NE:
715 return 0;
716 case TCG_COND_GE:
717 case TCG_COND_GEU:
718 case TCG_COND_LE:
719 case TCG_COND_LEU:
720 case TCG_COND_EQ:
721 return 1;
722 case TCG_COND_TSTEQ:
723 case TCG_COND_TSTNE:
724 return -1;
725 case TCG_COND_ALWAYS:
726 case TCG_COND_NEVER:
727 break;
728 }
729 g_assert_not_reached();
730 }
731
732 /*
733 * Return -1 if the condition can't be simplified,
734 * and the result of the condition (0 or 1) if it can.
735 */
736 static int do_constant_folding_cond(TCGType type, TCGArg x,
737 TCGArg y, TCGCond c)
738 {
739 if (arg_is_const(x) && arg_is_const(y)) {
740 uint64_t xv = arg_const_val(x);
741 uint64_t yv = arg_const_val(y);
742
743 switch (type) {
744 case TCG_TYPE_I32:
745 return do_constant_folding_cond_32(xv, yv, c);
746 case TCG_TYPE_I64:
747 return do_constant_folding_cond_64(xv, yv, c);
748 default:
749 /* Only scalar comparisons are optimizable */
750 return -1;
751 }
752 } else if (args_are_copies(x, y)) {
753 return do_constant_folding_cond_eq(c);
754 } else if (arg_is_const_val(y, 0)) {
755 switch (c) {
756 case TCG_COND_LTU:
757 case TCG_COND_TSTNE:
758 return 0;
759 case TCG_COND_GEU:
760 case TCG_COND_TSTEQ:
761 return 1;
762 default:
763 return -1;
764 }
765 }
766 return -1;
767 }
768
769 /**
770 * swap_commutative:
771 * @dest: TCGArg of the destination argument, or NO_DEST.
772 * @p1: first paired argument
773 * @p2: second paired argument
774 *
775 * If *@p1 is a constant and *@p2 is not, swap.
776 * If *@p2 matches @dest, swap.
777 * Return true if a swap was performed.
778 */
779
780 #define NO_DEST temp_arg(NULL)
781
782 static int pref_commutative(TempOptInfo *ti)
783 {
784 /* Slight preference for non-zero constants second. */
785 return !ti_is_const(ti) ? 0 : ti_const_val(ti) ? 3 : 2;
786 }
787
788 static bool swap_commutative(TCGArg dest, TCGArg *p1, TCGArg *p2)
789 {
790 TCGArg a1 = *p1, a2 = *p2;
791 int sum = 0;
792 sum += pref_commutative(arg_info(a1));
793 sum -= pref_commutative(arg_info(a2));
794
795 /* Prefer the constant in second argument, and then the form
796 op a, a, b, which is better handled on non-RISC hosts. */
797 if (sum > 0 || (sum == 0 && dest == a2)) {
798 *p1 = a2;
799 *p2 = a1;
800 return true;
801 }
802 return false;
803 }
804
805 /*
806 * Return -1 if the condition can't be simplified,
807 * and the result of the condition (0 or 1) if it can.
808 */
809 static bool fold_and(OptContext *ctx, TCGOp *op);
810 static int do_constant_folding_cond1(OptContext *ctx, TCGOp *op, TCGArg dest,
811 TCGArg *p1, TCGArg *p2, TCGArg *pcond)
812 {
813 TCGCond cond;
814 TempOptInfo *i1;
815 bool swap;
816 int r;
817
818 swap = swap_commutative(dest, p1, p2);
819 cond = *pcond;
820 if (swap) {
821 *pcond = cond = tcg_swap_cond(cond);
822 }
823
824 r = do_constant_folding_cond(ctx->type, *p1, *p2, cond);
825 if (r >= 0) {
826 return r;
827 }
828 if (!is_tst_cond(cond)) {
829 return -1;
830 }
831
832 i1 = arg_info(*p1);
833
834 /*
835 * TSTNE x,x -> NE x,0
836 * TSTNE x,i -> NE x,0 if i includes all nonzero bits of x
837 */
838 if (args_are_copies(*p1, *p2) ||
839 (arg_is_const(*p2) && (i1->z_mask & ~arg_const_val(*p2)) == 0)) {
840 *p2 = arg_new_constant(ctx, 0);
841 *pcond = tcg_tst_eqne_cond(cond);
842 return -1;
843 }
844
845 /* TSTNE x,i -> LT x,0 if i only includes sign bit copies */
846 if (arg_is_const(*p2) && (arg_const_val(*p2) & ~i1->s_mask) == 0) {
847 *p2 = arg_new_constant(ctx, 0);
848 *pcond = tcg_tst_ltge_cond(cond);
849 return -1;
850 }
851
852 /* Expand to AND with a temporary if no backend support. */
853 if (!TCG_TARGET_HAS_tst) {
854 TCGOp *op2 = opt_insert_before(ctx, op, INDEX_op_and, 3);
855 TCGArg tmp = arg_new_temp(ctx);
856
857 op2->args[0] = tmp;
858 op2->args[1] = *p1;
859 op2->args[2] = *p2;
860 fold_and(ctx, op2);
861
862 *p1 = tmp;
863 *p2 = arg_new_constant(ctx, 0);
864 *pcond = tcg_tst_eqne_cond(cond);
865 }
866 return -1;
867 }
868
869 static void init_arguments(OptContext *ctx, TCGOp *op, int nb_args)
870 {
871 for (int i = 0; i < nb_args; i++) {
872 TCGTemp *ts = arg_temp(op->args[i]);
873 init_ts_info(ctx, ts);
874 }
875 }
876
877 static void copy_propagate(OptContext *ctx, TCGOp *op,
878 int nb_oargs, int nb_iargs)
879 {
880 for (int i = nb_oargs; i < nb_oargs + nb_iargs; i++) {
881 TCGTemp *ts = arg_temp(op->args[i]);
882 if (ts_is_copy(ts)) {
883 op->args[i] = temp_arg(find_better_copy(ts));
884 }
885 }
886 }
887
888 static void finish_bb(OptContext *ctx)
889 {
890 /* We only optimize memory barriers across basic blocks. */
891 ctx->prev_mb = NULL;
892 }
893
894 static void finish_ebb(OptContext *ctx)
895 {
896 finish_bb(ctx);
897 /* We only optimize across extended basic blocks. */
898 memset(&ctx->temps_used, 0, sizeof(ctx->temps_used));
899 remove_mem_copy_all(ctx);
900 }
901
902 static bool finish_folding(OptContext *ctx, TCGOp *op)
903 {
904 const TCGOpDef *def = &tcg_op_defs[op->opc];
905 int i, nb_oargs;
906
907 nb_oargs = def->nb_oargs;
908 for (i = 0; i < nb_oargs; i++) {
909 TCGTemp *ts = arg_temp(op->args[i]);
910 reset_ts(ctx, ts);
911 }
912 return true;
913 }
914
915 /*
916 * The fold_* functions return true when processing is complete,
917 * usually by folding the operation to a constant or to a copy,
918 * and calling tcg_opt_gen_{mov,movi}. They may do other things,
919 * like collect information about the value produced, for use in
920 * optimizing a subsequent operation.
921 *
922 * These first fold_* functions are all helpers, used by other
923 * folders for more specific operations.
924 */
925
926 static bool fold_const1(OptContext *ctx, TCGOp *op)
927 {
928 if (arg_is_const(op->args[1])) {
929 uint64_t t = arg_const_val(op->args[1]);
930
931 t = do_constant_folding(op->opc, ctx->type, t, 0);
932 return tcg_opt_gen_movi(ctx, op, op->args[0], t);
933 }
934 return false;
935 }
936
937 static bool fold_const2(OptContext *ctx, TCGOp *op)
938 {
939 if (arg_is_const(op->args[1]) && arg_is_const(op->args[2])) {
940 uint64_t t1 = arg_const_val(op->args[1]);
941 uint64_t t2 = arg_const_val(op->args[2]);
942
943 t1 = do_constant_folding(op->opc, ctx->type, t1, t2);
944 return tcg_opt_gen_movi(ctx, op, op->args[0], t1);
945 }
946 return false;
947 }
948
949 static bool fold_commutative(OptContext *ctx, TCGOp *op)
950 {
951 swap_commutative(op->args[0], &op->args[1], &op->args[2]);
952 return false;
953 }
954
955 static bool fold_const2_commutative(OptContext *ctx, TCGOp *op)
956 {
957 swap_commutative(op->args[0], &op->args[1], &op->args[2]);
958 return fold_const2(ctx, op);
959 }
960
961 /*
962 * Record "zero" and "sign" masks for the single output of @op.
963 * See TempOptInfo definition of z_mask and s_mask.
964 * If z_mask allows, fold the output to constant zero.
965 * The passed s_mask may be augmented by z_mask.
966 */
967 static bool fold_masks_zosa_int(OptContext *ctx, TCGOp *op,
968 uint64_t z_mask, uint64_t o_mask,
969 int64_t s_mask, uint64_t a_mask)
970 {
971 const TCGOpDef *def = &tcg_op_defs[op->opc];
972 TCGTemp *ts;
973 TempOptInfo *ti;
974 int rep;
975
976 /* Only single-output opcodes are supported here. */
977 tcg_debug_assert(def->nb_oargs == 1);
978
979 /*
980 * 32-bit ops generate 32-bit results, which for the purpose of
981 * simplifying tcg are sign-extended. Certainly that's how we
982 * represent our constants elsewhere. Note that the bits will
983 * be reset properly for a 64-bit value when encountering the
984 * type changing opcodes.
985 */
986 if (ctx->type == TCG_TYPE_I32) {
987 z_mask = (int32_t)z_mask;
988 o_mask = (int32_t)o_mask;
989 s_mask |= INT32_MIN;
990 a_mask = (uint32_t)a_mask;
991 }
992
993 /* Bits that are known 1 and bits that are known 0 must not overlap. */
994 tcg_debug_assert((o_mask & ~z_mask) == 0);
995
996 /* All bits that are not known zero are known one is a constant. */
997 if (z_mask == o_mask) {
998 return tcg_opt_gen_movi(ctx, op, op->args[0], o_mask);
999 }
1000
1001 /* If no bits are affected, the operation devolves to a copy. */
1002 if (a_mask == 0) {
1003 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]);
1004 }
1005
1006 ts = arg_temp(op->args[0]);
1007 reset_ts(ctx, ts);
1008
1009 ti = ts_info(ts);
1010 ti->z_mask = z_mask;
1011 ti->o_mask = o_mask;
1012
1013 /* Canonicalize s_mask and incorporate data from [zo]_mask. */
1014 rep = clz64(~s_mask);
1015 rep = MAX(rep, clz64(z_mask));
1016 rep = MAX(rep, clz64(~o_mask));
1017 rep = MAX(rep - 1, 0);
1018 ti->s_mask = INT64_MIN >> rep;
1019
1020 return false;
1021 }
1022
1023 static bool fold_masks_zosa(OptContext *ctx, TCGOp *op, uint64_t z_mask,
1024 uint64_t o_mask, int64_t s_mask, uint64_t a_mask)
1025 {
1026 fold_masks_zosa_int(ctx, op, z_mask, o_mask, s_mask, a_mask);
1027 return true;
1028 }
1029
1030 static bool fold_masks_zos(OptContext *ctx, TCGOp *op,
1031 uint64_t z_mask, uint64_t o_mask, uint64_t s_mask)
1032 {
1033 return fold_masks_zosa(ctx, op, z_mask, o_mask, s_mask, -1);
1034 }
1035
1036 static bool fold_masks_zo(OptContext *ctx, TCGOp *op,
1037 uint64_t z_mask, uint64_t o_mask)
1038 {
1039 return fold_masks_zosa(ctx, op, z_mask, o_mask, 0, -1);
1040 }
1041
1042 static bool fold_masks_zs(OptContext *ctx, TCGOp *op,
1043 uint64_t z_mask, uint64_t s_mask)
1044 {
1045 return fold_masks_zosa(ctx, op, z_mask, 0, s_mask, -1);
1046 }
1047
1048 static bool fold_masks_z(OptContext *ctx, TCGOp *op, uint64_t z_mask)
1049 {
1050 return fold_masks_zosa(ctx, op, z_mask, 0, 0, -1);
1051 }
1052
1053 static bool fold_masks_s(OptContext *ctx, TCGOp *op, uint64_t s_mask)
1054 {
1055 return fold_masks_zosa(ctx, op, -1, 0, s_mask, -1);
1056 }
1057
1058 /*
1059 * Convert @op to NOT, if NOT is supported by the host.
1060 * Return true f the conversion is successful, which will still
1061 * indicate that the processing is complete.
1062 */
1063 static bool fold_not(OptContext *ctx, TCGOp *op);
1064 static bool fold_to_not(OptContext *ctx, TCGOp *op, int idx)
1065 {
1066 TCGOpcode not_op;
1067 bool have_not;
1068
1069 switch (ctx->type) {
1070 case TCG_TYPE_I32:
1071 case TCG_TYPE_I64:
1072 not_op = INDEX_op_not;
1073 have_not = tcg_op_supported(INDEX_op_not, ctx->type, 0);
1074 break;
1075 case TCG_TYPE_V64:
1076 case TCG_TYPE_V128:
1077 case TCG_TYPE_V256:
1078 not_op = INDEX_op_not_vec;
1079 have_not = TCG_TARGET_HAS_not_vec;
1080 break;
1081 default:
1082 g_assert_not_reached();
1083 }
1084 if (have_not) {
1085 op->opc = not_op;
1086 op->args[1] = op->args[idx];
1087 return fold_not(ctx, op);
1088 }
1089 return false;
1090 }
1091
1092 /* If the binary operation has first argument @i, fold to @i. */
1093 static bool fold_ix_to_i(OptContext *ctx, TCGOp *op, uint64_t i)
1094 {
1095 if (arg_is_const_val(op->args[1], i)) {
1096 return tcg_opt_gen_movi(ctx, op, op->args[0], i);
1097 }
1098 return false;
1099 }
1100
1101 /* If the binary operation has first argument @i, fold to NOT. */
1102 static bool fold_ix_to_not(OptContext *ctx, TCGOp *op, uint64_t i)
1103 {
1104 if (arg_is_const_val(op->args[1], i)) {
1105 return fold_to_not(ctx, op, 2);
1106 }
1107 return false;
1108 }
1109
1110 /* If the binary operation has second argument @i, fold to @i. */
1111 static bool fold_xi_to_i(OptContext *ctx, TCGOp *op, uint64_t i)
1112 {
1113 if (arg_is_const_val(op->args[2], i)) {
1114 return tcg_opt_gen_movi(ctx, op, op->args[0], i);
1115 }
1116 return false;
1117 }
1118
1119 /* If the binary operation has second argument @i, fold to identity. */
1120 static bool fold_xi_to_x(OptContext *ctx, TCGOp *op, uint64_t i)
1121 {
1122 if (arg_is_const_val(op->args[2], i)) {
1123 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]);
1124 }
1125 return false;
1126 }
1127
1128 /* If the binary operation has second argument @i, fold to NOT. */
1129 static bool fold_xi_to_not(OptContext *ctx, TCGOp *op, uint64_t i)
1130 {
1131 if (arg_is_const_val(op->args[2], i)) {
1132 return fold_to_not(ctx, op, 1);
1133 }
1134 return false;
1135 }
1136
1137 /* If the binary operation has both arguments equal, fold to @i. */
1138 static bool fold_xx_to_i(OptContext *ctx, TCGOp *op, uint64_t i)
1139 {
1140 if (args_are_copies(op->args[1], op->args[2])) {
1141 return tcg_opt_gen_movi(ctx, op, op->args[0], i);
1142 }
1143 return false;
1144 }
1145
1146 /* If the binary operation has both arguments equal, fold to identity. */
1147 static bool fold_xx_to_x(OptContext *ctx, TCGOp *op)
1148 {
1149 if (args_are_copies(op->args[1], op->args[2])) {
1150 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]);
1151 }
1152 return false;
1153 }
1154
1155 /*
1156 * These outermost fold_<op> functions are sorted alphabetically.
1157 *
1158 * The ordering of the transformations should be:
1159 * 1) those that produce a constant
1160 * 2) those that produce a copy
1161 * 3) those that produce information about the result value.
1162 */
1163
1164 static bool fold_addco(OptContext *ctx, TCGOp *op);
1165 static bool fold_or(OptContext *ctx, TCGOp *op);
1166 static bool fold_orc(OptContext *ctx, TCGOp *op);
1167 static bool fold_subbo(OptContext *ctx, TCGOp *op);
1168 static bool fold_xor(OptContext *ctx, TCGOp *op);
1169
1170 static bool fold_add(OptContext *ctx, TCGOp *op)
1171 {
1172 if (fold_const2_commutative(ctx, op) ||
1173 fold_xi_to_x(ctx, op, 0)) {
1174 return true;
1175 }
1176 return finish_folding(ctx, op);
1177 }
1178
1179 /* We cannot as yet do_constant_folding with vectors. */
1180 static bool fold_add_vec(OptContext *ctx, TCGOp *op)
1181 {
1182 if (fold_commutative(ctx, op) ||
1183 fold_xi_to_x(ctx, op, 0)) {
1184 return true;
1185 }
1186 return finish_folding(ctx, op);
1187 }
1188
1189 static void squash_prev_carryout(OptContext *ctx, TCGOp *op)
1190 {
1191 TempOptInfo *t2;
1192
1193 op = QTAILQ_PREV(op, link);
1194 switch (op->opc) {
1195 case INDEX_op_addco:
1196 op->opc = INDEX_op_add;
1197 fold_add(ctx, op);
1198 break;
1199 case INDEX_op_addcio:
1200 op->opc = INDEX_op_addci;
1201 break;
1202 case INDEX_op_addc1o:
1203 op->opc = INDEX_op_add;
1204 t2 = arg_info(op->args[2]);
1205 if (ti_is_const(t2)) {
1206 op->args[2] = arg_new_constant(ctx, ti_const_val(t2) + 1);
1207 /* Perform other constant folding, if needed. */
1208 fold_add(ctx, op);
1209 } else {
1210 TCGArg ret = op->args[0];
1211 op = opt_insert_after(ctx, op, INDEX_op_add, 3);
1212 op->args[0] = ret;
1213 op->args[1] = ret;
1214 op->args[2] = arg_new_constant(ctx, 1);
1215 }
1216 break;
1217 default:
1218 g_assert_not_reached();
1219 }
1220 }
1221
1222 static bool fold_addci(OptContext *ctx, TCGOp *op)
1223 {
1224 fold_commutative(ctx, op);
1225
1226 if (ctx->carry_state < 0) {
1227 return finish_folding(ctx, op);
1228 }
1229
1230 squash_prev_carryout(ctx, op);
1231 op->opc = INDEX_op_add;
1232
1233 if (ctx->carry_state > 0) {
1234 TempOptInfo *t2 = arg_info(op->args[2]);
1235
1236 /*
1237 * Propagate the known carry-in into a constant, if possible.
1238 * Otherwise emit a second add +1.
1239 */
1240 if (ti_is_const(t2)) {
1241 op->args[2] = arg_new_constant(ctx, ti_const_val(t2) + 1);
1242 } else {
1243 TCGOp *op2 = opt_insert_before(ctx, op, INDEX_op_add, 3);
1244
1245 op2->args[0] = op->args[0];
1246 op2->args[1] = op->args[1];
1247 op2->args[2] = op->args[2];
1248 fold_add(ctx, op2);
1249
1250 op->args[1] = op->args[0];
1251 op->args[2] = arg_new_constant(ctx, 1);
1252 }
1253 }
1254
1255 ctx->carry_state = -1;
1256 return fold_add(ctx, op);
1257 }
1258
1259 static bool fold_addcio(OptContext *ctx, TCGOp *op)
1260 {
1261 TempOptInfo *t1, *t2;
1262 int carry_out = -1;
1263 uint64_t sum, max;
1264
1265 fold_commutative(ctx, op);
1266 t1 = arg_info(op->args[1]);
1267 t2 = arg_info(op->args[2]);
1268
1269 /*
1270 * The z_mask value is >= the maximum value that can be represented
1271 * with the known zero bits. So adding the z_mask values will not
1272 * overflow if and only if the true values cannot overflow.
1273 */
1274 if (!uadd64_overflow(t1->z_mask, t2->z_mask, &sum) &&
1275 !uadd64_overflow(sum, ctx->carry_state != 0, &sum)) {
1276 carry_out = 0;
1277 }
1278
1279 if (ctx->carry_state < 0) {
1280 ctx->carry_state = carry_out;
1281 return finish_folding(ctx, op);
1282 }
1283
1284 squash_prev_carryout(ctx, op);
1285 if (ctx->carry_state == 0) {
1286 goto do_addco;
1287 }
1288
1289 /* Propagate the known carry-in into a constant, if possible. */
1290 max = ctx->type == TCG_TYPE_I32 ? UINT32_MAX : UINT64_MAX;
1291 if (ti_is_const(t2)) {
1292 uint64_t v = ti_const_val(t2) & max;
1293 if (v < max) {
1294 op->args[2] = arg_new_constant(ctx, v + 1);
1295 goto do_addco;
1296 }
1297 /* max + known carry in produces known carry out. */
1298 carry_out = 1;
1299 }
1300 if (ti_is_const(t1)) {
1301 uint64_t v = ti_const_val(t1) & max;
1302 if (v < max) {
1303 op->args[1] = arg_new_constant(ctx, v + 1);
1304 goto do_addco;
1305 }
1306 carry_out = 1;
1307 }
1308
1309 /* Adjust the opcode to remember the known carry-in. */
1310 op->opc = INDEX_op_addc1o;
1311 ctx->carry_state = carry_out;
1312 return finish_folding(ctx, op);
1313
1314 do_addco:
1315 op->opc = INDEX_op_addco;
1316 return fold_addco(ctx, op);
1317 }
1318
1319 static bool fold_addco(OptContext *ctx, TCGOp *op)
1320 {
1321 TempOptInfo *t1, *t2;
1322 int carry_out = -1;
1323 uint64_t ign;
1324
1325 fold_commutative(ctx, op);
1326 t1 = arg_info(op->args[1]);
1327 t2 = arg_info(op->args[2]);
1328
1329 if (ti_is_const(t2)) {
1330 uint64_t v2 = ti_const_val(t2);
1331
1332 if (ti_is_const(t1)) {
1333 uint64_t v1 = ti_const_val(t1);
1334 /* Given sign-extension of z_mask for I32, we need not truncate. */
1335 carry_out = uadd64_overflow(v1, v2, &ign);
1336 } else if (v2 == 0) {
1337 carry_out = 0;
1338 }
1339 } else {
1340 /*
1341 * The z_mask value is >= the maximum value that can be represented
1342 * with the known zero bits. So adding the z_mask values will not
1343 * overflow if and only if the true values cannot overflow.
1344 */
1345 if (!uadd64_overflow(t1->z_mask, t2->z_mask, &ign)) {
1346 carry_out = 0;
1347 }
1348 }
1349 ctx->carry_state = carry_out;
1350 return finish_folding(ctx, op);
1351 }
1352
1353 static bool fold_and(OptContext *ctx, TCGOp *op)
1354 {
1355 uint64_t z_mask, o_mask, s_mask, a_mask;
1356 TempOptInfo *t1, *t2;
1357
1358 if (fold_const2_commutative(ctx, op)) {
1359 return true;
1360 }
1361
1362 t1 = arg_info(op->args[1]);
1363 t2 = arg_info(op->args[2]);
1364
1365 z_mask = t1->z_mask & t2->z_mask;
1366 o_mask = t1->o_mask & t2->o_mask;
1367
1368 /*
1369 * Sign repetitions are perforce all identical, whether they are 1 or 0.
1370 * Bitwise operations preserve the relative quantity of the repetitions.
1371 */
1372 s_mask = t1->s_mask & t2->s_mask;
1373
1374 /* Affected bits are those not known zero, masked by those known one. */
1375 a_mask = t1->z_mask & ~t2->o_mask;
1376
1377 if (!fold_masks_zosa_int(ctx, op, z_mask, o_mask, s_mask, a_mask)) {
1378 if (op->opc == INDEX_op_and && ti_is_const(t2)) {
1379 /*
1380 * Canonicalize on extract, if valid. This aids x86 with its
1381 * 2 operand MOVZBL and 2 operand AND, selecting the TCGOpcode
1382 * which does not require matching operands. Other backends can
1383 * trivially expand the extract to AND during code generation.
1384 */
1385 uint64_t val = ti_const_val(t2);
1386 if (!(val & (val + 1))) {
1387 unsigned len = ctz64(~val);
1388 if (TCG_TARGET_extract_valid(ctx->type, 0, len)) {
1389 op->opc = INDEX_op_extract;
1390 op->args[2] = 0;
1391 op->args[3] = len;
1392 }
1393 }
1394 } else {
1395 fold_xx_to_x(ctx, op);
1396 }
1397 }
1398 return true;
1399 }
1400
1401 static bool fold_andc(OptContext *ctx, TCGOp *op)
1402 {
1403 uint64_t z_mask, o_mask, s_mask, a_mask;
1404 TempOptInfo *t1, *t2;
1405
1406 if (fold_const2(ctx, op)) {
1407 return true;
1408 }
1409
1410 t1 = arg_info(op->args[1]);
1411 t2 = arg_info(op->args[2]);
1412
1413 if (ti_is_const(t2)) {
1414 /* Fold andc r,x,i to and r,x,~i. */
1415 switch (ctx->type) {
1416 case TCG_TYPE_I32:
1417 case TCG_TYPE_I64:
1418 op->opc = INDEX_op_and;
1419 break;
1420 case TCG_TYPE_V64:
1421 case TCG_TYPE_V128:
1422 case TCG_TYPE_V256:
1423 op->opc = INDEX_op_and_vec;
1424 break;
1425 default:
1426 g_assert_not_reached();
1427 }
1428 op->args[2] = arg_new_constant(ctx, ~ti_const_val(t2));
1429 return fold_and(ctx, op);
1430 }
1431 if (fold_xx_to_i(ctx, op, 0) ||
1432 fold_ix_to_not(ctx, op, -1)) {
1433 return true;
1434 }
1435
1436 z_mask = t1->z_mask & ~t2->o_mask;
1437 o_mask = t1->o_mask & ~t2->z_mask;
1438 s_mask = t1->s_mask & t2->s_mask;
1439
1440 /* Affected bits are those not known zero, masked by those known zero. */
1441 a_mask = t1->z_mask & t2->z_mask;
1442
1443 return fold_masks_zosa(ctx, op, z_mask, o_mask, s_mask, a_mask);
1444 }
1445
1446 static bool fold_bitsel_vec(OptContext *ctx, TCGOp *op)
1447 {
1448 /* If true and false values are the same, eliminate the cmp. */
1449 if (args_are_copies(op->args[2], op->args[3])) {
1450 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[2]);
1451 }
1452
1453 if (arg_is_const(op->args[2]) && arg_is_const(op->args[3])) {
1454 uint64_t tv = arg_const_val(op->args[2]);
1455 uint64_t fv = arg_const_val(op->args[3]);
1456
1457 if (tv == -1 && fv == 0) {
1458 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]);
1459 }
1460 if (tv == 0 && fv == -1) {
1461 if (TCG_TARGET_HAS_not_vec) {
1462 op->opc = INDEX_op_not_vec;
1463 return fold_not(ctx, op);
1464 } else {
1465 op->opc = INDEX_op_xor_vec;
1466 op->args[2] = arg_new_constant(ctx, -1);
1467 return fold_xor(ctx, op);
1468 }
1469 }
1470 }
1471 if (arg_is_const(op->args[2])) {
1472 uint64_t tv = arg_const_val(op->args[2]);
1473 if (tv == -1) {
1474 op->opc = INDEX_op_or_vec;
1475 op->args[2] = op->args[3];
1476 return fold_or(ctx, op);
1477 }
1478 if (tv == 0 && TCG_TARGET_HAS_andc_vec) {
1479 op->opc = INDEX_op_andc_vec;
1480 op->args[2] = op->args[1];
1481 op->args[1] = op->args[3];
1482 return fold_andc(ctx, op);
1483 }
1484 }
1485 if (arg_is_const(op->args[3])) {
1486 uint64_t fv = arg_const_val(op->args[3]);
1487 if (fv == 0) {
1488 op->opc = INDEX_op_and_vec;
1489 return fold_and(ctx, op);
1490 }
1491 if (fv == -1 && TCG_TARGET_HAS_orc_vec) {
1492 TCGArg ta = op->args[2];
1493 op->opc = INDEX_op_orc_vec;
1494 op->args[2] = op->args[1];
1495 op->args[1] = ta;
1496 return fold_orc(ctx, op);
1497 }
1498 }
1499 return finish_folding(ctx, op);
1500 }
1501
1502 static bool fold_brcond(OptContext *ctx, TCGOp *op)
1503 {
1504 int i = do_constant_folding_cond1(ctx, op, NO_DEST, &op->args[0],
1505 &op->args[1], &op->args[2]);
1506 if (i == 0) {
1507 tcg_op_remove(ctx->tcg, op);
1508 return true;
1509 }
1510 if (i > 0) {
1511 op->opc = INDEX_op_br;
1512 op->args[0] = op->args[3];
1513 finish_ebb(ctx);
1514 } else {
1515 finish_bb(ctx);
1516 }
1517 return true;
1518 }
1519
1520 static bool fold_bswap(OptContext *ctx, TCGOp *op)
1521 {
1522 uint64_t z_mask, o_mask, s_mask;
1523 TempOptInfo *t1 = arg_info(op->args[1]);
1524 int flags = 0;
1525
1526 switch (op->opc) {
1527 case INDEX_op_bswap16:
1528 flags = op->args[2];
1529 s_mask = INT16_MIN;
1530 break;
1531 case INDEX_op_bswap32:
1532 case INDEX_op_revbit32:
1533 flags = op->args[2];
1534 s_mask = INT32_MIN;
1535 break;
1536 case INDEX_op_bswap64:
1537 case INDEX_op_revbit8:
1538 case INDEX_op_revbit64:
1539 s_mask = 0;
1540 break;
1541 default:
1542 g_assert_not_reached();
1543 }
1544
1545 if (ti_is_const(t1)) {
1546 return tcg_opt_gen_movi(ctx, op, op->args[0],
1547 do_constant_folding(op->opc, ctx->type,
1548 ti_const_val(t1), flags));
1549 }
1550
1551 z_mask = do_constant_folding(op->opc, ctx->type, t1->z_mask, flags);
1552 o_mask = do_constant_folding(op->opc, ctx->type, t1->o_mask, flags);
1553
1554 if (flags & TCG_BSWAP_OS) {
1555 /* s_mask set */
1556 } else {
1557 if (!(flags & TCG_BSWAP_OZ)) {
1558 z_mask |= s_mask << 1;
1559 }
1560 s_mask = 0;
1561 }
1562
1563 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
1564 }
1565
1566 static bool fold_call(OptContext *ctx, TCGOp *op)
1567 {
1568 TCGContext *s = ctx->tcg;
1569 int nb_oargs = TCGOP_CALLO(op);
1570 int nb_iargs = TCGOP_CALLI(op);
1571 int flags, i;
1572
1573 init_arguments(ctx, op, nb_oargs + nb_iargs);
1574 copy_propagate(ctx, op, nb_oargs, nb_iargs);
1575
1576 /* If the function reads or writes globals, reset temp data. */
1577 flags = tcg_call_flags(op);
1578 if (!(flags & (TCG_CALL_NO_READ_GLOBALS | TCG_CALL_NO_WRITE_GLOBALS))) {
1579 int nb_globals = s->nb_globals;
1580
1581 for (i = 0; i < nb_globals; i++) {
1582 if (test_bit(i, ctx->temps_used.l)) {
1583 reset_ts(ctx, &ctx->tcg->temps[i]);
1584 }
1585 }
1586 }
1587
1588 /* If the function has side effects, reset mem data. */
1589 if (!(flags & TCG_CALL_NO_SIDE_EFFECTS)) {
1590 remove_mem_copy_all(ctx);
1591 }
1592
1593 /* Reset temp data for outputs. */
1594 for (i = 0; i < nb_oargs; i++) {
1595 reset_temp(ctx, op->args[i]);
1596 }
1597
1598 /* Stop optimizing MB across calls. */
1599 ctx->prev_mb = NULL;
1600 return true;
1601 }
1602
1603 static bool fold_cmp_vec(OptContext *ctx, TCGOp *op)
1604 {
1605 /* Canonicalize the comparison to put immediate second. */
1606 if (swap_commutative(NO_DEST, &op->args[1], &op->args[2])) {
1607 op->args[3] = tcg_swap_cond(op->args[3]);
1608 }
1609 return finish_folding(ctx, op);
1610 }
1611
1612 static bool fold_cmpsel_vec(OptContext *ctx, TCGOp *op)
1613 {
1614 /* If true and false values are the same, eliminate the cmp. */
1615 if (args_are_copies(op->args[3], op->args[4])) {
1616 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[3]);
1617 }
1618
1619 /* Canonicalize the comparison to put immediate second. */
1620 if (swap_commutative(NO_DEST, &op->args[1], &op->args[2])) {
1621 op->args[5] = tcg_swap_cond(op->args[5]);
1622 }
1623 /*
1624 * Canonicalize the "false" input reg to match the destination,
1625 * so that the tcg backend can implement "move if true".
1626 */
1627 if (swap_commutative(op->args[0], &op->args[4], &op->args[3])) {
1628 op->args[5] = tcg_invert_cond(op->args[5]);
1629 }
1630 return finish_folding(ctx, op);
1631 }
1632
1633 static bool fold_count_zeros(OptContext *ctx, TCGOp *op)
1634 {
1635 uint64_t z_mask, s_mask;
1636 TempOptInfo *t1 = arg_info(op->args[1]);
1637 TempOptInfo *t2 = arg_info(op->args[2]);
1638
1639 if (ti_is_const(t1)) {
1640 uint64_t t = ti_const_val(t1);
1641
1642 if (t != 0) {
1643 t = do_constant_folding(op->opc, ctx->type, t, 0);
1644 return tcg_opt_gen_movi(ctx, op, op->args[0], t);
1645 }
1646 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[2]);
1647 }
1648
1649 switch (ctx->type) {
1650 case TCG_TYPE_I32:
1651 z_mask = 31;
1652 break;
1653 case TCG_TYPE_I64:
1654 z_mask = 63;
1655 break;
1656 default:
1657 g_assert_not_reached();
1658 }
1659 s_mask = ~z_mask;
1660 z_mask |= t2->z_mask;
1661 s_mask &= t2->s_mask;
1662
1663 return fold_masks_zs(ctx, op, z_mask, s_mask);
1664 }
1665
1666 static bool fold_ctpop(OptContext *ctx, TCGOp *op)
1667 {
1668 uint64_t z_mask;
1669
1670 if (fold_const1(ctx, op)) {
1671 return true;
1672 }
1673
1674 switch (ctx->type) {
1675 case TCG_TYPE_I32:
1676 z_mask = 32 | 31;
1677 break;
1678 case TCG_TYPE_I64:
1679 z_mask = 64 | 63;
1680 break;
1681 default:
1682 g_assert_not_reached();
1683 }
1684 return fold_masks_z(ctx, op, z_mask);
1685 }
1686
1687 static bool fold_deposit(OptContext *ctx, TCGOp *op)
1688 {
1689 TCGArg ret = op->args[0];
1690 TCGArg arg1 = op->args[1];
1691 TCGArg arg2 = op->args[2];
1692 int ofs = op->args[3];
1693 int len = op->args[4];
1694 TempOptInfo *t1 = arg_info(arg1);
1695 TempOptInfo *t2 = arg_info(arg2);
1696 int width;
1697 uint64_t z_mask, o_mask, s_mask, type_mask, len_mask;
1698 TCGOp *op2;
1699 bool valid;
1700
1701 if (ti_is_const(t1) && ti_is_const(t2)) {
1702 return tcg_opt_gen_movi(ctx, op, op->args[0],
1703 deposit64(ti_const_val(t1), ofs, len,
1704 ti_const_val(t2)));
1705 }
1706
1707 width = 8 * tcg_type_size(ctx->type);
1708 type_mask = MAKE_64BIT_MASK(0, width);
1709 len_mask = MAKE_64BIT_MASK(0, len);
1710
1711 /* Inserting all-zero into a value. */
1712 if ((t2->z_mask & len_mask) == 0) {
1713 op->opc = INDEX_op_and;
1714 op->args[2] = arg_new_constant(ctx, ~(len_mask << ofs));
1715 return fold_and(ctx, op);
1716 }
1717
1718 /* Inserting all-one into a value. */
1719 if ((t2->o_mask & len_mask) == len_mask) {
1720 op->opc = INDEX_op_or;
1721 op->args[2] = arg_new_constant(ctx, len_mask << ofs);
1722 return fold_or(ctx, op);
1723 }
1724
1725 valid = TCG_TARGET_deposit_valid(ctx->type, ofs, len);
1726
1727 /* Lower invalid deposit of constant as AND + OR. */
1728 if (!valid && ti_is_const(t2)) {
1729 uint64_t ins_val = (ti_const_val(t2) & len_mask) << ofs;
1730
1731 op2 = opt_insert_before(ctx, op, INDEX_op_and, 3);
1732 op2->args[0] = ret;
1733 op2->args[1] = arg1;
1734 op2->args[2] = arg_new_constant(ctx, ~(len_mask << ofs));
1735 fold_and(ctx, op2);
1736
1737 op->opc = INDEX_op_or;
1738 op->args[1] = ret;
1739 op->args[2] = arg_new_constant(ctx, ins_val);
1740 return fold_or(ctx, op);
1741 }
1742
1743 /*
1744 * Compute result masks before calling other fold_* subroutines
1745 * which could modify the masks of our inputs.
1746 */
1747 z_mask = deposit64(t1->z_mask, ofs, len, t2->z_mask);
1748 o_mask = deposit64(t1->o_mask, ofs, len, t2->o_mask);
1749 if (ofs + len < width) {
1750 s_mask = t1->s_mask & ~MAKE_64BIT_MASK(0, ofs + len);
1751 } else {
1752 s_mask = t2->s_mask << ofs;
1753 }
1754
1755 /* Inserting a value into zero. */
1756 if (ti_is_const_val(t1, 0)) {
1757 uint64_t need_mask;
1758
1759 /* Always lower deposit into zero at 0 as AND. */
1760 if (ofs == 0) {
1761 op->opc = INDEX_op_and;
1762 op->args[1] = arg2;
1763 op->args[2] = arg_new_constant(ctx, len_mask);
1764 return fold_and(ctx, op);
1765 }
1766
1767 /*
1768 * If the portion of the value outside len that remains after
1769 * shifting is zero, we can elide the mask and just shift.
1770 */
1771 need_mask = t2->z_mask & ~len_mask;
1772 need_mask = (need_mask << ofs) & type_mask;
1773 if (!need_mask) {
1774 op->opc = INDEX_op_shl;
1775 op->args[1] = arg2;
1776 op->args[2] = arg_new_constant(ctx, ofs);
1777 goto done;
1778 }
1779
1780 /* Lower invalid deposit into zero as AND + SHL or SHL + SHR. */
1781 if (!valid) {
1782 if (TCG_TARGET_extract_valid(ctx->type, 0, len)) {
1783 /* EXTRACT (at 0) + SHL */
1784 op2 = opt_insert_before(ctx, op, INDEX_op_extract, 4);
1785 op2->args[0] = ret;
1786 op2->args[1] = arg2;
1787 op2->args[2] = 0;
1788 op2->args[3] = len;
1789 } else if (tcg_op_imm_match(INDEX_op_and, ctx->type, len_mask)) {
1790 /* AND + SHL */
1791 op2 = opt_insert_before(ctx, op, INDEX_op_and, 3);
1792 op2->args[0] = ret;
1793 op2->args[1] = arg2;
1794 op2->args[2] = arg_new_constant(ctx, len_mask);
1795 } else {
1796 /* SHL + SHR */
1797 int shl = width - len;
1798 int shr = width - len - ofs;
1799
1800 op2 = opt_insert_before(ctx, op, INDEX_op_shl, 3);
1801 op2->args[0] = ret;
1802 op2->args[1] = arg2;
1803 op2->args[2] = arg_new_constant(ctx, shl);
1804
1805 op->opc = INDEX_op_shr;
1806 op->args[1] = ret;
1807 op->args[2] = arg_new_constant(ctx, shr);
1808 goto done;
1809 }
1810
1811 /* Finish the (EXTRACT|AND) + SHL cases. */
1812 op->opc = INDEX_op_shl;
1813 op->args[1] = ret;
1814 op->args[2] = arg_new_constant(ctx, ofs);
1815 goto done;
1816 }
1817 }
1818
1819 /* After special cases, lower invalid deposit. */
1820 if (!valid) {
1821 TCGArg tmp;
1822
1823 if (tcg_op_supported(INDEX_op_extract2, ctx->type, 0)) {
1824 if (ofs == 0 && tcg_op_supported(INDEX_op_rotl, ctx->type, 0)) {
1825 /*
1826 * ret = arg2:arg1 >> len
1827 * ret = rotl(ret, len)
1828 */
1829 op2 = opt_insert_before(ctx, op, INDEX_op_extract2, 4);
1830 op2->args[0] = ret;
1831 op2->args[1] = arg1;
1832 op2->args[2] = arg2;
1833 op2->args[3] = len;
1834
1835 op->opc = INDEX_op_rotl;
1836 op->args[1] = ret;
1837 op->args[2] = arg_new_constant(ctx, len);
1838 goto done;
1839 }
1840 if (ofs + len == width) {
1841 /*
1842 * tmp = arg1 << len
1843 * ret = arg2:tmp >> len
1844 */
1845 tmp = ret == arg2 ? arg_new_temp(ctx) : ret;
1846
1847 op2 = opt_insert_before(ctx, op, INDEX_op_shl, 4);
1848 op2->args[0] = tmp;
1849 op2->args[1] = arg1;
1850 op2->args[2] = arg_new_constant(ctx, len);
1851
1852 op->opc = INDEX_op_extract2;
1853 op->args[0] = ret;
1854 op->args[1] = tmp;
1855 op->args[2] = arg2;
1856 op->args[3] = len;
1857 goto done;
1858 }
1859 }
1860
1861 /*
1862 * tmp = arg2 & mask
1863 * ret = arg1 & ~(mask << ofs)
1864 * tmp = tmp << ofs
1865 * ret = ret | tmp
1866 */
1867 tmp = arg_new_temp(ctx);
1868
1869 op2 = opt_insert_before(ctx, op, INDEX_op_and, 3);
1870 op2->args[0] = tmp;
1871 op2->args[1] = arg2;
1872 op2->args[2] = arg_new_constant(ctx, len_mask);
1873 fold_and(ctx, op2);
1874
1875 op2 = opt_insert_before(ctx, op, INDEX_op_shl, 3);
1876 op2->args[0] = tmp;
1877 op2->args[1] = tmp;
1878 op2->args[2] = arg_new_constant(ctx, ofs);
1879
1880 op2 = opt_insert_before(ctx, op, INDEX_op_and, 3);
1881 op2->args[0] = ret;
1882 op2->args[1] = arg1;
1883 op2->args[2] = arg_new_constant(ctx, ~(len_mask << ofs));
1884 fold_and(ctx, op2);
1885
1886 op->opc = INDEX_op_or;
1887 op->args[1] = ret;
1888 op->args[2] = tmp;
1889 }
1890
1891 done:
1892 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
1893 }
1894
1895 static bool fold_divide(OptContext *ctx, TCGOp *op)
1896 {
1897 if (fold_const2(ctx, op) ||
1898 fold_xi_to_x(ctx, op, 1)) {
1899 return true;
1900 }
1901 return finish_folding(ctx, op);
1902 }
1903
1904 static bool fold_dup(OptContext *ctx, TCGOp *op)
1905 {
1906 if (arg_is_const(op->args[1])) {
1907 uint64_t t = arg_const_val(op->args[1]);
1908 t = dup_const(TCGOP_VECE(op), t);
1909 return tcg_opt_gen_movi(ctx, op, op->args[0], t);
1910 }
1911 return finish_folding(ctx, op);
1912 }
1913
1914 static bool fold_eqv(OptContext *ctx, TCGOp *op)
1915 {
1916 uint64_t z_mask, o_mask, s_mask;
1917 TempOptInfo *t1, *t2;
1918
1919 if (fold_const2_commutative(ctx, op)) {
1920 return true;
1921 }
1922
1923 t2 = arg_info(op->args[2]);
1924 if (ti_is_const(t2)) {
1925 /* Fold eqv r,x,i to xor r,x,~i. */
1926 switch (ctx->type) {
1927 case TCG_TYPE_I32:
1928 case TCG_TYPE_I64:
1929 op->opc = INDEX_op_xor;
1930 break;
1931 case TCG_TYPE_V64:
1932 case TCG_TYPE_V128:
1933 case TCG_TYPE_V256:
1934 op->opc = INDEX_op_xor_vec;
1935 break;
1936 default:
1937 g_assert_not_reached();
1938 }
1939 op->args[2] = arg_new_constant(ctx, ~ti_const_val(t2));
1940 return fold_xor(ctx, op);
1941 }
1942
1943 t1 = arg_info(op->args[1]);
1944
1945 z_mask = (t1->z_mask | ~t2->o_mask) & (t2->z_mask | ~t1->o_mask);
1946 o_mask = ~(t1->z_mask | t2->z_mask) | (t1->o_mask & t2->o_mask);
1947 s_mask = t1->s_mask & t2->s_mask;
1948
1949 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
1950 }
1951
1952 static bool fold_extract(OptContext *ctx, TCGOp *op)
1953 {
1954 uint64_t z_mask, o_mask, a_mask;
1955 TempOptInfo *t1 = arg_info(op->args[1]);
1956 int pos = op->args[2];
1957 int len = op->args[3];
1958
1959 if (ti_is_const(t1)) {
1960 return tcg_opt_gen_movi(ctx, op, op->args[0],
1961 extract64(ti_const_val(t1), pos, len));
1962 }
1963
1964 z_mask = extract64(t1->z_mask, pos, len);
1965 o_mask = extract64(t1->o_mask, pos, len);
1966 a_mask = pos ? -1 : t1->z_mask ^ z_mask;
1967
1968 return fold_masks_zosa(ctx, op, z_mask, o_mask, 0, a_mask);
1969 }
1970
1971 static bool fold_extract2(OptContext *ctx, TCGOp *op)
1972 {
1973 TempOptInfo *t1 = arg_info(op->args[1]);
1974 TempOptInfo *t2 = arg_info(op->args[2]);
1975 uint64_t z1 = t1->z_mask;
1976 uint64_t z2 = t2->z_mask;
1977 uint64_t o1 = t1->o_mask;
1978 uint64_t o2 = t2->o_mask;
1979 uint64_t zr, or;
1980 int shr = op->args[3];
1981 int shl;
1982
1983 if (ctx->type == TCG_TYPE_I32) {
1984 z1 = (uint32_t)z1 >> shr;
1985 o1 = (uint32_t)o1 >> shr;
1986 shl = 32 - shr;
1987 z2 = (uint64_t)((int32_t)z2 << shl);
1988 o2 = (uint64_t)((int32_t)o2 << shl);
1989 } else {
1990 z1 >>= shr;
1991 o1 >>= shr;
1992 shl = 64 - shr;
1993 z2 <<= shl;
1994 o2 <<= shl;
1995 }
1996 zr = z1 | z2;
1997 or = o1 | o2;
1998
1999 if (zr == or) {
2000 return tcg_opt_gen_movi(ctx, op, op->args[0], zr);
2001 }
2002
2003 if (z2 == 0) {
2004 /* High part zeros folds to simple right shift. */
2005 op->opc = INDEX_op_shr;
2006 op->args[2] = arg_new_constant(ctx, shr);
2007 } else if (z1 == 0) {
2008 /* Low part zeros folds to simple left shift. */
2009 op->opc = INDEX_op_shl;
2010 op->args[1] = op->args[2];
2011 op->args[2] = arg_new_constant(ctx, shl);
2012 } else if (!tcg_op_supported(INDEX_op_extract2, ctx->type, 0)) {
2013 TCGArg tmp = arg_new_temp(ctx);
2014 TCGOp *op2 = opt_insert_before(ctx, op, INDEX_op_shr, 3);
2015
2016 op2->args[0] = tmp;
2017 op2->args[1] = op->args[1];
2018 op2->args[2] = arg_new_constant(ctx, shr);
2019
2020 if (TCG_TARGET_deposit_valid(ctx->type, shl, shr)) {
2021 /*
2022 * Deposit has more arguments than extract2,
2023 * so we need to create a new TCGOp.
2024 */
2025 op2 = opt_insert_before(ctx, op, INDEX_op_deposit, 5);
2026 op2->args[0] = op->args[0];
2027 op2->args[1] = tmp;
2028 op2->args[2] = op->args[2];
2029 op2->args[3] = shl;
2030 op2->args[4] = shr;
2031
2032 tcg_op_remove(ctx->tcg, op);
2033 op = op2;
2034 } else {
2035 op2 = opt_insert_before(ctx, op, INDEX_op_shl, 3);
2036 op2->args[0] = op->args[0];
2037 op2->args[1] = op->args[2];
2038 op2->args[2] = arg_new_constant(ctx, shl);
2039
2040 op->opc = INDEX_op_or;
2041 op->args[1] = op->args[0];
2042 op->args[2] = tmp;
2043 }
2044 }
2045
2046 return fold_masks_zo(ctx, op, zr, or);
2047 }
2048
2049 static bool fold_exts(OptContext *ctx, TCGOp *op)
2050 {
2051 uint64_t z_mask, o_mask, s_mask;
2052 TempOptInfo *t1;
2053
2054 if (fold_const1(ctx, op)) {
2055 return true;
2056 }
2057
2058 t1 = arg_info(op->args[1]);
2059 z_mask = t1->z_mask;
2060 o_mask = t1->o_mask;
2061 s_mask = t1->s_mask;
2062
2063 switch (op->opc) {
2064 case INDEX_op_ext_i32_i64:
2065 s_mask |= INT32_MIN;
2066 z_mask = (int32_t)z_mask;
2067 o_mask = (int32_t)o_mask;
2068 break;
2069 default:
2070 g_assert_not_reached();
2071 }
2072 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
2073 }
2074
2075 static bool fold_extu(OptContext *ctx, TCGOp *op)
2076 {
2077 uint64_t z_mask, o_mask;
2078 TempOptInfo *t1;
2079
2080 if (fold_const1(ctx, op)) {
2081 return true;
2082 }
2083
2084 t1 = arg_info(op->args[1]);
2085 z_mask = t1->z_mask;
2086 o_mask = t1->o_mask;
2087
2088 switch (op->opc) {
2089 case INDEX_op_extrl_i64_i32:
2090 case INDEX_op_extu_i32_i64:
2091 z_mask = (uint32_t)z_mask;
2092 o_mask = (uint32_t)o_mask;
2093 break;
2094 case INDEX_op_extrh_i64_i32:
2095 z_mask >>= 32;
2096 o_mask >>= 32;
2097 break;
2098 default:
2099 g_assert_not_reached();
2100 }
2101 return fold_masks_zo(ctx, op, z_mask, o_mask);
2102 }
2103
2104 static bool fold_mb(OptContext *ctx, TCGOp *op)
2105 {
2106 /* Eliminate duplicate and redundant fence instructions. */
2107 if (ctx->prev_mb) {
2108 /*
2109 * Merge two barriers of the same type into one,
2110 * or a weaker barrier into a stronger one,
2111 * or two weaker barriers into a stronger one.
2112 * mb X; mb Y => mb X|Y
2113 * mb; strl => mb; st
2114 * ldaq; mb => ld; mb
2115 * ldaq; strl => ld; mb; st
2116 * Other combinations are also merged into a strong
2117 * barrier. This is stricter than specified but for
2118 * the purposes of TCG is better than not optimizing.
2119 */
2120 ctx->prev_mb->args[0] |= op->args[0];
2121 tcg_op_remove(ctx->tcg, op);
2122 } else {
2123 ctx->prev_mb = op;
2124 }
2125 return true;
2126 }
2127
2128 static bool fold_minmax(OptContext *ctx, TCGOp *op, uint64_t bound)
2129 {
2130 if (fold_const2_commutative(ctx, op) ||
2131 fold_xi_to_i(ctx, op, bound) ||
2132 fold_xx_to_x(ctx, op)) {
2133 return true;
2134 }
2135 return finish_folding(ctx, op);
2136 }
2137
2138 static bool fold_mov(OptContext *ctx, TCGOp *op)
2139 {
2140 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]);
2141 }
2142
2143 static bool fold_movcond(OptContext *ctx, TCGOp *op)
2144 {
2145 uint64_t z_mask, o_mask, s_mask;
2146 TempOptInfo *tt, *ft;
2147 int i;
2148
2149 /* If true and false values are the same, eliminate the cmp. */
2150 if (args_are_copies(op->args[3], op->args[4])) {
2151 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[3]);
2152 }
2153
2154 /*
2155 * Canonicalize the "false" input reg to match the destination reg so
2156 * that the tcg backend can implement a "move if true" operation.
2157 */
2158 if (swap_commutative(op->args[0], &op->args[4], &op->args[3])) {
2159 op->args[5] = tcg_invert_cond(op->args[5]);
2160 }
2161
2162 i = do_constant_folding_cond1(ctx, op, NO_DEST, &op->args[1],
2163 &op->args[2], &op->args[5]);
2164 if (i >= 0) {
2165 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[4 - i]);
2166 }
2167
2168 tt = arg_info(op->args[3]);
2169 ft = arg_info(op->args[4]);
2170 z_mask = tt->z_mask | ft->z_mask;
2171 o_mask = tt->o_mask & ft->o_mask;
2172 s_mask = tt->s_mask & ft->s_mask;
2173
2174 if (ti_is_const(tt) && ti_is_const(ft)) {
2175 uint64_t tv = ti_const_val(tt);
2176 uint64_t fv = ti_const_val(ft);
2177 TCGCond cond = op->args[5];
2178
2179 if (tv == 1 && fv == 0) {
2180 op->opc = INDEX_op_setcond;
2181 op->args[3] = cond;
2182 } else if (fv == 1 && tv == 0) {
2183 op->opc = INDEX_op_setcond;
2184 op->args[3] = tcg_invert_cond(cond);
2185 } else if (tv == -1 && fv == 0) {
2186 op->opc = INDEX_op_negsetcond;
2187 op->args[3] = cond;
2188 } else if (fv == -1 && tv == 0) {
2189 op->opc = INDEX_op_negsetcond;
2190 op->args[3] = tcg_invert_cond(cond);
2191 }
2192 }
2193
2194 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
2195 }
2196
2197 static bool fold_mul(OptContext *ctx, TCGOp *op)
2198 {
2199 if (fold_const2_commutative(ctx, op) ||
2200 fold_xi_to_i(ctx, op, 0) ||
2201 fold_xi_to_x(ctx, op, 1)) {
2202 return true;
2203 }
2204 return finish_folding(ctx, op);
2205 }
2206
2207 static bool fold_mul_highpart(OptContext *ctx, TCGOp *op)
2208 {
2209 if (fold_const2_commutative(ctx, op) ||
2210 fold_xi_to_i(ctx, op, 0)) {
2211 return true;
2212 }
2213 return finish_folding(ctx, op);
2214 }
2215
2216 static bool fold_multiply2(OptContext *ctx, TCGOp *op)
2217 {
2218 swap_commutative(op->args[0], &op->args[2], &op->args[3]);
2219
2220 if (arg_is_const(op->args[3])) {
2221 uint64_t b = arg_const_val(op->args[3]);
2222 TCGArg rl = op->args[0];
2223 TCGArg rh = op->args[1];
2224 TCGOp *op2;
2225
2226 if (arg_is_const(op->args[2])) {
2227 uint64_t a = arg_const_val(op->args[2]);
2228 uint64_t h, l;
2229
2230 switch (op->opc) {
2231 case INDEX_op_mulu2:
2232 if (ctx->type == TCG_TYPE_I32) {
2233 l = (uint64_t)(uint32_t)a * (uint32_t)b;
2234 h = (int32_t)(l >> 32);
2235 l = (int32_t)l;
2236 } else {
2237 mulu64(&l, &h, a, b);
2238 }
2239 break;
2240 case INDEX_op_muls2:
2241 if (ctx->type == TCG_TYPE_I32) {
2242 l = (int64_t)(int32_t)a * (int32_t)b;
2243 h = l >> 32;
2244 l = (int32_t)l;
2245 } else {
2246 muls64(&l, &h, a, b);
2247 }
2248 break;
2249 default:
2250 g_assert_not_reached();
2251 }
2252
2253 /* The proper opcode is supplied by tcg_opt_gen_mov. */
2254 op2 = opt_insert_before(ctx, op, 0, 2);
2255 tcg_opt_gen_movi(ctx, op, rl, l);
2256 tcg_opt_gen_movi(ctx, op2, rh, h);
2257 return true;
2258 }
2259
2260 if (b == 0) {
2261 op2 = opt_insert_before(ctx, op, 0, 2);
2262 tcg_opt_gen_movi(ctx, op2, rl, 0);
2263 tcg_opt_gen_movi(ctx, op, rh, 0);
2264 return true;
2265 }
2266 if (b == 1) {
2267 op2 = opt_insert_before(ctx, op, 0, 2);
2268 tcg_opt_gen_mov(ctx, op2, rl, op->args[2]);
2269
2270 switch (op->opc) {
2271 case INDEX_op_mulu2:
2272 tcg_opt_gen_movi(ctx, op, rh, 0);
2273 break;
2274 case INDEX_op_muls2:
2275 op->opc = INDEX_op_sar;
2276 op->args[0] = rh;
2277 op->args[1] = rl;
2278 op->args[2] =
2279 arg_new_constant(ctx, tcg_type_size(ctx->type) * 8 - 1);
2280 break;
2281 default:
2282 g_assert_not_reached();
2283 }
2284
2285 return true;
2286 }
2287 }
2288 return finish_folding(ctx, op);
2289 }
2290
2291 static bool fold_nand(OptContext *ctx, TCGOp *op)
2292 {
2293 uint64_t z_mask, o_mask, s_mask;
2294 TempOptInfo *t1, *t2;
2295
2296 if (fold_const2_commutative(ctx, op) ||
2297 fold_xi_to_not(ctx, op, -1)) {
2298 return true;
2299 }
2300
2301 t1 = arg_info(op->args[1]);
2302 t2 = arg_info(op->args[2]);
2303
2304 z_mask = ~(t1->o_mask & t2->o_mask);
2305 o_mask = ~(t1->z_mask & t2->z_mask);
2306 s_mask = t1->s_mask & t2->s_mask;
2307
2308 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
2309 }
2310
2311 static bool fold_neg_no_const(OptContext *ctx, TCGOp *op)
2312 {
2313 /* Set to 1 all bits to the left of the rightmost. */
2314 uint64_t z_mask = arg_info(op->args[1])->z_mask;
2315 z_mask = -(z_mask & -z_mask);
2316
2317 return fold_masks_z(ctx, op, z_mask);
2318 }
2319
2320 static bool fold_neg(OptContext *ctx, TCGOp *op)
2321 {
2322 return fold_const1(ctx, op) || fold_neg_no_const(ctx, op);
2323 }
2324
2325 static bool fold_nor(OptContext *ctx, TCGOp *op)
2326 {
2327 uint64_t z_mask, o_mask, s_mask;
2328 TempOptInfo *t1, *t2;
2329
2330 if (fold_const2_commutative(ctx, op) ||
2331 fold_xi_to_not(ctx, op, 0)) {
2332 return true;
2333 }
2334
2335 t1 = arg_info(op->args[1]);
2336 t2 = arg_info(op->args[2]);
2337
2338 z_mask = ~(t1->o_mask | t2->o_mask);
2339 o_mask = ~(t1->z_mask | t2->z_mask);
2340 s_mask = t1->s_mask & t2->s_mask;
2341
2342 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
2343 }
2344
2345 static bool fold_not(OptContext *ctx, TCGOp *op)
2346 {
2347 TempOptInfo *t1;
2348
2349 if (fold_const1(ctx, op)) {
2350 return true;
2351 }
2352
2353 t1 = arg_info(op->args[1]);
2354 return fold_masks_zos(ctx, op, ~t1->o_mask, ~t1->z_mask, t1->s_mask);
2355 }
2356
2357 static bool fold_or(OptContext *ctx, TCGOp *op)
2358 {
2359 uint64_t z_mask, o_mask, s_mask, a_mask;
2360 TempOptInfo *t1, *t2;
2361
2362 if (fold_const2_commutative(ctx, op) ||
2363 fold_xi_to_x(ctx, op, 0) ||
2364 fold_xx_to_x(ctx, op)) {
2365 return true;
2366 }
2367
2368 t1 = arg_info(op->args[1]);
2369 t2 = arg_info(op->args[2]);
2370
2371 z_mask = t1->z_mask | t2->z_mask;
2372 o_mask = t1->o_mask | t2->o_mask;
2373 s_mask = t1->s_mask & t2->s_mask;
2374
2375 /* Affected bits are those not known one, masked by those known zero. */
2376 a_mask = ~t1->o_mask & t2->z_mask;
2377
2378 return fold_masks_zosa(ctx, op, z_mask, o_mask, s_mask, a_mask);
2379 }
2380
2381 static bool fold_orc(OptContext *ctx, TCGOp *op)
2382 {
2383 uint64_t z_mask, o_mask, s_mask, a_mask;
2384 TempOptInfo *t1, *t2;
2385
2386 if (fold_const2(ctx, op)) {
2387 return true;
2388 }
2389
2390 t2 = arg_info(op->args[2]);
2391 if (ti_is_const(t2)) {
2392 /* Fold orc r,x,i to or r,x,~i. */
2393 switch (ctx->type) {
2394 case TCG_TYPE_I32:
2395 case TCG_TYPE_I64:
2396 op->opc = INDEX_op_or;
2397 break;
2398 case TCG_TYPE_V64:
2399 case TCG_TYPE_V128:
2400 case TCG_TYPE_V256:
2401 op->opc = INDEX_op_or_vec;
2402 break;
2403 default:
2404 g_assert_not_reached();
2405 }
2406 op->args[2] = arg_new_constant(ctx, ~ti_const_val(t2));
2407 return fold_or(ctx, op);
2408 }
2409 if (fold_xx_to_i(ctx, op, -1) ||
2410 fold_ix_to_not(ctx, op, 0)) {
2411 return true;
2412 }
2413 t1 = arg_info(op->args[1]);
2414
2415 z_mask = t1->z_mask | ~t2->o_mask;
2416 o_mask = t1->o_mask | ~t2->z_mask;
2417 s_mask = t1->s_mask & t2->s_mask;
2418
2419 /* Affected bits are those not known one, masked by those known one. */
2420 a_mask = ~t1->o_mask & ~t2->o_mask;
2421
2422 return fold_masks_zosa(ctx, op, z_mask, o_mask, s_mask, a_mask);
2423 }
2424
2425 static bool fold_qemu_ld_1reg(OptContext *ctx, TCGOp *op)
2426 {
2427 const TCGOpDef *def = &tcg_op_defs[op->opc];
2428 MemOpIdx oi = op->args[def->nb_oargs + def->nb_iargs];
2429 MemOp mop = get_memop(oi);
2430 int width = 8 * memop_size(mop);
2431 uint64_t z_mask = -1, s_mask = 0;
2432
2433 if (width < 64) {
2434 if (mop & MO_SIGN) {
2435 s_mask = MAKE_64BIT_MASK(width - 1, 64 - (width - 1));
2436 } else {
2437 z_mask = MAKE_64BIT_MASK(0, width);
2438 }
2439 }
2440
2441 /* Opcodes that touch guest memory stop the mb optimization. */
2442 ctx->prev_mb = NULL;
2443
2444 return fold_masks_zs(ctx, op, z_mask, s_mask);
2445 }
2446
2447 static bool fold_qemu_ld_2reg(OptContext *ctx, TCGOp *op)
2448 {
2449 /* Opcodes that touch guest memory stop the mb optimization. */
2450 ctx->prev_mb = NULL;
2451 return finish_folding(ctx, op);
2452 }
2453
2454 static bool fold_qemu_st(OptContext *ctx, TCGOp *op)
2455 {
2456 /* Opcodes that touch guest memory stop the mb optimization. */
2457 ctx->prev_mb = NULL;
2458 return true;
2459 }
2460
2461 static bool fold_remainder(OptContext *ctx, TCGOp *op)
2462 {
2463 if (fold_const2(ctx, op) ||
2464 fold_xx_to_i(ctx, op, 0)) {
2465 return true;
2466 }
2467 return finish_folding(ctx, op);
2468 }
2469
2470 /* Return 1 if finished, -1 if simplified, 0 if unchanged. */
2471 static int fold_setcond_zmask(OptContext *ctx, TCGOp *op, bool neg)
2472 {
2473 uint64_t a_zmask, b_val;
2474 TCGCond cond;
2475
2476 if (!arg_is_const(op->args[2])) {
2477 return false;
2478 }
2479
2480 a_zmask = arg_info(op->args[1])->z_mask;
2481 b_val = arg_const_val(op->args[2]);
2482 cond = op->args[3];
2483
2484 if (ctx->type == TCG_TYPE_I32) {
2485 a_zmask = (uint32_t)a_zmask;
2486 b_val = (uint32_t)b_val;
2487 }
2488
2489 /*
2490 * A with only low bits set vs B with high bits set means that A < B.
2491 */
2492 if (a_zmask < b_val) {
2493 bool inv = false;
2494
2495 switch (cond) {
2496 case TCG_COND_NE:
2497 case TCG_COND_LEU:
2498 case TCG_COND_LTU:
2499 inv = true;
2500 /* fall through */
2501 case TCG_COND_GTU:
2502 case TCG_COND_GEU:
2503 case TCG_COND_EQ:
2504 return tcg_opt_gen_movi(ctx, op, op->args[0], neg ? -inv : inv);
2505 default:
2506 break;
2507 }
2508 }
2509
2510 /*
2511 * A with only lsb set is already boolean.
2512 */
2513 if (a_zmask <= 1) {
2514 bool convert = false;
2515 bool inv = false;
2516
2517 switch (cond) {
2518 case TCG_COND_EQ:
2519 inv = true;
2520 /* fall through */
2521 case TCG_COND_NE:
2522 convert = (b_val == 0);
2523 break;
2524 case TCG_COND_LTU:
2525 case TCG_COND_TSTEQ:
2526 inv = true;
2527 /* fall through */
2528 case TCG_COND_GEU:
2529 case TCG_COND_TSTNE:
2530 convert = (b_val == 1);
2531 break;
2532 default:
2533 break;
2534 }
2535 if (convert) {
2536 if (!inv && !neg) {
2537 return tcg_opt_gen_mov(ctx, op, op->args[0], op->args[1]);
2538 }
2539
2540 if (!inv) {
2541 op->opc = INDEX_op_neg;
2542 } else if (neg) {
2543 op->opc = INDEX_op_add;
2544 op->args[2] = arg_new_constant(ctx, -1);
2545 } else {
2546 op->opc = INDEX_op_xor;
2547 op->args[2] = arg_new_constant(ctx, 1);
2548 }
2549 return -1;
2550 }
2551 }
2552 return 0;
2553 }
2554
2555 static void fold_setcond_tst_pow2(OptContext *ctx, TCGOp *op, bool neg)
2556 {
2557 TCGCond cond = op->args[3];
2558 TCGArg ret, src1, src2;
2559 TCGOp *op2;
2560 uint64_t val;
2561 int sh;
2562 bool inv;
2563
2564 if (!is_tst_cond(cond) || !arg_is_const(op->args[2])) {
2565 return;
2566 }
2567
2568 src2 = op->args[2];
2569 val = arg_const_val(src2);
2570 if (!is_power_of_2(val)) {
2571 return;
2572 }
2573 sh = ctz64(val);
2574
2575 ret = op->args[0];
2576 src1 = op->args[1];
2577 inv = cond == TCG_COND_TSTEQ;
2578
2579 if (sh && neg && !inv && TCG_TARGET_sextract_valid(ctx->type, sh, 1)) {
2580 op->opc = INDEX_op_sextract;
2581 op->args[1] = src1;
2582 op->args[2] = sh;
2583 op->args[3] = 1;
2584 return;
2585 } else if (sh && TCG_TARGET_extract_valid(ctx->type, sh, 1)) {
2586 op->opc = INDEX_op_extract;
2587 op->args[1] = src1;
2588 op->args[2] = sh;
2589 op->args[3] = 1;
2590 } else {
2591 if (sh) {
2592 op2 = opt_insert_before(ctx, op, INDEX_op_shr, 3);
2593 op2->args[0] = ret;
2594 op2->args[1] = src1;
2595 op2->args[2] = arg_new_constant(ctx, sh);
2596 src1 = ret;
2597 }
2598 op->opc = INDEX_op_and;
2599 op->args[1] = src1;
2600 op->args[2] = arg_new_constant(ctx, 1);
2601 }
2602
2603 if (neg && inv) {
2604 op2 = opt_insert_after(ctx, op, INDEX_op_add, 3);
2605 op2->args[0] = ret;
2606 op2->args[1] = ret;
2607 op2->args[2] = arg_new_constant(ctx, -1);
2608 } else if (inv) {
2609 op2 = opt_insert_after(ctx, op, INDEX_op_xor, 3);
2610 op2->args[0] = ret;
2611 op2->args[1] = ret;
2612 op2->args[2] = arg_new_constant(ctx, 1);
2613 } else if (neg) {
2614 op2 = opt_insert_after(ctx, op, INDEX_op_neg, 2);
2615 op2->args[0] = ret;
2616 op2->args[1] = ret;
2617 }
2618 }
2619
2620 static bool fold_setcond(OptContext *ctx, TCGOp *op)
2621 {
2622 int i = do_constant_folding_cond1(ctx, op, op->args[0], &op->args[1],
2623 &op->args[2], &op->args[3]);
2624 if (i >= 0) {
2625 return tcg_opt_gen_movi(ctx, op, op->args[0], i);
2626 }
2627
2628 i = fold_setcond_zmask(ctx, op, false);
2629 if (i > 0) {
2630 return true;
2631 }
2632 if (i == 0) {
2633 fold_setcond_tst_pow2(ctx, op, false);
2634 }
2635
2636 return fold_masks_z(ctx, op, 1);
2637 }
2638
2639 static bool fold_negsetcond(OptContext *ctx, TCGOp *op)
2640 {
2641 int i = do_constant_folding_cond1(ctx, op, op->args[0], &op->args[1],
2642 &op->args[2], &op->args[3]);
2643 if (i >= 0) {
2644 return tcg_opt_gen_movi(ctx, op, op->args[0], -i);
2645 }
2646
2647 i = fold_setcond_zmask(ctx, op, true);
2648 if (i > 0) {
2649 return true;
2650 }
2651 if (i == 0) {
2652 fold_setcond_tst_pow2(ctx, op, true);
2653 }
2654
2655 /* Value is {0,-1} so all bits are repetitions of the sign. */
2656 return fold_masks_s(ctx, op, -1);
2657 }
2658
2659 static bool fold_sextract(OptContext *ctx, TCGOp *op)
2660 {
2661 uint64_t z_mask, o_mask, s_mask, a_mask;
2662 TempOptInfo *t1 = arg_info(op->args[1]);
2663 int pos = op->args[2];
2664 int len = op->args[3];
2665
2666 if (ti_is_const(t1)) {
2667 return tcg_opt_gen_movi(ctx, op, op->args[0],
2668 sextract64(ti_const_val(t1), pos, len));
2669 }
2670
2671 s_mask = t1->s_mask >> pos;
2672 s_mask |= -1ull << (len - 1);
2673 a_mask = pos ? -1 : s_mask & ~t1->s_mask;
2674
2675 z_mask = sextract64(t1->z_mask, pos, len);
2676 o_mask = sextract64(t1->o_mask, pos, len);
2677
2678 return fold_masks_zosa(ctx, op, z_mask, o_mask, s_mask, a_mask);
2679 }
2680
2681 static bool fold_shift(OptContext *ctx, TCGOp *op)
2682 {
2683 uint64_t s_mask, z_mask, o_mask;
2684 TempOptInfo *t1, *t2;
2685
2686 if (fold_const2(ctx, op) ||
2687 fold_ix_to_i(ctx, op, 0) ||
2688 fold_xi_to_x(ctx, op, 0)) {
2689 return true;
2690 }
2691
2692 t1 = arg_info(op->args[1]);
2693 t2 = arg_info(op->args[2]);
2694 s_mask = t1->s_mask;
2695 z_mask = t1->z_mask;
2696 o_mask = t1->o_mask;
2697
2698 if (ti_is_const(t2)) {
2699 int sh = ti_const_val(t2);
2700
2701 z_mask = do_constant_folding(op->opc, ctx->type, z_mask, sh);
2702 o_mask = do_constant_folding(op->opc, ctx->type, o_mask, sh);
2703
2704 if (op->opc == INDEX_op_shr) {
2705 /*
2706 * Logical right shift will force the sign bit zero.
2707 * Don't bother computing s_mask and let fold_masks
2708 * recompute from z_mask.
2709 */
2710 return fold_masks_zo(ctx, op, z_mask, o_mask);
2711 }
2712
2713 s_mask = do_constant_folding(op->opc, ctx->type, s_mask, sh);
2714 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
2715 }
2716
2717 switch (op->opc) {
2718 case INDEX_op_sar:
2719 /*
2720 * Arithmetic right shift will not reduce the number of
2721 * input sign repetitions.
2722 */
2723 return fold_masks_s(ctx, op, s_mask);
2724 case INDEX_op_shr:
2725 /*
2726 * If the sign bit is known zero, then logical right shift
2727 * will not reduce the number of input sign repetitions.
2728 */
2729 if (~z_mask & -s_mask) {
2730 return fold_masks_s(ctx, op, s_mask);
2731 }
2732 break;
2733 default:
2734 break;
2735 }
2736
2737 return finish_folding(ctx, op);
2738 }
2739
2740 static bool fold_sub_to_neg(OptContext *ctx, TCGOp *op)
2741 {
2742 TCGOpcode neg_op;
2743 bool have_neg;
2744
2745 if (!arg_is_const_val(op->args[1], 0)) {
2746 return false;
2747 }
2748
2749 switch (ctx->type) {
2750 case TCG_TYPE_I32:
2751 case TCG_TYPE_I64:
2752 neg_op = INDEX_op_neg;
2753 have_neg = true;
2754 break;
2755 case TCG_TYPE_V64:
2756 case TCG_TYPE_V128:
2757 case TCG_TYPE_V256:
2758 neg_op = INDEX_op_neg_vec;
2759 have_neg = (TCG_TARGET_HAS_neg_vec &&
2760 tcg_can_emit_vec_op(neg_op, ctx->type, TCGOP_VECE(op)) > 0);
2761 break;
2762 default:
2763 g_assert_not_reached();
2764 }
2765 if (have_neg) {
2766 op->opc = neg_op;
2767 op->args[1] = op->args[2];
2768 return fold_neg_no_const(ctx, op);
2769 }
2770 return false;
2771 }
2772
2773 /* We cannot as yet do_constant_folding with vectors. */
2774 static bool fold_sub_vec(OptContext *ctx, TCGOp *op)
2775 {
2776 if (fold_xx_to_i(ctx, op, 0) ||
2777 fold_xi_to_x(ctx, op, 0) ||
2778 fold_sub_to_neg(ctx, op)) {
2779 return true;
2780 }
2781 return finish_folding(ctx, op);
2782 }
2783
2784 static bool fold_sub(OptContext *ctx, TCGOp *op)
2785 {
2786 if (fold_const2(ctx, op) ||
2787 fold_xx_to_i(ctx, op, 0) ||
2788 fold_xi_to_x(ctx, op, 0) ||
2789 fold_sub_to_neg(ctx, op)) {
2790 return true;
2791 }
2792
2793 /* Fold sub r,x,i to add r,x,-i */
2794 if (arg_is_const(op->args[2])) {
2795 uint64_t val = arg_const_val(op->args[2]);
2796
2797 op->opc = INDEX_op_add;
2798 op->args[2] = arg_new_constant(ctx, -val);
2799 }
2800 return finish_folding(ctx, op);
2801 }
2802
2803 static void squash_prev_borrowout(OptContext *ctx, TCGOp *op)
2804 {
2805 TempOptInfo *t2;
2806
2807 op = QTAILQ_PREV(op, link);
2808 switch (op->opc) {
2809 case INDEX_op_subbo:
2810 op->opc = INDEX_op_sub;
2811 fold_sub(ctx, op);
2812 break;
2813 case INDEX_op_subbio:
2814 op->opc = INDEX_op_subbi;
2815 break;
2816 case INDEX_op_subb1o:
2817 t2 = arg_info(op->args[2]);
2818 if (ti_is_const(t2)) {
2819 op->opc = INDEX_op_add;
2820 op->args[2] = arg_new_constant(ctx, -(ti_const_val(t2) + 1));
2821 /* Perform other constant folding, if needed. */
2822 fold_add(ctx, op);
2823 } else {
2824 TCGArg ret = op->args[0];
2825 op->opc = INDEX_op_sub;
2826 op = opt_insert_after(ctx, op, INDEX_op_add, 3);
2827 op->args[0] = ret;
2828 op->args[1] = ret;
2829 op->args[2] = arg_new_constant(ctx, -1);
2830 }
2831 break;
2832 default:
2833 g_assert_not_reached();
2834 }
2835 }
2836
2837 static bool fold_subbi(OptContext *ctx, TCGOp *op)
2838 {
2839 TempOptInfo *t2;
2840 int borrow_in = ctx->carry_state;
2841
2842 if (borrow_in < 0) {
2843 return finish_folding(ctx, op);
2844 }
2845 ctx->carry_state = -1;
2846
2847 squash_prev_borrowout(ctx, op);
2848 if (borrow_in == 0) {
2849 op->opc = INDEX_op_sub;
2850 return fold_sub(ctx, op);
2851 }
2852
2853 /*
2854 * Propagate the known carry-in into any constant, then negate to
2855 * transform from sub to add. If there is no constant, emit a
2856 * separate add -1.
2857 */
2858 t2 = arg_info(op->args[2]);
2859 if (ti_is_const(t2)) {
2860 op->args[2] = arg_new_constant(ctx, -(ti_const_val(t2) + 1));
2861 } else {
2862 TCGOp *op2 = opt_insert_before(ctx, op, INDEX_op_sub, 3);
2863
2864 op2->args[0] = op->args[0];
2865 op2->args[1] = op->args[1];
2866 op2->args[2] = op->args[2];
2867 fold_sub(ctx, op2);
2868
2869 op->args[1] = op->args[0];
2870 op->args[2] = arg_new_constant(ctx, -1);
2871 }
2872 op->opc = INDEX_op_add;
2873 return fold_add(ctx, op);
2874 }
2875
2876 static bool fold_subbio(OptContext *ctx, TCGOp *op)
2877 {
2878 TempOptInfo *t1, *t2;
2879 int borrow_out = -1;
2880
2881 if (ctx->carry_state < 0) {
2882 return finish_folding(ctx, op);
2883 }
2884
2885 squash_prev_borrowout(ctx, op);
2886 if (ctx->carry_state == 0) {
2887 goto do_subbo;
2888 }
2889
2890 t1 = arg_info(op->args[1]);
2891 t2 = arg_info(op->args[2]);
2892
2893 /* Propagate the known borrow-in into a constant, if possible. */
2894 if (ti_is_const(t2)) {
2895 uint64_t max = ctx->type == TCG_TYPE_I32 ? UINT32_MAX : UINT64_MAX;
2896 uint64_t v = ti_const_val(t2) & max;
2897
2898 if (v < max) {
2899 op->args[2] = arg_new_constant(ctx, v + 1);
2900 goto do_subbo;
2901 }
2902 /* subtracting max + 1 produces known borrow out. */
2903 borrow_out = 1;
2904 }
2905 if (ti_is_const(t1)) {
2906 uint64_t v = ti_const_val(t1);
2907 if (v != 0) {
2908 op->args[2] = arg_new_constant(ctx, v - 1);
2909 goto do_subbo;
2910 }
2911 }
2912
2913 /* Adjust the opcode to remember the known carry-in. */
2914 op->opc = INDEX_op_subb1o;
2915 ctx->carry_state = borrow_out;
2916 return finish_folding(ctx, op);
2917
2918 do_subbo:
2919 op->opc = INDEX_op_subbo;
2920 return fold_subbo(ctx, op);
2921 }
2922
2923 static bool fold_subbo(OptContext *ctx, TCGOp *op)
2924 {
2925 TempOptInfo *t1 = arg_info(op->args[1]);
2926 TempOptInfo *t2 = arg_info(op->args[2]);
2927 int borrow_out = -1;
2928
2929 if (ti_is_const(t2)) {
2930 uint64_t v2 = ti_const_val(t2);
2931 if (v2 == 0) {
2932 borrow_out = 0;
2933 } else if (ti_is_const(t1)) {
2934 uint64_t v1 = ti_const_val(t1);
2935 borrow_out = v1 < v2;
2936 }
2937 }
2938 ctx->carry_state = borrow_out;
2939 return finish_folding(ctx, op);
2940 }
2941
2942 static bool fold_tcg_ld(OptContext *ctx, TCGOp *op)
2943 {
2944 uint64_t z_mask = -1, s_mask = 0;
2945
2946 /* We can't do any folding with a load, but we can record bits. */
2947 switch (op->opc) {
2948 case INDEX_op_ld8s:
2949 s_mask = INT8_MIN;
2950 break;
2951 case INDEX_op_ld8u:
2952 z_mask = MAKE_64BIT_MASK(0, 8);
2953 break;
2954 case INDEX_op_ld16s:
2955 s_mask = INT16_MIN;
2956 break;
2957 case INDEX_op_ld16u:
2958 z_mask = MAKE_64BIT_MASK(0, 16);
2959 break;
2960 case INDEX_op_ld32s:
2961 s_mask = INT32_MIN;
2962 break;
2963 case INDEX_op_ld32u:
2964 z_mask = MAKE_64BIT_MASK(0, 32);
2965 break;
2966 default:
2967 g_assert_not_reached();
2968 }
2969 return fold_masks_zs(ctx, op, z_mask, s_mask);
2970 }
2971
2972 static bool fold_tcg_ld_memcopy(OptContext *ctx, TCGOp *op)
2973 {
2974 TCGTemp *dst, *src;
2975 intptr_t ofs;
2976 TCGType type;
2977
2978 if (op->args[1] != tcgv_ptr_arg(tcg_env)) {
2979 return finish_folding(ctx, op);
2980 }
2981
2982 type = ctx->type;
2983 ofs = op->args[2];
2984 dst = arg_temp(op->args[0]);
2985 src = find_mem_copy_for(ctx, type, ofs);
2986 if (src && src->base_type == type) {
2987 return tcg_opt_gen_mov(ctx, op, temp_arg(dst), temp_arg(src));
2988 }
2989
2990 reset_ts(ctx, dst);
2991 record_mem_copy(ctx, type, dst, ofs, ofs + tcg_type_size(type) - 1);
2992 return true;
2993 }
2994
2995 static bool fold_tcg_st(OptContext *ctx, TCGOp *op)
2996 {
2997 intptr_t ofs = op->args[2];
2998 intptr_t lm1;
2999
3000 if (op->args[1] != tcgv_ptr_arg(tcg_env)) {
3001 remove_mem_copy_all(ctx);
3002 return true;
3003 }
3004
3005 switch (op->opc) {
3006 case INDEX_op_st8:
3007 lm1 = 0;
3008 break;
3009 case INDEX_op_st16:
3010 lm1 = 1;
3011 break;
3012 case INDEX_op_st32:
3013 lm1 = 3;
3014 break;
3015 case INDEX_op_st:
3016 case INDEX_op_st_vec:
3017 lm1 = tcg_type_size(ctx->type) - 1;
3018 break;
3019 default:
3020 g_assert_not_reached();
3021 }
3022 remove_mem_copy_in(ctx, ofs, ofs + lm1);
3023 return true;
3024 }
3025
3026 static bool fold_tcg_st_memcopy(OptContext *ctx, TCGOp *op)
3027 {
3028 TCGTemp *src;
3029 intptr_t ofs, last;
3030 TCGType type;
3031
3032 if (op->args[1] != tcgv_ptr_arg(tcg_env)) {
3033 return fold_tcg_st(ctx, op);
3034 }
3035
3036 src = arg_temp(op->args[0]);
3037 ofs = op->args[2];
3038 type = ctx->type;
3039
3040 /*
3041 * Eliminate duplicate stores of a constant.
3042 * This happens frequently when the target ISA zero-extends.
3043 */
3044 if (ts_is_const(src)) {
3045 TCGTemp *prev = find_mem_copy_for(ctx, type, ofs);
3046 if (src == prev) {
3047 tcg_op_remove(ctx->tcg, op);
3048 return true;
3049 }
3050 }
3051
3052 last = ofs + tcg_type_size(type) - 1;
3053 remove_mem_copy_in(ctx, ofs, last);
3054 record_mem_copy(ctx, type, src, ofs, last);
3055 return true;
3056 }
3057
3058 static bool fold_xor(OptContext *ctx, TCGOp *op)
3059 {
3060 uint64_t z_mask, o_mask, s_mask;
3061 TempOptInfo *t1, *t2;
3062
3063 if (fold_const2_commutative(ctx, op) ||
3064 fold_xx_to_i(ctx, op, 0) ||
3065 fold_xi_to_x(ctx, op, 0) ||
3066 fold_xi_to_not(ctx, op, -1)) {
3067 return true;
3068 }
3069
3070 t1 = arg_info(op->args[1]);
3071 t2 = arg_info(op->args[2]);
3072
3073 z_mask = (t1->z_mask | t2->z_mask) & ~(t1->o_mask & t2->o_mask);
3074 o_mask = (t1->o_mask & ~t2->z_mask) | (t2->o_mask & ~t1->z_mask);
3075 s_mask = t1->s_mask & t2->s_mask;
3076
3077 return fold_masks_zos(ctx, op, z_mask, o_mask, s_mask);
3078 }
3079
3080 /* Propagate constants and copies, fold constant expressions. */
3081 void tcg_optimize(TCGContext *s)
3082 {
3083 int nb_temps, i;
3084 TCGOp *op, *op_next;
3085 OptContext ctx = { .tcg = s };
3086
3087 QSIMPLEQ_INIT(&ctx.mem_free);
3088
3089 /* Array VALS has an element for each temp.
3090 If this temp holds a constant then its value is kept in VALS' element.
3091 If this temp is a copy of other ones then the other copies are
3092 available through the doubly linked circular list. */
3093
3094 nb_temps = s->nb_temps;
3095 for (i = 0; i < nb_temps; ++i) {
3096 s->temps[i].state_ptr = NULL;
3097 }
3098
3099 QTAILQ_FOREACH_SAFE(op, &s->ops, link, op_next) {
3100 TCGOpcode opc = op->opc;
3101 const TCGOpDef *def;
3102 bool done = false;
3103
3104 /* Calls are special. */
3105 if (opc == INDEX_op_call) {
3106 fold_call(&ctx, op);
3107 continue;
3108 }
3109
3110 def = &tcg_op_defs[opc];
3111 init_arguments(&ctx, op, def->nb_oargs + def->nb_iargs);
3112 copy_propagate(&ctx, op, def->nb_oargs, def->nb_iargs);
3113
3114 /* Pre-compute the type of the operation. */
3115 ctx.type = TCGOP_TYPE(op);
3116
3117 /*
3118 * Process each opcode.
3119 * Sorted alphabetically by opcode as much as possible.
3120 */
3121 switch (opc) {
3122 case INDEX_op_add:
3123 done = fold_add(&ctx, op);
3124 break;
3125 case INDEX_op_add_vec:
3126 done = fold_add_vec(&ctx, op);
3127 break;
3128 case INDEX_op_addci:
3129 done = fold_addci(&ctx, op);
3130 break;
3131 case INDEX_op_addcio:
3132 done = fold_addcio(&ctx, op);
3133 break;
3134 case INDEX_op_addco:
3135 done = fold_addco(&ctx, op);
3136 break;
3137 case INDEX_op_and:
3138 case INDEX_op_and_vec:
3139 done = fold_and(&ctx, op);
3140 break;
3141 case INDEX_op_andc:
3142 case INDEX_op_andc_vec:
3143 done = fold_andc(&ctx, op);
3144 break;
3145 case INDEX_op_brcond:
3146 done = fold_brcond(&ctx, op);
3147 break;
3148 case INDEX_op_bswap16:
3149 case INDEX_op_bswap32:
3150 case INDEX_op_bswap64:
3151 case INDEX_op_revbit8:
3152 case INDEX_op_revbit32:
3153 case INDEX_op_revbit64:
3154 done = fold_bswap(&ctx, op);
3155 break;
3156 case INDEX_op_clz:
3157 case INDEX_op_ctz:
3158 done = fold_count_zeros(&ctx, op);
3159 break;
3160 case INDEX_op_ctpop:
3161 done = fold_ctpop(&ctx, op);
3162 break;
3163 case INDEX_op_deposit:
3164 done = fold_deposit(&ctx, op);
3165 break;
3166 case INDEX_op_divs:
3167 case INDEX_op_divu:
3168 done = fold_divide(&ctx, op);
3169 break;
3170 case INDEX_op_dup_vec:
3171 done = fold_dup(&ctx, op);
3172 break;
3173 case INDEX_op_eqv:
3174 case INDEX_op_eqv_vec:
3175 done = fold_eqv(&ctx, op);
3176 break;
3177 case INDEX_op_extract:
3178 done = fold_extract(&ctx, op);
3179 break;
3180 case INDEX_op_extract2:
3181 done = fold_extract2(&ctx, op);
3182 break;
3183 case INDEX_op_ext_i32_i64:
3184 done = fold_exts(&ctx, op);
3185 break;
3186 case INDEX_op_extu_i32_i64:
3187 case INDEX_op_extrl_i64_i32:
3188 case INDEX_op_extrh_i64_i32:
3189 done = fold_extu(&ctx, op);
3190 break;
3191 case INDEX_op_ld8s:
3192 case INDEX_op_ld8u:
3193 case INDEX_op_ld16s:
3194 case INDEX_op_ld16u:
3195 case INDEX_op_ld32s:
3196 case INDEX_op_ld32u:
3197 done = fold_tcg_ld(&ctx, op);
3198 break;
3199 case INDEX_op_ld:
3200 case INDEX_op_ld_vec:
3201 done = fold_tcg_ld_memcopy(&ctx, op);
3202 break;
3203 case INDEX_op_st8:
3204 case INDEX_op_st16:
3205 case INDEX_op_st32:
3206 done = fold_tcg_st(&ctx, op);
3207 break;
3208 case INDEX_op_st:
3209 case INDEX_op_st_vec:
3210 done = fold_tcg_st_memcopy(&ctx, op);
3211 break;
3212 case INDEX_op_mb:
3213 done = fold_mb(&ctx, op);
3214 break;
3215 case INDEX_op_mov:
3216 case INDEX_op_mov_vec:
3217 done = fold_mov(&ctx, op);
3218 break;
3219 case INDEX_op_movcond:
3220 done = fold_movcond(&ctx, op);
3221 break;
3222 case INDEX_op_mul:
3223 done = fold_mul(&ctx, op);
3224 break;
3225 case INDEX_op_mulsh:
3226 case INDEX_op_muluh:
3227 done = fold_mul_highpart(&ctx, op);
3228 break;
3229 case INDEX_op_muls2:
3230 case INDEX_op_mulu2:
3231 done = fold_multiply2(&ctx, op);
3232 break;
3233 case INDEX_op_nand:
3234 case INDEX_op_nand_vec:
3235 done = fold_nand(&ctx, op);
3236 break;
3237 case INDEX_op_neg:
3238 done = fold_neg(&ctx, op);
3239 break;
3240 case INDEX_op_nor:
3241 case INDEX_op_nor_vec:
3242 done = fold_nor(&ctx, op);
3243 break;
3244 case INDEX_op_not:
3245 case INDEX_op_not_vec:
3246 done = fold_not(&ctx, op);
3247 break;
3248 case INDEX_op_or:
3249 case INDEX_op_or_vec:
3250 done = fold_or(&ctx, op);
3251 break;
3252 case INDEX_op_orc:
3253 case INDEX_op_orc_vec:
3254 done = fold_orc(&ctx, op);
3255 break;
3256 case INDEX_op_qemu_ld:
3257 done = fold_qemu_ld_1reg(&ctx, op);
3258 break;
3259 case INDEX_op_qemu_ld2:
3260 done = fold_qemu_ld_2reg(&ctx, op);
3261 break;
3262 case INDEX_op_qemu_st:
3263 case INDEX_op_qemu_st2:
3264 done = fold_qemu_st(&ctx, op);
3265 break;
3266 case INDEX_op_rems:
3267 case INDEX_op_remu:
3268 done = fold_remainder(&ctx, op);
3269 break;
3270 case INDEX_op_rotl:
3271 case INDEX_op_rotr:
3272 case INDEX_op_sar:
3273 case INDEX_op_shl:
3274 case INDEX_op_shr:
3275 done = fold_shift(&ctx, op);
3276 break;
3277 case INDEX_op_setcond:
3278 done = fold_setcond(&ctx, op);
3279 break;
3280 case INDEX_op_negsetcond:
3281 done = fold_negsetcond(&ctx, op);
3282 break;
3283 case INDEX_op_cmp_vec:
3284 done = fold_cmp_vec(&ctx, op);
3285 break;
3286 case INDEX_op_cmpsel_vec:
3287 done = fold_cmpsel_vec(&ctx, op);
3288 break;
3289 case INDEX_op_bitsel_vec:
3290 done = fold_bitsel_vec(&ctx, op);
3291 break;
3292 case INDEX_op_sextract:
3293 done = fold_sextract(&ctx, op);
3294 break;
3295 case INDEX_op_smax:
3296 done = fold_minmax(&ctx, op, (ctx.type == TCG_TYPE_I32
3297 ? INT32_MAX : INT64_MAX));
3298 break;
3299 case INDEX_op_smin:
3300 done = fold_minmax(&ctx, op, (ctx.type == TCG_TYPE_I32
3301 ? INT32_MIN : INT64_MIN));
3302 break;
3303 case INDEX_op_sub:
3304 done = fold_sub(&ctx, op);
3305 break;
3306 case INDEX_op_subbi:
3307 done = fold_subbi(&ctx, op);
3308 break;
3309 case INDEX_op_subbio:
3310 done = fold_subbio(&ctx, op);
3311 break;
3312 case INDEX_op_subbo:
3313 done = fold_subbo(&ctx, op);
3314 break;
3315 case INDEX_op_sub_vec:
3316 done = fold_sub_vec(&ctx, op);
3317 break;
3318 case INDEX_op_umax:
3319 /*
3320 * Note that 32-bit constants are stored sign extended,
3321 * so (int32_t)UINT32_MAX == -1.
3322 */
3323 done = fold_minmax(&ctx, op, -1);
3324 break;
3325 case INDEX_op_umin:
3326 done = fold_minmax(&ctx, op, 0);
3327 break;
3328 case INDEX_op_xor:
3329 case INDEX_op_xor_vec:
3330 done = fold_xor(&ctx, op);
3331 break;
3332 case INDEX_op_set_label:
3333 case INDEX_op_br:
3334 case INDEX_op_exit_tb:
3335 case INDEX_op_goto_tb:
3336 case INDEX_op_goto_ptr:
3337 finish_ebb(&ctx);
3338 done = true;
3339 break;
3340 default:
3341 done = finish_folding(&ctx, op);
3342 break;
3343 }
3344 tcg_debug_assert(done);
3345 }
3346 }