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