Print this page
new smatch
| Split |
Close |
| Expand all |
| Collapse all |
--- old/usr/src/tools/smatch/src/simplify.c
+++ new/usr/src/tools/smatch/src/simplify.c
1 1 /*
2 2 * Simplify - do instruction simplification before CSE
3 3 *
4 4 * Copyright (C) 2004 Linus Torvalds
5 5 */
6 6
7 +///
8 +// Instruction simplification
9 +// --------------------------
10 +//
11 +// Notation
12 +// ^^^^^^^^
13 +// The following conventions are used to describe the simplications:
14 +// * Uppercase letters are reserved for constants:
15 +// * `M` for a constant mask,
16 +// * `S` for a constant shift,
17 +// * `N` for a constant number of bits (usually other than a shift),
18 +// * `C` or 'K' for others constants.
19 +// * Lowercase letters `a`, `b`, `x`, `y`, ... are used for non-constants
20 +// or when it doesn't matter if the pseudo is a constant or not.
21 +// * Primes are used if needed to distinguish symbols (`M`, `M'`, ...).
22 +// * Expressions or sub-expressions involving only constants are
23 +// understood to be evaluated.
24 +// * `$mask(N)` is used for `((1 << N) -1)`
25 +// * `$trunc(x, N)` is used for `(x & $mask(N))`
26 +// * Expressions like `(-1 << S)`, `(-1 >> S)` and others formulae are
27 +// understood to be truncated to the size of the current instruction
28 +// (needed, since in general this size is not the same as the one used
29 +// by sparse for the evaluation of arithmetic operations).
30 +// * `TRUNC(x, N)` is used for a truncation *to* a size of `N` bits
31 +// * `ZEXT(x, N)` is used for a zero-extension *from* a size of `N` bits
32 +// * `OP(x, C)` is used to represent some generic operation using a constant,
33 +// including when the constant is implicit (e.g. `TRUNC(x, N)`).
34 +// * `MASK(x, M)` is used to respresent a 'masking' instruction:
35 +// - `AND(x, M)`
36 +// - `LSR(x, S)`, with `M` = (-1 << S)
37 +// - `SHL(x, S)`, with `M` = (-1 >> S)
38 +// - `TRUNC(x, N)`, with `M` = $mask(N)
39 +// - `ZEXT(x, N)`, with `M` = $mask(N)
40 +// * `SHIFT(x, S)` is used for `LSR(x, S)` or `SHL(x, S)`.
41 +
7 42 #include <assert.h>
8 43
9 44 #include "parse.h"
10 45 #include "expression.h"
11 46 #include "linearize.h"
12 47 #include "flow.h"
13 48 #include "symbol.h"
14 49
15 -/* Find the trivial parent for a phi-source */
50 +///
51 +// Utilities
52 +// ^^^^^^^^^
53 +
54 +///
55 +// find the trivial parent for a phi-source
16 56 static struct basic_block *phi_parent(struct basic_block *source, pseudo_t pseudo)
17 57 {
18 58 /* Can't go upwards if the pseudo is defined in the bb it came from.. */
19 59 if (pseudo->type == PSEUDO_REG) {
20 60 struct instruction *def = pseudo->def;
21 61 if (def->bb == source)
22 62 return source;
23 63 }
24 64 if (bb_list_size(source->children) != 1 || bb_list_size(source->parents) != 1)
25 65 return source;
26 66 return first_basic_block(source->parents);
27 67 }
28 68
29 -/*
30 - * Copy the phi-node's phisrcs into to given array.
31 - * Returns 0 if the the list contained the expected
32 - * number of element, a positive number if there was
33 - * more than expected and a negative one if less.
34 - *
35 - * Note: we can't reuse a function like linearize_ptr_list()
36 - * because any VOIDs in the phi-list must be ignored here
37 - * as in this context they mean 'entry has been removed'.
38 - */
69 +///
70 +// copy the phi-node's phisrcs into to given array
71 +// @return: 0 if the the list contained the expected
72 +// number of element, a positive number if there was
73 +// more than expected and a negative one if less.
74 +//
75 +// :note: we can't reuse a function like linearize_ptr_list()
76 +// because any VOIDs in the phi-list must be ignored here
77 +// as in this context they mean 'entry has been removed'.
39 78 static int get_phisources(struct instruction *sources[], int nbr, struct instruction *insn)
40 79 {
41 80 pseudo_t phi;
42 81 int i = 0;
43 82
44 83 assert(insn->opcode == OP_PHI);
45 84 FOR_EACH_PTR(insn->phi_list, phi) {
46 85 struct instruction *def;
47 86 if (phi == VOID)
48 87 continue;
49 88 if (i >= nbr)
50 89 return 1;
51 90 def = phi->def;
52 91 assert(def->opcode == OP_PHISOURCE);
53 92 sources[i++] = def;
54 93 } END_FOR_EACH_PTR(phi);
55 94 return i - nbr;
56 95 }
57 96
58 97 static int if_convert_phi(struct instruction *insn)
59 98 {
60 99 struct instruction *array[2];
|
↓ open down ↓ |
12 lines elided |
↑ open up ↑ |
61 100 struct basic_block *parents[3];
62 101 struct basic_block *bb, *bb1, *bb2, *source;
63 102 struct instruction *br;
64 103 pseudo_t p1, p2;
65 104
66 105 bb = insn->bb;
67 106 if (get_phisources(array, 2, insn))
68 107 return 0;
69 108 if (linearize_ptr_list((struct ptr_list *)bb->parents, (void **)parents, 3) != 2)
70 109 return 0;
71 - p1 = array[0]->src1;
110 + p1 = array[0]->phi_src;
72 111 bb1 = array[0]->bb;
73 - p2 = array[1]->src1;
112 + p2 = array[1]->phi_src;
74 113 bb2 = array[1]->bb;
75 114
76 115 /* Only try the simple "direct parents" case */
77 116 if ((bb1 != parents[0] || bb2 != parents[1]) &&
78 117 (bb1 != parents[1] || bb2 != parents[0]))
79 118 return 0;
80 119
81 120 /*
82 121 * See if we can find a common source for this..
83 122 */
84 123 source = phi_parent(bb1, p1);
85 124 if (source != phi_parent(bb2, p2))
86 125 return 0;
87 126
88 127 /*
89 128 * Cool. We now know that 'source' is the exclusive
90 129 * parent of both phi-nodes, so the exit at the
91 130 * end of it fully determines which one it is, and
92 131 * we can turn it into a select.
93 132 *
94 133 * HOWEVER, right now we only handle regular
95 134 * conditional branches. No multijumps or computed
96 135 * stuff. Verify that here.
97 136 */
98 137 br = last_instruction(source->insns);
99 138 if (!br || br->opcode != OP_CBR)
100 139 return 0;
101 140
102 141 assert(br->cond);
103 142 assert(br->bb_false);
104 143
105 144 /*
106 145 * We're in business. Match up true/false with p1/p2.
107 146 */
108 147 if (br->bb_true == bb2 || br->bb_false == bb1) {
109 148 pseudo_t p = p1;
110 149 p1 = p2;
111 150 p2 = p;
112 151 }
113 152
114 153 /*
115 154 * OK, we can now replace that last
116 155 *
117 156 * br cond, a, b
118 157 *
119 158 * with the sequence
120 159 *
121 160 * setcc cond
122 161 * select pseudo, p1, p2
123 162 * br cond, a, b
124 163 *
125 164 * and remove the phi-node. If it then
|
↓ open down ↓ |
42 lines elided |
↑ open up ↑ |
126 165 * turns out that 'a' or 'b' is entirely
127 166 * empty (common case), and now no longer
128 167 * a phi-source, we'll be able to simplify
129 168 * the conditional branch too.
130 169 */
131 170 insert_select(source, br, insn, p1, p2);
132 171 kill_instruction(insn);
133 172 return REPEAT_CSE;
134 173 }
135 174
136 -static int clean_up_phi(struct instruction *insn)
175 +///
176 +// detect trivial phi-nodes
177 +// @insn: the phi-node
178 +// @pseudo: the candidate resulting pseudo (NULL when starting)
179 +// @return: the unique result if the phi-node is trivial, NULL otherwise
180 +//
181 +// A phi-node is trivial if it has a single possible result:
182 +// * all operands are the same
183 +// * the operands are themselves defined by a chain or cycle of phi-nodes
184 +// and the set of all operands involved contains a single value
185 +// not defined by these phi-nodes
186 +//
187 +// Since the result is unique, these phi-nodes can be removed.
188 +static pseudo_t trivial_phi(pseudo_t pseudo, struct instruction *insn, struct pseudo_list **list)
137 189 {
190 + pseudo_t target = insn->target;
138 191 pseudo_t phi;
139 - struct instruction *last;
140 - int same;
141 192
142 - last = NULL;
143 - same = 1;
193 + add_pseudo(list, target);
194 +
144 195 FOR_EACH_PTR(insn->phi_list, phi) {
145 196 struct instruction *def;
197 + pseudo_t src;
198 +
146 199 if (phi == VOID)
147 200 continue;
148 201 def = phi->def;
149 - if (def->src1 == VOID || !def->bb)
202 + if (!def->bb)
150 203 continue;
151 - if (last) {
152 - if (last->src1 != def->src1)
153 - same = 0;
204 + src = def->phi_src; // bypass OP_PHISRC & get the real source
205 + if (src == VOID)
154 206 continue;
207 + if (!pseudo) {
208 + pseudo = src;
209 + continue;
155 210 }
156 - last = def;
211 + if (src == pseudo)
212 + continue;
213 + if (src == target)
214 + continue;
215 + if (DEF_OPCODE(def, src) == OP_PHI) {
216 + if (pseudo_in_list(*list, src))
217 + continue;
218 + if ((pseudo = trivial_phi(pseudo, def, list)))
219 + continue;
220 + }
221 + return NULL;
157 222 } END_FOR_EACH_PTR(phi);
158 223
159 - if (same) {
160 - pseudo_t pseudo = last ? last->src1 : VOID;
224 + return pseudo ? pseudo : VOID;
225 +}
226 +
227 +static int clean_up_phi(struct instruction *insn)
228 +{
229 + struct pseudo_list *list = NULL;
230 + pseudo_t pseudo;
231 +
232 + if ((pseudo = trivial_phi(NULL, insn, &list))) {
161 233 convert_instruction_target(insn, pseudo);
162 234 kill_instruction(insn);
163 235 return REPEAT_CSE;
164 236 }
165 237
166 238 return if_convert_phi(insn);
167 239 }
168 240
169 241 static int delete_pseudo_user_list_entry(struct pseudo_user_list **list, pseudo_t *entry, int count)
170 242 {
171 243 struct pseudo_user *pu;
|
↓ open down ↓ |
1 lines elided |
↑ open up ↑ |
172 244
173 245 FOR_EACH_PTR(*list, pu) {
174 246 if (pu->userp == entry) {
175 247 MARK_CURRENT_DELETED(pu);
176 248 if (!--count)
177 249 goto out;
178 250 }
179 251 } END_FOR_EACH_PTR(pu);
180 252 assert(count <= 0);
181 253 out:
182 - if (ptr_list_size((struct ptr_list *) *list) == 0)
254 + if (pseudo_user_list_empty(*list))
183 255 *list = NULL;
184 256 return count;
185 257 }
186 258
187 -static inline void remove_usage(pseudo_t p, pseudo_t *usep)
259 +static inline void rem_usage(pseudo_t p, pseudo_t *usep, int kill)
188 260 {
189 261 if (has_use_list(p)) {
262 + if (p->type == PSEUDO_SYM)
263 + repeat_phase |= REPEAT_SYMBOL_CLEANUP;
190 264 delete_pseudo_user_list_entry(&p->users, usep, 1);
191 - if (!p->users)
265 + if (kill && !p->users)
192 266 kill_instruction(p->def);
193 267 }
194 268 }
195 269
270 +static inline void remove_usage(pseudo_t p, pseudo_t *usep)
271 +{
272 + rem_usage(p, usep, 1);
273 +}
274 +
196 275 void kill_use(pseudo_t *usep)
197 276 {
198 277 if (usep) {
199 278 pseudo_t p = *usep;
200 279 *usep = VOID;
201 - remove_usage(p, usep);
280 + rem_usage(p, usep, 1);
202 281 }
203 282 }
204 283
284 +// Like kill_use() but do not (recursively) kill dead instructions
285 +void remove_use(pseudo_t *usep)
286 +{
287 + pseudo_t p = *usep;
288 + *usep = VOID;
289 + rem_usage(p, usep, 0);
290 +}
291 +
205 292 static void kill_use_list(struct pseudo_list *list)
206 293 {
207 294 pseudo_t p;
208 295 FOR_EACH_PTR(list, p) {
209 296 if (p == VOID)
210 297 continue;
211 298 kill_use(THIS_ADDRESS(p));
212 299 } END_FOR_EACH_PTR(p);
213 300 }
214 301
215 -/*
216 - * kill an instruction:
217 - * - remove it from its bb
218 - * - remove the usage of all its operands
219 - * If forse is zero, the normal case, the function only for
220 - * instructions free of (possible) side-effects. Otherwise
221 - * the function does that unconditionally (must only be used
222 - * for unreachable instructions.
223 - */
224 -void kill_insn(struct instruction *insn, int force)
302 +///
303 +// kill an instruction
304 +// @insn: the instruction to be killed
305 +// @force: if unset, the normal case, the instruction is not killed
306 +// if not free of possible side-effect; if set the instruction
307 +// is unconditionally killed.
308 +//
309 +// The killed instruction is removed from its BB and the usage
310 +// of all its operands are removed. The instruction is also
311 +// marked as killed by setting its ->bb to NULL.
312 +int kill_insn(struct instruction *insn, int force)
225 313 {
226 314 if (!insn || !insn->bb)
227 - return;
315 + return 0;
228 316
229 317 switch (insn->opcode) {
230 318 case OP_SEL:
231 319 case OP_RANGE:
232 320 kill_use(&insn->src3);
233 321 /* fall through */
234 322
235 323 case OP_BINARY ... OP_BINCMP_END:
236 324 kill_use(&insn->src2);
237 325 /* fall through */
238 326
239 - case OP_CAST:
240 - case OP_SCAST:
241 - case OP_FPCAST:
242 - case OP_PTRCAST:
327 + case OP_UNOP ... OP_UNOP_END:
243 328 case OP_SETVAL:
244 - case OP_NOT: case OP_NEG:
245 329 case OP_SLICE:
246 330 kill_use(&insn->src1);
247 331 break;
248 332
249 333 case OP_PHI:
250 334 kill_use_list(insn->phi_list);
251 335 break;
252 336 case OP_PHISOURCE:
253 337 kill_use(&insn->phi_src);
254 338 break;
255 339
256 340 case OP_SYMADDR:
341 + kill_use(&insn->src);
257 342 repeat_phase |= REPEAT_SYMBOL_CLEANUP;
258 343 break;
259 344
260 345 case OP_CBR:
346 + case OP_SWITCH:
261 347 case OP_COMPUTEDGOTO:
262 348 kill_use(&insn->cond);
263 349 break;
264 350
265 351 case OP_CALL:
266 352 if (!force) {
267 353 /* a "pure" function can be killed too */
268 354 if (!(insn->func->type == PSEUDO_SYM))
269 - return;
355 + return 0;
270 356 if (!(insn->func->sym->ctype.modifiers & MOD_PURE))
271 - return;
357 + return 0;
272 358 }
273 359 kill_use_list(insn->arguments);
274 360 if (insn->func->type == PSEUDO_REG)
275 361 kill_use(&insn->func);
276 362 break;
277 363
278 364 case OP_LOAD:
279 - if (!force && insn->type->ctype.modifiers & MOD_VOLATILE)
280 - return;
365 + if (!force && insn->is_volatile)
366 + return 0;
281 367 kill_use(&insn->src);
282 368 break;
283 369
284 370 case OP_STORE:
285 371 if (!force)
286 - return;
372 + return 0;
287 373 kill_use(&insn->src);
288 374 kill_use(&insn->target);
289 375 break;
290 376
291 377 case OP_ENTRY:
292 378 /* ignore */
293 - return;
379 + return 0;
294 380
295 381 case OP_BR:
382 + case OP_SETFVAL:
296 383 default:
297 384 break;
298 385 }
299 386
300 387 insn->bb = NULL;
301 - repeat_phase |= REPEAT_CSE;
302 - return;
388 + return repeat_phase |= REPEAT_CSE;
303 389 }
304 390
305 -/*
306 - * Kill trivially dead instructions
307 - */
391 +///
392 +// kill trivially dead instructions
308 393 static int dead_insn(struct instruction *insn, pseudo_t *src1, pseudo_t *src2, pseudo_t *src3)
309 394 {
310 - struct pseudo_user *pu;
311 - FOR_EACH_PTR(insn->target->users, pu) {
312 - if (*pu->userp != VOID)
313 - return 0;
314 - } END_FOR_EACH_PTR(pu);
395 + if (has_users(insn->target))
396 + return 0;
315 397
316 398 insn->bb = NULL;
317 399 kill_use(src1);
318 400 kill_use(src2);
319 401 kill_use(src3);
320 402 return REPEAT_CSE;
321 403 }
322 404
405 +static inline bool has_target(struct instruction *insn)
406 +{
407 + return opcode_table[insn->opcode].flags & OPF_TARGET;
408 +}
409 +
410 +void remove_dead_insns(struct entrypoint *ep)
411 +{
412 + struct basic_block *bb;
413 +
414 + FOR_EACH_PTR_REVERSE(ep->bbs, bb) {
415 + struct instruction *insn;
416 + FOR_EACH_PTR_REVERSE(bb->insns, insn) {
417 + if (!insn->bb)
418 + continue;
419 + if (!has_target(insn))
420 + continue;
421 + if (!has_users(insn->target))
422 + kill_instruction(insn);
423 + } END_FOR_EACH_PTR_REVERSE(insn);
424 + } END_FOR_EACH_PTR_REVERSE(bb);
425 +}
426 +
323 427 static inline int constant(pseudo_t pseudo)
324 428 {
325 429 return pseudo->type == PSEUDO_VAL;
326 430 }
327 431
432 +///
433 +// replace the operand of an instruction
434 +// @insn: the instruction
435 +// @pp: the address of the instruction's operand
436 +// @new: the new value for the operand
437 +// @return: REPEAT_CSE.
438 +static inline int replace_pseudo(struct instruction *insn, pseudo_t *pp, pseudo_t new)
439 +{
440 + pseudo_t old = *pp;
441 + use_pseudo(insn, new, pp);
442 + remove_usage(old, pp);
443 + return REPEAT_CSE;
444 +}
445 +
328 446 static int replace_with_pseudo(struct instruction *insn, pseudo_t pseudo)
329 447 {
330 448 convert_instruction_target(insn, pseudo);
331 449
332 450 switch (insn->opcode) {
333 451 case OP_SEL:
334 452 case OP_RANGE:
335 453 kill_use(&insn->src3);
336 454 case OP_BINARY ... OP_BINCMP_END:
337 455 kill_use(&insn->src2);
338 - case OP_NOT:
339 - case OP_NEG:
456 + case OP_UNOP ... OP_UNOP_END:
340 457 case OP_SYMADDR:
341 - case OP_CAST:
342 - case OP_SCAST:
343 - case OP_FPCAST:
344 - case OP_PTRCAST:
345 458 kill_use(&insn->src1);
346 459 break;
347 460
348 461 default:
349 462 assert(0);
350 463 }
351 464 insn->bb = NULL;
352 465 return REPEAT_CSE;
353 466 }
354 467
355 -unsigned int value_size(long long value)
468 +static inline int def_opcode(pseudo_t p)
356 469 {
470 + if (p->type != PSEUDO_REG)
471 + return OP_BADOP;
472 + return p->def->opcode;
473 +}
474 +
475 +static unsigned int value_size(long long value)
476 +{
357 477 value >>= 8;
358 478 if (!value)
359 479 return 8;
360 480 value >>= 8;
361 481 if (!value)
362 482 return 16;
363 483 value >>= 16;
364 484 if (!value)
365 485 return 32;
366 486 return 64;
367 487 }
368 488
369 -/*
370 - * Try to determine the maximum size of bits in a pseudo.
371 - *
372 - * Right now this only follow casts and constant values, but we
373 - * could look at things like logical 'and' instructions etc.
374 - */
489 +///
490 +// try to determine the maximum size of bits in a pseudo
491 +//
492 +// Right now this only follow casts and constant values, but we
493 +// could look at things like AND instructions, etc.
375 494 static unsigned int operand_size(struct instruction *insn, pseudo_t pseudo)
376 495 {
377 496 unsigned int size = insn->size;
378 497
379 498 if (pseudo->type == PSEUDO_REG) {
380 499 struct instruction *src = pseudo->def;
381 - if (src && src->opcode == OP_CAST && src->orig_type) {
500 + if (src && src->opcode == OP_ZEXT && src->orig_type) {
382 501 unsigned int orig_size = src->orig_type->bit_size;
383 502 if (orig_size < size)
384 503 size = orig_size;
385 504 }
386 505 }
387 506 if (pseudo->type == PSEUDO_VAL) {
388 507 unsigned int orig_size = value_size(pseudo->value);
389 508 if (orig_size < size)
390 509 size = orig_size;
391 510 }
392 511 return size;
393 512 }
394 513
395 -static int simplify_asr(struct instruction *insn, pseudo_t pseudo, long long value)
514 +static pseudo_t eval_insn(struct instruction *insn)
396 515 {
397 - unsigned int size = operand_size(insn, pseudo);
516 + /* FIXME! Verify signs and sizes!! */
517 + unsigned int size = insn->size;
518 + long long left = insn->src1->value;
519 + long long right = insn->src2->value;
520 + unsigned long long ul, ur;
521 + long long res, mask, bits;
398 522
399 - if (value >= size) {
400 - warning(insn->pos, "right shift by bigger than source value");
401 - return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
523 + mask = 1ULL << (size-1);
524 + bits = mask | (mask-1);
525 +
526 + if (left & mask)
527 + left |= ~bits;
528 + if (right & mask)
529 + right |= ~bits;
530 + ul = left & bits;
531 + ur = right & bits;
532 +
533 + switch (insn->opcode) {
534 + case OP_ADD:
535 + res = left + right;
536 + break;
537 + case OP_SUB:
538 + res = left - right;
539 + break;
540 + case OP_MUL:
541 + res = ul * ur;
542 + break;
543 + case OP_DIVU:
544 + if (!ur)
545 + goto undef;
546 + res = ul / ur;
547 + break;
548 + case OP_DIVS:
549 + if (!right)
550 + goto undef;
551 + if (left == mask && right == -1)
552 + goto undef;
553 + res = left / right;
554 + break;
555 + case OP_MODU:
556 + if (!ur)
557 + goto undef;
558 + res = ul % ur;
559 + break;
560 + case OP_MODS:
561 + if (!right)
562 + goto undef;
563 + if (left == mask && right == -1)
564 + goto undef;
565 + res = left % right;
566 + break;
567 + case OP_SHL:
568 + if (ur >= size)
569 + goto undef;
570 + res = left << right;
571 + break;
572 + case OP_LSR:
573 + if (ur >= size)
574 + goto undef;
575 + res = ul >> ur;
576 + break;
577 + case OP_ASR:
578 + if (ur >= size)
579 + goto undef;
580 + res = left >> right;
581 + break;
582 + /* Logical */
583 + case OP_AND:
584 + res = left & right;
585 + break;
586 + case OP_OR:
587 + res = left | right;
588 + break;
589 + case OP_XOR:
590 + res = left ^ right;
591 + break;
592 +
593 + /* Binary comparison */
594 + case OP_SET_EQ:
595 + res = left == right;
596 + break;
597 + case OP_SET_NE:
598 + res = left != right;
599 + break;
600 + case OP_SET_LE:
601 + res = left <= right;
602 + break;
603 + case OP_SET_GE:
604 + res = left >= right;
605 + break;
606 + case OP_SET_LT:
607 + res = left < right;
608 + break;
609 + case OP_SET_GT:
610 + res = left > right;
611 + break;
612 + case OP_SET_B:
613 + res = ul < ur;
614 + break;
615 + case OP_SET_A:
616 + res = ul > ur;
617 + break;
618 + case OP_SET_BE:
619 + res = ul <= ur;
620 + break;
621 + case OP_SET_AE:
622 + res = ul >= ur;
623 + break;
624 + default:
625 + return NULL;
402 626 }
627 + res &= bits;
628 +
629 + return value_pseudo(res);
630 +
631 +undef:
632 + return NULL;
633 +}
634 +
635 +///
636 +// Simplifications
637 +// ^^^^^^^^^^^^^^^
638 +
639 +///
640 +// try to simplify MASK(OR(AND(x, M'), b), M)
641 +// @insn: the masking instruction
642 +// @mask: the associated mask (M)
643 +// @ora: one of the OR's operands, guaranteed to be PSEUDO_REG
644 +// @orb: the other OR's operand
645 +// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
646 +static int simplify_mask_or_and(struct instruction *insn, unsigned long long mask,
647 + pseudo_t ora, pseudo_t orb)
648 +{
649 + unsigned long long omask, nmask;
650 + struct instruction *and = ora->def;
651 + pseudo_t src2 = and->src2;
652 +
653 + if (and->opcode != OP_AND)
654 + return 0;
655 + if (!constant(src2))
656 + return 0;
657 + omask = src2->value;
658 + nmask = omask & mask;
659 + if (nmask == 0) {
660 + // if (M' & M) == 0: ((a & M') | b) -> b
661 + return replace_pseudo(insn, &insn->src1, orb);
662 + }
663 + if (multi_users(insn->src1))
664 + return 0; // can't modify anything inside the OR
665 + if (nmask == mask) {
666 + struct instruction *or = insn->src1->def;
667 + pseudo_t *arg = (ora == or->src1) ? &or->src1 : &or->src2;
668 + // if (M' & M) == M: ((a & M') | b) -> (a | b)
669 + return replace_pseudo(or, arg, and->src1);
670 + }
671 + if (nmask != omask && !multi_users(ora)) {
672 + // if (M' & M) != M': AND(a, M') -> AND(a, (M' & M))
673 + and->src2 = value_pseudo(nmask);
674 + return REPEAT_CSE;
675 + }
676 + return 0;
677 +}
678 +
679 +///
680 +// try to simplify MASK(OR(a, b), M)
681 +// @insn: the masking instruction
682 +// @mask: the associated mask (M)
683 +// @or: the OR instruction
684 +// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
685 +static int simplify_mask_or(struct instruction *insn, unsigned long long mask, struct instruction *or)
686 +{
687 + pseudo_t src1 = or->src1;
688 + pseudo_t src2 = or->src2;
689 + int rc;
690 +
691 + if (src1->type == PSEUDO_REG) {
692 + if ((rc = simplify_mask_or_and(insn, mask, src1, src2)))
693 + return rc;
694 + }
695 + if (src2->type == PSEUDO_REG) {
696 + if ((rc = simplify_mask_or_and(insn, mask, src2, src1)))
697 + return rc;
698 + } else if (src2->type == PSEUDO_VAL) {
699 + unsigned long long oval = src2->value;
700 + unsigned long long nval = oval & mask;
701 + // Try to simplify:
702 + // MASK(OR(x, C), M)
703 + if (nval == 0) {
704 + // if (C & M) == 0: OR(x, C) -> x
705 + return replace_pseudo(insn, &insn->src1, src1);
706 + }
707 + if (nval == mask) {
708 + // if (C & M) == M: OR(x, C) -> M
709 + return replace_pseudo(insn, &insn->src1, value_pseudo(mask));
710 + }
711 + if (nval != oval && !multi_users(or->target)) {
712 + // if (C & M) != C: OR(x, C) -> OR(x, (C & M))
713 + return replace_pseudo(or, &or->src2, value_pseudo(nval));
714 + }
715 + }
716 + return 0;
717 +}
718 +
719 +///
720 +// try to simplify MASK(SHIFT(OR(a, b), S), M)
721 +// @sh: the shift instruction
722 +// @or: the OR instruction
723 +// @mask: the mask associated to MASK (M):
724 +// @return: 0 if no changes have been made, one or more REPEAT_* flags otherwise.
725 +static int simplify_mask_shift_or(struct instruction *sh, struct instruction *or, unsigned long long mask)
726 +{
727 + unsigned long long smask = bits_mask(sh->size);
728 + int shift = sh->src2->value;
729 +
730 + if (sh->opcode == OP_LSR)
731 + mask <<= shift;
732 + else
733 + mask >>= shift;
734 + return simplify_mask_or(sh, smask & mask, or);
735 +}
736 +
737 +static int simplify_mask_shift(struct instruction *sh, unsigned long long mask)
738 +{
739 + struct instruction *inner;
740 +
741 + if (!constant(sh->src2) || sh->tainted)
742 + return 0;
743 + switch (DEF_OPCODE(inner, sh->src1)) {
744 + case OP_OR:
745 + if (!multi_users(sh->target))
746 + return simplify_mask_shift_or(sh, inner, mask);
747 + break;
748 + }
749 + return 0;
750 +}
751 +
752 +static long long check_shift_count(struct instruction *insn, unsigned long long uval)
753 +{
754 + unsigned int size = insn->size;
755 + long long sval = uval;
756 +
757 + if (uval < size)
758 + return uval;
759 +
760 + sval = sign_extend_safe(sval, size);
761 + sval = sign_extend_safe(sval, bits_in_int);
762 + if (sval < 0)
763 + insn->src2 = value_pseudo(sval);
764 + if (insn->tainted)
765 + return sval;
766 +
767 + if (sval < 0 && Wshift_count_negative)
768 + warning(insn->pos, "shift count is negative (%lld)", sval);
769 + if (sval > 0 && Wshift_count_overflow) {
770 + struct symbol *ctype = insn->type;
771 + const char *tname;
772 + if (ctype->type == SYM_NODE)
773 + ctype = ctype->ctype.base_type;
774 + tname = show_typename(ctype);
775 + warning(insn->pos, "shift too big (%llu) for type %s", sval, tname);
776 + }
777 + insn->tainted = 1;
778 + return sval;
779 +}
780 +
781 +static int simplify_shift(struct instruction *insn, pseudo_t pseudo, long long value)
782 +{
783 + struct instruction *def;
784 + unsigned long long mask, omask, nmask;
785 + unsigned long long nval;
786 + unsigned int size;
787 + pseudo_t src2;
788 +
403 789 if (!value)
404 790 return replace_with_pseudo(insn, pseudo);
791 + value = check_shift_count(insn, value);
792 + if (value < 0)
793 + return 0;
794 +
795 + size = insn->size;
796 + switch (insn->opcode) {
797 + case OP_ASR:
798 + if (value >= size)
799 + return 0;
800 + if (pseudo->type != PSEUDO_REG)
801 + break;
802 + def = pseudo->def;
803 + switch (def->opcode) {
804 + case OP_LSR:
805 + case OP_ASR:
806 + if (def == insn) // cyclic DAG!
807 + break;
808 + src2 = def->src2;
809 + if (src2->type != PSEUDO_VAL)
810 + break;
811 + nval = src2->value;
812 + if (nval > insn->size || nval == 0)
813 + break;
814 + value += nval;
815 + if (def->opcode == OP_LSR)
816 + insn->opcode = OP_LSR;
817 + else if (value >= size)
818 + value = size - 1;
819 + goto new_value;
820 +
821 + case OP_ZEXT:
822 + // transform:
823 + // zext.N %t <- (O) %a
824 + // asr.N %r <- %t, C
825 + // into
826 + // zext.N %t <- (O) %a
827 + // lsr.N %r <- %t, C
828 + insn->opcode = OP_LSR;
829 + return REPEAT_CSE;
830 + }
831 + break;
832 + case OP_LSR:
833 + size = operand_size(insn, pseudo);
834 + if (value >= size)
835 + goto zero;
836 + switch(DEF_OPCODE(def, pseudo)) {
837 + case OP_AND:
838 + // replace (A & M) >> S
839 + // by (A >> S) & (M >> S)
840 + if (!constant(def->src2))
841 + break;
842 + mask = bits_mask(insn->size - value) << value;
843 + omask = def->src2->value;
844 + nmask = omask & mask;
845 + if (nmask == 0)
846 + return replace_with_pseudo(insn, value_pseudo(0));
847 + if (nmask == mask)
848 + return replace_pseudo(insn, &insn->src1, def->src1);
849 + if (nbr_users(pseudo) > 1)
850 + break;
851 + def->opcode = OP_LSR;
852 + def->src2 = insn->src2;
853 + insn->opcode = OP_AND;
854 + insn->src2 = value_pseudo(omask >> value);
855 + return REPEAT_CSE;
856 + case OP_LSR:
857 + goto case_shift_shift;
858 + case OP_OR:
859 + mask = bits_mask(size);
860 + return simplify_mask_shift_or(insn, def, mask);
861 + case OP_SHL:
862 + // replace ((x << S) >> S)
863 + // by (x & (-1 >> S))
864 + if (def->src2 != insn->src2)
865 + break;
866 + mask = bits_mask(insn->size - value);
867 + goto replace_mask;
868 + }
869 + break;
870 + case OP_SHL:
871 + if (value >= size)
872 + goto zero;
873 + switch(DEF_OPCODE(def, pseudo)) {
874 + case OP_AND:
875 + // simplify (A & M) << S
876 + if (!constant(def->src2))
877 + break;
878 + mask = bits_mask(insn->size) >> value;
879 + omask = def->src2->value;
880 + nmask = omask & mask;
881 + if (nmask == 0)
882 + return replace_with_pseudo(insn, value_pseudo(0));
883 + if (nmask == mask)
884 + return replace_pseudo(insn, &insn->src1, def->src1);
885 + // do not simplify into ((A << S) & (M << S))
886 + break;
887 + case OP_LSR:
888 + // replace ((x >> S) << S)
889 + // by (x & (-1 << S))
890 + if (def->src2 != insn->src2)
891 + break;
892 + mask = bits_mask(insn->size - value) << value;
893 + goto replace_mask;
894 + case OP_OR:
895 + mask = bits_mask(size);
896 + return simplify_mask_shift_or(insn, def, mask);
897 + case OP_SHL:
898 + case_shift_shift: // also for LSR - LSR
899 + if (def == insn) // cyclic DAG!
900 + break;
901 + src2 = def->src2;
902 + if (src2->type != PSEUDO_VAL)
903 + break;
904 + nval = src2->value;
905 + if (nval > insn->size)
906 + break;
907 + value += nval;
908 + goto new_value;
909 + }
910 + break;
911 + }
405 912 return 0;
913 +
914 +new_value:
915 + if (value < size) {
916 + insn->src2 = value_pseudo(value);
917 + return replace_pseudo(insn, &insn->src1, pseudo->def->src1);
918 + }
919 +zero:
920 + return replace_with_pseudo(insn, value_pseudo(0));
921 +replace_mask:
922 + insn->opcode = OP_AND;
923 + insn->src2 = value_pseudo(mask);
924 + return replace_pseudo(insn, &insn->src1, def->src1);
406 925 }
407 926
408 927 static int simplify_mul_div(struct instruction *insn, long long value)
409 928 {
410 929 unsigned long long sbit = 1ULL << (insn->size - 1);
411 930 unsigned long long bits = sbit | (sbit - 1);
412 931
413 932 if (value == 1)
414 933 return replace_with_pseudo(insn, insn->src1);
415 934
416 935 switch (insn->opcode) {
417 - case OP_MULS:
418 - case OP_MULU:
936 + case OP_MUL:
419 937 if (value == 0)
420 938 return replace_with_pseudo(insn, insn->src2);
421 939 /* Fall through */
422 940 case OP_DIVS:
423 941 if (!(value & sbit)) // positive
424 942 break;
425 943
426 944 value |= ~bits;
427 945 if (value == -1) {
428 946 insn->opcode = OP_NEG;
429 947 return REPEAT_CSE;
430 948 }
431 949 }
432 950
433 951 return 0;
434 952 }
435 953
436 -static int compare_opcode(int opcode, int inverse)
437 -{
438 - if (!inverse)
439 - return opcode;
440 -
441 - switch (opcode) {
442 - case OP_SET_EQ: return OP_SET_NE;
443 - case OP_SET_NE: return OP_SET_EQ;
444 -
445 - case OP_SET_LT: return OP_SET_GE;
446 - case OP_SET_LE: return OP_SET_GT;
447 - case OP_SET_GT: return OP_SET_LE;
448 - case OP_SET_GE: return OP_SET_LT;
449 -
450 - case OP_SET_A: return OP_SET_BE;
451 - case OP_SET_AE: return OP_SET_B;
452 - case OP_SET_B: return OP_SET_AE;
453 - case OP_SET_BE: return OP_SET_A;
454 -
455 - default:
456 - return opcode;
457 - }
458 -}
459 -
460 954 static int simplify_seteq_setne(struct instruction *insn, long long value)
461 955 {
462 956 pseudo_t old = insn->src1;
463 - struct instruction *def = old->def;
464 - pseudo_t src1, src2;
957 + struct instruction *def;
958 + unsigned osize;
465 959 int inverse;
466 960 int opcode;
467 961
468 962 if (value != 0 && value != 1)
469 963 return 0;
470 964
965 + if (old->type != PSEUDO_REG)
966 + return 0;
967 + def = old->def;
471 968 if (!def)
472 969 return 0;
473 970
474 971 inverse = (insn->opcode == OP_SET_NE) == value;
972 + if (!inverse && def->size == 1 && insn->size == 1) {
973 + // Replace:
974 + // setne %r <- %s, $0
975 + // or:
976 + // seteq %r <- %s, $1
977 + // by %s when boolean
978 + return replace_with_pseudo(insn, old);
979 + }
475 980 opcode = def->opcode;
476 981 switch (opcode) {
477 - case OP_BINCMP ... OP_BINCMP_END:
982 + case OP_AND:
983 + if (inverse)
984 + break;
985 + if (def->size != insn->size)
986 + break;
987 + if (def->src2->type != PSEUDO_VAL)
988 + break;
989 + if (def->src2->value != 1)
990 + break;
991 + return replace_with_pseudo(insn, old);
992 + case OP_FPCMP ... OP_BINCMP_END:
478 993 // Convert:
479 994 // setcc.n %t <- %a, %b
480 995 // setne.m %r <- %t, $0
481 996 // into:
482 997 // setcc.n %t <- %a, %b
483 998 // setcc.m %r <- %a, $b
484 999 // and similar for setne/eq ... 0/1
485 - src1 = def->src1;
486 - src2 = def->src2;
487 - insn->opcode = compare_opcode(opcode, inverse);
488 - use_pseudo(insn, src1, &insn->src1);
489 - use_pseudo(insn, src2, &insn->src2);
1000 + insn->opcode = inverse ? opcode_table[opcode].negate : opcode;
1001 + use_pseudo(insn, def->src1, &insn->src1);
1002 + use_pseudo(insn, def->src2, &insn->src2);
490 1003 remove_usage(old, &insn->src1);
491 1004 return REPEAT_CSE;
492 1005
493 - default:
494 - return 0;
1006 + case OP_SEXT:
1007 + if (value && (def->orig_type->bit_size == 1))
1008 + break;
1009 + /* Fall through */
1010 + case OP_ZEXT:
1011 + // Convert:
1012 + // *ext.m %s <- (1) %a
1013 + // setne.1 %r <- %s, $0
1014 + // into:
1015 + // setne.1 %s <- %a, $0
1016 + // and same for setne/eq ... 0/1
1017 + return replace_pseudo(insn, &insn->src1, def->src);
1018 + case OP_TRUNC:
1019 + if (multi_users(old))
1020 + break;
1021 + // convert
1022 + // trunc.n %s <- (o) %a
1023 + // setne.m %r <- %s, $0
1024 + // into:
1025 + // and.o %s <- %a, $((1 << o) - 1)
1026 + // setne.m %r <- %s, $0
1027 + // and same for setne/eq ... 0/1
1028 + osize = def->size;
1029 + def->opcode = OP_AND;
1030 + def->type = def->orig_type;
1031 + def->size = def->type->bit_size;
1032 + def->src2 = value_pseudo(bits_mask(osize));
1033 + return REPEAT_CSE;
495 1034 }
1035 + return 0;
496 1036 }
497 1037
1038 +static int simplify_constant_mask(struct instruction *insn, unsigned long long mask)
1039 +{
1040 + pseudo_t old = insn->src1;
1041 + unsigned long long omask;
1042 + unsigned long long nmask;
1043 + struct instruction *def;
1044 + int osize;
1045 +
1046 + switch (DEF_OPCODE(def, old)) {
1047 + case OP_FPCMP ... OP_BINCMP_END:
1048 + osize = 1;
1049 + goto oldsize;
1050 + case OP_OR:
1051 + return simplify_mask_or(insn, mask, def);
1052 + case OP_LSR:
1053 + case OP_SHL:
1054 + return simplify_mask_shift(def, mask);
1055 + case OP_ZEXT:
1056 + osize = def->orig_type->bit_size;
1057 + /* fall through */
1058 + oldsize:
1059 + omask = (1ULL << osize) - 1;
1060 + nmask = mask & omask;
1061 + if (nmask == omask)
1062 + // the AND mask is redundant
1063 + return replace_with_pseudo(insn, old);
1064 + if (nmask != mask) {
1065 + // can use a smaller mask
1066 + insn->src2 = value_pseudo(nmask);
1067 + return REPEAT_CSE;
1068 + }
1069 + break;
1070 + }
1071 + return 0;
1072 +}
1073 +
498 1074 static int simplify_constant_rightside(struct instruction *insn)
499 1075 {
500 1076 long long value = insn->src2->value;
1077 + long long sbit = 1ULL << (insn->size - 1);
1078 + long long bits = sbit | (sbit - 1);
501 1079
502 1080 switch (insn->opcode) {
503 - case OP_OR_BOOL:
504 - if (value == 1)
1081 + case OP_OR:
1082 + if ((value & bits) == bits)
505 1083 return replace_with_pseudo(insn, insn->src2);
506 1084 goto case_neutral_zero;
507 1085
1086 + case OP_XOR:
1087 + if ((value & bits) == bits) {
1088 + insn->opcode = OP_NOT;
1089 + return REPEAT_CSE;
1090 + }
1091 + goto case_neutral_zero;
1092 +
508 1093 case OP_SUB:
509 1094 if (value) {
510 1095 insn->opcode = OP_ADD;
511 - insn->src2 = value_pseudo(insn->type, -value);
1096 + insn->src2 = value_pseudo(-value);
512 1097 return REPEAT_CSE;
513 1098 }
514 1099 /* Fall through */
515 1100 case OP_ADD:
516 - case OP_OR: case OP_XOR:
517 - case OP_SHL:
518 - case OP_LSR:
519 1101 case_neutral_zero:
520 1102 if (!value)
521 1103 return replace_with_pseudo(insn, insn->src1);
522 1104 return 0;
523 1105 case OP_ASR:
524 - return simplify_asr(insn, insn->src1, value);
1106 + case OP_SHL:
1107 + case OP_LSR:
1108 + return simplify_shift(insn, insn->src1, value);
525 1109
526 1110 case OP_MODU: case OP_MODS:
527 1111 if (value == 1)
528 - return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
1112 + return replace_with_pseudo(insn, value_pseudo(0));
529 1113 return 0;
530 1114
531 1115 case OP_DIVU: case OP_DIVS:
532 - case OP_MULU: case OP_MULS:
1116 + case OP_MUL:
533 1117 return simplify_mul_div(insn, value);
534 1118
535 - case OP_AND_BOOL:
536 - if (value == 1)
537 - return replace_with_pseudo(insn, insn->src1);
538 - /* Fall through */
539 1119 case OP_AND:
540 1120 if (!value)
541 1121 return replace_with_pseudo(insn, insn->src2);
542 - return 0;
1122 + if ((value & bits) == bits)
1123 + return replace_with_pseudo(insn, insn->src1);
1124 + return simplify_constant_mask(insn, value);
543 1125
544 1126 case OP_SET_NE:
545 1127 case OP_SET_EQ:
546 1128 return simplify_seteq_setne(insn, value);
547 1129 }
548 1130 return 0;
549 1131 }
550 1132
551 1133 static int simplify_constant_leftside(struct instruction *insn)
552 1134 {
553 1135 long long value = insn->src1->value;
|
↓ open down ↓ |
1 lines elided |
↑ open up ↑ |
554 1136
555 1137 switch (insn->opcode) {
556 1138 case OP_ADD: case OP_OR: case OP_XOR:
557 1139 if (!value)
558 1140 return replace_with_pseudo(insn, insn->src2);
559 1141 return 0;
560 1142
561 1143 case OP_SHL:
562 1144 case OP_LSR: case OP_ASR:
563 1145 case OP_AND:
564 - case OP_MULU: case OP_MULS:
1146 + case OP_MUL:
565 1147 if (!value)
566 1148 return replace_with_pseudo(insn, insn->src1);
567 1149 return 0;
568 1150 }
569 1151 return 0;
570 1152 }
571 1153
572 1154 static int simplify_constant_binop(struct instruction *insn)
573 1155 {
574 - /* FIXME! Verify signs and sizes!! */
575 - long long left = insn->src1->value;
576 - long long right = insn->src2->value;
577 - unsigned long long ul, ur;
578 - long long res, mask, bits;
1156 + pseudo_t res = eval_insn(insn);
579 1157
580 - mask = 1ULL << (insn->size-1);
581 - bits = mask | (mask-1);
582 -
583 - if (left & mask)
584 - left |= ~bits;
585 - if (right & mask)
586 - right |= ~bits;
587 - ul = left & bits;
588 - ur = right & bits;
589 -
590 - switch (insn->opcode) {
591 - case OP_ADD:
592 - res = left + right;
593 - break;
594 - case OP_SUB:
595 - res = left - right;
596 - break;
597 - case OP_MULU:
598 - res = ul * ur;
599 - break;
600 - case OP_MULS:
601 - res = left * right;
602 - break;
603 - case OP_DIVU:
604 - if (!ur)
605 - return 0;
606 - res = ul / ur;
607 - break;
608 - case OP_DIVS:
609 - if (!right)
610 - return 0;
611 - if (left == mask && right == -1)
612 - return 0;
613 - res = left / right;
614 - break;
615 - case OP_MODU:
616 - if (!ur)
617 - return 0;
618 - res = ul % ur;
619 - break;
620 - case OP_MODS:
621 - if (!right)
622 - return 0;
623 - if (left == mask && right == -1)
624 - return 0;
625 - res = left % right;
626 - break;
627 - case OP_SHL:
628 - res = left << right;
629 - break;
630 - case OP_LSR:
631 - res = ul >> ur;
632 - break;
633 - case OP_ASR:
634 - res = left >> right;
635 - break;
636 - /* Logical */
637 - case OP_AND:
638 - res = left & right;
639 - break;
640 - case OP_OR:
641 - res = left | right;
642 - break;
643 - case OP_XOR:
644 - res = left ^ right;
645 - break;
646 - case OP_AND_BOOL:
647 - res = left && right;
648 - break;
649 - case OP_OR_BOOL:
650 - res = left || right;
651 - break;
652 -
653 - /* Binary comparison */
654 - case OP_SET_EQ:
655 - res = left == right;
656 - break;
657 - case OP_SET_NE:
658 - res = left != right;
659 - break;
660 - case OP_SET_LE:
661 - res = left <= right;
662 - break;
663 - case OP_SET_GE:
664 - res = left >= right;
665 - break;
666 - case OP_SET_LT:
667 - res = left < right;
668 - break;
669 - case OP_SET_GT:
670 - res = left > right;
671 - break;
672 - case OP_SET_B:
673 - res = ul < ur;
674 - break;
675 - case OP_SET_A:
676 - res = ul > ur;
677 - break;
678 - case OP_SET_BE:
679 - res = ul <= ur;
680 - break;
681 - case OP_SET_AE:
682 - res = ul >= ur;
683 - break;
684 - default:
1158 + if (!res)
685 1159 return 0;
686 - }
687 - res &= bits;
688 1160
689 - replace_with_pseudo(insn, value_pseudo(insn->type, res));
1161 + replace_with_pseudo(insn, res);
690 1162 return REPEAT_CSE;
691 1163 }
692 1164
693 1165 static int simplify_binop_same_args(struct instruction *insn, pseudo_t arg)
694 1166 {
695 1167 switch (insn->opcode) {
696 1168 case OP_SET_NE:
697 1169 case OP_SET_LT: case OP_SET_GT:
698 1170 case OP_SET_B: case OP_SET_A:
699 1171 if (Wtautological_compare)
700 1172 warning(insn->pos, "self-comparison always evaluates to false");
701 1173 case OP_SUB:
702 1174 case OP_XOR:
703 - return replace_with_pseudo(insn, value_pseudo(insn->type, 0));
1175 + return replace_with_pseudo(insn, value_pseudo(0));
704 1176
705 1177 case OP_SET_EQ:
706 1178 case OP_SET_LE: case OP_SET_GE:
707 1179 case OP_SET_BE: case OP_SET_AE:
708 1180 if (Wtautological_compare)
709 1181 warning(insn->pos, "self-comparison always evaluates to true");
710 - return replace_with_pseudo(insn, value_pseudo(insn->type, 1));
1182 + return replace_with_pseudo(insn, value_pseudo(1));
711 1183
712 1184 case OP_AND:
713 1185 case OP_OR:
714 1186 return replace_with_pseudo(insn, arg);
715 1187
716 - case OP_AND_BOOL:
717 - case OP_OR_BOOL:
718 - remove_usage(arg, &insn->src2);
719 - insn->src2 = value_pseudo(insn->type, 0);
720 - insn->opcode = OP_SET_NE;
721 - return REPEAT_CSE;
722 -
723 1188 default:
724 1189 break;
725 1190 }
726 1191
727 1192 return 0;
728 1193 }
729 1194
730 1195 static int simplify_binop(struct instruction *insn)
731 1196 {
732 1197 if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
733 1198 return REPEAT_CSE;
734 1199 if (constant(insn->src1)) {
735 1200 if (constant(insn->src2))
736 1201 return simplify_constant_binop(insn);
737 1202 return simplify_constant_leftside(insn);
738 1203 }
739 1204 if (constant(insn->src2))
740 1205 return simplify_constant_rightside(insn);
741 1206 if (insn->src1 == insn->src2)
742 1207 return simplify_binop_same_args(insn, insn->src1);
743 1208 return 0;
744 1209 }
745 1210
746 1211 static void switch_pseudo(struct instruction *insn1, pseudo_t *pp1, struct instruction *insn2, pseudo_t *pp2)
747 1212 {
748 1213 pseudo_t p1 = *pp1, p2 = *pp2;
749 1214
750 1215 use_pseudo(insn1, p2, pp1);
751 1216 use_pseudo(insn2, p1, pp2);
752 1217 remove_usage(p1, pp1);
753 1218 remove_usage(p2, pp2);
754 1219 }
755 1220
756 1221 static int canonical_order(pseudo_t p1, pseudo_t p2)
757 1222 {
|
↓ open down ↓ |
25 lines elided |
↑ open up ↑ |
758 1223 /* symbol/constants on the right */
759 1224 if (p1->type == PSEUDO_VAL)
760 1225 return p2->type == PSEUDO_VAL;
761 1226
762 1227 if (p1->type == PSEUDO_SYM)
763 1228 return p2->type == PSEUDO_SYM || p2->type == PSEUDO_VAL;
764 1229
765 1230 return 1;
766 1231 }
767 1232
768 -static int simplify_commutative_binop(struct instruction *insn)
1233 +static int canonicalize_commutative(struct instruction *insn)
769 1234 {
770 - if (!canonical_order(insn->src1, insn->src2)) {
771 - switch_pseudo(insn, &insn->src1, insn, &insn->src2);
772 - return REPEAT_CSE;
773 - }
774 - return 0;
1235 + if (canonical_order(insn->src1, insn->src2))
1236 + return 0;
1237 +
1238 + switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1239 + return repeat_phase |= REPEAT_CSE;
775 1240 }
776 1241
1242 +static int canonicalize_compare(struct instruction *insn)
1243 +{
1244 + if (canonical_order(insn->src1, insn->src2))
1245 + return 0;
1246 +
1247 + switch_pseudo(insn, &insn->src1, insn, &insn->src2);
1248 + insn->opcode = opcode_table[insn->opcode].swap;
1249 + return repeat_phase |= REPEAT_CSE;
1250 +}
1251 +
777 1252 static inline int simple_pseudo(pseudo_t pseudo)
778 1253 {
779 1254 return pseudo->type == PSEUDO_VAL || pseudo->type == PSEUDO_SYM;
780 1255 }
781 1256
782 1257 static int simplify_associative_binop(struct instruction *insn)
783 1258 {
784 1259 struct instruction *def;
785 1260 pseudo_t pseudo = insn->src1;
786 1261
787 1262 if (!simple_pseudo(insn->src2))
|
↓ open down ↓ |
1 lines elided |
↑ open up ↑ |
788 1263 return 0;
789 1264 if (pseudo->type != PSEUDO_REG)
790 1265 return 0;
791 1266 def = pseudo->def;
792 1267 if (def == insn)
793 1268 return 0;
794 1269 if (def->opcode != insn->opcode)
795 1270 return 0;
796 1271 if (!simple_pseudo(def->src2))
797 1272 return 0;
798 - if (ptr_list_size((struct ptr_list *)def->target->users) != 1)
1273 + if (multi_users(def->target))
799 1274 return 0;
800 1275 switch_pseudo(def, &def->src1, insn, &insn->src2);
801 1276 return REPEAT_CSE;
802 1277 }
803 1278
804 1279 static int simplify_constant_unop(struct instruction *insn)
805 1280 {
806 1281 long long val = insn->src1->value;
807 1282 long long res, mask;
808 1283
809 1284 switch (insn->opcode) {
810 1285 case OP_NOT:
811 1286 res = ~val;
812 1287 break;
813 1288 case OP_NEG:
814 1289 res = -val;
815 1290 break;
1291 + case OP_SEXT:
1292 + mask = 1ULL << (insn->orig_type->bit_size-1);
1293 + if (val & mask)
1294 + val |= ~(mask | (mask-1));
1295 + /* fall through */
1296 + case OP_ZEXT:
1297 + case OP_TRUNC:
1298 + res = val;
1299 + break;
816 1300 default:
817 1301 return 0;
818 1302 }
819 1303 mask = 1ULL << (insn->size-1);
820 1304 res &= mask | (mask-1);
821 1305
822 - replace_with_pseudo(insn, value_pseudo(insn->type, res));
1306 + replace_with_pseudo(insn, value_pseudo(res));
823 1307 return REPEAT_CSE;
824 1308 }
825 1309
826 1310 static int simplify_unop(struct instruction *insn)
827 1311 {
828 1312 if (dead_insn(insn, &insn->src1, NULL, NULL))
829 1313 return REPEAT_CSE;
830 1314 if (constant(insn->src1))
831 1315 return simplify_constant_unop(insn);
832 1316
833 1317 switch (insn->opcode) {
834 1318 struct instruction *def;
835 1319
836 1320 case OP_NOT:
837 1321 def = insn->src->def;
838 1322 if (def && def->opcode == OP_NOT)
839 1323 return replace_with_pseudo(insn, def->src);
840 1324 break;
841 1325 case OP_NEG:
842 1326 def = insn->src->def;
843 1327 if (def && def->opcode == OP_NEG)
844 1328 return replace_with_pseudo(insn, def->src);
845 1329 break;
846 1330 default:
847 1331 return 0;
848 1332 }
849 1333 return 0;
850 1334 }
851 1335
852 1336 static int simplify_one_memop(struct instruction *insn, pseudo_t orig)
853 1337 {
854 1338 pseudo_t addr = insn->src;
855 1339 pseudo_t new, off;
856 1340
857 1341 if (addr->type == PSEUDO_REG) {
858 1342 struct instruction *def = addr->def;
859 1343 if (def->opcode == OP_SYMADDR && def->src) {
860 1344 kill_use(&insn->src);
861 1345 use_pseudo(insn, def->src, &insn->src);
862 1346 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
863 1347 }
864 1348 if (def->opcode == OP_ADD) {
865 1349 new = def->src1;
866 1350 off = def->src2;
867 1351 if (constant(off))
868 1352 goto offset;
869 1353 new = off;
|
↓ open down ↓ |
37 lines elided |
↑ open up ↑ |
870 1354 off = def->src1;
871 1355 if (constant(off))
872 1356 goto offset;
873 1357 return 0;
874 1358 }
875 1359 }
876 1360 return 0;
877 1361
878 1362 offset:
879 1363 /* Invalid code */
880 - if (new == orig) {
1364 + if (new == orig || new == addr) {
881 1365 if (new == VOID)
882 1366 return 0;
883 1367 /*
884 1368 * If some BB have been removed it is possible that this
885 1369 * memop is in fact part of a dead BB. In this case
886 1370 * we must not warn since nothing is wrong.
887 1371 * If not part of a dead BB this will be redone after
888 1372 * the BBs have been cleaned up.
889 1373 */
890 1374 if (repeat_phase & REPEAT_CFG_CLEANUP)
891 1375 return 0;
892 - new = VOID;
893 1376 warning(insn->pos, "crazy programmer");
1377 + replace_pseudo(insn, &insn->src, VOID);
1378 + return 0;
894 1379 }
895 1380 insn->offset += off->value;
896 - use_pseudo(insn, new, &insn->src);
897 - remove_usage(addr, &insn->src);
1381 + replace_pseudo(insn, &insn->src, new);
898 1382 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
899 1383 }
900 1384
901 -/*
902 - * We walk the whole chain of adds/subs backwards. That's not
903 - * only more efficient, but it allows us to find loops.
904 - */
1385 +///
1386 +// simplify memops instructions
1387 +//
1388 +// :note: We walk the whole chain of adds/subs backwards.
1389 +// That's not only more efficient, but it allows us to find loops.
905 1390 static int simplify_memop(struct instruction *insn)
906 1391 {
907 1392 int one, ret = 0;
908 1393 pseudo_t orig = insn->src;
909 1394
910 1395 do {
911 1396 one = simplify_one_memop(insn, orig);
912 1397 ret |= one;
913 1398 } while (one);
914 1399 return ret;
915 1400 }
916 1401
917 -static long long get_cast_value(long long val, int old_size, int new_size, int sign)
918 -{
919 - long long mask;
920 -
921 - if (sign && new_size > old_size) {
922 - mask = 1 << (old_size-1);
923 - if (val & mask)
924 - val |= ~(mask | (mask-1));
925 - }
926 - mask = 1 << (new_size-1);
927 - return val & (mask | (mask-1));
928 -}
929 -
930 1402 static int simplify_cast(struct instruction *insn)
931 1403 {
932 - struct symbol *orig_type;
933 - int orig_size, size;
1404 + unsigned long long mask;
1405 + struct instruction *def;
934 1406 pseudo_t src;
1407 + pseudo_t val;
1408 + int osize;
1409 + int size;
935 1410
936 1411 if (dead_insn(insn, &insn->src, NULL, NULL))
937 1412 return REPEAT_CSE;
938 1413
939 - orig_type = insn->orig_type;
940 - if (!orig_type)
941 - return 0;
1414 + src = insn->src;
942 1415
943 - /* Keep casts with pointer on either side (not only case of OP_PTRCAST) */
944 - if (is_ptr_type(orig_type) || is_ptr_type(insn->type))
945 - return 0;
1416 + /* A cast of a constant? */
1417 + if (constant(src))
1418 + return simplify_constant_unop(insn);
946 1419
947 - orig_size = orig_type->bit_size;
1420 + // can merge with the previous instruction?
948 1421 size = insn->size;
949 - src = insn->src;
1422 + def = src->def;
1423 + switch (def_opcode(src)) {
1424 + case OP_AND:
1425 + val = def->src2;
1426 + if (val->type != PSEUDO_VAL)
1427 + break;
1428 + /* A cast of a AND might be a no-op.. */
1429 + switch (insn->opcode) {
1430 + case OP_TRUNC:
1431 + if (multi_users(src))
1432 + break;
1433 + def->opcode = OP_TRUNC;
1434 + def->orig_type = def->type;
1435 + def->type = insn->type;
1436 + def->size = size;
950 1437
951 - /* A cast of a constant? */
952 - if (constant(src)) {
953 - int sign = orig_type->ctype.modifiers & MOD_SIGNED;
954 - long long val = get_cast_value(src->value, orig_size, size, sign);
955 - src = value_pseudo(orig_type, val);
956 - goto simplify;
957 - }
1438 + insn->opcode = OP_AND;
1439 + mask = val->value;
1440 + mask &= (1ULL << size) - 1;
1441 + insn->src2 = value_pseudo(mask);
1442 + return REPEAT_CSE;
958 1443
959 - /* A cast of a "and" might be a no-op.. */
960 - if (src->type == PSEUDO_REG) {
961 - struct instruction *def = src->def;
962 - if (def->opcode == OP_AND && def->size >= size) {
963 - pseudo_t val = def->src2;
964 - if (val->type == PSEUDO_VAL) {
965 - unsigned long long value = val->value;
966 - if (!(value >> (size-1)))
967 - goto simplify;
968 - }
1444 + case OP_SEXT:
1445 + if (val->value & (1 << (def->size - 1)))
1446 + break;
1447 + // OK, sign bit is 0
1448 + case OP_ZEXT:
1449 + if (multi_users(src))
1450 + break;
1451 + // transform:
1452 + // and.n %b <- %a, M
1453 + // *ext.m %c <- (n) %b
1454 + // into:
1455 + // zext.m %b <- %a
1456 + // and.m %c <- %b, M
1457 + // For ZEXT, the mask will always be small
1458 + // enough. For SEXT, it can only be done if
1459 + // the mask force the sign bit to 0.
1460 + def->opcode = OP_ZEXT;
1461 + def->orig_type = insn->orig_type;
1462 + def->type = insn->type;
1463 + def->size = insn->size;
1464 + insn->opcode = OP_AND;
1465 + insn->src2 = val;
1466 + return REPEAT_CSE;
969 1467 }
1468 + break;
1469 + case OP_FPCMP ... OP_BINCMP_END:
1470 + switch (insn->opcode) {
1471 + case OP_SEXT:
1472 + if (insn->size == 1)
1473 + break;
1474 + /* fall through */
1475 + case OP_ZEXT:
1476 + case OP_TRUNC:
1477 + // simplify:
1478 + // setcc.n %t <- %a, %b
1479 + // zext.m %r <- (n) %t
1480 + // into:
1481 + // setcc.m %r <- %a, %b
1482 + // and same for s/zext/trunc/
1483 + insn->opcode = def->opcode;
1484 + use_pseudo(insn, def->src2, &insn->src2);
1485 + return replace_pseudo(insn, &insn->src1, def->src1);
1486 + }
1487 + break;
1488 + case OP_OR:
1489 + switch (insn->opcode) {
1490 + case OP_TRUNC:
1491 + mask = bits_mask(insn->size);
1492 + return simplify_mask_or(insn, mask, def);
1493 + }
1494 + break;
1495 + case OP_LSR:
1496 + case OP_SHL:
1497 + if (insn->opcode != OP_TRUNC)
1498 + break;
1499 + mask = bits_mask(insn->size);
1500 + return simplify_mask_shift(def, mask);
1501 + case OP_TRUNC:
1502 + switch (insn->opcode) {
1503 + case OP_TRUNC:
1504 + insn->orig_type = def->orig_type;
1505 + return replace_pseudo(insn, &insn->src1, def->src);
1506 + case OP_ZEXT:
1507 + if (size != def->orig_type->bit_size)
1508 + break;
1509 + insn->opcode = OP_AND;
1510 + insn->src2 = value_pseudo((1ULL << def->size) - 1);
1511 + return replace_pseudo(insn, &insn->src1, def->src);
1512 + }
1513 + break;
1514 + case OP_ZEXT:
1515 + switch (insn->opcode) {
1516 + case OP_SEXT:
1517 + insn->opcode = OP_ZEXT;
1518 + /* fall through */
1519 + case OP_ZEXT:
1520 + insn->orig_type = def->orig_type;
1521 + return replace_pseudo(insn, &insn->src, def->src);
1522 + }
1523 + /* fall through */
1524 + case OP_SEXT:
1525 + switch (insn->opcode) {
1526 + case OP_TRUNC:
1527 + osize = def->orig_type->bit_size;
1528 + if (size == osize)
1529 + return replace_with_pseudo(insn, def->src);
1530 + if (size > osize)
1531 + insn->opcode = def->opcode;
1532 + insn->orig_type = def->orig_type;
1533 + return replace_pseudo(insn, &insn->src, def->src);
1534 + }
1535 + switch (insn->opcode) {
1536 + case OP_SEXT:
1537 + insn->orig_type = def->orig_type;
1538 + return replace_pseudo(insn, &insn->src, def->src);
1539 + }
1540 + break;
970 1541 }
971 1542
972 - if (size == orig_size) {
973 - int op = (orig_type->ctype.modifiers & MOD_SIGNED) ? OP_SCAST : OP_CAST;
974 - if (insn->opcode == op)
975 - goto simplify;
976 - if (insn->opcode == OP_FPCAST && is_float_type(orig_type))
977 - goto simplify;
978 - }
979 -
980 1543 return 0;
981 -
982 -simplify:
983 - return replace_with_pseudo(insn, src);
984 1544 }
985 1545
986 1546 static int simplify_select(struct instruction *insn)
987 1547 {
988 1548 pseudo_t cond, src1, src2;
989 1549
990 1550 if (dead_insn(insn, &insn->src1, &insn->src2, &insn->src3))
991 1551 return REPEAT_CSE;
992 1552
993 1553 cond = insn->src1;
994 1554 src1 = insn->src2;
995 1555 src2 = insn->src3;
996 1556 if (constant(cond) || src1 == src2) {
997 1557 pseudo_t *kill, take;
998 1558 kill_use(&insn->src1);
999 1559 take = cond->value ? src1 : src2;
1000 1560 kill = cond->value ? &insn->src3 : &insn->src2;
1001 1561 kill_use(kill);
1002 1562 replace_with_pseudo(insn, take);
1003 1563 return REPEAT_CSE;
1004 1564 }
1005 1565 if (constant(src1) && constant(src2)) {
1006 1566 long long val1 = src1->value;
1007 1567 long long val2 = src2->value;
1008 1568
1009 1569 /* The pair 0/1 is special - replace with SETNE/SETEQ */
1010 1570 if ((val1 | val2) == 1) {
1011 1571 int opcode = OP_SET_EQ;
|
↓ open down ↓ |
18 lines elided |
↑ open up ↑ |
1012 1572 if (val1) {
1013 1573 src1 = src2;
1014 1574 opcode = OP_SET_NE;
1015 1575 }
1016 1576 insn->opcode = opcode;
1017 1577 /* insn->src1 is already cond */
1018 1578 insn->src2 = src1; /* Zero */
1019 1579 return REPEAT_CSE;
1020 1580 }
1021 1581 }
1582 + if (cond == src2 && is_zero(src1)) {
1583 + kill_use(&insn->src1);
1584 + kill_use(&insn->src3);
1585 + replace_with_pseudo(insn, value_pseudo(0));
1586 + return REPEAT_CSE;
1587 + }
1022 1588 return 0;
1023 1589 }
1024 1590
1025 1591 static int is_in_range(pseudo_t src, long long low, long long high)
1026 1592 {
1027 1593 long long value;
1028 1594
1029 1595 switch (src->type) {
1030 1596 case PSEUDO_VAL:
1031 1597 value = src->value;
1032 1598 return value >= low && value <= high;
1033 1599 default:
1034 1600 return 0;
1035 1601 }
1036 1602 }
1037 1603
1038 1604 static int simplify_range(struct instruction *insn)
1039 1605 {
1040 1606 pseudo_t src1, src2, src3;
1041 1607
1042 1608 src1 = insn->src1;
1043 1609 src2 = insn->src2;
|
↓ open down ↓ |
12 lines elided |
↑ open up ↑ |
1044 1610 src3 = insn->src3;
1045 1611 if (src2->type != PSEUDO_VAL || src3->type != PSEUDO_VAL)
1046 1612 return 0;
1047 1613 if (is_in_range(src1, src2->value, src3->value)) {
1048 1614 kill_instruction(insn);
1049 1615 return REPEAT_CSE;
1050 1616 }
1051 1617 return 0;
1052 1618 }
1053 1619
1054 -/*
1055 - * Simplify "set_ne/eq $0 + br"
1056 - */
1057 -static int simplify_cond_branch(struct instruction *br, pseudo_t cond, struct instruction *def, pseudo_t *pp)
1620 +///
1621 +// simplify SET_NE/EQ $0 + BR
1622 +static int simplify_cond_branch(struct instruction *br, struct instruction *def, pseudo_t newcond)
1058 1623 {
1059 - use_pseudo(br, *pp, &br->cond);
1060 - remove_usage(cond, &br->cond);
1624 + replace_pseudo(br, &br->cond, newcond);
1061 1625 if (def->opcode == OP_SET_EQ) {
1062 - struct basic_block *true = br->bb_true;
1063 - struct basic_block *false = br->bb_false;
1064 - br->bb_false = true;
1065 - br->bb_true = false;
1626 + struct basic_block *tmp = br->bb_true;
1627 + br->bb_true = br->bb_false;
1628 + br->bb_false = tmp;
1066 1629 }
1067 1630 return REPEAT_CSE;
1068 1631 }
1069 1632
1070 1633 static int simplify_branch(struct instruction *insn)
1071 1634 {
1072 1635 pseudo_t cond = insn->cond;
1073 1636
1074 1637 /* Constant conditional */
1075 1638 if (constant(cond)) {
1076 1639 insert_branch(insn->bb, insn, cond->value ? insn->bb_true : insn->bb_false);
1077 1640 return REPEAT_CSE;
1078 1641 }
1079 1642
1080 1643 /* Same target? */
1081 1644 if (insn->bb_true == insn->bb_false) {
1082 1645 struct basic_block *bb = insn->bb;
1083 1646 struct basic_block *target = insn->bb_false;
1084 1647 remove_bb_from_list(&target->parents, bb, 1);
1085 1648 remove_bb_from_list(&bb->children, target, 1);
1086 1649 insn->bb_false = NULL;
1087 1650 kill_use(&insn->cond);
1088 1651 insn->cond = NULL;
|
↓ open down ↓ |
13 lines elided |
↑ open up ↑ |
1089 1652 insn->opcode = OP_BR;
1090 1653 return REPEAT_CSE;
1091 1654 }
1092 1655
1093 1656 /* Conditional on a SETNE $0 or SETEQ $0 */
1094 1657 if (cond->type == PSEUDO_REG) {
1095 1658 struct instruction *def = cond->def;
1096 1659
1097 1660 if (def->opcode == OP_SET_NE || def->opcode == OP_SET_EQ) {
1098 1661 if (constant(def->src1) && !def->src1->value)
1099 - return simplify_cond_branch(insn, cond, def, &def->src2);
1662 + return simplify_cond_branch(insn, def, def->src2);
1100 1663 if (constant(def->src2) && !def->src2->value)
1101 - return simplify_cond_branch(insn, cond, def, &def->src1);
1664 + return simplify_cond_branch(insn, def, def->src1);
1102 1665 }
1103 1666 if (def->opcode == OP_SEL) {
1104 1667 if (constant(def->src2) && constant(def->src3)) {
1105 1668 long long val1 = def->src2->value;
1106 1669 long long val2 = def->src3->value;
1107 1670 if (!val1 && !val2) {
1108 1671 insert_branch(insn->bb, insn, insn->bb_false);
1109 1672 return REPEAT_CSE;
1110 1673 }
1111 1674 if (val1 && val2) {
1112 1675 insert_branch(insn->bb, insn, insn->bb_true);
1113 1676 return REPEAT_CSE;
1114 1677 }
1115 1678 if (val2) {
1116 - struct basic_block *true = insn->bb_true;
1117 - struct basic_block *false = insn->bb_false;
1118 - insn->bb_false = true;
1119 - insn->bb_true = false;
1679 + struct basic_block *tmp = insn->bb_true;
1680 + insn->bb_true = insn->bb_false;
1681 + insn->bb_false = tmp;
1120 1682 }
1121 - use_pseudo(insn, def->src1, &insn->cond);
1122 - remove_usage(cond, &insn->cond);
1123 - return REPEAT_CSE;
1683 + return replace_pseudo(insn, &insn->cond, def->src1);
1124 1684 }
1125 1685 }
1126 - if (def->opcode == OP_CAST || def->opcode == OP_SCAST) {
1127 - int orig_size = def->orig_type ? def->orig_type->bit_size : 0;
1128 - if (def->size > orig_size) {
1129 - use_pseudo(insn, def->src, &insn->cond);
1130 - remove_usage(cond, &insn->cond);
1131 - return REPEAT_CSE;
1132 - }
1133 - }
1686 + if (def->opcode == OP_SEXT || def->opcode == OP_ZEXT)
1687 + return replace_pseudo(insn, &insn->cond, def->src);
1134 1688 }
1135 1689 return 0;
1136 1690 }
1137 1691
1138 1692 static int simplify_switch(struct instruction *insn)
1139 1693 {
1140 1694 pseudo_t cond = insn->cond;
1141 1695 long long val;
1142 1696 struct multijmp *jmp;
1143 1697
1144 1698 if (!constant(cond))
1145 1699 return 0;
1146 1700 val = insn->cond->value;
1147 1701
1148 1702 FOR_EACH_PTR(insn->multijmp_list, jmp) {
1149 1703 /* Default case */
1150 1704 if (jmp->begin > jmp->end)
1151 1705 goto found;
1152 1706 if (val >= jmp->begin && val <= jmp->end)
1153 1707 goto found;
1154 1708 } END_FOR_EACH_PTR(jmp);
1155 1709 warning(insn->pos, "Impossible case statement");
1156 1710 return 0;
1157 1711
|
↓ open down ↓ |
14 lines elided |
↑ open up ↑ |
1158 1712 found:
1159 1713 insert_branch(insn->bb, insn, jmp->target);
1160 1714 return REPEAT_CSE;
1161 1715 }
1162 1716
1163 1717 int simplify_instruction(struct instruction *insn)
1164 1718 {
1165 1719 if (!insn->bb)
1166 1720 return 0;
1167 1721 switch (insn->opcode) {
1168 - case OP_ADD: case OP_MULS:
1722 + case OP_ADD: case OP_MUL:
1169 1723 case OP_AND: case OP_OR: case OP_XOR:
1170 - case OP_AND_BOOL: case OP_OR_BOOL:
1724 + canonicalize_commutative(insn);
1171 1725 if (simplify_binop(insn))
1172 1726 return REPEAT_CSE;
1173 - if (simplify_commutative_binop(insn))
1174 - return REPEAT_CSE;
1175 1727 return simplify_associative_binop(insn);
1176 1728
1177 - case OP_MULU:
1178 1729 case OP_SET_EQ: case OP_SET_NE:
1179 - if (simplify_binop(insn))
1180 - return REPEAT_CSE;
1181 - return simplify_commutative_binop(insn);
1730 + canonicalize_commutative(insn);
1731 + return simplify_binop(insn);
1182 1732
1733 + case OP_SET_LE: case OP_SET_GE:
1734 + case OP_SET_LT: case OP_SET_GT:
1735 + case OP_SET_B: case OP_SET_A:
1736 + case OP_SET_BE: case OP_SET_AE:
1737 + canonicalize_compare(insn);
1738 + /* fall through */
1183 1739 case OP_SUB:
1184 1740 case OP_DIVU: case OP_DIVS:
1185 1741 case OP_MODU: case OP_MODS:
1186 1742 case OP_SHL:
1187 1743 case OP_LSR: case OP_ASR:
1188 - case OP_SET_LE: case OP_SET_GE:
1189 - case OP_SET_LT: case OP_SET_GT:
1190 - case OP_SET_B: case OP_SET_A:
1191 - case OP_SET_BE: case OP_SET_AE:
1192 1744 return simplify_binop(insn);
1193 1745
1194 - case OP_NOT: case OP_NEG:
1746 + case OP_NOT: case OP_NEG: case OP_FNEG:
1195 1747 return simplify_unop(insn);
1196 - case OP_LOAD: case OP_STORE:
1748 + case OP_LOAD:
1749 + if (!has_users(insn->target))
1750 + return kill_instruction(insn);
1751 + /* fall-through */
1752 + case OP_STORE:
1197 1753 return simplify_memop(insn);
1198 1754 case OP_SYMADDR:
1199 - if (dead_insn(insn, NULL, NULL, NULL))
1755 + if (dead_insn(insn, &insn->src, NULL, NULL))
1200 1756 return REPEAT_CSE | REPEAT_SYMBOL_CLEANUP;
1201 - return replace_with_pseudo(insn, insn->symbol);
1202 - case OP_CAST:
1203 - case OP_SCAST:
1204 - case OP_FPCAST:
1205 - case OP_PTRCAST:
1757 + return replace_with_pseudo(insn, insn->src);
1758 + case OP_SEXT: case OP_ZEXT:
1759 + case OP_TRUNC:
1206 1760 return simplify_cast(insn);
1761 + case OP_FCVTU: case OP_FCVTS:
1762 + case OP_UCVTF: case OP_SCVTF:
1763 + case OP_FCVTF:
1764 + case OP_PTRCAST:
1765 + if (dead_insn(insn, &insn->src, NULL, NULL))
1766 + return REPEAT_CSE;
1767 + break;
1768 + case OP_UTPTR:
1769 + case OP_PTRTU:
1770 + return replace_with_pseudo(insn, insn->src);
1771 + case OP_SLICE:
1772 + if (dead_insn(insn, &insn->src, NULL, NULL))
1773 + return REPEAT_CSE;
1774 + break;
1775 + case OP_SETVAL:
1776 + case OP_SETFVAL:
1777 + if (dead_insn(insn, NULL, NULL, NULL))
1778 + return REPEAT_CSE;
1779 + break;
1207 1780 case OP_PHI:
1208 1781 if (dead_insn(insn, NULL, NULL, NULL)) {
1209 1782 kill_use_list(insn->phi_list);
1210 1783 return REPEAT_CSE;
1211 1784 }
1212 1785 return clean_up_phi(insn);
1213 1786 case OP_PHISOURCE:
1214 1787 if (dead_insn(insn, &insn->phi_src, NULL, NULL))
1215 1788 return REPEAT_CSE;
1216 1789 break;
1217 1790 case OP_SEL:
1218 1791 return simplify_select(insn);
1219 1792 case OP_CBR:
1220 1793 return simplify_branch(insn);
1221 1794 case OP_SWITCH:
1222 1795 return simplify_switch(insn);
1223 1796 case OP_RANGE:
1224 1797 return simplify_range(insn);
1798 + case OP_FADD:
1799 + case OP_FSUB:
1800 + case OP_FMUL:
1801 + case OP_FDIV:
1802 + if (dead_insn(insn, &insn->src1, &insn->src2, NULL))
1803 + return REPEAT_CSE;
1804 + break;
1225 1805 }
1226 1806 return 0;
1227 1807 }
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX