]>
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(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 /* Propagate constants and copies, fold constant expressions. */
271 static TCGArg
*tcg_constant_folding(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
272 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
274 int i
, nb_ops
, op_index
, nb_temps
, nb_globals
, nb_call_args
;
279 /* Array VALS has an element for each temp.
280 If this temp holds a constant then its value is kept in VALS' element.
281 If this temp is a copy of other ones then this equivalence class'
282 representative is kept in VALS' element.
283 If this temp is neither copy nor constant then corresponding VALS'
284 element is unused. */
286 nb_temps
= s
->nb_temps
;
287 nb_globals
= s
->nb_globals
;
288 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
290 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
292 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
293 op
= gen_opc_buf
[op_index
];
294 def
= &tcg_op_defs
[op
];
295 /* Do copy propagation */
296 if (!(def
->flags
& (TCG_OPF_CALL_CLOBBER
| TCG_OPF_SIDE_EFFECTS
))) {
297 assert(op
!= INDEX_op_call
);
298 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
299 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
300 args
[i
] = temps
[args
[i
]].val
;
305 /* For commutative operations make constant second argument */
315 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
325 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
332 if (temps
[args
[1]].state
== TCG_TEMP_CONST
333 && temps
[args
[1]].val
== 0) {
334 gen_opc_buf
[op_index
] = op_to_movi(op
);
335 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
345 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
356 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
357 /* Proceed with possible constant folding. */
360 if (temps
[args
[2]].state
== TCG_TEMP_CONST
361 && temps
[args
[2]].val
== 0) {
362 if ((temps
[args
[0]].state
== TCG_TEMP_COPY
363 && temps
[args
[0]].val
== args
[1])
364 || args
[0] == args
[1]) {
366 gen_opc_buf
[op_index
] = INDEX_op_nop
;
368 gen_opc_buf
[op_index
] = op_to_mov(op
);
369 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
370 nb_temps
, nb_globals
);
381 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
385 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
386 && temps
[args
[2]].val
== 0)) {
387 gen_opc_buf
[op_index
] = op_to_movi(op
);
388 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
398 /* Simplify expression for "op r, a, a => mov r, a" cases */
402 if (args
[1] == args
[2]) {
403 if (args
[1] == args
[0]) {
405 gen_opc_buf
[op_index
] = INDEX_op_nop
;
407 gen_opc_buf
[op_index
] = op_to_mov(op
);
408 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1], nb_temps
,
420 /* Propagate constants through copy operations and do constant
421 folding. Constants will be substituted to arguments by register
422 allocator where needed and possible. Also detect copies. */
425 if ((temps
[args
[1]].state
== TCG_TEMP_COPY
426 && temps
[args
[1]].val
== args
[0])
427 || args
[0] == args
[1]) {
429 gen_opc_buf
[op_index
] = INDEX_op_nop
;
432 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
433 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
434 nb_temps
, nb_globals
);
439 /* Source argument is constant. Rewrite the operation and
440 let movi case handle it. */
442 gen_opc_buf
[op_index
] = op
;
443 args
[1] = temps
[args
[1]].val
;
446 tcg_opt_gen_movi(gen_args
, args
[0], args
[1], nb_temps
, nb_globals
);
452 CASE_OP_32_64(ext8s
):
453 CASE_OP_32_64(ext8u
):
454 CASE_OP_32_64(ext16s
):
455 CASE_OP_32_64(ext16u
):
456 case INDEX_op_ext32s_i64
:
457 case INDEX_op_ext32u_i64
:
458 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
459 gen_opc_buf
[op_index
] = op_to_movi(op
);
460 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
461 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
466 reset_temp(args
[0], nb_temps
, nb_globals
);
467 gen_args
[0] = args
[0];
468 gen_args
[1] = args
[1];
489 if (temps
[args
[1]].state
== TCG_TEMP_CONST
490 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
491 gen_opc_buf
[op_index
] = op_to_movi(op
);
492 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
494 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
499 reset_temp(args
[0], nb_temps
, nb_globals
);
500 gen_args
[0] = args
[0];
501 gen_args
[1] = args
[1];
502 gen_args
[2] = args
[2];
508 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
509 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
510 for (i
= 0; i
< nb_globals
; i
++) {
511 reset_temp(i
, nb_temps
, nb_globals
);
514 for (i
= 0; i
< (args
[0] >> 16); i
++) {
515 reset_temp(args
[i
+ 1], nb_temps
, nb_globals
);
517 i
= nb_call_args
+ 3;
525 case INDEX_op_set_label
:
528 CASE_OP_32_64(brcond
):
529 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
530 for (i
= 0; i
< def
->nb_args
; i
++) {
537 /* Default case: we do know nothing about operation so no
538 propagation is done. We only trash output args. */
539 for (i
= 0; i
< def
->nb_oargs
; i
++) {
540 reset_temp(args
[i
], nb_temps
, nb_globals
);
542 for (i
= 0; i
< def
->nb_args
; i
++) {
543 gen_args
[i
] = args
[i
];
545 args
+= def
->nb_args
;
546 gen_args
+= def
->nb_args
;
554 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
555 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
558 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);