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