Print this page
11972 resync smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/cse.c
+++ new/usr/src/tools/smatch/src/cse.c
1 1 /*
2 2 * CSE - walk the linearized instruction flow, and
3 3 * see if we can simplify it and apply CSE on it.
4 4 *
5 5 * Copyright (C) 2004 Linus Torvalds
6 6 */
|
↓ open down ↓ |
6 lines elided |
↑ open up ↑ |
7 7
8 8 #include <string.h>
9 9 #include <stdarg.h>
10 10 #include <stdlib.h>
11 11 #include <stdio.h>
12 12 #include <stddef.h>
13 13 #include <assert.h>
14 14
15 15 #include "parse.h"
16 16 #include "expression.h"
17 +#include "flowgraph.h"
17 18 #include "linearize.h"
18 19 #include "flow.h"
20 +#include "cse.h"
19 21
20 22 #define INSN_HASH_SIZE 256
21 23 static struct instruction_list *insn_hash_table[INSN_HASH_SIZE];
22 24
23 -int repeat_phase;
24 -
25 25 static int phi_compare(pseudo_t phi1, pseudo_t phi2)
26 26 {
27 27 const struct instruction *def1 = phi1->def;
28 28 const struct instruction *def2 = phi2->def;
29 29
30 30 if (def1->src1 != def2->src1)
31 31 return def1->src1 < def2->src1 ? -1 : 1;
32 32 if (def1->bb != def2->bb)
33 33 return def1->bb < def2->bb ? -1 : 1;
34 34 return 0;
35 35 }
36 36
37 37
38 -static void clean_up_one_instruction(struct basic_block *bb, struct instruction *insn)
38 +void cse_collect(struct instruction *insn)
39 39 {
40 40 unsigned long hash;
41 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 42 hash = (insn->opcode << 3) + (insn->size >> 3);
49 43 switch (insn->opcode) {
50 44 case OP_SEL:
51 45 hash += hashval(insn->src3);
52 46 /* Fall through */
53 47
54 48 /* Binary arithmetic */
55 49 case OP_ADD: case OP_SUB:
56 - case OP_MULU: case OP_MULS:
50 + case OP_MUL:
57 51 case OP_DIVU: case OP_DIVS:
58 52 case OP_MODU: case OP_MODS:
59 53 case OP_SHL:
60 54 case OP_LSR: case OP_ASR:
61 55 case OP_AND: case OP_OR:
62 56
63 57 /* Binary logical */
64 - case OP_XOR: case OP_AND_BOOL:
65 - case OP_OR_BOOL:
58 + case OP_XOR:
66 59
67 60 /* Binary comparison */
68 61 case OP_SET_EQ: case OP_SET_NE:
69 62 case OP_SET_LE: case OP_SET_GE:
70 63 case OP_SET_LT: case OP_SET_GT:
71 64 case OP_SET_B: case OP_SET_A:
72 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 73 hash += hashval(insn->src2);
74 74 /* Fall through */
75 75
76 76 /* Unary */
77 77 case OP_NOT: case OP_NEG:
78 + case OP_FNEG:
79 + case OP_SYMADDR:
78 80 hash += hashval(insn->src1);
79 81 break;
80 82
81 83 case OP_SETVAL:
82 84 hash += hashval(insn->val);
83 85 break;
84 86
85 - case OP_SYMADDR:
86 - hash += hashval(insn->symbol);
87 + case OP_SETFVAL:
88 + hash += hashval(insn->fvalue);
87 89 break;
88 90
89 - case OP_CAST:
90 - case OP_SCAST:
91 + case OP_SEXT: case OP_ZEXT:
92 + case OP_TRUNC:
91 93 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);
94 + case OP_UTPTR: case OP_PTRTU:
95 + if (!insn->orig_type || insn->orig_type->bit_size < 0)
96 + return;
99 97 hash += hashval(insn->src);
98 +
99 + // Note: see corresponding line in insn_compare()
100 + hash += hashval(insn->orig_type->bit_size);
100 101 break;
101 102
102 103 /* Other */
103 104 case OP_PHI: {
104 105 pseudo_t phi;
105 106 FOR_EACH_PTR(insn->phi_list, phi) {
106 107 struct instruction *def;
107 108 if (phi == VOID || !phi->def)
108 109 continue;
109 110 def = phi->def;
110 111 hash += hashval(def->src1);
111 112 hash += hashval(def->bb);
112 113 } END_FOR_EACH_PTR(phi);
113 114 break;
114 115 }
115 116
116 117 default:
117 118 /*
|
↓ open down ↓ |
8 lines elided |
↑ open up ↑ |
118 119 * Nothing to do, don't even bother hashing them,
119 120 * we're not going to try to CSE them
120 121 */
121 122 return;
122 123 }
123 124 hash += hash >> 16;
124 125 hash &= INSN_HASH_SIZE-1;
125 126 add_instruction(insn_hash_table + hash, insn);
126 127 }
127 128
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 129 /* Compare two (sorted) phi-lists */
141 130 static int phi_list_compare(struct pseudo_list *l1, struct pseudo_list *l2)
142 131 {
143 132 pseudo_t phi1, phi2;
144 133
145 134 PREPARE_PTR_LIST(l1, phi1);
146 135 PREPARE_PTR_LIST(l2, phi2);
147 136 for (;;) {
148 137 int cmp;
149 138
150 139 while (phi1 && (phi1 == VOID || !phi1->def))
151 140 NEXT_PTR_LIST(phi1);
152 141 while (phi2 && (phi2 == VOID || !phi2->def))
153 142 NEXT_PTR_LIST(phi2);
154 143
155 144 if (!phi1)
156 145 return phi2 ? -1 : 0;
157 146 if (!phi2)
158 147 return phi1 ? 1 : 0;
159 148 cmp = phi_compare(phi1, phi2);
160 149 if (cmp)
161 150 return cmp;
162 151 NEXT_PTR_LIST(phi1);
163 152 NEXT_PTR_LIST(phi2);
|
↓ open down ↓ |
14 lines elided |
↑ open up ↑ |
164 153 }
165 154 /* Not reached, but we need to make the nesting come out right */
166 155 FINISH_PTR_LIST(phi2);
167 156 FINISH_PTR_LIST(phi1);
168 157 }
169 158
170 159 static int insn_compare(const void *_i1, const void *_i2)
171 160 {
172 161 const struct instruction *i1 = _i1;
173 162 const struct instruction *i2 = _i2;
163 + int size1, size2;
164 + int diff;
174 165
175 166 if (i1->opcode != i2->opcode)
176 167 return i1->opcode < i2->opcode ? -1 : 1;
177 168
178 169 switch (i1->opcode) {
179 170
180 171 /* commutative binop */
181 172 case OP_ADD:
182 - case OP_MULU: case OP_MULS:
183 - case OP_AND_BOOL: case OP_OR_BOOL:
173 + case OP_MUL:
184 174 case OP_AND: case OP_OR:
185 175 case OP_XOR:
186 176 case OP_SET_EQ: case OP_SET_NE:
187 177 if (i1->src1 == i2->src2 && i1->src2 == i2->src1)
188 178 return 0;
189 179 goto case_binops;
190 180
191 181 case OP_SEL:
192 182 if (i1->src3 != i2->src3)
193 183 return i1->src3 < i2->src3 ? -1 : 1;
194 184 /* Fall-through to binops */
195 185
196 186 /* Binary arithmetic */
197 187 case OP_SUB:
|
↓ open down ↓ |
4 lines elided |
↑ open up ↑ |
198 188 case OP_DIVU: case OP_DIVS:
199 189 case OP_MODU: case OP_MODS:
200 190 case OP_SHL:
201 191 case OP_LSR: case OP_ASR:
202 192
203 193 /* Binary comparison */
204 194 case OP_SET_LE: case OP_SET_GE:
205 195 case OP_SET_LT: case OP_SET_GT:
206 196 case OP_SET_B: case OP_SET_A:
207 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:
208 205 case_binops:
209 206 if (i1->src2 != i2->src2)
210 207 return i1->src2 < i2->src2 ? -1 : 1;
211 208 /* Fall through to unops */
212 209
213 210 /* Unary */
214 211 case OP_NOT: case OP_NEG:
212 + case OP_FNEG:
213 + case OP_SYMADDR:
215 214 if (i1->src1 != i2->src1)
216 215 return i1->src1 < i2->src1 ? -1 : 1;
217 216 break;
218 217
219 - case OP_SYMADDR:
220 - if (i1->symbol != i2->symbol)
221 - return i1->symbol < i2->symbol ? -1 : 1;
222 - break;
223 -
224 218 case OP_SETVAL:
225 219 if (i1->val != i2->val)
226 220 return i1->val < i2->val ? -1 : 1;
227 221 break;
228 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 229 /* Other */
230 230 case OP_PHI:
231 231 return phi_list_compare(i1->phi_list, i2->phi_list);
232 232
233 - case OP_CAST:
234 - case OP_SCAST:
233 + case OP_SEXT: case OP_ZEXT:
234 + case OP_TRUNC:
235 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;
236 + case OP_UTPTR: case OP_PTRTU:
241 237 if (i1->src != i2->src)
242 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;
243 249 break;
244 250
245 251 default:
246 252 warning(i1->pos, "bad instruction on hash chain");
247 253 }
248 254 if (i1->size != i2->size)
249 255 return i1->size < i2->size ? -1 : 1;
250 256 return 0;
251 257 }
252 258
253 259 static void sort_instruction_list(struct instruction_list **list)
254 260 {
255 261 sort_list((struct ptr_list **)list , insn_compare);
256 262 }
|
↓ open down ↓ |
4 lines elided |
↑ open up ↑ |
257 263
258 264 static struct instruction * cse_one_instruction(struct instruction *insn, struct instruction *def)
259 265 {
260 266 convert_instruction_target(insn, def->target);
261 267
262 268 kill_instruction(insn);
263 269 repeat_phase |= REPEAT_CSE;
264 270 return def;
265 271 }
266 272
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 273 static struct basic_block *trivial_common_parent(struct basic_block *bb1, struct basic_block *bb2)
290 274 {
291 275 struct basic_block *parent;
292 276
293 277 if (bb_list_size(bb1->parents) != 1)
294 278 return NULL;
295 279 parent = first_basic_block(bb1->parents);
296 280 if (bb_list_size(bb2->parents) != 1)
297 281 return NULL;
298 282 if (first_basic_block(bb2->parents) != parent)
299 283 return NULL;
300 284 return parent;
301 285 }
302 286
303 287 static inline void remove_instruction(struct instruction_list **list, struct instruction *insn, int count)
304 288 {
305 289 delete_ptr_list_entry((struct ptr_list **)list, insn, count);
306 290 }
307 291
308 292 static void add_instruction_to_end(struct instruction *insn, struct basic_block *bb)
309 293 {
310 294 struct instruction *br = delete_last_instruction(&bb->insns);
311 295 insn->bb = bb;
312 296 add_instruction(&bb->insns, insn);
313 297 add_instruction(&bb->insns, br);
314 298 }
315 299
316 300 static struct instruction * try_to_cse(struct entrypoint *ep, struct instruction *i1, struct instruction *i2)
317 301 {
318 302 struct basic_block *b1, *b2, *common;
319 303
320 304 /*
321 305 * OK, i1 and i2 are the same instruction, modulo "target".
322 306 * We should now see if we can combine them.
323 307 */
324 308 b1 = i1->bb;
325 309 b2 = i2->bb;
326 310
327 311 /*
328 312 * Currently we only handle the uninteresting degenerate case where
329 313 * the CSE is inside one basic-block.
330 314 */
331 315 if (b1 == b2) {
|
↓ open down ↓ |
33 lines elided |
↑ open up ↑ |
332 316 struct instruction *insn;
333 317 FOR_EACH_PTR(b1->insns, insn) {
334 318 if (insn == i1)
335 319 return cse_one_instruction(i2, i1);
336 320 if (insn == i2)
337 321 return cse_one_instruction(i1, i2);
338 322 } END_FOR_EACH_PTR(insn);
339 323 warning(b1->pos, "Whaa? unable to find CSE instructions");
340 324 return i1;
341 325 }
342 - if (bb_dominates(ep, b1, b2, ++bb_generation))
326 + if (domtree_dominates(b1, b2))
343 327 return cse_one_instruction(i2, i1);
344 328
345 - if (bb_dominates(ep, b2, b1, ++bb_generation))
329 + if (domtree_dominates(b2, b1))
346 330 return cse_one_instruction(i1, i2);
347 331
348 332 /* No direct dominance - but we could try to find a common ancestor.. */
349 333 common = trivial_common_parent(b1, b2);
350 334 if (common) {
351 335 i1 = cse_one_instruction(i2, i1);
352 336 remove_instruction(&b1->insns, i1, 1);
353 337 add_instruction_to_end(i1, common);
338 + } else {
339 + i1 = i2;
354 340 }
355 341
356 342 return i1;
357 343 }
358 344
359 -void cleanup_and_cse(struct entrypoint *ep)
345 +void cse_eliminate(struct entrypoint *ep)
360 346 {
361 347 int i;
362 348
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 349 for (i = 0; i < INSN_HASH_SIZE; i++) {
370 350 struct instruction_list **list = insn_hash_table + i;
371 351 if (*list) {
372 352 if (instruction_list_size(*list) > 1) {
373 353 struct instruction *insn, *last;
374 354
375 355 sort_instruction_list(list);
376 356
377 357 last = NULL;
378 358 FOR_EACH_PTR(*list, insn) {
379 359 if (!insn->bb)
380 360 continue;
381 361 if (last) {
382 362 if (!insn_compare(last, insn))
383 363 insn = try_to_cse(ep, last, insn);
384 364 }
385 365 last = insn;
386 366 } END_FOR_EACH_PTR(insn);
387 367 }
388 - free_ptr_list((struct ptr_list **)list);
368 + free_ptr_list(list);
389 369 }
390 370 }
391 -
392 - if (repeat_phase & REPEAT_SYMBOL_CLEANUP)
393 - simplify_memops(ep);
394 -
395 - if (repeat_phase & REPEAT_CSE)
396 - goto repeat;
397 371 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX