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(enum TCGOpcode op)
  96 {
  97     const TCGOpDef *def = &tcg_op_defs[op];
  98     return def->flags & TCG_OPF_64BIT ? 64 : 32;
  99 }
 100
 101 static int op_to_movi(int op)
 102 {
 103     switch (op_bits(op)) {
 104     case 32:
 105         return INDEX_op_movi_i32;
 106 #if TCG_TARGET_REG_BITS == 64
 107     case 64:
 108         return INDEX_op_movi_i64;
 109 #endif
 110     default:
 111         fprintf(stderr, "op_to_movi: unexpected return value of "
 112                 "function op_bits.\n");
 113         tcg_abort();
 114     }
 115 }
 116
 117 static void tcg_opt_gen_mov(TCGContext *s, TCGArg *gen_args, TCGArg dst,
 118                             TCGArg src, int nb_temps, int nb_globals)
 119 {
 120         reset_temp(dst, nb_temps, nb_globals);
 121         assert(temps[src].state != TCG_TEMP_COPY);
 122         /* Don't try to copy if one of temps is a global or either one
 123            is local and another is register */
 124         if (src >= nb_globals && dst >= nb_globals &&
 125             tcg_arg_is_local(s, src) == tcg_arg_is_local(s, dst)) {
 126             assert(temps[src].state != TCG_TEMP_CONST);
 127             if (temps[src].state != TCG_TEMP_HAS_COPY) {
 128                 temps[src].state = TCG_TEMP_HAS_COPY;
 129                 temps[src].next_copy = src;
 130                 temps[src].prev_copy = src;
 131             }
 132             temps[dst].state = TCG_TEMP_COPY;
 133             temps[dst].val = src;
 134             temps[dst].next_copy = temps[src].next_copy;
 135             temps[dst].prev_copy = src;
 136             temps[temps[dst].next_copy].prev_copy = dst;
 137             temps[src].next_copy = dst;
 138         }
 139         gen_args[0] = dst;
 140         gen_args[1] = src;
 141 }
 142
 143 static void tcg_opt_gen_movi(TCGArg *gen_args, TCGArg dst, TCGArg val,
 144                              int nb_temps, int nb_globals)
 145 {
 146         reset_temp(dst, nb_temps, nb_globals);
 147         temps[dst].state = TCG_TEMP_CONST;
 148         temps[dst].val = val;
 149         gen_args[0] = dst;
 150         gen_args[1] = val;
 151 }
 152
 153 static int op_to_mov(int op)
 154 {
 155     switch (op_bits(op)) {
 156     case 32:
 157         return INDEX_op_mov_i32;
 158 #if TCG_TARGET_REG_BITS == 64
 159     case 64:
 160         return INDEX_op_mov_i64;
 161 #endif
 162     default:
 163         fprintf(stderr, "op_to_mov: unexpected return value of "
 164                 "function op_bits.\n");
 165         tcg_abort();
 166     }
 167 }
 168
 169 static TCGArg do_constant_folding_2(int op, TCGArg x, TCGArg y)
 170 {
 171     switch (op) {
 172     CASE_OP_32_64(add):
 173         return x + y;
 174
 175     CASE_OP_32_64(sub):
 176         return x - y;
 177
 178     CASE_OP_32_64(mul):
 179         return x * y;
 180
 181     CASE_OP_32_64(and):
 182         return x & y;
 183
 184     CASE_OP_32_64(or):
 185         return x | y;
 186
 187     CASE_OP_32_64(xor):
 188         return x ^ y;
 189
 190     case INDEX_op_shl_i32:
 191         return (uint32_t)x << (uint32_t)y;
 192
 193 #if TCG_TARGET_REG_BITS == 64
 194     case INDEX_op_shl_i64:
 195         return (uint64_t)x << (uint64_t)y;
 196 #endif
 197
 198     case INDEX_op_shr_i32:
 199         return (uint32_t)x >> (uint32_t)y;
 200
 201 #if TCG_TARGET_REG_BITS == 64
 202     case INDEX_op_shr_i64:
 203         return (uint64_t)x >> (uint64_t)y;
 204 #endif
 205
 206     case INDEX_op_sar_i32:
 207         return (int32_t)x >> (int32_t)y;
 208
 209 #if TCG_TARGET_REG_BITS == 64
 210     case INDEX_op_sar_i64:
 211         return (int64_t)x >> (int64_t)y;
 212 #endif
 213
 214 #ifdef TCG_TARGET_HAS_rot_i32
 215     case INDEX_op_rotr_i32:
 216 #if TCG_TARGET_REG_BITS == 64
 217         x &= 0xffffffff;
 218         y &= 0xffffffff;
 219 #endif
 220         x = (x << (32 - y)) | (x >> y);
 221         return x;
 222 #endif
 223
 224 #ifdef TCG_TARGET_HAS_rot_i64
 225 #if TCG_TARGET_REG_BITS == 64
 226     case INDEX_op_rotr_i64:
 227         x = (x << (64 - y)) | (x >> y);
 228         return x;
 229 #endif
 230 #endif
 231
 232 #ifdef TCG_TARGET_HAS_rot_i32
 233     case INDEX_op_rotl_i32:
 234 #if TCG_TARGET_REG_BITS == 64
 235         x &= 0xffffffff;
 236         y &= 0xffffffff;
 237 #endif
 238         x = (x << y) | (x >> (32 - y));
 239         return x;
 240 #endif
 241
 242 #ifdef TCG_TARGET_HAS_rot_i64
 243 #if TCG_TARGET_REG_BITS == 64
 244     case INDEX_op_rotl_i64:
 245         x = (x << y) | (x >> (64 - y));
 246         return x;
 247 #endif
 248 #endif
 249
 250 #if defined(TCG_TARGET_HAS_not_i32) || defined(TCG_TARGET_HAS_not_i64)
 251 #ifdef TCG_TARGET_HAS_not_i32
 252     case INDEX_op_not_i32:
 253 #endif
 254 #ifdef TCG_TARGET_HAS_not_i64
 255     case INDEX_op_not_i64:
 256 #endif
 257         return ~x;
 258 #endif
 259
 260 #if defined(TCG_TARGET_HAS_ext8s_i32) || defined(TCG_TARGET_HAS_ext8s_i64)
 261 #ifdef TCG_TARGET_HAS_ext8s_i32
 262     case INDEX_op_ext8s_i32:
 263 #endif
 264 #ifdef TCG_TARGET_HAS_ext8s_i64
 265     case INDEX_op_ext8s_i64:
 266 #endif
 267         return (int8_t)x;
 268 #endif
 269
 270 #if defined(TCG_TARGET_HAS_ext16s_i32) || defined(TCG_TARGET_HAS_ext16s_i64)
 271 #ifdef TCG_TARGET_HAS_ext16s_i32
 272     case INDEX_op_ext16s_i32:
 273 #endif
 274 #ifdef TCG_TARGET_HAS_ext16s_i64
 275     case INDEX_op_ext16s_i64:
 276 #endif
 277         return (int16_t)x;
 278 #endif
 279
 280 #if defined(TCG_TARGET_HAS_ext8u_i32) || defined(TCG_TARGET_HAS_ext8u_i64)
 281 #ifdef TCG_TARGET_HAS_ext8u_i32
 282     case INDEX_op_ext8u_i32:
 283 #endif
 284 #ifdef TCG_TARGET_HAS_ext8u_i64
 285     case INDEX_op_ext8u_i64:
 286 #endif
 287         return (uint8_t)x;
 288 #endif
 289
 290 #if defined(TCG_TARGET_HAS_ext16u_i32) || defined(TCG_TARGET_HAS_ext16u_i64)
 291 #ifdef TCG_TARGET_HAS_ext16u_i32
 292     case INDEX_op_ext16u_i32:
 293 #endif
 294 #ifdef TCG_TARGET_HAS_ext16u_i64
 295     case INDEX_op_ext16u_i64:
 296 #endif
 297         return (uint16_t)x;
 298 #endif
 299
 300 #if TCG_TARGET_REG_BITS == 64
 301 #ifdef TCG_TARGET_HAS_ext32s_i64
 302     case INDEX_op_ext32s_i64:
 303         return (int32_t)x;
 304 #endif
 305
 306 #ifdef TCG_TARGET_HAS_ext32u_i64
 307     case INDEX_op_ext32u_i64:
 308         return (uint32_t)x;
 309 #endif
 310 #endif
 311
 312     default:
 313         fprintf(stderr,
 314                 "Unrecognized operation %d in do_constant_folding.\n", op);
 315         tcg_abort();
 316     }
 317 }
 318
 319 static TCGArg do_constant_folding(int op, TCGArg x, TCGArg y)
 320 {
 321     TCGArg res = do_constant_folding_2(op, x, y);
 322 #if TCG_TARGET_REG_BITS == 64
 323     if (op_bits(op) == 32) {
 324         res &= 0xffffffff;
 325     }
 326 #endif
 327     return res;
 328 }
 329
 330 /* Propagate constants and copies, fold constant expressions. */
 331 static TCGArg *tcg_constant_folding(TCGContext *s, uint16_t *tcg_opc_ptr,
 332                                     TCGArg *args, TCGOpDef *tcg_op_defs)
 333 {
 334     int i, nb_ops, op_index, op, nb_temps, nb_globals, nb_call_args;
 335     const TCGOpDef *def;
 336     TCGArg *gen_args;
 337     TCGArg tmp;
 338     /* Array VALS has an element for each temp.
 339        If this temp holds a constant then its value is kept in VALS' element.
 340        If this temp is a copy of other ones then this equivalence class'
 341        representative is kept in VALS' element.
 342        If this temp is neither copy nor constant then corresponding VALS'
 343        element is unused. */
 344
 345     nb_temps = s->nb_temps;
 346     nb_globals = s->nb_globals;
 347     memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
 348
 349     nb_ops = tcg_opc_ptr - gen_opc_buf;
 350     gen_args = args;
 351     for (op_index = 0; op_index < nb_ops; op_index++) {
 352         op = gen_opc_buf[op_index];
 353         def = &tcg_op_defs[op];
 354         /* Do copy propagation */
 355         if (!(def->flags & (TCG_OPF_CALL_CLOBBER | TCG_OPF_SIDE_EFFECTS))) {
 356             assert(op != INDEX_op_call);
 357             for (i = def->nb_oargs; i < def->nb_oargs + def->nb_iargs; i++) {
 358                 if (temps[args[i]].state == TCG_TEMP_COPY) {
 359                     args[i] = temps[args[i]].val;
 360                 }
 361             }
 362         }
 363
 364         /* For commutative operations make constant second argument */
 365         switch (op) {
 366         CASE_OP_32_64(add):
 367         CASE_OP_32_64(mul):
 368         CASE_OP_32_64(and):
 369         CASE_OP_32_64(or):
 370         CASE_OP_32_64(xor):
 371             if (temps[args[1]].state == TCG_TEMP_CONST) {
 372                 tmp = args[1];
 373                 args[1] = args[2];
 374                 args[2] = tmp;
 375             }
 376             break;
 377         default:
 378             break;
 379         }
 380
 381         /* Simplify expression if possible. */
 382         switch (op) {
 383         CASE_OP_32_64(add):
 384         CASE_OP_32_64(sub):
 385         CASE_OP_32_64(shl):
 386         CASE_OP_32_64(shr):
 387         CASE_OP_32_64(sar):
 388 #ifdef TCG_TARGET_HAS_rot_i32
 389         case INDEX_op_rotl_i32:
 390         case INDEX_op_rotr_i32:
 391 #endif
 392 #ifdef TCG_TARGET_HAS_rot_i64
 393         case INDEX_op_rotl_i64:
 394         case INDEX_op_rotr_i64:
 395 #endif
 396             if (temps[args[1]].state == TCG_TEMP_CONST) {
 397                 /* Proceed with possible constant folding. */
 398                 break;
 399             }
 400             if (temps[args[2]].state == TCG_TEMP_CONST
 401                 && temps[args[2]].val == 0) {
 402                 if ((temps[args[0]].state == TCG_TEMP_COPY
 403                     && temps[args[0]].val == args[1])
 404                     || args[0] == args[1]) {
 405                     args += 3;
 406                     gen_opc_buf[op_index] = INDEX_op_nop;
 407                 } else {
 408                     gen_opc_buf[op_index] = op_to_mov(op);
 409                     tcg_opt_gen_mov(s, gen_args, args[0], args[1],
 410                                     nb_temps, nb_globals);
 411                     gen_args += 2;
 412                     args += 3;
 413                 }
 414                 continue;
 415             }
 416             break;
 417         CASE_OP_32_64(mul):
 418             if ((temps[args[2]].state == TCG_TEMP_CONST
 419                 && temps[args[2]].val == 0)) {
 420                 gen_opc_buf[op_index] = op_to_movi(op);
 421                 tcg_opt_gen_movi(gen_args, args[0], 0, nb_temps, nb_globals);
 422                 args += 3;
 423                 gen_args += 2;
 424                 continue;
 425             }
 426             break;
 427         CASE_OP_32_64(or):
 428         CASE_OP_32_64(and):
 429             if (args[1] == args[2]) {
 430                 if (args[1] == args[0]) {
 431                     args += 3;
 432                     gen_opc_buf[op_index] = INDEX_op_nop;
 433                 } else {
 434                     gen_opc_buf[op_index] = op_to_mov(op);
 435                     tcg_opt_gen_mov(s, gen_args, args[0], args[1], nb_temps,
 436                                     nb_globals);
 437                     gen_args += 2;
 438                     args += 3;
 439                 }
 440                 continue;
 441             }
 442             break;
 443         }
 444
 445         /* Propagate constants through copy operations and do constant
 446            folding.  Constants will be substituted to arguments by register
 447            allocator where needed and possible.  Also detect copies. */
 448         switch (op) {
 449         CASE_OP_32_64(mov):
 450             if ((temps[args[1]].state == TCG_TEMP_COPY
 451                 && temps[args[1]].val == args[0])
 452                 || args[0] == args[1]) {
 453                 args += 2;
 454                 gen_opc_buf[op_index] = INDEX_op_nop;
 455                 break;
 456             }
 457             if (temps[args[1]].state != TCG_TEMP_CONST) {
 458                 tcg_opt_gen_mov(s, gen_args, args[0], args[1],
 459                                 nb_temps, nb_globals);
 460                 gen_args += 2;
 461                 args += 2;
 462                 break;
 463             }
 464             /* Source argument is constant.  Rewrite the operation and
 465                let movi case handle it. */
 466             op = op_to_movi(op);
 467             gen_opc_buf[op_index] = op;
 468             args[1] = temps[args[1]].val;
 469             /* fallthrough */
 470         CASE_OP_32_64(movi):
 471             tcg_opt_gen_movi(gen_args, args[0], args[1], nb_temps, nb_globals);
 472             gen_args += 2;
 473             args += 2;
 474             break;
 475         CASE_OP_32_64(not):
 476 #ifdef TCG_TARGET_HAS_ext8s_i32
 477         case INDEX_op_ext8s_i32:
 478 #endif
 479 #ifdef TCG_TARGET_HAS_ext8s_i64
 480         case INDEX_op_ext8s_i64:
 481 #endif
 482 #ifdef TCG_TARGET_HAS_ext16s_i32
 483         case INDEX_op_ext16s_i32:
 484 #endif
 485 #ifdef TCG_TARGET_HAS_ext16s_i64
 486         case INDEX_op_ext16s_i64:
 487 #endif
 488 #ifdef TCG_TARGET_HAS_ext8u_i32
 489         case INDEX_op_ext8u_i32:
 490 #endif
 491 #ifdef TCG_TARGET_HAS_ext8u_i64
 492         case INDEX_op_ext8u_i64:
 493 #endif
 494 #ifdef TCG_TARGET_HAS_ext16u_i32
 495         case INDEX_op_ext16u_i32:
 496 #endif
 497 #ifdef TCG_TARGET_HAS_ext16u_i64
 498         case INDEX_op_ext16u_i64:
 499 #endif
 500 #if TCG_TARGET_REG_BITS == 64
 501         case INDEX_op_ext32s_i64:
 502         case INDEX_op_ext32u_i64:
 503 #endif
 504             if (temps[args[1]].state == TCG_TEMP_CONST) {
 505                 gen_opc_buf[op_index] = op_to_movi(op);
 506                 tmp = do_constant_folding(op, temps[args[1]].val, 0);
 507                 tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
 508                 gen_args += 2;
 509                 args += 2;
 510                 break;
 511             } else {
 512                 reset_temp(args[0], nb_temps, nb_globals);
 513                 gen_args[0] = args[0];
 514                 gen_args[1] = args[1];
 515                 gen_args += 2;
 516                 args += 2;
 517                 break;
 518             }
 519         CASE_OP_32_64(add):
 520         CASE_OP_32_64(sub):
 521         CASE_OP_32_64(mul):
 522         CASE_OP_32_64(or):
 523         CASE_OP_32_64(and):
 524         CASE_OP_32_64(xor):
 525         CASE_OP_32_64(shl):
 526         CASE_OP_32_64(shr):
 527         CASE_OP_32_64(sar):
 528 #ifdef TCG_TARGET_HAS_rot_i32
 529         case INDEX_op_rotl_i32:
 530         case INDEX_op_rotr_i32:
 531 #endif
 532 #ifdef TCG_TARGET_HAS_rot_i64
 533         case INDEX_op_rotl_i64:
 534         case INDEX_op_rotr_i64:
 535 #endif
 536             if (temps[args[1]].state == TCG_TEMP_CONST
 537                 && temps[args[2]].state == TCG_TEMP_CONST) {
 538                 gen_opc_buf[op_index] = op_to_movi(op);
 539                 tmp = do_constant_folding(op, temps[args[1]].val,
 540                                           temps[args[2]].val);
 541                 tcg_opt_gen_movi(gen_args, args[0], tmp, nb_temps, nb_globals);
 542                 gen_args += 2;
 543                 args += 3;
 544                 break;
 545             } else {
 546                 reset_temp(args[0], nb_temps, nb_globals);
 547                 gen_args[0] = args[0];
 548                 gen_args[1] = args[1];
 549                 gen_args[2] = args[2];
 550                 gen_args += 3;
 551                 args += 3;
 552                 break;
 553             }
 554         case INDEX_op_call:
 555             nb_call_args = (args[0] >> 16) + (args[0] & 0xffff);
 556             if (!(args[nb_call_args + 1] & (TCG_CALL_CONST | TCG_CALL_PURE))) {
 557                 for (i = 0; i < nb_globals; i++) {
 558                     reset_temp(i, nb_temps, nb_globals);
 559                 }
 560             }
 561             for (i = 0; i < (args[0] >> 16); i++) {
 562                 reset_temp(args[i + 1], nb_temps, nb_globals);
 563             }
 564             i = nb_call_args + 3;
 565             while (i) {
 566                 *gen_args = *args;
 567                 args++;
 568                 gen_args++;
 569                 i--;
 570             }
 571             break;
 572         case INDEX_op_set_label:
 573         case INDEX_op_jmp:
 574         case INDEX_op_br:
 575         CASE_OP_32_64(brcond):
 576             memset(temps, 0, nb_temps * sizeof(struct tcg_temp_info));
 577             for (i = 0; i < def->nb_args; i++) {
 578                 *gen_args = *args;
 579                 args++;
 580                 gen_args++;
 581             }
 582             break;
 583         default:
 584             /* Default case: we do know nothing about operation so no
 585                propagation is done.  We only trash output args.  */
 586             for (i = 0; i < def->nb_oargs; i++) {
 587                 reset_temp(args[i], nb_temps, nb_globals);
 588             }
 589             for (i = 0; i < def->nb_args; i++) {
 590                 gen_args[i] = args[i];
 591             }
 592             args += def->nb_args;
 593             gen_args += def->nb_args;
 594             break;
 595         }
 596     }
 597
 598     return gen_args;
 599 }
 600
 601 TCGArg *tcg_optimize(TCGContext *s, uint16_t *tcg_opc_ptr,
 602         TCGArg *args, TCGOpDef *tcg_op_defs)
 603 {
 604     TCGArg *res;
 605     res = tcg_constant_folding(s, tcg_opc_ptr, args, tcg_op_defs);
 606     return res;
 607 }