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)
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 }
|
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)
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 }
|