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