[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"

#if TCG_TARGET_REG_BITS == 64
#define CASE_OP_32_64(x)                        \
        glue(glue(case INDEX_op_, x), _i32):    \
        glue(glue(case INDEX_op_, x), _i64)
#else
#define CASE_OP_32_64(x)                        \
        glue(glue(case INDEX_op_, x), _i32)
#endif

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(int op)
{
    switch (op) {
    case INDEX_op_mov_i32:
        return 32;
#if TCG_TARGET_REG_BITS == 64
    case INDEX_op_mov_i64:
        return 64;
#endif
    default:
        fprintf(stderr, "Unrecognized operation %d in op_bits.\n", op);
        tcg_abort();
    }
}

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

static void tcg_opt_gen_mov(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);
        if (src >= nb_globals) {
            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;
}

/* 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, op, nb_temps, nb_globals, nb_call_args;
    const TCGOpDef *def;
    TCGArg *gen_args;
    /* 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;
                }
            }
        }

        /* 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(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 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
	34	#if TCG_TARGET_REG_BITS == 64
	35	#define CASE_OP_32_64(x) \
	36	glue(glue(case INDEX_op_, x), _i32): \
	37	glue(glue(case INDEX_op_, x), _i64)
	38	#else
	39	#define CASE_OP_32_64(x) \
	40	glue(glue(case INDEX_op_, x), _i32)
	41	#endif
	42
22613af4 KB	43	typedef enum {
	44	TCG_TEMP_UNDEF = 0,
	45	TCG_TEMP_CONST,
	46	TCG_TEMP_COPY,
	47	TCG_TEMP_HAS_COPY,
	48	TCG_TEMP_ANY
	49	} tcg_temp_state;
	50
	51	struct tcg_temp_info {
	52	tcg_temp_state state;
	53	uint16_t prev_copy;
	54	uint16_t next_copy;
	55	tcg_target_ulong val;
	56	};
	57
	58	static struct tcg_temp_info temps[TCG_MAX_TEMPS];
	59
	60	/* Reset TEMP's state to TCG_TEMP_ANY. If TEMP was a representative of some
	61	class of equivalent temp's, a new representative should be chosen in this
	62	class. */
	63	static void reset_temp(TCGArg temp, int nb_temps, int nb_globals)
	64	{
	65	int i;
	66	TCGArg new_base = (TCGArg)-1;
	67	if (temps[temp].state == TCG_TEMP_HAS_COPY) {
	68	for (i = temps[temp].next_copy; i != temp; i = temps[i].next_copy) {
	69	if (i >= nb_globals) {
	70	temps[i].state = TCG_TEMP_HAS_COPY;
	71	new_base = i;
	72	break;
	73	}
	74	}
	75	for (i = temps[temp].next_copy; i != temp; i = temps[i].next_copy) {
	76	if (new_base == (TCGArg)-1) {
	77	temps[i].state = TCG_TEMP_ANY;
	78	} else {
	79	temps[i].val = new_base;
	80	}
	81	}
	82	temps[temps[temp].next_copy].prev_copy = temps[temp].prev_copy;
	83	temps[temps[temp].prev_copy].next_copy = temps[temp].next_copy;
	84	} else if (temps[temp].state == TCG_TEMP_COPY) {
	85	temps[temps[temp].next_copy].prev_copy = temps[temp].prev_copy;
	86	temps[temps[temp].prev_copy].next_copy = temps[temp].next_copy;
	87	new_base = temps[temp].val;
	88	}
	89	temps[temp].state = TCG_TEMP_ANY;
	90	if (new_base != (TCGArg)-1 && temps[new_base].next_copy == new_base) {
	91	temps[new_base].state = TCG_TEMP_ANY;
	92	}
	93	}
	94
	95	static int op_bits(int op)
	96	{
	97	switch (op) {
	98	case INDEX_op_mov_i32:
	99	return 32;
	100	#if TCG_TARGET_REG_BITS == 64
	101	case INDEX_op_mov_i64:
	102	return 64;
	103	#endif
	104	default:
	105	fprintf(stderr, "Unrecognized operation %d in op_bits.\n", op);
	106	tcg_abort();
107	}
108	}
109
110	static int op_to_movi(int op)
111	{
112	switch (op_bits(op)) {
113	case 32:
114	return INDEX_op_movi_i32;
115	#if TCG_TARGET_REG_BITS == 64
116	case 64:
117	return INDEX_op_movi_i64;
118	#endif
119	default:
120	fprintf(stderr, "op_to_movi: unexpected return value of "
121	"function op_bits.\n");
122	tcg_abort();
123	}
124	}
125
126	static void tcg_opt_gen_mov(TCGArg *gen_args, TCGArg dst, TCGArg src,
127	int nb_temps, int nb_globals)
128	{
129	reset_temp(dst, nb_temps, nb_globals);
130	assert(temps[src].state != TCG_TEMP_COPY);
131	if (src >= nb_globals) {
132	assert(temps[src].state != TCG_TEMP_CONST);
133	if (temps[src].state != TCG_TEMP_HAS_COPY) {
134	temps[src].state = TCG_TEMP_HAS_COPY;
135	temps[src].next_copy = src;
136	temps[src].prev_copy = src;
137	}
138	temps[dst].state = TCG_TEMP_COPY;
139	temps[dst].val = src;
140	temps[dst].next_copy = temps[src].next_copy;
141	temps[dst].prev_copy = src;
142	temps[temps[dst].next_copy].prev_copy = dst;
143	temps[src].next_copy = dst;
144	}
145	gen_args[0] = dst;
146	gen_args[1] = src;
147	}
148
149	static void tcg_opt_gen_movi(TCGArg *gen_args, TCGArg dst, TCGArg val,
150	int nb_temps, int nb_globals)
151	{
152	reset_temp(dst, nb_temps, nb_globals);
153	temps[dst].state = TCG_TEMP_CONST;
154	temps[dst].val = val;
155	gen_args[0] = dst;
156	gen_args[1] = val;
157	}
158
159	/* Propagate constants and copies, fold constant expressions. */
8f2e8c07 KB	160	static TCGArg tcg_constant_folding(TCGContext s, uint16_t *tcg_opc_ptr,
	161	TCGArg args, TCGOpDef tcg_op_defs)
	162	{
22613af4	163	int i, nb_ops, op_index, op, nb_temps, nb_globals, nb_call_args;
8f2e8c07 KB	164	const TCGOpDef *def;
8f2e8c07 KB	165	TCGArg *gen_args;
22613af4 KB	166	/* Array VALS has an element for each temp.
	167	If this temp holds a constant then its value is kept in VALS' element.
	168	If this temp is a copy of other ones then this equivalence class'
	169	representative is kept in VALS' element.
	170	If this temp is neither copy nor constant then corresponding VALS'
	171	element is unused. */
8f2e8c07 KB	172
	173	nb_temps = s->nb_temps;
	174	nb_globals = s->nb_globals;
22613af4	175	memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
8f2e8c07 KB	176
	177	nb_ops = tcg_opc_ptr - gen_opc_buf;
	178	gen_args = args;
	179	for (op_index = 0; op_index < nb_ops; op_index++) {
	180	op = gen_opc_buf[op_index];
	181	def = &tcg_op_defs[op];
22613af4 KB	182	/* Do copy propagation */
	183	if (!(def->flags & (TCG_OPF_CALL_CLOBBER \| TCG_OPF_SIDE_EFFECTS))) {
	184	assert(op != INDEX_op_call);
	185	for (i = def->nb_oargs; i < def->nb_oargs + def->nb_iargs; i++) {
	186	if (temps[args[i]].state == TCG_TEMP_COPY) {
	187	args[i] = temps[args[i]].val;
	188	}
	189	}
	190	}
	191
	192	/* Propagate constants through copy operations and do constant
	193	folding. Constants will be substituted to arguments by register
	194	allocator where needed and possible. Also detect copies. */
8f2e8c07	195	switch (op) {
22613af4 KB	196	CASE_OP_32_64(mov):
	197	if ((temps[args[1]].state == TCG_TEMP_COPY
	198	&& temps[args[1]].val == args[0])
	199	\|\| args[0] == args[1]) {
	200	args += 2;
	201	gen_opc_buf[op_index] = INDEX_op_nop;
	202	break;
	203	}
	204	if (temps[args[1]].state != TCG_TEMP_CONST) {
	205	tcg_opt_gen_mov(gen_args, args[0], args[1],
	206	nb_temps, nb_globals);
	207	gen_args += 2;
	208	args += 2;
	209	break;
	210	}
	211	/* Source argument is constant. Rewrite the operation and
	212	let movi case handle it. */
	213	op = op_to_movi(op);
	214	gen_opc_buf[op_index] = op;
	215	args[1] = temps[args[1]].val;
	216	/* fallthrough */
	217	CASE_OP_32_64(movi):
	218	tcg_opt_gen_movi(gen_args, args[0], args[1], nb_temps, nb_globals);
	219	gen_args += 2;
	220	args += 2;
	221	break;
8f2e8c07	222	case INDEX_op_call:
22613af4 KB	223	nb_call_args = (args[0] >> 16) + (args[0] & 0xffff);
	224	if (!(args[nb_call_args + 1] & (TCG_CALL_CONST \| TCG_CALL_PURE))) {
	225	for (i = 0; i < nb_globals; i++) {
	226	reset_temp(i, nb_temps, nb_globals);
	227	}
	228	}
	229	for (i = 0; i < (args[0] >> 16); i++) {
	230	reset_temp(args[i + 1], nb_temps, nb_globals);
	231	}
	232	i = nb_call_args + 3;
8f2e8c07 KB	233	while (i) {
	234	gen_args = args;
	235	args++;
	236	gen_args++;
	237	i--;
	238	}
	239	break;
	240	case INDEX_op_set_label:
	241	case INDEX_op_jmp:
	242	case INDEX_op_br:
	243	CASE_OP_32_64(brcond):
22613af4	244	memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
8f2e8c07 KB	245	for (i = 0; i < def->nb_args; i++) {
	246	gen_args = args;
	247	args++;
	248	gen_args++;
	249	}
	250	break;
	251	default:
22613af4 KB	252	/* Default case: we do know nothing about operation so no
	253	propagation is done. We only trash output args. */
	254	for (i = 0; i < def->nb_oargs; i++) {
	255	reset_temp(args[i], nb_temps, nb_globals);
	256	}
8f2e8c07 KB	257	for (i = 0; i < def->nb_args; i++) {
	258	gen_args[i] = args[i];
	259	}
	260	args += def->nb_args;
	261	gen_args += def->nb_args;
	262	break;
	263	}
	264	}
	265
	266	return gen_args;
	267	}
	268
	269	TCGArg tcg_optimize(TCGContext s, uint16_t *tcg_opc_ptr,
	270	TCGArg args, TCGOpDef tcg_op_defs)
	271	{
	272	TCGArg *res;
	273	res = tcg_constant_folding(s, tcg_opc_ptr, args, tcg_op_defs);
	274	return res;
	275	}