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