[qemu.git] / tcg / optimize.c

/*
 * Optimizations for Tiny Code Generator for QEMU
 *
 * Copyright (c) 2010 Samsung Electronics.
 * Contributed by Kirill Batuzov <batuzovk@ispras.ru>
 *
 * Permission is hereby granted, free of charge, to any person obtaining a copy
 * of this software and associated documentation files (the "Software"), to deal
 * in the Software without restriction, including without limitation the rights
 * to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
 * copies of the Software, and to permit persons to whom the Software is
 * furnished to do so, subject to the following conditions:
 *
 * The above copyright notice and this permission notice shall be included in
 * all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
 * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
 * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
 * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
 * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
 * THE SOFTWARE.
 */

#include "config.h"

#include <stdlib.h>
#include <stdio.h>

#include "qemu-common.h"
#include "tcg-op.h"

#define CASE_OP_32_64(x)                        \
        glue(glue(case INDEX_op_, x), _i32):    \
        glue(glue(case INDEX_op_, x), _i64)

typedef enum {
    TCG_TEMP_UNDEF = 0,
    TCG_TEMP_CONST,
    TCG_TEMP_COPY,
    TCG_TEMP_HAS_COPY,
    TCG_TEMP_ANY
} tcg_temp_state;

struct tcg_temp_info {
    tcg_temp_state state;
    uint16_t prev_copy;
    uint16_t next_copy;
    tcg_target_ulong val;
};

static struct tcg_temp_info temps[TCG_MAX_TEMPS];

/* Reset TEMP's state to TCG_TEMP_ANY.  If TEMP was a representative of some
   class of equivalent temp's, a new representative should be chosen in this
   class. */
static void reset_temp(TCGArg temp, int nb_temps, int nb_globals)
{
    int i;
    TCGArg new_base = (TCGArg)-1;
    if (temps[temp].state == TCG_TEMP_HAS_COPY) {
        for (i = temps[temp].next_copy; i != temp; i = temps[i].next_copy) {
            if (i >= nb_globals) {
                temps[i].state = TCG_TEMP_HAS_COPY;
                new_base = i;
                break;
            }
        }
        for (i = temps[temp].next_copy; i != temp; i = temps[i].next_copy) {
            if (new_base == (TCGArg)-1) {
                temps[i].state = TCG_TEMP_ANY;
            } else {
                temps[i].val = new_base;
            }
        }
        temps[temps[temp].next_copy].prev_copy = temps[temp].prev_copy;
        temps[temps[temp].prev_copy].next_copy = temps[temp].next_copy;
    } else if (temps[temp].state == TCG_TEMP_COPY) {
        temps[temps[temp].next_copy].prev_copy = temps[temp].prev_copy;
        temps[temps[temp].prev_copy].next_copy = temps[temp].next_copy;
        new_base = temps[temp].val;
    }
    temps[temp].state = TCG_TEMP_ANY;
    if (new_base != (TCGArg)-1 && temps[new_base].next_copy == new_base) {
        temps[new_base].state = TCG_TEMP_ANY;
    }
}

static int op_bits(TCGOpcode op)
{
    const TCGOpDef *def = &tcg_op_defs[op];
    return def->flags & TCG_OPF_64BIT ? 64 : 32;
}

static TCGOpcode op_to_movi(TCGOpcode op)
{
    switch (op_bits(op)) {
    case 32:
        return INDEX_op_movi_i32;
    case 64:
        return INDEX_op_movi_i64;
    default:
        fprintf(stderr, "op_to_movi: unexpected return value of "
                "function op_bits.\n");
        tcg_abort();
    }
}

static void tcg_opt_gen_mov(TCGContext *s, TCGArg *gen_args, TCGArg dst,
                            TCGArg src, int nb_temps, int nb_globals)
{
        reset_temp(dst, nb_temps, nb_globals);
        assert(temps[src].state != TCG_TEMP_COPY);
        /* Don't try to copy if one of temps is a global or either one
           is local and another is register */
        if (src >= nb_globals && dst >= nb_globals &&
            tcg_arg_is_local(s, src) == tcg_arg_is_local(s, dst)) {
            assert(temps[src].state != TCG_TEMP_CONST);
            if (temps[src].state != TCG_TEMP_HAS_COPY) {
                temps[src].state = TCG_TEMP_HAS_COPY;
                temps[src].next_copy = src;
                temps[src].prev_copy = src;
            }
            temps[dst].state = TCG_TEMP_COPY;
            temps[dst].val = src;
            temps[dst].next_copy = temps[src].next_copy;
            temps[dst].prev_copy = src;
            temps[temps[dst].next_copy].prev_copy = dst;
            temps[src].next_copy = dst;
        }
        gen_args[0] = dst;
        gen_args[1] = src;
}

