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 "linearize.h"
  18 #include "flow.h"
  19
  20 #define INSN_HASH_SIZE 65536
  21 static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
  22
  23 #define hashval(x) ((unsigned long)(x))
  24
  25 int repeat_phase, merge_phi_sources;
  26
  27 static int phi_compare(pseudo_t phi1, pseudo_t phi2)
  28 {
  29         const struct instruction *def1 = phi1->def;
  30         const struct instruction *def2 = phi2->def;
  31
  32         if (def1->src1 != def2->src1)
  33                 return def1->src1 < def2->src1 ? -1 : 1;
  34         if (def1->bb != def2->bb)
  35                 return def1->bb < def2->bb ? -1 : 1;
  36         return 0;
  37 }
  38
  39
  40 static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
  41 {
  42         unsigned long hash;
  43
  44         if (!insn->bb)
  45                 return;
  46         assert(insn->bb == bb);
  47         repeat_phase |= simplify_instruction(insn);
  48         hash = (insn->opcode << 3) + (insn->size >> 3);
  49         switch (insn->opcode) {
  50         case OP_SEL:
  51                 hash += hashval(insn->src3);
  52                 /* Fallthrough */
  53
  54         /* Binary arithmetic */
  55         case OP_ADD: case OP_SUB:
  56         case OP_MUL: case OP_DIV:
  57         case OP_MOD: case OP_SHL:
  58         case OP_SHR:
  59         case OP_AND: case OP_OR:
  60
  61         /* Binary logical */
  62         case OP_XOR: case OP_AND_BOOL:
  63         case OP_OR_BOOL:
  64
  65         /* Binary comparison */
  66         case OP_SET_EQ: case OP_SET_NE:
  67         case OP_SET_LE: case OP_SET_GE:
  68         case OP_SET_LT: case OP_SET_GT:
  69         case OP_SET_B:  case OP_SET_A:
  70         case OP_SET_BE: case OP_SET_AE:
  71                 hash += hashval(insn->src2);
  72                 /* Fallthrough */
  73
  74         /* Unary */
  75         case OP_NOT: case OP_NEG:
  76                 hash += hashval(insn->src1);
  77                 break;
  78
  79         case OP_SETVAL:
  80                 hash += hashval(insn->val);
  81                 hash += hashval(insn->symbol);
  82                 break;
  83
  84         /* Other */
  85         case OP_PHI: {
  86                 pseudo_t phi;
  87                 FOR_EACH_PTR(insn->phi_list, phi) {
  88                         struct instruction *def;
  89                         if (phi == VOID)
  90                                 continue;
  91                         def = phi->def;
  92                         hash += hashval(def->src1);
  93                         hash += hashval(def->bb);
  94                 } END_FOR_EACH_PTR(phi);
  95                 break;
  96         }
  97
  98         case OP_PHISOURCE:
  99                 hash += hashval(insn->src1);
 100                 hash += hashval(insn->bb);
 101                 break;
 102
 103         default:
 104                 /*
 105                  * Nothing to do, don't even bother hashing them,
 106                  * we're not going to try to CSE them
 107                  */
 108                 return;
 109         }
 110         hash += hash >> 16;
 111         hash &= INSN_HASH_SIZE-1;
 112         add_instruction(insn_hash_table + hash, insn);
 113 }
 114
 115 static void clean_up_insns(struct entrypoint *ep)
 116 {
 117         struct basic_block *bb;
 118
 119         FOR_EACH_PTR(ep->bbs, bb) {
 120                 struct instruction *insn;
 121                 FOR_EACH_PTR(bb->insns, insn) {
 122                         clean_up_one_instruction(bb, insn);
 123                 } END_FOR_EACH_PTR(insn);
 124         } END_FOR_EACH_PTR(bb);
 125 }
 126
 127 extern void show_instruction(struct instruction *);
 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 == VOID)
 140                         NEXT_PTR_LIST(phi1);
 141                 while (phi2 == VOID)
 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
 164         if (i1->opcode != i2->opcode)
 165                 return i1->opcode < i2->opcode ? -1 : 1;
 166
 167         switch (i1->opcode) {
 168         case OP_SEL:
 169                 if (i1->src3 != i2->src3)
 170                         return i1->src3 < i2->src3 ? -1 : 1;
 171                 /* Fall-through to binops */
 172
 173         /* Binary arithmetic */
 174         case OP_ADD: case OP_SUB:
 175         case OP_MUL: case OP_DIV:
 176         case OP_MOD: case OP_SHL:
 177         case OP_SHR:
 178         case OP_AND: case OP_OR:
 179
 180         /* Binary logical */
 181         case OP_XOR: case OP_AND_BOOL:
 182         case OP_OR_BOOL:
 183
 184         /* Binary comparison */
 185         case OP_SET_EQ: case OP_SET_NE:
 186         case OP_SET_LE: case OP_SET_GE:
 187         case OP_SET_LT: case OP_SET_GT:
 188         case OP_SET_B:  case OP_SET_A:
 189         case OP_SET_BE: case OP_SET_AE:
 190                 if (i1->src2 != i2->src2)
 191                         return i1->src2 < i2->src2 ? -1 : 1;
 192                 /* Fall-through to unops */
 193
 194         /* Unary */
 195         case OP_NOT: case OP_NEG:
 196                 if (i1->src1 != i2->src1)
 197                         return i1->src1 < i2->src1 ? -1 : 1;
 198                 break;
 199
 200         case OP_SETVAL:
 201                 if (i1->val != i2->val)
 202                         return i1->val < i2->val ? -1 : 1;
 203                 if (i1->symbol != i2->symbol)
 204                         return i1->symbol < i2->symbol ? -1 : 1;
 205                 break;
 206
 207         /* Other */
 208         case OP_PHI:
 209                 return phi_list_compare(i1->phi_list, i2->phi_list);
 210
 211         case OP_PHISOURCE:
 212                 if (i1->src1 != i2->src1)
 213                         return i1->src1 < i2->src1 ? -1 : 1;
 214                 if (i1->bb != i2->bb)
 215                         return i1->bb < i2->bb ? -1 : 1;
 216                 if (!merge_phi_sources) {
 217                         if (i1 != i2)
 218                                 return i1 < i2 ? -1 : 1;
 219                 }
 220                 break;
 221
 222         default:
 223                 warning(i1->bb->pos, "bad instruction on hash chain");
 224         }
 225         if (i1->size != i2->size)
 226                 return i1->size < i2->size ? -1 : 1;
 227         return 0;
 228 }
 229
 230 static void sort_instruction_list(struct instruction_list **list)
 231 {
 232         sort_list((struct ptr_list **)list , insn_compare);
 233 }
 234
 235 static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
 236 {
 237         convert_instruction_target(insn, def->target);
 238         insn->opcode = OP_NOP;
 239         insn->bb = NULL;
 240         repeat_phase |= REPEAT_CSE;
 241         return def;
 242 }
 243
 244 /*
 245  * Does "bb1" dominate "bb2"?
 246  */
 247 static int bb_dominates(struct entrypoint *ep, struct basic_block *bb1, struct basic_block *bb2, unsigned long generation)
 248 {
 249         struct basic_block *parent;
 250
 251         /* Nothing dominates the entrypoint.. */
 252         if (bb2 == ep->entry)
 253                 return 0;
 254         FOR_EACH_PTR(bb2->parents, parent) {
 255                 if (parent == bb1)
 256                         continue;
 257                 if (parent->generation == generation)
 258                         continue;
 259                 parent->generation = generation;
 260                 if (!bb_dominates(ep, bb1, parent, generation))
 261                         return 0;
 262         } END_FOR_EACH_PTR(parent);
 263         return 1;
 264 }
 265
 266 static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
 267 {
 268         struct basic_block *parent;
 269
 270         if (bb_list_size(bb1->parents) != 1)
 271                 return 0;
 272         parent = first_basic_block(bb1->parents);
 273         if (bb_list_size(bb2->parents) != 1)
 274                 return 0;
 275         if (first_basic_block(bb2->parents) != parent)
 276                 return 0;
 277         return parent;
 278 }
 279
 280 static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
 281 {
 282         delete_ptr_list_entry((struct ptr_list **)list, insn, count);
 283 }
 284
 285 static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb)
 286 {
 287         struct instruction *br = delete_last_instruction(&bb->insns);
 288         insn->bb = bb;
 289         add_instruction(&bb->insns, insn);
 290         add_instruction(&bb->insns, br);
 291 }
 292
 293 static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2)
 294 {
 295         struct basic_block *b1, *b2, *common;
 296
 297         /*
 298          * Ok, i1 and i2 are the same instruction, modulo "target".
 299          * We should now see if we can combine them.
 300          */
 301         b1 = i1->bb;
 302         b2 = i2->bb;
 303
 304         /*
 305          * Currently we only handle the uninteresting degenerate case where
 306          * the CSE is inside one basic-block.
 307          */
 308         if (b1 == b2) {
 309                 struct instruction *insn;
 310                 FOR_EACH_PTR(b1->insns, insn) {
 311                         if (insn == i1)
 312                                 return cse_one_instruction(i2, i1);
 313                         if (insn == i2)
 314                                 return cse_one_instruction(i1, i2);
 315                 } END_FOR_EACH_PTR(insn);
 316                 warning(b1->pos, "Whaa? unable to find CSE instructions");
 317                 return i1;
 318         }
 319         if (bb_dominates(ep, b1, b2, ++bb_generation))
 320                 return cse_one_instruction(i2, i1);
 321
 322         if (bb_dominates(ep, b2, b1, ++bb_generation))
 323                 return cse_one_instruction(i1, i2);
 324
 325         /* No direct dominance - but we could try to find a common ancestor.. */
 326         common = trivial_common_parent(b1, b2);
 327         if (common) {
 328                 i1 = cse_one_instruction(i2, i1);
 329                 remove_instruction(&b1->insns, i1, 1);
 330                 add_instruction_to_end(i1, common);
 331         }
 332
 333         return i1;
 334 }
 335
 336 void cleanup_and_cse(struct entrypoint *ep)
 337 {
 338         int i;
 339
 340         simplify_memops(ep);
 341 repeat:
 342         repeat_phase = 0;
 343         clean_up_insns(ep);
 344         for (i = 0; i < INSN_HASH_SIZE; i++) {
 345                 struct instruction_list **list = insn_hash_table + i;
 346                 if (*list) {
 347                         if (instruction_list_size(*list) > 1) {
 348                                 struct instruction *insn, *last;
 349
 350                                 sort_instruction_list(list);
 351
 352                                 last = NULL;
 353                                 FOR_EACH_PTR(*list, insn) {
 354                                         if (!insn->bb)
 355                                                 continue;
 356                                         if (last) {
 357                                                 if (!insn_compare(last, insn))
 358                                                         insn = try_to_cse(ep, last, insn);
 359                                         }
 360                                         last = insn;
 361                                 } END_FOR_EACH_PTR(insn);
 362                         }
 363                         free_ptr_list((struct ptr_list **)list);
 364                 }
 365         }
 366
 367         if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
 368                 simplify_memops(ep);
 369
 370         if (repeat_phase & REPEAT_CSE)
 371                 goto repeat;
 372 }