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 23static struct instruction_list *insn_hash_table[INSN_HASH_SIZE]; 24 25static 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 38void 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_LABEL: 84 hash += hashval(insn->bb_true); 85 break; 86 87 case OP_SETVAL: 88 hash += hashval(insn->val); 89 break; 90 91 case OP_SETFVAL: 92 hash += hashval(insn->fvalue); 93 break; 94 95 case OP_SEXT: case OP_ZEXT: 96 case OP_TRUNC: 97 case OP_PTRCAST: 98 case OP_UTPTR: case OP_PTRTU: 99 if (!insn->orig_type || insn->orig_type->bit_size < 0) 100 return; 101 hash += hashval(insn->src); 102 103 // Note: see corresponding line in insn_compare() 104 hash += hashval(insn->orig_type->bit_size); 105 break; 106 107 /* Other */ 108 case OP_PHI: { 109 pseudo_t phi; 110 FOR_EACH_PTR(insn->phi_list, phi) { 111 struct instruction *def; 112 if (phi == VOID || !phi->def) 113 continue; 114 def = phi->def; 115 hash += hashval(def->src1); 116 hash += hashval(def->bb); 117 } END_FOR_EACH_PTR(phi); 118 break; 119 } 120 121 default: 122 /* 123 * Nothing to do, don't even bother hashing them, 124 * we're not going to try to CSE them 125 */ 126 return; 127 } 128 hash += hash >> 16; 129 hash &= INSN_HASH_SIZE-1; 130 add_instruction(insn_hash_table + hash, insn); 131} 132 133/* Compare two (sorted) phi-lists */ 134static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2) 135{ 136 pseudo_t phi1, phi2; 137 138 PREPARE_PTR_LIST(l1, phi1); 139 PREPARE_PTR_LIST(l2, phi2); 140 for (;;) { 141 int cmp; 142 143 while (phi1 && (phi1 == VOID || !phi1->def)) 144 NEXT_PTR_LIST(phi1); 145 while (phi2 && (phi2 == VOID || !phi2->def)) 146 NEXT_PTR_LIST(phi2); 147 148 if (!phi1) 149 return phi2 ? -1 : 0; 150 if (!phi2) 151 return phi1 ? 1 : 0; 152 cmp = phi_compare(phi1, phi2); 153 if (cmp) 154 return cmp; 155 NEXT_PTR_LIST(phi1); 156 NEXT_PTR_LIST(phi2); 157 } 158 /* Not reached, but we need to make the nesting come out right */ 159 FINISH_PTR_LIST(phi2); 160 FINISH_PTR_LIST(phi1); 161} 162 163static int insn_compare(const void *_i1, const void *_i2) 164{ 165 const struct instruction *i1 = _i1; 166 const struct instruction *i2 = _i2; 167 int size1, size2; 168 int diff; 169 170 if (i1->opcode != i2->opcode) 171 return i1->opcode < i2->opcode ? -1 : 1; 172 173 switch (i1->opcode) { 174 175 /* commutative binop */ 176 case OP_ADD: 177 case OP_MUL: 178 case OP_AND: case OP_OR: 179 case OP_XOR: 180 case OP_SET_EQ: case OP_SET_NE: 181 if (i1->src1 == i2->src2 && i1->src2 == i2->src1) 182 return 0; 183 goto case_binops; 184 185 case OP_SEL: 186 if (i1->src3 != i2->src3) 187 return i1->src3 < i2->src3 ? -1 : 1; 188 /* Fall-through to binops */ 189 190 /* Binary arithmetic */ 191 case OP_SUB: 192 case OP_DIVU: case OP_DIVS: 193 case OP_MODU: case OP_MODS: 194 case OP_SHL: 195 case OP_LSR: case OP_ASR: 196 197 /* Binary comparison */ 198 case OP_SET_LE: case OP_SET_GE: 199 case OP_SET_LT: case OP_SET_GT: 200 case OP_SET_B: case OP_SET_A: 201 case OP_SET_BE: case OP_SET_AE: 202 203 /* floating-point arithmetic */ 204 case OP_FPCMP ... OP_FPCMP_END: 205 case OP_FADD: 206 case OP_FSUB: 207 case OP_FMUL: 208 case OP_FDIV: 209 case_binops: 210 if (i1->src2 != i2->src2) 211 return i1->src2 < i2->src2 ? -1 : 1; 212 /* Fall through to unops */ 213 214 /* Unary */ 215 case OP_NOT: case OP_NEG: 216 case OP_FNEG: 217 case OP_SYMADDR: 218 if (i1->src1 != i2->src1) 219 return i1->src1 < i2->src1 ? -1 : 1; 220 break; 221 222 case OP_LABEL: 223 if (i1->bb_true != i2->bb_true) 224 return i1->bb_true < i2->bb_true ? -1 : 1; 225 break; 226 227 case OP_SETVAL: 228 if (i1->val != i2->val) 229 return i1->val < i2->val ? -1 : 1; 230 break; 231 232 case OP_SETFVAL: 233 diff = memcmp(&i1->fvalue, &i2->fvalue, sizeof(i1->fvalue)); 234 if (diff) 235 return diff; 236 break; 237 238 /* Other */ 239 case OP_PHI: 240 return phi_list_compare(i1->phi_list, i2->phi_list); 241 242 case OP_SEXT: case OP_ZEXT: 243 case OP_TRUNC: 244 case OP_PTRCAST: 245 case OP_UTPTR: case OP_PTRTU: 246 if (i1->src != i2->src) 247 return i1->src < i2->src ? -1 : 1; 248 249 // Note: if it can be guaranted that identical ->src 250 // implies identical orig_type->bit_size, then this 251 // test and the hashing of the original size in 252 // cse_collect() are not needed. 253 // It must be generaly true but it isn't guaranted (yet). 254 size1 = i1->orig_type->bit_size; 255 size2 = i2->orig_type->bit_size; 256 if (size1 != size2) 257 return size1 < size2 ? -1 : 1; 258 break; 259 260 default: 261 warning(i1->pos, "bad instruction on hash chain"); 262 } 263 if (i1->size != i2->size) 264 return i1->size < i2->size ? -1 : 1; 265 return 0; 266} 267 268static void sort_instruction_list(struct instruction_list **list) 269{ 270 sort_list((struct ptr_list **)list , insn_compare); 271} 272 273static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def) 274{ 275 convert_instruction_target(insn, def->target); 276 277 kill_instruction(insn); 278 repeat_phase |= REPEAT_CSE; 279 return def; 280} 281 282static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2) 283{ 284 struct basic_block *parent; 285 286 if (bb_list_size(bb1->parents) != 1) 287 return NULL; 288 parent = first_basic_block(bb1->parents); 289 if (bb_list_size(bb2->parents) != 1) 290 return NULL; 291 if (first_basic_block(bb2->parents) != parent) 292 return NULL; 293 return parent; 294} 295 296static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count) 297{ 298 delete_ptr_list_entry((struct ptr_list **)list, insn, count); 299} 300 301static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2) 302{ 303 struct basic_block *b1, *b2, *common; 304 305 /* 306 * OK, i1 and i2 are the same instruction, modulo "target". 307 * We should now see if we can combine them. 308 */ 309 b1 = i1->bb; 310 b2 = i2->bb; 311 312 /* 313 * Currently we only handle the uninteresting degenerate case where 314 * the CSE is inside one basic-block. 315 */ 316 if (b1 == b2) { 317 struct instruction *insn; 318 FOR_EACH_PTR(b1->insns, insn) { 319 if (insn == i1) 320 return cse_one_instruction(i2, i1); 321 if (insn == i2) 322 return cse_one_instruction(i1, i2); 323 } END_FOR_EACH_PTR(insn); 324 warning(b1->pos, "Whaa? unable to find CSE instructions"); 325 return i1; 326 } 327 if (domtree_dominates(b1, b2)) 328 return cse_one_instruction(i2, i1); 329 330 if (domtree_dominates(b2, b1)) 331 return cse_one_instruction(i1, i2); 332 333 /* No direct dominance - but we could try to find a common ancestor.. */ 334 common = trivial_common_parent(b1, b2); 335 if (common) { 336 i1 = cse_one_instruction(i2, i1); 337 remove_instruction(&b1->insns, i1, 1); 338 insert_last_instruction(common, i1); 339 } else { 340 i1 = i2; 341 } 342 343 return i1; 344} 345 346void cse_eliminate(struct entrypoint *ep) 347{ 348 int i; 349 350 for (i = 0; i < INSN_HASH_SIZE; i++) { 351 struct instruction_list **list = insn_hash_table + i; 352 if (*list) { 353 if (instruction_list_size(*list) > 1) { 354 struct instruction *insn, *last; 355 356 sort_instruction_list(list); 357 358 last = NULL; 359 FOR_EACH_PTR(*list, insn) { 360 if (!insn->bb) 361 continue; 362 if (last) { 363 if (!insn_compare(last, insn)) 364 insn = try_to_cse(ep, last, insn); 365 } 366 last = insn; 367 } END_FOR_EACH_PTR(insn); 368 } 369 free_ptr_list(list); 370 } 371 } 372} 373