]>
git.proxmox.com Git - 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 static bool do_constant_folding_cond_32(uint32_t x
, uint32_t y
, TCGCond c
)
303 return (int32_t)x
< (int32_t)y
;
305 return (int32_t)x
>= (int32_t)y
;
307 return (int32_t)x
<= (int32_t)y
;
309 return (int32_t)x
> (int32_t)y
;
323 static bool do_constant_folding_cond_64(uint64_t x
, uint64_t y
, TCGCond c
)
331 return (int64_t)x
< (int64_t)y
;
333 return (int64_t)x
>= (int64_t)y
;
335 return (int64_t)x
<= (int64_t)y
;
337 return (int64_t)x
> (int64_t)y
;
351 static bool do_constant_folding_cond_eq(TCGCond c
)
371 /* Return 2 if the condition can't be simplified, and the result
372 of the condition (0 or 1) if it can */
373 static TCGArg
do_constant_folding_cond(TCGOpcode op
, TCGArg x
,
376 if (temps
[x
].state
== TCG_TEMP_CONST
&& temps
[y
].state
== TCG_TEMP_CONST
) {
377 switch (op_bits(op
)) {
379 return do_constant_folding_cond_32(temps
[x
].val
, temps
[y
].val
, c
);
381 return do_constant_folding_cond_64(temps
[x
].val
, temps
[y
].val
, c
);
385 } else if (temps_are_copies(x
, y
)) {
386 return do_constant_folding_cond_eq(c
);
387 } else if (temps
[y
].state
== TCG_TEMP_CONST
&& temps
[y
].val
== 0) {
401 static bool swap_commutative(TCGArg dest
, TCGArg
*p1
, TCGArg
*p2
)
403 TCGArg a1
= *p1
, a2
= *p2
;
405 sum
+= temps
[a1
].state
== TCG_TEMP_CONST
;
406 sum
-= temps
[a2
].state
== TCG_TEMP_CONST
;
408 /* Prefer the constant in second argument, and then the form
409 op a, a, b, which is better handled on non-RISC hosts. */
410 if (sum
> 0 || (sum
== 0 && dest
== a2
)) {
418 static bool swap_commutative2(TCGArg
*p1
, TCGArg
*p2
)
421 sum
+= temps
[p1
[0]].state
== TCG_TEMP_CONST
;
422 sum
+= temps
[p1
[1]].state
== TCG_TEMP_CONST
;
423 sum
-= temps
[p2
[0]].state
== TCG_TEMP_CONST
;
424 sum
-= temps
[p2
[1]].state
== TCG_TEMP_CONST
;
427 t
= p1
[0], p1
[0] = p2
[0], p2
[0] = t
;
428 t
= p1
[1], p1
[1] = p2
[1], p2
[1] = t
;
434 /* Propagate constants and copies, fold constant expressions. */
435 static TCGArg
*tcg_constant_folding(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
436 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
438 int i
, nb_ops
, op_index
, nb_temps
, nb_globals
, nb_call_args
;
444 /* Array VALS has an element for each temp.
445 If this temp holds a constant then its value is kept in VALS' element.
446 If this temp is a copy of other ones then the other copies are
447 available through the doubly linked circular list. */
449 nb_temps
= s
->nb_temps
;
450 nb_globals
= s
->nb_globals
;
451 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
453 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
455 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
456 op
= gen_opc_buf
[op_index
];
457 def
= &tcg_op_defs
[op
];
458 /* Do copy propagation */
459 if (op
== INDEX_op_call
) {
460 int nb_oargs
= args
[0] >> 16;
461 int nb_iargs
= args
[0] & 0xffff;
462 for (i
= nb_oargs
+ 1; i
< nb_oargs
+ nb_iargs
+ 1; i
++) {
463 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
464 args
[i
] = find_better_copy(s
, args
[i
]);
468 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
469 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
470 args
[i
] = find_better_copy(s
, args
[i
]);
475 /* For commutative operations make constant second argument */
485 swap_commutative(args
[0], &args
[1], &args
[2]);
487 CASE_OP_32_64(brcond
):
488 if (swap_commutative(-1, &args
[0], &args
[1])) {
489 args
[2] = tcg_swap_cond(args
[2]);
492 CASE_OP_32_64(setcond
):
493 if (swap_commutative(args
[0], &args
[1], &args
[2])) {
494 args
[3] = tcg_swap_cond(args
[3]);
497 CASE_OP_32_64(movcond
):
498 if (swap_commutative(-1, &args
[1], &args
[2])) {
499 args
[5] = tcg_swap_cond(args
[5]);
501 /* For movcond, we canonicalize the "false" input reg to match
502 the destination reg so that the tcg backend can implement
503 a "move if true" operation. */
504 if (swap_commutative(args
[0], &args
[4], &args
[3])) {
505 args
[5] = tcg_invert_cond(args
[5]);
508 case INDEX_op_add2_i32
:
509 swap_commutative(args
[0], &args
[2], &args
[4]);
510 swap_commutative(args
[1], &args
[3], &args
[5]);
512 case INDEX_op_brcond2_i32
:
513 if (swap_commutative2(&args
[0], &args
[2])) {
514 args
[4] = tcg_swap_cond(args
[4]);
517 case INDEX_op_setcond2_i32
:
518 if (swap_commutative2(&args
[1], &args
[3])) {
519 args
[5] = tcg_swap_cond(args
[5]);
526 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
533 if (temps
[args
[1]].state
== TCG_TEMP_CONST
534 && temps
[args
[1]].val
== 0) {
535 gen_opc_buf
[op_index
] = op_to_movi(op
);
536 tcg_opt_gen_movi(gen_args
, args
[0], 0);
546 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
557 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
558 /* Proceed with possible constant folding. */
561 if (temps
[args
[2]].state
== TCG_TEMP_CONST
562 && temps
[args
[2]].val
== 0) {
563 if (temps_are_copies(args
[0], args
[1])) {
564 gen_opc_buf
[op_index
] = INDEX_op_nop
;
566 gen_opc_buf
[op_index
] = op_to_mov(op
);
567 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
578 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
582 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
583 && temps
[args
[2]].val
== 0)) {
584 gen_opc_buf
[op_index
] = op_to_movi(op
);
585 tcg_opt_gen_movi(gen_args
, args
[0], 0);
595 /* Simplify expression for "op r, a, a => mov r, a" cases */
599 if (temps_are_copies(args
[1], args
[2])) {
600 if (temps_are_copies(args
[0], args
[1])) {
601 gen_opc_buf
[op_index
] = INDEX_op_nop
;
603 gen_opc_buf
[op_index
] = op_to_mov(op
);
604 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
615 /* Simplify expression for "op r, a, a => movi r, 0" cases */
619 if (temps_are_copies(args
[1], args
[2])) {
620 gen_opc_buf
[op_index
] = op_to_movi(op
);
621 tcg_opt_gen_movi(gen_args
, args
[0], 0);
631 /* Propagate constants through copy operations and do constant
632 folding. Constants will be substituted to arguments by register
633 allocator where needed and possible. Also detect copies. */
636 if (temps_are_copies(args
[0], args
[1])) {
638 gen_opc_buf
[op_index
] = INDEX_op_nop
;
641 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
642 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
647 /* Source argument is constant. Rewrite the operation and
648 let movi case handle it. */
650 gen_opc_buf
[op_index
] = op
;
651 args
[1] = temps
[args
[1]].val
;
654 tcg_opt_gen_movi(gen_args
, args
[0], args
[1]);
661 CASE_OP_32_64(ext8s
):
662 CASE_OP_32_64(ext8u
):
663 CASE_OP_32_64(ext16s
):
664 CASE_OP_32_64(ext16u
):
665 case INDEX_op_ext32s_i64
:
666 case INDEX_op_ext32u_i64
:
667 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
668 gen_opc_buf
[op_index
] = op_to_movi(op
);
669 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
670 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
693 if (temps
[args
[1]].state
== TCG_TEMP_CONST
694 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
695 gen_opc_buf
[op_index
] = op_to_movi(op
);
696 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
698 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
705 CASE_OP_32_64(deposit
):
706 if (temps
[args
[1]].state
== TCG_TEMP_CONST
707 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
708 gen_opc_buf
[op_index
] = op_to_movi(op
);
709 tmp
= ((1ull << args
[4]) - 1);
710 tmp
= (temps
[args
[1]].val
& ~(tmp
<< args
[3]))
711 | ((temps
[args
[2]].val
& tmp
) << args
[3]);
712 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
719 CASE_OP_32_64(setcond
):
720 tmp
= do_constant_folding_cond(op
, args
[1], args
[2], args
[3]);
722 gen_opc_buf
[op_index
] = op_to_movi(op
);
723 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
730 CASE_OP_32_64(brcond
):
731 tmp
= do_constant_folding_cond(op
, args
[0], args
[1], args
[2]);
734 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
735 gen_opc_buf
[op_index
] = INDEX_op_br
;
736 gen_args
[0] = args
[3];
739 gen_opc_buf
[op_index
] = INDEX_op_nop
;
746 CASE_OP_32_64(movcond
):
747 tmp
= do_constant_folding_cond(op
, args
[1], args
[2], args
[5]);
749 if (temps_are_copies(args
[0], args
[4-tmp
])) {
750 gen_opc_buf
[op_index
] = INDEX_op_nop
;
751 } else if (temps
[args
[4-tmp
]].state
== TCG_TEMP_CONST
) {
752 gen_opc_buf
[op_index
] = op_to_movi(op
);
753 tcg_opt_gen_movi(gen_args
, args
[0], temps
[args
[4-tmp
]].val
);
756 gen_opc_buf
[op_index
] = op_to_mov(op
);
757 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[4-tmp
]);
765 case INDEX_op_brcond2_i32
:
766 /* Simplify LT/GE comparisons vs zero to a single compare
767 vs the high word of the input. */
768 if ((args
[4] == TCG_COND_LT
|| args
[4] == TCG_COND_GE
)
769 && temps
[args
[2]].state
== TCG_TEMP_CONST
770 && temps
[args
[3]].state
== TCG_TEMP_CONST
771 && temps
[args
[2]].val
== 0
772 && temps
[args
[3]].val
== 0) {
773 gen_opc_buf
[op_index
] = INDEX_op_brcond_i32
;
774 gen_args
[0] = args
[1];
775 gen_args
[1] = args
[3];
776 gen_args
[2] = args
[4];
777 gen_args
[3] = args
[5];
780 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
785 case INDEX_op_setcond2_i32
:
786 /* Simplify LT/GE comparisons vs zero to a single compare
787 vs the high word of the input. */
788 if ((args
[5] == TCG_COND_LT
|| args
[5] == TCG_COND_GE
)
789 && temps
[args
[3]].state
== TCG_TEMP_CONST
790 && temps
[args
[4]].state
== TCG_TEMP_CONST
791 && temps
[args
[3]].val
== 0
792 && temps
[args
[4]].val
== 0) {
793 gen_opc_buf
[op_index
] = INDEX_op_setcond_i32
;
794 gen_args
[0] = args
[0];
795 gen_args
[1] = args
[2];
796 gen_args
[2] = args
[4];
797 gen_args
[3] = args
[5];
805 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
806 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
807 for (i
= 0; i
< nb_globals
; i
++) {
811 for (i
= 0; i
< (args
[0] >> 16); i
++) {
812 reset_temp(args
[i
+ 1]);
814 i
= nb_call_args
+ 3;
825 /* Default case: we know nothing about operation (or were unable
826 to compute the operation result) so no propagation is done.
827 We trash everything if the operation is the end of a basic
828 block, otherwise we only trash the output args. */
829 if (def
->flags
& TCG_OPF_BB_END
) {
830 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
832 for (i
= 0; i
< def
->nb_oargs
; i
++) {
836 for (i
= 0; i
< def
->nb_args
; i
++) {
837 gen_args
[i
] = args
[i
];
839 args
+= def
->nb_args
;
840 gen_args
+= def
->nb_args
;
848 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
849 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
852 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);