tcg/optimize.c

   1 /*
   2  * Optimizations for Tiny Code Generator for QEMU
   3  *
   4  * Copyright (c) 2010 Samsung Electronics.
   5  * Contributed by Kirill Batuzov <[email protected]>
   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
  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     case INDEX_op_add_i32:
 100     case INDEX_op_sub_i32:
 101     case INDEX_op_mul_i32:
 102         return 32;
 103 #if TCG_TARGET_REG_BITS == 64
 104     case INDEX_op_mov_i64:
 105     case INDEX_op_add_i64:
 106     case INDEX_op_sub_i64:
 107     case INDEX_op_mul_i64:
 108         return 64;
 109 #endif
 110     default:
 111         fprintf(stderr, "Unrecognized operation %d in op_bits.\n", op);
 112         tcg_abort();
 113     }
 114 }
 115
 116 static int op_to_movi(int op)
 117 {
 118     switch (op_bits(op)) {
 119     case 32:
 120         return INDEX_op_movi_i32;
 121 #if TCG_TARGET_REG_BITS == 64
 122     case 64:
 123         return INDEX_op_movi_i64;
 124 #endif
 125     default:
 126         fprintf(stderr, "op_to_movi: unexpected return value of "
 127                 "function op_bits.\n");
 128         tcg_abort();
 129     }
 130 }
 131
 132 static void tcg_opt_gen_mov(TCGArg *gen_args, TCGArg dst, TCGArg src,
 133                             int nb_temps, int nb_globals)
 134 {
 135         reset_temp(dst, nb_temps, nb_globals);
 136         assert(temps[src].state != TCG_TEMP_COPY);
 137         if (src >= nb_globals) {
 138             assert(temps[src].state != TCG_TEMP_CONST);
 139             if (temps[src].state != TCG_TEMP_HAS_COPY) {
 140                 temps[src].state = TCG_TEMP_HAS_COPY;
 141                 temps[src].next_copy = src;
 142                 temps[src].prev_copy = src;
 143             }
 144             temps[dst].state = TCG_TEMP_COPY;
 145             temps[dst].val = src;
 146             temps[dst].next_copy = temps[src].next_copy;
 147             temps[dst].prev_copy = src;
 148             temps[temps[dst].next_copy].prev_copy = dst;
 149             temps[src].next_copy = dst;
 150         }
 151         gen_args[0] = dst;
 152         gen_args[1] = src;
 153 }
 154
 155 static void tcg_opt_gen_movi(TCGArg *gen_args, TCGArg dst, TCGArg val,
 156                              int nb_temps, int nb_globals)
 157 {
 158         reset_temp(dst, nb_temps, nb_globals);
 159         temps[dst].state = TCG_TEMP_CONST;
 160         temps[dst].val = val;
 161         gen_args[0] = dst;
 162         gen_args[1] = val;
 163 }
 164
 165 static int op_to_mov(int op)
 166 {
 167     switch (op_bits(op)) {
 168     case 32:
 169         return INDEX_op_mov_i32;
 170 #if TCG_TARGET_REG_BITS == 64
 171     case 64:
 172         return INDEX_op_mov_i64;
 173 #endif
 174     default:
 175         fprintf(stderr, "op_to_mov: unexpected return value of "
 176                 "function op_bits.\n");
 177         tcg_abort();
 178     }
 179 }
 180
 181 static TCGArg do_constant_folding_2(int op, TCGArg x, TCGArg y)
 182 {
 183     switch (op) {
 184     CASE_OP_32_64(add):
 185         return x + y;
 186
 187     CASE_OP_32_64(sub):
 188         return x - y;
 189
 190     CASE_OP_32_64(mul):
 191         return x * y;
 192
 193     default:
 194         fprintf(stderr,
 195                 "Unrecognized operation %d in do_constant_folding.\n", op);
 196         tcg_abort();
 197     }
 198 }
 199
 200 static TCGArg do_constant_folding(int op, TCGArg x, TCGArg y)
 201 {
 202     TCGArg res = do_constant_folding_2(op, x, y);
 203 #if TCG_TARGET_REG_BITS == 64
 204     if (op_bits(op) == 32) {
 205         res &= 0xffffffff;
 206     }
 207 #endif
 208     return res;
 209 }
 210
 211 /* Propagate constants and copies, fold constant expressions. */
 212 static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr,
 213                                     TCGArg *args, TCGOpDef *tcg_op_defs)
 214 {
 215     int i, nb_ops, op_index, op, nb_temps, nb_globals, nb_call_args;
 216     const TCGOpDef *def;
 217     TCGArg *gen_args;
 218     TCGArg tmp;
 219     /* Array VALS has an element for each temp.
 220        If this temp holds a constant then its value is kept in VALS' element.
 221        If this temp is a copy of other ones then this equivalence class'
 222        representative is kept in VALS' element.
 223        If this temp is neither copy nor constant then corresponding VALS'
 224        element is unused. */
 225
 226     nb_temps = s->nb_temps;
 227     nb_globals = s->nb_globals;
 228     memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
 229
 230     nb_ops = tcg_opc_ptr - gen_opc_buf;
 231     gen_args = args;
 232     for (op_index = 0; op_index < nb_ops; op_index++) {
 233         op = gen_opc_buf[op_index];
 234         def = &tcg_op_defs[op];
 235         /* Do copy propagation */
 236         if (!(def->flags & (TCG_OPF_CALL_CLOBBER | TCG_OPF_SIDE_EFFECTS))) {
 237             assert(op != INDEX_op_call);
 238             for (i = def->nb_oargs; i < def->nb_oargs + def->nb_iargs; i++) {
 239                 if (temps[args[i]].state == TCG_TEMP_COPY) {
 240                     args[i] = temps[args[i]].val;
 241                 }
 242             }
 243         }
 244
 245         /* For commutative operations make constant second argument */
 246         switch (op) {
 247         CASE_OP_32_64(add):
 248         CASE_OP_32_64(mul):
 249             if (temps[args[1]].state == TCG_TEMP_CONST) {
 250                 tmp = args[1];
 251                 args[1] = args[2];
 252                 args[2] = tmp;
 253             }
 254             break;
 255         default:
 256             break;
 257         }
 258
 259         /* Simplify expression if possible. */
 260         switch (op) {
 261         CASE_OP_32_64(add):
 262         CASE_OP_32_64(sub):
 263             if (temps[args[1]].state == TCG_TEMP_CONST) {
 264                 /* Proceed with possible constant folding. */
 265                 break;
 266             }
 267             if (temps[args[2]].state == TCG_TEMP_CONST
 268                 && temps[args[2]].val == 0) {
 269                 if ((temps[args[0]].state == TCG_TEMP_COPY
 270                     && temps[args[0]].val == args[1])
 271                     || args[0] == args[1]) {
 272                     args += 3;
 273                     gen_opc_buf[op_index] = INDEX_op_nop;
 274                 } else {
 275                     gen_opc_buf[op_index] = op_to_mov(op);
 276                     tcg_opt_gen_mov(gen_args, args[0], args[1],
 277                                     nb_temps, nb_globals);
 278                     gen_args += 2;
 279                     args += 3;
 280                 }
 281                 continue;
 282             }
 283             break;
 284         CASE_OP_32_64(mul):
 285             if ((temps[args[2]].state == TCG_TEMP_CONST
 286                 && temps[args[2]].val == 0)) {
 287                 gen_opc_buf[op_index] = op_to_movi(op);
 288                 tcg_opt_gen_movi(gen_args, args[0], 0, nb_temps, nb_globals);
 289                 args += 3;
 290                 gen_args += 2;
 291                 continue;
 292             }
 293             break;
 294         }
 295
 296         /* Propagate constants through copy operations and do constant
 297            folding.  Constants will be substituted to arguments by register
 298            allocator where needed and possible.  Also detect copies. */
 299         switch (op) {
 300         CASE_OP_32_64(mov):
 301             if ((temps[args[1]].state == TCG_TEMP_COPY
 302                 && temps[args[1]].val == args[0])
 303                 || args[0] == args[1]) {
 304                 args += 2;
 305                 gen_opc_buf[op_index] = INDEX_op_nop;
 306                 break;
 307             }
 308             if (temps[args[1]].state != TCG_TEMP_CONST) {
 309                 tcg_opt_gen_mov(gen_args, args[0], args[1],
 310                                 nb_temps, nb_globals);
 311                 gen_args += 2;
 312                 args += 2;
 313                 break;
 314             }
 315             /* Source argument is constant.  Rewrite the operation and
 316                let movi case handle it. */
 317             op = op_to_movi(op);
 318             gen_opc_buf[op_index] = op;
 319             args[1] = temps[args[1]].val;
 320             /* fallthrough */
 321         CASE_OP_32_64(movi):
 322             tcg_opt_gen_movi(gen_args, args[0], args[1], nb_temps, nb_globals);
 323             gen_args += 2;
 324             args += 2;
 325             break;
 326         CASE_OP_32_64(add):
 327         CASE_OP_32_64(sub):
 328         CASE_OP_32_64(mul):
 329             if (temps[args[1]].state == TCG_TEMP_CONST
 330                 && temps[args[2]].state == TCG_TEMP_CONST) {
 331                 gen_opc_buf[op_index] = op_to_movi(op);
 332                 tmp = do_constant_folding(op, temps[args[1]].val,
 333                                           temps[args[2]].val);
 334                 tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
 335                 gen_args += 2;
 336                 args += 3;
 337                 break;
 338             } else {
 339                 reset_temp(args[0], nb_temps, nb_globals);
 340                 gen_args[0] = args[0];
 341                 gen_args[1] = args[1];
 342                 gen_args[2] = args[2];
 343                 gen_args += 3;
 344                 args += 3;
 345                 break;
 346             }
 347         case INDEX_op_call:
 348             nb_call_args = (args[0] >> 16) + (args[0] & 0xffff);
 349             if (!(args[nb_call_args + 1] & (TCG_CALL_CONST | TCG_CALL_PURE))) {
 350                 for (i = 0; i < nb_globals; i++) {
 351                     reset_temp(i, nb_temps, nb_globals);
 352                 }
 353             }
 354             for (i = 0; i < (args[0] >> 16); i++) {
 355                 reset_temp(args[i + 1], nb_temps, nb_globals);
 356             }
 357             i = nb_call_args + 3;
 358             while (i) {
 359                 *gen_args = *args;
 360                 args++;
 361                 gen_args++;
 362                 i--;
 363             }
 364             break;
 365         case INDEX_op_set_label:
 366         case INDEX_op_jmp:
 367         case INDEX_op_br:
 368         CASE_OP_32_64(brcond):
 369             memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
 370             for (i = 0; i < def->nb_args; i++) {
 371                 *gen_args = *args;
 372                 args++;
 373                 gen_args++;
 374             }
 375             break;
 376         default:
 377             /* Default case: we do know nothing about operation so no
 378                propagation is done.  We only trash output args.  */
 379             for (i = 0; i < def->nb_oargs; i++) {
 380                 reset_temp(args[i], nb_temps, nb_globals);
 381             }
 382             for (i = 0; i < def->nb_args; i++) {
 383                 gen_args[i] = args[i];
 384             }
 385             args += def->nb_args;
 386             gen_args += def->nb_args;
 387             break;
 388         }
 389     }
 390
 391     return gen_args;
 392 }
 393
 394 TCGArg *tcg_optimize(TCGContext *s, uint16_t *tcg_opc_ptr,
 395         TCGArg *args, TCGOpDef *tcg_op_defs)
 396 {
 397     TCGArg *res;
 398     res = tcg_constant_folding(s, tcg_opc_ptr, args, tcg_op_defs);
 399     return res;
 400 }