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
;
329 return (uint64_t)temps
[x
].val
== (uint64_t)temps
[y
].val
;
331 return (uint64_t)temps
[x
].val
!= (uint64_t)temps
[y
].val
;
333 return (int64_t)temps
[x
].val
< (int64_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 (uint64_t)temps
[x
].val
< (uint64_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
;
351 } else if (temps_are_copies(x
, y
)) {
366 } else if (temps
[y
].state
== TCG_TEMP_CONST
&& temps
[y
].val
== 0) {
380 "Unrecognized bitness %d or condition %d in "
381 "do_constant_folding_cond.\n", op_bits(op
), c
);
385 /* Propagate constants and copies, fold constant expressions. */
386 static TCGArg
*tcg_constant_folding(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
387 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
389 int i
, nb_ops
, op_index
, nb_temps
, nb_globals
, nb_call_args
;
396 /* Array VALS has an element for each temp.
397 If this temp holds a constant then its value is kept in VALS' element.
398 If this temp is a copy of other ones then the other copies are
399 available through the doubly linked circular list. */
401 nb_temps
= s
->nb_temps
;
402 nb_globals
= s
->nb_globals
;
403 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
405 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
407 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
408 op
= gen_opc_buf
[op_index
];
409 def
= &tcg_op_defs
[op
];
410 /* Do copy propagation */
411 if (op
== INDEX_op_call
) {
412 int nb_oargs
= args
[0] >> 16;
413 int nb_iargs
= args
[0] & 0xffff;
414 for (i
= nb_oargs
+ 1; i
< nb_oargs
+ nb_iargs
+ 1; i
++) {
415 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
416 args
[i
] = find_better_copy(s
, args
[i
]);
420 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
421 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
422 args
[i
] = find_better_copy(s
, args
[i
]);
427 /* For commutative operations make constant second argument */
437 /* Prefer the constant in second argument, and then the form
438 op a, a, b, which is better handled on non-RISC hosts. */
439 if (temps
[args
[1]].state
== TCG_TEMP_CONST
|| (args
[0] == args
[2]
440 && temps
[args
[2]].state
!= TCG_TEMP_CONST
)) {
446 CASE_OP_32_64(brcond
):
447 if (temps
[args
[0]].state
== TCG_TEMP_CONST
448 && temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
452 args
[2] = tcg_swap_cond(args
[2]);
455 CASE_OP_32_64(setcond
):
456 if (temps
[args
[1]].state
== TCG_TEMP_CONST
457 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
461 args
[3] = tcg_swap_cond(args
[3]);
464 CASE_OP_32_64(movcond
):
466 if (temps
[args
[1]].state
== TCG_TEMP_CONST
467 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
471 cond
= tcg_swap_cond(cond
);
473 /* For movcond, we canonicalize the "false" input reg to match
474 the destination reg so that the tcg backend can implement
475 a "move if true" operation. */
476 if (args
[0] == args
[3]) {
480 cond
= tcg_invert_cond(cond
);
487 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
494 if (temps
[args
[1]].state
== TCG_TEMP_CONST
495 && temps
[args
[1]].val
== 0) {
496 gen_opc_buf
[op_index
] = op_to_movi(op
);
497 tcg_opt_gen_movi(gen_args
, args
[0], 0);
507 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
518 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
519 /* Proceed with possible constant folding. */
522 if (temps
[args
[2]].state
== TCG_TEMP_CONST
523 && temps
[args
[2]].val
== 0) {
524 if (temps_are_copies(args
[0], args
[1])) {
525 gen_opc_buf
[op_index
] = INDEX_op_nop
;
527 gen_opc_buf
[op_index
] = op_to_mov(op
);
528 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
539 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
543 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
544 && temps
[args
[2]].val
== 0)) {
545 gen_opc_buf
[op_index
] = op_to_movi(op
);
546 tcg_opt_gen_movi(gen_args
, args
[0], 0);
556 /* Simplify expression for "op r, a, a => mov r, a" cases */
560 if (temps_are_copies(args
[1], args
[2])) {
561 if (temps_are_copies(args
[0], args
[1])) {
562 gen_opc_buf
[op_index
] = INDEX_op_nop
;
564 gen_opc_buf
[op_index
] = op_to_mov(op
);
565 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
576 /* Simplify expression for "op r, a, a => movi r, 0" cases */
580 if (temps_are_copies(args
[1], args
[2])) {
581 gen_opc_buf
[op_index
] = op_to_movi(op
);
582 tcg_opt_gen_movi(gen_args
, args
[0], 0);
592 /* Propagate constants through copy operations and do constant
593 folding. Constants will be substituted to arguments by register
594 allocator where needed and possible. Also detect copies. */
597 if (temps_are_copies(args
[0], args
[1])) {
599 gen_opc_buf
[op_index
] = INDEX_op_nop
;
602 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
603 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
608 /* Source argument is constant. Rewrite the operation and
609 let movi case handle it. */
611 gen_opc_buf
[op_index
] = op
;
612 args
[1] = temps
[args
[1]].val
;
615 tcg_opt_gen_movi(gen_args
, args
[0], args
[1]);
621 CASE_OP_32_64(ext8s
):
622 CASE_OP_32_64(ext8u
):
623 CASE_OP_32_64(ext16s
):
624 CASE_OP_32_64(ext16u
):
625 case INDEX_op_ext32s_i64
:
626 case INDEX_op_ext32u_i64
:
627 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
628 gen_opc_buf
[op_index
] = op_to_movi(op
);
629 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
630 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
633 gen_args
[0] = args
[0];
634 gen_args
[1] = args
[1];
655 if (temps
[args
[1]].state
== TCG_TEMP_CONST
656 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
657 gen_opc_buf
[op_index
] = op_to_movi(op
);
658 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
660 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
664 gen_args
[0] = args
[0];
665 gen_args
[1] = args
[1];
666 gen_args
[2] = args
[2];
671 CASE_OP_32_64(setcond
):
672 tmp
= do_constant_folding_cond(op
, args
[1], args
[2], args
[3]);
674 gen_opc_buf
[op_index
] = op_to_movi(op
);
675 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
679 gen_args
[0] = args
[0];
680 gen_args
[1] = args
[1];
681 gen_args
[2] = args
[2];
682 gen_args
[3] = args
[3];
687 CASE_OP_32_64(brcond
):
688 tmp
= do_constant_folding_cond(op
, args
[0], args
[1], args
[2]);
691 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
692 gen_opc_buf
[op_index
] = INDEX_op_br
;
693 gen_args
[0] = args
[3];
696 gen_opc_buf
[op_index
] = INDEX_op_nop
;
699 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
701 gen_args
[0] = args
[0];
702 gen_args
[1] = args
[1];
703 gen_args
[2] = args
[2];
704 gen_args
[3] = args
[3];
709 CASE_OP_32_64(movcond
):
710 tmp
= do_constant_folding_cond(op
, args
[1], args
[2], args
[5]);
712 if (temps_are_copies(args
[0], args
[4-tmp
])) {
713 gen_opc_buf
[op_index
] = INDEX_op_nop
;
714 } else if (temps
[args
[4-tmp
]].state
== TCG_TEMP_CONST
) {
715 gen_opc_buf
[op_index
] = op_to_movi(op
);
716 tcg_opt_gen_movi(gen_args
, args
[0], temps
[args
[4-tmp
]].val
);
719 gen_opc_buf
[op_index
] = op_to_mov(op
);
720 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[4-tmp
]);
725 gen_args
[0] = args
[0];
726 gen_args
[1] = args
[1];
727 gen_args
[2] = args
[2];
728 gen_args
[3] = args
[3];
729 gen_args
[4] = args
[4];
730 gen_args
[5] = args
[5];
736 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
737 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
738 for (i
= 0; i
< nb_globals
; i
++) {
742 for (i
= 0; i
< (args
[0] >> 16); i
++) {
743 reset_temp(args
[i
+ 1]);
745 i
= nb_call_args
+ 3;
754 /* Default case: we do know nothing about operation so no
755 propagation is done. We trash everything if the operation
756 is the end of a basic block, otherwise we only trash the
758 if (def
->flags
& TCG_OPF_BB_END
) {
759 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
761 for (i
= 0; i
< def
->nb_oargs
; i
++) {
765 for (i
= 0; i
< def
->nb_args
; i
++) {
766 gen_args
[i
] = args
[i
];
768 args
+= def
->nb_args
;
769 gen_args
+= def
->nb_args
;
777 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
778 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
781 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);