]>
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 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]) {
445 gen_opc_buf
[op_index
] = INDEX_op_nop
;
447 gen_opc_buf
[op_index
] = op_to_mov(op
);
448 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
449 nb_temps
, nb_globals
);
460 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
464 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
465 && temps
[args
[2]].val
== 0)) {
466 gen_opc_buf
[op_index
] = op_to_movi(op
);
467 tcg_opt_gen_movi(gen_args
, args
[0], 0, nb_temps
, nb_globals
);
477 /* Simplify expression for "op r, a, a => mov r, a" cases */
481 if (args
[1] == args
[2]) {
482 if (args
[1] == args
[0]) {
484 gen_opc_buf
[op_index
] = INDEX_op_nop
;
486 gen_opc_buf
[op_index
] = op_to_mov(op
);
487 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1], nb_temps
,
499 /* Propagate constants through copy operations and do constant
500 folding. Constants will be substituted to arguments by register
501 allocator where needed and possible. Also detect copies. */
504 if ((temps
[args
[1]].state
== TCG_TEMP_COPY
505 && temps
[args
[1]].val
== args
[0])
506 || args
[0] == args
[1]) {
508 gen_opc_buf
[op_index
] = INDEX_op_nop
;
511 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
512 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1],
513 nb_temps
, nb_globals
);
518 /* Source argument is constant. Rewrite the operation and
519 let movi case handle it. */
521 gen_opc_buf
[op_index
] = op
;
522 args
[1] = temps
[args
[1]].val
;
525 tcg_opt_gen_movi(gen_args
, args
[0], args
[1], nb_temps
, nb_globals
);
531 CASE_OP_32_64(ext8s
):
532 CASE_OP_32_64(ext8u
):
533 CASE_OP_32_64(ext16s
):
534 CASE_OP_32_64(ext16u
):
535 case INDEX_op_ext32s_i64
:
536 case INDEX_op_ext32u_i64
:
537 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
538 gen_opc_buf
[op_index
] = op_to_movi(op
);
539 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
540 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
545 reset_temp(args
[0], nb_temps
, nb_globals
);
546 gen_args
[0] = args
[0];
547 gen_args
[1] = args
[1];
568 if (temps
[args
[1]].state
== TCG_TEMP_CONST
569 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
570 gen_opc_buf
[op_index
] = op_to_movi(op
);
571 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
573 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
578 reset_temp(args
[0], nb_temps
, nb_globals
);
579 gen_args
[0] = args
[0];
580 gen_args
[1] = args
[1];
581 gen_args
[2] = args
[2];
586 CASE_OP_32_64(setcond
):
587 if (temps
[args
[1]].state
== TCG_TEMP_CONST
588 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
589 gen_opc_buf
[op_index
] = op_to_movi(op
);
590 tmp
= do_constant_folding_cond(op
, temps
[args
[1]].val
,
591 temps
[args
[2]].val
, args
[3]);
592 tcg_opt_gen_movi(gen_args
, args
[0], tmp
, nb_temps
, nb_globals
);
597 reset_temp(args
[0], nb_temps
, nb_globals
);
598 gen_args
[0] = args
[0];
599 gen_args
[1] = args
[1];
600 gen_args
[2] = args
[2];
601 gen_args
[3] = args
[3];
607 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
608 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
609 for (i
= 0; i
< nb_globals
; i
++) {
610 reset_temp(i
, nb_temps
, nb_globals
);
613 for (i
= 0; i
< (args
[0] >> 16); i
++) {
614 reset_temp(args
[i
+ 1], nb_temps
, nb_globals
);
616 i
= nb_call_args
+ 3;
624 case INDEX_op_set_label
:
627 CASE_OP_32_64(brcond
):
628 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
629 for (i
= 0; i
< def
->nb_args
; i
++) {
636 /* Default case: we do know nothing about operation so no
637 propagation is done. We only trash output args. */
638 for (i
= 0; i
< def
->nb_oargs
; i
++) {
639 reset_temp(args
[i
], nb_temps
, nb_globals
);
641 for (i
= 0; i
< def
->nb_args
; i
++) {
642 gen_args
[i
] = args
[i
];
644 args
+= def
->nb_args
;
645 gen_args
+= def
->nb_args
;
653 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
654 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
657 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);