static void tcg_opt_gen_movi(TCGArg *gen_args, TCGArg dst, TCGArg val,
                             int nb_temps, int nb_globals)
{
        reset_temp(dst, nb_temps, nb_globals);
        temps[dst].state = TCG_TEMP_CONST;
        temps[dst].val = val;
        gen_args[0] = dst;
        gen_args[1] = val;
}

static TCGOpcode op_to_mov(TCGOpcode op)
{
    switch (op_bits(op)) {
    case 32:
        return INDEX_op_mov_i32;
    case 64:
        return INDEX_op_mov_i64;
    default:
        fprintf(stderr, "op_to_mov: unexpected return value of "
                "function op_bits.\n");
        tcg_abort();
    }
}

static TCGArg do_constant_folding_2(TCGOpcode op, TCGArg x, TCGArg y)
{
    switch (op) {
    CASE_OP_32_64(add):
        return x + y;

    CASE_OP_32_64(sub):
        return x - y;

    CASE_OP_32_64(mul):
        return x * y;

    CASE_OP_32_64(and):
        return x & y;

    CASE_OP_32_64(or):
        return x | y;

    CASE_OP_32_64(xor):
        return x ^ y;

    case INDEX_op_shl_i32:
        return (uint32_t)x << (uint32_t)y;

    case INDEX_op_shl_i64:
        return (uint64_t)x << (uint64_t)y;

    case INDEX_op_shr_i32:
        return (uint32_t)x >> (uint32_t)y;

    case INDEX_op_shr_i64:
        return (uint64_t)x >> (uint64_t)y;

    case INDEX_op_sar_i32:
        return (int32_t)x >> (int32_t)y;

    case INDEX_op_sar_i64:
        return (int64_t)x >> (int64_t)y;

    case INDEX_op_rotr_i32:
        x = ((uint32_t)x << (32 - y)) | ((uint32_t)x >> y);
        return x;

    case INDEX_op_rotr_i64:
        x = ((uint64_t)x << (64 - y)) | ((uint64_t)x >> y);
        return x;

    case INDEX_op_rotl_i32:
        x = ((uint32_t)x << y) | ((uint32_t)x >> (32 - y));
        return x;

    case INDEX_op_rotl_i64:
        x = ((uint64_t)x << y) | ((uint64_t)x >> (64 - y));
        return x;

    CASE_OP_32_64(not):
        return ~x;

    CASE_OP_32_64(neg):
        return -x;

    CASE_OP_32_64(andc):
        return x & ~y;

    CASE_OP_32_64(orc):
        return x | ~y;

    CASE_OP_32_64(eqv):
        return ~(x ^ y);

    CASE_OP_32_64(nand):
        return ~(x & y);

    CASE_OP_32_64(nor):
        return ~(x | y);

    CASE_OP_32_64(ext8s):
        return (int8_t)x;

    CASE_OP_32_64(ext16s):
        return (int16_t)x;

    CASE_OP_32_64(ext8u):
        return (uint8_t)x;

    CASE_OP_32_64(ext16u):
        return (uint16_t)x;

    case INDEX_op_ext32s_i64:
        return (int32_t)x;

    case INDEX_op_ext32u_i64:
        return (uint32_t)x;

    default:
        fprintf(stderr,
                "Unrecognized operation %d in do_constant_folding.\n", op);
        tcg_abort();
    }
}

static TCGArg do_constant_folding(TCGOpcode op, TCGArg x, TCGArg y)
{
    TCGArg res = do_constant_folding_2(op, x, y);
    if (op_bits(op) == 32) {
        res &= 0xffffffff;
    }
    return res;
}

