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 "qemu/osdep.h" 27 28 29 #include "qemu-common.h" 30 #include "tcg-op.h" 31 32 #define CASE_OP_32_64(x) \ 33 glue(glue(case INDEX_op_, x), _i32): \ 34 glue(glue(case INDEX_op_, x), _i64) 35 36 struct tcg_temp_info { 37 bool is_const; 38 uint16_t prev_copy; 39 uint16_t next_copy; 40 tcg_target_ulong val; 41 tcg_target_ulong mask; 42 }; 43 44 static struct tcg_temp_info temps[TCG_MAX_TEMPS]; 45 static TCGTempSet temps_used; 46 47 static inline bool temp_is_const(TCGArg arg) 48 { 49 return temps[arg].is_const; 50 } 51 52 static inline bool temp_is_copy(TCGArg arg) 53 { 54 return temps[arg].next_copy != arg; 55 } 56 57 /* Reset TEMP's state, possibly removing the temp for the list of copies. */ 58 static void reset_temp(TCGArg temp) 59 { 60 temps[temps[temp].next_copy].prev_copy = temps[temp].prev_copy; 61 temps[temps[temp].prev_copy].next_copy = temps[temp].next_copy; 62 temps[temp].next_copy = temp; 63 temps[temp].prev_copy = temp; 64 temps[temp].is_const = false; 65 temps[temp].mask = -1; 66 } 67 68 /* Reset all temporaries, given that there are NB_TEMPS of them. */ 69 static void reset_all_temps(int nb_temps) 70 { 71 bitmap_zero(temps_used.l, nb_temps); 72 } 73 74 /* Initialize and activate a temporary. */ 75 static void init_temp_info(TCGArg temp) 76 { 77 if (!test_bit(temp, temps_used.l)) { 78 temps[temp].next_copy = temp; 79 temps[temp].prev_copy = temp; 80 temps[temp].is_const = false; 81 temps[temp].mask = -1; 82 set_bit(temp, temps_used.l); 83 } 84 } 85 86 static TCGOp *insert_op_before(TCGContext *s, TCGOp *old_op, 87 TCGOpcode opc, int nargs) 88 { 89 int oi = s->gen_next_op_idx; 90 int pi = s->gen_next_parm_idx; 91 int prev = old_op->prev; 92 int next = old_op - s->gen_op_buf; 93 TCGOp *new_op; 94 95 tcg_debug_assert(oi < OPC_BUF_SIZE); 96 tcg_debug_assert(pi + nargs <= OPPARAM_BUF_SIZE); 97 s->gen_next_op_idx = oi + 1; 98 s->gen_next_parm_idx = pi + nargs; 99 100 new_op = &s->gen_op_buf[oi]; 101 *new_op = (TCGOp){ 102 .opc = opc, 103 .args = pi, 104 .prev = prev, 105 .next = next 106 }; 107 if (prev >= 0) { 108 s->gen_op_buf[prev].next = oi; 109 } else { 110 s->gen_first_op_idx = oi; 111 } 112 old_op->prev = oi; 113 114 return new_op; 115 } 116 117 static int op_bits(TCGOpcode op) 118 { 119 const TCGOpDef *def = &tcg_op_defs[op]; 120 return def->flags & TCG_OPF_64BIT ? 64 : 32; 121 } 122 123 static TCGOpcode op_to_mov(TCGOpcode op) 124 { 125 switch (op_bits(op)) { 126 case 32: 127 return INDEX_op_mov_i32; 128 case 64: 129 return INDEX_op_mov_i64; 130 default: 131 fprintf(stderr, "op_to_mov: unexpected return value of " 132 "function op_bits.\n"); 133 tcg_abort(); 134 } 135 } 136 137 static TCGOpcode op_to_movi(TCGOpcode op) 138 { 139 switch (op_bits(op)) { 140 case 32: 141 return INDEX_op_movi_i32; 142 case 64: 143 return INDEX_op_movi_i64; 144 default: 145 fprintf(stderr, "op_to_movi: unexpected return value of " 146 "function op_bits.\n"); 147 tcg_abort(); 148 } 149 } 150 151 static TCGArg find_better_copy(TCGContext *s, TCGArg temp) 152 { 153 TCGArg i; 154 155 /* If this is already a global, we can't do better. */ 156 if (temp < s->nb_globals) { 157 return temp; 158 } 159 160 /* Search for a global first. */ 161 for (i = temps[temp].next_copy ; i != temp ; i = temps[i].next_copy) { 162 if (i < s->nb_globals) { 163 return i; 164 } 165 } 166 167 /* If it is a temp, search for a temp local. */ 168 if (!s->temps[temp].temp_local) { 169 for (i = temps[temp].next_copy ; i != temp ; i = temps[i].next_copy) { 170 if (s->temps[i].temp_local) { 171 return i; 172 } 173 } 174 } 175 176 /* Failure to find a better representation, return the same temp. */ 177 return temp; 178 } 179 180 static bool temps_are_copies(TCGArg arg1, TCGArg arg2) 181 { 182 TCGArg i; 183 184 if (arg1 == arg2) { 185 return true; 186 } 187 188 if (!temp_is_copy(arg1) || !temp_is_copy(arg2)) { 189 return false; 190 } 191 192 for (i = temps[arg1].next_copy ; i != arg1 ; i = temps[i].next_copy) { 193 if (i == arg2) { 194 return true; 195 } 196 } 197 198 return false; 199 } 200 201 static void tcg_opt_gen_movi(TCGContext *s, TCGOp *op, TCGArg *args, 202 TCGArg dst, TCGArg val) 203 { 204 TCGOpcode new_op = op_to_movi(op->opc); 205 tcg_target_ulong mask; 206 207 op->opc = new_op; 208 209 reset_temp(dst); 210 temps[dst].is_const = true; 211 temps[dst].val = val; 212 mask = val; 213 if (TCG_TARGET_REG_BITS > 32 && new_op == INDEX_op_movi_i32) { 214 /* High bits of the destination are now garbage. */ 215 mask |= ~0xffffffffull; 216 } 217 temps[dst].mask = mask; 218 219 args[0] = dst; 220 args[1] = val; 221 } 222 223 static void tcg_opt_gen_mov(TCGContext *s, TCGOp *op, TCGArg *args, 224 TCGArg dst, TCGArg src) 225 { 226 if (temps_are_copies(dst, src)) { 227 tcg_op_remove(s, op); 228 return; 229 } 230 231 TCGOpcode new_op = op_to_mov(op->opc); 232 tcg_target_ulong mask; 233 234 op->opc = new_op; 235 236 reset_temp(dst); 237 mask = temps[src].mask; 238 if (TCG_TARGET_REG_BITS > 32 && new_op == INDEX_op_mov_i32) { 239 /* High bits of the destination are now garbage. */ 240 mask |= ~0xffffffffull; 241 } 242 temps[dst].mask = mask; 243 244 if (s->temps[src].type == s->temps[dst].type) { 245 temps[dst].next_copy = temps[src].next_copy; 246 temps[dst].prev_copy = src; 247 temps[temps[dst].next_copy].prev_copy = dst; 248 temps[src].next_copy = dst; 249 temps[dst].is_const = temps[src].is_const; 250 temps[dst].val = temps[src].val; 251 } 252 253 args[0] = dst; 254 args[1] = src; 255 } 256 257 static TCGArg do_constant_folding_2(TCGOpcode op, TCGArg x, TCGArg y) 258 { 259 uint64_t l64, h64; 260 261 switch (op) { 262 CASE_OP_32_64(add): 263 return x + y; 264 265 CASE_OP_32_64(sub): 266 return x - y; 267 268 CASE_OP_32_64(mul): 269 return x * y; 270 271 CASE_OP_32_64(and): 272 return x & y; 273 274 CASE_OP_32_64(or): 275 return x | y; 276 277 CASE_OP_32_64(xor): 278 return x ^ y; 279 280 case INDEX_op_shl_i32: 281 return (uint32_t)x << (y & 31); 282 283 case INDEX_op_shl_i64: 284 return (uint64_t)x << (y & 63); 285 286 case INDEX_op_shr_i32: 287 return (uint32_t)x >> (y & 31); 288 289 case INDEX_op_shr_i64: 290 return (uint64_t)x >> (y & 63); 291 292 case INDEX_op_sar_i32: 293 return (int32_t)x >> (y & 31); 294 295 case INDEX_op_sar_i64: 296 return (int64_t)x >> (y & 63); 297 298 case INDEX_op_rotr_i32: 299 return ror32(x, y & 31); 300 301 case INDEX_op_rotr_i64: 302 return ror64(x, y & 63); 303 304 case INDEX_op_rotl_i32: 305 return rol32(x, y & 31); 306 307 case INDEX_op_rotl_i64: 308 return rol64(x, y & 63); 309 310 CASE_OP_32_64(not): 311 return ~x; 312 313 CASE_OP_32_64(neg): 314 return -x; 315 316 CASE_OP_32_64(andc): 317 return x & ~y; 318 319 CASE_OP_32_64(orc): 320 return x | ~y; 321 322 CASE_OP_32_64(eqv): 323 return ~(x ^ y); 324 325 CASE_OP_32_64(nand): 326 return ~(x & y); 327 328 CASE_OP_32_64(nor): 329 return ~(x | y); 330 331 CASE_OP_32_64(ext8s): 332 return (int8_t)x; 333 334 CASE_OP_32_64(ext16s): 335 return (int16_t)x; 336 337 CASE_OP_32_64(ext8u): 338 return (uint8_t)x; 339 340 CASE_OP_32_64(ext16u): 341 return (uint16_t)x; 342 343 case INDEX_op_ext_i32_i64: 344 case INDEX_op_ext32s_i64: 345 return (int32_t)x; 346 347 case INDEX_op_extu_i32_i64: 348 case INDEX_op_extrl_i64_i32: 349 case INDEX_op_ext32u_i64: 350 return (uint32_t)x; 351 352 case INDEX_op_extrh_i64_i32: 353 return (uint64_t)x >> 32; 354 355 case INDEX_op_muluh_i32: 356 return ((uint64_t)(uint32_t)x * (uint32_t)y) >> 32; 357 case INDEX_op_mulsh_i32: 358 return ((int64_t)(int32_t)x * (int32_t)y) >> 32; 359 360 case INDEX_op_muluh_i64: 361 mulu64(&l64, &h64, x, y); 362 return h64; 363 case INDEX_op_mulsh_i64: 364 muls64(&l64, &h64, x, y); 365 return h64; 366 367 case INDEX_op_div_i32: 368 /* Avoid crashing on divide by zero, otherwise undefined. */ 369 return (int32_t)x / ((int32_t)y ? : 1); 370 case INDEX_op_divu_i32: 371 return (uint32_t)x / ((uint32_t)y ? : 1); 372 case INDEX_op_div_i64: 373 return (int64_t)x / ((int64_t)y ? : 1); 374 case INDEX_op_divu_i64: 375 return (uint64_t)x / ((uint64_t)y ? : 1); 376 377 case INDEX_op_rem_i32: 378 return (int32_t)x % ((int32_t)y ? : 1); 379 case INDEX_op_remu_i32: 380 return (uint32_t)x % ((uint32_t)y ? : 1); 381 case INDEX_op_rem_i64: 382 return (int64_t)x % ((int64_t)y ? : 1); 383 case INDEX_op_remu_i64: 384 return (uint64_t)x % ((uint64_t)y ? : 1); 385 386 default: 387 fprintf(stderr, 388 "Unrecognized operation %d in do_constant_folding.\n", op); 389 tcg_abort(); 390 } 391 } 392 393 static TCGArg do_constant_folding(TCGOpcode op, TCGArg x, TCGArg y) 394 { 395 TCGArg res = do_constant_folding_2(op, x, y); 396 if (op_bits(op) == 32) { 397 res = (int32_t)res; 398 } 399 return res; 400 } 401 402 static bool do_constant_folding_cond_32(uint32_t x, uint32_t y, TCGCond c) 403 { 404 switch (c) { 405 case TCG_COND_EQ: 406 return x == y; 407 case TCG_COND_NE: 408 return x != y; 409 case TCG_COND_LT: 410 return (int32_t)x < (int32_t)y; 411 case TCG_COND_GE: 412 return (int32_t)x >= (int32_t)y; 413 case TCG_COND_LE: 414 return (int32_t)x <= (int32_t)y; 415 case TCG_COND_GT: 416 return (int32_t)x > (int32_t)y; 417 case TCG_COND_LTU: 418 return x < y; 419 case TCG_COND_GEU: 420 return x >= y; 421 case TCG_COND_LEU: 422 return x <= y; 423 case TCG_COND_GTU: 424 return x > y; 425 default: 426 tcg_abort(); 427 } 428 } 429 430 static bool do_constant_folding_cond_64(uint64_t x, uint64_t y, TCGCond c) 431 { 432 switch (c) { 433 case TCG_COND_EQ: 434 return x == y; 435 case TCG_COND_NE: 436 return x != y; 437 case TCG_COND_LT: 438 return (int64_t)x < (int64_t)y; 439 case TCG_COND_GE: 440 return (int64_t)x >= (int64_t)y; 441 case TCG_COND_LE: 442 return (int64_t)x <= (int64_t)y; 443 case TCG_COND_GT: 444 return (int64_t)x > (int64_t)y; 445 case TCG_COND_LTU: 446 return x < y; 447 case TCG_COND_GEU: 448 return x >= y; 449 case TCG_COND_LEU: 450 return x <= y; 451 case TCG_COND_GTU: 452 return x > y; 453 default: 454 tcg_abort(); 455 } 456 } 457 458 static bool do_constant_folding_cond_eq(TCGCond c) 459 { 460 switch (c) { 461 case TCG_COND_GT: 462 case TCG_COND_LTU: 463 case TCG_COND_LT: 464 case TCG_COND_GTU: 465 case TCG_COND_NE: 466 return 0; 467 case TCG_COND_GE: 468 case TCG_COND_GEU: 469 case TCG_COND_LE: 470 case TCG_COND_LEU: 471 case TCG_COND_EQ: 472 return 1; 473 default: 474 tcg_abort(); 475 } 476 } 477 478 /* Return 2 if the condition can't be simplified, and the result 479 of the condition (0 or 1) if it can */ 480 static TCGArg do_constant_folding_cond(TCGOpcode op, TCGArg x, 481 TCGArg y, TCGCond c) 482 { 483 if (temp_is_const(x) && temp_is_const(y)) { 484 switch (op_bits(op)) { 485 case 32: 486 return do_constant_folding_cond_32(temps[x].val, temps[y].val, c); 487 case 64: 488 return do_constant_folding_cond_64(temps[x].val, temps[y].val, c); 489 default: 490 tcg_abort(); 491 } 492 } else if (temps_are_copies(x, y)) { 493 return do_constant_folding_cond_eq(c); 494 } else if (temp_is_const(y) && temps[y].val == 0) { 495 switch (c) { 496 case TCG_COND_LTU: 497 return 0; 498 case TCG_COND_GEU: 499 return 1; 500 default: 501 return 2; 502 } 503 } else { 504 return 2; 505 } 506 } 507 508 /* Return 2 if the condition can't be simplified, and the result 509 of the condition (0 or 1) if it can */ 510 static TCGArg do_constant_folding_cond2(TCGArg *p1, TCGArg *p2, TCGCond c) 511 { 512 TCGArg al = p1[0], ah = p1[1]; 513 TCGArg bl = p2[0], bh = p2[1]; 514 515 if (temp_is_const(bl) && temp_is_const(bh)) { 516 uint64_t b = ((uint64_t)temps[bh].val << 32) | (uint32_t)temps[bl].val; 517 518 if (temp_is_const(al) && temp_is_const(ah)) { 519 uint64_t a; 520 a = ((uint64_t)temps[ah].val << 32) | (uint32_t)temps[al].val; 521 return do_constant_folding_cond_64(a, b, c); 522 } 523 if (b == 0) { 524 switch (c) { 525 case TCG_COND_LTU: 526 return 0; 527 case TCG_COND_GEU: 528 return 1; 529 default: 530 break; 531 } 532 } 533 } 534 if (temps_are_copies(al, bl) && temps_are_copies(ah, bh)) { 535 return do_constant_folding_cond_eq(c); 536 } 537 return 2; 538 } 539 540 static bool swap_commutative(TCGArg dest, TCGArg *p1, TCGArg *p2) 541 { 542 TCGArg a1 = *p1, a2 = *p2; 543 int sum = 0; 544 sum += temp_is_const(a1); 545 sum -= temp_is_const(a2); 546 547 /* Prefer the constant in second argument, and then the form 548 op a, a, b, which is better handled on non-RISC hosts. */ 549 if (sum > 0 || (sum == 0 && dest == a2)) { 550 *p1 = a2; 551 *p2 = a1; 552 return true; 553 } 554 return false; 555 } 556 557 static bool swap_commutative2(TCGArg *p1, TCGArg *p2) 558 { 559 int sum = 0; 560 sum += temp_is_const(p1[0]); 561 sum += temp_is_const(p1[1]); 562 sum -= temp_is_const(p2[0]); 563 sum -= temp_is_const(p2[1]); 564 if (sum > 0) { 565 TCGArg t; 566 t = p1[0], p1[0] = p2[0], p2[0] = t; 567 t = p1[1], p1[1] = p2[1], p2[1] = t; 568 return true; 569 } 570 return false; 571 } 572 573 /* Propagate constants and copies, fold constant expressions. */ 574 void tcg_optimize(TCGContext *s) 575 { 576 int oi, oi_next, nb_temps, nb_globals; 577 578 /* Array VALS has an element for each temp. 579 If this temp holds a constant then its value is kept in VALS' element. 580 If this temp is a copy of other ones then the other copies are 581 available through the doubly linked circular list. */ 582 583 nb_temps = s->nb_temps; 584 nb_globals = s->nb_globals; 585 reset_all_temps(nb_temps); 586 587 for (oi = s->gen_first_op_idx; oi >= 0; oi = oi_next) { 588 tcg_target_ulong mask, partmask, affected; 589 int nb_oargs, nb_iargs, i; 590 TCGArg tmp; 591 592 TCGOp * const op = &s->gen_op_buf[oi]; 593 TCGArg * const args = &s->gen_opparam_buf[op->args]; 594 TCGOpcode opc = op->opc; 595 const TCGOpDef *def = &tcg_op_defs[opc]; 596 597 oi_next = op->next; 598 599 /* Count the arguments, and initialize the temps that are 600 going to be used */ 601 if (opc == INDEX_op_call) { 602 nb_oargs = op->callo; 603 nb_iargs = op->calli; 604 for (i = 0; i < nb_oargs + nb_iargs; i++) { 605 tmp = args[i]; 606 if (tmp != TCG_CALL_DUMMY_ARG) { 607 init_temp_info(tmp); 608 } 609 } 610 } else { 611 nb_oargs = def->nb_oargs; 612 nb_iargs = def->nb_iargs; 613 for (i = 0; i < nb_oargs + nb_iargs; i++) { 614 init_temp_info(args[i]); 615 } 616 } 617 618 /* Do copy propagation */ 619 for (i = nb_oargs; i < nb_oargs + nb_iargs; i++) { 620 if (temp_is_copy(args[i])) { 621 args[i] = find_better_copy(s, args[i]); 622 } 623 } 624 625 /* For commutative operations make constant second argument */ 626 switch (opc) { 627 CASE_OP_32_64(add): 628 CASE_OP_32_64(mul): 629 CASE_OP_32_64(and): 630 CASE_OP_32_64(or): 631 CASE_OP_32_64(xor): 632 CASE_OP_32_64(eqv): 633 CASE_OP_32_64(nand): 634 CASE_OP_32_64(nor): 635 CASE_OP_32_64(muluh): 636 CASE_OP_32_64(mulsh): 637 swap_commutative(args[0], &args[1], &args[2]); 638 break; 639 CASE_OP_32_64(brcond): 640 if (swap_commutative(-1, &args[0], &args[1])) { 641 args[2] = tcg_swap_cond(args[2]); 642 } 643 break; 644 CASE_OP_32_64(setcond): 645 if (swap_commutative(args[0], &args[1], &args[2])) { 646 args[3] = tcg_swap_cond(args[3]); 647 } 648 break; 649 CASE_OP_32_64(movcond): 650 if (swap_commutative(-1, &args[1], &args[2])) { 651 args[5] = tcg_swap_cond(args[5]); 652 } 653 /* For movcond, we canonicalize the "false" input reg to match 654 the destination reg so that the tcg backend can implement 655 a "move if true" operation. */ 656 if (swap_commutative(args[0], &args[4], &args[3])) { 657 args[5] = tcg_invert_cond(args[5]); 658 } 659 break; 660 CASE_OP_32_64(add2): 661 swap_commutative(args[0], &args[2], &args[4]); 662 swap_commutative(args[1], &args[3], &args[5]); 663 break; 664 CASE_OP_32_64(mulu2): 665 CASE_OP_32_64(muls2): 666 swap_commutative(args[0], &args[2], &args[3]); 667 break; 668 case INDEX_op_brcond2_i32: 669 if (swap_commutative2(&args[0], &args[2])) { 670 args[4] = tcg_swap_cond(args[4]); 671 } 672 break; 673 case INDEX_op_setcond2_i32: 674 if (swap_commutative2(&args[1], &args[3])) { 675 args[5] = tcg_swap_cond(args[5]); 676 } 677 break; 678 default: 679 break; 680 } 681 682 /* Simplify expressions for "shift/rot r, 0, a => movi r, 0", 683 and "sub r, 0, a => neg r, a" case. */ 684 switch (opc) { 685 CASE_OP_32_64(shl): 686 CASE_OP_32_64(shr): 687 CASE_OP_32_64(sar): 688 CASE_OP_32_64(rotl): 689 CASE_OP_32_64(rotr): 690 if (temp_is_const(args[1]) && temps[args[1]].val == 0) { 691 tcg_opt_gen_movi(s, op, args, args[0], 0); 692 continue; 693 } 694 break; 695 CASE_OP_32_64(sub): 696 { 697 TCGOpcode neg_op; 698 bool have_neg; 699 700 if (temp_is_const(args[2])) { 701 /* Proceed with possible constant folding. */ 702 break; 703 } 704 if (opc == INDEX_op_sub_i32) { 705 neg_op = INDEX_op_neg_i32; 706 have_neg = TCG_TARGET_HAS_neg_i32; 707 } else { 708 neg_op = INDEX_op_neg_i64; 709 have_neg = TCG_TARGET_HAS_neg_i64; 710 } 711 if (!have_neg) { 712 break; 713 } 714 if (temp_is_const(args[1]) && temps[args[1]].val == 0) { 715 op->opc = neg_op; 716 reset_temp(args[0]); 717 args[1] = args[2]; 718 continue; 719 } 720 } 721 break; 722 CASE_OP_32_64(xor): 723 CASE_OP_32_64(nand): 724 if (!temp_is_const(args[1]) 725 && temp_is_const(args[2]) && temps[args[2]].val == -1) { 726 i = 1; 727 goto try_not; 728 } 729 break; 730 CASE_OP_32_64(nor): 731 if (!temp_is_const(args[1]) 732 && temp_is_const(args[2]) && temps[args[2]].val == 0) { 733 i = 1; 734 goto try_not; 735 } 736 break; 737 CASE_OP_32_64(andc): 738 if (!temp_is_const(args[2]) 739 && temp_is_const(args[1]) && temps[args[1]].val == -1) { 740 i = 2; 741 goto try_not; 742 } 743 break; 744 CASE_OP_32_64(orc): 745 CASE_OP_32_64(eqv): 746 if (!temp_is_const(args[2]) 747 && temp_is_const(args[1]) && temps[args[1]].val == 0) { 748 i = 2; 749 goto try_not; 750 } 751 break; 752 try_not: 753 { 754 TCGOpcode not_op; 755 bool have_not; 756 757 if (def->flags & TCG_OPF_64BIT) { 758 not_op = INDEX_op_not_i64; 759 have_not = TCG_TARGET_HAS_not_i64; 760 } else { 761 not_op = INDEX_op_not_i32; 762 have_not = TCG_TARGET_HAS_not_i32; 763 } 764 if (!have_not) { 765 break; 766 } 767 op->opc = not_op; 768 reset_temp(args[0]); 769 args[1] = args[i]; 770 continue; 771 } 772 default: 773 break; 774 } 775 776 /* Simplify expression for "op r, a, const => mov r, a" cases */ 777 switch (opc) { 778 CASE_OP_32_64(add): 779 CASE_OP_32_64(sub): 780 CASE_OP_32_64(shl): 781 CASE_OP_32_64(shr): 782 CASE_OP_32_64(sar): 783 CASE_OP_32_64(rotl): 784 CASE_OP_32_64(rotr): 785 CASE_OP_32_64(or): 786 CASE_OP_32_64(xor): 787 CASE_OP_32_64(andc): 788 if (!temp_is_const(args[1]) 789 && temp_is_const(args[2]) && temps[args[2]].val == 0) { 790 tcg_opt_gen_mov(s, op, args, args[0], args[1]); 791 continue; 792 } 793 break; 794 CASE_OP_32_64(and): 795 CASE_OP_32_64(orc): 796 CASE_OP_32_64(eqv): 797 if (!temp_is_const(args[1]) 798 && temp_is_const(args[2]) && temps[args[2]].val == -1) { 799 tcg_opt_gen_mov(s, op, args, args[0], args[1]); 800 continue; 801 } 802 break; 803 default: 804 break; 805 } 806 807 /* Simplify using known-zero bits. Currently only ops with a single 808 output argument is supported. */ 809 mask = -1; 810 affected = -1; 811 switch (opc) { 812 CASE_OP_32_64(ext8s): 813 if ((temps[args[1]].mask & 0x80) != 0) { 814 break; 815 } 816 CASE_OP_32_64(ext8u): 817 mask = 0xff; 818 goto and_const; 819 CASE_OP_32_64(ext16s): 820 if ((temps[args[1]].mask & 0x8000) != 0) { 821 break; 822 } 823 CASE_OP_32_64(ext16u): 824 mask = 0xffff; 825 goto and_const; 826 case INDEX_op_ext32s_i64: 827 if ((temps[args[1]].mask & 0x80000000) != 0) { 828 break; 829 } 830 case INDEX_op_ext32u_i64: 831 mask = 0xffffffffU; 832 goto and_const; 833 834 CASE_OP_32_64(and): 835 mask = temps[args[2]].mask; 836 if (temp_is_const(args[2])) { 837 and_const: 838 affected = temps[args[1]].mask & ~mask; 839 } 840 mask = temps[args[1]].mask & mask; 841 break; 842 843 case INDEX_op_ext_i32_i64: 844 if ((temps[args[1]].mask & 0x80000000) != 0) { 845 break; 846 } 847 case INDEX_op_extu_i32_i64: 848 /* We do not compute affected as it is a size changing op. */ 849 mask = (uint32_t)temps[args[1]].mask; 850 break; 851 852 CASE_OP_32_64(andc): 853 /* Known-zeros does not imply known-ones. Therefore unless 854 args[2] is constant, we can't infer anything from it. */ 855 if (temp_is_const(args[2])) { 856 mask = ~temps[args[2]].mask; 857 goto and_const; 858 } 859 /* But we certainly know nothing outside args[1] may be set. */ 860 mask = temps[args[1]].mask; 861 break; 862 863 case INDEX_op_sar_i32: 864 if (temp_is_const(args[2])) { 865 tmp = temps[args[2]].val & 31; 866 mask = (int32_t)temps[args[1]].mask >> tmp; 867 } 868 break; 869 case INDEX_op_sar_i64: 870 if (temp_is_const(args[2])) { 871 tmp = temps[args[2]].val & 63; 872 mask = (int64_t)temps[args[1]].mask >> tmp; 873 } 874 break; 875 876 case INDEX_op_shr_i32: 877 if (temp_is_const(args[2])) { 878 tmp = temps[args[2]].val & 31; 879 mask = (uint32_t)temps[args[1]].mask >> tmp; 880 } 881 break; 882 case INDEX_op_shr_i64: 883 if (temp_is_const(args[2])) { 884 tmp = temps[args[2]].val & 63; 885 mask = (uint64_t)temps[args[1]].mask >> tmp; 886 } 887 break; 888 889 case INDEX_op_extrl_i64_i32: 890 mask = (uint32_t)temps[args[1]].mask; 891 break; 892 case INDEX_op_extrh_i64_i32: 893 mask = (uint64_t)temps[args[1]].mask >> 32; 894 break; 895 896 CASE_OP_32_64(shl): 897 if (temp_is_const(args[2])) { 898 tmp = temps[args[2]].val & (TCG_TARGET_REG_BITS - 1); 899 mask = temps[args[1]].mask << tmp; 900 } 901 break; 902 903 CASE_OP_32_64(neg): 904 /* Set to 1 all bits to the left of the rightmost. */ 905 mask = -(temps[args[1]].mask & -temps[args[1]].mask); 906 break; 907 908 CASE_OP_32_64(deposit): 909 mask = deposit64(temps[args[1]].mask, args[3], args[4], 910 temps[args[2]].mask); 911 break; 912 913 CASE_OP_32_64(or): 914 CASE_OP_32_64(xor): 915 mask = temps[args[1]].mask | temps[args[2]].mask; 916 break; 917 918 CASE_OP_32_64(setcond): 919 case INDEX_op_setcond2_i32: 920 mask = 1; 921 break; 922 923 CASE_OP_32_64(movcond): 924 mask = temps[args[3]].mask | temps[args[4]].mask; 925 break; 926 927 CASE_OP_32_64(ld8u): 928 mask = 0xff; 929 break; 930 CASE_OP_32_64(ld16u): 931 mask = 0xffff; 932 break; 933 case INDEX_op_ld32u_i64: 934 mask = 0xffffffffu; 935 break; 936 937 CASE_OP_32_64(qemu_ld): 938 { 939 TCGMemOpIdx oi = args[nb_oargs + nb_iargs]; 940 TCGMemOp mop = get_memop(oi); 941 if (!(mop & MO_SIGN)) { 942 mask = (2ULL << ((8 << (mop & MO_SIZE)) - 1)) - 1; 943 } 944 } 945 break; 946 947 default: 948 break; 949 } 950 951 /* 32-bit ops generate 32-bit results. For the result is zero test 952 below, we can ignore high bits, but for further optimizations we 953 need to record that the high bits contain garbage. */ 954 partmask = mask; 955 if (!(def->flags & TCG_OPF_64BIT)) { 956 mask |= ~(tcg_target_ulong)0xffffffffu; 957 partmask &= 0xffffffffu; 958 affected &= 0xffffffffu; 959 } 960 961 if (partmask == 0) { 962 assert(nb_oargs == 1); 963 tcg_opt_gen_movi(s, op, args, args[0], 0); 964 continue; 965 } 966 if (affected == 0) { 967 assert(nb_oargs == 1); 968 tcg_opt_gen_mov(s, op, args, args[0], args[1]); 969 continue; 970 } 971 972 /* Simplify expression for "op r, a, 0 => movi r, 0" cases */ 973 switch (opc) { 974 CASE_OP_32_64(and): 975 CASE_OP_32_64(mul): 976 CASE_OP_32_64(muluh): 977 CASE_OP_32_64(mulsh): 978 if ((temp_is_const(args[2]) && temps[args[2]].val == 0)) { 979 tcg_opt_gen_movi(s, op, args, args[0], 0); 980 continue; 981 } 982 break; 983 default: 984 break; 985 } 986 987 /* Simplify expression for "op r, a, a => mov r, a" cases */ 988 switch (opc) { 989 CASE_OP_32_64(or): 990 CASE_OP_32_64(and): 991 if (temps_are_copies(args[1], args[2])) { 992 tcg_opt_gen_mov(s, op, args, args[0], args[1]); 993 continue; 994 } 995 break; 996 default: 997 break; 998 } 999 1000 /* Simplify expression for "op r, a, a => movi r, 0" cases */ 1001 switch (opc) { 1002 CASE_OP_32_64(andc): 1003 CASE_OP_32_64(sub): 1004 CASE_OP_32_64(xor): 1005 if (temps_are_copies(args[1], args[2])) { 1006 tcg_opt_gen_movi(s, op, args, args[0], 0); 1007 continue; 1008 } 1009 break; 1010 default: 1011 break; 1012 } 1013 1014 /* Propagate constants through copy operations and do constant 1015 folding. Constants will be substituted to arguments by register 1016 allocator where needed and possible. Also detect copies. */ 1017 switch (opc) { 1018 CASE_OP_32_64(mov): 1019 tcg_opt_gen_mov(s, op, args, args[0], args[1]); 1020 break; 1021 CASE_OP_32_64(movi): 1022 tcg_opt_gen_movi(s, op, args, args[0], args[1]); 1023 break; 1024 1025 CASE_OP_32_64(not): 1026 CASE_OP_32_64(neg): 1027 CASE_OP_32_64(ext8s): 1028 CASE_OP_32_64(ext8u): 1029 CASE_OP_32_64(ext16s): 1030 CASE_OP_32_64(ext16u): 1031 case INDEX_op_ext32s_i64: 1032 case INDEX_op_ext32u_i64: 1033 case INDEX_op_ext_i32_i64: 1034 case INDEX_op_extu_i32_i64: 1035 case INDEX_op_extrl_i64_i32: 1036 case INDEX_op_extrh_i64_i32: 1037 if (temp_is_const(args[1])) { 1038 tmp = do_constant_folding(opc, temps[args[1]].val, 0); 1039 tcg_opt_gen_movi(s, op, args, args[0], tmp); 1040 break; 1041 } 1042 goto do_default; 1043 1044 CASE_OP_32_64(add): 1045 CASE_OP_32_64(sub): 1046 CASE_OP_32_64(mul): 1047 CASE_OP_32_64(or): 1048 CASE_OP_32_64(and): 1049 CASE_OP_32_64(xor): 1050 CASE_OP_32_64(shl): 1051 CASE_OP_32_64(shr): 1052 CASE_OP_32_64(sar): 1053 CASE_OP_32_64(rotl): 1054 CASE_OP_32_64(rotr): 1055 CASE_OP_32_64(andc): 1056 CASE_OP_32_64(orc): 1057 CASE_OP_32_64(eqv): 1058 CASE_OP_32_64(nand): 1059 CASE_OP_32_64(nor): 1060 CASE_OP_32_64(muluh): 1061 CASE_OP_32_64(mulsh): 1062 CASE_OP_32_64(div): 1063 CASE_OP_32_64(divu): 1064 CASE_OP_32_64(rem): 1065 CASE_OP_32_64(remu): 1066 if (temp_is_const(args[1]) && temp_is_const(args[2])) { 1067 tmp = do_constant_folding(opc, temps[args[1]].val, 1068 temps[args[2]].val); 1069 tcg_opt_gen_movi(s, op, args, args[0], tmp); 1070 break; 1071 } 1072 goto do_default; 1073 1074 CASE_OP_32_64(deposit): 1075 if (temp_is_const(args[1]) && temp_is_const(args[2])) { 1076 tmp = deposit64(temps[args[1]].val, args[3], args[4], 1077 temps[args[2]].val); 1078 tcg_opt_gen_movi(s, op, args, args[0], tmp); 1079 break; 1080 } 1081 goto do_default; 1082 1083 CASE_OP_32_64(setcond): 1084 tmp = do_constant_folding_cond(opc, args[1], args[2], args[3]); 1085 if (tmp != 2) { 1086 tcg_opt_gen_movi(s, op, args, args[0], tmp); 1087 break; 1088 } 1089 goto do_default; 1090 1091 CASE_OP_32_64(brcond): 1092 tmp = do_constant_folding_cond(opc, args[0], args[1], args[2]); 1093 if (tmp != 2) { 1094 if (tmp) { 1095 reset_all_temps(nb_temps); 1096 op->opc = INDEX_op_br; 1097 args[0] = args[3]; 1098 } else { 1099 tcg_op_remove(s, op); 1100 } 1101 break; 1102 } 1103 goto do_default; 1104 1105 CASE_OP_32_64(movcond): 1106 tmp = do_constant_folding_cond(opc, args[1], args[2], args[5]); 1107 if (tmp != 2) { 1108 tcg_opt_gen_mov(s, op, args, args[0], args[4-tmp]); 1109 break; 1110 } 1111 goto do_default; 1112 1113 case INDEX_op_add2_i32: 1114 case INDEX_op_sub2_i32: 1115 if (temp_is_const(args[2]) && temp_is_const(args[3]) 1116 && temp_is_const(args[4]) && temp_is_const(args[5])) { 1117 uint32_t al = temps[args[2]].val; 1118 uint32_t ah = temps[args[3]].val; 1119 uint32_t bl = temps[args[4]].val; 1120 uint32_t bh = temps[args[5]].val; 1121 uint64_t a = ((uint64_t)ah << 32) | al; 1122 uint64_t b = ((uint64_t)bh << 32) | bl; 1123 TCGArg rl, rh; 1124 TCGOp *op2 = insert_op_before(s, op, INDEX_op_movi_i32, 2); 1125 TCGArg *args2 = &s->gen_opparam_buf[op2->args]; 1126 1127 if (opc == INDEX_op_add2_i32) { 1128 a += b; 1129 } else { 1130 a -= b; 1131 } 1132 1133 rl = args[0]; 1134 rh = args[1]; 1135 tcg_opt_gen_movi(s, op, args, rl, (int32_t)a); 1136 tcg_opt_gen_movi(s, op2, args2, rh, (int32_t)(a >> 32)); 1137 1138 /* We've done all we need to do with the movi. Skip it. */ 1139 oi_next = op2->next; 1140 break; 1141 } 1142 goto do_default; 1143 1144 case INDEX_op_mulu2_i32: 1145 if (temp_is_const(args[2]) && temp_is_const(args[3])) { 1146 uint32_t a = temps[args[2]].val; 1147 uint32_t b = temps[args[3]].val; 1148 uint64_t r = (uint64_t)a * b; 1149 TCGArg rl, rh; 1150 TCGOp *op2 = insert_op_before(s, op, INDEX_op_movi_i32, 2); 1151 TCGArg *args2 = &s->gen_opparam_buf[op2->args]; 1152 1153 rl = args[0]; 1154 rh = args[1]; 1155 tcg_opt_gen_movi(s, op, args, rl, (int32_t)r); 1156 tcg_opt_gen_movi(s, op2, args2, rh, (int32_t)(r >> 32)); 1157 1158 /* We've done all we need to do with the movi. Skip it. */ 1159 oi_next = op2->next; 1160 break; 1161 } 1162 goto do_default; 1163 1164 case INDEX_op_brcond2_i32: 1165 tmp = do_constant_folding_cond2(&args[0], &args[2], args[4]); 1166 if (tmp != 2) { 1167 if (tmp) { 1168 do_brcond_true: 1169 reset_all_temps(nb_temps); 1170 op->opc = INDEX_op_br; 1171 args[0] = args[5]; 1172 } else { 1173 do_brcond_false: 1174 tcg_op_remove(s, op); 1175 } 1176 } else if ((args[4] == TCG_COND_LT || args[4] == TCG_COND_GE) 1177 && temp_is_const(args[2]) && temps[args[2]].val == 0 1178 && temp_is_const(args[3]) && temps[args[3]].val == 0) { 1179 /* Simplify LT/GE comparisons vs zero to a single compare 1180 vs the high word of the input. */ 1181 do_brcond_high: 1182 reset_all_temps(nb_temps); 1183 op->opc = INDEX_op_brcond_i32; 1184 args[0] = args[1]; 1185 args[1] = args[3]; 1186 args[2] = args[4]; 1187 args[3] = args[5]; 1188 } else if (args[4] == TCG_COND_EQ) { 1189 /* Simplify EQ comparisons where one of the pairs 1190 can be simplified. */ 1191 tmp = do_constant_folding_cond(INDEX_op_brcond_i32, 1192 args[0], args[2], TCG_COND_EQ); 1193 if (tmp == 0) { 1194 goto do_brcond_false; 1195 } else if (tmp == 1) { 1196 goto do_brcond_high; 1197 } 1198 tmp = do_constant_folding_cond(INDEX_op_brcond_i32, 1199 args[1], args[3], TCG_COND_EQ); 1200 if (tmp == 0) { 1201 goto do_brcond_false; 1202 } else if (tmp != 1) { 1203 goto do_default; 1204 } 1205 do_brcond_low: 1206 reset_all_temps(nb_temps); 1207 op->opc = INDEX_op_brcond_i32; 1208 args[1] = args[2]; 1209 args[2] = args[4]; 1210 args[3] = args[5]; 1211 } else if (args[4] == TCG_COND_NE) { 1212 /* Simplify NE comparisons where one of the pairs 1213 can be simplified. */ 1214 tmp = do_constant_folding_cond(INDEX_op_brcond_i32, 1215 args[0], args[2], TCG_COND_NE); 1216 if (tmp == 0) { 1217 goto do_brcond_high; 1218 } else if (tmp == 1) { 1219 goto do_brcond_true; 1220 } 1221 tmp = do_constant_folding_cond(INDEX_op_brcond_i32, 1222 args[1], args[3], TCG_COND_NE); 1223 if (tmp == 0) { 1224 goto do_brcond_low; 1225 } else if (tmp == 1) { 1226 goto do_brcond_true; 1227 } 1228 goto do_default; 1229 } else { 1230 goto do_default; 1231 } 1232 break; 1233 1234 case INDEX_op_setcond2_i32: 1235 tmp = do_constant_folding_cond2(&args[1], &args[3], args[5]); 1236 if (tmp != 2) { 1237 do_setcond_const: 1238 tcg_opt_gen_movi(s, op, args, args[0], tmp); 1239 } else if ((args[5] == TCG_COND_LT || args[5] == TCG_COND_GE) 1240 && temp_is_const(args[3]) && temps[args[3]].val == 0 1241 && temp_is_const(args[4]) && temps[args[4]].val == 0) { 1242 /* Simplify LT/GE comparisons vs zero to a single compare 1243 vs the high word of the input. */ 1244 do_setcond_high: 1245 reset_temp(args[0]); 1246 temps[args[0]].mask = 1; 1247 op->opc = INDEX_op_setcond_i32; 1248 args[1] = args[2]; 1249 args[2] = args[4]; 1250 args[3] = args[5]; 1251 } else if (args[5] == TCG_COND_EQ) { 1252 /* Simplify EQ comparisons where one of the pairs 1253 can be simplified. */ 1254 tmp = do_constant_folding_cond(INDEX_op_setcond_i32, 1255 args[1], args[3], TCG_COND_EQ); 1256 if (tmp == 0) { 1257 goto do_setcond_const; 1258 } else if (tmp == 1) { 1259 goto do_setcond_high; 1260 } 1261 tmp = do_constant_folding_cond(INDEX_op_setcond_i32, 1262 args[2], args[4], TCG_COND_EQ); 1263 if (tmp == 0) { 1264 goto do_setcond_high; 1265 } else if (tmp != 1) { 1266 goto do_default; 1267 } 1268 do_setcond_low: 1269 reset_temp(args[0]); 1270 temps[args[0]].mask = 1; 1271 op->opc = INDEX_op_setcond_i32; 1272 args[2] = args[3]; 1273 args[3] = args[5]; 1274 } else if (args[5] == TCG_COND_NE) { 1275 /* Simplify NE comparisons where one of the pairs 1276 can be simplified. */ 1277 tmp = do_constant_folding_cond(INDEX_op_setcond_i32, 1278 args[1], args[3], TCG_COND_NE); 1279 if (tmp == 0) { 1280 goto do_setcond_high; 1281 } else if (tmp == 1) { 1282 goto do_setcond_const; 1283 } 1284 tmp = do_constant_folding_cond(INDEX_op_setcond_i32, 1285 args[2], args[4], TCG_COND_NE); 1286 if (tmp == 0) { 1287 goto do_setcond_low; 1288 } else if (tmp == 1) { 1289 goto do_setcond_const; 1290 } 1291 goto do_default; 1292 } else { 1293 goto do_default; 1294 } 1295 break; 1296 1297 case INDEX_op_call: 1298 if (!(args[nb_oargs + nb_iargs + 1] 1299 & (TCG_CALL_NO_READ_GLOBALS | TCG_CALL_NO_WRITE_GLOBALS))) { 1300 for (i = 0; i < nb_globals; i++) { 1301 if (test_bit(i, temps_used.l)) { 1302 reset_temp(i); 1303 } 1304 } 1305 } 1306 goto do_reset_output; 1307 1308 default: 1309 do_default: 1310 /* Default case: we know nothing about operation (or were unable 1311 to compute the operation result) so no propagation is done. 1312 We trash everything if the operation is the end of a basic 1313 block, otherwise we only trash the output args. "mask" is 1314 the non-zero bits mask for the first output arg. */ 1315 if (def->flags & TCG_OPF_BB_END) { 1316 reset_all_temps(nb_temps); 1317 } else { 1318 do_reset_output: 1319 for (i = 0; i < nb_oargs; i++) { 1320 reset_temp(args[i]); 1321 /* Save the corresponding known-zero bits mask for the 1322 first output argument (only one supported so far). */ 1323 if (i == 0) { 1324 temps[args[i]].mask = mask; 1325 } 1326 } 1327 } 1328 break; 1329 } 1330 } 1331 } 1332