diff options
author | Ben Cheng <bccheng@google.com> | 2014-03-25 22:37:19 -0700 |
---|---|---|
committer | Ben Cheng <bccheng@google.com> | 2014-03-25 22:37:19 -0700 |
commit | 1bc5aee63eb72b341f506ad058502cd0361f0d10 (patch) | |
tree | c607e8252f3405424ff15bc2d00aa38dadbb2518 /gcc-4.9/gcc/tree-ssa-ccp.c | |
parent | 283a0bf58fcf333c58a2a92c3ebbc41fb9eb1fdb (diff) | |
download | toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.tar.gz toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.tar.bz2 toolchain_gcc-1bc5aee63eb72b341f506ad058502cd0361f0d10.zip |
Initial checkin of GCC 4.9.0 from trunk (r208799).
Change-Id: I48a3c08bb98542aa215912a75f03c0890e497dba
Diffstat (limited to 'gcc-4.9/gcc/tree-ssa-ccp.c')
-rw-r--r-- | gcc-4.9/gcc/tree-ssa-ccp.c | 2751 |
1 files changed, 2751 insertions, 0 deletions
diff --git a/gcc-4.9/gcc/tree-ssa-ccp.c b/gcc-4.9/gcc/tree-ssa-ccp.c new file mode 100644 index 000000000..eeefeaf07 --- /dev/null +++ b/gcc-4.9/gcc/tree-ssa-ccp.c @@ -0,0 +1,2751 @@ +/* Conditional constant propagation pass for the GNU compiler. + Copyright (C) 2000-2014 Free Software Foundation, Inc. + Adapted from original RTL SSA-CCP by Daniel Berlin <dberlin@dberlin.org> + Adapted to GIMPLE trees by Diego Novillo <dnovillo@redhat.com> + +This file is part of GCC. + +GCC is free software; you can redistribute it and/or modify it +under the terms of the GNU General Public License as published by the +Free Software Foundation; either version 3, or (at your option) any +later version. + +GCC is distributed in the hope that it will be useful, but WITHOUT +ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or +FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License +for more details. + +You should have received a copy of the GNU General Public License +along with GCC; see the file COPYING3. If not see +<http://www.gnu.org/licenses/>. */ + +/* Conditional constant propagation (CCP) is based on the SSA + propagation engine (tree-ssa-propagate.c). Constant assignments of + the form VAR = CST are propagated from the assignments into uses of + VAR, which in turn may generate new constants. The simulation uses + a four level lattice to keep track of constant values associated + with SSA names. Given an SSA name V_i, it may take one of the + following values: + + UNINITIALIZED -> the initial state of the value. This value + is replaced with a correct initial value + the first time the value is used, so the + rest of the pass does not need to care about + it. Using this value simplifies initialization + of the pass, and prevents us from needlessly + scanning statements that are never reached. + + UNDEFINED -> V_i is a local variable whose definition + has not been processed yet. Therefore we + don't yet know if its value is a constant + or not. + + CONSTANT -> V_i has been found to hold a constant + value C. + + VARYING -> V_i cannot take a constant value, or if it + does, it is not possible to determine it + at compile time. + + The core of SSA-CCP is in ccp_visit_stmt and ccp_visit_phi_node: + + 1- In ccp_visit_stmt, we are interested in assignments whose RHS + evaluates into a constant and conditional jumps whose predicate + evaluates into a boolean true or false. When an assignment of + the form V_i = CONST is found, V_i's lattice value is set to + CONSTANT and CONST is associated with it. This causes the + propagation engine to add all the SSA edges coming out the + assignment into the worklists, so that statements that use V_i + can be visited. + + If the statement is a conditional with a constant predicate, we + mark the outgoing edges as executable or not executable + depending on the predicate's value. This is then used when + visiting PHI nodes to know when a PHI argument can be ignored. + + + 2- In ccp_visit_phi_node, if all the PHI arguments evaluate to the + same constant C, then the LHS of the PHI is set to C. This + evaluation is known as the "meet operation". Since one of the + goals of this evaluation is to optimistically return constant + values as often as possible, it uses two main short cuts: + + - If an argument is flowing in through a non-executable edge, it + is ignored. This is useful in cases like this: + + if (PRED) + a_9 = 3; + else + a_10 = 100; + a_11 = PHI (a_9, a_10) + + If PRED is known to always evaluate to false, then we can + assume that a_11 will always take its value from a_10, meaning + that instead of consider it VARYING (a_9 and a_10 have + different values), we can consider it CONSTANT 100. + + - If an argument has an UNDEFINED value, then it does not affect + the outcome of the meet operation. If a variable V_i has an + UNDEFINED value, it means that either its defining statement + hasn't been visited yet or V_i has no defining statement, in + which case the original symbol 'V' is being used + uninitialized. Since 'V' is a local variable, the compiler + may assume any initial value for it. + + + After propagation, every variable V_i that ends up with a lattice + value of CONSTANT will have the associated constant value in the + array CONST_VAL[i].VALUE. That is fed into substitute_and_fold for + final substitution and folding. + + References: + + Constant propagation with conditional branches, + Wegman and Zadeck, ACM TOPLAS 13(2):181-210. + + Building an Optimizing Compiler, + Robert Morgan, Butterworth-Heinemann, 1998, Section 8.9. + + Advanced Compiler Design and Implementation, + Steven Muchnick, Morgan Kaufmann, 1997, Section 12.6 */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "stor-layout.h" +#include "flags.h" +#include "tm_p.h" +#include "basic-block.h" +#include "function.h" +#include "gimple-pretty-print.h" +#include "hash-table.h" +#include "tree-ssa-alias.h" +#include "internal-fn.h" +#include "gimple-fold.h" +#include "tree-eh.h" +#include "gimple-expr.h" +#include "is-a.h" +#include "gimple.h" +#include "gimplify.h" +#include "gimple-iterator.h" +#include "gimple-ssa.h" +#include "tree-cfg.h" +#include "tree-phinodes.h" +#include "ssa-iterators.h" +#include "stringpool.h" +#include "tree-ssanames.h" +#include "tree-pass.h" +#include "tree-ssa-propagate.h" +#include "value-prof.h" +#include "langhooks.h" +#include "target.h" +#include "diagnostic-core.h" +#include "dbgcnt.h" +#include "params.h" + + +/* Possible lattice values. */ +typedef enum +{ + UNINITIALIZED, + UNDEFINED, + CONSTANT, + VARYING +} ccp_lattice_t; + +struct prop_value_d { + /* Lattice value. */ + ccp_lattice_t lattice_val; + + /* Propagated value. */ + tree value; + + /* Mask that applies to the propagated value during CCP. For + X with a CONSTANT lattice value X & ~mask == value & ~mask. */ + double_int mask; +}; + +typedef struct prop_value_d prop_value_t; + +/* Array of propagated constant values. After propagation, + CONST_VAL[I].VALUE holds the constant value for SSA_NAME(I). If + the constant is held in an SSA name representing a memory store + (i.e., a VDEF), CONST_VAL[I].MEM_REF will contain the actual + memory reference used to store (i.e., the LHS of the assignment + doing the store). */ +static prop_value_t *const_val; +static unsigned n_const_val; + +static void canonicalize_value (prop_value_t *); +static bool ccp_fold_stmt (gimple_stmt_iterator *); + +/* Dump constant propagation value VAL to file OUTF prefixed by PREFIX. */ + +static void +dump_lattice_value (FILE *outf, const char *prefix, prop_value_t val) +{ + switch (val.lattice_val) + { + case UNINITIALIZED: + fprintf (outf, "%sUNINITIALIZED", prefix); + break; + case UNDEFINED: + fprintf (outf, "%sUNDEFINED", prefix); + break; + case VARYING: + fprintf (outf, "%sVARYING", prefix); + break; + case CONSTANT: + if (TREE_CODE (val.value) != INTEGER_CST + || val.mask.is_zero ()) + { + fprintf (outf, "%sCONSTANT ", prefix); + print_generic_expr (outf, val.value, dump_flags); + } + else + { + double_int cval = tree_to_double_int (val.value).and_not (val.mask); + fprintf (outf, "%sCONSTANT " HOST_WIDE_INT_PRINT_DOUBLE_HEX, + prefix, cval.high, cval.low); + fprintf (outf, " (" HOST_WIDE_INT_PRINT_DOUBLE_HEX ")", + val.mask.high, val.mask.low); + } + break; + default: + gcc_unreachable (); + } +} + + +/* Print lattice value VAL to stderr. */ + +void debug_lattice_value (prop_value_t val); + +DEBUG_FUNCTION void +debug_lattice_value (prop_value_t val) +{ + dump_lattice_value (stderr, "", val); + fprintf (stderr, "\n"); +} + + +/* Compute a default value for variable VAR and store it in the + CONST_VAL array. The following rules are used to get default + values: + + 1- Global and static variables that are declared constant are + considered CONSTANT. + + 2- Any other value is considered UNDEFINED. This is useful when + considering PHI nodes. PHI arguments that are undefined do not + change the constant value of the PHI node, which allows for more + constants to be propagated. + + 3- Variables defined by statements other than assignments and PHI + nodes are considered VARYING. + + 4- Initial values of variables that are not GIMPLE registers are + considered VARYING. */ + +static prop_value_t +get_default_value (tree var) +{ + prop_value_t val = { UNINITIALIZED, NULL_TREE, { 0, 0 } }; + gimple stmt; + + stmt = SSA_NAME_DEF_STMT (var); + + if (gimple_nop_p (stmt)) + { + /* Variables defined by an empty statement are those used + before being initialized. If VAR is a local variable, we + can assume initially that it is UNDEFINED, otherwise we must + consider it VARYING. */ + if (!virtual_operand_p (var) + && TREE_CODE (SSA_NAME_VAR (var)) == VAR_DECL) + val.lattice_val = UNDEFINED; + else + { + val.lattice_val = VARYING; + val.mask = double_int_minus_one; + if (flag_tree_bit_ccp) + { + double_int nonzero_bits = get_nonzero_bits (var); + double_int mask + = double_int::mask (TYPE_PRECISION (TREE_TYPE (var))); + if (nonzero_bits != double_int_minus_one && nonzero_bits != mask) + { + val.lattice_val = CONSTANT; + val.value = build_zero_cst (TREE_TYPE (var)); + /* CCP wants the bits above precision set. */ + val.mask = nonzero_bits | ~mask; + } + } + } + } + else if (is_gimple_assign (stmt)) + { + tree cst; + if (gimple_assign_single_p (stmt) + && DECL_P (gimple_assign_rhs1 (stmt)) + && (cst = get_symbol_constant_value (gimple_assign_rhs1 (stmt)))) + { + val.lattice_val = CONSTANT; + val.value = cst; + } + else + { + /* Any other variable defined by an assignment is considered + UNDEFINED. */ + val.lattice_val = UNDEFINED; + } + } + else if ((is_gimple_call (stmt) + && gimple_call_lhs (stmt) != NULL_TREE) + || gimple_code (stmt) == GIMPLE_PHI) + { + /* A variable defined by a call or a PHI node is considered + UNDEFINED. */ + val.lattice_val = UNDEFINED; + } + else + { + /* Otherwise, VAR will never take on a constant value. */ + val.lattice_val = VARYING; + val.mask = double_int_minus_one; + } + + return val; +} + + +/* Get the constant value associated with variable VAR. */ + +static inline prop_value_t * +get_value (tree var) +{ + prop_value_t *val; + + if (const_val == NULL + || SSA_NAME_VERSION (var) >= n_const_val) + return NULL; + + val = &const_val[SSA_NAME_VERSION (var)]; + if (val->lattice_val == UNINITIALIZED) + *val = get_default_value (var); + + canonicalize_value (val); + + return val; +} + +/* Return the constant tree value associated with VAR. */ + +static inline tree +get_constant_value (tree var) +{ + prop_value_t *val; + if (TREE_CODE (var) != SSA_NAME) + { + if (is_gimple_min_invariant (var)) + return var; + return NULL_TREE; + } + val = get_value (var); + if (val + && val->lattice_val == CONSTANT + && (TREE_CODE (val->value) != INTEGER_CST + || val->mask.is_zero ())) + return val->value; + return NULL_TREE; +} + +/* Sets the value associated with VAR to VARYING. */ + +static inline void +set_value_varying (tree var) +{ + prop_value_t *val = &const_val[SSA_NAME_VERSION (var)]; + + val->lattice_val = VARYING; + val->value = NULL_TREE; + val->mask = double_int_minus_one; +} + +/* For float types, modify the value of VAL to make ccp work correctly + for non-standard values (-0, NaN): + + If HONOR_SIGNED_ZEROS is false, and VAL = -0, we canonicalize it to 0. + If HONOR_NANS is false, and VAL is NaN, we canonicalize it to UNDEFINED. + This is to fix the following problem (see PR 29921): Suppose we have + + x = 0.0 * y + + and we set value of y to NaN. This causes value of x to be set to NaN. + When we later determine that y is in fact VARYING, fold uses the fact + that HONOR_NANS is false, and we try to change the value of x to 0, + causing an ICE. With HONOR_NANS being false, the real appearance of + NaN would cause undefined behavior, though, so claiming that y (and x) + are UNDEFINED initially is correct. + + For other constants, make sure to drop TREE_OVERFLOW. */ + +static void +canonicalize_value (prop_value_t *val) +{ + enum machine_mode mode; + tree type; + REAL_VALUE_TYPE d; + + if (val->lattice_val != CONSTANT) + return; + + if (TREE_OVERFLOW_P (val->value)) + val->value = drop_tree_overflow (val->value); + + if (TREE_CODE (val->value) != REAL_CST) + return; + + d = TREE_REAL_CST (val->value); + type = TREE_TYPE (val->value); + mode = TYPE_MODE (type); + + if (!HONOR_SIGNED_ZEROS (mode) + && REAL_VALUE_MINUS_ZERO (d)) + { + val->value = build_real (type, dconst0); + return; + } + + if (!HONOR_NANS (mode) + && REAL_VALUE_ISNAN (d)) + { + val->lattice_val = UNDEFINED; + val->value = NULL; + return; + } +} + +/* Return whether the lattice transition is valid. */ + +static bool +valid_lattice_transition (prop_value_t old_val, prop_value_t new_val) +{ + /* Lattice transitions must always be monotonically increasing in + value. */ + if (old_val.lattice_val < new_val.lattice_val) + return true; + + if (old_val.lattice_val != new_val.lattice_val) + return false; + + if (!old_val.value && !new_val.value) + return true; + + /* Now both lattice values are CONSTANT. */ + + /* Allow transitioning from PHI <&x, not executable> == &x + to PHI <&x, &y> == common alignment. */ + if (TREE_CODE (old_val.value) != INTEGER_CST + && TREE_CODE (new_val.value) == INTEGER_CST) + return true; + + /* Bit-lattices have to agree in the still valid bits. */ + if (TREE_CODE (old_val.value) == INTEGER_CST + && TREE_CODE (new_val.value) == INTEGER_CST) + return tree_to_double_int (old_val.value).and_not (new_val.mask) + == tree_to_double_int (new_val.value).and_not (new_val.mask); + + /* Otherwise constant values have to agree. */ + return operand_equal_p (old_val.value, new_val.value, 0); +} + +/* Set the value for variable VAR to NEW_VAL. Return true if the new + value is different from VAR's previous value. */ + +static bool +set_lattice_value (tree var, prop_value_t new_val) +{ + /* We can deal with old UNINITIALIZED values just fine here. */ + prop_value_t *old_val = &const_val[SSA_NAME_VERSION (var)]; + + canonicalize_value (&new_val); + + /* We have to be careful to not go up the bitwise lattice + represented by the mask. + ??? This doesn't seem to be the best place to enforce this. */ + if (new_val.lattice_val == CONSTANT + && old_val->lattice_val == CONSTANT + && TREE_CODE (new_val.value) == INTEGER_CST + && TREE_CODE (old_val->value) == INTEGER_CST) + { + double_int diff; + diff = tree_to_double_int (new_val.value) + ^ tree_to_double_int (old_val->value); + new_val.mask = new_val.mask | old_val->mask | diff; + } + + gcc_assert (valid_lattice_transition (*old_val, new_val)); + + /* If *OLD_VAL and NEW_VAL are the same, return false to inform the + caller that this was a non-transition. */ + if (old_val->lattice_val != new_val.lattice_val + || (new_val.lattice_val == CONSTANT + && TREE_CODE (new_val.value) == INTEGER_CST + && (TREE_CODE (old_val->value) != INTEGER_CST + || new_val.mask != old_val->mask))) + { + /* ??? We would like to delay creation of INTEGER_CSTs from + partially constants here. */ + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + dump_lattice_value (dump_file, "Lattice value changed to ", new_val); + fprintf (dump_file, ". Adding SSA edges to worklist.\n"); + } + + *old_val = new_val; + + gcc_assert (new_val.lattice_val != UNINITIALIZED); + return true; + } + + return false; +} + +static prop_value_t get_value_for_expr (tree, bool); +static prop_value_t bit_value_binop (enum tree_code, tree, tree, tree); +static void bit_value_binop_1 (enum tree_code, tree, double_int *, double_int *, + tree, double_int, double_int, + tree, double_int, double_int); + +/* Return a double_int that can be used for bitwise simplifications + from VAL. */ + +static double_int +value_to_double_int (prop_value_t val) +{ + if (val.value + && TREE_CODE (val.value) == INTEGER_CST) + return tree_to_double_int (val.value); + else + return double_int_zero; +} + +/* Return the value for the address expression EXPR based on alignment + information. */ + +static prop_value_t +get_value_from_alignment (tree expr) +{ + tree type = TREE_TYPE (expr); + prop_value_t val; + unsigned HOST_WIDE_INT bitpos; + unsigned int align; + + gcc_assert (TREE_CODE (expr) == ADDR_EXPR); + + get_pointer_alignment_1 (expr, &align, &bitpos); + val.mask = (POINTER_TYPE_P (type) || TYPE_UNSIGNED (type) + ? double_int::mask (TYPE_PRECISION (type)) + : double_int_minus_one) + .and_not (double_int::from_uhwi (align / BITS_PER_UNIT - 1)); + val.lattice_val = val.mask.is_minus_one () ? VARYING : CONSTANT; + if (val.lattice_val == CONSTANT) + val.value + = double_int_to_tree (type, + double_int::from_uhwi (bitpos / BITS_PER_UNIT)); + else + val.value = NULL_TREE; + + return val; +} + +/* Return the value for the tree operand EXPR. If FOR_BITS_P is true + return constant bits extracted from alignment information for + invariant addresses. */ + +static prop_value_t +get_value_for_expr (tree expr, bool for_bits_p) +{ + prop_value_t val; + + if (TREE_CODE (expr) == SSA_NAME) + { + val = *get_value (expr); + if (for_bits_p + && val.lattice_val == CONSTANT + && TREE_CODE (val.value) == ADDR_EXPR) + val = get_value_from_alignment (val.value); + } + else if (is_gimple_min_invariant (expr) + && (!for_bits_p || TREE_CODE (expr) != ADDR_EXPR)) + { + val.lattice_val = CONSTANT; + val.value = expr; + val.mask = double_int_zero; + canonicalize_value (&val); + } + else if (TREE_CODE (expr) == ADDR_EXPR) + val = get_value_from_alignment (expr); + else + { + val.lattice_val = VARYING; + val.mask = double_int_minus_one; + val.value = NULL_TREE; + } + return val; +} + +/* Return the likely CCP lattice value for STMT. + + If STMT has no operands, then return CONSTANT. + + Else if undefinedness of operands of STMT cause its value to be + undefined, then return UNDEFINED. + + Else if any operands of STMT are constants, then return CONSTANT. + + Else return VARYING. */ + +static ccp_lattice_t +likely_value (gimple stmt) +{ + bool has_constant_operand, has_undefined_operand, all_undefined_operands; + tree use; + ssa_op_iter iter; + unsigned i; + + enum gimple_code code = gimple_code (stmt); + + /* This function appears to be called only for assignments, calls, + conditionals, and switches, due to the logic in visit_stmt. */ + gcc_assert (code == GIMPLE_ASSIGN + || code == GIMPLE_CALL + || code == GIMPLE_COND + || code == GIMPLE_SWITCH); + + /* If the statement has volatile operands, it won't fold to a + constant value. */ + if (gimple_has_volatile_ops (stmt)) + return VARYING; + + /* Arrive here for more complex cases. */ + has_constant_operand = false; + has_undefined_operand = false; + all_undefined_operands = true; + FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE) + { + prop_value_t *val = get_value (use); + + if (val->lattice_val == UNDEFINED) + has_undefined_operand = true; + else + all_undefined_operands = false; + + if (val->lattice_val == CONSTANT) + has_constant_operand = true; + } + + /* There may be constants in regular rhs operands. For calls we + have to ignore lhs, fndecl and static chain, otherwise only + the lhs. */ + for (i = (is_gimple_call (stmt) ? 2 : 0) + gimple_has_lhs (stmt); + i < gimple_num_ops (stmt); ++i) + { + tree op = gimple_op (stmt, i); + if (!op || TREE_CODE (op) == SSA_NAME) + continue; + if (is_gimple_min_invariant (op)) + has_constant_operand = true; + } + + if (has_constant_operand) + all_undefined_operands = false; + + if (has_undefined_operand + && code == GIMPLE_CALL + && gimple_call_internal_p (stmt)) + switch (gimple_call_internal_fn (stmt)) + { + /* These 3 builtins use the first argument just as a magic + way how to find out a decl uid. */ + case IFN_GOMP_SIMD_LANE: + case IFN_GOMP_SIMD_VF: + case IFN_GOMP_SIMD_LAST_LANE: + has_undefined_operand = false; + break; + default: + break; + } + + /* If the operation combines operands like COMPLEX_EXPR make sure to + not mark the result UNDEFINED if only one part of the result is + undefined. */ + if (has_undefined_operand && all_undefined_operands) + return UNDEFINED; + else if (code == GIMPLE_ASSIGN && has_undefined_operand) + { + switch (gimple_assign_rhs_code (stmt)) + { + /* Unary operators are handled with all_undefined_operands. */ + case PLUS_EXPR: + case MINUS_EXPR: + case POINTER_PLUS_EXPR: + /* Not MIN_EXPR, MAX_EXPR. One VARYING operand may be selected. + Not bitwise operators, one VARYING operand may specify the + result completely. Not logical operators for the same reason. + Not COMPLEX_EXPR as one VARYING operand makes the result partly + not UNDEFINED. Not *DIV_EXPR, comparisons and shifts because + the undefined operand may be promoted. */ + return UNDEFINED; + + case ADDR_EXPR: + /* If any part of an address is UNDEFINED, like the index + of an ARRAY_EXPR, then treat the result as UNDEFINED. */ + return UNDEFINED; + + default: + ; + } + } + /* If there was an UNDEFINED operand but the result may be not UNDEFINED + fall back to CONSTANT. During iteration UNDEFINED may still drop + to CONSTANT. */ + if (has_undefined_operand) + return CONSTANT; + + /* We do not consider virtual operands here -- load from read-only + memory may have only VARYING virtual operands, but still be + constant. */ + if (has_constant_operand + || gimple_references_memory_p (stmt)) + return CONSTANT; + + return VARYING; +} + +/* Returns true if STMT cannot be constant. */ + +static bool +surely_varying_stmt_p (gimple stmt) +{ + /* If the statement has operands that we cannot handle, it cannot be + constant. */ + if (gimple_has_volatile_ops (stmt)) + return true; + + /* If it is a call and does not return a value or is not a + builtin and not an indirect call or a call to function with + assume_aligned/alloc_align attribute, it is varying. */ + if (is_gimple_call (stmt)) + { + tree fndecl, fntype = gimple_call_fntype (stmt); + if (!gimple_call_lhs (stmt) + || ((fndecl = gimple_call_fndecl (stmt)) != NULL_TREE + && !DECL_BUILT_IN (fndecl) + && !lookup_attribute ("assume_aligned", + TYPE_ATTRIBUTES (fntype)) + && !lookup_attribute ("alloc_align", + TYPE_ATTRIBUTES (fntype)))) + return true; + } + + /* Any other store operation is not interesting. */ + else if (gimple_vdef (stmt)) + return true; + + /* Anything other than assignments and conditional jumps are not + interesting for CCP. */ + if (gimple_code (stmt) != GIMPLE_ASSIGN + && gimple_code (stmt) != GIMPLE_COND + && gimple_code (stmt) != GIMPLE_SWITCH + && gimple_code (stmt) != GIMPLE_CALL) + return true; + + return false; +} + +/* Initialize local data structures for CCP. */ + +static void +ccp_initialize (void) +{ + basic_block bb; + + n_const_val = num_ssa_names; + const_val = XCNEWVEC (prop_value_t, n_const_val); + + /* Initialize simulation flags for PHI nodes and statements. */ + FOR_EACH_BB_FN (bb, cfun) + { + gimple_stmt_iterator i; + + for (i = gsi_start_bb (bb); !gsi_end_p (i); gsi_next (&i)) + { + gimple stmt = gsi_stmt (i); + bool is_varying; + + /* If the statement is a control insn, then we do not + want to avoid simulating the statement once. Failure + to do so means that those edges will never get added. */ + if (stmt_ends_bb_p (stmt)) + is_varying = false; + else + is_varying = surely_varying_stmt_p (stmt); + + if (is_varying) + { + tree def; + ssa_op_iter iter; + + /* If the statement will not produce a constant, mark + all its outputs VARYING. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) + set_value_varying (def); + } + prop_set_simulate_again (stmt, !is_varying); + } + } + + /* Now process PHI nodes. We never clear the simulate_again flag on + phi nodes, since we do not know which edges are executable yet, + except for phi nodes for virtual operands when we do not do store ccp. */ + FOR_EACH_BB_FN (bb, cfun) + { + gimple_stmt_iterator i; + + for (i = gsi_start_phis (bb); !gsi_end_p (i); gsi_next (&i)) + { + gimple phi = gsi_stmt (i); + + if (virtual_operand_p (gimple_phi_result (phi))) + prop_set_simulate_again (phi, false); + else + prop_set_simulate_again (phi, true); + } + } +} + +/* Debug count support. Reset the values of ssa names + VARYING when the total number ssa names analyzed is + beyond the debug count specified. */ + +static void +do_dbg_cnt (void) +{ + unsigned i; + for (i = 0; i < num_ssa_names; i++) + { + if (!dbg_cnt (ccp)) + { + const_val[i].lattice_val = VARYING; + const_val[i].mask = double_int_minus_one; + const_val[i].value = NULL_TREE; + } + } +} + + +/* Do final substitution of propagated values, cleanup the flowgraph and + free allocated storage. + + Return TRUE when something was optimized. */ + +static bool +ccp_finalize (void) +{ + bool something_changed; + unsigned i; + + do_dbg_cnt (); + + /* Derive alignment and misalignment information from partially + constant pointers in the lattice or nonzero bits from partially + constant integers. */ + for (i = 1; i < num_ssa_names; ++i) + { + tree name = ssa_name (i); + prop_value_t *val; + unsigned int tem, align; + + if (!name + || (!POINTER_TYPE_P (TREE_TYPE (name)) + && (!INTEGRAL_TYPE_P (TREE_TYPE (name)) + /* Don't record nonzero bits before IPA to avoid + using too much memory. */ + || first_pass_instance))) + continue; + + val = get_value (name); + if (val->lattice_val != CONSTANT + || TREE_CODE (val->value) != INTEGER_CST) + continue; + + if (POINTER_TYPE_P (TREE_TYPE (name))) + { + /* Trailing mask bits specify the alignment, trailing value + bits the misalignment. */ + tem = val->mask.low; + align = (tem & -tem); + if (align > 1) + set_ptr_info_alignment (get_ptr_info (name), align, + (TREE_INT_CST_LOW (val->value) + & (align - 1))); + } + else + { + double_int nonzero_bits = val->mask; + nonzero_bits = nonzero_bits | tree_to_double_int (val->value); + nonzero_bits &= get_nonzero_bits (name); + set_nonzero_bits (name, nonzero_bits); + } + } + + /* Perform substitutions based on the known constant values. */ + something_changed = substitute_and_fold (get_constant_value, + ccp_fold_stmt, true); + + free (const_val); + const_val = NULL; + return something_changed;; +} + + +/* Compute the meet operator between *VAL1 and *VAL2. Store the result + in VAL1. + + any M UNDEFINED = any + any M VARYING = VARYING + Ci M Cj = Ci if (i == j) + Ci M Cj = VARYING if (i != j) + */ + +static void +ccp_lattice_meet (prop_value_t *val1, prop_value_t *val2) +{ + if (val1->lattice_val == UNDEFINED) + { + /* UNDEFINED M any = any */ + *val1 = *val2; + } + else if (val2->lattice_val == UNDEFINED) + { + /* any M UNDEFINED = any + Nothing to do. VAL1 already contains the value we want. */ + ; + } + else if (val1->lattice_val == VARYING + || val2->lattice_val == VARYING) + { + /* any M VARYING = VARYING. */ + val1->lattice_val = VARYING; + val1->mask = double_int_minus_one; + val1->value = NULL_TREE; + } + else if (val1->lattice_val == CONSTANT + && val2->lattice_val == CONSTANT + && TREE_CODE (val1->value) == INTEGER_CST + && TREE_CODE (val2->value) == INTEGER_CST) + { + /* Ci M Cj = Ci if (i == j) + Ci M Cj = VARYING if (i != j) + + For INTEGER_CSTs mask unequal bits. If no equal bits remain, + drop to varying. */ + val1->mask = val1->mask | val2->mask + | (tree_to_double_int (val1->value) + ^ tree_to_double_int (val2->value)); + if (val1->mask.is_minus_one ()) + { + val1->lattice_val = VARYING; + val1->value = NULL_TREE; + } + } + else if (val1->lattice_val == CONSTANT + && val2->lattice_val == CONSTANT + && simple_cst_equal (val1->value, val2->value) == 1) + { + /* Ci M Cj = Ci if (i == j) + Ci M Cj = VARYING if (i != j) + + VAL1 already contains the value we want for equivalent values. */ + } + else if (val1->lattice_val == CONSTANT + && val2->lattice_val == CONSTANT + && (TREE_CODE (val1->value) == ADDR_EXPR + || TREE_CODE (val2->value) == ADDR_EXPR)) + { + /* When not equal addresses are involved try meeting for + alignment. */ + prop_value_t tem = *val2; + if (TREE_CODE (val1->value) == ADDR_EXPR) + *val1 = get_value_for_expr (val1->value, true); + if (TREE_CODE (val2->value) == ADDR_EXPR) + tem = get_value_for_expr (val2->value, true); + ccp_lattice_meet (val1, &tem); + } + else + { + /* Any other combination is VARYING. */ + val1->lattice_val = VARYING; + val1->mask = double_int_minus_one; + val1->value = NULL_TREE; + } +} + + +/* Loop through the PHI_NODE's parameters for BLOCK and compare their + lattice values to determine PHI_NODE's lattice value. The value of a + PHI node is determined calling ccp_lattice_meet with all the arguments + of the PHI node that are incoming via executable edges. */ + +static enum ssa_prop_result +ccp_visit_phi_node (gimple phi) +{ + unsigned i; + prop_value_t *old_val, new_val; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nVisiting PHI node: "); + print_gimple_stmt (dump_file, phi, 0, dump_flags); + } + + old_val = get_value (gimple_phi_result (phi)); + switch (old_val->lattice_val) + { + case VARYING: + return SSA_PROP_VARYING; + + case CONSTANT: + new_val = *old_val; + break; + + case UNDEFINED: + new_val.lattice_val = UNDEFINED; + new_val.value = NULL_TREE; + break; + + default: + gcc_unreachable (); + } + + for (i = 0; i < gimple_phi_num_args (phi); i++) + { + /* Compute the meet operator over all the PHI arguments flowing + through executable edges. */ + edge e = gimple_phi_arg_edge (phi, i); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, + "\n Argument #%d (%d -> %d %sexecutable)\n", + i, e->src->index, e->dest->index, + (e->flags & EDGE_EXECUTABLE) ? "" : "not "); + } + + /* If the incoming edge is executable, Compute the meet operator for + the existing value of the PHI node and the current PHI argument. */ + if (e->flags & EDGE_EXECUTABLE) + { + tree arg = gimple_phi_arg (phi, i)->def; + prop_value_t arg_val = get_value_for_expr (arg, false); + + ccp_lattice_meet (&new_val, &arg_val); + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\t"); + print_generic_expr (dump_file, arg, dump_flags); + dump_lattice_value (dump_file, "\tValue: ", arg_val); + fprintf (dump_file, "\n"); + } + + if (new_val.lattice_val == VARYING) + break; + } + } + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + dump_lattice_value (dump_file, "\n PHI node value: ", new_val); + fprintf (dump_file, "\n\n"); + } + + /* Make the transition to the new value. */ + if (set_lattice_value (gimple_phi_result (phi), new_val)) + { + if (new_val.lattice_val == VARYING) + return SSA_PROP_VARYING; + else + return SSA_PROP_INTERESTING; + } + else + return SSA_PROP_NOT_INTERESTING; +} + +/* Return the constant value for OP or OP otherwise. */ + +static tree +valueize_op (tree op) +{ + if (TREE_CODE (op) == SSA_NAME) + { + tree tem = get_constant_value (op); + if (tem) + return tem; + } + return op; +} + +/* CCP specific front-end to the non-destructive constant folding + routines. + + Attempt to simplify the RHS of STMT knowing that one or more + operands are constants. + + If simplification is possible, return the simplified RHS, + otherwise return the original RHS or NULL_TREE. */ + +static tree +ccp_fold (gimple stmt) +{ + location_t loc = gimple_location (stmt); + switch (gimple_code (stmt)) + { + case GIMPLE_COND: + { + /* Handle comparison operators that can appear in GIMPLE form. */ + tree op0 = valueize_op (gimple_cond_lhs (stmt)); + tree op1 = valueize_op (gimple_cond_rhs (stmt)); + enum tree_code code = gimple_cond_code (stmt); + return fold_binary_loc (loc, code, boolean_type_node, op0, op1); + } + + case GIMPLE_SWITCH: + { + /* Return the constant switch index. */ + return valueize_op (gimple_switch_index (stmt)); + } + + case GIMPLE_ASSIGN: + case GIMPLE_CALL: + return gimple_fold_stmt_to_constant_1 (stmt, valueize_op); + + default: + gcc_unreachable (); + } +} + +/* Apply the operation CODE in type TYPE to the value, mask pair + RVAL and RMASK representing a value of type RTYPE and set + the value, mask pair *VAL and *MASK to the result. */ + +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) +{ + switch (code) + { + case BIT_NOT_EXPR: + *mask = rmask; + *val = ~rval; + break; + + case NEGATE_EXPR: + { + double_int temv, temm; + /* Return ~rval + 1. */ + bit_value_unop_1 (BIT_NOT_EXPR, type, &temv, &temm, type, rval, rmask); + bit_value_binop_1 (PLUS_EXPR, type, val, mask, + type, temv, temm, + type, double_int_one, double_int_zero); + break; + } + + CASE_CONVERT: + { + bool uns; + + /* First extend mask and value according to the original type. */ + uns = TYPE_UNSIGNED (rtype); + *mask = rmask.ext (TYPE_PRECISION (rtype), uns); + *val = rval.ext (TYPE_PRECISION (rtype), uns); + + /* Then extend mask and value according to the target type. */ + uns = TYPE_UNSIGNED (type); + *mask = (*mask).ext (TYPE_PRECISION (type), uns); + *val = (*val).ext (TYPE_PRECISION (type), uns); + break; + } + + default: + *mask = double_int_minus_one; + break; + } +} + +/* Apply the operation CODE in type TYPE to the value, mask pairs + R1VAL, R1MASK and R2VAL, R2MASK representing a values of type R1TYPE + and R2TYPE and set the value, mask pair *VAL and *MASK to the result. */ + +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) +{ + bool uns = TYPE_UNSIGNED (type); + /* Assume we'll get a constant result. Use an initial varying value, + we fall back to varying in the end if necessary. */ + *mask = double_int_minus_one; + switch (code) + { + case BIT_AND_EXPR: + /* The mask is constant where there is a known not + set bit, (m1 | m2) & ((v1 | m1) & (v2 | m2)) */ + *mask = (r1mask | r2mask) & (r1val | r1mask) & (r2val | r2mask); + *val = r1val & r2val; + break; + + case BIT_IOR_EXPR: + /* The mask is constant where there is a known + set bit, (m1 | m2) & ~((v1 & ~m1) | (v2 & ~m2)). */ + *mask = (r1mask | r2mask) + .and_not (r1val.and_not (r1mask) | r2val.and_not (r2mask)); + *val = r1val | r2val; + break; + + case BIT_XOR_EXPR: + /* m1 | m2 */ + *mask = r1mask | r2mask; + *val = r1val ^ r2val; + break; + + case LROTATE_EXPR: + case RROTATE_EXPR: + if (r2mask.is_zero ()) + { + HOST_WIDE_INT shift = r2val.low; + if (code == RROTATE_EXPR) + shift = -shift; + *mask = r1mask.lrotate (shift, TYPE_PRECISION (type)); + *val = r1val.lrotate (shift, TYPE_PRECISION (type)); + } + break; + + case LSHIFT_EXPR: + case RSHIFT_EXPR: + /* ??? We can handle partially known shift counts if we know + its sign. That way we can tell that (x << (y | 8)) & 255 + is zero. */ + if (r2mask.is_zero ()) + { + HOST_WIDE_INT shift = r2val.low; + if (code == RSHIFT_EXPR) + shift = -shift; + /* We need to know if we are doing a left or a right shift + to properly shift in zeros for left shift and unsigned + right shifts and the sign bit for signed right shifts. + For signed right shifts we shift in varying in case + the sign bit was varying. */ + if (shift > 0) + { + *mask = r1mask.llshift (shift, TYPE_PRECISION (type)); + *val = r1val.llshift (shift, TYPE_PRECISION (type)); + } + else if (shift < 0) + { + shift = -shift; + *mask = r1mask.rshift (shift, TYPE_PRECISION (type), !uns); + *val = r1val.rshift (shift, TYPE_PRECISION (type), !uns); + } + else + { + *mask = r1mask; + *val = r1val; + } + } + break; + + case PLUS_EXPR: + case POINTER_PLUS_EXPR: + { + double_int lo, hi; + /* Do the addition with unknown bits set to zero, to give carry-ins of + zero wherever possible. */ + lo = r1val.and_not (r1mask) + r2val.and_not (r2mask); + lo = lo.ext (TYPE_PRECISION (type), uns); + /* Do the addition with unknown bits set to one, to give carry-ins of + one wherever possible. */ + hi = (r1val | r1mask) + (r2val | r2mask); + hi = hi.ext (TYPE_PRECISION (type), uns); + /* Each bit in the result is known if (a) the corresponding bits in + both inputs are known, and (b) the carry-in to that bit position + is known. We can check condition (b) by seeing if we got the same + result with minimised carries as with maximised carries. */ + *mask = r1mask | r2mask | (lo ^ hi); + *mask = (*mask).ext (TYPE_PRECISION (type), uns); + /* It shouldn't matter whether we choose lo or hi here. */ + *val = lo; + break; + } + + case MINUS_EXPR: + { + double_int temv, temm; + bit_value_unop_1 (NEGATE_EXPR, r2type, &temv, &temm, + r2type, r2val, r2mask); + bit_value_binop_1 (PLUS_EXPR, type, val, mask, + r1type, r1val, r1mask, + r2type, temv, temm); + break; + } + + case MULT_EXPR: + { + /* Just track trailing zeros in both operands and transfer + them to the other. */ + int r1tz = (r1val | r1mask).trailing_zeros (); + int r2tz = (r2val | r2mask).trailing_zeros (); + if (r1tz + r2tz >= HOST_BITS_PER_DOUBLE_INT) + { + *mask = double_int_zero; + *val = double_int_zero; + } + else if (r1tz + r2tz > 0) + { + *mask = ~double_int::mask (r1tz + r2tz); + *mask = (*mask).ext (TYPE_PRECISION (type), uns); + *val = double_int_zero; + } + break; + } + + case EQ_EXPR: + case NE_EXPR: + { + double_int m = r1mask | r2mask; + if (r1val.and_not (m) != r2val.and_not (m)) + { + *mask = double_int_zero; + *val = ((code == EQ_EXPR) ? double_int_zero : double_int_one); + } + else + { + /* We know the result of a comparison is always one or zero. */ + *mask = double_int_one; + *val = double_int_zero; + } + break; + } + + case GE_EXPR: + case GT_EXPR: + { + double_int tem = r1val; + r1val = r2val; + r2val = tem; + tem = r1mask; + r1mask = r2mask; + r2mask = tem; + code = swap_tree_comparison (code); + } + /* Fallthru. */ + case LT_EXPR: + case LE_EXPR: + { + int minmax, maxmin; + /* If the most significant bits are not known we know nothing. */ + if (r1mask.is_negative () || r2mask.is_negative ()) + break; + + /* For comparisons the signedness is in the comparison operands. */ + uns = TYPE_UNSIGNED (r1type); + + /* If we know the most significant bits we know the values + value ranges by means of treating varying bits as zero + or one. Do a cross comparison of the max/min pairs. */ + maxmin = (r1val | r1mask).cmp (r2val.and_not (r2mask), uns); + minmax = r1val.and_not (r1mask).cmp (r2val | r2mask, uns); + if (maxmin < 0) /* r1 is less than r2. */ + { + *mask = double_int_zero; + *val = double_int_one; + } + else if (minmax > 0) /* r1 is not less or equal to r2. */ + { + *mask = double_int_zero; + *val = double_int_zero; + } + else if (maxmin == minmax) /* r1 and r2 are equal. */ + { + /* This probably should never happen as we'd have + folded the thing during fully constant value folding. */ + *mask = double_int_zero; + *val = (code == LE_EXPR ? double_int_one : double_int_zero); + } + else + { + /* We know the result of a comparison is always one or zero. */ + *mask = double_int_one; + *val = double_int_zero; + } + break; + } + + default:; + } +} + +/* Return the propagation value when applying the operation CODE to + the value RHS yielding type TYPE. */ + +static prop_value_t +bit_value_unop (enum tree_code code, tree type, tree rhs) +{ + prop_value_t rval = get_value_for_expr (rhs, true); + double_int value, mask; + prop_value_t val; + + if (rval.lattice_val == UNDEFINED) + return rval; + + gcc_assert ((rval.lattice_val == CONSTANT + && TREE_CODE (rval.value) == INTEGER_CST) + || rval.mask.is_minus_one ()); + bit_value_unop_1 (code, type, &value, &mask, + TREE_TYPE (rhs), value_to_double_int (rval), rval.mask); + if (!mask.is_minus_one ()) + { + val.lattice_val = CONSTANT; + val.mask = mask; + /* ??? Delay building trees here. */ + val.value = double_int_to_tree (type, value); + } + else + { + val.lattice_val = VARYING; + val.value = NULL_TREE; + val.mask = double_int_minus_one; + } + return val; +} + +/* Return the propagation value when applying the operation CODE to + the values RHS1 and RHS2 yielding type TYPE. */ + +static prop_value_t +bit_value_binop (enum tree_code code, tree type, tree rhs1, tree rhs2) +{ + prop_value_t r1val = get_value_for_expr (rhs1, true); + prop_value_t r2val = get_value_for_expr (rhs2, true); + double_int value, mask; + prop_value_t val; + + if (r1val.lattice_val == UNDEFINED + || r2val.lattice_val == UNDEFINED) + { + val.lattice_val = VARYING; + val.value = NULL_TREE; + val.mask = double_int_minus_one; + return val; + } + + gcc_assert ((r1val.lattice_val == CONSTANT + && TREE_CODE (r1val.value) == INTEGER_CST) + || r1val.mask.is_minus_one ()); + gcc_assert ((r2val.lattice_val == CONSTANT + && TREE_CODE (r2val.value) == INTEGER_CST) + || r2val.mask.is_minus_one ()); + bit_value_binop_1 (code, type, &value, &mask, + TREE_TYPE (rhs1), value_to_double_int (r1val), r1val.mask, + TREE_TYPE (rhs2), value_to_double_int (r2val), r2val.mask); + if (!mask.is_minus_one ()) + { + val.lattice_val = CONSTANT; + val.mask = mask; + /* ??? Delay building trees here. */ + val.value = double_int_to_tree (type, value); + } + else + { + val.lattice_val = VARYING; + val.value = NULL_TREE; + val.mask = double_int_minus_one; + } + return val; +} + +/* Return the propagation value for __builtin_assume_aligned + and functions with assume_aligned or alloc_aligned attribute. + For __builtin_assume_aligned, ATTR is NULL_TREE, + for assume_aligned attribute ATTR is non-NULL and ALLOC_ALIGNED + is false, for alloc_aligned attribute ATTR is non-NULL and + ALLOC_ALIGNED is true. */ + +static prop_value_t +bit_value_assume_aligned (gimple stmt, tree attr, prop_value_t ptrval, + bool alloc_aligned) +{ + tree align, misalign = NULL_TREE, type; + unsigned HOST_WIDE_INT aligni, misaligni = 0; + prop_value_t alignval; + double_int value, mask; + prop_value_t val; + + if (attr == NULL_TREE) + { + tree ptr = gimple_call_arg (stmt, 0); + type = TREE_TYPE (ptr); + ptrval = get_value_for_expr (ptr, true); + } + else + { + tree lhs = gimple_call_lhs (stmt); + type = TREE_TYPE (lhs); + } + + if (ptrval.lattice_val == UNDEFINED) + return ptrval; + gcc_assert ((ptrval.lattice_val == CONSTANT + && TREE_CODE (ptrval.value) == INTEGER_CST) + || ptrval.mask.is_minus_one ()); + if (attr == NULL_TREE) + { + /* Get aligni and misaligni from __builtin_assume_aligned. */ + align = gimple_call_arg (stmt, 1); + if (!tree_fits_uhwi_p (align)) + return ptrval; + aligni = tree_to_uhwi (align); + if (gimple_call_num_args (stmt) > 2) + { + misalign = gimple_call_arg (stmt, 2); + if (!tree_fits_uhwi_p (misalign)) + return ptrval; + misaligni = tree_to_uhwi (misalign); + } + } + else + { + /* Get aligni and misaligni from assume_aligned or + alloc_align attributes. */ + if (TREE_VALUE (attr) == NULL_TREE) + return ptrval; + attr = TREE_VALUE (attr); + align = TREE_VALUE (attr); + if (!tree_fits_uhwi_p (align)) + return ptrval; + aligni = tree_to_uhwi (align); + if (alloc_aligned) + { + if (aligni == 0 || aligni > gimple_call_num_args (stmt)) + return ptrval; + align = gimple_call_arg (stmt, aligni - 1); + if (!tree_fits_uhwi_p (align)) + return ptrval; + aligni = tree_to_uhwi (align); + } + else if (TREE_CHAIN (attr) && TREE_VALUE (TREE_CHAIN (attr))) + { + misalign = TREE_VALUE (TREE_CHAIN (attr)); + if (!tree_fits_uhwi_p (misalign)) + return ptrval; + misaligni = tree_to_uhwi (misalign); + } + } + if (aligni <= 1 || (aligni & (aligni - 1)) != 0 || misaligni >= aligni) + return ptrval; + + align = build_int_cst_type (type, -aligni); + alignval = get_value_for_expr (align, true); + bit_value_binop_1 (BIT_AND_EXPR, type, &value, &mask, + type, value_to_double_int (ptrval), ptrval.mask, + type, value_to_double_int (alignval), alignval.mask); + if (!mask.is_minus_one ()) + { + val.lattice_val = CONSTANT; + val.mask = mask; + gcc_assert ((mask.low & (aligni - 1)) == 0); + gcc_assert ((value.low & (aligni - 1)) == 0); + value.low |= misaligni; + /* ??? Delay building trees here. */ + val.value = double_int_to_tree (type, value); + } + else + { + val.lattice_val = VARYING; + val.value = NULL_TREE; + val.mask = double_int_minus_one; + } + return val; +} + +/* Evaluate statement STMT. + Valid only for assignments, calls, conditionals, and switches. */ + +static prop_value_t +evaluate_stmt (gimple stmt) +{ + prop_value_t val; + tree simplified = NULL_TREE; + ccp_lattice_t likelyvalue = likely_value (stmt); + bool is_constant = false; + unsigned int align; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "which is likely "); + switch (likelyvalue) + { + case CONSTANT: + fprintf (dump_file, "CONSTANT"); + break; + case UNDEFINED: + fprintf (dump_file, "UNDEFINED"); + break; + case VARYING: + fprintf (dump_file, "VARYING"); + break; + default:; + } + fprintf (dump_file, "\n"); + } + + /* If the statement is likely to have a CONSTANT result, then try + to fold the statement to determine the constant value. */ + /* FIXME. This is the only place that we call ccp_fold. + Since likely_value never returns CONSTANT for calls, we will + not attempt to fold them, including builtins that may profit. */ + if (likelyvalue == CONSTANT) + { + fold_defer_overflow_warnings (); + simplified = ccp_fold (stmt); + is_constant = simplified && is_gimple_min_invariant (simplified); + fold_undefer_overflow_warnings (is_constant, stmt, 0); + if (is_constant) + { + /* The statement produced a constant value. */ + val.lattice_val = CONSTANT; + val.value = simplified; + val.mask = double_int_zero; + } + } + /* If the statement is likely to have a VARYING result, then do not + bother folding the statement. */ + else if (likelyvalue == VARYING) + { + enum gimple_code code = gimple_code (stmt); + if (code == GIMPLE_ASSIGN) + { + enum tree_code subcode = gimple_assign_rhs_code (stmt); + + /* Other cases cannot satisfy is_gimple_min_invariant + without folding. */ + if (get_gimple_rhs_class (subcode) == GIMPLE_SINGLE_RHS) + simplified = gimple_assign_rhs1 (stmt); + } + else if (code == GIMPLE_SWITCH) + simplified = gimple_switch_index (stmt); + else + /* These cannot satisfy is_gimple_min_invariant without folding. */ + gcc_assert (code == GIMPLE_CALL || code == GIMPLE_COND); + is_constant = simplified && is_gimple_min_invariant (simplified); + if (is_constant) + { + /* The statement produced a constant value. */ + val.lattice_val = CONSTANT; + val.value = simplified; + val.mask = double_int_zero; + } + } + + /* Resort to simplification for bitwise tracking. */ + if (flag_tree_bit_ccp + && (likelyvalue == CONSTANT || is_gimple_call (stmt)) + && !is_constant) + { + enum gimple_code code = gimple_code (stmt); + val.lattice_val = VARYING; + val.value = NULL_TREE; + val.mask = double_int_minus_one; + if (code == GIMPLE_ASSIGN) + { + enum tree_code subcode = gimple_assign_rhs_code (stmt); + tree rhs1 = gimple_assign_rhs1 (stmt); + switch (get_gimple_rhs_class (subcode)) + { + case GIMPLE_SINGLE_RHS: + if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) + || POINTER_TYPE_P (TREE_TYPE (rhs1))) + val = get_value_for_expr (rhs1, true); + break; + + case GIMPLE_UNARY_RHS: + if ((INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) + || POINTER_TYPE_P (TREE_TYPE (rhs1))) + && (INTEGRAL_TYPE_P (gimple_expr_type (stmt)) + || POINTER_TYPE_P (gimple_expr_type (stmt)))) + val = bit_value_unop (subcode, gimple_expr_type (stmt), rhs1); + break; + + case GIMPLE_BINARY_RHS: + if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) + || POINTER_TYPE_P (TREE_TYPE (rhs1))) + { + tree lhs = gimple_assign_lhs (stmt); + tree rhs2 = gimple_assign_rhs2 (stmt); + val = bit_value_binop (subcode, + TREE_TYPE (lhs), rhs1, rhs2); + } + break; + + default:; + } + } + else if (code == GIMPLE_COND) + { + enum tree_code code = gimple_cond_code (stmt); + tree rhs1 = gimple_cond_lhs (stmt); + tree rhs2 = gimple_cond_rhs (stmt); + if (INTEGRAL_TYPE_P (TREE_TYPE (rhs1)) + || POINTER_TYPE_P (TREE_TYPE (rhs1))) + val = bit_value_binop (code, TREE_TYPE (rhs1), rhs1, rhs2); + } + else if (gimple_call_builtin_p (stmt, BUILT_IN_NORMAL)) + { + tree fndecl = gimple_call_fndecl (stmt); + switch (DECL_FUNCTION_CODE (fndecl)) + { + case BUILT_IN_MALLOC: + case BUILT_IN_REALLOC: + case BUILT_IN_CALLOC: + case BUILT_IN_STRDUP: + case BUILT_IN_STRNDUP: + val.lattice_val = CONSTANT; + val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0); + val.mask = double_int::from_shwi + (~(((HOST_WIDE_INT) MALLOC_ABI_ALIGNMENT) + / BITS_PER_UNIT - 1)); + break; + + case BUILT_IN_ALLOCA: + case BUILT_IN_ALLOCA_WITH_ALIGN: + align = (DECL_FUNCTION_CODE (fndecl) == BUILT_IN_ALLOCA_WITH_ALIGN + ? TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)) + : BIGGEST_ALIGNMENT); + val.lattice_val = CONSTANT; + val.value = build_int_cst (TREE_TYPE (gimple_get_lhs (stmt)), 0); + val.mask = double_int::from_shwi (~(((HOST_WIDE_INT) align) + / BITS_PER_UNIT - 1)); + break; + + /* These builtins return their first argument, unmodified. */ + case BUILT_IN_MEMCPY: + case BUILT_IN_MEMMOVE: + case BUILT_IN_MEMSET: + case BUILT_IN_STRCPY: + case BUILT_IN_STRNCPY: + case BUILT_IN_MEMCPY_CHK: + case BUILT_IN_MEMMOVE_CHK: + case BUILT_IN_MEMSET_CHK: + case BUILT_IN_STRCPY_CHK: + case BUILT_IN_STRNCPY_CHK: + val = get_value_for_expr (gimple_call_arg (stmt, 0), true); + break; + + case BUILT_IN_ASSUME_ALIGNED: + val = bit_value_assume_aligned (stmt, NULL_TREE, val, false); + break; + + default:; + } + } + if (is_gimple_call (stmt) && gimple_call_lhs (stmt)) + { + tree fntype = gimple_call_fntype (stmt); + if (fntype) + { + tree attrs = lookup_attribute ("assume_aligned", + TYPE_ATTRIBUTES (fntype)); + if (attrs) + val = bit_value_assume_aligned (stmt, attrs, val, false); + attrs = lookup_attribute ("alloc_align", + TYPE_ATTRIBUTES (fntype)); + if (attrs) + val = bit_value_assume_aligned (stmt, attrs, val, true); + } + } + is_constant = (val.lattice_val == CONSTANT); + } + + if (flag_tree_bit_ccp + && ((is_constant && TREE_CODE (val.value) == INTEGER_CST) + || (!is_constant && likelyvalue != UNDEFINED)) + && gimple_get_lhs (stmt) + && TREE_CODE (gimple_get_lhs (stmt)) == SSA_NAME) + { + tree lhs = gimple_get_lhs (stmt); + double_int nonzero_bits = get_nonzero_bits (lhs); + double_int mask = double_int::mask (TYPE_PRECISION (TREE_TYPE (lhs))); + if (nonzero_bits != double_int_minus_one && nonzero_bits != mask) + { + if (!is_constant) + { + val.lattice_val = CONSTANT; + val.value = build_zero_cst (TREE_TYPE (lhs)); + /* CCP wants the bits above precision set. */ + val.mask = nonzero_bits | ~mask; + is_constant = true; + } + else + { + double_int valv = tree_to_double_int (val.value); + if (!(valv & ~nonzero_bits & mask).is_zero ()) + val.value = double_int_to_tree (TREE_TYPE (lhs), + valv & nonzero_bits); + if (nonzero_bits.is_zero ()) + val.mask = double_int_zero; + else + val.mask = val.mask & (nonzero_bits | ~mask); + } + } + } + + if (!is_constant) + { + /* The statement produced a nonconstant value. If the statement + had UNDEFINED operands, then the result of the statement + should be UNDEFINED. Otherwise, the statement is VARYING. */ + if (likelyvalue == UNDEFINED) + { + val.lattice_val = likelyvalue; + val.mask = double_int_zero; + } + else + { + val.lattice_val = VARYING; + val.mask = double_int_minus_one; + } + + val.value = NULL_TREE; + } + + return val; +} + +typedef hash_table <pointer_hash <gimple_statement_base> > gimple_htab; + +/* Given a BUILT_IN_STACK_SAVE value SAVED_VAL, insert a clobber of VAR before + each matching BUILT_IN_STACK_RESTORE. Mark visited phis in VISITED. */ + +static void +insert_clobber_before_stack_restore (tree saved_val, tree var, + gimple_htab *visited) +{ + gimple stmt, clobber_stmt; + tree clobber; + imm_use_iterator iter; + gimple_stmt_iterator i; + gimple *slot; + + FOR_EACH_IMM_USE_STMT (stmt, iter, saved_val) + if (gimple_call_builtin_p (stmt, BUILT_IN_STACK_RESTORE)) + { + clobber = build_constructor (TREE_TYPE (var), + NULL); + TREE_THIS_VOLATILE (clobber) = 1; + clobber_stmt = gimple_build_assign (var, clobber); + + i = gsi_for_stmt (stmt); + gsi_insert_before (&i, clobber_stmt, GSI_SAME_STMT); + } + else if (gimple_code (stmt) == GIMPLE_PHI) + { + if (!visited->is_created ()) + visited->create (10); + + slot = visited->find_slot (stmt, INSERT); + if (*slot != NULL) + continue; + + *slot = stmt; + insert_clobber_before_stack_restore (gimple_phi_result (stmt), var, + visited); + } + else if (gimple_assign_ssa_name_copy_p (stmt)) + insert_clobber_before_stack_restore (gimple_assign_lhs (stmt), var, + visited); + else + gcc_assert (is_gimple_debug (stmt)); +} + +/* Advance the iterator to the previous non-debug gimple statement in the same + or dominating basic block. */ + +static inline void +gsi_prev_dom_bb_nondebug (gimple_stmt_iterator *i) +{ + basic_block dom; + + gsi_prev_nondebug (i); + while (gsi_end_p (*i)) + { + dom = get_immediate_dominator (CDI_DOMINATORS, i->bb); + if (dom == NULL || dom == ENTRY_BLOCK_PTR_FOR_FN (cfun)) + return; + + *i = gsi_last_bb (dom); + } +} + +/* Find a BUILT_IN_STACK_SAVE dominating gsi_stmt (I), and insert + a clobber of VAR before each matching BUILT_IN_STACK_RESTORE. + + It is possible that BUILT_IN_STACK_SAVE cannot be find in a dominator when a + previous pass (such as DOM) duplicated it along multiple paths to a BB. In + that case the function gives up without inserting the clobbers. */ + +static void +insert_clobbers_for_var (gimple_stmt_iterator i, tree var) +{ + gimple stmt; + tree saved_val; + gimple_htab visited; + + for (; !gsi_end_p (i); gsi_prev_dom_bb_nondebug (&i)) + { + stmt = gsi_stmt (i); + + if (!gimple_call_builtin_p (stmt, BUILT_IN_STACK_SAVE)) + continue; + + saved_val = gimple_call_lhs (stmt); + if (saved_val == NULL_TREE) + continue; + + insert_clobber_before_stack_restore (saved_val, var, &visited); + break; + } + + if (visited.is_created ()) + visited.dispose (); +} + +/* Detects a __builtin_alloca_with_align with constant size argument. Declares + fixed-size array and returns the address, if found, otherwise returns + NULL_TREE. */ + +static tree +fold_builtin_alloca_with_align (gimple stmt) +{ + unsigned HOST_WIDE_INT size, threshold, n_elem; + tree lhs, arg, block, var, elem_type, array_type; + + /* Get lhs. */ + lhs = gimple_call_lhs (stmt); + if (lhs == NULL_TREE) + return NULL_TREE; + + /* Detect constant argument. */ + arg = get_constant_value (gimple_call_arg (stmt, 0)); + if (arg == NULL_TREE + || TREE_CODE (arg) != INTEGER_CST + || !tree_fits_uhwi_p (arg)) + return NULL_TREE; + + size = tree_to_uhwi (arg); + + /* Heuristic: don't fold large allocas. */ + threshold = (unsigned HOST_WIDE_INT)PARAM_VALUE (PARAM_LARGE_STACK_FRAME); + /* In case the alloca is located at function entry, it has the same lifetime + as a declared array, so we allow a larger size. */ + block = gimple_block (stmt); + if (!(cfun->after_inlining + && TREE_CODE (BLOCK_SUPERCONTEXT (block)) == FUNCTION_DECL)) + threshold /= 10; + if (size > threshold) + return NULL_TREE; + + /* Declare array. */ + elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1); + n_elem = size * 8 / BITS_PER_UNIT; + array_type = build_array_type_nelts (elem_type, n_elem); + var = create_tmp_var (array_type, NULL); + DECL_ALIGN (var) = TREE_INT_CST_LOW (gimple_call_arg (stmt, 1)); + { + struct ptr_info_def *pi = SSA_NAME_PTR_INFO (lhs); + if (pi != NULL && !pi->pt.anything) + { + bool singleton_p; + unsigned uid; + singleton_p = pt_solution_singleton_p (&pi->pt, &uid); + gcc_assert (singleton_p); + SET_DECL_PT_UID (var, uid); + } + } + + /* Fold alloca to the address of the array. */ + return fold_convert (TREE_TYPE (lhs), build_fold_addr_expr (var)); +} + +/* Fold the stmt at *GSI with CCP specific information that propagating + and regular folding does not catch. */ + +static bool +ccp_fold_stmt (gimple_stmt_iterator *gsi) +{ + gimple stmt = gsi_stmt (*gsi); + + switch (gimple_code (stmt)) + { + case GIMPLE_COND: + { + prop_value_t val; + /* Statement evaluation will handle type mismatches in constants + more gracefully than the final propagation. This allows us to + fold more conditionals here. */ + val = evaluate_stmt (stmt); + if (val.lattice_val != CONSTANT + || !val.mask.is_zero ()) + return false; + + if (dump_file) + { + fprintf (dump_file, "Folding predicate "); + print_gimple_expr (dump_file, stmt, 0, 0); + fprintf (dump_file, " to "); + print_generic_expr (dump_file, val.value, 0); + fprintf (dump_file, "\n"); + } + + if (integer_zerop (val.value)) + gimple_cond_make_false (stmt); + else + gimple_cond_make_true (stmt); + + return true; + } + + case GIMPLE_CALL: + { + tree lhs = gimple_call_lhs (stmt); + int flags = gimple_call_flags (stmt); + tree val; + tree argt; + bool changed = false; + unsigned i; + + /* If the call was folded into a constant make sure it goes + away even if we cannot propagate into all uses because of + type issues. */ + if (lhs + && TREE_CODE (lhs) == SSA_NAME + && (val = get_constant_value (lhs)) + /* Don't optimize away calls that have side-effects. */ + && (flags & (ECF_CONST|ECF_PURE)) != 0 + && (flags & ECF_LOOPING_CONST_OR_PURE) == 0) + { + tree new_rhs = unshare_expr (val); + bool res; + if (!useless_type_conversion_p (TREE_TYPE (lhs), + TREE_TYPE (new_rhs))) + new_rhs = fold_convert (TREE_TYPE (lhs), new_rhs); + res = update_call_from_tree (gsi, new_rhs); + gcc_assert (res); + return true; + } + + /* Internal calls provide no argument types, so the extra laxity + for normal calls does not apply. */ + if (gimple_call_internal_p (stmt)) + return false; + + /* The heuristic of fold_builtin_alloca_with_align differs before and + after inlining, so we don't require the arg to be changed into a + constant for folding, but just to be constant. */ + if (gimple_call_builtin_p (stmt, BUILT_IN_ALLOCA_WITH_ALIGN)) + { + tree new_rhs = fold_builtin_alloca_with_align (stmt); + if (new_rhs) + { + bool res = update_call_from_tree (gsi, new_rhs); + tree var = TREE_OPERAND (TREE_OPERAND (new_rhs, 0),0); + gcc_assert (res); + insert_clobbers_for_var (*gsi, var); + return true; + } + } + + /* Propagate into the call arguments. Compared to replace_uses_in + this can use the argument slot types for type verification + instead of the current argument type. We also can safely + drop qualifiers here as we are dealing with constants anyway. */ + argt = TYPE_ARG_TYPES (gimple_call_fntype (stmt)); + for (i = 0; i < gimple_call_num_args (stmt) && argt; + ++i, argt = TREE_CHAIN (argt)) + { + tree arg = gimple_call_arg (stmt, i); + if (TREE_CODE (arg) == SSA_NAME + && (val = get_constant_value (arg)) + && useless_type_conversion_p + (TYPE_MAIN_VARIANT (TREE_VALUE (argt)), + TYPE_MAIN_VARIANT (TREE_TYPE (val)))) + { + gimple_call_set_arg (stmt, i, unshare_expr (val)); + changed = true; + } + } + + return changed; + } + + case GIMPLE_ASSIGN: + { + tree lhs = gimple_assign_lhs (stmt); + tree val; + + /* If we have a load that turned out to be constant replace it + as we cannot propagate into all uses in all cases. */ + if (gimple_assign_single_p (stmt) + && TREE_CODE (lhs) == SSA_NAME + && (val = get_constant_value (lhs))) + { + tree rhs = unshare_expr (val); + if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) + rhs = fold_build1 (VIEW_CONVERT_EXPR, TREE_TYPE (lhs), rhs); + gimple_assign_set_rhs_from_tree (gsi, rhs); + return true; + } + + return false; + } + + default: + return false; + } +} + +/* Visit the assignment statement STMT. Set the value of its LHS to the + value computed by the RHS and store LHS in *OUTPUT_P. If STMT + creates virtual definitions, set the value of each new name to that + of the RHS (if we can derive a constant out of the RHS). + Value-returning call statements also perform an assignment, and + are handled here. */ + +static enum ssa_prop_result +visit_assignment (gimple stmt, tree *output_p) +{ + prop_value_t val; + enum ssa_prop_result retval; + + tree lhs = gimple_get_lhs (stmt); + + gcc_assert (gimple_code (stmt) != GIMPLE_CALL + || gimple_call_lhs (stmt) != NULL_TREE); + + if (gimple_assign_single_p (stmt) + && gimple_assign_rhs_code (stmt) == SSA_NAME) + /* For a simple copy operation, we copy the lattice values. */ + val = *get_value (gimple_assign_rhs1 (stmt)); + else + /* Evaluate the statement, which could be + either a GIMPLE_ASSIGN or a GIMPLE_CALL. */ + val = evaluate_stmt (stmt); + + retval = SSA_PROP_NOT_INTERESTING; + + /* Set the lattice value of the statement's output. */ + if (TREE_CODE (lhs) == SSA_NAME) + { + /* If STMT is an assignment to an SSA_NAME, we only have one + value to set. */ + if (set_lattice_value (lhs, val)) + { + *output_p = lhs; + if (val.lattice_val == VARYING) + retval = SSA_PROP_VARYING; + else + retval = SSA_PROP_INTERESTING; + } + } + + return retval; +} + + +/* Visit the conditional statement STMT. Return SSA_PROP_INTERESTING + if it can determine which edge will be taken. Otherwise, return + SSA_PROP_VARYING. */ + +static enum ssa_prop_result +visit_cond_stmt (gimple stmt, edge *taken_edge_p) +{ + prop_value_t val; + basic_block block; + + block = gimple_bb (stmt); + val = evaluate_stmt (stmt); + if (val.lattice_val != CONSTANT + || !val.mask.is_zero ()) + return SSA_PROP_VARYING; + + /* Find which edge out of the conditional block will be taken and add it + to the worklist. If no single edge can be determined statically, + return SSA_PROP_VARYING to feed all the outgoing edges to the + propagation engine. */ + *taken_edge_p = find_taken_edge (block, val.value); + if (*taken_edge_p) + return SSA_PROP_INTERESTING; + else + return SSA_PROP_VARYING; +} + + +/* Evaluate statement STMT. If the statement produces an output value and + its evaluation changes the lattice value of its output, return + SSA_PROP_INTERESTING and set *OUTPUT_P to the SSA_NAME holding the + output value. + + If STMT is a conditional branch and we can determine its truth + value, set *TAKEN_EDGE_P accordingly. If STMT produces a varying + value, return SSA_PROP_VARYING. */ + +static enum ssa_prop_result +ccp_visit_stmt (gimple stmt, edge *taken_edge_p, tree *output_p) +{ + tree def; + ssa_op_iter iter; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "\nVisiting statement:\n"); + print_gimple_stmt (dump_file, stmt, 0, dump_flags); + } + + switch (gimple_code (stmt)) + { + case GIMPLE_ASSIGN: + /* If the statement is an assignment that produces a single + output value, evaluate its RHS to see if the lattice value of + its output has changed. */ + return visit_assignment (stmt, output_p); + + case GIMPLE_CALL: + /* A value-returning call also performs an assignment. */ + if (gimple_call_lhs (stmt) != NULL_TREE) + return visit_assignment (stmt, output_p); + break; + + case GIMPLE_COND: + case GIMPLE_SWITCH: + /* If STMT is a conditional branch, see if we can determine + which branch will be taken. */ + /* FIXME. It appears that we should be able to optimize + computed GOTOs here as well. */ + return visit_cond_stmt (stmt, taken_edge_p); + + default: + break; + } + + /* Any other kind of statement is not interesting for constant + propagation and, therefore, not worth simulating. */ + if (dump_file && (dump_flags & TDF_DETAILS)) + fprintf (dump_file, "No interesting values produced. Marked VARYING.\n"); + + /* Definitions made by statements other than assignments to + SSA_NAMEs represent unknown modifications to their outputs. + Mark them VARYING. */ + FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) + { + prop_value_t v = { VARYING, NULL_TREE, { -1, (HOST_WIDE_INT) -1 } }; + set_lattice_value (def, v); + } + + return SSA_PROP_VARYING; +} + + +/* Main entry point for SSA Conditional Constant Propagation. */ + +static unsigned int +do_ssa_ccp (void) +{ + unsigned int todo = 0; + calculate_dominance_info (CDI_DOMINATORS); + ccp_initialize (); + ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); + if (ccp_finalize ()) + todo = (TODO_cleanup_cfg | TODO_update_ssa); + free_dominance_info (CDI_DOMINATORS); + return todo; +} + + +static bool +gate_ccp (void) +{ + return flag_tree_ccp != 0; +} + + +namespace { + +const pass_data pass_data_ccp = +{ + GIMPLE_PASS, /* type */ + "ccp", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + true, /* has_gate */ + true, /* has_execute */ + TV_TREE_CCP, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + ( TODO_verify_ssa | TODO_update_address_taken + | TODO_verify_stmts ), /* todo_flags_finish */ +}; + +class pass_ccp : public gimple_opt_pass +{ +public: + pass_ccp (gcc::context *ctxt) + : gimple_opt_pass (pass_data_ccp, ctxt) + {} + + /* opt_pass methods: */ + opt_pass * clone () { return new pass_ccp (m_ctxt); } + bool gate () { return gate_ccp (); } + unsigned int execute () { return do_ssa_ccp (); } + +}; // class pass_ccp + +} // anon namespace + +gimple_opt_pass * +make_pass_ccp (gcc::context *ctxt) +{ + return new pass_ccp (ctxt); +} + + + +/* Try to optimize out __builtin_stack_restore. Optimize it out + if there is another __builtin_stack_restore in the same basic + block and no calls or ASM_EXPRs are in between, or if this block's + only outgoing edge is to EXIT_BLOCK and there are no calls or + ASM_EXPRs after this __builtin_stack_restore. */ + +static tree +optimize_stack_restore (gimple_stmt_iterator i) +{ + tree callee; + gimple stmt; + + basic_block bb = gsi_bb (i); + gimple call = gsi_stmt (i); + + if (gimple_code (call) != GIMPLE_CALL + || gimple_call_num_args (call) != 1 + || TREE_CODE (gimple_call_arg (call, 0)) != SSA_NAME + || !POINTER_TYPE_P (TREE_TYPE (gimple_call_arg (call, 0)))) + return NULL_TREE; + + for (gsi_next (&i); !gsi_end_p (i); gsi_next (&i)) + { + stmt = gsi_stmt (i); + if (gimple_code (stmt) == GIMPLE_ASM) + return NULL_TREE; + if (gimple_code (stmt) != GIMPLE_CALL) + continue; + + callee = gimple_call_fndecl (stmt); + if (!callee + || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL + /* All regular builtins are ok, just obviously not alloca. */ + || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA + || DECL_FUNCTION_CODE (callee) == BUILT_IN_ALLOCA_WITH_ALIGN) + return NULL_TREE; + + if (DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_RESTORE) + goto second_stack_restore; + } + + if (!gsi_end_p (i)) + return NULL_TREE; + + /* Allow one successor of the exit block, or zero successors. */ + switch (EDGE_COUNT (bb->succs)) + { + case 0: + break; + case 1: + if (single_succ_edge (bb)->dest != EXIT_BLOCK_PTR_FOR_FN (cfun)) + return NULL_TREE; + break; + default: + return NULL_TREE; + } + second_stack_restore: + + /* If there's exactly one use, then zap the call to __builtin_stack_save. + If there are multiple uses, then the last one should remove the call. + In any case, whether the call to __builtin_stack_save can be removed + or not is irrelevant to removing the call to __builtin_stack_restore. */ + if (has_single_use (gimple_call_arg (call, 0))) + { + gimple stack_save = SSA_NAME_DEF_STMT (gimple_call_arg (call, 0)); + if (is_gimple_call (stack_save)) + { + callee = gimple_call_fndecl (stack_save); + if (callee + && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL + && DECL_FUNCTION_CODE (callee) == BUILT_IN_STACK_SAVE) + { + gimple_stmt_iterator stack_save_gsi; + tree rhs; + + stack_save_gsi = gsi_for_stmt (stack_save); + rhs = build_int_cst (TREE_TYPE (gimple_call_arg (call, 0)), 0); + update_call_from_tree (&stack_save_gsi, rhs); + } + } + } + + /* No effect, so the statement will be deleted. */ + return integer_zero_node; +} + +/* If va_list type is a simple pointer and nothing special is needed, + optimize __builtin_va_start (&ap, 0) into ap = __builtin_next_arg (0), + __builtin_va_end (&ap) out as NOP and __builtin_va_copy into a simple + pointer assignment. */ + +static tree +optimize_stdarg_builtin (gimple call) +{ + tree callee, lhs, rhs, cfun_va_list; + bool va_list_simple_ptr; + location_t loc = gimple_location (call); + + if (gimple_code (call) != GIMPLE_CALL) + return NULL_TREE; + + callee = gimple_call_fndecl (call); + + cfun_va_list = targetm.fn_abi_va_list (callee); + va_list_simple_ptr = POINTER_TYPE_P (cfun_va_list) + && (TREE_TYPE (cfun_va_list) == void_type_node + || TREE_TYPE (cfun_va_list) == char_type_node); + + switch (DECL_FUNCTION_CODE (callee)) + { + case BUILT_IN_VA_START: + if (!va_list_simple_ptr + || targetm.expand_builtin_va_start != NULL + || !builtin_decl_explicit_p (BUILT_IN_NEXT_ARG)) + return NULL_TREE; + + if (gimple_call_num_args (call) != 2) + return NULL_TREE; + + lhs = gimple_call_arg (call, 0); + if (!POINTER_TYPE_P (TREE_TYPE (lhs)) + || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs))) + != TYPE_MAIN_VARIANT (cfun_va_list)) + return NULL_TREE; + + lhs = build_fold_indirect_ref_loc (loc, lhs); + rhs = build_call_expr_loc (loc, builtin_decl_explicit (BUILT_IN_NEXT_ARG), + 1, integer_zero_node); + rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); + return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs); + + case BUILT_IN_VA_COPY: + if (!va_list_simple_ptr) + return NULL_TREE; + + if (gimple_call_num_args (call) != 2) + return NULL_TREE; + + lhs = gimple_call_arg (call, 0); + if (!POINTER_TYPE_P (TREE_TYPE (lhs)) + || TYPE_MAIN_VARIANT (TREE_TYPE (TREE_TYPE (lhs))) + != TYPE_MAIN_VARIANT (cfun_va_list)) + return NULL_TREE; + + lhs = build_fold_indirect_ref_loc (loc, lhs); + rhs = gimple_call_arg (call, 1); + if (TYPE_MAIN_VARIANT (TREE_TYPE (rhs)) + != TYPE_MAIN_VARIANT (cfun_va_list)) + return NULL_TREE; + + rhs = fold_convert_loc (loc, TREE_TYPE (lhs), rhs); + return build2 (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs); + + case BUILT_IN_VA_END: + /* No effect, so the statement will be deleted. */ + return integer_zero_node; + + default: + gcc_unreachable (); + } +} + +/* Attemp to make the block of __builtin_unreachable I unreachable by changing + the incoming jumps. Return true if at least one jump was changed. */ + +static bool +optimize_unreachable (gimple_stmt_iterator i) +{ + basic_block bb = gsi_bb (i); + gimple_stmt_iterator gsi; + gimple stmt; + edge_iterator ei; + edge e; + bool ret; + + for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) + { + stmt = gsi_stmt (gsi); + + if (is_gimple_debug (stmt)) + continue; + + if (gimple_code (stmt) == GIMPLE_LABEL) + { + /* Verify we do not need to preserve the label. */ + if (FORCED_LABEL (gimple_label_label (stmt))) + return false; + + continue; + } + + /* Only handle the case that __builtin_unreachable is the first statement + in the block. We rely on DCE to remove stmts without side-effects + before __builtin_unreachable. */ + if (gsi_stmt (gsi) != gsi_stmt (i)) + return false; + } + + ret = false; + FOR_EACH_EDGE (e, ei, bb->preds) + { + gsi = gsi_last_bb (e->src); + if (gsi_end_p (gsi)) + continue; + + stmt = gsi_stmt (gsi); + if (gimple_code (stmt) == GIMPLE_COND) + { + if (e->flags & EDGE_TRUE_VALUE) + gimple_cond_make_false (stmt); + else if (e->flags & EDGE_FALSE_VALUE) + gimple_cond_make_true (stmt); + else + gcc_unreachable (); + update_stmt (stmt); + } + else + { + /* Todo: handle other cases, f.i. switch statement. */ + continue; + } + + ret = true; + } + + return ret; +} + +/* A simple pass that attempts to fold all builtin functions. This pass + is run after we've propagated as many constants as we can. */ + +static unsigned int +execute_fold_all_builtins (void) +{ + bool cfg_changed = false; + basic_block bb; + unsigned int todoflags = 0; + + FOR_EACH_BB_FN (bb, cfun) + { + gimple_stmt_iterator i; + for (i = gsi_start_bb (bb); !gsi_end_p (i); ) + { + gimple stmt, old_stmt; + tree callee, result; + enum built_in_function fcode; + + stmt = gsi_stmt (i); + + if (gimple_code (stmt) != GIMPLE_CALL) + { + /* Remove all *ssaname_N ={v} {CLOBBER}; stmts, + after the last GIMPLE DSE they aren't needed and might + unnecessarily keep the SSA_NAMEs live. */ + if (gimple_clobber_p (stmt)) + { + tree lhs = gimple_assign_lhs (stmt); + if (TREE_CODE (lhs) == MEM_REF + && TREE_CODE (TREE_OPERAND (lhs, 0)) == SSA_NAME) + { + unlink_stmt_vdef (stmt); + gsi_remove (&i, true); + release_defs (stmt); + continue; + } + } + gsi_next (&i); + continue; + } + callee = gimple_call_fndecl (stmt); + if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL) + { + gsi_next (&i); + continue; + } + fcode = DECL_FUNCTION_CODE (callee); + + result = gimple_fold_builtin (stmt); + + if (result) + gimple_remove_stmt_histograms (cfun, stmt); + + if (!result) + switch (DECL_FUNCTION_CODE (callee)) + { + case BUILT_IN_CONSTANT_P: + /* Resolve __builtin_constant_p. If it hasn't been + folded to integer_one_node by now, it's fairly + certain that the value simply isn't constant. */ + result = integer_zero_node; + break; + + case BUILT_IN_ASSUME_ALIGNED: + /* Remove __builtin_assume_aligned. */ + result = gimple_call_arg (stmt, 0); + break; + + case BUILT_IN_STACK_RESTORE: + result = optimize_stack_restore (i); + if (result) + break; + gsi_next (&i); + continue; + + case BUILT_IN_UNREACHABLE: + if (optimize_unreachable (i)) + cfg_changed = true; + break; + + case BUILT_IN_VA_START: + case BUILT_IN_VA_END: + case BUILT_IN_VA_COPY: + /* These shouldn't be folded before pass_stdarg. */ + result = optimize_stdarg_builtin (stmt); + if (result) + break; + /* FALLTHRU */ + + default: + gsi_next (&i); + continue; + } + + if (result == NULL_TREE) + break; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "Simplified\n "); + print_gimple_stmt (dump_file, stmt, 0, dump_flags); + } + + old_stmt = stmt; + if (!update_call_from_tree (&i, result)) + { + gimplify_and_update_call_from_tree (&i, result); + todoflags |= TODO_update_address_taken; + } + + stmt = gsi_stmt (i); + update_stmt (stmt); + + if (maybe_clean_or_replace_eh_stmt (old_stmt, stmt) + && gimple_purge_dead_eh_edges (bb)) + cfg_changed = true; + + if (dump_file && (dump_flags & TDF_DETAILS)) + { + fprintf (dump_file, "to\n "); + print_gimple_stmt (dump_file, stmt, 0, dump_flags); + fprintf (dump_file, "\n"); + } + + /* Retry the same statement if it changed into another + builtin, there might be new opportunities now. */ + if (gimple_code (stmt) != GIMPLE_CALL) + { + gsi_next (&i); + continue; + } + callee = gimple_call_fndecl (stmt); + if (!callee + || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL + || DECL_FUNCTION_CODE (callee) == fcode) + gsi_next (&i); + } + } + + /* Delete unreachable blocks. */ + if (cfg_changed) + todoflags |= TODO_cleanup_cfg; + + return todoflags; +} + + +namespace { + +const pass_data pass_data_fold_builtins = +{ + GIMPLE_PASS, /* type */ + "fab", /* name */ + OPTGROUP_NONE, /* optinfo_flags */ + false, /* has_gate */ + true, /* has_execute */ + TV_NONE, /* tv_id */ + ( PROP_cfg | PROP_ssa ), /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + ( TODO_verify_ssa | TODO_update_ssa ), /* todo_flags_finish */ +}; + +class pass_fold_builtins : public gimple_opt_pass +{ +public: + pass_fold_builtins (gcc::context *ctxt) + : gimple_opt_pass (pass_data_fold_builtins, ctxt) + {} + + /* opt_pass methods: */ + opt_pass * clone () { return new pass_fold_builtins (m_ctxt); } + unsigned int execute () { return execute_fold_all_builtins (); } + +}; // class pass_fold_builtins + +} // anon namespace + +gimple_opt_pass * +make_pass_fold_builtins (gcc::context *ctxt) +{ + return new pass_fold_builtins (ctxt); +} |