/* Propagate constants and copies, fold constant expressions. */
static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr,
                                    TCGArg *args, TCGOpDef *tcg_op_defs)
{
    int i, nb_ops, op_index, nb_temps, nb_globals, nb_call_args;
    TCGOpcode op;
    const TCGOpDef *def;
    TCGArg *gen_args;
    TCGArg tmp;
    /* Array VALS has an element for each temp.
       If this temp holds a constant then its value is kept in VALS' element.
       If this temp is a copy of other ones then this equivalence class'
       representative is kept in VALS' element.
       If this temp is neither copy nor constant then corresponding VALS'
       element is unused. */

    nb_temps = s->nb_temps;
    nb_globals = s->nb_globals;
    memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));

    nb_ops = tcg_opc_ptr - gen_opc_buf;
    gen_args = args;
    for (op_index = 0; op_index < nb_ops; op_index++) {
        op = gen_opc_buf[op_index];
        def = &tcg_op_defs[op];
        /* Do copy propagation */
        if (!(def->flags & (TCG_OPF_CALL_CLOBBER | TCG_OPF_SIDE_EFFECTS))) {
            assert(op != INDEX_op_call);
            for (i = def->nb_oargs; i < def->nb_oargs + def->nb_iargs; i++) {
                if (temps[args[i]].state == TCG_TEMP_COPY) {
                    args[i] = temps[args[i]].val;
                }
            }
        }

        /* For commutative operations make constant second argument */
        switch (op) {
        CASE_OP_32_64(add):
        CASE_OP_32_64(mul):
        CASE_OP_32_64(and):
        CASE_OP_32_64(or):
        CASE_OP_32_64(xor):
        CASE_OP_32_64(eqv):
        CASE_OP_32_64(nand):
        CASE_OP_32_64(nor):
            if (temps[args[1]].state == TCG_TEMP_CONST) {
                tmp = args[1];
                args[1] = args[2];
                args[2] = tmp;
            }
            break;
        default:
            break;
        }

        /* Simplify expression if possible. */
        switch (op) {
        CASE_OP_32_64(add):
        CASE_OP_32_64(sub):
        CASE_OP_32_64(shl):
        CASE_OP_32_64(shr):
        CASE_OP_32_64(sar):
        CASE_OP_32_64(rotl):
        CASE_OP_32_64(rotr):
            if (temps[args[1]].state == TCG_TEMP_CONST) {
                /* Proceed with possible constant folding. */
                break;
            }
            if (temps[args[2]].state == TCG_TEMP_CONST
                && temps[args[2]].val == 0) {
                if ((temps[args[0]].state == TCG_TEMP_COPY
                    && temps[args[0]].val == args[1])
                    || args[0] == args[1]) {
                    args += 3;
                    gen_opc_buf[op_index] = INDEX_op_nop;
                } else {
                    gen_opc_buf[op_index] = op_to_mov(op);
                    tcg_opt_gen_mov(s, gen_args, args[0], args[1],
                                    nb_temps, nb_globals);
                    gen_args += 2;
                    args += 3;
                }
                continue;
            }
            break;
        CASE_OP_32_64(mul):
            if ((temps[args[2]].state == TCG_TEMP_CONST
                && temps[args[2]].val == 0)) {
                gen_opc_buf[op_index] = op_to_movi(op);
                tcg_opt_gen_movi(gen_args, args[0], 0, nb_temps, nb_globals);
                args += 3;
                gen_args += 2;
                continue;
            }
            break;
        CASE_OP_32_64(or):
        CASE_OP_32_64(and):
            if (args[1] == args[2]) {
                if (args[1] == args[0]) {
                    args += 3;
                    gen_opc_buf[op_index] = INDEX_op_nop;
                } else {
                    gen_opc_buf[op_index] = op_to_mov(op);
                    tcg_opt_gen_mov(s, gen_args, args[0], args[1], nb_temps,
                                    nb_globals);
                    gen_args += 2;
                    args += 3;
                }
                continue;
            }
            break;
        default:
            break;
        }

        /* Propagate constants through copy operations and do constant
           folding.  Constants will be substituted to arguments by register
           allocator where needed and possible.  Also detect copies. */
        switch (op) {
        CASE_OP_32_64(mov):
            if ((temps[args[1]].state == TCG_TEMP_COPY
                && temps[args[1]].val == args[0])
                || args[0] == args[1]) {
                args += 2;
                gen_opc_buf[op_index] = INDEX_op_nop;
                break;
            }
            if (temps[args[1]].state != TCG_TEMP_CONST) {
                tcg_opt_gen_mov(s, gen_args, args[0], args[1],
                                nb_temps, nb_globals);
                gen_args += 2;
                args += 2;
                break;
            }
            /* Source argument is constant.  Rewrite the operation and
               let movi case handle it. */
            op = op_to_movi(op);
            gen_opc_buf[op_index] = op;
            args[1] = temps[args[1]].val;
            /* fallthrough */
        CASE_OP_32_64(movi):
            tcg_opt_gen_movi(gen_args, args[0], args[1], nb_temps, nb_globals);
            gen_args += 2;
            args += 2;
            break;
        CASE_OP_32_64(not):
        CASE_OP_32_64(neg):
        CASE_OP_32_64(ext8s):
        CASE_OP_32_64(ext8u):
        CASE_OP_32_64(ext16s):
        CASE_OP_32_64(ext16u):
        case INDEX_op_ext32s_i64:
        case INDEX_op_ext32u_i64:
            if (temps[args[1]].state == TCG_TEMP_CONST) {
                gen_opc_buf[op_index] = op_to_movi(op);
                tmp = do_constant_folding(op, temps[args[1]].val, 0);
                tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
                gen_args += 2;
                args += 2;
                break;
            } else {
                reset_temp(args[0], nb_temps, nb_globals);
                gen_args[0] = args[0];
                gen_args[1] = args[1];
                gen_args += 2;
                args += 2;
                break;
            }
        CASE_OP_32_64(add):
        CASE_OP_32_64(sub):
        CASE_OP_32_64(mul):
        CASE_OP_32_64(or):
        CASE_OP_32_64(and):
        CASE_OP_32_64(xor):
        CASE_OP_32_64(shl):
        CASE_OP_32_64(shr):
        CASE_OP_32_64(sar):
        CASE_OP_32_64(rotl):
        CASE_OP_32_64(rotr):
        CASE_OP_32_64(andc):
        CASE_OP_32_64(orc):
        CASE_OP_32_64(eqv):
        CASE_OP_32_64(nand):
        CASE_OP_32_64(nor):
            if (temps[args[1]].state == TCG_TEMP_CONST
                && temps[args[2]].state == TCG_TEMP_CONST) {
                gen_opc_buf[op_index] = op_to_movi(op);
                tmp = do_constant_folding(op, temps[args[1]].val,
                                          temps[args[2]].val);
                tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
                gen_args += 2;
                args += 3;
                break;
            } else {
                reset_temp(args[0], nb_temps, nb_globals);
                gen_args[0] = args[0];
                gen_args[1] = args[1];
                gen_args[2] = args[2];
                gen_args += 3;
                args += 3;
                break;
            }
        case INDEX_op_call:
            nb_call_args = (args[0] >> 16) + (args[0] & 0xffff);
            if (!(args[nb_call_args + 1] & (TCG_CALL_CONST | TCG_CALL_PURE))) {
                for (i = 0; i < nb_globals; i++) {
                    reset_temp(i, nb_temps, nb_globals);
                }
            }
            for (i = 0; i < (args[0] >> 16); i++) {
                reset_temp(args[i + 1], nb_temps, nb_globals);
            }
            i = nb_call_args + 3;
            while (i) {
                *gen_args = *args;
                args++;
                gen_args++;
                i--;
            }
            break;
        case INDEX_op_set_label:
        case INDEX_op_jmp:
        case INDEX_op_br:
        CASE_OP_32_64(brcond):
            memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
            for (i = 0; i < def->nb_args; i++) {
                *gen_args = *args;
                args++;
                gen_args++;
            }
            break;
        default:
            /* Default case: we do know nothing about operation so no
               propagation is done.  We only trash output args.  */
            for (i = 0; i < def->nb_oargs; i++) {
                reset_temp(args[i], nb_temps, nb_globals);
            }
            for (i = 0; i < def->nb_args; i++) {
                gen_args[i] = args[i];
            }
            args += def->nb_args;
            gen_args += def->nb_args;
            break;
        }
    }

    return gen_args;
}

