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 }