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