TCGArg *tcg_optimize(TCGContext *s, uint16_t *tcg_opc_ptr,
        TCGArg *args, TCGOpDef *tcg_op_defs)
{
    TCGArg *res;
    res = tcg_constant_folding(s, tcg_opc_ptr, args, tcg_op_defs);
    return res;
}
Commit	Line	Data
8f2e8c07 KB	1	/*
	2	* Optimizations for Tiny Code Generator for QEMU
	3	*
	4	* Copyright (c) 2010 Samsung Electronics.
	5	* Contributed by Kirill Batuzov <batuzovk@ispras.ru>
	6	*
	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:
	13	*
	14	* The above copyright notice and this permission notice shall be included in
	15	* all copies or substantial portions of the Software.
	16	*
	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
	23	* THE SOFTWARE.
	24	*/
	25
	26	#include "config.h"
	27
	28	#include <stdlib.h>
	29	#include <stdio.h>
	30
	31	#include "qemu-common.h"
	32	#include "tcg-op.h"
	33
8f2e8c07 KB	34	#define CASE_OP_32_64(x) \
	35	glue(glue(case INDEX_op_, x), _i32): \
	36	glue(glue(case INDEX_op_, x), _i64)
8f2e8c07	37
22613af4 KB	38	typedef enum {
	39	TCG_TEMP_UNDEF = 0,
	40	TCG_TEMP_CONST,
	41	TCG_TEMP_COPY,
	42	TCG_TEMP_HAS_COPY,
	43	TCG_TEMP_ANY
	44	} tcg_temp_state;
	45
	46	struct tcg_temp_info {
	47	tcg_temp_state state;
	48	uint16_t prev_copy;
	49	uint16_t next_copy;
	50	tcg_target_ulong val;
	51	};
	52
	53	static struct tcg_temp_info temps[TCG_MAX_TEMPS];
	54
	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
	57	class. */
	58	static void reset_temp(TCGArg temp, int nb_temps, int nb_globals)
	59	{
	60	int i;
	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;
	66	new_base = i;
	67	break;
	68	}
	69	}
	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;
	73	} else {
	74	temps[i].val = new_base;
	75	}
	76	}
	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;
	83	}
	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;
	87	}
	88	}
	89
