cse.c

   1 /*
   2  * CSE - walk the linearized instruction flow, and
   3  * see if we can simplify it and apply CSE on it.
   4  *
   5  * Copyright (C) 2004 Linus Torvalds
   6  */
   7
   8 #include <string.h>
   9 #include <stdarg.h>
  10 #include <stdlib.h>
  11 #include <stdio.h>
  12 #include <stddef.h>
  13 #include <assert.h>
  14
  15 #include "parse.h"
  16 #include "expression.h"
  17 #include "flowgraph.h"
  18 #include "linearize.h"
  19 #include "flow.h"
  20 #include "cse.h"
  21
  22 #define INSN_HASH_SIZE 256
  23 static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
  24
  25 static int phi_compare(pseudo_t phi1, pseudo_t phi2)
  26 {
  27         const struct instruction *def1 = phi1->def;
  28         const struct instruction *def2 = phi2->def;
  29
  30         if (def1->src1 != def2->src1)
  31                 return def1->src1 < def2->src1 ? -1 : 1;
  32         if (def1->bb != def2->bb)
  33                 return def1->bb < def2->bb ? -1 : 1;
  34         return 0;
  35 }
  36
  37
  38 void cse_collect(struct instruction *insn)
  39 {
  40         unsigned long hash;
  41
  42         hash = (insn->opcode << 3) + (insn->size >> 3);
  43         switch (insn->opcode) {
  44         case OP_SEL:
  45                 hash += hashval(insn->src3);
  46                 /* Fall through */
  47
  48         /* Binary arithmetic */
  49         case OP_ADD: case OP_SUB:
  50         case OP_MUL:
  51         case OP_DIVU: case OP_DIVS:
  52         case OP_MODU: case OP_MODS:
  53         case OP_SHL:
  54         case OP_LSR: case OP_ASR:
  55         case OP_AND: case OP_OR:
  56
  57         /* Binary logical */
  58         case OP_XOR:
  59
  60         /* Binary comparison */
  61         case OP_SET_EQ: case OP_SET_NE:
  62         case OP_SET_LE: case OP_SET_GE:
  63         case OP_SET_LT: case OP_SET_GT:
  64         case OP_SET_B:  case OP_SET_A:
  65         case OP_SET_BE: case OP_SET_AE:
  66
  67         /* floating-point arithmetic & comparison */
  68         case OP_FPCMP ... OP_FPCMP_END:
  69         case OP_FADD:
  70         case OP_FSUB:
  71         case OP_FMUL:
  72         case OP_FDIV:
  73                 hash += hashval(insn->src2);
  74                 /* Fall through */
  75
  76         /* Unary */
  77         case OP_NOT: case OP_NEG:
  78         case OP_FNEG:
  79         case OP_SYMADDR:
  80                 hash += hashval(insn->src1);
  81                 break;
  82
  83         case OP_LABEL:
  84                 hash += hashval(insn->bb_true);
  85                 break;
  86
  87         case OP_SETVAL:
  88                 hash += hashval(insn->val);
  89                 break;
  90
  91         case OP_SETFVAL:
  92                 hash += hashval(insn->fvalue);
  93                 break;
  94
  95         case OP_SEXT: case OP_ZEXT:
  96         case OP_TRUNC:
  97         case OP_PTRCAST:
  98         case OP_UTPTR: case OP_PTRTU:
  99                 if (!insn->orig_type || insn->orig_type->bit_size < 0)
 100                         return;
 101                 hash += hashval(insn->src);
 102
 103                 // Note: see corresponding line in insn_compare()
 104                 hash += hashval(insn->orig_type->bit_size);
 105                 break;
 106
 107         /* Other */
 108         case OP_PHI: {
 109                 pseudo_t phi;
 110                 FOR_EACH_PTR(insn->phi_list, phi) {
 111                         struct instruction *def;
 112                         if (phi == VOID || !phi->def)
 113                                 continue;
 114                         def = phi->def;
 115                         hash += hashval(def->src1);
 116                         hash += hashval(def->bb);
 117                 } END_FOR_EACH_PTR(phi);
 118                 break;
 119         }
 120
 121         default:
 122                 /*
 123                  * Nothing to do, don't even bother hashing them,
 124                  * we're not going to try to CSE them
 125                  */
 126                 return;
 127         }
 128         hash += hash >> 16;
 129         hash &= INSN_HASH_SIZE-1;
 130         add_instruction(insn_hash_table + hash, insn);
 131 }
 132
 133 /* Compare two (sorted) phi-lists */
 134 static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2)
 135 {
 136         pseudo_t phi1, phi2;
 137
 138         PREPARE_PTR_LIST(l1, phi1);
 139         PREPARE_PTR_LIST(l2, phi2);
 140         for (;;) {
 141                 int cmp;
 142
 143                 while (phi1 && (phi1 == VOID || !phi1->def))
 144                         NEXT_PTR_LIST(phi1);
 145                 while (phi2 && (phi2 == VOID || !phi2->def))
 146                         NEXT_PTR_LIST(phi2);
 147
 148                 if (!phi1)
 149                         return phi2 ? -1 : 0;
 150                 if (!phi2)
 151                         return phi1 ? 1 : 0;
 152                 cmp = phi_compare(phi1, phi2);
 153                 if (cmp)
 154                         return cmp;
 155                 NEXT_PTR_LIST(phi1);
 156                 NEXT_PTR_LIST(phi2);
 157         }
 158         /* Not reached, but we need to make the nesting come out right */
 159         FINISH_PTR_LIST(phi2);
 160         FINISH_PTR_LIST(phi1);
 161 }
 162
 163 static int insn_compare(const void *_i1, const void *_i2)
 164 {
 165         const struct instruction *i1 = _i1;
 166         const struct instruction *i2 = _i2;
 167         int size1, size2;
 168         int diff;
 169
 170         if (i1->opcode != i2->opcode)
 171                 return i1->opcode < i2->opcode ? -1 : 1;
 172
 173         switch (i1->opcode) {
 174
 175         /* commutative binop */
 176         case OP_ADD:
 177         case OP_MUL:
 178         case OP_AND: case OP_OR:
 179         case OP_XOR:
 180         case OP_SET_EQ: case OP_SET_NE:
 181                 if (i1->src1 == i2->src2 && i1->src2 == i2->src1)
 182                         return 0;
 183                 goto case_binops;
 184
 185         case OP_SEL:
 186                 if (i1->src3 != i2->src3)
 187                         return i1->src3 < i2->src3 ? -1 : 1;
 188                 /* Fall-through to binops */
 189
 190         /* Binary arithmetic */
 191         case OP_SUB:
 192         case OP_DIVU: case OP_DIVS:
 193         case OP_MODU: case OP_MODS:
 194         case OP_SHL:
 195         case OP_LSR: case OP_ASR:
 196
 197         /* Binary comparison */
 198         case OP_SET_LE: case OP_SET_GE:
 199         case OP_SET_LT: case OP_SET_GT:
 200         case OP_SET_B:  case OP_SET_A:
 201         case OP_SET_BE: case OP_SET_AE:
 202
 203         /* floating-point arithmetic */
 204         case OP_FPCMP ... OP_FPCMP_END:
 205         case OP_FADD:
 206         case OP_FSUB:
 207         case OP_FMUL:
 208         case OP_FDIV:
 209         case_binops:
 210                 if (i1->src2 != i2->src2)
 211                         return i1->src2 < i2->src2 ? -1 : 1;
 212                 /* Fall through to unops */
 213
 214         /* Unary */
 215         case OP_NOT: case OP_NEG:
 216         case OP_FNEG:
 217         case OP_SYMADDR:
 218                 if (i1->src1 != i2->src1)
 219                         return i1->src1 < i2->src1 ? -1 : 1;
 220                 break;
 221
 222         case OP_LABEL:
 223                 if (i1->bb_true != i2->bb_true)
 224                         return i1->bb_true < i2->bb_true ? -1 : 1;
 225                 break;
 226
 227         case OP_SETVAL:
 228                 if (i1->val != i2->val)
 229                         return i1->val < i2->val ? -1 : 1;
 230                 break;
 231
 232         case OP_SETFVAL:
 233                 diff = memcmp(&i1->fvalue, &i2->fvalue, sizeof(i1->fvalue));
 234                 if (diff)
 235                         return diff;
 236                 break;
 237
 238         /* Other */
 239         case OP_PHI:
 240                 return phi_list_compare(i1->phi_list, i2->phi_list);
 241
 242         case OP_SEXT: case OP_ZEXT:
 243         case OP_TRUNC:
 244         case OP_PTRCAST:
 245         case OP_UTPTR: case OP_PTRTU:
 246                 if (i1->src != i2->src)
 247                         return i1->src < i2->src ? -1 : 1;
 248
 249                 // Note: if it can be guaranted that identical ->src
 250                 // implies identical orig_type->bit_size, then this
 251                 // test and the hashing of the original size in
 252                 // cse_collect() are not needed.
 253                 // It must be generaly true but it isn't guaranted (yet).
 254                 size1 = i1->orig_type->bit_size;
 255                 size2 = i2->orig_type->bit_size;
 256                 if (size1 != size2)
 257                         return size1 < size2 ? -1 : 1;
 258                 break;
 259
 260         default:
 261                 warning(i1->pos, "bad instruction on hash chain");
 262         }
 263         if (i1->size != i2->size)
 264                 return i1->size < i2->size ? -1 : 1;
 265         return 0;
 266 }
 267
 268 static void sort_instruction_list(struct instruction_list **list)
 269 {
 270         sort_list((struct ptr_list **)list , insn_compare);
 271 }
 272
 273 static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
 274 {
 275         convert_instruction_target(insn, def->target);
 276
 277         kill_instruction(insn);
 278         repeat_phase |= REPEAT_CSE;
 279         return def;
 280 }
 281
 282 static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
 283 {
 284         struct basic_block *parent;
 285
 286         if (bb_list_size(bb1->parents) != 1)
 287                 return NULL;
 288         parent = first_basic_block(bb1->parents);
 289         if (bb_list_size(bb2->parents) != 1)
 290                 return NULL;
 291         if (first_basic_block(bb2->parents) != parent)
 292                 return NULL;
 293         return parent;
 294 }
 295
 296 static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
 297 {
 298         delete_ptr_list_entry((struct ptr_list **)list, insn, count);
 299 }
 300
 301 static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb)
 302 {
 303         struct instruction *br = delete_last_instruction(&bb->insns);
 304         insn->bb = bb;
 305         add_instruction(&bb->insns, insn);
 306         add_instruction(&bb->insns, br);
 307 }
 308
 309 static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2)
 310 {
 311         struct basic_block *b1, *b2, *common;
 312
 313         /*
 314          * OK, i1 and i2 are the same instruction, modulo "target".
 315          * We should now see if we can combine them.
 316          */
 317         b1 = i1->bb;
 318         b2 = i2->bb;
 319
 320         /*
 321          * Currently we only handle the uninteresting degenerate case where
 322          * the CSE is inside one basic-block.
 323          */
 324         if (b1 == b2) {
 325                 struct instruction *insn;
 326                 FOR_EACH_PTR(b1->insns, insn) {
 327                         if (insn == i1)
 328                                 return cse_one_instruction(i2, i1);
 329                         if (insn == i2)
 330                                 return cse_one_instruction(i1, i2);
 331                 } END_FOR_EACH_PTR(insn);
 332                 warning(b1->pos, "Whaa? unable to find CSE instructions");
 333                 return i1;
 334         }
 335         if (domtree_dominates(b1, b2))
 336                 return cse_one_instruction(i2, i1);
 337
 338         if (domtree_dominates(b2, b1))
 339                 return cse_one_instruction(i1, i2);
 340
 341         /* No direct dominance - but we could try to find a common ancestor.. */
 342         common = trivial_common_parent(b1, b2);
 343         if (common) {
 344                 i1 = cse_one_instruction(i2, i1);
 345                 remove_instruction(&b1->insns, i1, 1);
 346                 add_instruction_to_end(i1, common);
 347         } else {
 348                 i1 = i2;
 349         }
 350
 351         return i1;
 352 }
 353
 354 void cse_eliminate(struct entrypoint *ep)
 355 {
 356         int i;
 357
 358         for (i = 0; i < INSN_HASH_SIZE; i++) {
 359                 struct instruction_list **list = insn_hash_table + i;
 360                 if (*list) {
 361                         if (instruction_list_size(*list) > 1) {
 362                                 struct instruction *insn, *last;
 363
 364                                 sort_instruction_list(list);
 365
 366                                 last = NULL;
 367                                 FOR_EACH_PTR(*list, insn) {
 368                                         if (!insn->bb)
 369                                                 continue;
 370                                         if (last) {
 371                                                 if (!insn_compare(last, insn))
 372                                                         insn = try_to_cse(ep, last, insn);
 373                                         }
 374                                         last = insn;
 375                                 } END_FOR_EACH_PTR(insn);
 376                         }
 377                         free_ptr_list(list);
 378                 }
 379         }
 380 }