]>
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 /* 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 expression for "op r, a, 0 => mov r, a" cases */
334 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
335 /* Proceed with possible constant folding. */
338 if (temps
[args
[2]].state
== TCG_TEMP_CONST
339 && temps
[args
[2]].val
== 0) {
340 if ((temps
[args
[0]].state
== TCG_TEMP_COPY
341 && temps
[args
[0]].val
== args
[1])
342 || args
[0] == args
[1]) {
344 gen_opc_buf
[op_index
] = INDEX_op_nop
;
346 gen_opc_buf
[op_index
] = op_to_mov(op
);
347 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
348 nb_temps
, nb_globals
);
359 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
362 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
363 && temps
[args
[2]].val
== 0)) {
364 gen_opc_buf
[op_index
] = op_to_movi(op
);
365 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
375 /* Simplify expression for "op r, a, a => mov r, a" cases */
379 if (args
[1] == args
[2]) {
380 if (args
[1] == args
[0]) {
382 gen_opc_buf
[op_index
] = INDEX_op_nop
;
384 gen_opc_buf
[op_index
] = op_to_mov(op
);
385 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1], nb_temps
,
397 /* Propagate constants through copy operations and do constant
398 folding. Constants will be substituted to arguments by register
399 allocator where needed and possible. Also detect copies. */
402 if ((temps
[args
[1]].state
== TCG_TEMP_COPY
403 && temps
[args
[1]].val
== args
[0])
404 || args
[0] == args
[1]) {
406 gen_opc_buf
[op_index
] = INDEX_op_nop
;
409 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
410 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
411 nb_temps
, nb_globals
);
416 /* Source argument is constant. Rewrite the operation and
417 let movi case handle it. */
419 gen_opc_buf
[op_index
] = op
;
420 args
[1] = temps
[args
[1]].val
;
423 tcg_opt_gen_movi(gen_args
, args
[0], args
[1], nb_temps
, nb_globals
);
429 CASE_OP_32_64(ext8s
):
430 CASE_OP_32_64(ext8u
):
431 CASE_OP_32_64(ext16s
):
432 CASE_OP_32_64(ext16u
):
433 case INDEX_op_ext32s_i64
:
434 case INDEX_op_ext32u_i64
:
435 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
436 gen_opc_buf
[op_index
] = op_to_movi(op
);
437 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
438 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
443 reset_temp(args
[0], nb_temps
, nb_globals
);
444 gen_args
[0] = args
[0];
445 gen_args
[1] = args
[1];
466 if (temps
[args
[1]].state
== TCG_TEMP_CONST
467 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
468 gen_opc_buf
[op_index
] = op_to_movi(op
);
469 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
471 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
476 reset_temp(args
[0], nb_temps
, nb_globals
);
477 gen_args
[0] = args
[0];
478 gen_args
[1] = args
[1];
479 gen_args
[2] = args
[2];
485 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
486 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
487 for (i
= 0; i
< nb_globals
; i
++) {
488 reset_temp(i
, nb_temps
, nb_globals
);
491 for (i
= 0; i
< (args
[0] >> 16); i
++) {
492 reset_temp(args
[i
+ 1], nb_temps
, nb_globals
);
494 i
= nb_call_args
+ 3;
502 case INDEX_op_set_label
:
505 CASE_OP_32_64(brcond
):
506 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
507 for (i
= 0; i
< def
->nb_args
; i
++) {
514 /* Default case: we do know nothing about operation so no
515 propagation is done. We only trash output args. */
516 for (i
= 0; i
< def
->nb_oargs
; i
++) {
517 reset_temp(args
[i
], nb_temps
, nb_globals
);
519 for (i
= 0; i
< def
->nb_args
; i
++) {
520 gen_args
[i
] = args
[i
];
522 args
+= def
->nb_args
;
523 gen_args
+= def
->nb_args
;
531 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
532 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
535 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);