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
phi_compare(pseudo_t phi1,pseudo_t phi2)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
cse_collect(struct instruction * insn)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_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 */
phi_list_compare(struct pseudo_list * l1,struct pseudo_list * l2)134 static 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
insn_compare(const void * _i1,const void * _i2)163 static 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
sort_instruction_list(struct instruction_list ** list)268 static void sort_instruction_list(struct instruction_list **list)
269 {
270 sort_list((struct ptr_list **)list , insn_compare);
271 }
272
cse_one_instruction(struct instruction * insn,struct instruction * def)273 static 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
trivial_common_parent(struct basic_block * bb1,struct basic_block * bb2)282 static 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
remove_instruction(struct instruction_list ** list,struct instruction * insn,int count)296 static 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
try_to_cse(struct entrypoint * ep,struct instruction * i1,struct instruction * i2)301 static 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
cse_eliminate(struct entrypoint * ep)346 void 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