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 if (repeat_phase & REPEAT_CFG_CLEANUP) 368 kill_unreachable_bbs(ep); 369 for (i = 0; i < INSN_HASH_SIZE; i++) { 370 struct instruction_list **list = insn_hash_table + i; 371 if (*list) { 372 if (instruction_list_size(*list) > 1) { 373 struct instruction *insn, *last; 374 375 sort_instruction_list(list); 376 377 last = NULL; 378 FOR_EACH_PTR(*list, insn) { 379 if (!insn->bb) 380 continue; 381 if (last) { 382 if (!insn_compare(last, insn)) 383 insn = try_to_cse(ep, last, insn); 384 } 385 last = insn; 386 } END_FOR_EACH_PTR(insn); 387 } 388 free_ptr_list((struct ptr_list **)list); 389 } 390 } 391 392 if (repeat_phase & REPEAT_SYMBOL_CLEANUP) 393 simplify_memops(ep); 394 395 if (repeat_phase & REPEAT_CSE) 396 goto repeat; 397 } 398