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 1;
 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 = phi->def;
 126                 if (def->src1 == VOID || !def->bb)
 127                         continue;
 128                 if (last) {
 129                         if (last->src1 != def->src1)
 130                                 same = 0;
 131                         continue;
 132                 }
 133                 last = def;
 134         } END_FOR_EACH_PTR(phi);
 135
 136         if (same) {
 137                 pseudo_t pseudo = last ? last->src1 : VOID;
 138                 convert_instruction_target(insn, pseudo);
 139                 insn->bb = NULL;
 140                 return 1;
 141         }
 142
 143         return if_convert_phi(insn);
 144 }
 145
 146 static void try_to_kill(struct instruction *);
 147
 148 static void kill_use(pseudo_t pseudo)
 149 {
 150         if (pseudo->type == PSEUDO_REG) {
 151                 if (ptr_list_size((struct ptr_list *)pseudo->users) == 1) {
 152                         try_to_kill(pseudo->def);
 153                 }
 154         }
 155 }
 156
 157 static void try_to_kill(struct instruction *insn)
 158 {
 159         int opcode = insn->opcode;
 160         switch (opcode) {
 161         case OP_BINARY ... OP_BINCMP_END:
 162                 insn->bb = NULL;
 163                 kill_use(insn->src1);
 164                 kill_use(insn->src2);
 165                 return;
 166         case OP_NOT: case OP_NEG:
 167                 insn->bb = NULL;
 168                 kill_use(insn->src1);
 169                 return;
 170
 171         case OP_PHI: case OP_SETVAL:
 172                 insn->bb = NULL;
 173                 return;
 174         }
 175 }
 176
 177 /*
 178  * Kill trivially dead instructions
 179  */
 180 static int dead_insn(struct instruction *insn, pseudo_t src1, pseudo_t src2)
 181 {
 182         pseudo_t *usep;
 183         FOR_EACH_PTR(insn->target->users, usep) {
 184                 if (*usep != VOID)
 185                         return 0;
 186         } END_FOR_EACH_PTR(usep);
 187
 188         insn->bb = NULL;
 189         kill_use(src1);
 190         kill_use(src2);
 191         return 1;
 192 }
 193
 194 static inline int constant(pseudo_t pseudo)
 195 {
 196         return pseudo->type == PSEUDO_VAL;
 197 }
 198
 199 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
 200 {
 201         convert_instruction_target(insn, pseudo);
 202         insn->bb = NULL;
 203         return 1;
 204 }
 205
 206 static int simplify_constant_rightside(struct instruction *insn)
 207 {
 208         long long value = insn->src2->value;
 209
 210         switch (insn->opcode) {
 211         case OP_ADD: case OP_SUB:
 212         case OP_OR: case OP_XOR:
 213         case OP_SHL: case OP_SHR:
 214                 if (!value)
 215                         return replace_with_pseudo(insn, insn->src1);
 216                 return 0;
 217
 218         case OP_AND: case OP_MUL:
 219                 if (!value)
 220                         return replace_with_pseudo(insn, insn->src2);
 221                 return 0;
 222         }
 223         return 0;
 224 }
 225
 226 static int simplify_constant_leftside(struct instruction *insn)
 227 {
 228         return 0;
 229 }
 230
 231 static int simplify_constant_binop(struct instruction *insn)
 232 {
 233         /* FIXME! Verify signs and sizes!! */
 234         long long left = insn->src1->value;
 235         long long right = insn->src2->value;
 236         long long res, mask;
 237
 238         switch (insn->opcode) {
 239         case OP_ADD:
 240                 res = left + right;
 241                 break;
 242         case OP_SUB:
 243                 res = left - right;
 244                 break;
 245         case OP_MUL:
 246                 /* FIXME! Check sign! */
 247                 res = left * right;
 248                 break;
 249         case OP_DIV:
 250                 if (!right)
 251                         return 0;
 252                 /* FIXME! Check sign! */
 253                 res = left / right;
 254                 break;
 255         case OP_MOD:
 256                 if (!right)
 257                         return 0;
 258                 /* FIXME! Check sign! */
 259                 res = left % right;
 260                 break;
 261         case OP_SHL:
 262                 res = left << right;
 263                 break;
 264         case OP_SHR:
 265                 /* FIXME! Check sign! */
 266                 res = left >> right;
 267                 break;
 268        /* Logical */
 269         case OP_AND:
 270                 res = left & right;
 271                 break;
 272         case OP_OR:
 273                 res = left | right;
 274                 break;
 275         case OP_XOR:
 276                 res = left ^ right;
 277                 break;
 278         case OP_AND_BOOL:
 279                 res = left && right;
 280                 break;
 281         case OP_OR_BOOL:
 282                 res = left || right;
 283                 break;
 284
 285         /* Binary comparison */
 286         case OP_SET_EQ:
 287                 res = left == right;
 288                 break;
 289         case OP_SET_NE:
 290                 res = left != right;
 291                 break;
 292         case OP_SET_LE:
 293                 /* FIXME! Check sign! */
 294                 res = left <= right;
 295                 break;
 296         case OP_SET_GE:
 297                 /* FIXME! Check sign! */
 298                 res = left >= right;
 299                 break;
 300         case OP_SET_LT:
 301                 /* FIXME! Check sign! */
 302                 res = left < right;
 303                 break;
 304         case OP_SET_GT:
 305                 /* FIXME! Check sign! */
 306                 res = left > right;
 307                 break;
 308         case OP_SET_B:
 309                 /* FIXME! Check sign! */
 310                 res = (unsigned long long) left < (unsigned long long) right;
 311                 break;
 312         case OP_SET_A:
 313                 /* FIXME! Check sign! */
 314                 res = (unsigned long long) left > (unsigned long long) right;
 315                 break;
 316         case OP_SET_BE:
 317                 /* FIXME! Check sign! */
 318                 res = (unsigned long long) left <= (unsigned long long) right;
 319                 break;
 320         case OP_SET_AE:
 321                 /* FIXME! Check sign! */
 322                 res = (unsigned long long) left >= (unsigned long long) right;
 323                 break;
 324         default:
 325                 return 0;
 326         }
 327         mask = 1ULL << (insn->type->bit_size-1);
 328         res &= mask | (mask-1);
 329
 330         /* FIXME!! Sign??? */
 331         replace_with_pseudo(insn, value_pseudo(res));
 332         return 1;
 333 }
 334
 335 static int simplify_binop(struct instruction *insn)
 336 {
 337         if (dead_insn(insn, insn->src1, insn->src2))
 338                 return 1;
 339         if (constant(insn->src1)) {
 340                 if (constant(insn->src2))
 341                         return simplify_constant_binop(insn);
 342                 return simplify_constant_leftside(insn);
 343         }
 344         if (constant(insn->src2))
 345                 return simplify_constant_rightside(insn);
 346         return 0;
 347 }
 348
 349 static int simplify_constant_unop(struct instruction *insn)
 350 {
 351         return 0;
 352 }
 353
 354 static int simplify_unop(struct instruction *insn)
 355 {
 356         if (dead_insn(insn, insn->src1, VOID))
 357                 return 1;
 358         if (constant(insn->src1))
 359                 return simplify_constant_unop(insn);
 360         return 0;
 361 }
 362
 363 int simplify_instruction(struct instruction *insn)
 364 {
 365         pseudo_t cond;
 366         static struct instruction *last_setcc;
 367         struct instruction *setcc = last_setcc;
 368
 369         last_setcc = NULL;
 370
 371         switch (insn->opcode) {
 372         case OP_BINARY ... OP_BINCMP_END:
 373                 return simplify_binop(insn);
 374
 375         case OP_NOT: case OP_NEG:
 376                 return simplify_unop(insn);
 377
 378         case OP_SETVAL:
 379                 if (dead_insn(insn, VOID, VOID))
 380                         return 1;
 381                 break;
 382         case OP_PHI:
 383                 if (dead_insn(insn, VOID, VOID)) {
 384                         clear_phi(insn);
 385                         return 1;
 386                 }
 387                 return clean_up_phi(insn);
 388         case OP_PHISOURCE:
 389                 if (dead_insn(insn, insn->src1, VOID))
 390                         return 1;
 391                 break;
 392         case OP_SETCC:
 393                 last_setcc = insn;
 394                 return 0;
 395         case OP_SEL:
 396                 assert(setcc && setcc->bb);
 397                 if (dead_insn(insn, insn->src1, insn->src2)) {
 398                         setcc->bb = NULL;
 399                         return 1;
 400                 }
 401                 cond = setcc->src;
 402                 if (!constant(cond) && insn->src1 != insn->src2)
 403                         return 0;
 404                 setcc->bb = NULL;
 405                 kill_use(cond);
 406                 replace_with_pseudo(insn, cond->value ? insn->src1 : insn->src2);
 407                 return 1;
 408         case OP_BR:
 409                 cond = insn->cond;
 410                 if (!cond || !constant(cond))
 411                         break;
 412                 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
 413                 return 1;
 414         }
 415         return 0;
 416 }