fe0de7aa	90	static int op_bits(TCGOpcode op)
22613af4	91	{
8399ad59 RH	92	const TCGOpDef *def = &tcg_op_defs[op];
8399ad59 RH	93	return def->flags & TCG_OPF_64BIT ? 64 : 32;
22613af4 KB	94	}
22613af4 KB	95
fe0de7aa	96	static TCGOpcode op_to_movi(TCGOpcode op)
22613af4 KB	97	{
	98	switch (op_bits(op)) {
	99	case 32:
	100	return INDEX_op_movi_i32;
22613af4 KB	101	case 64:
22613af4 KB	102	return INDEX_op_movi_i64;
22613af4 KB	103	default:
	104	fprintf(stderr, "op_to_movi: unexpected return value of "
	105	"function op_bits.\n");
	106	tcg_abort();
	107	}
	108	}
	109
e31b0a7c BS	110	static void tcg_opt_gen_mov(TCGContext s, TCGArg gen_args, TCGArg dst,
e31b0a7c BS	111	TCGArg src, int nb_temps, int nb_globals)
22613af4 KB	112	{
	113	reset_temp(dst, nb_temps, nb_globals);
	114	assert(temps[src].state != TCG_TEMP_COPY);
e31b0a7c BS	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)) {
22613af4 KB	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;
	124	}
	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;
	131	}
	132	gen_args[0] = dst;
	133	gen_args[1] = src;
	134	}
	135
	136	static void tcg_opt_gen_movi(TCGArg *gen_args, TCGArg dst, TCGArg val,
	137	int nb_temps, int nb_globals)
	138	{
	139	reset_temp(dst, nb_temps, nb_globals);
	140	temps[dst].state = TCG_TEMP_CONST;
	141	temps[dst].val = val;
	142	gen_args[0] = dst;
	143	gen_args[1] = val;
	144	}
	145
fe0de7aa	146	static TCGOpcode op_to_mov(TCGOpcode op)
53108fb5 KB	147	{
	148	switch (op_bits(op)) {
	149	case 32:
	150	return INDEX_op_mov_i32;
53108fb5 KB	151	case 64:
53108fb5 KB	152	return INDEX_op_mov_i64;
53108fb5 KB	153	default:
	154	fprintf(stderr, "op_to_mov: unexpected return value of "
	155	"function op_bits.\n");
	156	tcg_abort();
	157	}
	158	}
	159
