1 /* Conditional constant propagation pass for the GNU compiler.
2 Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009,
3 2010, 2011, 2012, 2013 Free Software Foundation, Inc.
4 Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
5 Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
6
7 This file is part of GCC.
8
9 GCC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 3, or (at your option) any
12 later version.
13
14 GCC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
18
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
22
23 /* Conditional constant propagation (CCP) is based on the SSA
24 propagation engine (tree-ssa-propagate.c). Constant assignments of
25 the form VAR = CST are propagated from the assignments into uses of
26 VAR, which in turn may generate new constants. The simulation uses
27 a four level lattice to keep track of constant values associated
28 with SSA names. Given an SSA name V_i, it may take one of the
29 following values:
30
31 UNINITIALIZED -> the initial state of the value. This value
32 is replaced with a correct initial value
33 the first time the value is used, so the
34 rest of the pass does not need to care about
35 it. Using this value simplifies initialization
36 of the pass, and prevents us from needlessly
37 scanning statements that are never reached.
38
39 UNDEFINED -> V_i is a local variable whose definition
40 has not been processed yet. Therefore we
41 don't yet know if its value is a constant
42 or not.
43
44 CONSTANT -> V_i has been found to hold a constant
45 value C.
46
47 VARYING -> V_i cannot take a constant value, or if it
48 does, it is not possible to determine it
49 at compile time.
50
51 The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
52
53 1- In ccp_visit_stmt, we are interested in assignments whose RHS
54 evaluates into a constant and conditional jumps whose predicate
55 evaluates into a boolean true or false. When an assignment of
56 the form V_i = CONST is found, V_i's lattice value is set to
57 CONSTANT and CONST is associated with it. This causes the
58 propagation engine to add all the SSA edges coming out the
59 assignment into the worklists, so that statements that use V_i
60 can be visited.
61
62 If the statement is a conditional with a constant predicate, we
63 mark the outgoing edges as executable or not executable
64 depending on the predicate's value. This is then used when
65 visiting PHI nodes to know when a PHI argument can be ignored.
66
67
68 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
69 same constant C, then the LHS of the PHI is set to C. This
70 evaluation is known as the "meet operation". Since one of the
71 goals of this evaluation is to optimistically return constant
72 values as often as possible, it uses two main short cuts:
73
74 - If an argument is flowing in through a non-executable edge, it
75 is ignored. This is useful in cases like this:
76
77 if (PRED)
78 a_9 = 3;
79 else
80 a_10 = 100;
81 a_11 = PHI (a_9, a_10)
82
83 If PRED is known to always evaluate to false, then we can
84 assume that a_11 will always take its value from a_10, meaning
85 that instead of consider it VARYING (a_9 and a_10 have
86 different values), we can consider it CONSTANT 100.
87
88 - If an argument has an UNDEFINED value, then it does not affect
89 the outcome of the meet operation. If a variable V_i has an
90 UNDEFINED value, it means that either its defining statement
91 hasn't been visited yet or V_i has no defining statement, in
92 which case the original symbol 'V' is being used
93 uninitialized. Since 'V' is a local variable, the compiler
94 may assume any initial value for it.
95
96
97 After propagation, every variable V_i that ends up with a lattice
98 value of CONSTANT will have the associated constant value in the
99 array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
100 final substitution and folding.
101
102 References:
103
104 Constant propagation with conditional branches,
105 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
106
107 Building an Optimizing Compiler,
108 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
109
110 Advanced Compiler Design and Implementation,
111 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
112
113 #include "config.h"
114 #include "system.h"
115 #include "coretypes.h"
116 #include "tm.h"
117 #include "tree.h"
118 #include "flags.h"
119 #include "tm_p.h"
120 #include "basic-block.h"
121 #include "output.h"
122 #include "function.h"
123 #include "tree-pretty-print.h"
124 #include "gimple-pretty-print.h"
125 #include "timevar.h"
126 #include "tree-dump.h"
127 #include "tree-flow.h"
128 #include "tree-pass.h"
129 #include "tree-ssa-propagate.h"
130 #include "value-prof.h"
131 #include "langhooks.h"
132 #include "target.h"
133 #include "diagnostic-core.h"
134 #include "dbgcnt.h"
135 #include "gimple-fold.h"
136 #include "params.h"
137
138
139 /* Possible lattice values. */
140 typedef enum
141 {
142 UNINITIALIZED,
143 UNDEFINED,
144 CONSTANT,
145 VARYING
146 } ccp_lattice_t;
147
148 struct prop_value_d {
149 /* Lattice value. */
150 ccp_lattice_t lattice_val;
151
152 /* Propagated value. */
153 tree value;
154
155 /* Mask that applies to the propagated value during CCP. For
156 X with a CONSTANT lattice value X & ~mask == value & ~mask. */
157 double_int mask;
158 };
159
160 typedef struct prop_value_d prop_value_t;
161
162 /* Array of propagated constant values. After propagation,
163 CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
164 the constant is held in an SSA name representing a memory store
165 (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
166 memory reference used to store (i.e., the LHS of the assignment
167 doing the store). */
168 static prop_value_t *const_val;
169
170 static void canonicalize_float_value (prop_value_t *);
171 static bool ccp_fold_stmt (gimple_stmt_iterator *);
172
173 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
174
175 static void
dump_lattice_value(FILE * outf,const char * prefix,prop_value_t val)176 dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val)
177 {
178 switch (val.lattice_val)
179 {
180 case UNINITIALIZED:
181 fprintf (outf, "%sUNINITIALIZED", prefix);
182 break;
183 case UNDEFINED:
184 fprintf (outf, "%sUNDEFINED", prefix);
185 break;
186 case VARYING:
187 fprintf (outf, "%sVARYING", prefix);
188 break;
189 case CONSTANT:
190 fprintf (outf, "%sCONSTANT ", prefix);
191 if (TREE_CODE (val.value) != INTEGER_CST
192 || double_int_zero_p (val.mask))
193 print_generic_expr (outf, val.value, dump_flags);
194 else
195 {
196 double_int cval = double_int_and_not (tree_to_double_int (val.value),
197 val.mask);
198 fprintf (outf, "%sCONSTANT " HOST_WIDE_INT_PRINT_DOUBLE_HEX,
199 prefix, cval.high, cval.low);
200 fprintf (outf, " (" HOST_WIDE_INT_PRINT_DOUBLE_HEX ")",
201 val.mask.high, val.mask.low);
202 }
203 break;
204 default:
205 gcc_unreachable ();
206 }
207 }
208
209
210 /* Print lattice value VAL to stderr. */
211
212 void debug_lattice_value (prop_value_t val);
213
214 DEBUG_FUNCTION void
debug_lattice_value(prop_value_t val)215 debug_lattice_value (prop_value_t val)
216 {
217 dump_lattice_value (stderr, "", val);
218 fprintf (stderr, "\n");
219 }
220
221
222 /* Compute a default value for variable VAR and store it in the
223 CONST_VAL array. The following rules are used to get default
224 values:
225
226 1- Global and static variables that are declared constant are
227 considered CONSTANT.
228
229 2- Any other value is considered UNDEFINED. This is useful when
230 considering PHI nodes. PHI arguments that are undefined do not
231 change the constant value of the PHI node, which allows for more
232 constants to be propagated.
233
234 3- Variables defined by statements other than assignments and PHI
235 nodes are considered VARYING.
236
237 4- Initial values of variables that are not GIMPLE registers are
238 considered VARYING. */
239
240 static prop_value_t
get_default_value(tree var)241 get_default_value (tree var)
242 {
243 tree sym = SSA_NAME_VAR (var);
244 prop_value_t val = { UNINITIALIZED, NULL_TREE, { 0, 0 } };
245 gimple stmt;
246
247 stmt = SSA_NAME_DEF_STMT (var);
248
249 if (gimple_nop_p (stmt))
250 {
251 /* Variables defined by an empty statement are those used
252 before being initialized. If VAR is a local variable, we
253 can assume initially that it is UNDEFINED, otherwise we must
254 consider it VARYING. */
255 if (is_gimple_reg (sym)
256 && TREE_CODE (sym) == VAR_DECL)
257 val.lattice_val = UNDEFINED;
258 else
259 {
260 val.lattice_val = VARYING;
261 val.mask = double_int_minus_one;
262 }
263 }
264 else if (is_gimple_assign (stmt)
265 /* Value-returning GIMPLE_CALL statements assign to
266 a variable, and are treated similarly to GIMPLE_ASSIGN. */
267 || (is_gimple_call (stmt)
268 && gimple_call_lhs (stmt) != NULL_TREE)
269 || gimple_code (stmt) == GIMPLE_PHI)
270 {
271 tree cst;
272 if (gimple_assign_single_p (stmt)
273 && DECL_P (gimple_assign_rhs1 (stmt))
274 && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
275 {
276 val.lattice_val = CONSTANT;
277 val.value = cst;
278 }
279 else
280 /* Any other variable defined by an assignment or a PHI node
281 is considered UNDEFINED. */
282 val.lattice_val = UNDEFINED;
283 }
284 else
285 {
286 /* Otherwise, VAR will never take on a constant value. */
287 val.lattice_val = VARYING;
288 val.mask = double_int_minus_one;
289 }
290
291 return val;
292 }
293
294
295 /* Get the constant value associated with variable VAR. */
296
297 static inline prop_value_t *
get_value(tree var)298 get_value (tree var)
299 {
300 prop_value_t *val;
301
302 if (const_val == NULL)
303 return NULL;
304
305 val = &const_val[SSA_NAME_VERSION (var)];
306 if (val->lattice_val == UNINITIALIZED)
307 *val = get_default_value (var);
308
309 canonicalize_float_value (val);
310
311 return val;
312 }
313
314 /* Return the constant tree value associated with VAR. */
315
316 static inline tree
get_constant_value(tree var)317 get_constant_value (tree var)
318 {
319 prop_value_t *val;
320 if (TREE_CODE (var) != SSA_NAME)
321 {
322 if (is_gimple_min_invariant (var))
323 return var;
324 return NULL_TREE;
325 }
326 val = get_value (var);
327 if (val
328 && val->lattice_val == CONSTANT
329 && (TREE_CODE (val->value) != INTEGER_CST
330 || double_int_zero_p (val->mask)))
331 return val->value;
332 return NULL_TREE;
333 }
334
335 /* Sets the value associated with VAR to VARYING. */
336
337 static inline void
set_value_varying(tree var)338 set_value_varying (tree var)
339 {
340 prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
341
342 val->lattice_val = VARYING;
343 val->value = NULL_TREE;
344 val->mask = double_int_minus_one;
345 }
346
347 /* For float types, modify the value of VAL to make ccp work correctly
348 for non-standard values (-0, NaN):
349
350 If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0.
351 If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED.
352 This is to fix the following problem (see PR 29921): Suppose we have
353
354 x = 0.0 * y
355
356 and we set value of y to NaN. This causes value of x to be set to NaN.
357 When we later determine that y is in fact VARYING, fold uses the fact
358 that HONOR_NANS is false, and we try to change the value of x to 0,
359 causing an ICE. With HONOR_NANS being false, the real appearance of
360 NaN would cause undefined behavior, though, so claiming that y (and x)
361 are UNDEFINED initially is correct. */
362
363 static void
canonicalize_float_value(prop_value_t * val)364 canonicalize_float_value (prop_value_t *val)
365 {
366 enum machine_mode mode;
367 tree type;
368 REAL_VALUE_TYPE d;
369
370 if (val->lattice_val != CONSTANT
371 || TREE_CODE (val->value) != REAL_CST)
372 return;
373
374 d = TREE_REAL_CST (val->value);
375 type = TREE_TYPE (val->value);
376 mode = TYPE_MODE (type);
377
378 if (!HONOR_SIGNED_ZEROS (mode)
379 && REAL_VALUE_MINUS_ZERO (d))
380 {
381 val->value = build_real (type, dconst0);
382 return;
383 }
384
385 if (!HONOR_NANS (mode)
386 && REAL_VALUE_ISNAN (d))
387 {
388 val->lattice_val = UNDEFINED;
389 val->value = NULL;
390 return;
391 }
392 }
393
394 /* Return whether the lattice transition is valid. */
395
396 static bool
valid_lattice_transition(prop_value_t old_val,prop_value_t new_val)397 valid_lattice_transition (prop_value_t old_val, prop_value_t new_val)
398 {
399 /* Lattice transitions must always be monotonically increasing in
400 value. */
401 if (old_val.lattice_val < new_val.lattice_val)
402 return true;
403
404 if (old_val.lattice_val != new_val.lattice_val)
405 return false;
406
407 if (!old_val.value && !new_val.value)
408 return true;
409
410 /* Now both lattice values are CONSTANT. */
411
412 /* Allow transitioning from PHI <&x, not executable> == &x
413 to PHI <&x, &y> == common alignment. */
414 if (TREE_CODE (old_val.value) != INTEGER_CST
415 && TREE_CODE (new_val.value) == INTEGER_CST)
416 return true;
417
418 /* Bit-lattices have to agree in the still valid bits. */
419 if (TREE_CODE (old_val.value) == INTEGER_CST
420 && TREE_CODE (new_val.value) == INTEGER_CST)
421 return double_int_equal_p
422 (double_int_and_not (tree_to_double_int (old_val.value),
423 new_val.mask),
424 double_int_and_not (tree_to_double_int (new_val.value),
425 new_val.mask));
426
427 /* Otherwise constant values have to agree. */
428 return operand_equal_p (old_val.value, new_val.value, 0);
429 }
430
431 /* Set the value for variable VAR to NEW_VAL. Return true if the new
432 value is different from VAR's previous value. */
433
434 static bool
set_lattice_value(tree var,prop_value_t new_val)435 set_lattice_value (tree var, prop_value_t new_val)
436 {
437 /* We can deal with old UNINITIALIZED values just fine here. */
438 prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
439
440 canonicalize_float_value (&new_val);
441
442 /* We have to be careful to not go up the bitwise lattice
443 represented by the mask.
444 ??? This doesn't seem to be the best place to enforce this. */
445 if (new_val.lattice_val == CONSTANT
446 && old_val->lattice_val == CONSTANT
447 && TREE_CODE (new_val.value) == INTEGER_CST
448 && TREE_CODE (old_val->value) == INTEGER_CST)
449 {
450 double_int diff;
451 diff = double_int_xor (tree_to_double_int (new_val.value),
452 tree_to_double_int (old_val->value));
453 new_val.mask = double_int_ior (new_val.mask,
454 double_int_ior (old_val->mask, diff));
455 }
456
457 gcc_assert (valid_lattice_transition (*old_val, new_val));
458
459 /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
460 caller that this was a non-transition. */
461 if (old_val->lattice_val != new_val.lattice_val
462 || (new_val.lattice_val == CONSTANT
463 && TREE_CODE (new_val.value) == INTEGER_CST
464 && (TREE_CODE (old_val->value) != INTEGER_CST
465 || !double_int_equal_p (new_val.mask, old_val->mask))))
466 {
467 /* ??? We would like to delay creation of INTEGER_CSTs from
468 partially constants here. */
469
470 if (dump_file && (dump_flags & TDF_DETAILS))
471 {
472 dump_lattice_value (dump_file, "Lattice value changed to ", new_val);
473 fprintf (dump_file, ". Adding SSA edges to worklist.\n");
474 }
475
476 *old_val = new_val;
477
478 gcc_assert (new_val.lattice_val != UNINITIALIZED);
479 return true;
480 }
481
482 return false;
483 }
484
485 static prop_value_t get_value_for_expr (tree, bool);
486 static prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
487 static void bit_value_binop_1 (enum tree_code, tree, double_int *, double_int *,
488 tree, double_int, double_int,
489 tree, double_int, double_int);
490
491 /* Return a double_int that can be used for bitwise simplifications
492 from VAL. */
493
494 static double_int
value_to_double_int(prop_value_t val)495 value_to_double_int (prop_value_t val)
496 {
497 if (val.value
498 && TREE_CODE (val.value) == INTEGER_CST)
499 return tree_to_double_int (val.value);
500 else
501 return double_int_zero;
502 }
503
504 /* Return the value for the address expression EXPR based on alignment
505 information. */
506
507 static prop_value_t
get_value_from_alignment(tree expr)508 get_value_from_alignment (tree expr)
509 {
510 tree type = TREE_TYPE (expr);
511 prop_value_t val;
512 unsigned HOST_WIDE_INT bitpos;
513 unsigned int align;
514
515 gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
516
517 align = get_object_alignment_1 (TREE_OPERAND (expr, 0), &bitpos);
518 val.mask
519 = double_int_and_not (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
520 ? double_int_mask (TYPE_PRECISION (type))
521 : double_int_minus_one,
522 uhwi_to_double_int (align / BITS_PER_UNIT - 1));
523 val.lattice_val = double_int_minus_one_p (val.mask) ? VARYING : CONSTANT;
524 if (val.lattice_val == CONSTANT)
525 val.value
526 = double_int_to_tree (type, uhwi_to_double_int (bitpos / BITS_PER_UNIT));
527 else
528 val.value = NULL_TREE;
529
530 return val;
531 }
532
533 /* Return the value for the tree operand EXPR. If FOR_BITS_P is true
534 return constant bits extracted from alignment information for
535 invariant addresses. */
536
537 static prop_value_t
get_value_for_expr(tree expr,bool for_bits_p)538 get_value_for_expr (tree expr, bool for_bits_p)
539 {
540 prop_value_t val;
541
542 if (TREE_CODE (expr) == SSA_NAME)
543 {
544 val = *get_value (expr);
545 if (for_bits_p
546 && val.lattice_val == CONSTANT
547 && TREE_CODE (val.value) == ADDR_EXPR)
548 val = get_value_from_alignment (val.value);
549 }
550 else if (is_gimple_min_invariant (expr)
551 && (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR))
552 {
553 val.lattice_val = CONSTANT;
554 val.value = expr;
555 val.mask = double_int_zero;
556 canonicalize_float_value (&val);
557 }
558 else if (TREE_CODE (expr) == ADDR_EXPR)
559 val = get_value_from_alignment (expr);
560 else
561 {
562 val.lattice_val = VARYING;
563 val.mask = double_int_minus_one;
564 val.value = NULL_TREE;
565 }
566 return val;
567 }
568
569 /* Return the likely CCP lattice value for STMT.
570
571 If STMT has no operands, then return CONSTANT.
572
573 Else if undefinedness of operands of STMT cause its value to be
574 undefined, then return UNDEFINED.
575
576 Else if any operands of STMT are constants, then return CONSTANT.
577
578 Else return VARYING. */
579
580 static ccp_lattice_t
likely_value(gimple stmt)581 likely_value (gimple stmt)
582 {
583 bool has_constant_operand, has_undefined_operand, all_undefined_operands;
584 tree use;
585 ssa_op_iter iter;
586 unsigned i;
587
588 enum gimple_code code = gimple_code (stmt);
589
590 /* This function appears to be called only for assignments, calls,
591 conditionals, and switches, due to the logic in visit_stmt. */
592 gcc_assert (code == GIMPLE_ASSIGN
593 || code == GIMPLE_CALL
594 || code == GIMPLE_COND
595 || code == GIMPLE_SWITCH);
596
597 /* If the statement has volatile operands, it won't fold to a
598 constant value. */
599 if (gimple_has_volatile_ops (stmt))
600 return VARYING;
601
602 /* Arrive here for more complex cases. */
603 has_constant_operand = false;
604 has_undefined_operand = false;
605 all_undefined_operands = true;
606 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
607 {
608 prop_value_t *val = get_value (use);
609
610 if (val->lattice_val == UNDEFINED)
611 has_undefined_operand = true;
612 else
613 all_undefined_operands = false;
614
615 if (val->lattice_val == CONSTANT)
616 has_constant_operand = true;
617 }
618
619 /* There may be constants in regular rhs operands. For calls we
620 have to ignore lhs, fndecl and static chain, otherwise only
621 the lhs. */
622 for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
623 i < gimple_num_ops (stmt); ++i)
624 {
625 tree op = gimple_op (stmt, i);
626 if (!op || TREE_CODE (op) == SSA_NAME)
627 continue;
628 if (is_gimple_min_invariant (op))
629 has_constant_operand = true;
630 }
631
632 if (has_constant_operand)
633 all_undefined_operands = false;
634
635 /* If the operation combines operands like COMPLEX_EXPR make sure to
636 not mark the result UNDEFINED if only one part of the result is
637 undefined. */
638 if (has_undefined_operand && all_undefined_operands)
639 return UNDEFINED;
640 else if (code == GIMPLE_ASSIGN && has_undefined_operand)
641 {
642 switch (gimple_assign_rhs_code (stmt))
643 {
644 /* Unary operators are handled with all_undefined_operands. */
645 case PLUS_EXPR:
646 case MINUS_EXPR:
647 case POINTER_PLUS_EXPR:
648 /* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected.
649 Not bitwise operators, one VARYING operand may specify the
650 result completely. Not logical operators for the same reason.
651 Not COMPLEX_EXPR as one VARYING operand makes the result partly
652 not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because
653 the undefined operand may be promoted. */
654 return UNDEFINED;
655
656 case ADDR_EXPR:
657 /* If any part of an address is UNDEFINED, like the index
658 of an ARRAY_EXPR, then treat the result as UNDEFINED. */
659 return UNDEFINED;
660
661 default:
662 ;
663 }
664 }
665 /* If there was an UNDEFINED operand but the result may be not UNDEFINED
666 fall back to CONSTANT. During iteration UNDEFINED may still drop
667 to CONSTANT. */
668 if (has_undefined_operand)
669 return CONSTANT;
670
671 /* We do not consider virtual operands here -- load from read-only
672 memory may have only VARYING virtual operands, but still be
673 constant. */
674 if (has_constant_operand
675 || gimple_references_memory_p (stmt))
676 return CONSTANT;
677
678 return VARYING;
679 }
680
681 /* Returns true if STMT cannot be constant. */
682
683 static bool
surely_varying_stmt_p(gimple stmt)684 surely_varying_stmt_p (gimple stmt)
685 {
686 /* If the statement has operands that we cannot handle, it cannot be
687 constant. */
688 if (gimple_has_volatile_ops (stmt))
689 return true;
690
691 /* If it is a call and does not return a value or is not a
692 builtin and not an indirect call, it is varying. */
693 if (is_gimple_call (stmt))
694 {
695 tree fndecl;
696 if (!gimple_call_lhs (stmt)
697 || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
698 && !DECL_BUILT_IN (fndecl)))
699 return true;
700 }
701
702 /* Any other store operation is not interesting. */
703 else if (gimple_vdef (stmt))
704 return true;
705
706 /* Anything other than assignments and conditional jumps are not
707 interesting for CCP. */
708 if (gimple_code (stmt) != GIMPLE_ASSIGN
709 && gimple_code (stmt) != GIMPLE_COND
710 && gimple_code (stmt) != GIMPLE_SWITCH
711 && gimple_code (stmt) != GIMPLE_CALL)
712 return true;
713
714 return false;
715 }
716
717 /* Initialize local data structures for CCP. */
718
719 static void
ccp_initialize(void)720 ccp_initialize (void)
721 {
722 basic_block bb;
723
724 const_val = XCNEWVEC (prop_value_t, num_ssa_names);
725
726 /* Initialize simulation flags for PHI nodes and statements. */
727 FOR_EACH_BB (bb)
728 {
729 gimple_stmt_iterator i;
730
731 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
732 {
733 gimple stmt = gsi_stmt (i);
734 bool is_varying;
735
736 /* If the statement is a control insn, then we do not
737 want to avoid simulating the statement once. Failure
738 to do so means that those edges will never get added. */
739 if (stmt_ends_bb_p (stmt))
740 is_varying = false;
741 else
742 is_varying = surely_varying_stmt_p (stmt);
743
744 if (is_varying)
745 {
746 tree def;
747 ssa_op_iter iter;
748
749 /* If the statement will not produce a constant, mark
750 all its outputs VARYING. */
751 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
752 set_value_varying (def);
753 }
754 prop_set_simulate_again (stmt, !is_varying);
755 }
756 }
757
758 /* Now process PHI nodes. We never clear the simulate_again flag on
759 phi nodes, since we do not know which edges are executable yet,
760 except for phi nodes for virtual operands when we do not do store ccp. */
761 FOR_EACH_BB (bb)
762 {
763 gimple_stmt_iterator i;
764
765 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
766 {
767 gimple phi = gsi_stmt (i);
768
769 if (!is_gimple_reg (gimple_phi_result (phi)))
770 prop_set_simulate_again (phi, false);
771 else
772 prop_set_simulate_again (phi, true);
773 }
774 }
775 }
776
777 /* Debug count support. Reset the values of ssa names
778 VARYING when the total number ssa names analyzed is
779 beyond the debug count specified. */
780
781 static void
do_dbg_cnt(void)782 do_dbg_cnt (void)
783 {
784 unsigned i;
785 for (i = 0; i < num_ssa_names; i++)
786 {
787 if (!dbg_cnt (ccp))
788 {
789 const_val[i].lattice_val = VARYING;
790 const_val[i].mask = double_int_minus_one;
791 const_val[i].value = NULL_TREE;
792 }
793 }
794 }
795
796
797 /* Do final substitution of propagated values, cleanup the flowgraph and
798 free allocated storage.
799
800 Return TRUE when something was optimized. */
801
802 static bool
ccp_finalize(void)803 ccp_finalize (void)
804 {
805 bool something_changed;
806 unsigned i;
807
808 do_dbg_cnt ();
809
810 /* Derive alignment and misalignment information from partially
811 constant pointers in the lattice. */
812 for (i = 1; i < num_ssa_names; ++i)
813 {
814 tree name = ssa_name (i);
815 prop_value_t *val;
816 struct ptr_info_def *pi;
817 unsigned int tem, align;
818
819 if (!name
820 || !POINTER_TYPE_P (TREE_TYPE (name)))
821 continue;
822
823 val = get_value (name);
824 if (val->lattice_val != CONSTANT
825 || TREE_CODE (val->value) != INTEGER_CST)
826 continue;
827
828 /* Trailing constant bits specify the alignment, trailing value
829 bits the misalignment. */
830 tem = val->mask.low;
831 align = (tem & -tem);
832 if (align == 1)
833 continue;
834
835 pi = get_ptr_info (name);
836 pi->align = align;
837 pi->misalign = TREE_INT_CST_LOW (val->value) & (align - 1);
838 }
839
840 /* Perform substitutions based on the known constant values. */
841 something_changed = substitute_and_fold (get_constant_value,
842 ccp_fold_stmt, true);
843
844 free (const_val);
845 const_val = NULL;
846 return something_changed;;
847 }
848
849
850 /* Compute the meet operator between *VAL1 and *VAL2. Store the result
851 in VAL1.
852
853 any M UNDEFINED = any
854 any M VARYING = VARYING
855 Ci M Cj = Ci if (i == j)
856 Ci M Cj = VARYING if (i != j)
857 */
858
859 static void
ccp_lattice_meet(prop_value_t * val1,prop_value_t * val2)860 ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2)
861 {
862 if (val1->lattice_val == UNDEFINED)
863 {
864 /* UNDEFINED M any = any */
865 *val1 = *val2;
866 }
867 else if (val2->lattice_val == UNDEFINED)
868 {
869 /* any M UNDEFINED = any
870 Nothing to do. VAL1 already contains the value we want. */
871 ;
872 }
873 else if (val1->lattice_val == VARYING
874 || val2->lattice_val == VARYING)
875 {
876 /* any M VARYING = VARYING. */
877 val1->lattice_val = VARYING;
878 val1->mask = double_int_minus_one;
879 val1->value = NULL_TREE;
880 }
881 else if (val1->lattice_val == CONSTANT
882 && val2->lattice_val == CONSTANT
883 && TREE_CODE (val1->value) == INTEGER_CST
884 && TREE_CODE (val2->value) == INTEGER_CST)
885 {
886 /* Ci M Cj = Ci if (i == j)
887 Ci M Cj = VARYING if (i != j)
888
889 For INTEGER_CSTs mask unequal bits. If no equal bits remain,
890 drop to varying. */
891 val1->mask
892 = double_int_ior (double_int_ior (val1->mask,
893 val2->mask),
894 double_int_xor (tree_to_double_int (val1->value),
895 tree_to_double_int (val2->value)));
896 if (double_int_minus_one_p (val1->mask))
897 {
898 val1->lattice_val = VARYING;
899 val1->value = NULL_TREE;
900 }
901 }
902 else if (val1->lattice_val == CONSTANT
903 && val2->lattice_val == CONSTANT
904 && simple_cst_equal (val1->value, val2->value) == 1)
905 {
906 /* Ci M Cj = Ci if (i == j)
907 Ci M Cj = VARYING if (i != j)
908
909 VAL1 already contains the value we want for equivalent values. */
910 }
911 else if (val1->lattice_val == CONSTANT
912 && val2->lattice_val == CONSTANT
913 && (TREE_CODE (val1->value) == ADDR_EXPR
914 || TREE_CODE (val2->value) == ADDR_EXPR))
915 {
916 /* When not equal addresses are involved try meeting for
917 alignment. */
918 prop_value_t tem = *val2;
919 if (TREE_CODE (val1->value) == ADDR_EXPR)
920 *val1 = get_value_for_expr (val1->value, true);
921 if (TREE_CODE (val2->value) == ADDR_EXPR)
922 tem = get_value_for_expr (val2->value, true);
923 ccp_lattice_meet (val1, &tem);
924 }
925 else
926 {
927 /* Any other combination is VARYING. */
928 val1->lattice_val = VARYING;
929 val1->mask = double_int_minus_one;
930 val1->value = NULL_TREE;
931 }
932 }
933
934
935 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
936 lattice values to determine PHI_NODE's lattice value. The value of a
937 PHI node is determined calling ccp_lattice_meet with all the arguments
938 of the PHI node that are incoming via executable edges. */
939
940 static enum ssa_prop_result
ccp_visit_phi_node(gimple phi)941 ccp_visit_phi_node (gimple phi)
942 {
943 unsigned i;
944 prop_value_t *old_val, new_val;
945
946 if (dump_file && (dump_flags & TDF_DETAILS))
947 {
948 fprintf (dump_file, "\nVisiting PHI node: ");
949 print_gimple_stmt (dump_file, phi, 0, dump_flags);
950 }
951
952 old_val = get_value (gimple_phi_result (phi));
953 switch (old_val->lattice_val)
954 {
955 case VARYING:
956 return SSA_PROP_VARYING;
957
958 case CONSTANT:
959 new_val = *old_val;
960 break;
961
962 case UNDEFINED:
963 new_val.lattice_val = UNDEFINED;
964 new_val.value = NULL_TREE;
965 break;
966
967 default:
968 gcc_unreachable ();
969 }
970
971 for (i = 0; i < gimple_phi_num_args (phi); i++)
972 {
973 /* Compute the meet operator over all the PHI arguments flowing
974 through executable edges. */
975 edge e = gimple_phi_arg_edge (phi, i);
976
977 if (dump_file && (dump_flags & TDF_DETAILS))
978 {
979 fprintf (dump_file,
980 "\n Argument #%d (%d -> %d %sexecutable)\n",
981 i, e->src->index, e->dest->index,
982 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
983 }
984
985 /* If the incoming edge is executable, Compute the meet operator for
986 the existing value of the PHI node and the current PHI argument. */
987 if (e->flags & EDGE_EXECUTABLE)
988 {
989 tree arg = gimple_phi_arg (phi, i)->def;
990 prop_value_t arg_val = get_value_for_expr (arg, false);
991
992 ccp_lattice_meet (&new_val, &arg_val);
993
994 if (dump_file && (dump_flags & TDF_DETAILS))
995 {
996 fprintf (dump_file, "\t");
997 print_generic_expr (dump_file, arg, dump_flags);
998 dump_lattice_value (dump_file, "\tValue: ", arg_val);
999 fprintf (dump_file, "\n");
1000 }
1001
1002 if (new_val.lattice_val == VARYING)
1003 break;
1004 }
1005 }
1006
1007 if (dump_file && (dump_flags & TDF_DETAILS))
1008 {
1009 dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
1010 fprintf (dump_file, "\n\n");
1011 }
1012
1013 /* Make the transition to the new value. */
1014 if (set_lattice_value (gimple_phi_result (phi), new_val))
1015 {
1016 if (new_val.lattice_val == VARYING)
1017 return SSA_PROP_VARYING;
1018 else
1019 return SSA_PROP_INTERESTING;
1020 }
1021 else
1022 return SSA_PROP_NOT_INTERESTING;
1023 }
1024
1025 /* Return the constant value for OP or OP otherwise. */
1026
1027 static tree
valueize_op(tree op)1028 valueize_op (tree op)
1029 {
1030 if (TREE_CODE (op) == SSA_NAME)
1031 {
1032 tree tem = get_constant_value (op);
1033 if (tem)
1034 return tem;
1035 }
1036 return op;
1037 }
1038
1039 /* CCP specific front-end to the non-destructive constant folding
1040 routines.
1041
1042 Attempt to simplify the RHS of STMT knowing that one or more
1043 operands are constants.
1044
1045 If simplification is possible, return the simplified RHS,
1046 otherwise return the original RHS or NULL_TREE. */
1047
1048 static tree
ccp_fold(gimple stmt)1049 ccp_fold (gimple stmt)
1050 {
1051 location_t loc = gimple_location (stmt);
1052 switch (gimple_code (stmt))
1053 {
1054 case GIMPLE_COND:
1055 {
1056 /* Handle comparison operators that can appear in GIMPLE form. */
1057 tree op0 = valueize_op (gimple_cond_lhs (stmt));
1058 tree op1 = valueize_op (gimple_cond_rhs (stmt));
1059 enum tree_code code = gimple_cond_code (stmt);
1060 return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
1061 }
1062
1063 case GIMPLE_SWITCH:
1064 {
1065 /* Return the constant switch index. */
1066 return valueize_op (gimple_switch_index (stmt));
1067 }
1068
1069 case GIMPLE_ASSIGN:
1070 case GIMPLE_CALL:
1071 return gimple_fold_stmt_to_constant_1 (stmt, valueize_op);
1072
1073 default:
1074 gcc_unreachable ();
1075 }
1076 }
1077
1078 /* Apply the operation CODE in type TYPE to the value, mask pair
1079 RVAL and RMASK representing a value of type RTYPE and set
1080 the value, mask pair *VAL and *MASK to the result. */
1081
1082 static void
bit_value_unop_1(enum tree_code code,tree type,double_int * val,double_int * mask,tree rtype,double_int rval,double_int rmask)1083 bit_value_unop_1 (enum tree_code code, tree type,
1084 double_int *val, double_int *mask,
1085 tree rtype, double_int rval, double_int rmask)
1086 {
1087 switch (code)
1088 {
1089 case BIT_NOT_EXPR:
1090 *mask = rmask;
1091 *val = double_int_not (rval);
1092 break;
1093
1094 case NEGATE_EXPR:
1095 {
1096 double_int temv, temm;
1097 /* Return ~rval + 1. */
1098 bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask);
1099 bit_value_binop_1 (PLUS_EXPR, type, val, mask,
1100 type, temv, temm,
1101 type, double_int_one, double_int_zero);
1102 break;
1103 }
1104
1105 CASE_CONVERT:
1106 {
1107 bool uns;
1108
1109 /* First extend mask and value according to the original type. */
1110 uns = (TREE_CODE (rtype) == INTEGER_TYPE && TYPE_IS_SIZETYPE (rtype)
1111 ? 0 : TYPE_UNSIGNED (rtype));
1112 *mask = double_int_ext (rmask, TYPE_PRECISION (rtype), uns);
1113 *val = double_int_ext (rval, TYPE_PRECISION (rtype), uns);
1114
1115 /* Then extend mask and value according to the target type. */
1116 uns = (TREE_CODE (type) == INTEGER_TYPE && TYPE_IS_SIZETYPE (type)
1117 ? 0 : TYPE_UNSIGNED (type));
1118 *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
1119 *val = double_int_ext (*val, TYPE_PRECISION (type), uns);
1120 break;
1121 }
1122
1123 default:
1124 *mask = double_int_minus_one;
1125 break;
1126 }
1127 }
1128
1129 /* Apply the operation CODE in type TYPE to the value, mask pairs
1130 R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1131 and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */
1132
1133 static void
bit_value_binop_1(enum tree_code code,tree type,double_int * val,double_int * mask,tree r1type,double_int r1val,double_int r1mask,tree r2type,double_int r2val,double_int r2mask)1134 bit_value_binop_1 (enum tree_code code, tree type,
1135 double_int *val, double_int *mask,
1136 tree r1type, double_int r1val, double_int r1mask,
1137 tree r2type, double_int r2val, double_int r2mask)
1138 {
1139 bool uns = (TREE_CODE (type) == INTEGER_TYPE
1140 && TYPE_IS_SIZETYPE (type) ? 0 : TYPE_UNSIGNED (type));
1141 /* Assume we'll get a constant result. Use an initial varying value,
1142 we fall back to varying in the end if necessary. */
1143 *mask = double_int_minus_one;
1144 switch (code)
1145 {
1146 case BIT_AND_EXPR:
1147 /* The mask is constant where there is a known not
1148 set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1149 *mask = double_int_and (double_int_ior (r1mask, r2mask),
1150 double_int_and (double_int_ior (r1val, r1mask),
1151 double_int_ior (r2val, r2mask)));
1152 *val = double_int_and (r1val, r2val);
1153 break;
1154
1155 case BIT_IOR_EXPR:
1156 /* The mask is constant where there is a known
1157 set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */
1158 *mask = double_int_and_not
1159 (double_int_ior (r1mask, r2mask),
1160 double_int_ior (double_int_and_not (r1val, r1mask),
1161 double_int_and_not (r2val, r2mask)));
1162 *val = double_int_ior (r1val, r2val);
1163 break;
1164
1165 case BIT_XOR_EXPR:
1166 /* m1 | m2 */
1167 *mask = double_int_ior (r1mask, r2mask);
1168 *val = double_int_xor (r1val, r2val);
1169 break;
1170
1171 case LROTATE_EXPR:
1172 case RROTATE_EXPR:
1173 if (double_int_zero_p (r2mask))
1174 {
1175 HOST_WIDE_INT shift = r2val.low;
1176 if (code == RROTATE_EXPR)
1177 shift = -shift;
1178 *mask = double_int_lrotate (r1mask, shift, TYPE_PRECISION (type));
1179 *val = double_int_lrotate (r1val, shift, TYPE_PRECISION (type));
1180 }
1181 break;
1182
1183 case LSHIFT_EXPR:
1184 case RSHIFT_EXPR:
1185 /* ??? We can handle partially known shift counts if we know
1186 its sign. That way we can tell that (x << (y | 8)) & 255
1187 is zero. */
1188 if (double_int_zero_p (r2mask))
1189 {
1190 HOST_WIDE_INT shift = r2val.low;
1191 if (code == RSHIFT_EXPR)
1192 shift = -shift;
1193 /* We need to know if we are doing a left or a right shift
1194 to properly shift in zeros for left shift and unsigned
1195 right shifts and the sign bit for signed right shifts.
1196 For signed right shifts we shift in varying in case
1197 the sign bit was varying. */
1198 if (shift > 0)
1199 {
1200 *mask = double_int_lshift (r1mask, shift,
1201 TYPE_PRECISION (type), false);
1202 *val = double_int_lshift (r1val, shift,
1203 TYPE_PRECISION (type), false);
1204 }
1205 else if (shift < 0)
1206 {
1207 /* ??? We can have sizetype related inconsistencies in
1208 the IL. */
1209 if ((TREE_CODE (r1type) == INTEGER_TYPE
1210 && (TYPE_IS_SIZETYPE (r1type)
1211 ? 0 : TYPE_UNSIGNED (r1type))) != uns)
1212 break;
1213
1214 shift = -shift;
1215 *mask = double_int_rshift (r1mask, shift,
1216 TYPE_PRECISION (type), !uns);
1217 *val = double_int_rshift (r1val, shift,
1218 TYPE_PRECISION (type), !uns);
1219 }
1220 else
1221 {
1222 *mask = r1mask;
1223 *val = r1val;
1224 }
1225 }
1226 break;
1227
1228 case PLUS_EXPR:
1229 case POINTER_PLUS_EXPR:
1230 {
1231 double_int lo, hi;
1232 /* Do the addition with unknown bits set to zero, to give carry-ins of
1233 zero wherever possible. */
1234 lo = double_int_add (double_int_and_not (r1val, r1mask),
1235 double_int_and_not (r2val, r2mask));
1236 lo = double_int_ext (lo, TYPE_PRECISION (type), uns);
1237 /* Do the addition with unknown bits set to one, to give carry-ins of
1238 one wherever possible. */
1239 hi = double_int_add (double_int_ior (r1val, r1mask),
1240 double_int_ior (r2val, r2mask));
1241 hi = double_int_ext (hi, TYPE_PRECISION (type), uns);
1242 /* Each bit in the result is known if (a) the corresponding bits in
1243 both inputs are known, and (b) the carry-in to that bit position
1244 is known. We can check condition (b) by seeing if we got the same
1245 result with minimised carries as with maximised carries. */
1246 *mask = double_int_ior (double_int_ior (r1mask, r2mask),
1247 double_int_xor (lo, hi));
1248 *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
1249 /* It shouldn't matter whether we choose lo or hi here. */
1250 *val = lo;
1251 break;
1252 }
1253
1254 case MINUS_EXPR:
1255 {
1256 double_int temv, temm;
1257 bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm,
1258 r2type, r2val, r2mask);
1259 bit_value_binop_1 (PLUS_EXPR, type, val, mask,
1260 r1type, r1val, r1mask,
1261 r2type, temv, temm);
1262 break;
1263 }
1264
1265 case MULT_EXPR:
1266 {
1267 /* Just track trailing zeros in both operands and transfer
1268 them to the other. */
1269 int r1tz = double_int_ctz (double_int_ior (r1val, r1mask));
1270 int r2tz = double_int_ctz (double_int_ior (r2val, r2mask));
1271 if (r1tz + r2tz >= HOST_BITS_PER_DOUBLE_INT)
1272 {
1273 *mask = double_int_zero;
1274 *val = double_int_zero;
1275 }
1276 else if (r1tz + r2tz > 0)
1277 {
1278 *mask = double_int_not (double_int_mask (r1tz + r2tz));
1279 *mask = double_int_ext (*mask, TYPE_PRECISION (type), uns);
1280 *val = double_int_zero;
1281 }
1282 break;
1283 }
1284
1285 case EQ_EXPR:
1286 case NE_EXPR:
1287 {
1288 double_int m = double_int_ior (r1mask, r2mask);
1289 if (!double_int_equal_p (double_int_and_not (r1val, m),
1290 double_int_and_not (r2val, m)))
1291 {
1292 *mask = double_int_zero;
1293 *val = ((code == EQ_EXPR) ? double_int_zero : double_int_one);
1294 }
1295 else
1296 {
1297 /* We know the result of a comparison is always one or zero. */
1298 *mask = double_int_one;
1299 *val = double_int_zero;
1300 }
1301 break;
1302 }
1303
1304 case GE_EXPR:
1305 case GT_EXPR:
1306 {
1307 double_int tem = r1val;
1308 r1val = r2val;
1309 r2val = tem;
1310 tem = r1mask;
1311 r1mask = r2mask;
1312 r2mask = tem;
1313 code = swap_tree_comparison (code);
1314 }
1315 /* Fallthru. */
1316 case LT_EXPR:
1317 case LE_EXPR:
1318 {
1319 int minmax, maxmin;
1320 /* If the most significant bits are not known we know nothing. */
1321 if (double_int_negative_p (r1mask) || double_int_negative_p (r2mask))
1322 break;
1323
1324 /* For comparisons the signedness is in the comparison operands. */
1325 uns = (TREE_CODE (r1type) == INTEGER_TYPE
1326 && TYPE_IS_SIZETYPE (r1type) ? 0 : TYPE_UNSIGNED (r1type));
1327 /* ??? We can have sizetype related inconsistencies in the IL. */
1328 if ((TREE_CODE (r2type) == INTEGER_TYPE
1329 && TYPE_IS_SIZETYPE (r2type) ? 0 : TYPE_UNSIGNED (r2type)) != uns)
1330 break;
1331
1332 /* If we know the most significant bits we know the values
1333 value ranges by means of treating varying bits as zero
1334 or one. Do a cross comparison of the max/min pairs. */
1335 maxmin = double_int_cmp (double_int_ior (r1val, r1mask),
1336 double_int_and_not (r2val, r2mask), uns);
1337 minmax = double_int_cmp (double_int_and_not (r1val, r1mask),
1338 double_int_ior (r2val, r2mask), uns);
1339 if (maxmin < 0) /* r1 is less than r2. */
1340 {
1341 *mask = double_int_zero;
1342 *val = double_int_one;
1343 }
1344 else if (minmax > 0) /* r1 is not less or equal to r2. */
1345 {
1346 *mask = double_int_zero;
1347 *val = double_int_zero;
1348 }
1349 else if (maxmin == minmax) /* r1 and r2 are equal. */
1350 {
1351 /* This probably should never happen as we'd have
1352 folded the thing during fully constant value folding. */
1353 *mask = double_int_zero;
1354 *val = (code == LE_EXPR ? double_int_one : double_int_zero);
1355 }
1356 else
1357 {
1358 /* We know the result of a comparison is always one or zero. */
1359 *mask = double_int_one;
1360 *val = double_int_zero;
1361 }
1362 break;
1363 }
1364
1365 default:;
1366 }
1367 }
1368
1369 /* Return the propagation value when applying the operation CODE to
1370 the value RHS yielding type TYPE. */
1371
1372 static prop_value_t
bit_value_unop(enum tree_code code,tree type,tree rhs)1373 bit_value_unop (enum tree_code code, tree type, tree rhs)
1374 {
1375 prop_value_t rval = get_value_for_expr (rhs, true);
1376 double_int value, mask;
1377 prop_value_t val;
1378
1379 if (rval.lattice_val == UNDEFINED)
1380 return rval;
1381
1382 gcc_assert ((rval.lattice_val == CONSTANT
1383 && TREE_CODE (rval.value) == INTEGER_CST)
1384 || double_int_minus_one_p (rval.mask));
1385 bit_value_unop_1 (code, type, &value, &mask,
1386 TREE_TYPE (rhs), value_to_double_int (rval), rval.mask);
1387 if (!double_int_minus_one_p (mask))
1388 {
1389 val.lattice_val = CONSTANT;
1390 val.mask = mask;
1391 /* ??? Delay building trees here. */
1392 val.value = double_int_to_tree (type, value);
1393 }
1394 else
1395 {
1396 val.lattice_val = VARYING;
1397 val.value = NULL_TREE;
1398 val.mask = double_int_minus_one;
1399 }
1400 return val;
1401 }
1402
1403 /* Return the propagation value when applying the operation CODE to
1404 the values RHS1 and RHS2 yielding type TYPE. */
1405
1406 static prop_value_t
bit_value_binop(enum tree_code code,tree type,tree rhs1,tree rhs2)1407 bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
1408 {
1409 prop_value_t r1val = get_value_for_expr (rhs1, true);
1410 prop_value_t r2val = get_value_for_expr (rhs2, true);
1411 double_int value, mask;
1412 prop_value_t val;
1413
1414 if (r1val.lattice_val == UNDEFINED
1415 || r2val.lattice_val == UNDEFINED)
1416 {
1417 val.lattice_val = VARYING;
1418 val.value = NULL_TREE;
1419 val.mask = double_int_minus_one;
1420 return val;
1421 }
1422
1423 gcc_assert ((r1val.lattice_val == CONSTANT
1424 && TREE_CODE (r1val.value) == INTEGER_CST)
1425 || double_int_minus_one_p (r1val.mask));
1426 gcc_assert ((r2val.lattice_val == CONSTANT
1427 && TREE_CODE (r2val.value) == INTEGER_CST)
1428 || double_int_minus_one_p (r2val.mask));
1429 bit_value_binop_1 (code, type, &value, &mask,
1430 TREE_TYPE (rhs1), value_to_double_int (r1val), r1val.mask,
1431 TREE_TYPE (rhs2), value_to_double_int (r2val), r2val.mask);
1432 if (!double_int_minus_one_p (mask))
1433 {
1434 val.lattice_val = CONSTANT;
1435 val.mask = mask;
1436 /* ??? Delay building trees here. */
1437 val.value = double_int_to_tree (type, value);
1438 }
1439 else
1440 {
1441 val.lattice_val = VARYING;
1442 val.value = NULL_TREE;
1443 val.mask = double_int_minus_one;
1444 }
1445 return val;
1446 }
1447
1448 /* Return the propagation value when applying __builtin_assume_aligned to
1449 its arguments. */
1450
1451 static prop_value_t
bit_value_assume_aligned(gimple stmt)1452 bit_value_assume_aligned (gimple stmt)
1453 {
1454 tree ptr = gimple_call_arg (stmt, 0), align, misalign = NULL_TREE;
1455 tree type = TREE_TYPE (ptr);
1456 unsigned HOST_WIDE_INT aligni, misaligni = 0;
1457 prop_value_t ptrval = get_value_for_expr (ptr, true);
1458 prop_value_t alignval;
1459 double_int value, mask;
1460 prop_value_t val;
1461 if (ptrval.lattice_val == UNDEFINED)
1462 return ptrval;
1463 gcc_assert ((ptrval.lattice_val == CONSTANT
1464 && TREE_CODE (ptrval.value) == INTEGER_CST)
1465 || double_int_minus_one_p (ptrval.mask));
1466 align = gimple_call_arg (stmt, 1);
1467 if (!host_integerp (align, 1))
1468 return ptrval;
1469 aligni = tree_low_cst (align, 1);
1470 if (aligni <= 1
1471 || (aligni & (aligni - 1)) != 0)
1472 return ptrval;
1473 if (gimple_call_num_args (stmt) > 2)
1474 {
1475 misalign = gimple_call_arg (stmt, 2);
1476 if (!host_integerp (misalign, 1))
1477 return ptrval;
1478 misaligni = tree_low_cst (misalign, 1);
1479 if (misaligni >= aligni)
1480 return ptrval;
1481 }
1482 align = build_int_cst_type (type, -aligni);
1483 alignval = get_value_for_expr (align, true);
1484 bit_value_binop_1 (BIT_AND_EXPR, type, &value, &mask,
1485 type, value_to_double_int (ptrval), ptrval.mask,
1486 type, value_to_double_int (alignval), alignval.mask);
1487 if (!double_int_minus_one_p (mask))
1488 {
1489 val.lattice_val = CONSTANT;
1490 val.mask = mask;
1491 gcc_assert ((mask.low & (aligni - 1)) == 0);
1492 gcc_assert ((value.low & (aligni - 1)) == 0);
1493 value.low |= misaligni;
1494 /* ??? Delay building trees here. */
1495 val.value = double_int_to_tree (type, value);
1496 }
1497 else
1498 {
1499 val.lattice_val = VARYING;
1500 val.value = NULL_TREE;
1501 val.mask = double_int_minus_one;
1502 }
1503 return val;
1504 }
1505
1506 /* Evaluate statement STMT.
1507 Valid only for assignments, calls, conditionals, and switches. */
1508
1509 static prop_value_t
evaluate_stmt(gimple stmt)1510 evaluate_stmt (gimple stmt)
1511 {
1512 prop_value_t val;
1513 tree simplified = NULL_TREE;
1514 ccp_lattice_t likelyvalue = likely_value (stmt);
1515 bool is_constant = false;
1516 unsigned int align;
1517
1518 if (dump_file && (dump_flags & TDF_DETAILS))
1519 {
1520 fprintf (dump_file, "which is likely ");
1521 switch (likelyvalue)
1522 {
1523 case CONSTANT:
1524 fprintf (dump_file, "CONSTANT");
1525 break;
1526 case UNDEFINED:
1527 fprintf (dump_file, "UNDEFINED");
1528 break;
1529 case VARYING:
1530 fprintf (dump_file, "VARYING");
1531 break;
1532 default:;
1533 }
1534 fprintf (dump_file, "\n");
1535 }
1536
1537 /* If the statement is likely to have a CONSTANT result, then try
1538 to fold the statement to determine the constant value. */
1539 /* FIXME. This is the only place that we call ccp_fold.
1540 Since likely_value never returns CONSTANT for calls, we will
1541 not attempt to fold them, including builtins that may profit. */
1542 if (likelyvalue == CONSTANT)
1543 {
1544 fold_defer_overflow_warnings ();
1545 simplified = ccp_fold (stmt);
1546 is_constant = simplified && is_gimple_min_invariant (simplified);
1547 fold_undefer_overflow_warnings (is_constant, stmt, 0);
1548 if (is_constant)
1549 {
1550 /* The statement produced a constant value. */
1551 val.lattice_val = CONSTANT;
1552 val.value = simplified;
1553 val.mask = double_int_zero;
1554 }
1555 }
1556 /* If the statement is likely to have a VARYING result, then do not
1557 bother folding the statement. */
1558 else if (likelyvalue == VARYING)
1559 {
1560 enum gimple_code code = gimple_code (stmt);
1561 if (code == GIMPLE_ASSIGN)
1562 {
1563 enum tree_code subcode = gimple_assign_rhs_code (stmt);
1564
1565 /* Other cases cannot satisfy is_gimple_min_invariant
1566 without folding. */
1567 if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
1568 simplified = gimple_assign_rhs1 (stmt);
1569 }
1570 else if (code == GIMPLE_SWITCH)
1571 simplified = gimple_switch_index (stmt);
1572 else
1573 /* These cannot satisfy is_gimple_min_invariant without folding. */
1574 gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
1575 is_constant = simplified && is_gimple_min_invariant (simplified);
1576 if (is_constant)
1577 {
1578 /* The statement produced a constant value. */
1579 val.lattice_val = CONSTANT;
1580 val.value = simplified;
1581 val.mask = double_int_zero;
1582 }
1583 }
1584
1585 /* Resort to simplification for bitwise tracking. */
1586 if (flag_tree_bit_ccp
1587 && (likelyvalue == CONSTANT || is_gimple_call (stmt))
1588 && !is_constant)
1589 {
1590 enum gimple_code code = gimple_code (stmt);
1591 val.lattice_val = VARYING;
1592 val.value = NULL_TREE;
1593 val.mask = double_int_minus_one;
1594 if (code == GIMPLE_ASSIGN)
1595 {
1596 enum tree_code subcode = gimple_assign_rhs_code (stmt);
1597 tree rhs1 = gimple_assign_rhs1 (stmt);
1598 switch (get_gimple_rhs_class (subcode))
1599 {
1600 case GIMPLE_SINGLE_RHS:
1601 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1602 || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1603 val = get_value_for_expr (rhs1, true);
1604 break;
1605
1606 case GIMPLE_UNARY_RHS:
1607 if ((INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1608 || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1609 && (INTEGRAL_TYPE_P (gimple_expr_type (stmt))
1610 || POINTER_TYPE_P (gimple_expr_type (stmt))))
1611 val = bit_value_unop (subcode, gimple_expr_type (stmt), rhs1);
1612 break;
1613
1614 case GIMPLE_BINARY_RHS:
1615 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1616 || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1617 {
1618 tree lhs = gimple_assign_lhs (stmt);
1619 tree rhs2 = gimple_assign_rhs2 (stmt);
1620 val = bit_value_binop (subcode,
1621 TREE_TYPE (lhs), rhs1, rhs2);
1622 }
1623 break;
1624
1625 default:;
1626 }
1627 }
1628 else if (code == GIMPLE_COND)
1629 {
1630 enum tree_code code = gimple_cond_code (stmt);
1631 tree rhs1 = gimple_cond_lhs (stmt);
1632 tree rhs2 = gimple_cond_rhs (stmt);
1633 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1634 || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1635 val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
1636 }
1637 else if (gimple_call_builtin_class_p (stmt, BUILT_IN_NORMAL))
1638 {
1639 tree fndecl = gimple_call_fndecl (stmt);
1640 switch (DECL_FUNCTION_CODE (fndecl))
1641 {
1642 case BUILT_IN_MALLOC:
1643 case BUILT_IN_REALLOC:
1644 case BUILT_IN_CALLOC:
1645 case BUILT_IN_STRDUP:
1646 case BUILT_IN_STRNDUP:
1647 val.lattice_val = CONSTANT;
1648 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
1649 val.mask = shwi_to_double_int
1650 (~(((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT)
1651 / BITS_PER_UNIT - 1));
1652 break;
1653
1654 case BUILT_IN_ALLOCA:
1655 case BUILT_IN_ALLOCA_WITH_ALIGN:
1656 align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA_WITH_ALIGN
1657 ? TREE_INT_CST_LOW (gimple_call_arg (stmt, 1))
1658 : BIGGEST_ALIGNMENT);
1659 val.lattice_val = CONSTANT;
1660 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
1661 val.mask = shwi_to_double_int
1662 (~(((HOST_WIDE_INT) align)
1663 / BITS_PER_UNIT - 1));
1664 break;
1665
1666 /* These builtins return their first argument, unmodified. */
1667 case BUILT_IN_MEMCPY:
1668 case BUILT_IN_MEMMOVE:
1669 case BUILT_IN_MEMSET:
1670 case BUILT_IN_STRCPY:
1671 case BUILT_IN_STRNCPY:
1672 case BUILT_IN_MEMCPY_CHK:
1673 case BUILT_IN_MEMMOVE_CHK:
1674 case BUILT_IN_MEMSET_CHK:
1675 case BUILT_IN_STRCPY_CHK:
1676 case BUILT_IN_STRNCPY_CHK:
1677 val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
1678 break;
1679
1680 case BUILT_IN_ASSUME_ALIGNED:
1681 val = bit_value_assume_aligned (stmt);
1682 break;
1683
1684 default:;
1685 }
1686 }
1687 is_constant = (val.lattice_val == CONSTANT);
1688 }
1689
1690 if (!is_constant)
1691 {
1692 /* The statement produced a nonconstant value. If the statement
1693 had UNDEFINED operands, then the result of the statement
1694 should be UNDEFINED. Otherwise, the statement is VARYING. */
1695 if (likelyvalue == UNDEFINED)
1696 {
1697 val.lattice_val = likelyvalue;
1698 val.mask = double_int_zero;
1699 }
1700 else
1701 {
1702 val.lattice_val = VARYING;
1703 val.mask = double_int_minus_one;
1704 }
1705
1706 val.value = NULL_TREE;
1707 }
1708
1709 return val;
1710 }
1711
1712 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
1713 each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
1714
1715 static void
insert_clobber_before_stack_restore(tree saved_val,tree var,htab_t * visited)1716 insert_clobber_before_stack_restore (tree saved_val, tree var, htab_t *visited)
1717 {
1718 gimple stmt, clobber_stmt;
1719 tree clobber;
1720 imm_use_iterator iter;
1721 gimple_stmt_iterator i;
1722 gimple *slot;
1723
1724 FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
1725 if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
1726 {
1727 clobber = build_constructor (TREE_TYPE (var), NULL);
1728 TREE_THIS_VOLATILE (clobber) = 1;
1729 clobber_stmt = gimple_build_assign (var, clobber);
1730
1731 i = gsi_for_stmt (stmt);
1732 gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
1733 }
1734 else if (gimple_code (stmt) == GIMPLE_PHI)
1735 {
1736 if (*visited == NULL)
1737 *visited = htab_create (10, htab_hash_pointer, htab_eq_pointer, NULL);
1738
1739 slot = (gimple *)htab_find_slot (*visited, stmt, INSERT);
1740 if (*slot != NULL)
1741 continue;
1742
1743 *slot = stmt;
1744 insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
1745 visited);
1746 }
1747 else if (gimple_assign_ssa_name_copy_p (stmt))
1748 insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var,
1749 visited);
1750 else
1751 gcc_assert (is_gimple_debug (stmt));
1752 }
1753
1754 /* Advance the iterator to the previous non-debug gimple statement in the same
1755 or dominating basic block. */
1756
1757 static inline void
gsi_prev_dom_bb_nondebug(gimple_stmt_iterator * i)1758 gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
1759 {
1760 basic_block dom;
1761
1762 gsi_prev_nondebug (i);
1763 while (gsi_end_p (*i))
1764 {
1765 dom = get_immediate_dominator (CDI_DOMINATORS, i->bb);
1766 if (dom == NULL || dom == ENTRY_BLOCK_PTR)
1767 return;
1768
1769 *i = gsi_last_bb (dom);
1770 }
1771 }
1772
1773 /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
1774 a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
1775
1776 It is possible that BUILT_IN_STACK_SAVE cannot be find in a dominator when a
1777 previous pass (such as DOM) duplicated it along multiple paths to a BB. In
1778 that case the function gives up without inserting the clobbers. */
1779
1780 static void
insert_clobbers_for_var(gimple_stmt_iterator i,tree var)1781 insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
1782 {
1783 gimple stmt;
1784 tree saved_val;
1785 htab_t visited = NULL;
1786
1787 for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
1788 {
1789 stmt = gsi_stmt (i);
1790
1791 if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
1792 continue;
1793
1794 saved_val = gimple_call_lhs (stmt);
1795 if (saved_val == NULL_TREE)
1796 continue;
1797
1798 insert_clobber_before_stack_restore (saved_val, var, &visited);
1799 break;
1800 }
1801
1802 if (visited != NULL)
1803 htab_delete (visited);
1804 }
1805
1806 /* Detects a __builtin_alloca_with_align with constant size argument. Declares
1807 fixed-size array and returns the address, if found, otherwise returns
1808 NULL_TREE. */
1809
1810 static tree
fold_builtin_alloca_with_align(gimple stmt)1811 fold_builtin_alloca_with_align (gimple stmt)
1812 {
1813 unsigned HOST_WIDE_INT size, threshold, n_elem;
1814 tree lhs, arg, block, var, elem_type, array_type;
1815
1816 /* Get lhs. */
1817 lhs = gimple_call_lhs (stmt);
1818 if (lhs == NULL_TREE)
1819 return NULL_TREE;
1820
1821 /* Detect constant argument. */
1822 arg = get_constant_value (gimple_call_arg (stmt, 0));
1823 if (arg == NULL_TREE
1824 || TREE_CODE (arg) != INTEGER_CST
1825 || !host_integerp (arg, 1))
1826 return NULL_TREE;
1827
1828 size = TREE_INT_CST_LOW (arg);
1829
1830 /* Heuristic: don't fold large allocas. */
1831 threshold = (unsigned HOST_WIDE_INT)PARAM_VALUE (PARAM_LARGE_STACK_FRAME);
1832 /* In case the alloca is located at function entry, it has the same lifetime
1833 as a declared array, so we allow a larger size. */
1834 block = gimple_block (stmt);
1835 if (!(cfun->after_inlining
1836 && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
1837 threshold /= 10;
1838 if (size > threshold)
1839 return NULL_TREE;
1840
1841 /* Declare array. */
1842 elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
1843 n_elem = size * 8 / BITS_PER_UNIT;
1844 array_type = build_array_type_nelts (elem_type, n_elem);
1845 var = create_tmp_var (array_type, NULL);
1846 DECL_ALIGN (var) = TREE_INT_CST_LOW (gimple_call_arg (stmt, 1));
1847 {
1848 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
1849 if (pi != NULL && !pi->pt.anything)
1850 {
1851 bool singleton_p;
1852 unsigned uid;
1853 singleton_p = pt_solution_singleton_p (&pi->pt, &uid);
1854 gcc_assert (singleton_p);
1855 SET_DECL_PT_UID (var, uid);
1856 }
1857 }
1858
1859 /* Fold alloca to the address of the array. */
1860 return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
1861 }
1862
1863 /* Fold the stmt at *GSI with CCP specific information that propagating
1864 and regular folding does not catch. */
1865
1866 static bool
ccp_fold_stmt(gimple_stmt_iterator * gsi)1867 ccp_fold_stmt (gimple_stmt_iterator *gsi)
1868 {
1869 gimple stmt = gsi_stmt (*gsi);
1870
1871 switch (gimple_code (stmt))
1872 {
1873 case GIMPLE_COND:
1874 {
1875 prop_value_t val;
1876 /* Statement evaluation will handle type mismatches in constants
1877 more gracefully than the final propagation. This allows us to
1878 fold more conditionals here. */
1879 val = evaluate_stmt (stmt);
1880 if (val.lattice_val != CONSTANT
1881 || !double_int_zero_p (val.mask))
1882 return false;
1883
1884 if (dump_file)
1885 {
1886 fprintf (dump_file, "Folding predicate ");
1887 print_gimple_expr (dump_file, stmt, 0, 0);
1888 fprintf (dump_file, " to ");
1889 print_generic_expr (dump_file, val.value, 0);
1890 fprintf (dump_file, "\n");
1891 }
1892
1893 if (integer_zerop (val.value))
1894 gimple_cond_make_false (stmt);
1895 else
1896 gimple_cond_make_true (stmt);
1897
1898 return true;
1899 }
1900
1901 case GIMPLE_CALL:
1902 {
1903 tree lhs = gimple_call_lhs (stmt);
1904 int flags = gimple_call_flags (stmt);
1905 tree val;
1906 tree argt;
1907 bool changed = false;
1908 unsigned i;
1909
1910 /* If the call was folded into a constant make sure it goes
1911 away even if we cannot propagate into all uses because of
1912 type issues. */
1913 if (lhs
1914 && TREE_CODE (lhs) == SSA_NAME
1915 && (val = get_constant_value (lhs))
1916 /* Don't optimize away calls that have side-effects. */
1917 && (flags & (ECF_CONST|ECF_PURE)) != 0
1918 && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
1919 {
1920 tree new_rhs = unshare_expr (val);
1921 bool res;
1922 if (!useless_type_conversion_p (TREE_TYPE (lhs),
1923 TREE_TYPE (new_rhs)))
1924 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
1925 res = update_call_from_tree (gsi, new_rhs);
1926 gcc_assert (res);
1927 return true;
1928 }
1929
1930 /* Internal calls provide no argument types, so the extra laxity
1931 for normal calls does not apply. */
1932 if (gimple_call_internal_p (stmt))
1933 return false;
1934
1935 /* The heuristic of fold_builtin_alloca_with_align differs before and
1936 after inlining, so we don't require the arg to be changed into a
1937 constant for folding, but just to be constant. */
1938 if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN))
1939 {
1940 tree new_rhs = fold_builtin_alloca_with_align (stmt);
1941 if (new_rhs)
1942 {
1943 bool res = update_call_from_tree (gsi, new_rhs);
1944 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
1945 gcc_assert (res);
1946 insert_clobbers_for_var (*gsi, var);
1947 return true;
1948 }
1949 }
1950
1951 /* Propagate into the call arguments. Compared to replace_uses_in
1952 this can use the argument slot types for type verification
1953 instead of the current argument type. We also can safely
1954 drop qualifiers here as we are dealing with constants anyway. */
1955 argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
1956 for (i = 0; i < gimple_call_num_args (stmt) && argt;
1957 ++i, argt = TREE_CHAIN (argt))
1958 {
1959 tree arg = gimple_call_arg (stmt, i);
1960 if (TREE_CODE (arg) == SSA_NAME
1961 && (val = get_constant_value (arg))
1962 && useless_type_conversion_p
1963 (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
1964 TYPE_MAIN_VARIANT (TREE_TYPE (val))))
1965 {
1966 gimple_call_set_arg (stmt, i, unshare_expr (val));
1967 changed = true;
1968 }
1969 }
1970
1971 return changed;
1972 }
1973
1974 case GIMPLE_ASSIGN:
1975 {
1976 tree lhs = gimple_assign_lhs (stmt);
1977 tree val;
1978
1979 /* If we have a load that turned out to be constant replace it
1980 as we cannot propagate into all uses in all cases. */
1981 if (gimple_assign_single_p (stmt)
1982 && TREE_CODE (lhs) == SSA_NAME
1983 && (val = get_constant_value (lhs)))
1984 {
1985 tree rhs = unshare_expr (val);
1986 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
1987 rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
1988 gimple_assign_set_rhs_from_tree (gsi, rhs);
1989 return true;
1990 }
1991
1992 return false;
1993 }
1994
1995 default:
1996 return false;
1997 }
1998 }
1999
2000 /* Visit the assignment statement STMT. Set the value of its LHS to the
2001 value computed by the RHS and store LHS in *OUTPUT_P. If STMT
2002 creates virtual definitions, set the value of each new name to that
2003 of the RHS (if we can derive a constant out of the RHS).
2004 Value-returning call statements also perform an assignment, and
2005 are handled here. */
2006
2007 static enum ssa_prop_result
visit_assignment(gimple stmt,tree * output_p)2008 visit_assignment (gimple stmt, tree *output_p)
2009 {
2010 prop_value_t val;
2011 enum ssa_prop_result retval;
2012
2013 tree lhs = gimple_get_lhs (stmt);
2014
2015 gcc_assert (gimple_code (stmt) != GIMPLE_CALL
2016 || gimple_call_lhs (stmt) != NULL_TREE);
2017
2018 if (gimple_assign_single_p (stmt)
2019 && gimple_assign_rhs_code (stmt) == SSA_NAME)
2020 /* For a simple copy operation, we copy the lattice values. */
2021 val = *get_value (gimple_assign_rhs1 (stmt));
2022 else
2023 /* Evaluate the statement, which could be
2024 either a GIMPLE_ASSIGN or a GIMPLE_CALL. */
2025 val = evaluate_stmt (stmt);
2026
2027 retval = SSA_PROP_NOT_INTERESTING;
2028
2029 /* Set the lattice value of the statement's output. */
2030 if (TREE_CODE (lhs) == SSA_NAME)
2031 {
2032 /* If STMT is an assignment to an SSA_NAME, we only have one
2033 value to set. */
2034 if (set_lattice_value (lhs, val))
2035 {
2036 *output_p = lhs;
2037 if (val.lattice_val == VARYING)
2038 retval = SSA_PROP_VARYING;
2039 else
2040 retval = SSA_PROP_INTERESTING;
2041 }
2042 }
2043
2044 return retval;
2045 }
2046
2047
2048 /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
2049 if it can determine which edge will be taken. Otherwise, return
2050 SSA_PROP_VARYING. */
2051
2052 static enum ssa_prop_result
visit_cond_stmt(gimple stmt,edge * taken_edge_p)2053 visit_cond_stmt (gimple stmt, edge *taken_edge_p)
2054 {
2055 prop_value_t val;
2056 basic_block block;
2057
2058 block = gimple_bb (stmt);
2059 val = evaluate_stmt (stmt);
2060 if (val.lattice_val != CONSTANT
2061 || !double_int_zero_p (val.mask))
2062 return SSA_PROP_VARYING;
2063
2064 /* Find which edge out of the conditional block will be taken and add it
2065 to the worklist. If no single edge can be determined statically,
2066 return SSA_PROP_VARYING to feed all the outgoing edges to the
2067 propagation engine. */
2068 *taken_edge_p = find_taken_edge (block, val.value);
2069 if (*taken_edge_p)
2070 return SSA_PROP_INTERESTING;
2071 else
2072 return SSA_PROP_VARYING;
2073 }
2074
2075
2076 /* Evaluate statement STMT. If the statement produces an output value and
2077 its evaluation changes the lattice value of its output, return
2078 SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2079 output value.
2080
2081 If STMT is a conditional branch and we can determine its truth
2082 value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
2083 value, return SSA_PROP_VARYING. */
2084
2085 static enum ssa_prop_result
ccp_visit_stmt(gimple stmt,edge * taken_edge_p,tree * output_p)2086 ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p)
2087 {
2088 tree def;
2089 ssa_op_iter iter;
2090
2091 if (dump_file && (dump_flags & TDF_DETAILS))
2092 {
2093 fprintf (dump_file, "\nVisiting statement:\n");
2094 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2095 }
2096
2097 switch (gimple_code (stmt))
2098 {
2099 case GIMPLE_ASSIGN:
2100 /* If the statement is an assignment that produces a single
2101 output value, evaluate its RHS to see if the lattice value of
2102 its output has changed. */
2103 return visit_assignment (stmt, output_p);
2104
2105 case GIMPLE_CALL:
2106 /* A value-returning call also performs an assignment. */
2107 if (gimple_call_lhs (stmt) != NULL_TREE)
2108 return visit_assignment (stmt, output_p);
2109 break;
2110
2111 case GIMPLE_COND:
2112 case GIMPLE_SWITCH:
2113 /* If STMT is a conditional branch, see if we can determine
2114 which branch will be taken. */
2115 /* FIXME. It appears that we should be able to optimize
2116 computed GOTOs here as well. */
2117 return visit_cond_stmt (stmt, taken_edge_p);
2118
2119 default:
2120 break;
2121 }
2122
2123 /* Any other kind of statement is not interesting for constant
2124 propagation and, therefore, not worth simulating. */
2125 if (dump_file && (dump_flags & TDF_DETAILS))
2126 fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
2127
2128 /* Definitions made by statements other than assignments to
2129 SSA_NAMEs represent unknown modifications to their outputs.
2130 Mark them VARYING. */
2131 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
2132 {
2133 prop_value_t v = { VARYING, NULL_TREE, { -1, (HOST_WIDE_INT) -1 } };
2134 set_lattice_value (def, v);
2135 }
2136
2137 return SSA_PROP_VARYING;
2138 }
2139
2140
2141 /* Main entry point for SSA Conditional Constant Propagation. */
2142
2143 static unsigned int
do_ssa_ccp(void)2144 do_ssa_ccp (void)
2145 {
2146 unsigned int todo = 0;
2147 calculate_dominance_info (CDI_DOMINATORS);
2148 ccp_initialize ();
2149 ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
2150 if (ccp_finalize ())
2151 todo = (TODO_cleanup_cfg | TODO_update_ssa | TODO_remove_unused_locals);
2152 free_dominance_info (CDI_DOMINATORS);
2153 return todo;
2154 }
2155
2156
2157 static bool
gate_ccp(void)2158 gate_ccp (void)
2159 {
2160 return flag_tree_ccp != 0;
2161 }
2162
2163
2164 struct gimple_opt_pass pass_ccp =
2165 {
2166 {
2167 GIMPLE_PASS,
2168 "ccp", /* name */
2169 gate_ccp, /* gate */
2170 do_ssa_ccp, /* execute */
2171 NULL, /* sub */
2172 NULL, /* next */
2173 0, /* static_pass_number */
2174 TV_TREE_CCP, /* tv_id */
2175 PROP_cfg | PROP_ssa, /* properties_required */
2176 0, /* properties_provided */
2177 0, /* properties_destroyed */
2178 0, /* todo_flags_start */
2179 TODO_verify_ssa
2180 | TODO_verify_stmts | TODO_ggc_collect/* todo_flags_finish */
2181 }
2182 };
2183
2184
2185
2186 /* Try to optimize out __builtin_stack_restore. Optimize it out
2187 if there is another __builtin_stack_restore in the same basic
2188 block and no calls or ASM_EXPRs are in between, or if this block's
2189 only outgoing edge is to EXIT_BLOCK and there are no calls or
2190 ASM_EXPRs after this __builtin_stack_restore. */
2191
2192 static tree
optimize_stack_restore(gimple_stmt_iterator i)2193 optimize_stack_restore (gimple_stmt_iterator i)
2194 {
2195 tree callee;
2196 gimple stmt;
2197
2198 basic_block bb = gsi_bb (i);
2199 gimple call = gsi_stmt (i);
2200
2201 if (gimple_code (call) != GIMPLE_CALL
2202 || gimple_call_num_args (call) != 1
2203 || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
2204 || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
2205 return NULL_TREE;
2206
2207 for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
2208 {
2209 stmt = gsi_stmt (i);
2210 if (gimple_code (stmt) == GIMPLE_ASM)
2211 return NULL_TREE;
2212 if (gimple_code (stmt) != GIMPLE_CALL)
2213 continue;
2214
2215 callee = gimple_call_fndecl (stmt);
2216 if (!callee
2217 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2218 /* All regular builtins are ok, just obviously not alloca. */
2219 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA
2220 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA_WITH_ALIGN)
2221 return NULL_TREE;
2222
2223 if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE)
2224 goto second_stack_restore;
2225 }
2226
2227 if (!gsi_end_p (i))
2228 return NULL_TREE;
2229
2230 /* Allow one successor of the exit block, or zero successors. */
2231 switch (EDGE_COUNT (bb->succs))
2232 {
2233 case 0:
2234 break;
2235 case 1:
2236 if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR)
2237 return NULL_TREE;
2238 break;
2239 default:
2240 return NULL_TREE;
2241 }
2242 second_stack_restore:
2243
2244 /* If there's exactly one use, then zap the call to __builtin_stack_save.
2245 If there are multiple uses, then the last one should remove the call.
2246 In any case, whether the call to __builtin_stack_save can be removed
2247 or not is irrelevant to removing the call to __builtin_stack_restore. */
2248 if (has_single_use (gimple_call_arg (call, 0)))
2249 {
2250 gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
2251 if (is_gimple_call (stack_save))
2252 {
2253 callee = gimple_call_fndecl (stack_save);
2254 if (callee
2255 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
2256 && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE)
2257 {
2258 gimple_stmt_iterator stack_save_gsi;
2259 tree rhs;
2260
2261 stack_save_gsi = gsi_for_stmt (stack_save);
2262 rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
2263 update_call_from_tree (&stack_save_gsi, rhs);
2264 }
2265 }
2266 }
2267
2268 /* No effect, so the statement will be deleted. */
2269 return integer_zero_node;
2270 }
2271
2272 /* If va_list type is a simple pointer and nothing special is needed,
2273 optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
2274 __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
2275 pointer assignment. */
2276
2277 static tree
optimize_stdarg_builtin(gimple call)2278 optimize_stdarg_builtin (gimple call)
2279 {
2280 tree callee, lhs, rhs, cfun_va_list;
2281 bool va_list_simple_ptr;
2282 location_t loc = gimple_location (call);
2283
2284 if (gimple_code (call) != GIMPLE_CALL)
2285 return NULL_TREE;
2286
2287 callee = gimple_call_fndecl (call);
2288
2289 cfun_va_list = targetm.fn_abi_va_list (callee);
2290 va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
2291 && (TREE_TYPE (cfun_va_list) == void_type_node
2292 || TREE_TYPE (cfun_va_list) == char_type_node);
2293
2294 switch (DECL_FUNCTION_CODE (callee))
2295 {
2296 case BUILT_IN_VA_START:
2297 if (!va_list_simple_ptr
2298 || targetm.expand_builtin_va_start != NULL
2299 || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG))
2300 return NULL_TREE;
2301
2302 if (gimple_call_num_args (call) != 2)
2303 return NULL_TREE;
2304
2305 lhs = gimple_call_arg (call, 0);
2306 if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2307 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2308 != TYPE_MAIN_VARIANT (cfun_va_list))
2309 return NULL_TREE;
2310
2311 lhs = build_fold_indirect_ref_loc (loc, lhs);
2312 rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG),
2313 1, integer_zero_node);
2314 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
2315 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2316
2317 case BUILT_IN_VA_COPY:
2318 if (!va_list_simple_ptr)
2319 return NULL_TREE;
2320
2321 if (gimple_call_num_args (call) != 2)
2322 return NULL_TREE;
2323
2324 lhs = gimple_call_arg (call, 0);
2325 if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2326 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2327 != TYPE_MAIN_VARIANT (cfun_va_list))
2328 return NULL_TREE;
2329
2330 lhs = build_fold_indirect_ref_loc (loc, lhs);
2331 rhs = gimple_call_arg (call, 1);
2332 if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
2333 != TYPE_MAIN_VARIANT (cfun_va_list))
2334 return NULL_TREE;
2335
2336 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
2337 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2338
2339 case BUILT_IN_VA_END:
2340 /* No effect, so the statement will be deleted. */
2341 return integer_zero_node;
2342
2343 default:
2344 gcc_unreachable ();
2345 }
2346 }
2347
2348 /* A simple pass that attempts to fold all builtin functions. This pass
2349 is run after we've propagated as many constants as we can. */
2350
2351 static unsigned int
execute_fold_all_builtins(void)2352 execute_fold_all_builtins (void)
2353 {
2354 bool cfg_changed = false;
2355 basic_block bb;
2356 unsigned int todoflags = 0;
2357
2358 FOR_EACH_BB (bb)
2359 {
2360 gimple_stmt_iterator i;
2361 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
2362 {
2363 gimple stmt, old_stmt;
2364 tree callee, result;
2365 enum built_in_function fcode;
2366
2367 stmt = gsi_stmt (i);
2368
2369 if (gimple_code (stmt) != GIMPLE_CALL)
2370 {
2371 gsi_next (&i);
2372 continue;
2373 }
2374 callee = gimple_call_fndecl (stmt);
2375 if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2376 {
2377 gsi_next (&i);
2378 continue;
2379 }
2380 fcode = DECL_FUNCTION_CODE (callee);
2381
2382 result = gimple_fold_builtin (stmt);
2383
2384 if (result)
2385 gimple_remove_stmt_histograms (cfun, stmt);
2386
2387 if (!result)
2388 switch (DECL_FUNCTION_CODE (callee))
2389 {
2390 case BUILT_IN_CONSTANT_P:
2391 /* Resolve __builtin_constant_p. If it hasn't been
2392 folded to integer_one_node by now, it's fairly
2393 certain that the value simply isn't constant. */
2394 result = integer_zero_node;
2395 break;
2396
2397 case BUILT_IN_ASSUME_ALIGNED:
2398 /* Remove __builtin_assume_aligned. */
2399 result = gimple_call_arg (stmt, 0);
2400 break;
2401
2402 case BUILT_IN_STACK_RESTORE:
2403 result = optimize_stack_restore (i);
2404 if (result)
2405 break;
2406 gsi_next (&i);
2407 continue;
2408
2409 case BUILT_IN_VA_START:
2410 case BUILT_IN_VA_END:
2411 case BUILT_IN_VA_COPY:
2412 /* These shouldn't be folded before pass_stdarg. */
2413 result = optimize_stdarg_builtin (stmt);
2414 if (result)
2415 break;
2416 /* FALLTHRU */
2417
2418 default:
2419 gsi_next (&i);
2420 continue;
2421 }
2422
2423 if (dump_file && (dump_flags & TDF_DETAILS))
2424 {
2425 fprintf (dump_file, "Simplified\n ");
2426 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2427 }
2428
2429 old_stmt = stmt;
2430 if (!update_call_from_tree (&i, result))
2431 {
2432 gimplify_and_update_call_from_tree (&i, result);
2433 todoflags |= TODO_update_address_taken;
2434 }
2435
2436 stmt = gsi_stmt (i);
2437 update_stmt (stmt);
2438
2439 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
2440 && gimple_purge_dead_eh_edges (bb))
2441 cfg_changed = true;
2442
2443 if (dump_file && (dump_flags & TDF_DETAILS))
2444 {
2445 fprintf (dump_file, "to\n ");
2446 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2447 fprintf (dump_file, "\n");
2448 }
2449
2450 /* Retry the same statement if it changed into another
2451 builtin, there might be new opportunities now. */
2452 if (gimple_code (stmt) != GIMPLE_CALL)
2453 {
2454 gsi_next (&i);
2455 continue;
2456 }
2457 callee = gimple_call_fndecl (stmt);
2458 if (!callee
2459 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2460 || DECL_FUNCTION_CODE (callee) == fcode)
2461 gsi_next (&i);
2462 }
2463 }
2464
2465 /* Delete unreachable blocks. */
2466 if (cfg_changed)
2467 todoflags |= TODO_cleanup_cfg;
2468
2469 return todoflags;
2470 }
2471
2472
2473 struct gimple_opt_pass pass_fold_builtins =
2474 {
2475 {
2476 GIMPLE_PASS,
2477 "fab", /* name */
2478 NULL, /* gate */
2479 execute_fold_all_builtins, /* execute */
2480 NULL, /* sub */
2481 NULL, /* next */
2482 0, /* static_pass_number */
2483 TV_NONE, /* tv_id */
2484 PROP_cfg | PROP_ssa, /* properties_required */
2485 0, /* properties_provided */
2486 0, /* properties_destroyed */
2487 0, /* todo_flags_start */
2488 TODO_verify_ssa
2489 | TODO_update_ssa /* todo_flags_finish */
2490 }
2491 };
2492