simplify.c

   1 /*
   2  * Simplify - do instruction simplification before CSE
   3  *
   4  * Copyright (C) 2004 Linus Torvalds
   5  */
   6
   7 #include <assert.h>
   8
   9 #include "parse.h"
  10 #include "expression.h"
  11 #include "linearize.h"
  12 #include "flow.h"
  13
  14 /* Find the trivial parent for a phi-source */
  15 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
  16 {
  17         /* Can't go upwards if the pseudo is defined in the bb it came from.. */
  18         if (pseudo->type == PSEUDO_REG) {
  19                 struct instruction *def = pseudo->def;
  20                 if (def->bb == source)
  21                         return source;
  22         }
  23         if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
  24                 return source;
  25         return first_basic_block(source->parents);
  26 }
  27
  28 static void clear_phi(struct instruction *insn)
  29 {
  30         pseudo_t phi;
  31
  32         insn->bb = NULL;
  33         FOR_EACH_PTR(insn->phi_list, phi) {
  34                 *THIS_ADDRESS(phi) = VOID;
  35         } END_FOR_EACH_PTR(phi);
  36 }
  37
  38 static int if_convert_phi(struct instruction *insn)
  39 {
  40         pseudo_t array[3];
  41         struct basic_block *parents[3];
  42         struct basic_block *bb, *bb1, *bb2, *source;
  43         struct instruction *br;
  44         pseudo_t p1, p2;
  45
  46         bb = insn->bb;
  47         if (linearize_ptr_list((struct ptr_list *)insn->phi_list, (void **)array, 3) != 2)
  48                 return 0;
  49         if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
  50                 return 0;
  51         p1 = array[0]->def->src1;
  52         bb1 = array[0]->def->bb;
  53         p2 = array[1]->def->src1;
  54         bb2 = array[1]->def->bb;
  55
  56         /* Only try the simple "direct parents" case */
  57         if ((bb1 != parents[0] || bb2 != parents[1]) &&
  58             (bb1 != parents[1] || bb2 != parents[0]))
  59                 return 0;
  60
  61         /*
  62          * See if we can find a common source for this..
  63          */
  64         source = phi_parent(bb1, p1);
  65         if (source != phi_parent(bb2, p2))
  66                 return 0;
  67
  68         /*
  69          * Cool. We now know that 'source' is the exclusive
  70          * parent of both phi-nodes, so the exit at the
  71          * end of it fully determines which one it is, and
  72          * we can turn it into a select.
  73          *
  74          * HOWEVER, right now we only handle regular
  75          * conditional branches. No multijumps or computed
  76          * stuff. Verify that here.
  77          */
  78         br = last_instruction(source->insns);
  79         if (!br || br->opcode != OP_BR)
  80                 return 0;
  81
  82         assert(br->cond);
  83         assert(br->bb_false);
  84
  85         /*
  86          * We're in business. Match up true/false with p1/p2.
  87          */
  88         if (br->bb_true == bb2 || br->bb_false == bb1) {
  89                 pseudo_t p = p1;
  90                 p1 = p2;
  91                 p2 = p;
  92         }
  93
  94         /*
  95          * Ok, we can now replace that last
  96          *
  97          *      br cond, a, b
  98          *
  99          * with the sequence
 100          *
 101          *      setcc cond
 102          *      select pseudo, p1, p2
 103          *      br cond, a, b
 104          *
 105          * and remove the phi-node. If it then
 106          * turns out that 'a' or 'b' is entirely
 107          * empty (common case), and now no longer
 108          * a phi-source, we'll be able to simplify
 109          * the conditional branch too.
 110          */
 111         insert_select(source, br, insn, p1, p2);
 112         clear_phi(insn);
 113         return REPEAT_CSE;
 114 }
 115
 116 static int clean_up_phi(struct instruction *insn)
 117 {
 118         pseudo_t phi;
 119         struct instruction *last;
 120         int same;
 121
 122         last = NULL;
 123         same = 1;
 124         FOR_EACH_PTR(insn->phi_list, phi) {
 125                 struct instruction *def;
 126                 if (phi == VOID)
 127                         continue;
 128                 def = phi->def;
 129                 if (def->src1 == VOID || !def->bb)
 130                         continue;
 131                 if (last) {
 132                         if (last->src1 != def->src1)
 133                                 same = 0;
 134                         continue;
 135                 }
 136                 last = def;
 137         } END_FOR_EACH_PTR(phi);
 138
 139         if (same) {
 140                 pseudo_t pseudo = last ? last->src1 : VOID;
 141                 convert_instruction_target(insn, pseudo);
 142                 clear_phi(insn);
 143                 return REPEAT_CSE;
 144         }
 145
 146         return if_convert_phi(insn);
 147 }
 148
 149 static inline void remove_usage(pseudo_t p, pseudo_t *usep)
 150 {
 151         if (has_use_list(p)) {
 152                 delete_ptr_list_entry((struct ptr_list **)&p->users, usep, 1);
 153                 if (!p->users)
 154                         kill_instruction(p->def);
 155         }
 156 }
 157
 158 void kill_use(pseudo_t *usep)
 159 {
 160         if (usep) {
 161                 pseudo_t p = *usep;
 162                 *usep = VOID;
 163                 remove_usage(p, usep);
 164         }
 165 }
 166
 167 void kill_instruction(struct instruction *insn)
 168 {
 169         if (!insn || !insn->bb)
 170                 return;
 171
 172         switch (insn->opcode) {
 173         case OP_BINARY ... OP_BINCMP_END:
 174                 insn->bb = NULL;
 175                 kill_use(&insn->src1);
 176                 kill_use(&insn->src2);
 177                 repeat_phase |= REPEAT_CSE;
 178                 return;
 179
 180         case OP_NOT: case OP_NEG:
 181                 insn->bb = NULL;
 182                 kill_use(&insn->src1);
 183                 repeat_phase |= REPEAT_CSE;
 184                 return;
 185
 186         case OP_PHI:
 187                 insn->bb = NULL;
 188                 repeat_phase |= REPEAT_CSE;
 189                 return;
 190
 191          case OP_SETVAL:
 192                 insn->bb = NULL;
 193                 repeat_phase |= REPEAT_CSE;
 194                 if (insn->symbol)
 195                         repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 196                 return;
 197         }
 198 }
 199
 200 /*
 201  * Kill trivially dead instructions
 202  */
 203 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2)
 204 {
 205         pseudo_t *usep;
 206         FOR_EACH_PTR(insn->target->users, usep) {
 207                 if (*usep != VOID)
 208                         return 0;
 209         } END_FOR_EACH_PTR(usep);
 210
 211         insn->bb = NULL;
 212         kill_use(src1);
 213         kill_use(src2);
 214         return REPEAT_CSE;
 215 }
 216
 217 static inline int constant(pseudo_t pseudo)
 218 {
 219         return pseudo->type == PSEUDO_VAL;
 220 }
 221
 222 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 223 {
 224         convert_instruction_target(insn, pseudo);
 225         insn->bb = NULL;
 226         return REPEAT_CSE;
 227 }
 228
 229 static int simplify_constant_rightside(struct instruction *insn)
 230 {
 231         long long value = insn->src2->value;
 232
 233         switch (insn->opcode) {
 234         case OP_SUB:
 235                 if (value) {
 236                         insn->opcode = OP_ADD;
 237                         insn->src2 = value_pseudo(-value);
 238                         return REPEAT_CSE;
 239                 }
 240         /* Fallthrough */
 241         case OP_ADD:
 242         case OP_OR: case OP_XOR:
 243         case OP_SHL: case OP_SHR:
 244                 if (!value)
 245                         return replace_with_pseudo(insn, insn->src1);
 246                 return 0;
 247
 248         case OP_AND: case OP_MUL:
 249                 if (!value)
 250                         return replace_with_pseudo(insn, insn->src2);
 251                 return 0;
 252         }
 253         return 0;
 254 }
 255
 256 static int simplify_constant_leftside(struct instruction *insn)
 257 {
 258         long long value = insn->src1->value;
 259
 260         switch (insn->opcode) {
 261         case OP_ADD: case OP_OR: case OP_XOR:
 262                 if (!value)
 263                         return replace_with_pseudo(insn, insn->src2);
 264                 return 0;
 265
 266         case OP_SHL: case OP_SHR:
 267         case OP_AND: case OP_MUL:
 268                 if (!value)
 269                         return replace_with_pseudo(insn, insn->src1);
 270                 return 0;
 271         }
 272         return 0;
 273 }
 274
 275 static int simplify_constant_binop(struct instruction *insn)
 276 {
 277         /* FIXME! Verify signs and sizes!! */
 278         long long left = insn->src1->value;
 279         long long right = insn->src2->value;
 280         long long res, mask;
 281
 282         switch (insn->opcode) {
 283         case OP_ADD:
 284                 res = left + right;
 285                 break;
 286         case OP_SUB:
 287                 res = left - right;
 288                 break;
 289         case OP_MUL:
 290                 /* FIXME! Check sign! */
 291                 res = left * right;
 292                 break;
 293         case OP_DIV:
 294                 if (!right)
 295                         return 0;
 296                 /* FIXME! Check sign! */
 297                 res = left / right;
 298                 break;
 299         case OP_MOD:
 300                 if (!right)
 301                         return 0;
 302                 /* FIXME! Check sign! */
 303                 res = left % right;
 304                 break;
 305         case OP_SHL:
 306                 res = left << right;
 307                 break;
 308         case OP_SHR:
 309                 /* FIXME! Check sign! */
 310                 res = left >> right;
 311                 break;
 312        /* Logical */
 313         case OP_AND:
 314                 res = left & right;
 315                 break;
 316         case OP_OR:
 317                 res = left | right;
 318                 break;
 319         case OP_XOR:
 320                 res = left ^ right;
 321                 break;
 322         case OP_AND_BOOL:
 323                 res = left && right;
 324                 break;
 325         case OP_OR_BOOL:
 326                 res = left || right;
 327                 break;
 328
 329         /* Binary comparison */
 330         case OP_SET_EQ:
 331                 res = left == right;
 332                 break;
 333         case OP_SET_NE:
 334                 res = left != right;
 335                 break;
 336         case OP_SET_LE:
 337                 /* FIXME! Check sign! */
 338                 res = left <= right;
 339                 break;
 340         case OP_SET_GE:
 341                 /* FIXME! Check sign! */
 342                 res = left >= right;
 343                 break;
 344         case OP_SET_LT:
 345                 /* FIXME! Check sign! */
 346                 res = left < right;
 347                 break;
 348         case OP_SET_GT:
 349                 /* FIXME! Check sign! */
 350                 res = left > right;
 351                 break;
 352         case OP_SET_B:
 353                 /* FIXME! Check sign! */
 354                 res = (unsigned long long) left < (unsigned long long) right;
 355                 break;
 356         case OP_SET_A:
 357                 /* FIXME! Check sign! */
 358                 res = (unsigned long long) left > (unsigned long long) right;
 359                 break;
 360         case OP_SET_BE:
 361                 /* FIXME! Check sign! */
 362                 res = (unsigned long long) left <= (unsigned long long) right;
 363                 break;
 364         case OP_SET_AE:
 365                 /* FIXME! Check sign! */
 366                 res = (unsigned long long) left >= (unsigned long long) right;
 367                 break;
 368         default:
 369                 return 0;
 370         }
 371         mask = 1ULL << (insn->size-1);
 372         res &= mask | (mask-1);
 373
 374         /* FIXME!! Sign??? */
 375         replace_with_pseudo(insn, value_pseudo(res));
 376         return REPEAT_CSE;
 377 }
 378
 379 static int simplify_binop(struct instruction *insn)
 380 {
 381         if (dead_insn(insn, &insn->src1, &insn->src2))
 382                 return REPEAT_CSE;
 383         if (constant(insn->src1)) {
 384                 if (constant(insn->src2))
 385                         return simplify_constant_binop(insn);
 386                 return simplify_constant_leftside(insn);
 387         }
 388         if (constant(insn->src2))
 389                 return simplify_constant_rightside(insn);
 390         return 0;
 391 }
 392
 393 static int simplify_constant_unop(struct instruction *insn)
 394 {
 395         return 0;
 396 }
 397
 398 static int simplify_unop(struct instruction *insn)
 399 {
 400         if (dead_insn(insn, &insn->src1, NULL))
 401                 return REPEAT_CSE;
 402         if (constant(insn->src1))
 403                 return simplify_constant_unop(insn);
 404         return 0;
 405 }
 406
 407 static int simplify_memop(struct instruction *insn)
 408 {
 409         pseudo_t addr = insn->src;
 410         pseudo_t new, off;
 411
 412         if (addr->type == PSEUDO_REG) {
 413                 struct instruction *def = addr->def;
 414                 if (def->opcode == OP_SETVAL && def->src) {
 415                         kill_use(&insn->src);
 416                         use_pseudo(def->src, &insn->src);
 417                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 418                 }
 419                 if (def->opcode == OP_ADD) {
 420                         new = def->src1;
 421                         off = def->src2;
 422                         if (constant(off))
 423                                 goto offset;
 424                         new = off;
 425                         off = def->src1;
 426                         if (constant(off))
 427                                 goto offset;
 428                         return 0;
 429                 }
 430         }
 431         return 0;
 432
 433 offset:
 434         /* Invalid code */
 435         if (new == addr) {
 436                 if (new == VOID)
 437                         return 0;
 438                 new = VOID;
 439                 warning(insn->bb->pos, "crazy programmer");
 440         }
 441         insn->offset += off->value;
 442         use_pseudo(new, &insn->src);
 443         remove_usage(addr, &insn->src);
 444         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 445 }
 446
 447 static int simplify_cast(struct instruction *insn)
 448 {
 449         int orig_size;
 450
 451         if (dead_insn(insn, &insn->src, NULL))
 452                 return REPEAT_CSE;
 453         if (insn->opcode == OP_PTRCAST)
 454                 return 0;
 455         orig_size = insn->orig_type ? insn->orig_type->bit_size : 0;
 456         if (orig_size < 0)
 457                 orig_size = 0;
 458         if (insn->size != orig_size)
 459                 return 0;
 460         return replace_with_pseudo(insn, insn->src);
 461 }
 462
 463 static int simplify_select(struct instruction *insn, struct instruction *setcc)
 464 {
 465         pseudo_t cond, src1, src2;
 466
 467         assert(setcc && setcc->bb);
 468         if (dead_insn(insn, &insn->src1, &insn->src2)) {
 469                 setcc->bb = NULL;
 470                 return REPEAT_CSE;
 471         }
 472         cond = setcc->src;
 473         src1 = insn->src1;
 474         src2 = insn->src2;
 475         if (constant(cond) || src1 == src2) {
 476                 setcc->bb = NULL;
 477                 kill_use(&setcc->cond);
 478                 replace_with_pseudo(insn, cond->value ? src1 : src2);
 479                 return REPEAT_CSE;
 480         }
 481         if (constant(src1) && constant(src2)) {
 482                 long long val1 = src1->value;
 483                 long long val2 = src2->value;
 484
 485                 /* The pair 0/1 is special - replace with SETNE/SETEQ */
 486                 if ((val1 | val2) == 1) {
 487                         int opcode = OP_SET_EQ;
 488                         if (val1) {
 489                                 src1 = src2;
 490                                 opcode = OP_SET_NE;
 491                         }
 492                         insn->opcode = opcode;
 493                         insn->src2 = src1; /* Zero */
 494                         use_pseudo(cond, &insn->src1);
 495                         setcc->bb = NULL;
 496                         kill_use(&setcc->cond);
 497                         return REPEAT_CSE;
 498                 }
 499         }
 500         return 0;
 501 }
 502
 503 /*
 504  * Simplify "set_ne/eq $0 + br"
 505  */
 506 static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
 507 {
 508         use_pseudo(*pp, &br->cond);
 509         remove_usage(cond, &br->cond);
 510         if (def->opcode == OP_SET_EQ) {
 511                 struct basic_block *true = br->bb_true;
 512                 struct basic_block *false = br->bb_false;
 513                 br->bb_false = true;
 514                 br->bb_true = false;
 515         }
 516         return REPEAT_CSE;
 517 }
 518
 519 static int simplify_branch(struct instruction *insn)
 520 {
 521         pseudo_t cond = insn->cond;
 522
 523         if (!cond)
 524                 return 0;
 525
 526         /* Constant conditional */
 527         if (constant(cond)) {
 528                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
 529                 return REPEAT_CSE;
 530         }
 531
 532         /* Conditional on a SETNE $0 or SETEQ $0 */
 533         if (cond->type == PSEUDO_REG) {
 534                 struct instruction *def = cond->def;
 535
 536                 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
 537                         if (constant(def->src1) && !def->src1->value)
 538                                 return simplify_cond_branch(insn, cond, def, &def->src2);
 539                         if (constant(def->src2) && !def->src2->value)
 540                                 return simplify_cond_branch(insn, cond, def, &def->src1);
 541                 }
 542         }
 543         return 0;
 544 }
 545
 546 static int simplify_switch(struct instruction *insn)
 547 {
 548         pseudo_t cond = insn->cond;
 549         long long val;
 550         struct multijmp *jmp;
 551
 552         if (!constant(cond))
 553                 return 0;
 554         val = insn->cond->value;
 555
 556         FOR_EACH_PTR(insn->multijmp_list, jmp) {
 557                 /* Default case */
 558                 if (jmp->begin > jmp->end)
 559                         goto found;
 560                 if (val >= jmp->begin && val <= jmp->end)
 561                         goto found;
 562         } END_FOR_EACH_PTR(jmp);
 563         warning(insn->bb->pos, "Impossible case statement");
 564         return 0;
 565
 566 found:
 567         insert_branch(insn->bb, insn, jmp->target);
 568         return REPEAT_CSE;
 569 }
 570
 571 int simplify_instruction(struct instruction *insn)
 572 {
 573         static struct instruction *last_setcc;
 574         struct instruction *setcc = last_setcc;
 575
 576         last_setcc = NULL;
 577
 578         if (!insn->bb)
 579                 return 0;
 580         switch (insn->opcode) {
 581         case OP_BINARY ... OP_BINCMP_END:
 582                 return simplify_binop(insn);
 583
 584         case OP_NOT: case OP_NEG:
 585                 return simplify_unop(insn);
 586         case OP_LOAD: case OP_STORE:
 587                 return simplify_memop(insn);
 588         case OP_SETVAL:
 589                 if (dead_insn(insn, NULL, NULL))
 590                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 591                 break;
 592         case OP_PTRCAST:
 593         case OP_CAST:
 594                 return simplify_cast(insn);
 595         case OP_PHI:
 596                 if (dead_insn(insn, NULL, NULL)) {
 597                         clear_phi(insn);
 598                         return REPEAT_CSE;
 599                 }
 600                 return clean_up_phi(insn);
 601         case OP_PHISOURCE:
 602                 if (dead_insn(insn, &insn->src1, NULL))
 603                         return REPEAT_CSE;
 604                 break;
 605         case OP_SETCC:
 606                 last_setcc = insn;
 607                 return 0;
 608         case OP_SEL:
 609                 return simplify_select(insn, setcc);
 610         case OP_BR:
 611                 return simplify_branch(insn);
 612         case OP_SWITCH:
 613                 return simplify_switch(insn);
 614         }
 615         return 0;
 616 }