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