fe0de7aa	160	static TCGArg do_constant_folding_2(TCGOpcode op, TCGArg x, TCGArg y)
53108fb5 KB	161	{
	162	switch (op) {
	163	CASE_OP_32_64(add):
	164	return x + y;
	165
	166	CASE_OP_32_64(sub):
	167	return x - y;
	168
	169	CASE_OP_32_64(mul):
	170	return x * y;
	171
9a81090b KB	172	CASE_OP_32_64(and):
	173	return x & y;
	174
	175	CASE_OP_32_64(or):
	176	return x \| y;
	177
	178	CASE_OP_32_64(xor):
	179	return x ^ y;
	180
55c0975c KB	181	case INDEX_op_shl_i32:
	182	return (uint32_t)x << (uint32_t)y;
	183
55c0975c KB	184	case INDEX_op_shl_i64:
55c0975c KB	185	return (uint64_t)x << (uint64_t)y;
55c0975c KB	186
	187	case INDEX_op_shr_i32:
	188	return (uint32_t)x >> (uint32_t)y;
	189
55c0975c KB	190	case INDEX_op_shr_i64:
55c0975c KB	191	return (uint64_t)x >> (uint64_t)y;
55c0975c KB	192
	193	case INDEX_op_sar_i32:
	194	return (int32_t)x >> (int32_t)y;
	195
55c0975c KB	196	case INDEX_op_sar_i64:
55c0975c KB	197	return (int64_t)x >> (int64_t)y;
55c0975c KB	198
55c0975c KB	199	case INDEX_op_rotr_i32:
25c4d9cc	200	x = ((uint32_t)x << (32 - y)) \| ((uint32_t)x >> y);
55c0975c KB	201	return x;
55c0975c KB	202
55c0975c	203	case INDEX_op_rotr_i64:
25c4d9cc	204	x = ((uint64_t)x << (64 - y)) \| ((uint64_t)x >> y);
55c0975c	205	return x;
55c0975c KB	206
55c0975c KB	207	case INDEX_op_rotl_i32:
25c4d9cc	208	x = ((uint32_t)x << y) \| ((uint32_t)x >> (32 - y));
55c0975c KB	209	return x;
55c0975c KB	210
55c0975c	211	case INDEX_op_rotl_i64:
25c4d9cc	212	x = ((uint64_t)x << y) \| ((uint64_t)x >> (64 - y));
55c0975c	213	return x;
25c4d9cc RH	214
25c4d9cc RH	215	CASE_OP_32_64(not):
a640f031	216	return ~x;
25c4d9cc	217
cb25c80a RH	218	CASE_OP_32_64(neg):
	219	return -x;
	220
	221	CASE_OP_32_64(andc):
	222	return x & ~y;
	223
	224	CASE_OP_32_64(orc):
	225	return x \| ~y;
	226
	227	CASE_OP_32_64(eqv):
	228	return ~(x ^ y);
	229
	230	CASE_OP_32_64(nand):
	231	return ~(x & y);
	232
	233	CASE_OP_32_64(nor):
	234	return ~(x \| y);
	235
25c4d9cc	236	CASE_OP_32_64(ext8s):
a640f031	237	return (int8_t)x;
25c4d9cc RH	238
25c4d9cc RH	239	CASE_OP_32_64(ext16s):
a640f031	240	return (int16_t)x;
25c4d9cc RH	241
25c4d9cc RH	242	CASE_OP_32_64(ext8u):
a640f031	243	return (uint8_t)x;
25c4d9cc RH	244
25c4d9cc RH	245	CASE_OP_32_64(ext16u):
a640f031 KB	246	return (uint16_t)x;
a640f031 KB	247
a640f031 KB	248	case INDEX_op_ext32s_i64:
	249	return (int32_t)x;
	250
	251	case INDEX_op_ext32u_i64:
	252	return (uint32_t)x;
a640f031	253
53108fb5 KB	254	default:
	255	fprintf(stderr,
	256	"Unrecognized operation %d in do_constant_folding.\n", op);
	257	tcg_abort();
	258	}
	259	}
	260
fe0de7aa	261	static TCGArg do_constant_folding(TCGOpcode op, TCGArg x, TCGArg y)
53108fb5 KB	262	{
53108fb5 KB	263	TCGArg res = do_constant_folding_2(op, x, y);
53108fb5 KB	264	if (op_bits(op) == 32) {
	265	res &= 0xffffffff;
	266	}
53108fb5 KB	267	return res;
	268	}
	269
22613af4	270	/* Propagate constants and copies, fold constant expressions. */
8f2e8c07 KB	271	static TCGArg tcg_constant_folding(TCGContext s, uint16_t *tcg_opc_ptr,
	272	TCGArg args, TCGOpDef tcg_op_defs)
	273	{
fe0de7aa BS	274	int i, nb_ops, op_index, nb_temps, nb_globals, nb_call_args;
fe0de7aa BS	275	TCGOpcode op;
8f2e8c07 KB	276	const TCGOpDef *def;
8f2e8c07 KB	277	TCGArg *gen_args;
53108fb5	278	TCGArg tmp;
22613af4 KB	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. */
8f2e8c07 KB	285
	286	nb_temps = s->nb_temps;
	287	nb_globals = s->nb_globals;
22613af4	288	memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
8f2e8c07 KB	289
	290	nb_ops = tcg_opc_ptr - gen_opc_buf;
	291	gen_args = args;
	292	for (op_index = 0; op_index < nb_ops; op_index++) {
	293	op = gen_opc_buf[op_index];
	294	def = &tcg_op_defs[op];
22613af4 KB	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;
	301	}
	302	}
	303	}
	304
