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 (phi_parent(bb2, p2) != source)
  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                 int deleted;
 153                 deleted = delete_ptr_list_entry((struct ptr_list **)&p->users, usep);
 154                 assert(deleted == 1);
 155                 if (!p->users)
 156                         kill_instruction(p->def);
 157         }
 158 }
 159
 160 void kill_use(pseudo_t *usep)
 161 {
 162         if (usep) {
 163                 pseudo_t p = *usep;
 164                 *usep = VOID;
 165                 remove_usage(p, usep);
 166         }
 167 }
 168
 169 void kill_instruction(struct instruction *insn)
 170 {
 171         if (!insn || !insn->bb)
 172                 return;
 173
 174         switch (insn->opcode) {
 175         case OP_BINARY ... OP_BINCMP_END:
 176                 insn->bb = NULL;
 177                 kill_use(&insn->src1);
 178                 kill_use(&insn->src2);
 179                 repeat_phase |= REPEAT_CSE;
 180                 return;
 181
 182         case OP_NOT: case OP_NEG:
 183                 insn->bb = NULL;
 184                 kill_use(&insn->src1);
 185                 repeat_phase |= REPEAT_CSE;
 186                 return;
 187
 188         case OP_PHI:
 189                 insn->bb = NULL;
 190                 repeat_phase |= REPEAT_CSE;
 191                 return;
 192
 193          case OP_SETVAL:
 194                 insn->bb = NULL;
 195                 repeat_phase |= REPEAT_CSE;
 196                 if (insn->symbol)
 197                         repeat_phase |= REPEAT_SYMBOL_CLEANUP;
 198                 return;
 199         }
 200 }
 201
 202 /*
 203  * Kill trivially dead instructions
 204  */
 205 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2)
 206 {
 207         pseudo_t *usep;
 208         FOR_EACH_PTR(insn->target->users, usep) {
 209                 if (*usep != VOID)
 210                         return 0;
 211         } END_FOR_EACH_PTR(usep);
 212
 213         insn->bb = NULL;
 214         kill_use(src1);
 215         kill_use(src2);
 216         return REPEAT_CSE;
 217 }
 218
 219 static inline int constant(pseudo_t pseudo)
 220 {
 221         return pseudo->type == PSEUDO_VAL;
 222 }
 223
 224 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 225 {
 226         convert_instruction_target(insn, pseudo);
 227         insn->bb = NULL;
 228         return REPEAT_CSE;
 229 }
 230
 231 static int simplify_constant_rightside(struct instruction *insn)
 232 {
 233         long long value = insn->src2->value;
 234
 235         switch (insn->opcode) {
 236         case OP_ADD: case OP_SUB:
 237         case OP_OR: case OP_XOR:
 238         case OP_SHL: case OP_SHR:
 239                 if (!value)
 240                         return replace_with_pseudo(insn, insn->src1);
 241                 return 0;
 242
 243         case OP_AND: case OP_MUL:
 244                 if (!value)
 245                         return replace_with_pseudo(insn, insn->src2);
 246                 return 0;
 247         }
 248         return 0;
 249 }
 250
 251 static int simplify_constant_leftside(struct instruction *insn)
 252 {
 253         long long value = insn->src1->value;
 254
 255         switch (insn->opcode) {
 256         case OP_ADD: case OP_OR: case OP_XOR:
 257                 if (!value)
 258                         return replace_with_pseudo(insn, insn->src2);
 259                 return 0;
 260
 261         case OP_SHL: case OP_SHR:
 262         case OP_AND: case OP_MUL:
 263                 if (!value)
 264                         return replace_with_pseudo(insn, insn->src1);
 265                 return 0;
 266         }
 267         return 0;
 268 }
 269
 270 static int simplify_constant_binop(struct instruction *insn)
 271 {
 272         /* FIXME! Verify signs and sizes!! */
 273         long long left = insn->src1->value;
 274         long long right = insn->src2->value;
 275         long long res, mask;
 276
 277         switch (insn->opcode) {
 278         case OP_ADD:
 279                 res = left + right;
 280                 break;
 281         case OP_SUB:
 282                 res = left - right;
 283                 break;
 284         case OP_MUL:
 285                 /* FIXME! Check sign! */
 286                 res = left * right;
 287                 break;
 288         case OP_DIV:
 289                 if (!right)
 290                         return 0;
 291                 /* FIXME! Check sign! */
 292                 res = left / right;
 293                 break;
 294         case OP_MOD:
 295                 if (!right)
 296                         return 0;
 297                 /* FIXME! Check sign! */
 298                 res = left % right;
 299                 break;
 300         case OP_SHL:
 301                 res = left << right;
 302                 break;
 303         case OP_SHR:
 304                 /* FIXME! Check sign! */
 305                 res = left >> right;
 306                 break;
 307        /* Logical */
 308         case OP_AND:
 309                 res = left & right;
 310                 break;
 311         case OP_OR:
 312                 res = left | right;
 313                 break;
 314         case OP_XOR:
 315                 res = left ^ right;
 316                 break;
 317         case OP_AND_BOOL:
 318                 res = left && right;
 319                 break;
 320         case OP_OR_BOOL:
 321                 res = left || right;
 322                 break;
 323
 324         /* Binary comparison */
 325         case OP_SET_EQ:
 326                 res = left == right;
 327                 break;
 328         case OP_SET_NE:
 329                 res = left != right;
 330                 break;
 331         case OP_SET_LE:
 332                 /* FIXME! Check sign! */
 333                 res = left <= right;
 334                 break;
 335         case OP_SET_GE:
 336                 /* FIXME! Check sign! */
 337                 res = left >= right;
 338                 break;
 339         case OP_SET_LT:
 340                 /* FIXME! Check sign! */
 341                 res = left < right;
 342                 break;
 343         case OP_SET_GT:
 344                 /* FIXME! Check sign! */
 345                 res = left > right;
 346                 break;
 347         case OP_SET_B:
 348                 /* FIXME! Check sign! */
 349                 res = (unsigned long long) left < (unsigned long long) right;
 350                 break;
 351         case OP_SET_A:
 352                 /* FIXME! Check sign! */
 353                 res = (unsigned long long) left > (unsigned long long) right;
 354                 break;
 355         case OP_SET_BE:
 356                 /* FIXME! Check sign! */
 357                 res = (unsigned long long) left <= (unsigned long long) right;
 358                 break;
 359         case OP_SET_AE:
 360                 /* FIXME! Check sign! */
 361                 res = (unsigned long long) left >= (unsigned long long) right;
 362                 break;
 363         default:
 364                 return 0;
 365         }
 366         mask = 1ULL << (insn->type->bit_size-1);
 367         res &= mask | (mask-1);
 368
 369         /* FIXME!! Sign??? */
 370         replace_with_pseudo(insn, value_pseudo(res));
 371         return REPEAT_CSE;
 372 }
 373
 374 static int simplify_binop(struct instruction *insn)
 375 {
 376         if (dead_insn(insn, &insn->src1, &insn->src2))
 377                 return REPEAT_CSE;
 378         if (constant(insn->src1)) {
 379                 if (constant(insn->src2))
 380                         return simplify_constant_binop(insn);
 381                 return simplify_constant_leftside(insn);
 382         }
 383         if (constant(insn->src2))
 384                 return simplify_constant_rightside(insn);
 385         return 0;
 386 }
 387
 388 static int simplify_constant_unop(struct instruction *insn)
 389 {
 390         return 0;
 391 }
 392
 393 static int simplify_unop(struct instruction *insn)
 394 {
 395         if (dead_insn(insn, &insn->src1, NULL))
 396                 return REPEAT_CSE;
 397         if (constant(insn->src1))
 398                 return simplify_constant_unop(insn);
 399         return 0;
 400 }
 401
 402 static int simplify_memop(struct instruction *insn)
 403 {
 404         pseudo_t addr = insn->src;
 405         if (addr->type == PSEUDO_REG) {
 406                 struct instruction *def = addr->def;
 407                 if (def->opcode == OP_SETVAL && def->src) {
 408                         kill_use(&insn->src);
 409                         use_pseudo(def->src, &insn->src);
 410                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 411                 }
 412         }
 413         return 0;
 414 }
 415
 416 int simplify_instruction(struct instruction *insn)
 417 {
 418         pseudo_t cond;
 419         static struct instruction *last_setcc;
 420         struct instruction *setcc = last_setcc;
 421
 422         last_setcc = NULL;
 423
 424         if (!insn->bb)
 425                 return 0;
 426         switch (insn->opcode) {
 427         case OP_BINARY ... OP_BINCMP_END:
 428                 return simplify_binop(insn);
 429
 430         case OP_NOT: case OP_NEG:
 431                 return simplify_unop(insn);
 432         case OP_LOAD: case OP_STORE:
 433                 return simplify_memop(insn);
 434         case OP_SETVAL:
 435                 if (dead_insn(insn, NULL, NULL))
 436                         return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
 437                 break;
 438         case OP_PHI:
 439                 if (dead_insn(insn, NULL, NULL)) {
 440                         clear_phi(insn);
 441                         return REPEAT_CSE;
 442                 }
 443                 return clean_up_phi(insn);
 444         case OP_PHISOURCE:
 445                 if (dead_insn(insn, &insn->src1, NULL))
 446                         return REPEAT_CSE;
 447                 break;
 448         case OP_SETCC:
 449                 last_setcc = insn;
 450                 return 0;
 451         case OP_SEL:
 452                 assert(setcc && setcc->bb);
 453                 if (dead_insn(insn, &insn->src1, &insn->src2)) {
 454                         setcc->bb = NULL;
 455                         return REPEAT_CSE;
 456                 }
 457                 cond = setcc->src;
 458                 if (!constant(cond) && insn->src1 != insn->src2)
 459                         return 0;
 460                 setcc->bb = NULL;
 461                 kill_use(&setcc->cond);
 462                 replace_with_pseudo(insn, cond->value ? insn->src1 : insn->src2);
 463                 return REPEAT_CSE;
 464         case OP_BR:
 465                 cond = insn->cond;
 466                 if (!cond || !constant(cond))
 467                         break;
 468                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
 469                 return REPEAT_CSE;
 470         }
 471         return 0;
 472 }