]>
git.proxmox.com Git - mirror_qemu.git/blob - tcg/optimize.c
2 * Optimizations for Tiny Code Generator for QEMU
4 * Copyright (c) 2010 Samsung Electronics.
5 * Contributed by Kirill Batuzov <batuzovk@ispras.ru>
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:
14 * The above copyright notice and this permission notice shall be included in
15 * all copies or substantial portions of the Software.
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
31 #include "qemu-common.h"
34 #define CASE_OP_32_64(x) \
35 glue(glue(case INDEX_op_, x), _i32): \
36 glue(glue(case INDEX_op_, x), _i64)
44 struct tcg_temp_info
{
51 static struct tcg_temp_info temps
[TCG_MAX_TEMPS
];
53 /* Reset TEMP's state to TCG_TEMP_UNDEF. If TEMP only had one copy, remove
54 the copy flag from the left temp. */
55 static void reset_temp(TCGArg temp
)
57 if (temps
[temp
].state
== TCG_TEMP_COPY
) {
58 if (temps
[temp
].prev_copy
== temps
[temp
].next_copy
) {
59 temps
[temps
[temp
].next_copy
].state
= TCG_TEMP_UNDEF
;
61 temps
[temps
[temp
].next_copy
].prev_copy
= temps
[temp
].prev_copy
;
62 temps
[temps
[temp
].prev_copy
].next_copy
= temps
[temp
].next_copy
;
65 temps
[temp
].state
= TCG_TEMP_UNDEF
;
68 static int op_bits(TCGOpcode op
)
70 const TCGOpDef
*def
= &tcg_op_defs
[op
];
71 return def
->flags
& TCG_OPF_64BIT
? 64 : 32;
74 static TCGOpcode
op_to_movi(TCGOpcode op
)
76 switch (op_bits(op
)) {
78 return INDEX_op_movi_i32
;
80 return INDEX_op_movi_i64
;
82 fprintf(stderr
, "op_to_movi: unexpected return value of "
83 "function op_bits.\n");
88 static TCGArg
find_better_copy(TCGContext
*s
, TCGArg temp
)
92 /* If this is already a global, we can't do better. */
93 if (temp
< s
->nb_globals
) {
97 /* Search for a global first. */
98 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
99 if (i
< s
->nb_globals
) {
104 /* If it is a temp, search for a temp local. */
105 if (!s
->temps
[temp
].temp_local
) {
106 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
107 if (s
->temps
[i
].temp_local
) {
113 /* Failure to find a better representation, return the same temp. */
117 static bool temps_are_copies(TCGArg arg1
, TCGArg arg2
)
125 if (temps
[arg1
].state
!= TCG_TEMP_COPY
126 || temps
[arg2
].state
!= TCG_TEMP_COPY
) {
130 for (i
= temps
[arg1
].next_copy
; i
!= arg1
; i
= temps
[i
].next_copy
) {
139 static void tcg_opt_gen_mov(TCGContext
*s
, TCGArg
*gen_args
,
140 TCGArg dst
, TCGArg src
)
143 assert(temps
[src
].state
!= TCG_TEMP_CONST
);
145 if (s
->temps
[src
].type
== s
->temps
[dst
].type
) {
146 if (temps
[src
].state
!= TCG_TEMP_COPY
) {
147 temps
[src
].state
= TCG_TEMP_COPY
;
148 temps
[src
].next_copy
= src
;
149 temps
[src
].prev_copy
= src
;
151 temps
[dst
].state
= TCG_TEMP_COPY
;
152 temps
[dst
].next_copy
= temps
[src
].next_copy
;
153 temps
[dst
].prev_copy
= src
;
154 temps
[temps
[dst
].next_copy
].prev_copy
= dst
;
155 temps
[src
].next_copy
= dst
;
162 static void tcg_opt_gen_movi(TCGArg
*gen_args
, TCGArg dst
, TCGArg val
)
165 temps
[dst
].state
= TCG_TEMP_CONST
;
166 temps
[dst
].val
= val
;
171 static TCGOpcode
op_to_mov(TCGOpcode op
)
173 switch (op_bits(op
)) {
175 return INDEX_op_mov_i32
;
177 return INDEX_op_mov_i64
;
179 fprintf(stderr
, "op_to_mov: unexpected return value of "
180 "function op_bits.\n");
185 static TCGArg
do_constant_folding_2(TCGOpcode op
, TCGArg x
, TCGArg y
)
206 case INDEX_op_shl_i32
:
207 return (uint32_t)x
<< (uint32_t)y
;
209 case INDEX_op_shl_i64
:
210 return (uint64_t)x
<< (uint64_t)y
;
212 case INDEX_op_shr_i32
:
213 return (uint32_t)x
>> (uint32_t)y
;
215 case INDEX_op_shr_i64
:
216 return (uint64_t)x
>> (uint64_t)y
;
218 case INDEX_op_sar_i32
:
219 return (int32_t)x
>> (int32_t)y
;
221 case INDEX_op_sar_i64
:
222 return (int64_t)x
>> (int64_t)y
;
224 case INDEX_op_rotr_i32
:
225 x
= ((uint32_t)x
<< (32 - y
)) | ((uint32_t)x
>> y
);
228 case INDEX_op_rotr_i64
:
229 x
= ((uint64_t)x
<< (64 - y
)) | ((uint64_t)x
>> y
);
232 case INDEX_op_rotl_i32
:
233 x
= ((uint32_t)x
<< y
) | ((uint32_t)x
>> (32 - y
));
236 case INDEX_op_rotl_i64
:
237 x
= ((uint64_t)x
<< y
) | ((uint64_t)x
>> (64 - y
));
261 CASE_OP_32_64(ext8s
):
264 CASE_OP_32_64(ext16s
):
267 CASE_OP_32_64(ext8u
):
270 CASE_OP_32_64(ext16u
):
273 case INDEX_op_ext32s_i64
:
276 case INDEX_op_ext32u_i64
:
281 "Unrecognized operation %d in do_constant_folding.\n", op
);
286 static TCGArg
do_constant_folding(TCGOpcode op
, TCGArg x
, TCGArg y
)
288 TCGArg res
= do_constant_folding_2(op
, x
, y
);
289 if (op_bits(op
) == 32) {
295 /* Return 2 if the condition can't be simplified, and the result
296 of the condition (0 or 1) if it can */
297 static TCGArg
do_constant_folding_cond(TCGOpcode op
, TCGArg x
,
300 if (temps
[x
].state
== TCG_TEMP_CONST
&& temps
[y
].state
== TCG_TEMP_CONST
) {
301 switch (op_bits(op
)) {
305 return (uint32_t)temps
[x
].val
== (uint32_t)temps
[y
].val
;
307 return (uint32_t)temps
[x
].val
!= (uint32_t)temps
[y
].val
;
309 return (int32_t)temps
[x
].val
< (int32_t)temps
[y
].val
;
311 return (int32_t)temps
[x
].val
>= (int32_t)temps
[y
].val
;
313 return (int32_t)temps
[x
].val
<= (int32_t)temps
[y
].val
;
315 return (int32_t)temps
[x
].val
> (int32_t)temps
[y
].val
;
317 return (uint32_t)temps
[x
].val
< (uint32_t)temps
[y
].val
;
319 return (uint32_t)temps
[x
].val
>= (uint32_t)temps
[y
].val
;
321 return (uint32_t)temps
[x
].val
<= (uint32_t)temps
[y
].val
;
323 return (uint32_t)temps
[x
].val
> (uint32_t)temps
[y
].val
;
331 return (uint64_t)temps
[x
].val
== (uint64_t)temps
[y
].val
;
333 return (uint64_t)temps
[x
].val
!= (uint64_t)temps
[y
].val
;
335 return (int64_t)temps
[x
].val
< (int64_t)temps
[y
].val
;
337 return (int64_t)temps
[x
].val
>= (int64_t)temps
[y
].val
;
339 return (int64_t)temps
[x
].val
<= (int64_t)temps
[y
].val
;
341 return (int64_t)temps
[x
].val
> (int64_t)temps
[y
].val
;
343 return (uint64_t)temps
[x
].val
< (uint64_t)temps
[y
].val
;
345 return (uint64_t)temps
[x
].val
>= (uint64_t)temps
[y
].val
;
347 return (uint64_t)temps
[x
].val
<= (uint64_t)temps
[y
].val
;
349 return (uint64_t)temps
[x
].val
> (uint64_t)temps
[y
].val
;
355 } else if (temps_are_copies(x
, y
)) {
372 } else if (temps
[y
].state
== TCG_TEMP_CONST
&& temps
[y
].val
== 0) {
386 "Unrecognized bitness %d or condition %d in "
387 "do_constant_folding_cond.\n", op_bits(op
), c
);
391 static bool swap_commutative(TCGArg dest
, TCGArg
*p1
, TCGArg
*p2
)
393 TCGArg a1
= *p1
, a2
= *p2
;
395 sum
+= temps
[a1
].state
== TCG_TEMP_CONST
;
396 sum
-= temps
[a2
].state
== TCG_TEMP_CONST
;
398 /* Prefer the constant in second argument, and then the form
399 op a, a, b, which is better handled on non-RISC hosts. */
400 if (sum
> 0 || (sum
== 0 && dest
== a2
)) {
408 static bool swap_commutative2(TCGArg
*p1
, TCGArg
*p2
)
411 sum
+= temps
[p1
[0]].state
== TCG_TEMP_CONST
;
412 sum
+= temps
[p1
[1]].state
== TCG_TEMP_CONST
;
413 sum
-= temps
[p2
[0]].state
== TCG_TEMP_CONST
;
414 sum
-= temps
[p2
[1]].state
== TCG_TEMP_CONST
;
417 t
= p1
[0], p1
[0] = p2
[0], p2
[0] = t
;
418 t
= p1
[1], p1
[1] = p2
[1], p2
[1] = t
;
424 /* Propagate constants and copies, fold constant expressions. */
425 static TCGArg
*tcg_constant_folding(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
426 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
428 int i
, nb_ops
, op_index
, nb_temps
, nb_globals
, nb_call_args
;
434 /* Array VALS has an element for each temp.
435 If this temp holds a constant then its value is kept in VALS' element.
436 If this temp is a copy of other ones then the other copies are
437 available through the doubly linked circular list. */
439 nb_temps
= s
->nb_temps
;
440 nb_globals
= s
->nb_globals
;
441 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
443 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
445 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
446 op
= gen_opc_buf
[op_index
];
447 def
= &tcg_op_defs
[op
];
448 /* Do copy propagation */
449 if (op
== INDEX_op_call
) {
450 int nb_oargs
= args
[0] >> 16;
451 int nb_iargs
= args
[0] & 0xffff;
452 for (i
= nb_oargs
+ 1; i
< nb_oargs
+ nb_iargs
+ 1; i
++) {
453 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
454 args
[i
] = find_better_copy(s
, args
[i
]);
458 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
459 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
460 args
[i
] = find_better_copy(s
, args
[i
]);
465 /* For commutative operations make constant second argument */
475 swap_commutative(args
[0], &args
[1], &args
[2]);
477 CASE_OP_32_64(brcond
):
478 if (swap_commutative(-1, &args
[0], &args
[1])) {
479 args
[2] = tcg_swap_cond(args
[2]);
482 CASE_OP_32_64(setcond
):
483 if (swap_commutative(args
[0], &args
[1], &args
[2])) {
484 args
[3] = tcg_swap_cond(args
[3]);
487 CASE_OP_32_64(movcond
):
488 if (swap_commutative(-1, &args
[1], &args
[2])) {
489 args
[5] = tcg_swap_cond(args
[5]);
491 /* For movcond, we canonicalize the "false" input reg to match
492 the destination reg so that the tcg backend can implement
493 a "move if true" operation. */
494 if (swap_commutative(args
[0], &args
[4], &args
[3])) {
495 args
[5] = tcg_invert_cond(args
[5]);
498 case INDEX_op_add2_i32
:
499 swap_commutative(args
[0], &args
[2], &args
[4]);
500 swap_commutative(args
[1], &args
[3], &args
[5]);
502 case INDEX_op_brcond2_i32
:
503 if (swap_commutative2(&args
[0], &args
[2])) {
504 args
[4] = tcg_swap_cond(args
[4]);
507 case INDEX_op_setcond2_i32
:
508 if (swap_commutative2(&args
[1], &args
[3])) {
509 args
[5] = tcg_swap_cond(args
[5]);
516 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
523 if (temps
[args
[1]].state
== TCG_TEMP_CONST
524 && temps
[args
[1]].val
== 0) {
525 gen_opc_buf
[op_index
] = op_to_movi(op
);
526 tcg_opt_gen_movi(gen_args
, args
[0], 0);
536 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
547 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
548 /* Proceed with possible constant folding. */
551 if (temps
[args
[2]].state
== TCG_TEMP_CONST
552 && temps
[args
[2]].val
== 0) {
553 if (temps_are_copies(args
[0], args
[1])) {
554 gen_opc_buf
[op_index
] = INDEX_op_nop
;
556 gen_opc_buf
[op_index
] = op_to_mov(op
);
557 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
568 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
572 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
573 && temps
[args
[2]].val
== 0)) {
574 gen_opc_buf
[op_index
] = op_to_movi(op
);
575 tcg_opt_gen_movi(gen_args
, args
[0], 0);
585 /* Simplify expression for "op r, a, a => mov r, a" cases */
589 if (temps_are_copies(args
[1], args
[2])) {
590 if (temps_are_copies(args
[0], args
[1])) {
591 gen_opc_buf
[op_index
] = INDEX_op_nop
;
593 gen_opc_buf
[op_index
] = op_to_mov(op
);
594 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
605 /* Simplify expression for "op r, a, a => movi r, 0" cases */
609 if (temps_are_copies(args
[1], args
[2])) {
610 gen_opc_buf
[op_index
] = op_to_movi(op
);
611 tcg_opt_gen_movi(gen_args
, args
[0], 0);
621 /* Propagate constants through copy operations and do constant
622 folding. Constants will be substituted to arguments by register
623 allocator where needed and possible. Also detect copies. */
626 if (temps_are_copies(args
[0], args
[1])) {
628 gen_opc_buf
[op_index
] = INDEX_op_nop
;
631 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
632 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
637 /* Source argument is constant. Rewrite the operation and
638 let movi case handle it. */
640 gen_opc_buf
[op_index
] = op
;
641 args
[1] = temps
[args
[1]].val
;
644 tcg_opt_gen_movi(gen_args
, args
[0], args
[1]);
650 CASE_OP_32_64(ext8s
):
651 CASE_OP_32_64(ext8u
):
652 CASE_OP_32_64(ext16s
):
653 CASE_OP_32_64(ext16u
):
654 case INDEX_op_ext32s_i64
:
655 case INDEX_op_ext32u_i64
:
656 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
657 gen_opc_buf
[op_index
] = op_to_movi(op
);
658 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
659 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
662 gen_args
[0] = args
[0];
663 gen_args
[1] = args
[1];
684 if (temps
[args
[1]].state
== TCG_TEMP_CONST
685 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
686 gen_opc_buf
[op_index
] = op_to_movi(op
);
687 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
689 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
693 gen_args
[0] = args
[0];
694 gen_args
[1] = args
[1];
695 gen_args
[2] = args
[2];
700 CASE_OP_32_64(deposit
):
701 if (temps
[args
[1]].state
== TCG_TEMP_CONST
702 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
703 gen_opc_buf
[op_index
] = op_to_movi(op
);
704 tmp
= ((1ull << args
[4]) - 1);
705 tmp
= (temps
[args
[1]].val
& ~(tmp
<< args
[3]))
706 | ((temps
[args
[2]].val
& tmp
) << args
[3]);
707 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
711 gen_args
[0] = args
[0];
712 gen_args
[1] = args
[1];
713 gen_args
[2] = args
[2];
714 gen_args
[3] = args
[3];
715 gen_args
[4] = args
[4];
720 CASE_OP_32_64(setcond
):
721 tmp
= do_constant_folding_cond(op
, args
[1], args
[2], args
[3]);
723 gen_opc_buf
[op_index
] = op_to_movi(op
);
724 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
728 gen_args
[0] = args
[0];
729 gen_args
[1] = args
[1];
730 gen_args
[2] = args
[2];
731 gen_args
[3] = args
[3];
736 CASE_OP_32_64(brcond
):
737 tmp
= do_constant_folding_cond(op
, args
[0], args
[1], args
[2]);
740 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
741 gen_opc_buf
[op_index
] = INDEX_op_br
;
742 gen_args
[0] = args
[3];
745 gen_opc_buf
[op_index
] = INDEX_op_nop
;
748 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
750 gen_args
[0] = args
[0];
751 gen_args
[1] = args
[1];
752 gen_args
[2] = args
[2];
753 gen_args
[3] = args
[3];
758 CASE_OP_32_64(movcond
):
759 tmp
= do_constant_folding_cond(op
, args
[1], args
[2], args
[5]);
761 if (temps_are_copies(args
[0], args
[4-tmp
])) {
762 gen_opc_buf
[op_index
] = INDEX_op_nop
;
763 } else if (temps
[args
[4-tmp
]].state
== TCG_TEMP_CONST
) {
764 gen_opc_buf
[op_index
] = op_to_movi(op
);
765 tcg_opt_gen_movi(gen_args
, args
[0], temps
[args
[4-tmp
]].val
);
768 gen_opc_buf
[op_index
] = op_to_mov(op
);
769 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[4-tmp
]);
774 gen_args
[0] = args
[0];
775 gen_args
[1] = args
[1];
776 gen_args
[2] = args
[2];
777 gen_args
[3] = args
[3];
778 gen_args
[4] = args
[4];
779 gen_args
[5] = args
[5];
785 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
786 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
787 for (i
= 0; i
< nb_globals
; i
++) {
791 for (i
= 0; i
< (args
[0] >> 16); i
++) {
792 reset_temp(args
[i
+ 1]);
794 i
= nb_call_args
+ 3;
803 /* Default case: we do know nothing about operation so no
804 propagation is done. We trash everything if the operation
805 is the end of a basic block, otherwise we only trash the
807 if (def
->flags
& TCG_OPF_BB_END
) {
808 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
810 for (i
= 0; i
< def
->nb_oargs
; i
++) {
814 for (i
= 0; i
< def
->nb_args
; i
++) {
815 gen_args
[i
] = args
[i
];
817 args
+= def
->nb_args
;
818 gen_args
+= def
->nb_args
;
826 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
827 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
830 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);