1 /* Conditional constant propagation pass for the GNU compiler.
2 Copyright (C) 2000-2016 Free Software Foundation, Inc.
3 Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org>
4 Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it
9 under the terms of the GNU General Public License as published by the
10 Free Software Foundation; either version 3, or (at your option) any
13 GCC is distributed in the hope that it will be useful, but WITHOUT
14 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 /* Conditional constant propagation (CCP) is based on the SSA
23 propagation engine (tree-ssa-propagate.c). Constant assignments of
24 the form VAR = CST are propagated from the assignments into uses of
25 VAR, which in turn may generate new constants. The simulation uses
26 a four level lattice to keep track of constant values associated
27 with SSA names. Given an SSA name V_i, it may take one of the
30 UNINITIALIZED -> the initial state of the value. This value
31 is replaced with a correct initial value
32 the first time the value is used, so the
33 rest of the pass does not need to care about
34 it. Using this value simplifies initialization
35 of the pass, and prevents us from needlessly
36 scanning statements that are never reached.
38 UNDEFINED -> V_i is a local variable whose definition
39 has not been processed yet. Therefore we
40 don't yet know if its value is a constant
43 CONSTANT -> V_i has been found to hold a constant
46 VARYING -> V_i cannot take a constant value, or if it
47 does, it is not possible to determine it
50 The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node:
52 1- In ccp_visit_stmt, we are interested in assignments whose RHS
53 evaluates into a constant and conditional jumps whose predicate
54 evaluates into a boolean true or false. When an assignment of
55 the form V_i = CONST is found, V_i's lattice value is set to
56 CONSTANT and CONST is associated with it. This causes the
57 propagation engine to add all the SSA edges coming out the
58 assignment into the worklists, so that statements that use V_i
61 If the statement is a conditional with a constant predicate, we
62 mark the outgoing edges as executable or not executable
63 depending on the predicate's value. This is then used when
64 visiting PHI nodes to know when a PHI argument can be ignored.
67 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the
68 same constant C, then the LHS of the PHI is set to C. This
69 evaluation is known as the "meet operation". Since one of the
70 goals of this evaluation is to optimistically return constant
71 values as often as possible, it uses two main short cuts:
73 - If an argument is flowing in through a non-executable edge, it
74 is ignored. This is useful in cases like this:
80 a_11 = PHI (a_9, a_10)
82 If PRED is known to always evaluate to false, then we can
83 assume that a_11 will always take its value from a_10, meaning
84 that instead of consider it VARYING (a_9 and a_10 have
85 different values), we can consider it CONSTANT 100.
87 - If an argument has an UNDEFINED value, then it does not affect
88 the outcome of the meet operation. If a variable V_i has an
89 UNDEFINED value, it means that either its defining statement
90 hasn't been visited yet or V_i has no defining statement, in
91 which case the original symbol 'V' is being used
92 uninitialized. Since 'V' is a local variable, the compiler
93 may assume any initial value for it.
96 After propagation, every variable V_i that ends up with a lattice
97 value of CONSTANT will have the associated constant value in the
98 array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for
99 final substitution and folding.
101 This algorithm uses wide-ints at the max precision of the target.
102 This means that, with one uninteresting exception, variables with
103 UNSIGNED types never go to VARYING because the bits above the
104 precision of the type of the variable are always zero. The
105 uninteresting case is a variable of UNSIGNED type that has the
106 maximum precision of the target. Such variables can go to VARYING,
107 but this causes no loss of infomation since these variables will
112 Constant propagation with conditional branches,
113 Wegman and Zadeck, ACM TOPLAS 13(2):181-210.
115 Building an Optimizing Compiler,
116 Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9.
118 Advanced Compiler Design and Implementation,
119 Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */
123 #include "coretypes.h"
128 #include "tree-pass.h"
130 #include "gimple-pretty-print.h"
131 #include "fold-const.h"
132 #include "gimple-fold.h"
134 #include "gimplify.h"
135 #include "gimple-iterator.h"
136 #include "tree-cfg.h"
137 #include "tree-ssa-propagate.h"
140 #include "builtins.h"
141 #include "tree-chkp.h"
145 /* Possible lattice values. */
154 struct ccp_prop_value_t {
156 ccp_lattice_t lattice_val;
158 /* Propagated value. */
161 /* Mask that applies to the propagated value during CCP. For X
162 with a CONSTANT lattice value X & ~mask == value & ~mask. The
163 zero bits in the mask cover constant values. The ones mean no
168 /* Array of propagated constant values. After propagation,
169 CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If
170 the constant is held in an SSA name representing a memory store
171 (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual
172 memory reference used to store (i.e., the LHS of the assignment
174 static ccp_prop_value_t *const_val;
175 static unsigned n_const_val;
177 static void canonicalize_value (ccp_prop_value_t *);
178 static bool ccp_fold_stmt (gimple_stmt_iterator *);
179 static void ccp_lattice_meet (ccp_prop_value_t *, ccp_prop_value_t *);
181 /* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */
184 dump_lattice_value (FILE *outf, const char *prefix, ccp_prop_value_t val)
186 switch (val.lattice_val)
189 fprintf (outf, "%sUNINITIALIZED", prefix);
192 fprintf (outf, "%sUNDEFINED", prefix);
195 fprintf (outf, "%sVARYING", prefix);
198 if (TREE_CODE (val.value) != INTEGER_CST
201 fprintf (outf, "%sCONSTANT ", prefix);
202 print_generic_expr (outf, val.value, dump_flags);
206 widest_int cval = wi::bit_and_not (wi::to_widest (val.value),
208 fprintf (outf, "%sCONSTANT ", prefix);
209 print_hex (cval, outf);
210 fprintf (outf, " (");
211 print_hex (val.mask, outf);
221 /* Print lattice value VAL to stderr. */
223 void debug_lattice_value (ccp_prop_value_t val);
226 debug_lattice_value (ccp_prop_value_t val)
228 dump_lattice_value (stderr, "", val);
229 fprintf (stderr, "\n");
232 /* Extend NONZERO_BITS to a full mask, based on sgn. */
235 extend_mask (const wide_int &nonzero_bits, signop sgn)
237 return widest_int::from (nonzero_bits, sgn);
240 /* Compute a default value for variable VAR and store it in the
241 CONST_VAL array. The following rules are used to get default
244 1- Global and static variables that are declared constant are
247 2- Any other value is considered UNDEFINED. This is useful when
248 considering PHI nodes. PHI arguments that are undefined do not
249 change the constant value of the PHI node, which allows for more
250 constants to be propagated.
252 3- Variables defined by statements other than assignments and PHI
253 nodes are considered VARYING.
255 4- Initial values of variables that are not GIMPLE registers are
256 considered VARYING. */
258 static ccp_prop_value_t
259 get_default_value (tree var)
261 ccp_prop_value_t val = { UNINITIALIZED, NULL_TREE, 0 };
264 stmt = SSA_NAME_DEF_STMT (var);
266 if (gimple_nop_p (stmt))
268 /* Variables defined by an empty statement are those used
269 before being initialized. If VAR is a local variable, we
270 can assume initially that it is UNDEFINED, otherwise we must
271 consider it VARYING. */
272 if (!virtual_operand_p (var)
273 && TREE_CODE (SSA_NAME_VAR (var)) == VAR_DECL)
274 val.lattice_val = UNDEFINED;
277 val.lattice_val = VARYING;
279 if (flag_tree_bit_ccp)
281 wide_int nonzero_bits = get_nonzero_bits (var);
282 if (nonzero_bits != -1)
284 val.lattice_val = CONSTANT;
285 val.value = build_zero_cst (TREE_TYPE (var));
286 val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (var)));
291 else if (is_gimple_assign (stmt))
294 if (gimple_assign_single_p (stmt)
295 && DECL_P (gimple_assign_rhs1 (stmt))
296 && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt))))
298 val.lattice_val = CONSTANT;
303 /* Any other variable defined by an assignment is considered
305 val.lattice_val = UNDEFINED;
308 else if ((is_gimple_call (stmt)
309 && gimple_call_lhs (stmt) != NULL_TREE)
310 || gimple_code (stmt) == GIMPLE_PHI)
312 /* A variable defined by a call or a PHI node is considered
314 val.lattice_val = UNDEFINED;
318 /* Otherwise, VAR will never take on a constant value. */
319 val.lattice_val = VARYING;
327 /* Get the constant value associated with variable VAR. */
329 static inline ccp_prop_value_t *
332 ccp_prop_value_t *val;
334 if (const_val == NULL
335 || SSA_NAME_VERSION (var) >= n_const_val)
338 val = &const_val[SSA_NAME_VERSION (var)];
339 if (val->lattice_val == UNINITIALIZED)
340 *val = get_default_value (var);
342 canonicalize_value (val);
347 /* Return the constant tree value associated with VAR. */
350 get_constant_value (tree var)
352 ccp_prop_value_t *val;
353 if (TREE_CODE (var) != SSA_NAME)
355 if (is_gimple_min_invariant (var))
359 val = get_value (var);
361 && val->lattice_val == CONSTANT
362 && (TREE_CODE (val->value) != INTEGER_CST
368 /* Sets the value associated with VAR to VARYING. */
371 set_value_varying (tree var)
373 ccp_prop_value_t *val = &const_val[SSA_NAME_VERSION (var)];
375 val->lattice_val = VARYING;
376 val->value = NULL_TREE;
380 /* For integer constants, make sure to drop TREE_OVERFLOW. */
383 canonicalize_value (ccp_prop_value_t *val)
385 if (val->lattice_val != CONSTANT)
388 if (TREE_OVERFLOW_P (val->value))
389 val->value = drop_tree_overflow (val->value);
392 /* Return whether the lattice transition is valid. */
395 valid_lattice_transition (ccp_prop_value_t old_val, ccp_prop_value_t new_val)
397 /* Lattice transitions must always be monotonically increasing in
399 if (old_val.lattice_val < new_val.lattice_val)
402 if (old_val.lattice_val != new_val.lattice_val)
405 if (!old_val.value && !new_val.value)
408 /* Now both lattice values are CONSTANT. */
410 /* Allow arbitrary copy changes as we might look through PHI <a_1, ...>
411 when only a single copy edge is executable. */
412 if (TREE_CODE (old_val.value) == SSA_NAME
413 && TREE_CODE (new_val.value) == SSA_NAME)
416 /* Allow transitioning from a constant to a copy. */
417 if (is_gimple_min_invariant (old_val.value)
418 && TREE_CODE (new_val.value) == SSA_NAME)
421 /* Allow transitioning from PHI <&x, not executable> == &x
422 to PHI <&x, &y> == common alignment. */
423 if (TREE_CODE (old_val.value) != INTEGER_CST
424 && TREE_CODE (new_val.value) == INTEGER_CST)
427 /* Bit-lattices have to agree in the still valid bits. */
428 if (TREE_CODE (old_val.value) == INTEGER_CST
429 && TREE_CODE (new_val.value) == INTEGER_CST)
430 return (wi::bit_and_not (wi::to_widest (old_val.value), new_val.mask)
431 == wi::bit_and_not (wi::to_widest (new_val.value), new_val.mask));
433 /* Otherwise constant values have to agree. */
434 if (operand_equal_p (old_val.value, new_val.value, 0))
437 /* At least the kinds and types should agree now. */
438 if (TREE_CODE (old_val.value) != TREE_CODE (new_val.value)
439 || !types_compatible_p (TREE_TYPE (old_val.value),
440 TREE_TYPE (new_val.value)))
443 /* For floats and !HONOR_NANS allow transitions from (partial) NaN
445 tree type = TREE_TYPE (new_val.value);
446 if (SCALAR_FLOAT_TYPE_P (type)
447 && !HONOR_NANS (type))
449 if (REAL_VALUE_ISNAN (TREE_REAL_CST (old_val.value)))
452 else if (VECTOR_FLOAT_TYPE_P (type)
453 && !HONOR_NANS (type))
455 for (unsigned i = 0; i < VECTOR_CST_NELTS (old_val.value); ++i)
456 if (!REAL_VALUE_ISNAN
457 (TREE_REAL_CST (VECTOR_CST_ELT (old_val.value, i)))
458 && !operand_equal_p (VECTOR_CST_ELT (old_val.value, i),
459 VECTOR_CST_ELT (new_val.value, i), 0))
463 else if (COMPLEX_FLOAT_TYPE_P (type)
464 && !HONOR_NANS (type))
466 if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_REALPART (old_val.value)))
467 && !operand_equal_p (TREE_REALPART (old_val.value),
468 TREE_REALPART (new_val.value), 0))
470 if (!REAL_VALUE_ISNAN (TREE_REAL_CST (TREE_IMAGPART (old_val.value)))
471 && !operand_equal_p (TREE_IMAGPART (old_val.value),
472 TREE_IMAGPART (new_val.value), 0))
479 /* Set the value for variable VAR to NEW_VAL. Return true if the new
480 value is different from VAR's previous value. */
483 set_lattice_value (tree var, ccp_prop_value_t *new_val)
485 /* We can deal with old UNINITIALIZED values just fine here. */
486 ccp_prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)];
488 canonicalize_value (new_val);
490 /* We have to be careful to not go up the bitwise lattice
491 represented by the mask. Instead of dropping to VARYING
492 use the meet operator to retain a conservative value.
493 Missed optimizations like PR65851 makes this necessary.
494 It also ensures we converge to a stable lattice solution. */
495 if (new_val->lattice_val == CONSTANT
496 && old_val->lattice_val == CONSTANT
497 && TREE_CODE (new_val->value) != SSA_NAME)
498 ccp_lattice_meet (new_val, old_val);
500 gcc_checking_assert (valid_lattice_transition (*old_val, *new_val));
502 /* If *OLD_VAL and NEW_VAL are the same, return false to inform the
503 caller that this was a non-transition. */
504 if (old_val->lattice_val != new_val->lattice_val
505 || (new_val->lattice_val == CONSTANT
506 && (TREE_CODE (new_val->value) != TREE_CODE (old_val->value)
507 || (TREE_CODE (new_val->value) == INTEGER_CST
508 && (new_val->mask != old_val->mask
509 || (wi::bit_and_not (wi::to_widest (old_val->value),
511 != wi::bit_and_not (wi::to_widest (new_val->value),
513 || (TREE_CODE (new_val->value) != INTEGER_CST
514 && !operand_equal_p (new_val->value, old_val->value, 0)))))
516 /* ??? We would like to delay creation of INTEGER_CSTs from
517 partially constants here. */
519 if (dump_file && (dump_flags & TDF_DETAILS))
521 dump_lattice_value (dump_file, "Lattice value changed to ", *new_val);
522 fprintf (dump_file, ". Adding SSA edges to worklist.\n");
527 gcc_assert (new_val->lattice_val != UNINITIALIZED);
534 static ccp_prop_value_t get_value_for_expr (tree, bool);
535 static ccp_prop_value_t bit_value_binop (enum tree_code, tree, tree, tree);
536 static void bit_value_binop_1 (enum tree_code, tree, widest_int *, widest_int *,
537 tree, const widest_int &, const widest_int &,
538 tree, const widest_int &, const widest_int &);
540 /* Return a widest_int that can be used for bitwise simplifications
544 value_to_wide_int (ccp_prop_value_t val)
547 && TREE_CODE (val.value) == INTEGER_CST)
548 return wi::to_widest (val.value);
553 /* Return the value for the address expression EXPR based on alignment
556 static ccp_prop_value_t
557 get_value_from_alignment (tree expr)
559 tree type = TREE_TYPE (expr);
560 ccp_prop_value_t val;
561 unsigned HOST_WIDE_INT bitpos;
564 gcc_assert (TREE_CODE (expr) == ADDR_EXPR);
566 get_pointer_alignment_1 (expr, &align, &bitpos);
567 val.mask = (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type)
568 ? wi::mask <widest_int> (TYPE_PRECISION (type), false)
569 : -1).and_not (align / BITS_PER_UNIT - 1);
571 = wi::sext (val.mask, TYPE_PRECISION (type)) == -1 ? VARYING : CONSTANT;
572 if (val.lattice_val == CONSTANT)
573 val.value = build_int_cstu (type, bitpos / BITS_PER_UNIT);
575 val.value = NULL_TREE;
580 /* Return the value for the tree operand EXPR. If FOR_BITS_P is true
581 return constant bits extracted from alignment information for
582 invariant addresses. */
584 static ccp_prop_value_t
585 get_value_for_expr (tree expr, bool for_bits_p)
587 ccp_prop_value_t val;
589 if (TREE_CODE (expr) == SSA_NAME)
591 val = *get_value (expr);
593 && val.lattice_val == CONSTANT
594 && TREE_CODE (val.value) == ADDR_EXPR)
595 val = get_value_from_alignment (val.value);
596 /* Fall back to a copy value. */
598 && val.lattice_val == VARYING
599 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (expr))
601 val.lattice_val = CONSTANT;
606 else if (is_gimple_min_invariant (expr)
607 && (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR))
609 val.lattice_val = CONSTANT;
612 canonicalize_value (&val);
614 else if (TREE_CODE (expr) == ADDR_EXPR)
615 val = get_value_from_alignment (expr);
618 val.lattice_val = VARYING;
620 val.value = NULL_TREE;
623 if (val.lattice_val == VARYING
624 && TYPE_UNSIGNED (TREE_TYPE (expr)))
625 val.mask = wi::zext (val.mask, TYPE_PRECISION (TREE_TYPE (expr)));
630 /* Return the likely CCP lattice value for STMT.
632 If STMT has no operands, then return CONSTANT.
634 Else if undefinedness of operands of STMT cause its value to be
635 undefined, then return UNDEFINED.
637 Else if any operands of STMT are constants, then return CONSTANT.
639 Else return VARYING. */
642 likely_value (gimple *stmt)
644 bool has_constant_operand, has_undefined_operand, all_undefined_operands;
645 bool has_nsa_operand;
650 enum gimple_code code = gimple_code (stmt);
652 /* This function appears to be called only for assignments, calls,
653 conditionals, and switches, due to the logic in visit_stmt. */
654 gcc_assert (code == GIMPLE_ASSIGN
655 || code == GIMPLE_CALL
656 || code == GIMPLE_COND
657 || code == GIMPLE_SWITCH);
659 /* If the statement has volatile operands, it won't fold to a
661 if (gimple_has_volatile_ops (stmt))
664 /* Arrive here for more complex cases. */
665 has_constant_operand = false;
666 has_undefined_operand = false;
667 all_undefined_operands = true;
668 has_nsa_operand = false;
669 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
671 ccp_prop_value_t *val = get_value (use);
673 if (val->lattice_val == UNDEFINED)
674 has_undefined_operand = true;
676 all_undefined_operands = false;
678 if (val->lattice_val == CONSTANT)
679 has_constant_operand = true;
681 if (SSA_NAME_IS_DEFAULT_DEF (use)
682 || !prop_simulate_again_p (SSA_NAME_DEF_STMT (use)))
683 has_nsa_operand = true;
686 /* There may be constants in regular rhs operands. For calls we
687 have to ignore lhs, fndecl and static chain, otherwise only
689 for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt);
690 i < gimple_num_ops (stmt); ++i)
692 tree op = gimple_op (stmt, i);
693 if (!op || TREE_CODE (op) == SSA_NAME)
695 if (is_gimple_min_invariant (op))
696 has_constant_operand = true;
699 if (has_constant_operand)
700 all_undefined_operands = false;
702 if (has_undefined_operand
703 && code == GIMPLE_CALL
704 && gimple_call_internal_p (stmt))
705 switch (gimple_call_internal_fn (stmt))
707 /* These 3 builtins use the first argument just as a magic
708 way how to find out a decl uid. */
709 case IFN_GOMP_SIMD_LANE:
710 case IFN_GOMP_SIMD_VF:
711 case IFN_GOMP_SIMD_LAST_LANE:
712 has_undefined_operand = false;
718 /* If the operation combines operands like COMPLEX_EXPR make sure to
719 not mark the result UNDEFINED if only one part of the result is
721 if (has_undefined_operand && all_undefined_operands)
723 else if (code == GIMPLE_ASSIGN && has_undefined_operand)
725 switch (gimple_assign_rhs_code (stmt))
727 /* Unary operators are handled with all_undefined_operands. */
730 case POINTER_PLUS_EXPR:
731 /* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected.
732 Not bitwise operators, one VARYING operand may specify the
733 result completely. Not logical operators for the same reason.
734 Not COMPLEX_EXPR as one VARYING operand makes the result partly
735 not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because
736 the undefined operand may be promoted. */
740 /* If any part of an address is UNDEFINED, like the index
741 of an ARRAY_EXPR, then treat the result as UNDEFINED. */
748 /* If there was an UNDEFINED operand but the result may be not UNDEFINED
749 fall back to CONSTANT. During iteration UNDEFINED may still drop
751 if (has_undefined_operand)
754 /* We do not consider virtual operands here -- load from read-only
755 memory may have only VARYING virtual operands, but still be
756 constant. Also we can combine the stmt with definitions from
757 operands whose definitions are not simulated again. */
758 if (has_constant_operand
760 || gimple_references_memory_p (stmt))
766 /* Returns true if STMT cannot be constant. */
769 surely_varying_stmt_p (gimple *stmt)
771 /* If the statement has operands that we cannot handle, it cannot be
773 if (gimple_has_volatile_ops (stmt))
776 /* If it is a call and does not return a value or is not a
777 builtin and not an indirect call or a call to function with
778 assume_aligned/alloc_align attribute, it is varying. */
779 if (is_gimple_call (stmt))
781 tree fndecl, fntype = gimple_call_fntype (stmt);
782 if (!gimple_call_lhs (stmt)
783 || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE
784 && !DECL_BUILT_IN (fndecl)
785 && !lookup_attribute ("assume_aligned",
786 TYPE_ATTRIBUTES (fntype))
787 && !lookup_attribute ("alloc_align",
788 TYPE_ATTRIBUTES (fntype))))
792 /* Any other store operation is not interesting. */
793 else if (gimple_vdef (stmt))
796 /* Anything other than assignments and conditional jumps are not
797 interesting for CCP. */
798 if (gimple_code (stmt) != GIMPLE_ASSIGN
799 && gimple_code (stmt) != GIMPLE_COND
800 && gimple_code (stmt) != GIMPLE_SWITCH
801 && gimple_code (stmt) != GIMPLE_CALL)
807 /* Initialize local data structures for CCP. */
810 ccp_initialize (void)
814 n_const_val = num_ssa_names;
815 const_val = XCNEWVEC (ccp_prop_value_t, n_const_val);
817 /* Initialize simulation flags for PHI nodes and statements. */
818 FOR_EACH_BB_FN (bb, cfun)
820 gimple_stmt_iterator i;
822 for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i))
824 gimple *stmt = gsi_stmt (i);
827 /* If the statement is a control insn, then we do not
828 want to avoid simulating the statement once. Failure
829 to do so means that those edges will never get added. */
830 if (stmt_ends_bb_p (stmt))
833 is_varying = surely_varying_stmt_p (stmt);
840 /* If the statement will not produce a constant, mark
841 all its outputs VARYING. */
842 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
843 set_value_varying (def);
845 prop_set_simulate_again (stmt, !is_varying);
849 /* Now process PHI nodes. We never clear the simulate_again flag on
850 phi nodes, since we do not know which edges are executable yet,
851 except for phi nodes for virtual operands when we do not do store ccp. */
852 FOR_EACH_BB_FN (bb, cfun)
856 for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i))
858 gphi *phi = i.phi ();
860 if (virtual_operand_p (gimple_phi_result (phi)))
861 prop_set_simulate_again (phi, false);
863 prop_set_simulate_again (phi, true);
868 /* Debug count support. Reset the values of ssa names
869 VARYING when the total number ssa names analyzed is
870 beyond the debug count specified. */
876 for (i = 0; i < num_ssa_names; i++)
880 const_val[i].lattice_val = VARYING;
881 const_val[i].mask = -1;
882 const_val[i].value = NULL_TREE;
888 /* Do final substitution of propagated values, cleanup the flowgraph and
889 free allocated storage. If NONZERO_P, record nonzero bits.
891 Return TRUE when something was optimized. */
894 ccp_finalize (bool nonzero_p)
896 bool something_changed;
901 /* Derive alignment and misalignment information from partially
902 constant pointers in the lattice or nonzero bits from partially
903 constant integers. */
904 for (i = 1; i < num_ssa_names; ++i)
906 tree name = ssa_name (i);
907 ccp_prop_value_t *val;
908 unsigned int tem, align;
911 || (!POINTER_TYPE_P (TREE_TYPE (name))
912 && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
913 /* Don't record nonzero bits before IPA to avoid
914 using too much memory. */
918 val = get_value (name);
919 if (val->lattice_val != CONSTANT
920 || TREE_CODE (val->value) != INTEGER_CST)
923 if (POINTER_TYPE_P (TREE_TYPE (name)))
925 /* Trailing mask bits specify the alignment, trailing value
926 bits the misalignment. */
927 tem = val->mask.to_uhwi ();
928 align = (tem & -tem);
930 set_ptr_info_alignment (get_ptr_info (name), align,
931 (TREE_INT_CST_LOW (val->value)
936 unsigned int precision = TYPE_PRECISION (TREE_TYPE (val->value));
937 wide_int nonzero_bits = wide_int::from (val->mask, precision,
938 UNSIGNED) | val->value;
939 nonzero_bits &= get_nonzero_bits (name);
940 set_nonzero_bits (name, nonzero_bits);
944 /* Perform substitutions based on the known constant values. */
945 something_changed = substitute_and_fold (get_constant_value,
946 ccp_fold_stmt, true);
950 return something_changed;;
954 /* Compute the meet operator between *VAL1 and *VAL2. Store the result
957 any M UNDEFINED = any
958 any M VARYING = VARYING
959 Ci M Cj = Ci if (i == j)
960 Ci M Cj = VARYING if (i != j)
964 ccp_lattice_meet (ccp_prop_value_t *val1, ccp_prop_value_t *val2)
966 if (val1->lattice_val == UNDEFINED
967 /* For UNDEFINED M SSA we can't always SSA because its definition
968 may not dominate the PHI node. Doing optimistic copy propagation
969 also causes a lot of gcc.dg/uninit-pred*.c FAILs. */
970 && (val2->lattice_val != CONSTANT
971 || TREE_CODE (val2->value) != SSA_NAME))
973 /* UNDEFINED M any = any */
976 else if (val2->lattice_val == UNDEFINED
978 && (val1->lattice_val != CONSTANT
979 || TREE_CODE (val1->value) != SSA_NAME))
981 /* any M UNDEFINED = any
982 Nothing to do. VAL1 already contains the value we want. */
985 else if (val1->lattice_val == VARYING
986 || val2->lattice_val == VARYING)
988 /* any M VARYING = VARYING. */
989 val1->lattice_val = VARYING;
991 val1->value = NULL_TREE;
993 else if (val1->lattice_val == CONSTANT
994 && val2->lattice_val == CONSTANT
995 && TREE_CODE (val1->value) == INTEGER_CST
996 && TREE_CODE (val2->value) == INTEGER_CST)
998 /* Ci M Cj = Ci if (i == j)
999 Ci M Cj = VARYING if (i != j)
1001 For INTEGER_CSTs mask unequal bits. If no equal bits remain,
1003 val1->mask = (val1->mask | val2->mask
1004 | (wi::to_widest (val1->value)
1005 ^ wi::to_widest (val2->value)));
1006 if (wi::sext (val1->mask, TYPE_PRECISION (TREE_TYPE (val1->value))) == -1)
1008 val1->lattice_val = VARYING;
1009 val1->value = NULL_TREE;
1012 else if (val1->lattice_val == CONSTANT
1013 && val2->lattice_val == CONSTANT
1014 && operand_equal_p (val1->value, val2->value, 0))
1016 /* Ci M Cj = Ci if (i == j)
1017 Ci M Cj = VARYING if (i != j)
1019 VAL1 already contains the value we want for equivalent values. */
1021 else if (val1->lattice_val == CONSTANT
1022 && val2->lattice_val == CONSTANT
1023 && (TREE_CODE (val1->value) == ADDR_EXPR
1024 || TREE_CODE (val2->value) == ADDR_EXPR))
1026 /* When not equal addresses are involved try meeting for
1028 ccp_prop_value_t tem = *val2;
1029 if (TREE_CODE (val1->value) == ADDR_EXPR)
1030 *val1 = get_value_for_expr (val1->value, true);
1031 if (TREE_CODE (val2->value) == ADDR_EXPR)
1032 tem = get_value_for_expr (val2->value, true);
1033 ccp_lattice_meet (val1, &tem);
1037 /* Any other combination is VARYING. */
1038 val1->lattice_val = VARYING;
1040 val1->value = NULL_TREE;
1045 /* Loop through the PHI_NODE's parameters for BLOCK and compare their
1046 lattice values to determine PHI_NODE's lattice value. The value of a
1047 PHI node is determined calling ccp_lattice_meet with all the arguments
1048 of the PHI node that are incoming via executable edges. */
1050 static enum ssa_prop_result
1051 ccp_visit_phi_node (gphi *phi)
1054 ccp_prop_value_t new_val;
1056 if (dump_file && (dump_flags & TDF_DETAILS))
1058 fprintf (dump_file, "\nVisiting PHI node: ");
1059 print_gimple_stmt (dump_file, phi, 0, dump_flags);
1062 new_val.lattice_val = UNDEFINED;
1063 new_val.value = NULL_TREE;
1067 bool non_exec_edge = false;
1068 for (i = 0; i < gimple_phi_num_args (phi); i++)
1070 /* Compute the meet operator over all the PHI arguments flowing
1071 through executable edges. */
1072 edge e = gimple_phi_arg_edge (phi, i);
1074 if (dump_file && (dump_flags & TDF_DETAILS))
1077 "\n Argument #%d (%d -> %d %sexecutable)\n",
1078 i, e->src->index, e->dest->index,
1079 (e->flags & EDGE_EXECUTABLE) ? "" : "not ");
1082 /* If the incoming edge is executable, Compute the meet operator for
1083 the existing value of the PHI node and the current PHI argument. */
1084 if (e->flags & EDGE_EXECUTABLE)
1086 tree arg = gimple_phi_arg (phi, i)->def;
1087 ccp_prop_value_t arg_val = get_value_for_expr (arg, false);
1095 ccp_lattice_meet (&new_val, &arg_val);
1097 if (dump_file && (dump_flags & TDF_DETAILS))
1099 fprintf (dump_file, "\t");
1100 print_generic_expr (dump_file, arg, dump_flags);
1101 dump_lattice_value (dump_file, "\tValue: ", arg_val);
1102 fprintf (dump_file, "\n");
1105 if (new_val.lattice_val == VARYING)
1109 non_exec_edge = true;
1112 /* In case there were non-executable edges and the value is a copy
1113 make sure its definition dominates the PHI node. */
1115 && new_val.lattice_val == CONSTANT
1116 && TREE_CODE (new_val.value) == SSA_NAME
1117 && ! SSA_NAME_IS_DEFAULT_DEF (new_val.value)
1118 && ! dominated_by_p (CDI_DOMINATORS, gimple_bb (phi),
1119 gimple_bb (SSA_NAME_DEF_STMT (new_val.value))))
1121 new_val.lattice_val = VARYING;
1122 new_val.value = NULL_TREE;
1126 if (dump_file && (dump_flags & TDF_DETAILS))
1128 dump_lattice_value (dump_file, "\n PHI node value: ", new_val);
1129 fprintf (dump_file, "\n\n");
1132 /* Make the transition to the new value. */
1133 if (set_lattice_value (gimple_phi_result (phi), &new_val))
1135 if (new_val.lattice_val == VARYING)
1136 return SSA_PROP_VARYING;
1138 return SSA_PROP_INTERESTING;
1141 return SSA_PROP_NOT_INTERESTING;
1144 /* Return the constant value for OP or OP otherwise. */
1147 valueize_op (tree op)
1149 if (TREE_CODE (op) == SSA_NAME)
1151 tree tem = get_constant_value (op);
1158 /* Return the constant value for OP, but signal to not follow SSA
1159 edges if the definition may be simulated again. */
1162 valueize_op_1 (tree op)
1164 if (TREE_CODE (op) == SSA_NAME)
1166 /* If the definition may be simulated again we cannot follow
1167 this SSA edge as the SSA propagator does not necessarily
1168 re-visit the use. */
1169 gimple *def_stmt = SSA_NAME_DEF_STMT (op);
1170 if (!gimple_nop_p (def_stmt)
1171 && prop_simulate_again_p (def_stmt))
1173 tree tem = get_constant_value (op);
1180 /* CCP specific front-end to the non-destructive constant folding
1183 Attempt to simplify the RHS of STMT knowing that one or more
1184 operands are constants.
1186 If simplification is possible, return the simplified RHS,
1187 otherwise return the original RHS or NULL_TREE. */
1190 ccp_fold (gimple *stmt)
1192 location_t loc = gimple_location (stmt);
1193 switch (gimple_code (stmt))
1197 /* Handle comparison operators that can appear in GIMPLE form. */
1198 tree op0 = valueize_op (gimple_cond_lhs (stmt));
1199 tree op1 = valueize_op (gimple_cond_rhs (stmt));
1200 enum tree_code code = gimple_cond_code (stmt);
1201 return fold_binary_loc (loc, code, boolean_type_node, op0, op1);
1206 /* Return the constant switch index. */
1207 return valueize_op (gimple_switch_index (as_a <gswitch *> (stmt)));
1212 return gimple_fold_stmt_to_constant_1 (stmt,
1213 valueize_op, valueize_op_1);
1220 /* Apply the operation CODE in type TYPE to the value, mask pair
1221 RVAL and RMASK representing a value of type RTYPE and set
1222 the value, mask pair *VAL and *MASK to the result. */
1225 bit_value_unop_1 (enum tree_code code, tree type,
1226 widest_int *val, widest_int *mask,
1227 tree rtype, const widest_int &rval, const widest_int &rmask)
1238 widest_int temv, temm;
1239 /* Return ~rval + 1. */
1240 bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask);
1241 bit_value_binop_1 (PLUS_EXPR, type, val, mask,
1242 type, temv, temm, type, 1, 0);
1250 /* First extend mask and value according to the original type. */
1251 sgn = TYPE_SIGN (rtype);
1252 *mask = wi::ext (rmask, TYPE_PRECISION (rtype), sgn);
1253 *val = wi::ext (rval, TYPE_PRECISION (rtype), sgn);
1255 /* Then extend mask and value according to the target type. */
1256 sgn = TYPE_SIGN (type);
1257 *mask = wi::ext (*mask, TYPE_PRECISION (type), sgn);
1258 *val = wi::ext (*val, TYPE_PRECISION (type), sgn);
1268 /* Apply the operation CODE in type TYPE to the value, mask pairs
1269 R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE
1270 and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */
1273 bit_value_binop_1 (enum tree_code code, tree type,
1274 widest_int *val, widest_int *mask,
1275 tree r1type, const widest_int &r1val,
1276 const widest_int &r1mask, tree r2type,
1277 const widest_int &r2val, const widest_int &r2mask)
1279 signop sgn = TYPE_SIGN (type);
1280 int width = TYPE_PRECISION (type);
1281 bool swap_p = false;
1283 /* Assume we'll get a constant result. Use an initial non varying
1284 value, we fall back to varying in the end if necessary. */
1290 /* The mask is constant where there is a known not
1291 set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */
1292 *mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask);
1293 *val = r1val & r2val;
1297 /* The mask is constant where there is a known
1298 set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */
1299 *mask = (r1mask | r2mask)
1300 .and_not (r1val.and_not (r1mask) | r2val.and_not (r2mask));
1301 *val = r1val | r2val;
1306 *mask = r1mask | r2mask;
1307 *val = r1val ^ r2val;
1314 widest_int shift = r2val;
1322 if (wi::neg_p (shift))
1325 if (code == RROTATE_EXPR)
1326 code = LROTATE_EXPR;
1328 code = RROTATE_EXPR;
1330 if (code == RROTATE_EXPR)
1332 *mask = wi::rrotate (r1mask, shift, width);
1333 *val = wi::rrotate (r1val, shift, width);
1337 *mask = wi::lrotate (r1mask, shift, width);
1338 *val = wi::lrotate (r1val, shift, width);
1346 /* ??? We can handle partially known shift counts if we know
1347 its sign. That way we can tell that (x << (y | 8)) & 255
1351 widest_int shift = r2val;
1359 if (wi::neg_p (shift))
1362 if (code == RSHIFT_EXPR)
1367 if (code == RSHIFT_EXPR)
1369 *mask = wi::rshift (wi::ext (r1mask, width, sgn), shift, sgn);
1370 *val = wi::rshift (wi::ext (r1val, width, sgn), shift, sgn);
1374 *mask = wi::ext (wi::lshift (r1mask, shift), width, sgn);
1375 *val = wi::ext (wi::lshift (r1val, shift), width, sgn);
1382 case POINTER_PLUS_EXPR:
1384 /* Do the addition with unknown bits set to zero, to give carry-ins of
1385 zero wherever possible. */
1386 widest_int lo = r1val.and_not (r1mask) + r2val.and_not (r2mask);
1387 lo = wi::ext (lo, width, sgn);
1388 /* Do the addition with unknown bits set to one, to give carry-ins of
1389 one wherever possible. */
1390 widest_int hi = (r1val | r1mask) + (r2val | r2mask);
1391 hi = wi::ext (hi, width, sgn);
1392 /* Each bit in the result is known if (a) the corresponding bits in
1393 both inputs are known, and (b) the carry-in to that bit position
1394 is known. We can check condition (b) by seeing if we got the same
1395 result with minimised carries as with maximised carries. */
1396 *mask = r1mask | r2mask | (lo ^ hi);
1397 *mask = wi::ext (*mask, width, sgn);
1398 /* It shouldn't matter whether we choose lo or hi here. */
1405 widest_int temv, temm;
1406 bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm,
1407 r2type, r2val, r2mask);
1408 bit_value_binop_1 (PLUS_EXPR, type, val, mask,
1409 r1type, r1val, r1mask,
1410 r2type, temv, temm);
1416 /* Just track trailing zeros in both operands and transfer
1417 them to the other. */
1418 int r1tz = wi::ctz (r1val | r1mask);
1419 int r2tz = wi::ctz (r2val | r2mask);
1420 if (r1tz + r2tz >= width)
1425 else if (r1tz + r2tz > 0)
1427 *mask = wi::ext (wi::mask <widest_int> (r1tz + r2tz, true),
1437 widest_int m = r1mask | r2mask;
1438 if (r1val.and_not (m) != r2val.and_not (m))
1441 *val = ((code == EQ_EXPR) ? 0 : 1);
1445 /* We know the result of a comparison is always one or zero. */
1455 code = swap_tree_comparison (code);
1462 const widest_int &o1val = swap_p ? r2val : r1val;
1463 const widest_int &o1mask = swap_p ? r2mask : r1mask;
1464 const widest_int &o2val = swap_p ? r1val : r2val;
1465 const widest_int &o2mask = swap_p ? r1mask : r2mask;
1467 /* If the most significant bits are not known we know nothing. */
1468 if (wi::neg_p (o1mask) || wi::neg_p (o2mask))
1471 /* For comparisons the signedness is in the comparison operands. */
1472 sgn = TYPE_SIGN (r1type);
1474 /* If we know the most significant bits we know the values
1475 value ranges by means of treating varying bits as zero
1476 or one. Do a cross comparison of the max/min pairs. */
1477 maxmin = wi::cmp (o1val | o1mask, o2val.and_not (o2mask), sgn);
1478 minmax = wi::cmp (o1val.and_not (o1mask), o2val | o2mask, sgn);
1479 if (maxmin < 0) /* o1 is less than o2. */
1484 else if (minmax > 0) /* o1 is not less or equal to o2. */
1489 else if (maxmin == minmax) /* o1 and o2 are equal. */
1491 /* This probably should never happen as we'd have
1492 folded the thing during fully constant value folding. */
1494 *val = (code == LE_EXPR ? 1 : 0);
1498 /* We know the result of a comparison is always one or zero. */
1509 /* Return the propagation value when applying the operation CODE to
1510 the value RHS yielding type TYPE. */
1512 static ccp_prop_value_t
1513 bit_value_unop (enum tree_code code, tree type, tree rhs)
1515 ccp_prop_value_t rval = get_value_for_expr (rhs, true);
1516 widest_int value, mask;
1517 ccp_prop_value_t val;
1519 if (rval.lattice_val == UNDEFINED)
1522 gcc_assert ((rval.lattice_val == CONSTANT
1523 && TREE_CODE (rval.value) == INTEGER_CST)
1524 || wi::sext (rval.mask, TYPE_PRECISION (TREE_TYPE (rhs))) == -1);
1525 bit_value_unop_1 (code, type, &value, &mask,
1526 TREE_TYPE (rhs), value_to_wide_int (rval), rval.mask);
1527 if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
1529 val.lattice_val = CONSTANT;
1531 /* ??? Delay building trees here. */
1532 val.value = wide_int_to_tree (type, value);
1536 val.lattice_val = VARYING;
1537 val.value = NULL_TREE;
1543 /* Return the propagation value when applying the operation CODE to
1544 the values RHS1 and RHS2 yielding type TYPE. */
1546 static ccp_prop_value_t
1547 bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2)
1549 ccp_prop_value_t r1val = get_value_for_expr (rhs1, true);
1550 ccp_prop_value_t r2val = get_value_for_expr (rhs2, true);
1551 widest_int value, mask;
1552 ccp_prop_value_t val;
1554 if (r1val.lattice_val == UNDEFINED
1555 || r2val.lattice_val == UNDEFINED)
1557 val.lattice_val = VARYING;
1558 val.value = NULL_TREE;
1563 gcc_assert ((r1val.lattice_val == CONSTANT
1564 && TREE_CODE (r1val.value) == INTEGER_CST)
1565 || wi::sext (r1val.mask,
1566 TYPE_PRECISION (TREE_TYPE (rhs1))) == -1);
1567 gcc_assert ((r2val.lattice_val == CONSTANT
1568 && TREE_CODE (r2val.value) == INTEGER_CST)
1569 || wi::sext (r2val.mask,
1570 TYPE_PRECISION (TREE_TYPE (rhs2))) == -1);
1571 bit_value_binop_1 (code, type, &value, &mask,
1572 TREE_TYPE (rhs1), value_to_wide_int (r1val), r1val.mask,
1573 TREE_TYPE (rhs2), value_to_wide_int (r2val), r2val.mask);
1574 if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
1576 val.lattice_val = CONSTANT;
1578 /* ??? Delay building trees here. */
1579 val.value = wide_int_to_tree (type, value);
1583 val.lattice_val = VARYING;
1584 val.value = NULL_TREE;
1590 /* Return the propagation value for __builtin_assume_aligned
1591 and functions with assume_aligned or alloc_aligned attribute.
1592 For __builtin_assume_aligned, ATTR is NULL_TREE,
1593 for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED
1594 is false, for alloc_aligned attribute ATTR is non-NULL and
1595 ALLOC_ALIGNED is true. */
1597 static ccp_prop_value_t
1598 bit_value_assume_aligned (gimple *stmt, tree attr, ccp_prop_value_t ptrval,
1601 tree align, misalign = NULL_TREE, type;
1602 unsigned HOST_WIDE_INT aligni, misaligni = 0;
1603 ccp_prop_value_t alignval;
1604 widest_int value, mask;
1605 ccp_prop_value_t val;
1607 if (attr == NULL_TREE)
1609 tree ptr = gimple_call_arg (stmt, 0);
1610 type = TREE_TYPE (ptr);
1611 ptrval = get_value_for_expr (ptr, true);
1615 tree lhs = gimple_call_lhs (stmt);
1616 type = TREE_TYPE (lhs);
1619 if (ptrval.lattice_val == UNDEFINED)
1621 gcc_assert ((ptrval.lattice_val == CONSTANT
1622 && TREE_CODE (ptrval.value) == INTEGER_CST)
1623 || wi::sext (ptrval.mask, TYPE_PRECISION (type)) == -1);
1624 if (attr == NULL_TREE)
1626 /* Get aligni and misaligni from __builtin_assume_aligned. */
1627 align = gimple_call_arg (stmt, 1);
1628 if (!tree_fits_uhwi_p (align))
1630 aligni = tree_to_uhwi (align);
1631 if (gimple_call_num_args (stmt) > 2)
1633 misalign = gimple_call_arg (stmt, 2);
1634 if (!tree_fits_uhwi_p (misalign))
1636 misaligni = tree_to_uhwi (misalign);
1641 /* Get aligni and misaligni from assume_aligned or
1642 alloc_align attributes. */
1643 if (TREE_VALUE (attr) == NULL_TREE)
1645 attr = TREE_VALUE (attr);
1646 align = TREE_VALUE (attr);
1647 if (!tree_fits_uhwi_p (align))
1649 aligni = tree_to_uhwi (align);
1652 if (aligni == 0 || aligni > gimple_call_num_args (stmt))
1654 align = gimple_call_arg (stmt, aligni - 1);
1655 if (!tree_fits_uhwi_p (align))
1657 aligni = tree_to_uhwi (align);
1659 else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr)))
1661 misalign = TREE_VALUE (TREE_CHAIN (attr));
1662 if (!tree_fits_uhwi_p (misalign))
1664 misaligni = tree_to_uhwi (misalign);
1667 if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni)
1670 align = build_int_cst_type (type, -aligni);
1671 alignval = get_value_for_expr (align, true);
1672 bit_value_binop_1 (BIT_AND_EXPR, type, &value, &mask,
1673 type, value_to_wide_int (ptrval), ptrval.mask,
1674 type, value_to_wide_int (alignval), alignval.mask);
1675 if (wi::sext (mask, TYPE_PRECISION (type)) != -1)
1677 val.lattice_val = CONSTANT;
1679 gcc_assert ((mask.to_uhwi () & (aligni - 1)) == 0);
1680 gcc_assert ((value.to_uhwi () & (aligni - 1)) == 0);
1682 /* ??? Delay building trees here. */
1683 val.value = wide_int_to_tree (type, value);
1687 val.lattice_val = VARYING;
1688 val.value = NULL_TREE;
1694 /* Evaluate statement STMT.
1695 Valid only for assignments, calls, conditionals, and switches. */
1697 static ccp_prop_value_t
1698 evaluate_stmt (gimple *stmt)
1700 ccp_prop_value_t val;
1701 tree simplified = NULL_TREE;
1702 ccp_lattice_t likelyvalue = likely_value (stmt);
1703 bool is_constant = false;
1706 if (dump_file && (dump_flags & TDF_DETAILS))
1708 fprintf (dump_file, "which is likely ");
1709 switch (likelyvalue)
1712 fprintf (dump_file, "CONSTANT");
1715 fprintf (dump_file, "UNDEFINED");
1718 fprintf (dump_file, "VARYING");
1722 fprintf (dump_file, "\n");
1725 /* If the statement is likely to have a CONSTANT result, then try
1726 to fold the statement to determine the constant value. */
1727 /* FIXME. This is the only place that we call ccp_fold.
1728 Since likely_value never returns CONSTANT for calls, we will
1729 not attempt to fold them, including builtins that may profit. */
1730 if (likelyvalue == CONSTANT)
1732 fold_defer_overflow_warnings ();
1733 simplified = ccp_fold (stmt);
1735 && TREE_CODE (simplified) == SSA_NAME
1736 /* We may not use values of something that may be simulated again,
1737 see valueize_op_1. */
1738 && (SSA_NAME_IS_DEFAULT_DEF (simplified)
1739 || ! prop_simulate_again_p (SSA_NAME_DEF_STMT (simplified))))
1741 val = *get_value (simplified);
1742 if (val.lattice_val != VARYING)
1744 fold_undefer_overflow_warnings (true, stmt, 0);
1748 is_constant = simplified && is_gimple_min_invariant (simplified);
1749 fold_undefer_overflow_warnings (is_constant, stmt, 0);
1752 /* The statement produced a constant value. */
1753 val.lattice_val = CONSTANT;
1754 val.value = simplified;
1759 /* If the statement is likely to have a VARYING result, then do not
1760 bother folding the statement. */
1761 else if (likelyvalue == VARYING)
1763 enum gimple_code code = gimple_code (stmt);
1764 if (code == GIMPLE_ASSIGN)
1766 enum tree_code subcode = gimple_assign_rhs_code (stmt);
1768 /* Other cases cannot satisfy is_gimple_min_invariant
1770 if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS)
1771 simplified = gimple_assign_rhs1 (stmt);
1773 else if (code == GIMPLE_SWITCH)
1774 simplified = gimple_switch_index (as_a <gswitch *> (stmt));
1776 /* These cannot satisfy is_gimple_min_invariant without folding. */
1777 gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND);
1778 is_constant = simplified && is_gimple_min_invariant (simplified);
1781 /* The statement produced a constant value. */
1782 val.lattice_val = CONSTANT;
1783 val.value = simplified;
1787 /* If the statement result is likely UNDEFINED, make it so. */
1788 else if (likelyvalue == UNDEFINED)
1790 val.lattice_val = UNDEFINED;
1791 val.value = NULL_TREE;
1796 /* Resort to simplification for bitwise tracking. */
1797 if (flag_tree_bit_ccp
1798 && (likelyvalue == CONSTANT || is_gimple_call (stmt)
1799 || (gimple_assign_single_p (stmt)
1800 && gimple_assign_rhs_code (stmt) == ADDR_EXPR))
1803 enum gimple_code code = gimple_code (stmt);
1804 val.lattice_val = VARYING;
1805 val.value = NULL_TREE;
1807 if (code == GIMPLE_ASSIGN)
1809 enum tree_code subcode = gimple_assign_rhs_code (stmt);
1810 tree rhs1 = gimple_assign_rhs1 (stmt);
1811 tree lhs = gimple_assign_lhs (stmt);
1812 if ((INTEGRAL_TYPE_P (TREE_TYPE (lhs))
1813 || POINTER_TYPE_P (TREE_TYPE (lhs)))
1814 && (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1815 || POINTER_TYPE_P (TREE_TYPE (rhs1))))
1816 switch (get_gimple_rhs_class (subcode))
1818 case GIMPLE_SINGLE_RHS:
1819 val = get_value_for_expr (rhs1, true);
1822 case GIMPLE_UNARY_RHS:
1823 val = bit_value_unop (subcode, TREE_TYPE (lhs), rhs1);
1826 case GIMPLE_BINARY_RHS:
1827 val = bit_value_binop (subcode, TREE_TYPE (lhs), rhs1,
1828 gimple_assign_rhs2 (stmt));
1834 else if (code == GIMPLE_COND)
1836 enum tree_code code = gimple_cond_code (stmt);
1837 tree rhs1 = gimple_cond_lhs (stmt);
1838 tree rhs2 = gimple_cond_rhs (stmt);
1839 if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1))
1840 || POINTER_TYPE_P (TREE_TYPE (rhs1)))
1841 val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2);
1843 else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL))
1845 tree fndecl = gimple_call_fndecl (stmt);
1846 switch (DECL_FUNCTION_CODE (fndecl))
1848 case BUILT_IN_MALLOC:
1849 case BUILT_IN_REALLOC:
1850 case BUILT_IN_CALLOC:
1851 case BUILT_IN_STRDUP:
1852 case BUILT_IN_STRNDUP:
1853 val.lattice_val = CONSTANT;
1854 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
1855 val.mask = ~((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT
1856 / BITS_PER_UNIT - 1);
1859 case BUILT_IN_ALLOCA:
1860 case BUILT_IN_ALLOCA_WITH_ALIGN:
1861 align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA_WITH_ALIGN
1862 ? TREE_INT_CST_LOW (gimple_call_arg (stmt, 1))
1863 : BIGGEST_ALIGNMENT);
1864 val.lattice_val = CONSTANT;
1865 val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0);
1866 val.mask = ~((HOST_WIDE_INT) align / BITS_PER_UNIT - 1);
1869 /* These builtins return their first argument, unmodified. */
1870 case BUILT_IN_MEMCPY:
1871 case BUILT_IN_MEMMOVE:
1872 case BUILT_IN_MEMSET:
1873 case BUILT_IN_STRCPY:
1874 case BUILT_IN_STRNCPY:
1875 case BUILT_IN_MEMCPY_CHK:
1876 case BUILT_IN_MEMMOVE_CHK:
1877 case BUILT_IN_MEMSET_CHK:
1878 case BUILT_IN_STRCPY_CHK:
1879 case BUILT_IN_STRNCPY_CHK:
1880 val = get_value_for_expr (gimple_call_arg (stmt, 0), true);
1883 case BUILT_IN_ASSUME_ALIGNED:
1884 val = bit_value_assume_aligned (stmt, NULL_TREE, val, false);
1887 case BUILT_IN_ALIGNED_ALLOC:
1889 tree align = get_constant_value (gimple_call_arg (stmt, 0));
1891 && tree_fits_uhwi_p (align))
1893 unsigned HOST_WIDE_INT aligni = tree_to_uhwi (align);
1895 /* align must be power-of-two */
1896 && (aligni & (aligni - 1)) == 0)
1898 val.lattice_val = CONSTANT;
1899 val.value = build_int_cst (ptr_type_node, 0);
1909 if (is_gimple_call (stmt) && gimple_call_lhs (stmt))
1911 tree fntype = gimple_call_fntype (stmt);
1914 tree attrs = lookup_attribute ("assume_aligned",
1915 TYPE_ATTRIBUTES (fntype));
1917 val = bit_value_assume_aligned (stmt, attrs, val, false);
1918 attrs = lookup_attribute ("alloc_align",
1919 TYPE_ATTRIBUTES (fntype));
1921 val = bit_value_assume_aligned (stmt, attrs, val, true);
1924 is_constant = (val.lattice_val == CONSTANT);
1927 if (flag_tree_bit_ccp
1928 && ((is_constant && TREE_CODE (val.value) == INTEGER_CST)
1930 && gimple_get_lhs (stmt)
1931 && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME)
1933 tree lhs = gimple_get_lhs (stmt);
1934 wide_int nonzero_bits = get_nonzero_bits (lhs);
1935 if (nonzero_bits != -1)
1939 val.lattice_val = CONSTANT;
1940 val.value = build_zero_cst (TREE_TYPE (lhs));
1941 val.mask = extend_mask (nonzero_bits, TYPE_SIGN (TREE_TYPE (lhs)));
1946 if (wi::bit_and_not (val.value, nonzero_bits) != 0)
1947 val.value = wide_int_to_tree (TREE_TYPE (lhs),
1948 nonzero_bits & val.value);
1949 if (nonzero_bits == 0)
1952 val.mask = val.mask & extend_mask (nonzero_bits,
1953 TYPE_SIGN (TREE_TYPE (lhs)));
1958 /* The statement produced a nonconstant value. */
1961 /* The statement produced a copy. */
1962 if (simplified && TREE_CODE (simplified) == SSA_NAME
1963 && !SSA_NAME_OCCURS_IN_ABNORMAL_PHI (simplified))
1965 val.lattice_val = CONSTANT;
1966 val.value = simplified;
1969 /* The statement is VARYING. */
1972 val.lattice_val = VARYING;
1973 val.value = NULL_TREE;
1981 typedef hash_table<nofree_ptr_hash<gimple> > gimple_htab;
1983 /* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before
1984 each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */
1987 insert_clobber_before_stack_restore (tree saved_val, tree var,
1988 gimple_htab **visited)
1991 gassign *clobber_stmt;
1993 imm_use_iterator iter;
1994 gimple_stmt_iterator i;
1997 FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val)
1998 if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE))
2000 clobber = build_constructor (TREE_TYPE (var),
2002 TREE_THIS_VOLATILE (clobber) = 1;
2003 clobber_stmt = gimple_build_assign (var, clobber);
2005 i = gsi_for_stmt (stmt);
2006 gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT);
2008 else if (gimple_code (stmt) == GIMPLE_PHI)
2011 *visited = new gimple_htab (10);
2013 slot = (*visited)->find_slot (stmt, INSERT);
2018 insert_clobber_before_stack_restore (gimple_phi_result (stmt), var,
2021 else if (gimple_assign_ssa_name_copy_p (stmt))
2022 insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var,
2024 else if (chkp_gimple_call_builtin_p (stmt, BUILT_IN_CHKP_BNDRET))
2027 gcc_assert (is_gimple_debug (stmt));
2030 /* Advance the iterator to the previous non-debug gimple statement in the same
2031 or dominating basic block. */
2034 gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i)
2038 gsi_prev_nondebug (i);
2039 while (gsi_end_p (*i))
2041 dom = get_immediate_dominator (CDI_DOMINATORS, i->bb);
2042 if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun))
2045 *i = gsi_last_bb (dom);
2049 /* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert
2050 a clobber of VAR before each matching BUILT_IN_STACK_RESTORE.
2052 It is possible that BUILT_IN_STACK_SAVE cannot be find in a dominator when a
2053 previous pass (such as DOM) duplicated it along multiple paths to a BB. In
2054 that case the function gives up without inserting the clobbers. */
2057 insert_clobbers_for_var (gimple_stmt_iterator i, tree var)
2061 gimple_htab *visited = NULL;
2063 for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i))
2065 stmt = gsi_stmt (i);
2067 if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE))
2070 saved_val = gimple_call_lhs (stmt);
2071 if (saved_val == NULL_TREE)
2074 insert_clobber_before_stack_restore (saved_val, var, &visited);
2081 /* Detects a __builtin_alloca_with_align with constant size argument. Declares
2082 fixed-size array and returns the address, if found, otherwise returns
2086 fold_builtin_alloca_with_align (gimple *stmt)
2088 unsigned HOST_WIDE_INT size, threshold, n_elem;
2089 tree lhs, arg, block, var, elem_type, array_type;
2092 lhs = gimple_call_lhs (stmt);
2093 if (lhs == NULL_TREE)
2096 /* Detect constant argument. */
2097 arg = get_constant_value (gimple_call_arg (stmt, 0));
2098 if (arg == NULL_TREE
2099 || TREE_CODE (arg) != INTEGER_CST
2100 || !tree_fits_uhwi_p (arg))
2103 size = tree_to_uhwi (arg);
2105 /* Heuristic: don't fold large allocas. */
2106 threshold = (unsigned HOST_WIDE_INT)PARAM_VALUE (PARAM_LARGE_STACK_FRAME);
2107 /* In case the alloca is located at function entry, it has the same lifetime
2108 as a declared array, so we allow a larger size. */
2109 block = gimple_block (stmt);
2110 if (!(cfun->after_inlining
2112 && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL))
2114 if (size > threshold)
2117 /* Declare array. */
2118 elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
2119 n_elem = size * 8 / BITS_PER_UNIT;
2120 array_type = build_array_type_nelts (elem_type, n_elem);
2121 var = create_tmp_var (array_type);
2122 SET_DECL_ALIGN (var, TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)));
2124 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs);
2125 if (pi != NULL && !pi->pt.anything)
2129 singleton_p = pt_solution_singleton_p (&pi->pt, &uid);
2130 gcc_assert (singleton_p);
2131 SET_DECL_PT_UID (var, uid);
2135 /* Fold alloca to the address of the array. */
2136 return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var));
2139 /* Fold the stmt at *GSI with CCP specific information that propagating
2140 and regular folding does not catch. */
2143 ccp_fold_stmt (gimple_stmt_iterator *gsi)
2145 gimple *stmt = gsi_stmt (*gsi);
2147 switch (gimple_code (stmt))
2151 gcond *cond_stmt = as_a <gcond *> (stmt);
2152 ccp_prop_value_t val;
2153 /* Statement evaluation will handle type mismatches in constants
2154 more gracefully than the final propagation. This allows us to
2155 fold more conditionals here. */
2156 val = evaluate_stmt (stmt);
2157 if (val.lattice_val != CONSTANT
2163 fprintf (dump_file, "Folding predicate ");
2164 print_gimple_expr (dump_file, stmt, 0, 0);
2165 fprintf (dump_file, " to ");
2166 print_generic_expr (dump_file, val.value, 0);
2167 fprintf (dump_file, "\n");
2170 if (integer_zerop (val.value))
2171 gimple_cond_make_false (cond_stmt);
2173 gimple_cond_make_true (cond_stmt);
2180 tree lhs = gimple_call_lhs (stmt);
2181 int flags = gimple_call_flags (stmt);
2184 bool changed = false;
2187 /* If the call was folded into a constant make sure it goes
2188 away even if we cannot propagate into all uses because of
2191 && TREE_CODE (lhs) == SSA_NAME
2192 && (val = get_constant_value (lhs))
2193 /* Don't optimize away calls that have side-effects. */
2194 && (flags & (ECF_CONST|ECF_PURE)) != 0
2195 && (flags & ECF_LOOPING_CONST_OR_PURE) == 0)
2197 tree new_rhs = unshare_expr (val);
2199 if (!useless_type_conversion_p (TREE_TYPE (lhs),
2200 TREE_TYPE (new_rhs)))
2201 new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs);
2202 res = update_call_from_tree (gsi, new_rhs);
2207 /* Internal calls provide no argument types, so the extra laxity
2208 for normal calls does not apply. */
2209 if (gimple_call_internal_p (stmt))
2212 /* The heuristic of fold_builtin_alloca_with_align differs before and
2213 after inlining, so we don't require the arg to be changed into a
2214 constant for folding, but just to be constant. */
2215 if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN))
2217 tree new_rhs = fold_builtin_alloca_with_align (stmt);
2220 bool res = update_call_from_tree (gsi, new_rhs);
2221 tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0);
2223 insert_clobbers_for_var (*gsi, var);
2228 /* Propagate into the call arguments. Compared to replace_uses_in
2229 this can use the argument slot types for type verification
2230 instead of the current argument type. We also can safely
2231 drop qualifiers here as we are dealing with constants anyway. */
2232 argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt));
2233 for (i = 0; i < gimple_call_num_args (stmt) && argt;
2234 ++i, argt = TREE_CHAIN (argt))
2236 tree arg = gimple_call_arg (stmt, i);
2237 if (TREE_CODE (arg) == SSA_NAME
2238 && (val = get_constant_value (arg))
2239 && useless_type_conversion_p
2240 (TYPE_MAIN_VARIANT (TREE_VALUE (argt)),
2241 TYPE_MAIN_VARIANT (TREE_TYPE (val))))
2243 gimple_call_set_arg (stmt, i, unshare_expr (val));
2253 tree lhs = gimple_assign_lhs (stmt);
2256 /* If we have a load that turned out to be constant replace it
2257 as we cannot propagate into all uses in all cases. */
2258 if (gimple_assign_single_p (stmt)
2259 && TREE_CODE (lhs) == SSA_NAME
2260 && (val = get_constant_value (lhs)))
2262 tree rhs = unshare_expr (val);
2263 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
2264 rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs);
2265 gimple_assign_set_rhs_from_tree (gsi, rhs);
2277 /* Visit the assignment statement STMT. Set the value of its LHS to the
2278 value computed by the RHS and store LHS in *OUTPUT_P. If STMT
2279 creates virtual definitions, set the value of each new name to that
2280 of the RHS (if we can derive a constant out of the RHS).
2281 Value-returning call statements also perform an assignment, and
2282 are handled here. */
2284 static enum ssa_prop_result
2285 visit_assignment (gimple *stmt, tree *output_p)
2287 ccp_prop_value_t val;
2288 enum ssa_prop_result retval = SSA_PROP_NOT_INTERESTING;
2290 tree lhs = gimple_get_lhs (stmt);
2291 if (TREE_CODE (lhs) == SSA_NAME)
2293 /* Evaluate the statement, which could be
2294 either a GIMPLE_ASSIGN or a GIMPLE_CALL. */
2295 val = evaluate_stmt (stmt);
2297 /* If STMT is an assignment to an SSA_NAME, we only have one
2299 if (set_lattice_value (lhs, &val))
2302 if (val.lattice_val == VARYING)
2303 retval = SSA_PROP_VARYING;
2305 retval = SSA_PROP_INTERESTING;
2313 /* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING
2314 if it can determine which edge will be taken. Otherwise, return
2315 SSA_PROP_VARYING. */
2317 static enum ssa_prop_result
2318 visit_cond_stmt (gimple *stmt, edge *taken_edge_p)
2320 ccp_prop_value_t val;
2323 block = gimple_bb (stmt);
2324 val = evaluate_stmt (stmt);
2325 if (val.lattice_val != CONSTANT
2327 return SSA_PROP_VARYING;
2329 /* Find which edge out of the conditional block will be taken and add it
2330 to the worklist. If no single edge can be determined statically,
2331 return SSA_PROP_VARYING to feed all the outgoing edges to the
2332 propagation engine. */
2333 *taken_edge_p = find_taken_edge (block, val.value);
2335 return SSA_PROP_INTERESTING;
2337 return SSA_PROP_VARYING;
2341 /* Evaluate statement STMT. If the statement produces an output value and
2342 its evaluation changes the lattice value of its output, return
2343 SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the
2346 If STMT is a conditional branch and we can determine its truth
2347 value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying
2348 value, return SSA_PROP_VARYING. */
2350 static enum ssa_prop_result
2351 ccp_visit_stmt (gimple *stmt, edge *taken_edge_p, tree *output_p)
2356 if (dump_file && (dump_flags & TDF_DETAILS))
2358 fprintf (dump_file, "\nVisiting statement:\n");
2359 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2362 switch (gimple_code (stmt))
2365 /* If the statement is an assignment that produces a single
2366 output value, evaluate its RHS to see if the lattice value of
2367 its output has changed. */
2368 return visit_assignment (stmt, output_p);
2371 /* A value-returning call also performs an assignment. */
2372 if (gimple_call_lhs (stmt) != NULL_TREE)
2373 return visit_assignment (stmt, output_p);
2378 /* If STMT is a conditional branch, see if we can determine
2379 which branch will be taken. */
2380 /* FIXME. It appears that we should be able to optimize
2381 computed GOTOs here as well. */
2382 return visit_cond_stmt (stmt, taken_edge_p);
2388 /* Any other kind of statement is not interesting for constant
2389 propagation and, therefore, not worth simulating. */
2390 if (dump_file && (dump_flags & TDF_DETAILS))
2391 fprintf (dump_file, "No interesting values produced. Marked VARYING.\n");
2393 /* Definitions made by statements other than assignments to
2394 SSA_NAMEs represent unknown modifications to their outputs.
2395 Mark them VARYING. */
2396 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS)
2397 set_value_varying (def);
2399 return SSA_PROP_VARYING;
2403 /* Main entry point for SSA Conditional Constant Propagation. If NONZERO_P,
2404 record nonzero bits. */
2407 do_ssa_ccp (bool nonzero_p)
2409 unsigned int todo = 0;
2410 calculate_dominance_info (CDI_DOMINATORS);
2413 ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node);
2414 if (ccp_finalize (nonzero_p))
2416 todo = (TODO_cleanup_cfg | TODO_update_ssa);
2418 /* ccp_finalize does not preserve loop-closed ssa. */
2419 loops_state_clear (LOOP_CLOSED_SSA);
2422 free_dominance_info (CDI_DOMINATORS);
2429 const pass_data pass_data_ccp =
2431 GIMPLE_PASS, /* type */
2433 OPTGROUP_NONE, /* optinfo_flags */
2434 TV_TREE_CCP, /* tv_id */
2435 ( PROP_cfg | PROP_ssa ), /* properties_required */
2436 0, /* properties_provided */
2437 0, /* properties_destroyed */
2438 0, /* todo_flags_start */
2439 TODO_update_address_taken, /* todo_flags_finish */
2442 class pass_ccp : public gimple_opt_pass
2445 pass_ccp (gcc::context *ctxt)
2446 : gimple_opt_pass (pass_data_ccp, ctxt), nonzero_p (false)
2449 /* opt_pass methods: */
2450 opt_pass * clone () { return new pass_ccp (m_ctxt); }
2451 void set_pass_param (unsigned int n, bool param)
2453 gcc_assert (n == 0);
2456 virtual bool gate (function *) { return flag_tree_ccp != 0; }
2457 virtual unsigned int execute (function *) { return do_ssa_ccp (nonzero_p); }
2460 /* Determines whether the pass instance records nonzero bits. */
2462 }; // class pass_ccp
2467 make_pass_ccp (gcc::context *ctxt)
2469 return new pass_ccp (ctxt);
2474 /* Try to optimize out __builtin_stack_restore. Optimize it out
2475 if there is another __builtin_stack_restore in the same basic
2476 block and no calls or ASM_EXPRs are in between, or if this block's
2477 only outgoing edge is to EXIT_BLOCK and there are no calls or
2478 ASM_EXPRs after this __builtin_stack_restore. */
2481 optimize_stack_restore (gimple_stmt_iterator i)
2486 basic_block bb = gsi_bb (i);
2487 gimple *call = gsi_stmt (i);
2489 if (gimple_code (call) != GIMPLE_CALL
2490 || gimple_call_num_args (call) != 1
2491 || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME
2492 || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0))))
2495 for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i))
2497 stmt = gsi_stmt (i);
2498 if (gimple_code (stmt) == GIMPLE_ASM)
2500 if (gimple_code (stmt) != GIMPLE_CALL)
2503 callee = gimple_call_fndecl (stmt);
2505 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2506 /* All regular builtins are ok, just obviously not alloca. */
2507 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA
2508 || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA_WITH_ALIGN)
2511 if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE)
2512 goto second_stack_restore;
2518 /* Allow one successor of the exit block, or zero successors. */
2519 switch (EDGE_COUNT (bb->succs))
2524 if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun))
2530 second_stack_restore:
2532 /* If there's exactly one use, then zap the call to __builtin_stack_save.
2533 If there are multiple uses, then the last one should remove the call.
2534 In any case, whether the call to __builtin_stack_save can be removed
2535 or not is irrelevant to removing the call to __builtin_stack_restore. */
2536 if (has_single_use (gimple_call_arg (call, 0)))
2538 gimple *stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0));
2539 if (is_gimple_call (stack_save))
2541 callee = gimple_call_fndecl (stack_save);
2543 && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL
2544 && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE)
2546 gimple_stmt_iterator stack_save_gsi;
2549 stack_save_gsi = gsi_for_stmt (stack_save);
2550 rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0);
2551 update_call_from_tree (&stack_save_gsi, rhs);
2556 /* No effect, so the statement will be deleted. */
2557 return integer_zero_node;
2560 /* If va_list type is a simple pointer and nothing special is needed,
2561 optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0),
2562 __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple
2563 pointer assignment. */
2566 optimize_stdarg_builtin (gimple *call)
2568 tree callee, lhs, rhs, cfun_va_list;
2569 bool va_list_simple_ptr;
2570 location_t loc = gimple_location (call);
2572 if (gimple_code (call) != GIMPLE_CALL)
2575 callee = gimple_call_fndecl (call);
2577 cfun_va_list = targetm.fn_abi_va_list (callee);
2578 va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list)
2579 && (TREE_TYPE (cfun_va_list) == void_type_node
2580 || TREE_TYPE (cfun_va_list) == char_type_node);
2582 switch (DECL_FUNCTION_CODE (callee))
2584 case BUILT_IN_VA_START:
2585 if (!va_list_simple_ptr
2586 || targetm.expand_builtin_va_start != NULL
2587 || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG))
2590 if (gimple_call_num_args (call) != 2)
2593 lhs = gimple_call_arg (call, 0);
2594 if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2595 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2596 != TYPE_MAIN_VARIANT (cfun_va_list))
2599 lhs = build_fold_indirect_ref_loc (loc, lhs);
2600 rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG),
2601 1, integer_zero_node);
2602 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
2603 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2605 case BUILT_IN_VA_COPY:
2606 if (!va_list_simple_ptr)
2609 if (gimple_call_num_args (call) != 2)
2612 lhs = gimple_call_arg (call, 0);
2613 if (!POINTER_TYPE_P (TREE_TYPE (lhs))
2614 || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs)))
2615 != TYPE_MAIN_VARIANT (cfun_va_list))
2618 lhs = build_fold_indirect_ref_loc (loc, lhs);
2619 rhs = gimple_call_arg (call, 1);
2620 if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs))
2621 != TYPE_MAIN_VARIANT (cfun_va_list))
2624 rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs);
2625 return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
2627 case BUILT_IN_VA_END:
2628 /* No effect, so the statement will be deleted. */
2629 return integer_zero_node;
2636 /* Attemp to make the block of __builtin_unreachable I unreachable by changing
2637 the incoming jumps. Return true if at least one jump was changed. */
2640 optimize_unreachable (gimple_stmt_iterator i)
2642 basic_block bb = gsi_bb (i);
2643 gimple_stmt_iterator gsi;
2649 if (flag_sanitize & SANITIZE_UNREACHABLE)
2652 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
2654 stmt = gsi_stmt (gsi);
2656 if (is_gimple_debug (stmt))
2659 if (glabel *label_stmt = dyn_cast <glabel *> (stmt))
2661 /* Verify we do not need to preserve the label. */
2662 if (FORCED_LABEL (gimple_label_label (label_stmt)))
2668 /* Only handle the case that __builtin_unreachable is the first statement
2669 in the block. We rely on DCE to remove stmts without side-effects
2670 before __builtin_unreachable. */
2671 if (gsi_stmt (gsi) != gsi_stmt (i))
2676 FOR_EACH_EDGE (e, ei, bb->preds)
2678 gsi = gsi_last_bb (e->src);
2679 if (gsi_end_p (gsi))
2682 stmt = gsi_stmt (gsi);
2683 if (gcond *cond_stmt = dyn_cast <gcond *> (stmt))
2685 if (e->flags & EDGE_TRUE_VALUE)
2686 gimple_cond_make_false (cond_stmt);
2687 else if (e->flags & EDGE_FALSE_VALUE)
2688 gimple_cond_make_true (cond_stmt);
2691 update_stmt (cond_stmt);
2695 /* Todo: handle other cases, f.i. switch statement. */
2705 /* A simple pass that attempts to fold all builtin functions. This pass
2706 is run after we've propagated as many constants as we can. */
2710 const pass_data pass_data_fold_builtins =
2712 GIMPLE_PASS, /* type */
2714 OPTGROUP_NONE, /* optinfo_flags */
2715 TV_NONE, /* tv_id */
2716 ( PROP_cfg | PROP_ssa ), /* properties_required */
2717 0, /* properties_provided */
2718 0, /* properties_destroyed */
2719 0, /* todo_flags_start */
2720 TODO_update_ssa, /* todo_flags_finish */
2723 class pass_fold_builtins : public gimple_opt_pass
2726 pass_fold_builtins (gcc::context *ctxt)
2727 : gimple_opt_pass (pass_data_fold_builtins, ctxt)
2730 /* opt_pass methods: */
2731 opt_pass * clone () { return new pass_fold_builtins (m_ctxt); }
2732 virtual unsigned int execute (function *);
2734 }; // class pass_fold_builtins
2737 pass_fold_builtins::execute (function *fun)
2739 bool cfg_changed = false;
2741 unsigned int todoflags = 0;
2743 FOR_EACH_BB_FN (bb, fun)
2745 gimple_stmt_iterator i;
2746 for (i = gsi_start_bb (bb); !gsi_end_p (i); )
2748 gimple *stmt, *old_stmt;
2750 enum built_in_function fcode;
2752 stmt = gsi_stmt (i);
2754 if (gimple_code (stmt) != GIMPLE_CALL)
2756 /* Remove all *ssaname_N ={v} {CLOBBER}; stmts,
2757 after the last GIMPLE DSE they aren't needed and might
2758 unnecessarily keep the SSA_NAMEs live. */
2759 if (gimple_clobber_p (stmt))
2761 tree lhs = gimple_assign_lhs (stmt);
2762 if (TREE_CODE (lhs) == MEM_REF
2763 && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME)
2765 unlink_stmt_vdef (stmt);
2766 gsi_remove (&i, true);
2767 release_defs (stmt);
2775 callee = gimple_call_fndecl (stmt);
2776 if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL)
2782 fcode = DECL_FUNCTION_CODE (callee);
2787 tree result = NULL_TREE;
2788 switch (DECL_FUNCTION_CODE (callee))
2790 case BUILT_IN_CONSTANT_P:
2791 /* Resolve __builtin_constant_p. If it hasn't been
2792 folded to integer_one_node by now, it's fairly
2793 certain that the value simply isn't constant. */
2794 result = integer_zero_node;
2797 case BUILT_IN_ASSUME_ALIGNED:
2798 /* Remove __builtin_assume_aligned. */
2799 result = gimple_call_arg (stmt, 0);
2802 case BUILT_IN_STACK_RESTORE:
2803 result = optimize_stack_restore (i);
2809 case BUILT_IN_UNREACHABLE:
2810 if (optimize_unreachable (i))
2814 case BUILT_IN_VA_START:
2815 case BUILT_IN_VA_END:
2816 case BUILT_IN_VA_COPY:
2817 /* These shouldn't be folded before pass_stdarg. */
2818 result = optimize_stdarg_builtin (stmt);
2832 if (!update_call_from_tree (&i, result))
2833 gimplify_and_update_call_from_tree (&i, result);
2836 todoflags |= TODO_update_address_taken;
2838 if (dump_file && (dump_flags & TDF_DETAILS))
2840 fprintf (dump_file, "Simplified\n ");
2841 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2845 stmt = gsi_stmt (i);
2848 if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt)
2849 && gimple_purge_dead_eh_edges (bb))
2852 if (dump_file && (dump_flags & TDF_DETAILS))
2854 fprintf (dump_file, "to\n ");
2855 print_gimple_stmt (dump_file, stmt, 0, dump_flags);
2856 fprintf (dump_file, "\n");
2859 /* Retry the same statement if it changed into another
2860 builtin, there might be new opportunities now. */
2861 if (gimple_code (stmt) != GIMPLE_CALL)
2866 callee = gimple_call_fndecl (stmt);
2868 || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL
2869 || DECL_FUNCTION_CODE (callee) == fcode)
2874 /* Delete unreachable blocks. */
2876 todoflags |= TODO_cleanup_cfg;
2884 make_pass_fold_builtins (gcc::context *ctxt)
2886 return new pass_fold_builtins (ctxt);