]>
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)
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(TCGContext
*s
, TCGArg
*gen_args
, TCGArg dst
,
111 TCGArg src
, int nb_temps
, int nb_globals
)
113 reset_temp(dst
, nb_temps
, nb_globals
);
114 assert(temps
[src
].state
!= TCG_TEMP_COPY
);
115 /* Don't try to copy if one of temps is a global or either one
116 is local and another is register */
117 if (src
>= nb_globals
&& dst
>= nb_globals
&&
118 tcg_arg_is_local(s
, src
) == tcg_arg_is_local(s
, dst
)) {
119 assert(temps
[src
].state
!= TCG_TEMP_CONST
);
120 if (temps
[src
].state
!= TCG_TEMP_HAS_COPY
) {
121 temps
[src
].state
= TCG_TEMP_HAS_COPY
;
122 temps
[src
].next_copy
= src
;
123 temps
[src
].prev_copy
= src
;
125 temps
[dst
].state
= TCG_TEMP_COPY
;
126 temps
[dst
].val
= src
;
127 temps
[dst
].next_copy
= temps
[src
].next_copy
;
128 temps
[dst
].prev_copy
= src
;
129 temps
[temps
[dst
].next_copy
].prev_copy
= dst
;
130 temps
[src
].next_copy
= dst
;
136 static void tcg_opt_gen_movi(TCGArg
*gen_args
, TCGArg dst
, TCGArg val
,
137 int nb_temps
, int nb_globals
)
139 reset_temp(dst
, nb_temps
, nb_globals
);
140 temps
[dst
].state
= TCG_TEMP_CONST
;
141 temps
[dst
].val
= val
;
146 static TCGOpcode
op_to_mov(TCGOpcode op
)
148 switch (op_bits(op
)) {
150 return INDEX_op_mov_i32
;
152 return INDEX_op_mov_i64
;
154 fprintf(stderr
, "op_to_mov: unexpected return value of "
155 "function op_bits.\n");
160 static TCGArg
do_constant_folding_2(TCGOpcode op
, TCGArg x
, TCGArg y
)
181 case INDEX_op_shl_i32
:
182 return (uint32_t)x
<< (uint32_t)y
;
184 case INDEX_op_shl_i64
:
185 return (uint64_t)x
<< (uint64_t)y
;
187 case INDEX_op_shr_i32
:
188 return (uint32_t)x
>> (uint32_t)y
;
190 case INDEX_op_shr_i64
:
191 return (uint64_t)x
>> (uint64_t)y
;
193 case INDEX_op_sar_i32
:
194 return (int32_t)x
>> (int32_t)y
;
196 case INDEX_op_sar_i64
:
197 return (int64_t)x
>> (int64_t)y
;
199 case INDEX_op_rotr_i32
:
200 x
= ((uint32_t)x
<< (32 - y
)) | ((uint32_t)x
>> y
);
203 case INDEX_op_rotr_i64
:
204 x
= ((uint64_t)x
<< (64 - y
)) | ((uint64_t)x
>> y
);
207 case INDEX_op_rotl_i32
:
208 x
= ((uint32_t)x
<< y
) | ((uint32_t)x
>> (32 - y
));
211 case INDEX_op_rotl_i64
:
212 x
= ((uint64_t)x
<< y
) | ((uint64_t)x
>> (64 - y
));
236 CASE_OP_32_64(ext8s
):
239 CASE_OP_32_64(ext16s
):
242 CASE_OP_32_64(ext8u
):
245 CASE_OP_32_64(ext16u
):
248 case INDEX_op_ext32s_i64
:
251 case INDEX_op_ext32u_i64
:
256 "Unrecognized operation %d in do_constant_folding.\n", op
);
261 static TCGArg
do_constant_folding(TCGOpcode op
, TCGArg x
, TCGArg y
)
263 TCGArg res
= do_constant_folding_2(op
, x
, y
);
264 if (op_bits(op
) == 32) {
270 static TCGArg
do_constant_folding_cond(TCGOpcode op
, TCGArg x
,
273 switch (op_bits(op
)) {
277 return (uint32_t)x
== (uint32_t)y
;
279 return (uint32_t)x
!= (uint32_t)y
;
281 return (int32_t)x
< (int32_t)y
;
283 return (int32_t)x
>= (int32_t)y
;
285 return (int32_t)x
<= (int32_t)y
;
287 return (int32_t)x
> (int32_t)y
;
289 return (uint32_t)x
< (uint32_t)y
;
291 return (uint32_t)x
>= (uint32_t)y
;
293 return (uint32_t)x
<= (uint32_t)y
;
295 return (uint32_t)x
> (uint32_t)y
;
301 return (uint64_t)x
== (uint64_t)y
;
303 return (uint64_t)x
!= (uint64_t)y
;
305 return (int64_t)x
< (int64_t)y
;
307 return (int64_t)x
>= (int64_t)y
;
309 return (int64_t)x
<= (int64_t)y
;
311 return (int64_t)x
> (int64_t)y
;
313 return (uint64_t)x
< (uint64_t)y
;
315 return (uint64_t)x
>= (uint64_t)y
;
317 return (uint64_t)x
<= (uint64_t)y
;
319 return (uint64_t)x
> (uint64_t)y
;
325 "Unrecognized bitness %d or condition %d in "
326 "do_constant_folding_cond.\n", op_bits(op
), c
);
331 /* Propagate constants and copies, fold constant expressions. */
332 static TCGArg
*tcg_constant_folding(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
333 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
335 int i
, nb_ops
, op_index
, nb_temps
, nb_globals
, nb_call_args
;
340 /* Array VALS has an element for each temp.
341 If this temp holds a constant then its value is kept in VALS' element.
342 If this temp is a copy of other ones then this equivalence class'
343 representative is kept in VALS' element.
344 If this temp is neither copy nor constant then corresponding VALS'
345 element is unused. */
347 nb_temps
= s
->nb_temps
;
348 nb_globals
= s
->nb_globals
;
349 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
351 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
353 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
354 op
= gen_opc_buf
[op_index
];
355 def
= &tcg_op_defs
[op
];
356 /* Do copy propagation */
357 if (!(def
->flags
& (TCG_OPF_CALL_CLOBBER
| TCG_OPF_SIDE_EFFECTS
))) {
358 assert(op
!= INDEX_op_call
);
359 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
360 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
361 args
[i
] = temps
[args
[i
]].val
;
366 /* For commutative operations make constant second argument */
376 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
382 CASE_OP_32_64(brcond
):
383 if (temps
[args
[0]].state
== TCG_TEMP_CONST
384 && temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
388 args
[2] = tcg_swap_cond(args
[2]);
391 CASE_OP_32_64(setcond
):
392 if (temps
[args
[1]].state
== TCG_TEMP_CONST
393 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
397 args
[3] = tcg_swap_cond(args
[3]);
404 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
411 if (temps
[args
[1]].state
== TCG_TEMP_CONST
412 && temps
[args
[1]].val
== 0) {
413 gen_opc_buf
[op_index
] = op_to_movi(op
);
414 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
424 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
435 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
436 /* Proceed with possible constant folding. */
439 if (temps
[args
[2]].state
== TCG_TEMP_CONST
440 && temps
[args
[2]].val
== 0) {
441 if ((temps
[args
[0]].state
== TCG_TEMP_COPY
442 && temps
[args
[0]].val
== args
[1])
443 || args
[0] == args
[1]) {
444 gen_opc_buf
[op_index
] = INDEX_op_nop
;
446 gen_opc_buf
[op_index
] = op_to_mov(op
);
447 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
448 nb_temps
, nb_globals
);
459 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
463 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
464 && temps
[args
[2]].val
== 0)) {
465 gen_opc_buf
[op_index
] = op_to_movi(op
);
466 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
476 /* Simplify expression for "op r, a, a => mov r, a" cases */
480 if (args
[1] == args
[2]) {
481 if (args
[1] == args
[0]) {
482 gen_opc_buf
[op_index
] = INDEX_op_nop
;
484 gen_opc_buf
[op_index
] = op_to_mov(op
);
485 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1], nb_temps
,
497 /* Propagate constants through copy operations and do constant
498 folding. Constants will be substituted to arguments by register
499 allocator where needed and possible. Also detect copies. */
502 if ((temps
[args
[1]].state
== TCG_TEMP_COPY
503 && temps
[args
[1]].val
== args
[0])
504 || args
[0] == args
[1]) {
506 gen_opc_buf
[op_index
] = INDEX_op_nop
;
509 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
510 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
511 nb_temps
, nb_globals
);
516 /* Source argument is constant. Rewrite the operation and
517 let movi case handle it. */
519 gen_opc_buf
[op_index
] = op
;
520 args
[1] = temps
[args
[1]].val
;
523 tcg_opt_gen_movi(gen_args
, args
[0], args
[1], nb_temps
, nb_globals
);
529 CASE_OP_32_64(ext8s
):
530 CASE_OP_32_64(ext8u
):
531 CASE_OP_32_64(ext16s
):
532 CASE_OP_32_64(ext16u
):
533 case INDEX_op_ext32s_i64
:
534 case INDEX_op_ext32u_i64
:
535 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
536 gen_opc_buf
[op_index
] = op_to_movi(op
);
537 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
538 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
540 reset_temp(args
[0], nb_temps
, nb_globals
);
541 gen_args
[0] = args
[0];
542 gen_args
[1] = args
[1];
563 if (temps
[args
[1]].state
== TCG_TEMP_CONST
564 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
565 gen_opc_buf
[op_index
] = op_to_movi(op
);
566 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
568 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
571 reset_temp(args
[0], nb_temps
, nb_globals
);
572 gen_args
[0] = args
[0];
573 gen_args
[1] = args
[1];
574 gen_args
[2] = args
[2];
579 CASE_OP_32_64(setcond
):
580 if (temps
[args
[1]].state
== TCG_TEMP_CONST
581 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
582 gen_opc_buf
[op_index
] = op_to_movi(op
);
583 tmp
= do_constant_folding_cond(op
, temps
[args
[1]].val
,
584 temps
[args
[2]].val
, args
[3]);
585 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
588 reset_temp(args
[0], nb_temps
, nb_globals
);
589 gen_args
[0] = args
[0];
590 gen_args
[1] = args
[1];
591 gen_args
[2] = args
[2];
592 gen_args
[3] = args
[3];
597 CASE_OP_32_64(brcond
):
598 if (temps
[args
[0]].state
== TCG_TEMP_CONST
599 && temps
[args
[1]].state
== TCG_TEMP_CONST
) {
600 if (do_constant_folding_cond(op
, temps
[args
[0]].val
,
601 temps
[args
[1]].val
, args
[2])) {
602 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
603 gen_opc_buf
[op_index
] = INDEX_op_br
;
604 gen_args
[0] = args
[3];
607 gen_opc_buf
[op_index
] = INDEX_op_nop
;
610 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
611 reset_temp(args
[0], nb_temps
, nb_globals
);
612 gen_args
[0] = args
[0];
613 gen_args
[1] = args
[1];
614 gen_args
[2] = args
[2];
615 gen_args
[3] = args
[3];
621 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
622 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
623 for (i
= 0; i
< nb_globals
; i
++) {
624 reset_temp(i
, nb_temps
, nb_globals
);
627 for (i
= 0; i
< (args
[0] >> 16); i
++) {
628 reset_temp(args
[i
+ 1], nb_temps
, nb_globals
);
630 i
= nb_call_args
+ 3;
638 case INDEX_op_set_label
:
641 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
642 for (i
= 0; i
< def
->nb_args
; i
++) {
649 /* Default case: we do know nothing about operation so no
650 propagation is done. We only trash output args. */
651 for (i
= 0; i
< def
->nb_oargs
; i
++) {
652 reset_temp(args
[i
], nb_temps
, nb_globals
);
654 for (i
= 0; i
< def
->nb_args
; i
++) {
655 gen_args
[i
] = args
[i
];
657 args
+= def
->nb_args
;
658 gen_args
+= def
->nb_args
;
666 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
667 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
670 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);