]>
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)
44 struct tcg_temp_info
{
51 static struct tcg_temp_info temps
[TCG_MAX_TEMPS
];
53 /* Reset TEMP's state to TCG_TEMP_UNDEF. If TEMP only had one copy, remove
54 the copy flag from the left temp. */
55 static void reset_temp(TCGArg temp
)
57 if (temps
[temp
].state
== TCG_TEMP_COPY
) {
58 if (temps
[temp
].prev_copy
== temps
[temp
].next_copy
) {
59 temps
[temps
[temp
].next_copy
].state
= TCG_TEMP_UNDEF
;
61 temps
[temps
[temp
].next_copy
].prev_copy
= temps
[temp
].prev_copy
;
62 temps
[temps
[temp
].prev_copy
].next_copy
= temps
[temp
].next_copy
;
65 temps
[temp
].state
= TCG_TEMP_UNDEF
;
68 static int op_bits(TCGOpcode op
)
70 const TCGOpDef
*def
= &tcg_op_defs
[op
];
71 return def
->flags
& TCG_OPF_64BIT
? 64 : 32;
74 static TCGOpcode
op_to_movi(TCGOpcode op
)
76 switch (op_bits(op
)) {
78 return INDEX_op_movi_i32
;
80 return INDEX_op_movi_i64
;
82 fprintf(stderr
, "op_to_movi: unexpected return value of "
83 "function op_bits.\n");
88 static TCGArg
find_better_copy(TCGContext
*s
, TCGArg temp
)
92 /* If this is already a global, we can't do better. */
93 if (temp
< s
->nb_globals
) {
97 /* Search for a global first. */
98 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
99 if (i
< s
->nb_globals
) {
104 /* If it is a temp, search for a temp local. */
105 if (!s
->temps
[temp
].temp_local
) {
106 for (i
= temps
[temp
].next_copy
; i
!= temp
; i
= temps
[i
].next_copy
) {
107 if (s
->temps
[i
].temp_local
) {
113 /* Failure to find a better representation, return the same temp. */
117 static bool temps_are_copies(TCGArg arg1
, TCGArg arg2
)
125 if (temps
[arg1
].state
!= TCG_TEMP_COPY
126 || temps
[arg2
].state
!= TCG_TEMP_COPY
) {
130 for (i
= temps
[arg1
].next_copy
; i
!= arg1
; i
= temps
[i
].next_copy
) {
139 static void tcg_opt_gen_mov(TCGContext
*s
, TCGArg
*gen_args
,
140 TCGArg dst
, TCGArg src
)
143 assert(temps
[src
].state
!= TCG_TEMP_CONST
);
145 if (s
->temps
[src
].type
== s
->temps
[dst
].type
) {
146 if (temps
[src
].state
!= TCG_TEMP_COPY
) {
147 temps
[src
].state
= TCG_TEMP_COPY
;
148 temps
[src
].next_copy
= src
;
149 temps
[src
].prev_copy
= src
;
151 temps
[dst
].state
= TCG_TEMP_COPY
;
152 temps
[dst
].next_copy
= temps
[src
].next_copy
;
153 temps
[dst
].prev_copy
= src
;
154 temps
[temps
[dst
].next_copy
].prev_copy
= dst
;
155 temps
[src
].next_copy
= dst
;
162 static void tcg_opt_gen_movi(TCGArg
*gen_args
, TCGArg dst
, TCGArg val
)
165 temps
[dst
].state
= TCG_TEMP_CONST
;
166 temps
[dst
].val
= val
;
171 static TCGOpcode
op_to_mov(TCGOpcode op
)
173 switch (op_bits(op
)) {
175 return INDEX_op_mov_i32
;
177 return INDEX_op_mov_i64
;
179 fprintf(stderr
, "op_to_mov: unexpected return value of "
180 "function op_bits.\n");
185 static TCGArg
do_constant_folding_2(TCGOpcode op
, TCGArg x
, TCGArg y
)
206 case INDEX_op_shl_i32
:
207 return (uint32_t)x
<< (uint32_t)y
;
209 case INDEX_op_shl_i64
:
210 return (uint64_t)x
<< (uint64_t)y
;
212 case INDEX_op_shr_i32
:
213 return (uint32_t)x
>> (uint32_t)y
;
215 case INDEX_op_shr_i64
:
216 return (uint64_t)x
>> (uint64_t)y
;
218 case INDEX_op_sar_i32
:
219 return (int32_t)x
>> (int32_t)y
;
221 case INDEX_op_sar_i64
:
222 return (int64_t)x
>> (int64_t)y
;
224 case INDEX_op_rotr_i32
:
225 x
= ((uint32_t)x
<< (32 - y
)) | ((uint32_t)x
>> y
);
228 case INDEX_op_rotr_i64
:
229 x
= ((uint64_t)x
<< (64 - y
)) | ((uint64_t)x
>> y
);
232 case INDEX_op_rotl_i32
:
233 x
= ((uint32_t)x
<< y
) | ((uint32_t)x
>> (32 - y
));
236 case INDEX_op_rotl_i64
:
237 x
= ((uint64_t)x
<< y
) | ((uint64_t)x
>> (64 - y
));
261 CASE_OP_32_64(ext8s
):
264 CASE_OP_32_64(ext16s
):
267 CASE_OP_32_64(ext8u
):
270 CASE_OP_32_64(ext16u
):
273 case INDEX_op_ext32s_i64
:
276 case INDEX_op_ext32u_i64
:
281 "Unrecognized operation %d in do_constant_folding.\n", op
);
286 static TCGArg
do_constant_folding(TCGOpcode op
, TCGArg x
, TCGArg y
)
288 TCGArg res
= do_constant_folding_2(op
, x
, y
);
289 if (op_bits(op
) == 32) {
295 static TCGArg
do_constant_folding_cond(TCGOpcode op
, TCGArg x
,
298 switch (op_bits(op
)) {
302 return (uint32_t)x
== (uint32_t)y
;
304 return (uint32_t)x
!= (uint32_t)y
;
306 return (int32_t)x
< (int32_t)y
;
308 return (int32_t)x
>= (int32_t)y
;
310 return (int32_t)x
<= (int32_t)y
;
312 return (int32_t)x
> (int32_t)y
;
314 return (uint32_t)x
< (uint32_t)y
;
316 return (uint32_t)x
>= (uint32_t)y
;
318 return (uint32_t)x
<= (uint32_t)y
;
320 return (uint32_t)x
> (uint32_t)y
;
326 return (uint64_t)x
== (uint64_t)y
;
328 return (uint64_t)x
!= (uint64_t)y
;
330 return (int64_t)x
< (int64_t)y
;
332 return (int64_t)x
>= (int64_t)y
;
334 return (int64_t)x
<= (int64_t)y
;
336 return (int64_t)x
> (int64_t)y
;
338 return (uint64_t)x
< (uint64_t)y
;
340 return (uint64_t)x
>= (uint64_t)y
;
342 return (uint64_t)x
<= (uint64_t)y
;
344 return (uint64_t)x
> (uint64_t)y
;
350 "Unrecognized bitness %d or condition %d in "
351 "do_constant_folding_cond.\n", op_bits(op
), c
);
355 /* Propagate constants and copies, fold constant expressions. */
356 static TCGArg
*tcg_constant_folding(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
357 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
359 int i
, nb_ops
, op_index
, nb_temps
, nb_globals
, nb_call_args
;
366 /* Array VALS has an element for each temp.
367 If this temp holds a constant then its value is kept in VALS' element.
368 If this temp is a copy of other ones then the other copies are
369 available through the doubly linked circular list. */
371 nb_temps
= s
->nb_temps
;
372 nb_globals
= s
->nb_globals
;
373 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
375 nb_ops
= tcg_opc_ptr
- gen_opc_buf
;
377 for (op_index
= 0; op_index
< nb_ops
; op_index
++) {
378 op
= gen_opc_buf
[op_index
];
379 def
= &tcg_op_defs
[op
];
380 /* Do copy propagation */
381 if (op
== INDEX_op_call
) {
382 int nb_oargs
= args
[0] >> 16;
383 int nb_iargs
= args
[0] & 0xffff;
384 for (i
= nb_oargs
+ 1; i
< nb_oargs
+ nb_iargs
+ 1; i
++) {
385 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
386 args
[i
] = find_better_copy(s
, args
[i
]);
390 for (i
= def
->nb_oargs
; i
< def
->nb_oargs
+ def
->nb_iargs
; i
++) {
391 if (temps
[args
[i
]].state
== TCG_TEMP_COPY
) {
392 args
[i
] = find_better_copy(s
, args
[i
]);
397 /* For commutative operations make constant second argument */
407 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
413 CASE_OP_32_64(brcond
):
414 if (temps
[args
[0]].state
== TCG_TEMP_CONST
415 && temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
419 args
[2] = tcg_swap_cond(args
[2]);
422 CASE_OP_32_64(setcond
):
423 if (temps
[args
[1]].state
== TCG_TEMP_CONST
424 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
428 args
[3] = tcg_swap_cond(args
[3]);
431 CASE_OP_32_64(movcond
):
433 if (temps
[args
[1]].state
== TCG_TEMP_CONST
434 && temps
[args
[2]].state
!= TCG_TEMP_CONST
) {
438 cond
= tcg_swap_cond(cond
);
440 /* For movcond, we canonicalize the "false" input reg to match
441 the destination reg so that the tcg backend can implement
442 a "move if true" operation. */
443 if (args
[0] == args
[3]) {
447 cond
= tcg_invert_cond(cond
);
454 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0" */
461 if (temps
[args
[1]].state
== TCG_TEMP_CONST
462 && temps
[args
[1]].val
== 0) {
463 gen_opc_buf
[op_index
] = op_to_movi(op
);
464 tcg_opt_gen_movi(gen_args
, args
[0], 0);
474 /* Simplify expression for "op r, a, 0 => mov r, a" cases */
485 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
486 /* Proceed with possible constant folding. */
489 if (temps
[args
[2]].state
== TCG_TEMP_CONST
490 && temps
[args
[2]].val
== 0) {
491 if (temps_are_copies(args
[0], args
[1])) {
492 gen_opc_buf
[op_index
] = INDEX_op_nop
;
494 gen_opc_buf
[op_index
] = op_to_mov(op
);
495 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
506 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */
510 if ((temps
[args
[2]].state
== TCG_TEMP_CONST
511 && temps
[args
[2]].val
== 0)) {
512 gen_opc_buf
[op_index
] = op_to_movi(op
);
513 tcg_opt_gen_movi(gen_args
, args
[0], 0);
523 /* Simplify expression for "op r, a, a => mov r, a" cases */
527 if (temps_are_copies(args
[1], args
[2])) {
528 if (temps_are_copies(args
[0], args
[1])) {
529 gen_opc_buf
[op_index
] = INDEX_op_nop
;
531 gen_opc_buf
[op_index
] = op_to_mov(op
);
532 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
543 /* Simplify expression for "op r, a, a => movi r, 0" cases */
547 if (temps_are_copies(args
[1], args
[2])) {
548 gen_opc_buf
[op_index
] = op_to_movi(op
);
549 tcg_opt_gen_movi(gen_args
, args
[0], 0);
559 /* Propagate constants through copy operations and do constant
560 folding. Constants will be substituted to arguments by register
561 allocator where needed and possible. Also detect copies. */
564 if (temps_are_copies(args
[0], args
[1])) {
566 gen_opc_buf
[op_index
] = INDEX_op_nop
;
569 if (temps
[args
[1]].state
!= TCG_TEMP_CONST
) {
570 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[1]);
575 /* Source argument is constant. Rewrite the operation and
576 let movi case handle it. */
578 gen_opc_buf
[op_index
] = op
;
579 args
[1] = temps
[args
[1]].val
;
582 tcg_opt_gen_movi(gen_args
, args
[0], args
[1]);
588 CASE_OP_32_64(ext8s
):
589 CASE_OP_32_64(ext8u
):
590 CASE_OP_32_64(ext16s
):
591 CASE_OP_32_64(ext16u
):
592 case INDEX_op_ext32s_i64
:
593 case INDEX_op_ext32u_i64
:
594 if (temps
[args
[1]].state
== TCG_TEMP_CONST
) {
595 gen_opc_buf
[op_index
] = op_to_movi(op
);
596 tmp
= do_constant_folding(op
, temps
[args
[1]].val
, 0);
597 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
600 gen_args
[0] = args
[0];
601 gen_args
[1] = args
[1];
622 if (temps
[args
[1]].state
== TCG_TEMP_CONST
623 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
624 gen_opc_buf
[op_index
] = op_to_movi(op
);
625 tmp
= do_constant_folding(op
, temps
[args
[1]].val
,
627 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
631 gen_args
[0] = args
[0];
632 gen_args
[1] = args
[1];
633 gen_args
[2] = args
[2];
638 CASE_OP_32_64(setcond
):
639 if (temps
[args
[1]].state
== TCG_TEMP_CONST
640 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
641 gen_opc_buf
[op_index
] = op_to_movi(op
);
642 tmp
= do_constant_folding_cond(op
, temps
[args
[1]].val
,
643 temps
[args
[2]].val
, args
[3]);
644 tcg_opt_gen_movi(gen_args
, args
[0], tmp
);
648 gen_args
[0] = args
[0];
649 gen_args
[1] = args
[1];
650 gen_args
[2] = args
[2];
651 gen_args
[3] = args
[3];
656 CASE_OP_32_64(brcond
):
657 if (temps
[args
[0]].state
== TCG_TEMP_CONST
658 && temps
[args
[1]].state
== TCG_TEMP_CONST
) {
659 if (do_constant_folding_cond(op
, temps
[args
[0]].val
,
660 temps
[args
[1]].val
, args
[2])) {
661 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
662 gen_opc_buf
[op_index
] = INDEX_op_br
;
663 gen_args
[0] = args
[3];
666 gen_opc_buf
[op_index
] = INDEX_op_nop
;
669 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
671 gen_args
[0] = args
[0];
672 gen_args
[1] = args
[1];
673 gen_args
[2] = args
[2];
674 gen_args
[3] = args
[3];
679 CASE_OP_32_64(movcond
):
680 if (temps
[args
[1]].state
== TCG_TEMP_CONST
681 && temps
[args
[2]].state
== TCG_TEMP_CONST
) {
682 tmp
= do_constant_folding_cond(op
, temps
[args
[1]].val
,
683 temps
[args
[2]].val
, args
[5]);
684 if (temps_are_copies(args
[0], args
[4-tmp
])) {
685 gen_opc_buf
[op_index
] = INDEX_op_nop
;
686 } else if (temps
[args
[4-tmp
]].state
== TCG_TEMP_CONST
) {
687 gen_opc_buf
[op_index
] = op_to_movi(op
);
688 tcg_opt_gen_movi(gen_args
, args
[0], temps
[args
[4-tmp
]].val
);
691 gen_opc_buf
[op_index
] = op_to_mov(op
);
692 tcg_opt_gen_mov(s
, gen_args
, args
[0], args
[4-tmp
]);
697 gen_args
[0] = args
[0];
698 gen_args
[1] = args
[1];
699 gen_args
[2] = args
[2];
700 gen_args
[3] = args
[3];
701 gen_args
[4] = args
[4];
702 gen_args
[5] = args
[5];
708 nb_call_args
= (args
[0] >> 16) + (args
[0] & 0xffff);
709 if (!(args
[nb_call_args
+ 1] & (TCG_CALL_CONST
| TCG_CALL_PURE
))) {
710 for (i
= 0; i
< nb_globals
; i
++) {
714 for (i
= 0; i
< (args
[0] >> 16); i
++) {
715 reset_temp(args
[i
+ 1]);
717 i
= nb_call_args
+ 3;
726 /* Default case: we do know nothing about operation so no
727 propagation is done. We trash everything if the operation
728 is the end of a basic block, otherwise we only trash the
730 if (def
->flags
& TCG_OPF_BB_END
) {
731 memset(temps
, 0, nb_temps
* sizeof(struct tcg_temp_info
));
733 for (i
= 0; i
< def
->nb_oargs
; i
++) {
737 for (i
= 0; i
< def
->nb_args
; i
++) {
738 gen_args
[i
] = args
[i
];
740 args
+= def
->nb_args
;
741 gen_args
+= def
->nb_args
;
749 TCGArg
*tcg_optimize(TCGContext
*s
, uint16_t *tcg_opc_ptr
,
750 TCGArg
*args
, TCGOpDef
*tcg_op_defs
)
753 res
= tcg_constant_folding(s
, tcg_opc_ptr
, args
, tcg_op_defs
);