]>
git.proxmox.com Git - mirror_qemu.git/blob - tcg/optimize.c
da8dffe9cdd39ca56c147b61cd0050a3aaf52e49
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)
45 struct tcg_temp_info
{
52 static struct tcg_temp_info temps
[TCG_MAX_TEMPS
];
54 /* Reset TEMP's state to TCG_TEMP_UNDEF. If TEMP was a representative of some
55 class of equivalent temp's, a new representative should be chosen in this
57 static void reset_temp(TCGArg temp
, int nb_temps
, int nb_globals
)
60 TCGArg new_base
= (TCGArg
)-1;
61 if (temps
[temp
].state
== TCG_TEMP_HAS_COPY
) {
62 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
63 if (i
>= nb_globals
) {
64 temps
[i
].state
= TCG_TEMP_HAS_COPY
;
69 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
70 if (new_base
== (TCGArg
)-1) {
71 temps
[i
].state
= TCG_TEMP_UNDEF
;
73 temps
[i
].val
= new_base
;
76 temps
[temps
[temp
].next_copy
].prev_copy
= temps
[temp
].prev_copy
;
77 temps
[temps
[temp
].prev_copy
].next_copy
= temps
[temp
].next_copy
;
78 } else if (temps
[temp
].state
== TCG_TEMP_COPY
) {
79 temps
[temps
[temp
].next_copy
].prev_copy
= temps
[temp
].prev_copy
;
80 temps
[temps
[temp
].prev_copy
].next_copy
= temps
[temp
].next_copy
;
81 new_base
= temps
[temp
].val
;
83 temps
[temp
].state
= TCG_TEMP_UNDEF
;
84 if (new_base
!= (TCGArg
)-1 && temps
[new_base
].next_copy
== new_base
) {
85 temps
[new_base
].state
= TCG_TEMP_UNDEF
;
89 static int op_bits(TCGOpcode op
)
91 const TCGOpDef
*def
= &tcg_op_defs
[op
];
92 return def
->flags
& TCG_OPF_64BIT
? 64 : 32;
95 static TCGOpcode
op_to_movi(TCGOpcode op
)
97 switch (op_bits(op
)) {
99 return INDEX_op_movi_i32
;
101 return INDEX_op_movi_i64
;
103 fprintf(stderr
, "op_to_movi: unexpected return value of "
104 "function op_bits.\n");
109 static void tcg_opt_gen_mov(TCGContext
*s
, TCGArg
*gen_args
,
110 TCGArg dst
, TCGArg src
)
112 reset_temp(dst
, s
->nb_temps
, s
->nb_globals
);
113 assert(temps
[src
].state
!= TCG_TEMP_COPY
);
114 /* Only consider temps with the same type (width) as copies. */
115 if (src
>= s
->nb_globals
&& s
->temps
[dst
].type
== s
->temps
[src
].type
) {
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
;
339 /* Array VALS has an element for each temp.
340 If this temp holds a constant then its value is kept in VALS' element.
341 If this temp is a copy of other ones then this equivalence class'
342 representative is kept in VALS' element.
343 If this temp is neither copy nor constant then corresponding VALS'
344 element is unused. */
346 nb_temps
= s
->nb_temps
;
347 nb_globals
= s
->nb_globals
;
348 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
350 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
352 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
353 op
= gen_opc_buf
[op_index
];
354 def
= &tcg_op_defs
[op
];
355 /* Do copy propagation */
356 if (!(def
->flags
& (TCG_OPF_CALL_CLOBBER
| TCG_OPF_SIDE_EFFECTS
))) {
357 assert(op
!= INDEX_op_call
);
358 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
359 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
360 args
[i
] = temps
[args
[i
]].val
;
365 /* For commutative operations make constant second argument */
375 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
381 CASE_OP_32_64(brcond
):
382 if (temps
[args
[0]].state
== TCG_TEMP_CONST
383 && temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
387 args
[2] = tcg_swap_cond(args
[2]);
390 CASE_OP_32_64(setcond
):
391 if (temps
[args
[1]].state
== TCG_TEMP_CONST
392 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
396 args
[3] = tcg_swap_cond(args
[3]);
399 CASE_OP_32_64(movcond
):
401 if (temps
[args
[1]].state
== TCG_TEMP_CONST
402 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
406 cond
= tcg_swap_cond(cond
);
408 /* For movcond, we canonicalize the "false" input reg to match
409 the destination reg so that the tcg backend can implement
410 a "move if true" operation. */
411 if (args
[0] == args
[3]) {
415 cond
= tcg_invert_cond(cond
);
422 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
429 if (temps
[args
[1]].state
== TCG_TEMP_CONST
430 && temps
[args
[1]].val
== 0) {
431 gen_opc_buf
[op_index
] = op_to_movi(op
);
432 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
442 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
453 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
454 /* Proceed with possible constant folding. */
457 if (temps
[args
[2]].state
== TCG_TEMP_CONST
458 && temps
[args
[2]].val
== 0) {
459 if ((temps
[args
[0]].state
== TCG_TEMP_COPY
460 && temps
[args
[0]].val
== args
[1])
461 || args
[0] == args
[1]) {
462 gen_opc_buf
[op_index
] = INDEX_op_nop
;
464 gen_opc_buf
[op_index
] = op_to_mov(op
);
465 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
476 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
480 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
481 && temps
[args
[2]].val
== 0)) {
482 gen_opc_buf
[op_index
] = op_to_movi(op
);
483 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
493 /* Simplify expression for "op r, a, a => mov r, a" cases */
497 if (args
[1] == args
[2]) {
498 if (args
[1] == args
[0]) {
499 gen_opc_buf
[op_index
] = INDEX_op_nop
;
501 gen_opc_buf
[op_index
] = op_to_mov(op
);
502 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
513 /* Propagate constants through copy operations and do constant
514 folding. Constants will be substituted to arguments by register
515 allocator where needed and possible. Also detect copies. */
518 if ((temps
[args
[1]].state
== TCG_TEMP_COPY
519 && temps
[args
[1]].val
== args
[0])
520 || args
[0] == args
[1]) {
522 gen_opc_buf
[op_index
] = INDEX_op_nop
;
525 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
526 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
531 /* Source argument is constant. Rewrite the operation and
532 let movi case handle it. */
534 gen_opc_buf
[op_index
] = op
;
535 args
[1] = temps
[args
[1]].val
;
538 tcg_opt_gen_movi(gen_args
, args
[0], args
[1], nb_temps
, nb_globals
);
544 CASE_OP_32_64(ext8s
):
545 CASE_OP_32_64(ext8u
):
546 CASE_OP_32_64(ext16s
):
547 CASE_OP_32_64(ext16u
):
548 case INDEX_op_ext32s_i64
:
549 case INDEX_op_ext32u_i64
:
550 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
551 gen_opc_buf
[op_index
] = op_to_movi(op
);
552 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
553 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
555 reset_temp(args
[0], nb_temps
, nb_globals
);
556 gen_args
[0] = args
[0];
557 gen_args
[1] = args
[1];
578 if (temps
[args
[1]].state
== TCG_TEMP_CONST
579 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
580 gen_opc_buf
[op_index
] = op_to_movi(op
);
581 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
583 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
586 reset_temp(args
[0], nb_temps
, nb_globals
);
587 gen_args
[0] = args
[0];
588 gen_args
[1] = args
[1];
589 gen_args
[2] = args
[2];
594 CASE_OP_32_64(setcond
):
595 if (temps
[args
[1]].state
== TCG_TEMP_CONST
596 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
597 gen_opc_buf
[op_index
] = op_to_movi(op
);
598 tmp
= do_constant_folding_cond(op
, temps
[args
[1]].val
,
599 temps
[args
[2]].val
, args
[3]);
600 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
603 reset_temp(args
[0], nb_temps
, nb_globals
);
604 gen_args
[0] = args
[0];
605 gen_args
[1] = args
[1];
606 gen_args
[2] = args
[2];
607 gen_args
[3] = args
[3];
612 CASE_OP_32_64(brcond
):
613 if (temps
[args
[0]].state
== TCG_TEMP_CONST
614 && temps
[args
[1]].state
== TCG_TEMP_CONST
) {
615 if (do_constant_folding_cond(op
, temps
[args
[0]].val
,
616 temps
[args
[1]].val
, args
[2])) {
617 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
618 gen_opc_buf
[op_index
] = INDEX_op_br
;
619 gen_args
[0] = args
[3];
622 gen_opc_buf
[op_index
] = INDEX_op_nop
;
625 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
626 reset_temp(args
[0], nb_temps
, nb_globals
);
627 gen_args
[0] = args
[0];
628 gen_args
[1] = args
[1];
629 gen_args
[2] = args
[2];
630 gen_args
[3] = args
[3];
635 CASE_OP_32_64(movcond
):
636 if (temps
[args
[1]].state
== TCG_TEMP_CONST
637 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
638 tmp
= do_constant_folding_cond(op
, temps
[args
[1]].val
,
639 temps
[args
[2]].val
, args
[5]);
640 if (args
[0] == args
[4-tmp
]
641 || (temps
[args
[4-tmp
]].state
== TCG_TEMP_COPY
642 && temps
[args
[4-tmp
]].val
== args
[0])) {
643 gen_opc_buf
[op_index
] = INDEX_op_nop
;
644 } else if (temps
[args
[4-tmp
]].state
== TCG_TEMP_CONST
) {
645 gen_opc_buf
[op_index
] = op_to_movi(op
);
646 tcg_opt_gen_movi(gen_args
, args
[0], temps
[args
[4-tmp
]].val
,
647 nb_temps
, nb_globals
);
650 gen_opc_buf
[op_index
] = op_to_mov(op
);
651 tcg_opt_gen_mov(gen_args
, args
[0], args
[4-tmp
],
652 nb_temps
, nb_globals
);
656 reset_temp(args
[0], nb_temps
, nb_globals
);
657 gen_args
[0] = args
[0];
658 gen_args
[1] = args
[1];
659 gen_args
[2] = args
[2];
660 gen_args
[3] = args
[3];
661 gen_args
[4] = args
[4];
662 gen_args
[5] = args
[5];
668 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
669 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
670 for (i
= 0; i
< nb_globals
; i
++) {
671 reset_temp(i
, nb_temps
, nb_globals
);
674 for (i
= 0; i
< (args
[0] >> 16); i
++) {
675 reset_temp(args
[i
+ 1], nb_temps
, nb_globals
);
677 i
= nb_call_args
+ 3;
686 /* Default case: we do know nothing about operation so no
687 propagation is done. We trash everything if the operation
688 is the end of a basic block, otherwise we only trash the
690 if (def
->flags
& TCG_OPF_BB_END
) {
691 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
693 for (i
= 0; i
< def
->nb_oargs
; i
++) {
694 reset_temp(args
[i
], nb_temps
, nb_globals
);
697 for (i
= 0; i
< def
->nb_args
; i
++) {
698 gen_args
[i
] = args
[i
];
700 args
+= def
->nb_args
;
701 gen_args
+= def
->nb_args
;
709 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
710 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
713 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);