tcg/optimize.c

   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
  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     case INDEX_op_and_i32:
 103     case INDEX_op_or_i32:
 104     case INDEX_op_xor_i32:
 105     case INDEX_op_shl_i32:
 106     case INDEX_op_shr_i32:
 107     case INDEX_op_sar_i32:
 108     case INDEX_op_rotl_i32:
 109     case INDEX_op_rotr_i32:
 110         return 32;
 111 #if TCG_TARGET_REG_BITS == 64
 112     case INDEX_op_mov_i64:
 113     case INDEX_op_add_i64:
 114     case INDEX_op_sub_i64:
 115     case INDEX_op_mul_i64:
 116     case INDEX_op_and_i64:
 117     case INDEX_op_or_i64:
 118     case INDEX_op_xor_i64:
 119     case INDEX_op_shl_i64:
 120     case INDEX_op_shr_i64:
 121     case INDEX_op_sar_i64:
 122     case INDEX_op_rotl_i64:
 123     case INDEX_op_rotr_i64:
 124         return 64;
 125 #endif
 126     default:
 127         fprintf(stderr, "Unrecognized operation %d in op_bits.\n", op);
 128         tcg_abort();
 129     }
 130 }
 131
 132 static int op_to_movi(int op)
 133 {
 134     switch (op_bits(op)) {
 135     case 32:
 136         return INDEX_op_movi_i32;
 137 #if TCG_TARGET_REG_BITS == 64
 138     case 64:
 139         return INDEX_op_movi_i64;
 140 #endif
 141     default:
 142         fprintf(stderr, "op_to_movi: unexpected return value of "
 143                 "function op_bits.\n");
 144         tcg_abort();
 145     }
 146 }
 147
 148 static void tcg_opt_gen_mov(TCGArg *gen_args, TCGArg dst, TCGArg src,
 149                             int nb_temps, int nb_globals)
 150 {
 151         reset_temp(dst, nb_temps, nb_globals);
 152         assert(temps[src].state != TCG_TEMP_COPY);
 153         if (src >= nb_globals) {
 154             assert(temps[src].state != TCG_TEMP_CONST);
 155             if (temps[src].state != TCG_TEMP_HAS_COPY) {
 156                 temps[src].state = TCG_TEMP_HAS_COPY;
 157                 temps[src].next_copy = src;
 158                 temps[src].prev_copy = src;
 159             }
 160             temps[dst].state = TCG_TEMP_COPY;
 161             temps[dst].val = src;
 162             temps[dst].next_copy = temps[src].next_copy;
 163             temps[dst].prev_copy = src;
 164             temps[temps[dst].next_copy].prev_copy = dst;
 165             temps[src].next_copy = dst;
 166         }
 167         gen_args[0] = dst;
 168         gen_args[1] = src;
 169 }
 170
 171 static void tcg_opt_gen_movi(TCGArg *gen_args, TCGArg dst, TCGArg val,
 172                              int nb_temps, int nb_globals)
 173 {
 174         reset_temp(dst, nb_temps, nb_globals);
 175         temps[dst].state = TCG_TEMP_CONST;
 176         temps[dst].val = val;
 177         gen_args[0] = dst;
 178         gen_args[1] = val;
 179 }
 180
 181 static int op_to_mov(int op)
 182 {
 183     switch (op_bits(op)) {
 184     case 32:
 185         return INDEX_op_mov_i32;
 186 #if TCG_TARGET_REG_BITS == 64
 187     case 64:
 188         return INDEX_op_mov_i64;
 189 #endif
 190     default:
 191         fprintf(stderr, "op_to_mov: unexpected return value of "
 192                 "function op_bits.\n");
 193         tcg_abort();
 194     }
 195 }
 196
 197 static TCGArg do_constant_folding_2(int op, TCGArg x, TCGArg y)
 198 {
 199     switch (op) {
 200     CASE_OP_32_64(add):
 201         return x + y;
 202
 203     CASE_OP_32_64(sub):
 204         return x - y;
 205
 206     CASE_OP_32_64(mul):
 207         return x * y;
 208
 209     CASE_OP_32_64(and):
 210         return x & y;
 211
 212     CASE_OP_32_64(or):
 213         return x | y;
 214
 215     CASE_OP_32_64(xor):
 216         return x ^ y;
 217
 218     case INDEX_op_shl_i32:
 219         return (uint32_t)x << (uint32_t)y;
 220
 221 #if TCG_TARGET_REG_BITS == 64
 222     case INDEX_op_shl_i64:
 223         return (uint64_t)x << (uint64_t)y;
 224 #endif
 225
 226     case INDEX_op_shr_i32:
 227         return (uint32_t)x >> (uint32_t)y;
 228
 229 #if TCG_TARGET_REG_BITS == 64
 230     case INDEX_op_shr_i64:
 231         return (uint64_t)x >> (uint64_t)y;
 232 #endif
 233
 234     case INDEX_op_sar_i32:
 235         return (int32_t)x >> (int32_t)y;
 236
 237 #if TCG_TARGET_REG_BITS == 64
 238     case INDEX_op_sar_i64:
 239         return (int64_t)x >> (int64_t)y;
 240 #endif
 241
 242     case INDEX_op_rotr_i32:
 243 #if TCG_TARGET_REG_BITS == 64
 244         x &= 0xffffffff;
 245         y &= 0xffffffff;
 246 #endif
 247         x = (x << (32 - y)) | (x >> y);
 248         return x;
 249
 250 #if TCG_TARGET_REG_BITS == 64
 251     case INDEX_op_rotr_i64:
 252         x = (x << (64 - y)) | (x >> y);
 253         return x;
 254 #endif
 255
 256     case INDEX_op_rotl_i32:
 257 #if TCG_TARGET_REG_BITS == 64
 258         x &= 0xffffffff;
 259         y &= 0xffffffff;
 260 #endif
 261         x = (x << y) | (x >> (32 - y));
 262         return x;
 263
 264 #if TCG_TARGET_REG_BITS == 64
 265     case INDEX_op_rotl_i64:
 266         x = (x << y) | (x >> (64 - y));
 267         return x;
 268 #endif
 269
 270     default:
 271         fprintf(stderr,
 272                 "Unrecognized operation %d in do_constant_folding.\n", op);
 273         tcg_abort();
 274     }
 275 }
 276
 277 static TCGArg do_constant_folding(int op, TCGArg x, TCGArg y)
 278 {
 279     TCGArg res = do_constant_folding_2(op, x, y);
 280 #if TCG_TARGET_REG_BITS == 64
 281     if (op_bits(op) == 32) {
 282         res &= 0xffffffff;
 283     }
 284 #endif
 285     return res;
 286 }
 287
 288 /* Propagate constants and copies, fold constant expressions. */
 289 static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr,
 290                                     TCGArg *args, TCGOpDef *tcg_op_defs)
 291 {
 292     int i, nb_ops, op_index, op, nb_temps, nb_globals, nb_call_args;
 293     const TCGOpDef *def;
 294     TCGArg *gen_args;
 295     TCGArg tmp;
 296     /* Array VALS has an element for each temp.
 297        If this temp holds a constant then its value is kept in VALS' element.
 298        If this temp is a copy of other ones then this equivalence class'
 299        representative is kept in VALS' element.
 300        If this temp is neither copy nor constant then corresponding VALS'
 301        element is unused. */
 302
 303     nb_temps = s->nb_temps;
 304     nb_globals = s->nb_globals;
 305     memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
 306
 307     nb_ops = tcg_opc_ptr - gen_opc_buf;
 308     gen_args = args;
 309     for (op_index = 0; op_index < nb_ops; op_index++) {
 310         op = gen_opc_buf[op_index];
 311         def = &tcg_op_defs[op];
 312         /* Do copy propagation */
 313         if (!(def->flags & (TCG_OPF_CALL_CLOBBER | TCG_OPF_SIDE_EFFECTS))) {
 314             assert(op != INDEX_op_call);
 315             for (i = def->nb_oargs; i < def->nb_oargs + def->nb_iargs; i++) {
 316                 if (temps[args[i]].state == TCG_TEMP_COPY) {
 317                     args[i] = temps[args[i]].val;
 318                 }
 319             }
 320         }
 321
 322         /* For commutative operations make constant second argument */
 323         switch (op) {
 324         CASE_OP_32_64(add):
 325         CASE_OP_32_64(mul):
 326         CASE_OP_32_64(and):
 327         CASE_OP_32_64(or):
 328         CASE_OP_32_64(xor):
 329             if (temps[args[1]].state == TCG_TEMP_CONST) {
 330                 tmp = args[1];
 331                 args[1] = args[2];
 332                 args[2] = tmp;
 333             }
 334             break;
 335         default:
 336             break;
 337         }
 338
 339         /* Simplify expression if possible. */
 340         switch (op) {
 341         CASE_OP_32_64(add):
 342         CASE_OP_32_64(sub):
 343         CASE_OP_32_64(shl):
 344         CASE_OP_32_64(shr):
 345         CASE_OP_32_64(sar):
 346         CASE_OP_32_64(rotl):
 347         CASE_OP_32_64(rotr):
 348             if (temps[args[1]].state == TCG_TEMP_CONST) {
 349                 /* Proceed with possible constant folding. */
 350                 break;
 351             }
 352             if (temps[args[2]].state == TCG_TEMP_CONST
 353                 && temps[args[2]].val == 0) {
 354                 if ((temps[args[0]].state == TCG_TEMP_COPY
 355                     && temps[args[0]].val == args[1])
 356                     || args[0] == args[1]) {
 357                     args += 3;
 358                     gen_opc_buf[op_index] = INDEX_op_nop;
 359                 } else {
 360                     gen_opc_buf[op_index] = op_to_mov(op);
 361                     tcg_opt_gen_mov(gen_args, args[0], args[1],
 362                                     nb_temps, nb_globals);
 363                     gen_args += 2;
 364                     args += 3;
 365                 }
 366                 continue;
 367             }
 368             break;
 369         CASE_OP_32_64(mul):
 370             if ((temps[args[2]].state == TCG_TEMP_CONST
 371                 && temps[args[2]].val == 0)) {
 372                 gen_opc_buf[op_index] = op_to_movi(op);
 373                 tcg_opt_gen_movi(gen_args, args[0], 0, nb_temps, nb_globals);
 374                 args += 3;
 375                 gen_args += 2;
 376                 continue;
 377             }
 378             break;
 379         CASE_OP_32_64(or):
 380         CASE_OP_32_64(and):
 381             if (args[1] == args[2]) {
 382                 if (args[1] == args[0]) {
 383                     args += 3;
 384                     gen_opc_buf[op_index] = INDEX_op_nop;
 385                 } else {
 386                     gen_opc_buf[op_index] = op_to_mov(op);
 387                     tcg_opt_gen_mov(gen_args, args[0], args[1], nb_temps,
 388                                     nb_globals);
 389                     gen_args += 2;
 390                     args += 3;
 391                 }
 392                 continue;
 393             }
 394             break;
 395         }
 396
 397         /* Propagate constants through copy operations and do constant
 398            folding.  Constants will be substituted to arguments by register
 399            allocator where needed and possible.  Also detect copies. */
 400         switch (op) {
 401         CASE_OP_32_64(mov):
 402             if ((temps[args[1]].state == TCG_TEMP_COPY
 403                 && temps[args[1]].val == args[0])
 404                 || args[0] == args[1]) {
 405                 args += 2;
 406                 gen_opc_buf[op_index] = INDEX_op_nop;
 407                 break;
 408             }
 409             if (temps[args[1]].state != TCG_TEMP_CONST) {
 410                 tcg_opt_gen_mov(gen_args, args[0], args[1],
 411                                 nb_temps, nb_globals);
 412                 gen_args += 2;
 413                 args += 2;
 414                 break;
 415             }
 416             /* Source argument is constant.  Rewrite the operation and
 417                let movi case handle it. */
 418             op = op_to_movi(op);
 419             gen_opc_buf[op_index] = op;
 420             args[1] = temps[args[1]].val;
 421             /* fallthrough */
 422         CASE_OP_32_64(movi):
 423             tcg_opt_gen_movi(gen_args, args[0], args[1], nb_temps, nb_globals);
 424             gen_args += 2;
 425             args += 2;
 426             break;
 427         CASE_OP_32_64(add):
 428         CASE_OP_32_64(sub):
 429         CASE_OP_32_64(mul):
 430         CASE_OP_32_64(or):
 431         CASE_OP_32_64(and):
 432         CASE_OP_32_64(xor):
 433         CASE_OP_32_64(shl):
 434         CASE_OP_32_64(shr):
 435         CASE_OP_32_64(sar):
 436         CASE_OP_32_64(rotl):
 437         CASE_OP_32_64(rotr):
 438             if (temps[args[1]].state == TCG_TEMP_CONST
 439                 && temps[args[2]].state == TCG_TEMP_CONST) {
 440                 gen_opc_buf[op_index] = op_to_movi(op);
 441                 tmp = do_constant_folding(op, temps[args[1]].val,
 442                                           temps[args[2]].val);
 443                 tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
 444                 gen_args += 2;
 445                 args += 3;
 446                 break;
 447             } else {
 448                 reset_temp(args[0], nb_temps, nb_globals);
 449                 gen_args[0] = args[0];
 450                 gen_args[1] = args[1];
 451                 gen_args[2] = args[2];
 452                 gen_args += 3;
 453                 args += 3;
 454                 break;
 455             }
 456         case INDEX_op_call:
 457             nb_call_args = (args[0] >> 16) + (args[0] & 0xffff);
 458             if (!(args[nb_call_args + 1] & (TCG_CALL_CONST | TCG_CALL_PURE))) {
 459                 for (i = 0; i < nb_globals; i++) {
 460                     reset_temp(i, nb_temps, nb_globals);
 461                 }
 462             }
 463             for (i = 0; i < (args[0] >> 16); i++) {
 464                 reset_temp(args[i + 1], nb_temps, nb_globals);
 465             }
 466             i = nb_call_args + 3;
 467             while (i) {
 468                 *gen_args = *args;
 469                 args++;
 470                 gen_args++;
 471                 i--;
 472             }
 473             break;
 474         case INDEX_op_set_label:
 475         case INDEX_op_jmp:
 476         case INDEX_op_br:
 477         CASE_OP_32_64(brcond):
 478             memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
 479             for (i = 0; i < def->nb_args; i++) {
 480                 *gen_args = *args;
 481                 args++;
 482                 gen_args++;
 483             }
 484             break;
 485         default:
 486             /* Default case: we do know nothing about operation so no
 487                propagation is done.  We only trash output args.  */
 488             for (i = 0; i < def->nb_oargs; i++) {
 489                 reset_temp(args[i], nb_temps, nb_globals);
 490             }
 491             for (i = 0; i < def->nb_args; i++) {
 492                 gen_args[i] = args[i];
 493             }
 494             args += def->nb_args;
 495             gen_args += def->nb_args;
 496             break;
 497         }
 498     }
 499
 500     return gen_args;
 501 }
 502
 503 TCGArg *tcg_optimize(TCGContext *s, uint16_t *tcg_opc_ptr,
 504         TCGArg *args, TCGOpDef *tcg_op_defs)
 505 {
 506     TCGArg *res;
 507     res = tcg_constant_folding(s, tcg_opc_ptr, args, tcg_op_defs);
 508     return res;
 509 }