]>
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)
46 struct tcg_temp_info
{
53 static struct tcg_temp_info temps
[TCG_MAX_TEMPS
];
55 /* Reset TEMP's state to TCG_TEMP_ANY. If TEMP was a representative of some
56 class of equivalent temp's, a new representative should be chosen in this
58 static void reset_temp(TCGArg temp
, int nb_temps
, int nb_globals
)
61 TCGArg new_base
= (TCGArg
)-1;
62 if (temps
[temp
].state
== TCG_TEMP_HAS_COPY
) {
63 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
64 if (i
>= nb_globals
) {
65 temps
[i
].state
= TCG_TEMP_HAS_COPY
;
70 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
71 if (new_base
== (TCGArg
)-1) {
72 temps
[i
].state
= TCG_TEMP_ANY
;
74 temps
[i
].val
= new_base
;
77 temps
[temps
[temp
].next_copy
].prev_copy
= temps
[temp
].prev_copy
;
78 temps
[temps
[temp
].prev_copy
].next_copy
= temps
[temp
].next_copy
;
79 } else if (temps
[temp
].state
== TCG_TEMP_COPY
) {
80 temps
[temps
[temp
].next_copy
].prev_copy
= temps
[temp
].prev_copy
;
81 temps
[temps
[temp
].prev_copy
].next_copy
= temps
[temp
].next_copy
;
82 new_base
= temps
[temp
].val
;
84 temps
[temp
].state
= TCG_TEMP_ANY
;
85 if (new_base
!= (TCGArg
)-1 && temps
[new_base
].next_copy
== new_base
) {
86 temps
[new_base
].state
= TCG_TEMP_ANY
;
90 static int op_bits(TCGOpcode op
)
92 const TCGOpDef
*def
= &tcg_op_defs
[op
];
93 return def
->flags
& TCG_OPF_64BIT
? 64 : 32;
96 static TCGOpcode
op_to_movi(TCGOpcode op
)
98 switch (op_bits(op
)) {
100 return INDEX_op_movi_i32
;
102 return INDEX_op_movi_i64
;
104 fprintf(stderr
, "op_to_movi: unexpected return value of "
105 "function op_bits.\n");
110 static void tcg_opt_gen_mov(TCGArg
*gen_args
, TCGArg dst
, TCGArg src
,
111 int nb_temps
, int nb_globals
)
113 reset_temp(dst
, nb_temps
, nb_globals
);
114 assert(temps
[src
].state
!= TCG_TEMP_COPY
);
115 if (src
>= nb_globals
) {
116 assert(temps
[src
].state
!= TCG_TEMP_CONST
);
117 if (temps
[src
].state
!= TCG_TEMP_HAS_COPY
) {
118 temps
[src
].state
= TCG_TEMP_HAS_COPY
;
119 temps
[src
].next_copy
= src
;
120 temps
[src
].prev_copy
= src
;
122 temps
[dst
].state
= TCG_TEMP_COPY
;
123 temps
[dst
].val
= src
;
124 temps
[dst
].next_copy
= temps
[src
].next_copy
;
125 temps
[dst
].prev_copy
= src
;
126 temps
[temps
[dst
].next_copy
].prev_copy
= dst
;
127 temps
[src
].next_copy
= dst
;
133 static void tcg_opt_gen_movi(TCGArg
*gen_args
, TCGArg dst
, TCGArg val
,
134 int nb_temps
, int nb_globals
)
136 reset_temp(dst
, nb_temps
, nb_globals
);
137 temps
[dst
].state
= TCG_TEMP_CONST
;
138 temps
[dst
].val
= val
;
143 static TCGOpcode
op_to_mov(TCGOpcode op
)
145 switch (op_bits(op
)) {
147 return INDEX_op_mov_i32
;
149 return INDEX_op_mov_i64
;
151 fprintf(stderr
, "op_to_mov: unexpected return value of "
152 "function op_bits.\n");
157 static TCGArg
do_constant_folding_2(TCGOpcode op
, TCGArg x
, TCGArg y
)
178 case INDEX_op_shl_i32
:
179 return (uint32_t)x
<< (uint32_t)y
;
181 case INDEX_op_shl_i64
:
182 return (uint64_t)x
<< (uint64_t)y
;
184 case INDEX_op_shr_i32
:
185 return (uint32_t)x
>> (uint32_t)y
;
187 case INDEX_op_shr_i64
:
188 return (uint64_t)x
>> (uint64_t)y
;
190 case INDEX_op_sar_i32
:
191 return (int32_t)x
>> (int32_t)y
;
193 case INDEX_op_sar_i64
:
194 return (int64_t)x
>> (int64_t)y
;
196 case INDEX_op_rotr_i32
:
197 x
= ((uint32_t)x
<< (32 - y
)) | ((uint32_t)x
>> y
);
200 case INDEX_op_rotr_i64
:
201 x
= ((uint64_t)x
<< (64 - y
)) | ((uint64_t)x
>> y
);
204 case INDEX_op_rotl_i32
:
205 x
= ((uint32_t)x
<< y
) | ((uint32_t)x
>> (32 - y
));
208 case INDEX_op_rotl_i64
:
209 x
= ((uint64_t)x
<< y
) | ((uint64_t)x
>> (64 - y
));
233 CASE_OP_32_64(ext8s
):
236 CASE_OP_32_64(ext16s
):
239 CASE_OP_32_64(ext8u
):
242 CASE_OP_32_64(ext16u
):
245 case INDEX_op_ext32s_i64
:
248 case INDEX_op_ext32u_i64
:
253 "Unrecognized operation %d in do_constant_folding.\n", op
);
258 static TCGArg
do_constant_folding(TCGOpcode op
, TCGArg x
, TCGArg y
)
260 TCGArg res
= do_constant_folding_2(op
, x
, y
);
261 if (op_bits(op
) == 32) {
267 static TCGArg
do_constant_folding_cond(TCGOpcode op
, TCGArg x
,
270 switch (op_bits(op
)) {
274 return (uint32_t)x
== (uint32_t)y
;
276 return (uint32_t)x
!= (uint32_t)y
;
278 return (int32_t)x
< (int32_t)y
;
280 return (int32_t)x
>= (int32_t)y
;
282 return (int32_t)x
<= (int32_t)y
;
284 return (int32_t)x
> (int32_t)y
;
286 return (uint32_t)x
< (uint32_t)y
;
288 return (uint32_t)x
>= (uint32_t)y
;
290 return (uint32_t)x
<= (uint32_t)y
;
292 return (uint32_t)x
> (uint32_t)y
;
298 return (uint64_t)x
== (uint64_t)y
;
300 return (uint64_t)x
!= (uint64_t)y
;
302 return (int64_t)x
< (int64_t)y
;
304 return (int64_t)x
>= (int64_t)y
;
306 return (int64_t)x
<= (int64_t)y
;
308 return (int64_t)x
> (int64_t)y
;
310 return (uint64_t)x
< (uint64_t)y
;
312 return (uint64_t)x
>= (uint64_t)y
;
314 return (uint64_t)x
<= (uint64_t)y
;
316 return (uint64_t)x
> (uint64_t)y
;
322 "Unrecognized bitness %d or condition %d in "
323 "do_constant_folding_cond.\n", op_bits(op
), c
);
328 /* Propagate constants and copies, fold constant expressions. */
329 static TCGArg
*tcg_constant_folding(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
330 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
332 int i
, nb_ops
, op_index
, nb_temps
, nb_globals
, nb_call_args
;
337 /* Array VALS has an element for each temp.
338 If this temp holds a constant then its value is kept in VALS' element.
339 If this temp is a copy of other ones then this equivalence class'
340 representative is kept in VALS' element.
341 If this temp is neither copy nor constant then corresponding VALS'
342 element is unused. */
344 nb_temps
= s
->nb_temps
;
345 nb_globals
= s
->nb_globals
;
346 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
348 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
350 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
351 op
= gen_opc_buf
[op_index
];
352 def
= &tcg_op_defs
[op
];
353 /* Do copy propagation */
354 if (!(def
->flags
& (TCG_OPF_CALL_CLOBBER
| TCG_OPF_SIDE_EFFECTS
))) {
355 assert(op
!= INDEX_op_call
);
356 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
357 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
358 args
[i
] = temps
[args
[i
]].val
;
363 /* For commutative operations make constant second argument */
373 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
379 CASE_OP_32_64(brcond
):
380 if (temps
[args
[0]].state
== TCG_TEMP_CONST
381 && temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
385 args
[2] = tcg_swap_cond(args
[2]);
388 CASE_OP_32_64(setcond
):
389 if (temps
[args
[1]].state
== TCG_TEMP_CONST
390 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
394 args
[3] = tcg_swap_cond(args
[3]);
401 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
408 if (temps
[args
[1]].state
== TCG_TEMP_CONST
409 && temps
[args
[1]].val
== 0) {
410 gen_opc_buf
[op_index
] = op_to_movi(op
);
411 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
421 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
432 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
433 /* Proceed with possible constant folding. */
436 if (temps
[args
[2]].state
== TCG_TEMP_CONST
437 && temps
[args
[2]].val
== 0) {
438 if ((temps
[args
[0]].state
== TCG_TEMP_COPY
439 && temps
[args
[0]].val
== args
[1])
440 || args
[0] == args
[1]) {
441 gen_opc_buf
[op_index
] = INDEX_op_nop
;
443 gen_opc_buf
[op_index
] = op_to_mov(op
);
444 tcg_opt_gen_mov(gen_args
, args
[0], args
[1],
445 nb_temps
, nb_globals
);
456 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
460 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
461 && temps
[args
[2]].val
== 0)) {
462 gen_opc_buf
[op_index
] = op_to_movi(op
);
463 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
473 /* Simplify expression for "op r, a, a => mov r, a" cases */
477 if (args
[1] == args
[2]) {
478 if (args
[1] == args
[0]) {
479 gen_opc_buf
[op_index
] = INDEX_op_nop
;
481 gen_opc_buf
[op_index
] = op_to_mov(op
);
482 tcg_opt_gen_mov(gen_args
, args
[0], args
[1], nb_temps
,
494 /* Propagate constants through copy operations and do constant
495 folding. Constants will be substituted to arguments by register
496 allocator where needed and possible. Also detect copies. */
499 if ((temps
[args
[1]].state
== TCG_TEMP_COPY
500 && temps
[args
[1]].val
== args
[0])
501 || args
[0] == args
[1]) {
503 gen_opc_buf
[op_index
] = INDEX_op_nop
;
506 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
507 tcg_opt_gen_mov(gen_args
, args
[0], args
[1],
508 nb_temps
, nb_globals
);
513 /* Source argument is constant. Rewrite the operation and
514 let movi case handle it. */
516 gen_opc_buf
[op_index
] = op
;
517 args
[1] = temps
[args
[1]].val
;
520 tcg_opt_gen_movi(gen_args
, args
[0], args
[1], nb_temps
, nb_globals
);
526 CASE_OP_32_64(ext8s
):
527 CASE_OP_32_64(ext8u
):
528 CASE_OP_32_64(ext16s
):
529 CASE_OP_32_64(ext16u
):
530 case INDEX_op_ext32s_i64
:
531 case INDEX_op_ext32u_i64
:
532 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
533 gen_opc_buf
[op_index
] = op_to_movi(op
);
534 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
535 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
537 reset_temp(args
[0], nb_temps
, nb_globals
);
538 gen_args
[0] = args
[0];
539 gen_args
[1] = args
[1];
560 if (temps
[args
[1]].state
== TCG_TEMP_CONST
561 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
562 gen_opc_buf
[op_index
] = op_to_movi(op
);
563 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
565 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
568 reset_temp(args
[0], nb_temps
, nb_globals
);
569 gen_args
[0] = args
[0];
570 gen_args
[1] = args
[1];
571 gen_args
[2] = args
[2];
576 CASE_OP_32_64(setcond
):
577 if (temps
[args
[1]].state
== TCG_TEMP_CONST
578 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
579 gen_opc_buf
[op_index
] = op_to_movi(op
);
580 tmp
= do_constant_folding_cond(op
, temps
[args
[1]].val
,
581 temps
[args
[2]].val
, args
[3]);
582 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
585 reset_temp(args
[0], nb_temps
, nb_globals
);
586 gen_args
[0] = args
[0];
587 gen_args
[1] = args
[1];
588 gen_args
[2] = args
[2];
589 gen_args
[3] = args
[3];
594 CASE_OP_32_64(brcond
):
595 if (temps
[args
[0]].state
== TCG_TEMP_CONST
596 && temps
[args
[1]].state
== TCG_TEMP_CONST
) {
597 if (do_constant_folding_cond(op
, temps
[args
[0]].val
,
598 temps
[args
[1]].val
, args
[2])) {
599 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
600 gen_opc_buf
[op_index
] = INDEX_op_br
;
601 gen_args
[0] = args
[3];
604 gen_opc_buf
[op_index
] = INDEX_op_nop
;
607 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
608 reset_temp(args
[0], nb_temps
, nb_globals
);
609 gen_args
[0] = args
[0];
610 gen_args
[1] = args
[1];
611 gen_args
[2] = args
[2];
612 gen_args
[3] = args
[3];
618 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
619 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
620 for (i
= 0; i
< nb_globals
; i
++) {
621 reset_temp(i
, nb_temps
, nb_globals
);
624 for (i
= 0; i
< (args
[0] >> 16); i
++) {
625 reset_temp(args
[i
+ 1], nb_temps
, nb_globals
);
627 i
= nb_call_args
+ 3;
635 case INDEX_op_set_label
:
638 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
639 for (i
= 0; i
< def
->nb_args
; i
++) {
646 /* Default case: we do know nothing about operation so no
647 propagation is done. We only trash output args. */
648 for (i
= 0; i
< def
->nb_oargs
; i
++) {
649 reset_temp(args
[i
], nb_temps
, nb_globals
);
651 for (i
= 0; i
< def
->nb_args
; i
++) {
652 gen_args
[i
] = args
[i
];
654 args
+= def
->nb_args
;
655 gen_args
+= def
->nb_args
;
663 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
664 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
667 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);