53108fb5 KB	305	/* For commutative operations make constant second argument */
	306	switch (op) {
	307	CASE_OP_32_64(add):
	308	CASE_OP_32_64(mul):
9a81090b KB	309	CASE_OP_32_64(and):
	310	CASE_OP_32_64(or):
	311	CASE_OP_32_64(xor):
cb25c80a RH	312	CASE_OP_32_64(eqv):
	313	CASE_OP_32_64(nand):
	314	CASE_OP_32_64(nor):
53108fb5 KB	315	if (temps[args[1]].state == TCG_TEMP_CONST) {
	316	tmp = args[1];
	317	args[1] = args[2];
	318	args[2] = tmp;
	319	}
	320	break;
	321	default:
	322	break;
	323	}
	324
	325	/* Simplify expression if possible. */
	326	switch (op) {
	327	CASE_OP_32_64(add):
	328	CASE_OP_32_64(sub):
55c0975c KB	329	CASE_OP_32_64(shl):
	330	CASE_OP_32_64(shr):
	331	CASE_OP_32_64(sar):
25c4d9cc RH	332	CASE_OP_32_64(rotl):
25c4d9cc RH	333	CASE_OP_32_64(rotr):
53108fb5 KB	334	if (temps[args[1]].state == TCG_TEMP_CONST) {
	335	/* Proceed with possible constant folding. */
	336	break;
	337	}
	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]) {
	343	args += 3;
	344	gen_opc_buf[op_index] = INDEX_op_nop;
	345	} else {
	346	gen_opc_buf[op_index] = op_to_mov(op);
e31b0a7c	347	tcg_opt_gen_mov(s, gen_args, args[0], args[1],
53108fb5 KB	348	nb_temps, nb_globals);
	349	gen_args += 2;
	350	args += 3;
	351	}
	352	continue;
	353	}
	354	break;
	355	CASE_OP_32_64(mul):
	356	if ((temps[args[2]].state == TCG_TEMP_CONST
	357	&& temps[args[2]].val == 0)) {
	358	gen_opc_buf[op_index] = op_to_movi(op);
	359	tcg_opt_gen_movi(gen_args, args[0], 0, nb_temps, nb_globals);
	360	args += 3;
	361	gen_args += 2;
	362	continue;
	363	}
	364	break;
9a81090b KB	365	CASE_OP_32_64(or):
	366	CASE_OP_32_64(and):
	367	if (args[1] == args[2]) {
	368	if (args[1] == args[0]) {
	369	args += 3;
	370	gen_opc_buf[op_index] = INDEX_op_nop;
	371	} else {
	372	gen_opc_buf[op_index] = op_to_mov(op);
e31b0a7c	373	tcg_opt_gen_mov(s, gen_args, args[0], args[1], nb_temps,
9a81090b KB	374	nb_globals);
	375	gen_args += 2;
	376	args += 3;
	377	}
	378	continue;
	379	}
	380	break;
fe0de7aa BS	381	default:
fe0de7aa BS	382	break;
53108fb5 KB	383	}
53108fb5 KB	384
22613af4 KB	385	/* Propagate constants through copy operations and do constant
	386	folding. Constants will be substituted to arguments by register
	387	allocator where needed and possible. Also detect copies. */
