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
  14 #include "parse.h"
  15 #include "expression.h"
  16 #include "linearize.h"
  17 #include "flow.h"
  18
  19 #define INSN_HASH_SIZE 65536
  20 static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
  21
  22 #define hashval(x) ((unsigned long)(x))
  23
  24 static int phi_compare(const void *_phi1, const void *_phi2)
  25 {
  26         const struct phi *phi1 = _phi1;
  27         const struct phi *phi2 = _phi2;
  28
  29         if (phi1->pseudo != phi2->pseudo)
  30                 return phi1->pseudo < phi2->pseudo ? -1 : 1;
  31         if (phi1->source != phi2->source)
  32                 return phi1->source < phi2->source ? -1 : 1;
  33         return 0;
  34 }
  35
  36 static void sort_phi_list(struct phi_list **list)
  37 {
  38         sort_list((struct ptr_list **)list , phi_compare);
  39 }
  40
  41 static unsigned long clean_up_phi(struct instruction *insn)
  42 {
  43         struct phi *phi, *last;
  44         unsigned long hash = 0;
  45
  46         sort_phi_list(&insn->phi_list);
  47
  48         last = NULL;
  49         FOR_EACH_PTR(insn->phi_list, phi) {
  50                 if (last) {
  51                         if (last->pseudo == phi->pseudo &&
  52                             last->source == phi->source) {
  53                                 DELETE_CURRENT_PTR(phi);
  54                                 continue;
  55                         }
  56                 }
  57                 last = phi;
  58                 hash += hashval(phi->pseudo);
  59                 hash += hashval(phi->source);
  60         } END_FOR_EACH_PTR(phi);
  61         return hash;
  62 }
  63
  64 static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
  65 {
  66         unsigned long hash;
  67
  68         if (insn->bb != bb)
  69                 warning(bb->pos, "instruction with bad bb");
  70         hash = insn->opcode;
  71         switch (insn->opcode) {
  72
  73         /* Binary arithmetic */
  74         case OP_ADD: case OP_SUB:
  75         case OP_MUL: case OP_DIV:
  76         case OP_MOD: case OP_SHL:
  77         case OP_SHR: case OP_SEL:
  78         case OP_AND: case OP_OR:
  79
  80         /* Binary logical */
  81         case OP_XOR: case OP_AND_BOOL:
  82         case OP_OR_BOOL:
  83
  84         /* Binary comparison */
  85         case OP_SET_EQ: case OP_SET_NE:
  86         case OP_SET_LE: case OP_SET_GE:
  87         case OP_SET_LT: case OP_SET_GT:
  88         case OP_SET_B:  case OP_SET_A:
  89         case OP_SET_BE: case OP_SET_AE:
  90                 hash += hashval(insn->src1);
  91                 hash += hashval(insn->src2);
  92                 break;
  93
  94         /* Unary */
  95         case OP_NOT: case OP_NEG:
  96                 hash += hashval(insn->src1);
  97                 break;
  98
  99         case OP_SETVAL:
 100                 hash += hashval(insn->val);
 101                 hash += hashval(insn->symbol);
 102                 break;
 103
 104         /* Other */
 105         case OP_PHI:
 106                 hash += clean_up_phi(insn);
 107                 break;
 108
 109         default:
 110                 /*
 111                  * Nothing to do, don't even bother hashing them,
 112                  * we're not going to try to CSE them
 113                  */
 114                 return;
 115         }
 116         hash += hash >> 16;
 117         hash &= INSN_HASH_SIZE-1;
 118         add_instruction(insn_hash_table + hash, insn);
 119 }
 120
 121 static void clean_up_insns(struct entrypoint *ep)
 122 {
 123         struct basic_block *bb;
 124
 125         FOR_EACH_PTR(ep->bbs, bb) {
 126                 struct instruction *insn;
 127                 FOR_EACH_PTR(bb->insns, insn) {
 128                         clean_up_one_instruction(bb, insn);
 129                 } END_FOR_EACH_PTR(insn);
 130         } END_FOR_EACH_PTR(bb);
 131 }
 132
 133 extern void show_instruction(struct instruction *);
 134
 135 /* Compare two (sorted) phi-lists */
 136 static int phi_list_compare(struct phi_list *l1, struct phi_list *l2)
 137 {
 138         struct phi *phi1, *phi2;
 139
 140         PREPARE_PTR_LIST(l1, phi1);
 141         PREPARE_PTR_LIST(l2, phi2);
 142         for (;;) {
 143                 int cmp;
 144
 145                 if (!phi1)
 146                         return phi2 ? -1 : 0;
 147                 if (!phi2)
 148                         return phi1 ? 1 : 0;
 149                 cmp = phi_compare(phi1, phi2);
 150                 if (cmp)
 151                         return cmp;
 152                 NEXT_PTR_LIST(phi1);
 153                 NEXT_PTR_LIST(phi2);
 154         }
 155         /* Not reached, but we need to make the nesting come out right */
 156         FINISH_PTR_LIST(phi2);
 157         FINISH_PTR_LIST(phi1);
 158 }
 159
 160 static int insn_compare(const void *_i1, const void *_i2)
 161 {
 162         const struct instruction *i1 = _i1;
 163         const struct instruction *i2 = _i2;
 164
 165         if (i1->opcode != i2->opcode)
 166                 return i1->opcode < i2->opcode ? -1 : 1;
 167
 168         switch (i1->opcode) {
 169
 170         /* Binary arithmetic */
 171         case OP_ADD: case OP_SUB:
 172         case OP_MUL: case OP_DIV:
 173         case OP_MOD: case OP_SHL:
 174         case OP_SHR: case OP_SEL:
 175         case OP_AND: case OP_OR:
 176
 177         /* Binary logical */
 178         case OP_XOR: case OP_AND_BOOL:
 179         case OP_OR_BOOL:
 180
 181         /* Binary comparison */
 182         case OP_SET_EQ: case OP_SET_NE:
 183         case OP_SET_LE: case OP_SET_GE:
 184         case OP_SET_LT: case OP_SET_GT:
 185         case OP_SET_B:  case OP_SET_A:
 186         case OP_SET_BE: case OP_SET_AE:
 187                 if (i1->src1 != i2->src1)
 188                         return i1->src1 < i2->src1 ? -1 : 1;
 189                 if (i1->src2 != i2->src2)
 190                         return i1->src2 < i2->src2 ? -1 : 1;
 191                 break;
 192
 193         /* Unary */
 194         case OP_NOT: case OP_NEG:
 195                 if (i1->src1 != i2->src1)
 196                         return i1->src1 < i2->src1 ? -1 : 1;
 197                 break;
 198
 199         case OP_SETVAL:
 200                 if (i1->val != i2->val)
 201                         return i1->val < i2->val ? -1 : 1;
 202                 if (i1->symbol != i2->symbol)
 203                         return i1->symbol < i2->symbol ? -1 : 1;
 204                 break;
 205
 206         /* Other */
 207         case OP_PHI:
 208                 return phi_list_compare(i1->phi_list, i2->phi_list);
 209
 210         default:
 211                 warning(i1->bb->pos, "bad instruction on hash chain");
 212         }
 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         /* We re-use the "convert_load_insn()" function. Does the same thing */
 224         convert_load_insn(insn, def->target);
 225         return def;
 226 }
 227
 228 static struct instruction * try_to_cse(struct instruction *i1, struct instruction *i2)
 229 {
 230         struct basic_block *b1, *b2;
 231
 232         /*
 233          * Ok, i1 and i2 are the same instruction, modulo "target".
 234          * We should now see if we can combine them.
 235          */
 236         b1 = i1->bb;
 237         b2 = i2->bb;
 238
 239         /*
 240          * Currently we only handle the uninteresting degenerate case where
 241          * the CSE is inside one basic-block.
 242          */
 243         if (b1 == b2) {
 244                 struct instruction *insn;
 245                 FOR_EACH_PTR(b1->insns, insn) {
 246                         if (insn == i1)
 247                                 return cse_one_instruction(i2, i1);
 248                         if (insn == i2)
 249                                 return cse_one_instruction(i1, i2);
 250                 } END_FOR_EACH_PTR(insn);
 251                 warning(b1->pos, "Whaa? unable to find CSE instructions");
 252         }
 253         return NULL;
 254 }
 255
 256 void cleanup_and_cse(struct entrypoint *ep)
 257 {
 258         int i, success;
 259
 260 repeat:
 261         success = 0;
 262         clean_up_insns(ep);
 263         for (i = 0; i < INSN_HASH_SIZE; i++) {
 264                 struct instruction_list **list = insn_hash_table + i;
 265                 if (*list) {
 266                         if (instruction_list_size(*list) > 1) {
 267                                 struct instruction *insn, *last;
 268
 269                                 sort_instruction_list(list);
 270
 271                                 last = NULL;
 272                                 FOR_EACH_PTR(*list, insn) {
 273                                         if (last) {
 274                                                 if (!insn_compare(last, insn)) {
 275                                                         struct instruction *def = try_to_cse(last, insn);
 276                                                         if (def) {
 277                                                                 success++;
 278                                                                 insn = def;
 279                                                         }
 280                                                 }
 281                                         }
 282                                         last = insn;
 283                                 } END_FOR_EACH_PTR(insn);
 284                         }
 285                         free_ptr_list((struct ptr_list **)list);
 286                 }
 287         }
 288
 289         if (success)
 290                 goto repeat;
 291 }