8f2e8c07	388	switch (op) {
22613af4 KB	389	CASE_OP_32_64(mov):
	390	if ((temps[args[1]].state == TCG_TEMP_COPY
	391	&& temps[args[1]].val == args[0])
	392	\|\| args[0] == args[1]) {
	393	args += 2;
	394	gen_opc_buf[op_index] = INDEX_op_nop;
	395	break;
	396	}
	397	if (temps[args[1]].state != TCG_TEMP_CONST) {
e31b0a7c	398	tcg_opt_gen_mov(s, gen_args, args[0], args[1],
22613af4 KB	399	nb_temps, nb_globals);
	400	gen_args += 2;
	401	args += 2;
	402	break;
	403	}
	404	/* Source argument is constant. Rewrite the operation and
	405	let movi case handle it. */
	406	op = op_to_movi(op);
	407	gen_opc_buf[op_index] = op;
	408	args[1] = temps[args[1]].val;
	409	/* fallthrough */
	410	CASE_OP_32_64(movi):
	411	tcg_opt_gen_movi(gen_args, args[0], args[1], nb_temps, nb_globals);
	412	gen_args += 2;
	413	args += 2;
	414	break;
a640f031	415	CASE_OP_32_64(not):
cb25c80a	416	CASE_OP_32_64(neg):
25c4d9cc RH	417	CASE_OP_32_64(ext8s):
	418	CASE_OP_32_64(ext8u):
	419	CASE_OP_32_64(ext16s):
	420	CASE_OP_32_64(ext16u):
a640f031 KB	421	case INDEX_op_ext32s_i64:
a640f031 KB	422	case INDEX_op_ext32u_i64:
a640f031 KB	423	if (temps[args[1]].state == TCG_TEMP_CONST) {
	424	gen_opc_buf[op_index] = op_to_movi(op);
	425	tmp = do_constant_folding(op, temps[args[1]].val, 0);
	426	tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
	427	gen_args += 2;
	428	args += 2;
	429	break;
	430	} else {
	431	reset_temp(args[0], nb_temps, nb_globals);
	432	gen_args[0] = args[0];
	433	gen_args[1] = args[1];
	434	gen_args += 2;
	435	args += 2;
	436	break;
	437	}
53108fb5 KB	438	CASE_OP_32_64(add):
	439	CASE_OP_32_64(sub):
	440	CASE_OP_32_64(mul):
9a81090b KB	441	CASE_OP_32_64(or):
	442	CASE_OP_32_64(and):
	443	CASE_OP_32_64(xor):
55c0975c KB	444	CASE_OP_32_64(shl):
	445	CASE_OP_32_64(shr):
	446	CASE_OP_32_64(sar):
25c4d9cc RH	447	CASE_OP_32_64(rotl):
25c4d9cc RH	448	CASE_OP_32_64(rotr):
cb25c80a RH	449	CASE_OP_32_64(andc):
	450	CASE_OP_32_64(orc):
	451	CASE_OP_32_64(eqv):
	452	CASE_OP_32_64(nand):
	453	CASE_OP_32_64(nor):
53108fb5 KB	454	if (temps[args[1]].state == TCG_TEMP_CONST
	455	&& temps[args[2]].state == TCG_TEMP_CONST) {
	456	gen_opc_buf[op_index] = op_to_movi(op);
	457	tmp = do_constant_folding(op, temps[args[1]].val,
	458	temps[args[2]].val);
	459	tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
	460	gen_args += 2;
	461	args += 3;
	462	break;
	463	} else {
	464	reset_temp(args[0], nb_temps, nb_globals);
	465	gen_args[0] = args[0];
	466	gen_args[1] = args[1];
	467	gen_args[2] = args[2];
	468	gen_args += 3;
	469	args += 3;
	470	break;
	471	}
8f2e8c07	472	case INDEX_op_call:
22613af4 KB	473	nb_call_args = (args[0] >> 16) + (args[0] & 0xffff);
	474	if (!(args[nb_call_args + 1] & (TCG_CALL_CONST \| TCG_CALL_PURE))) {
	475	for (i = 0; i < nb_globals; i++) {
	476	reset_temp(i, nb_temps, nb_globals);
	477	}
	478	}
	479	for (i = 0; i < (args[0] >> 16); i++) {
	480	reset_temp(args[i + 1], nb_temps, nb_globals);
	481	}
	482	i = nb_call_args + 3;
8f2e8c07 KB	483	while (i) {
	484	gen_args = args;
	485	args++;
	486	gen_args++;
	487	i--;
	488	}
	489	break;
	490	case INDEX_op_set_label:
	491	case INDEX_op_jmp:
	492	case INDEX_op_br:
	493	CASE_OP_32_64(brcond):
22613af4	494	memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
8f2e8c07 KB	495	for (i = 0; i < def->nb_args; i++) {
	496	gen_args = args;
	497	args++;
	498	gen_args++;
	499	}
	500	break;
	501	default:
22613af4 KB	502	/* Default case: we do know nothing about operation so no
	503	propagation is done. We only trash output args. */
	504	for (i = 0; i < def->nb_oargs; i++) {
	505	reset_temp(args[i], nb_temps, nb_globals);
	506	}
8f2e8c07 KB	507	for (i = 0; i < def->nb_args; i++) {
	508	gen_args[i] = args[i];
	509	}
	510	args += def->nb_args;
	511	gen_args += def->nb_args;
	512	break;
	513	}
	514	}
	515
	516	return gen_args;
	517	}
	518
	519	TCGArg tcg_optimize(TCGContext s, uint16_t *tcg_opc_ptr,
	520	TCGArg args, TCGOpDef tcg_op_defs)
	521	{
	522	TCGArg *res;
	523	res = tcg_constant_folding(s, tcg_opc_ptr, args, tcg_op_defs);
	524	return res;
	525	}