diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/tree-ssa-ccp.c')
-rw-r--r-- | gcc-4.2.1-5666.3/gcc/tree-ssa-ccp.c | 2632 |
1 files changed, 0 insertions, 2632 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/tree-ssa-ccp.c b/gcc-4.2.1-5666.3/gcc/tree-ssa-ccp.c deleted file mode 100644 index 6e74f35f2..000000000 --- a/gcc-4.2.1-5666.3/gcc/tree-ssa-ccp.c +++ /dev/null @@ -1,2632 +0,0 @@ -/* Conditional constant propagation pass for the GNU compiler. - Copyright (C) 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007 - 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 2, 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 COPYING. If not, write to the Free -Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA -02110-1301, USA. */ - -/* 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 -> This is the default starting value. V_i - has not been processed yet. - - 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. - - - Constant propagation in stores and loads (STORE-CCP) - ---------------------------------------------------- - - While CCP has all the logic to propagate constants in GIMPLE - registers, it is missing the ability to associate constants with - stores and loads (i.e., pointer dereferences, structures and - global/aliased variables). We don't keep loads and stores in - SSA, but we do build a factored use-def web for them (in the - virtual operands). - - For instance, consider the following code fragment: - - struct A a; - const int B = 42; - - void foo (int i) - { - if (i > 10) - a.a = 42; - else - { - a.b = 21; - a.a = a.b + 21; - } - - if (a.a != B) - never_executed (); - } - - We should be able to deduce that the predicate 'a.a != B' is always - false. To achieve this, we associate constant values to the SSA - names in the V_MAY_DEF and V_MUST_DEF operands for each store. - Additionally, since we also glob partial loads/stores with the base - symbol, we also keep track of the memory reference where the - constant value was stored (in the MEM_REF field of PROP_VALUE_T). - For instance, - - # a_5 = V_MAY_DEF <a_4> - a.a = 2; - - # VUSE <a_5> - x_3 = a.b; - - In the example above, CCP will associate value '2' with 'a_5', but - it would be wrong to replace the load from 'a.b' with '2', because - '2' had been stored into a.a. - - To support STORE-CCP, it is necessary to add a new value to the - constant propagation lattice. When evaluating a load for a memory - reference we can no longer assume a value of UNDEFINED if we - haven't seen a preceding store to the same memory location. - Consider, for instance global variables: - - int A; - - foo (int i) - { - if (i_3 > 10) - A_4 = 3; - # A_5 = PHI (A_4, A_2); - - # VUSE <A_5> - A.0_6 = A; - - return A.0_6; - } - - The value of A_2 cannot be assumed to be UNDEFINED, as it may have - been defined outside of foo. If we were to assume it UNDEFINED, we - would erroneously optimize the above into 'return 3;'. Therefore, - when doing STORE-CCP, we introduce a fifth lattice value - (UNKNOWN_VAL), which overrides any other value when computing the - meet operation in PHI nodes. - - Though STORE-CCP is not too expensive, it does have to do more work - than regular CCP, so it is only enabled at -O2. Both regular CCP - and STORE-CCP use the exact same algorithm. The only distinction - is that when doing STORE-CCP, the boolean variable DO_STORE_CCP is - set to true. This affects the evaluation of statements and PHI - nodes. - - 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 "flags.h" -#include "rtl.h" -#include "tm_p.h" -#include "ggc.h" -#include "basic-block.h" -#include "output.h" -#include "expr.h" -#include "function.h" -#include "diagnostic.h" -#include "timevar.h" -#include "tree-dump.h" -#include "tree-flow.h" -#include "tree-pass.h" -#include "tree-ssa-propagate.h" -#include "langhooks.h" -#include "target.h" -#include "toplev.h" - - -/* Possible lattice values. */ -typedef enum -{ - UNINITIALIZED = 0, - UNDEFINED, - UNKNOWN_VAL, - CONSTANT, - VARYING -} ccp_lattice_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 V_MAY_DEF or V_MUST_DEF), 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; - -/* True if we are also propagating constants in stores and loads. */ -static bool do_store_ccp; - -/* 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 UNKNOWN_VAL: - fprintf (outf, "%sUNKNOWN_VAL", prefix); - break; - case CONSTANT: - fprintf (outf, "%sCONSTANT ", prefix); - print_generic_expr (outf, val.value, dump_flags); - break; - default: - gcc_unreachable (); - } -} - - -/* Print lattice value VAL to stderr. */ - -void debug_lattice_value (prop_value_t val); - -void -debug_lattice_value (prop_value_t val) -{ - dump_lattice_value (stderr, "", val); - fprintf (stderr, "\n"); -} - - -/* The regular is_gimple_min_invariant does a shallow test of the object. - It assumes that full gimplification has happened, or will happen on the - object. For a value coming from DECL_INITIAL, this is not true, so we - have to be more strict ourselves. */ - -static bool -ccp_decl_initial_min_invariant (tree t) -{ - if (!is_gimple_min_invariant (t)) - return false; - if (TREE_CODE (t) == ADDR_EXPR) - { - /* Inline and unroll is_gimple_addressable. */ - while (1) - { - t = TREE_OPERAND (t, 0); - if (is_gimple_id (t)) - return true; - if (!handled_component_p (t)) - return false; - } - } - return true; -} - - -/* 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- If SSA_NAME_VALUE is set and it is a constant, its value is - used. - - 4- Variables defined by statements other than assignments and PHI - nodes are considered VARYING. - - 5- Variables that are not GIMPLE registers are considered - UNKNOWN_VAL, which is really a stronger version of UNDEFINED. - It's used to avoid the short circuit evaluation implied by - UNDEFINED in ccp_lattice_meet. */ - -static prop_value_t -get_default_value (tree var) -{ - tree sym = SSA_NAME_VAR (var); - prop_value_t val = { UNINITIALIZED, NULL_TREE, NULL_TREE }; - - if (!do_store_ccp && !is_gimple_reg (var)) - { - /* Short circuit for regular CCP. We are not interested in any - non-register when DO_STORE_CCP is false. */ - val.lattice_val = VARYING; - } - else if (SSA_NAME_VALUE (var) - && is_gimple_min_invariant (SSA_NAME_VALUE (var))) - { - val.lattice_val = CONSTANT; - val.value = SSA_NAME_VALUE (var); - } - else if (TREE_STATIC (sym) - && TREE_READONLY (sym) - && !MTAG_P (sym) - && DECL_INITIAL (sym) - && ccp_decl_initial_min_invariant (DECL_INITIAL (sym))) - { - /* Globals and static variables declared 'const' take their - initial value. */ - val.lattice_val = CONSTANT; - val.value = DECL_INITIAL (sym); - val.mem_ref = sym; - } - else - { - tree stmt = SSA_NAME_DEF_STMT (var); - - if (IS_EMPTY_STMT (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. If we are - doing STORE-CCP, function arguments and non-register - variables are initially UNKNOWN_VAL, because we cannot - discard the value incoming from outside of this function - (see ccp_lattice_meet for details). */ - if (is_gimple_reg (sym) && TREE_CODE (sym) != PARM_DECL) - val.lattice_val = UNDEFINED; - else if (do_store_ccp) - val.lattice_val = UNKNOWN_VAL; - else - val.lattice_val = VARYING; - } - else if (TREE_CODE (stmt) == MODIFY_EXPR - || TREE_CODE (stmt) == PHI_NODE) - { - /* Any other variable defined by an assignment or a PHI node - is considered UNDEFINED (or UNKNOWN_VAL if VAR is not a - GIMPLE register). */ - val.lattice_val = is_gimple_reg (sym) ? UNDEFINED : UNKNOWN_VAL; - } - else - { - /* Otherwise, VAR will never take on a constant value. */ - val.lattice_val = VARYING; - } - } - - return val; -} - - -/* Get the constant value associated with variable VAR. If - MAY_USE_DEFAULT_P is true, call get_default_value on variables that - have the lattice value UNINITIALIZED. */ - -static prop_value_t * -get_value (tree var, bool may_use_default_p) -{ - prop_value_t *val = &const_val[SSA_NAME_VERSION (var)]; - if (may_use_default_p && val->lattice_val == UNINITIALIZED) - *val = get_default_value (var); - - return val; -} - - -/* 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) -{ - prop_value_t *old_val = get_value (var, false); - - /* Lattice transitions must always be monotonically increasing in - value. We allow two exceptions: - - 1- If *OLD_VAL and NEW_VAL are the same, return false to - inform the caller that this was a non-transition. - - 2- If we are doing store-ccp (i.e., DOING_STORE_CCP is true), - allow CONSTANT->UNKNOWN_VAL. The UNKNOWN_VAL state is a - special type of UNDEFINED state which prevents the short - circuit evaluation of PHI arguments (see ccp_visit_phi_node - and ccp_lattice_meet). */ - gcc_assert (old_val->lattice_val <= new_val.lattice_val - || (old_val->lattice_val == new_val.lattice_val - && old_val->value == new_val.value - && old_val->mem_ref == new_val.mem_ref) - || (do_store_ccp - && old_val->lattice_val == CONSTANT - && new_val.lattice_val == UNKNOWN_VAL)); - - if (old_val->lattice_val != new_val.lattice_val) - { - if (dump_file && (dump_flags & TDF_DETAILS)) - { - dump_lattice_value (dump_file, "Lattice value changed to ", new_val); - fprintf (dump_file, ". %sdding SSA edges to worklist.\n", - new_val.lattice_val != UNDEFINED ? "A" : "Not a"); - } - - *old_val = new_val; - - /* Transitions UNINITIALIZED -> UNDEFINED are never interesting - for propagation purposes. In these cases return false to - avoid doing useless work. */ - return (new_val.lattice_val != UNDEFINED); - } - - return false; -} - - -/* Return the likely CCP lattice value for STMT. - - If STMT has no operands, then return CONSTANT. - - Else if any operands of STMT are undefined, then return UNDEFINED. - - Else if any operands of STMT are constants, then return CONSTANT. - - Else return VARYING. */ - -static ccp_lattice_t -likely_value (tree stmt) -{ - bool found_constant; - stmt_ann_t ann; - tree use; - ssa_op_iter iter; - - ann = stmt_ann (stmt); - - /* If the statement has volatile operands, it won't fold to a - constant value. */ - if (ann->has_volatile_ops) - return VARYING; - - /* If we are not doing store-ccp, statements with loads - and/or stores will never fold into a constant. */ - if (!do_store_ccp - && !ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS)) - return VARYING; - - - /* A CALL_EXPR is assumed to be varying. NOTE: This may be overly - conservative, in the presence of const and pure calls. */ - if (get_call_expr_in (stmt) != NULL_TREE) - return VARYING; - - /* Anything other than assignments and conditional jumps are not - interesting for CCP. */ - if (TREE_CODE (stmt) != MODIFY_EXPR - && TREE_CODE (stmt) != COND_EXPR - && TREE_CODE (stmt) != SWITCH_EXPR) - return VARYING; - - if (is_gimple_min_invariant (get_rhs (stmt))) - return CONSTANT; - - found_constant = false; - FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE|SSA_OP_VUSE) - { - prop_value_t *val = get_value (use, true); - - if (val->lattice_val == VARYING) - return VARYING; - - if (val->lattice_val == UNKNOWN_VAL) - { - /* UNKNOWN_VAL is invalid when not doing STORE-CCP. */ - gcc_assert (do_store_ccp); - return UNKNOWN_VAL; - } - - if (val->lattice_val == CONSTANT) - found_constant = true; - } - - if (found_constant - || ZERO_SSA_OPERANDS (stmt, SSA_OP_USE) - || ZERO_SSA_OPERANDS (stmt, SSA_OP_VUSE)) - return CONSTANT; - - return UNDEFINED; -} - - -/* Initialize local data structures for CCP. */ - -static void -ccp_initialize (void) -{ - basic_block bb; - - const_val = XNEWVEC (prop_value_t, num_ssa_names); - memset (const_val, 0, num_ssa_names * sizeof (*const_val)); - - /* Initialize simulation flags for PHI nodes and statements. */ - FOR_EACH_BB (bb) - { - block_stmt_iterator i; - - for (i = bsi_start (bb); !bsi_end_p (i); bsi_next (&i)) - { - bool is_varying = false; - tree stmt = bsi_stmt (i); - - if (likely_value (stmt) == 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) - get_value (def, false)->lattice_val = VARYING; - - /* Never mark conditional jumps with DONT_SIMULATE_AGAIN, - otherwise the propagator will never add the outgoing - control edges. */ - if (TREE_CODE (stmt) != COND_EXPR - && TREE_CODE (stmt) != SWITCH_EXPR) - is_varying = true; - } - - DONT_SIMULATE_AGAIN (stmt) = is_varying; - } - } - - /* Now process PHI nodes. */ - FOR_EACH_BB (bb) - { - tree phi; - - for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi)) - { - int i; - tree arg; - prop_value_t *val = get_value (PHI_RESULT (phi), false); - - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - arg = PHI_ARG_DEF (phi, i); - - if (TREE_CODE (arg) == SSA_NAME - && get_value (arg, false)->lattice_val == VARYING) - { - val->lattice_val = VARYING; - break; - } - } - - DONT_SIMULATE_AGAIN (phi) = (val->lattice_val == VARYING); - } - } -} - - -/* Do final substitution of propagated values, cleanup the flowgraph and - free allocated storage. */ - -static void -ccp_finalize (void) -{ - /* Perform substitutions based on the known constant values. */ - substitute_and_fold (const_val, false); - - free (const_val); -} - - -/* Compute the meet operator between *VAL1 and *VAL2. Store the result - in VAL1. - - any M UNDEFINED = any - any M UNKNOWN_VAL = UNKNOWN_VAL - any M VARYING = VARYING - Ci M Cj = Ci if (i == j) - Ci M Cj = VARYING if (i != j) - - Lattice values UNKNOWN_VAL and UNDEFINED are similar but have - different semantics at PHI nodes. Both values imply that we don't - know whether the variable is constant or not. However, UNKNOWN_VAL - values override all others. For instance, suppose that A is a - global variable: - - +------+ - | | - | / \ - | / \ - | | A_1 = 4 - | \ / - | \ / - | A_3 = PHI (A_2, A_1) - | ... = A_3 - | | - +----+ - - If the edge into A_2 is not executable, the first visit to A_3 will - yield the constant 4. But the second visit to A_3 will be with A_2 - in state UNKNOWN_VAL. We can no longer conclude that A_3 is 4 - because A_2 may have been set in another function. If we had used - the lattice value UNDEFINED, we would have had wrongly concluded - that A_3 is 4. */ - - -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 == UNKNOWN_VAL - || val2->lattice_val == UNKNOWN_VAL) - { - /* UNKNOWN_VAL values are invalid if we are not doing STORE-CCP. */ - gcc_assert (do_store_ccp); - - /* any M UNKNOWN_VAL = UNKNOWN_VAL. */ - val1->lattice_val = UNKNOWN_VAL; - val1->value = NULL_TREE; - val1->mem_ref = NULL_TREE; - } - else if (val1->lattice_val == VARYING - || val2->lattice_val == VARYING) - { - /* any M VARYING = VARYING. */ - val1->lattice_val = VARYING; - val1->value = NULL_TREE; - val1->mem_ref = NULL_TREE; - } - else if (val1->lattice_val == CONSTANT - && val2->lattice_val == CONSTANT - && simple_cst_equal (val1->value, val2->value) == 1 - && (!do_store_ccp - || (val1->mem_ref && val2->mem_ref - && operand_equal_p (val1->mem_ref, val2->mem_ref, 0)))) - { - /* Ci M Cj = Ci if (i == j) - Ci M Cj = VARYING if (i != j) - - If these two values come from memory stores, make sure that - they come from the same memory reference. */ - val1->lattice_val = CONSTANT; - val1->value = val1->value; - val1->mem_ref = val1->mem_ref; - } - else - { - /* Any other combination is VARYING. */ - val1->lattice_val = VARYING; - val1->value = NULL_TREE; - val1->mem_ref = 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 (tree phi) -{ - int i; - prop_value_t *old_val, new_val; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "\nVisiting PHI node: "); - print_generic_expr (dump_file, phi, dump_flags); - } - - old_val = get_value (PHI_RESULT (phi), false); - switch (old_val->lattice_val) - { - case VARYING: - return SSA_PROP_VARYING; - - case CONSTANT: - new_val = *old_val; - break; - - case UNKNOWN_VAL: - /* To avoid the default value of UNKNOWN_VAL overriding - that of its possible constant arguments, temporarily - set the PHI node's default lattice value to be - UNDEFINED. If the PHI node's old value was UNKNOWN_VAL and - the new value is UNDEFINED, then we prevent the invalid - transition by not calling set_lattice_value. */ - gcc_assert (do_store_ccp); - - /* FALLTHRU */ - - case UNDEFINED: - case UNINITIALIZED: - new_val.lattice_val = UNDEFINED; - new_val.value = NULL_TREE; - new_val.mem_ref = NULL_TREE; - break; - - default: - gcc_unreachable (); - } - - for (i = 0; i < PHI_NUM_ARGS (phi); i++) - { - /* Compute the meet operator over all the PHI arguments flowing - through executable edges. */ - edge e = 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 = PHI_ARG_DEF (phi, i); - prop_value_t arg_val; - - if (is_gimple_min_invariant (arg)) - { - arg_val.lattice_val = CONSTANT; - arg_val.value = arg; - arg_val.mem_ref = NULL_TREE; - } - else - arg_val = *(get_value (arg, true)); - - 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"); - } - - /* Check for an invalid change from UNKNOWN_VAL to UNDEFINED. */ - if (do_store_ccp - && old_val->lattice_val == UNKNOWN_VAL - && new_val.lattice_val == UNDEFINED) - return SSA_PROP_NOT_INTERESTING; - - /* Otherwise, make the transition to the new value. */ - if (set_lattice_value (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; -} - - -/* 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. */ - -static tree -ccp_fold (tree stmt) -{ - tree rhs = get_rhs (stmt); - enum tree_code code = TREE_CODE (rhs); - enum tree_code_class kind = TREE_CODE_CLASS (code); - tree retval = NULL_TREE; - - if (TREE_CODE (rhs) == SSA_NAME) - { - /* If the RHS is an SSA_NAME, return its known constant value, - if any. */ - return get_value (rhs, true)->value; - } - else if (do_store_ccp && stmt_makes_single_load (stmt)) - { - /* If the RHS is a memory load, see if the VUSEs associated with - it are a valid constant for that memory load. */ - prop_value_t *val = get_value_loaded_by (stmt, const_val); - if (val && val->mem_ref) - { - if (operand_equal_p (val->mem_ref, rhs, 0)) - return val->value; - - /* If RHS is extracting REALPART_EXPR or IMAGPART_EXPR of a - complex type with a known constant value, return it. */ - if ((TREE_CODE (rhs) == REALPART_EXPR - || TREE_CODE (rhs) == IMAGPART_EXPR) - && operand_equal_p (val->mem_ref, TREE_OPERAND (rhs, 0), 0)) - return fold_build1 (TREE_CODE (rhs), TREE_TYPE (rhs), val->value); - } - return NULL_TREE; - } - - /* Unary operators. Note that we know the single operand must - be a constant. So this should almost always return a - simplified RHS. */ - if (kind == tcc_unary) - { - /* Handle unary operators which can appear in GIMPLE form. */ - tree op0 = TREE_OPERAND (rhs, 0); - - /* Simplify the operand down to a constant. */ - if (TREE_CODE (op0) == SSA_NAME) - { - prop_value_t *val = get_value (op0, true); - if (val->lattice_val == CONSTANT) - op0 = get_value (op0, true)->value; - } - - if ((code == NOP_EXPR || code == CONVERT_EXPR) - && tree_ssa_useless_type_conversion_1 (TREE_TYPE (rhs), - TREE_TYPE (op0))) - return op0; - return fold_unary (code, TREE_TYPE (rhs), op0); - } - - /* Binary and comparison operators. We know one or both of the - operands are constants. */ - else if (kind == tcc_binary - || kind == tcc_comparison - || code == TRUTH_AND_EXPR - || code == TRUTH_OR_EXPR - || code == TRUTH_XOR_EXPR) - { - /* Handle binary and comparison operators that can appear in - GIMPLE form. */ - tree op0 = TREE_OPERAND (rhs, 0); - tree op1 = TREE_OPERAND (rhs, 1); - - /* Simplify the operands down to constants when appropriate. */ - if (TREE_CODE (op0) == SSA_NAME) - { - prop_value_t *val = get_value (op0, true); - if (val->lattice_val == CONSTANT) - op0 = val->value; - } - - if (TREE_CODE (op1) == SSA_NAME) - { - prop_value_t *val = get_value (op1, true); - if (val->lattice_val == CONSTANT) - op1 = val->value; - } - - return fold_binary (code, TREE_TYPE (rhs), op0, op1); - } - - /* We may be able to fold away calls to builtin functions if their - arguments are constants. */ - else if (code == CALL_EXPR - && TREE_CODE (TREE_OPERAND (rhs, 0)) == ADDR_EXPR - && (TREE_CODE (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0)) - == FUNCTION_DECL) - && DECL_BUILT_IN (TREE_OPERAND (TREE_OPERAND (rhs, 0), 0))) - { - if (!ZERO_SSA_OPERANDS (stmt, SSA_OP_USE)) - { - tree *orig, var; - tree fndecl, arglist; - size_t i = 0; - ssa_op_iter iter; - use_operand_p var_p; - - /* Preserve the original values of every operand. */ - orig = XNEWVEC (tree, NUM_SSA_OPERANDS (stmt, SSA_OP_USE)); - FOR_EACH_SSA_TREE_OPERAND (var, stmt, iter, SSA_OP_USE) - orig[i++] = var; - - /* Substitute operands with their values and try to fold. */ - replace_uses_in (stmt, NULL, const_val); - fndecl = get_callee_fndecl (rhs); - arglist = TREE_OPERAND (rhs, 1); - retval = fold_builtin (fndecl, arglist, false); - - /* Restore operands to their original form. */ - i = 0; - FOR_EACH_SSA_USE_OPERAND (var_p, stmt, iter, SSA_OP_USE) - SET_USE (var_p, orig[i++]); - free (orig); - } - } - else - return rhs; - - /* If we got a simplified form, see if we need to convert its type. */ - if (retval) - return fold_convert (TREE_TYPE (rhs), retval); - - /* No simplification was possible. */ - return rhs; -} - - -/* Return the tree representing the element referenced by T if T is an - ARRAY_REF or COMPONENT_REF into constant aggregates. Return - NULL_TREE otherwise. */ - -static tree -fold_const_aggregate_ref (tree t) -{ - prop_value_t *value; - tree base, ctor, idx, field; - unsigned HOST_WIDE_INT cnt; - tree cfield, cval; - - switch (TREE_CODE (t)) - { - case ARRAY_REF: - /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its - DECL_INITIAL. If BASE is a nested reference into another - ARRAY_REF or COMPONENT_REF, make a recursive call to resolve - the inner reference. */ - base = TREE_OPERAND (t, 0); - switch (TREE_CODE (base)) - { - case VAR_DECL: - if (!TREE_READONLY (base) - || TREE_CODE (TREE_TYPE (base)) != ARRAY_TYPE - || !targetm.binds_local_p (base)) - return NULL_TREE; - - ctor = DECL_INITIAL (base); - break; - - case ARRAY_REF: - case COMPONENT_REF: - ctor = fold_const_aggregate_ref (base); - break; - - default: - return NULL_TREE; - } - - if (ctor == NULL_TREE - || (TREE_CODE (ctor) != CONSTRUCTOR - && TREE_CODE (ctor) != STRING_CST) - || !TREE_STATIC (ctor)) - return NULL_TREE; - - /* Get the index. If we have an SSA_NAME, try to resolve it - with the current lattice value for the SSA_NAME. */ - idx = TREE_OPERAND (t, 1); - switch (TREE_CODE (idx)) - { - case SSA_NAME: - if ((value = get_value (idx, true)) - && value->lattice_val == CONSTANT - && TREE_CODE (value->value) == INTEGER_CST) - idx = value->value; - else - return NULL_TREE; - break; - - case INTEGER_CST: - break; - - default: - return NULL_TREE; - } - - /* Fold read from constant string. */ - if (TREE_CODE (ctor) == STRING_CST) - { - if ((TYPE_MODE (TREE_TYPE (t)) - == TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) - && (GET_MODE_CLASS (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) - == MODE_INT) - && GET_MODE_SIZE (TYPE_MODE (TREE_TYPE (TREE_TYPE (ctor)))) == 1 - && compare_tree_int (idx, TREE_STRING_LENGTH (ctor)) < 0) - return build_int_cst (TREE_TYPE (t), (TREE_STRING_POINTER (ctor) - [TREE_INT_CST_LOW (idx)])); - return NULL_TREE; - } - - /* Whoo-hoo! I'll fold ya baby. Yeah! */ - FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval) - if (tree_int_cst_equal (cfield, idx)) - return cval; - break; - - case COMPONENT_REF: - /* Get a CONSTRUCTOR. If BASE is a VAR_DECL, get its - DECL_INITIAL. If BASE is a nested reference into another - ARRAY_REF or COMPONENT_REF, make a recursive call to resolve - the inner reference. */ - base = TREE_OPERAND (t, 0); - switch (TREE_CODE (base)) - { - case VAR_DECL: - if (!TREE_READONLY (base) - || TREE_CODE (TREE_TYPE (base)) != RECORD_TYPE - || !targetm.binds_local_p (base)) - return NULL_TREE; - - ctor = DECL_INITIAL (base); - break; - - case ARRAY_REF: - case COMPONENT_REF: - ctor = fold_const_aggregate_ref (base); - break; - - default: - return NULL_TREE; - } - - if (ctor == NULL_TREE - || TREE_CODE (ctor) != CONSTRUCTOR - || !TREE_STATIC (ctor)) - return NULL_TREE; - - field = TREE_OPERAND (t, 1); - - FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (ctor), cnt, cfield, cval) - if (cfield == field - /* FIXME: Handle bit-fields. */ - && ! DECL_BIT_FIELD (cfield)) - return cval; - break; - - case REALPART_EXPR: - case IMAGPART_EXPR: - { - tree c = fold_const_aggregate_ref (TREE_OPERAND (t, 0)); - if (c && TREE_CODE (c) == COMPLEX_CST) - return fold_build1 (TREE_CODE (t), TREE_TYPE (t), c); - break; - } - - default: - break; - } - - return NULL_TREE; -} - -/* Evaluate statement STMT. */ - -static prop_value_t -evaluate_stmt (tree stmt) -{ - prop_value_t val; - tree simplified = NULL_TREE; - ccp_lattice_t likelyvalue = likely_value (stmt); - bool is_constant; - - val.mem_ref = NULL_TREE; - - fold_defer_overflow_warnings (); - - /* If the statement is likely to have a CONSTANT result, then try - to fold the statement to determine the constant value. */ - if (likelyvalue == CONSTANT) - simplified = ccp_fold (stmt); - /* If the statement is likely to have a VARYING result, then do not - bother folding the statement. */ - if (likelyvalue == VARYING) - simplified = get_rhs (stmt); - /* If the statement is an ARRAY_REF or COMPONENT_REF into constant - aggregates, extract the referenced constant. Otherwise the - statement is likely to have an UNDEFINED value, and there will be - nothing to do. Note that fold_const_aggregate_ref returns - NULL_TREE if the first case does not match. */ - else if (!simplified) - simplified = fold_const_aggregate_ref (get_rhs (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; - } - else - { - /* 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 || likelyvalue == UNKNOWN_VAL) - val.lattice_val = likelyvalue; - else - val.lattice_val = VARYING; - - val.value = NULL_TREE; - } - - return val; -} - - -/* 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). */ - -static enum ssa_prop_result -visit_assignment (tree stmt, tree *output_p) -{ - prop_value_t val; - tree lhs, rhs; - enum ssa_prop_result retval; - - lhs = TREE_OPERAND (stmt, 0); - rhs = TREE_OPERAND (stmt, 1); - - if (TREE_CODE (rhs) == SSA_NAME) - { - /* For a simple copy operation, we copy the lattice values. */ - prop_value_t *nval = get_value (rhs, true); - val = *nval; - } - else if (do_store_ccp && stmt_makes_single_load (stmt)) - { - /* Same as above, but the RHS is not a gimple register and yet - has a known VUSE. If STMT is loading from the same memory - location that created the SSA_NAMEs for the virtual operands, - we can propagate the value on the RHS. */ - prop_value_t *nval = get_value_loaded_by (stmt, const_val); - - if (nval && nval->mem_ref - && operand_equal_p (nval->mem_ref, rhs, 0)) - val = *nval; - else - val = evaluate_stmt (stmt); - } - else - /* Evaluate the statement. */ - val = evaluate_stmt (stmt); - - /* If the original LHS was a VIEW_CONVERT_EXPR, modify the constant - value to be a VIEW_CONVERT_EXPR of the old constant value. - - ??? Also, if this was a definition of a bitfield, we need to widen - the constant value into the type of the destination variable. This - should not be necessary if GCC represented bitfields properly. */ - { - tree orig_lhs = TREE_OPERAND (stmt, 0); - - if (TREE_CODE (orig_lhs) == VIEW_CONVERT_EXPR - && val.lattice_val == CONSTANT) - { - tree w = fold_unary (VIEW_CONVERT_EXPR, - TREE_TYPE (TREE_OPERAND (orig_lhs, 0)), - val.value); - - orig_lhs = TREE_OPERAND (orig_lhs, 0); - if (w && is_gimple_min_invariant (w)) - val.value = w; - else - { - val.lattice_val = VARYING; - val.value = NULL; - } - } - - if (val.lattice_val == CONSTANT - && TREE_CODE (orig_lhs) == COMPONENT_REF - && DECL_BIT_FIELD (TREE_OPERAND (orig_lhs, 1))) - { - tree w = widen_bitfield (val.value, TREE_OPERAND (orig_lhs, 1), - orig_lhs); - - if (w && is_gimple_min_invariant (w)) - val.value = w; - else - { - val.lattice_val = VARYING; - val.value = NULL_TREE; - val.mem_ref = NULL_TREE; - } - } - } - - 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; - } - } - else if (do_store_ccp && stmt_makes_single_store (stmt)) - { - /* Otherwise, set the names in V_MAY_DEF/V_MUST_DEF operands - to the new constant value and mark the LHS as the memory - reference associated with VAL. */ - ssa_op_iter i; - tree vdef; - bool changed; - - /* Stores cannot take on an UNDEFINED value. */ - if (val.lattice_val == UNDEFINED) - val.lattice_val = UNKNOWN_VAL; - - /* Mark VAL as stored in the LHS of this assignment. */ - val.mem_ref = lhs; - - /* Set the value of every VDEF to VAL. */ - changed = false; - FOR_EACH_SSA_TREE_OPERAND (vdef, stmt, i, SSA_OP_VIRTUAL_DEFS) - changed |= set_lattice_value (vdef, val); - - /* Note that for propagation purposes, we are only interested in - visiting statements that load the exact same memory reference - stored here. Those statements will have the exact same list - of virtual uses, so it is enough to set the output of this - statement to be its first virtual definition. */ - *output_p = first_vdef (stmt); - if (changed) - { - 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 (tree stmt, edge *taken_edge_p) -{ - prop_value_t val; - basic_block block; - - block = bb_for_stmt (stmt); - val = evaluate_stmt (stmt); - - /* 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 = val.value ? find_taken_edge (block, val.value) : 0; - 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 (tree 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_generic_stmt (dump_file, stmt, dump_flags); - fprintf (dump_file, "\n"); - } - - if (TREE_CODE (stmt) == MODIFY_EXPR) - { - /* 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); - } - else if (TREE_CODE (stmt) == COND_EXPR || TREE_CODE (stmt) == SWITCH_EXPR) - { - /* If STMT is a conditional branch, see if we can determine - which branch will be taken. */ - return visit_cond_stmt (stmt, taken_edge_p); - } - - /* 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, NULL_TREE }; - set_lattice_value (def, v); - } - - return SSA_PROP_VARYING; -} - - -/* Main entry point for SSA Conditional Constant Propagation. */ - -static void -execute_ssa_ccp (bool store_ccp) -{ - do_store_ccp = store_ccp; - ccp_initialize (); - ssa_propagate (ccp_visit_stmt, ccp_visit_phi_node); - ccp_finalize (); -} - - -static unsigned int -do_ssa_ccp (void) -{ - execute_ssa_ccp (false); - return 0; -} - - -static bool -gate_ccp (void) -{ - return flag_tree_ccp != 0; -} - - -struct tree_opt_pass pass_ccp = -{ - "ccp", /* name */ - gate_ccp, /* gate */ - do_ssa_ccp, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_CCP, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ - 0, /* properties_provided */ - PROP_smt_usage, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_cleanup_cfg | TODO_dump_func | TODO_update_ssa - | TODO_ggc_collect | TODO_verify_ssa - | TODO_verify_stmts | TODO_update_smt_usage, /* todo_flags_finish */ - 0 /* letter */ -}; - - -static unsigned int -do_ssa_store_ccp (void) -{ - /* If STORE-CCP is not enabled, we just run regular CCP. */ - execute_ssa_ccp (flag_tree_store_ccp != 0); - return 0; -} - -static bool -gate_store_ccp (void) -{ - /* STORE-CCP is enabled only with -ftree-store-ccp, but when - -fno-tree-store-ccp is specified, we should run regular CCP. - That's why the pass is enabled with either flag. */ - return flag_tree_store_ccp != 0 || flag_tree_ccp != 0; -} - - -struct tree_opt_pass pass_store_ccp = -{ - "store_ccp", /* name */ - gate_store_ccp, /* gate */ - do_ssa_store_ccp, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - TV_TREE_STORE_CCP, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ - 0, /* properties_provided */ - PROP_smt_usage, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_dump_func | TODO_update_ssa - | TODO_ggc_collect | TODO_verify_ssa - | TODO_cleanup_cfg - | TODO_verify_stmts | TODO_update_smt_usage, /* todo_flags_finish */ - 0 /* letter */ -}; - -/* Given a constant value VAL for bitfield FIELD, and a destination - variable VAR, return VAL appropriately widened to fit into VAR. If - FIELD is wider than HOST_WIDE_INT, NULL is returned. */ - -tree -widen_bitfield (tree val, tree field, tree var) -{ - unsigned HOST_WIDE_INT var_size, field_size; - tree wide_val; - unsigned HOST_WIDE_INT mask; - unsigned int i; - - /* We can only do this if the size of the type and field and VAL are - all constants representable in HOST_WIDE_INT. */ - if (!host_integerp (TYPE_SIZE (TREE_TYPE (var)), 1) - || !host_integerp (DECL_SIZE (field), 1) - || !host_integerp (val, 0)) - return NULL_TREE; - - var_size = tree_low_cst (TYPE_SIZE (TREE_TYPE (var)), 1); - field_size = tree_low_cst (DECL_SIZE (field), 1); - - /* Give up if either the bitfield or the variable are too wide. */ - if (field_size > HOST_BITS_PER_WIDE_INT || var_size > HOST_BITS_PER_WIDE_INT) - return NULL_TREE; - - gcc_assert (var_size >= field_size); - - /* If the sign bit of the value is not set or the field's type is unsigned, - just mask off the high order bits of the value. */ - if (DECL_UNSIGNED (field) - || !(tree_low_cst (val, 0) & (((HOST_WIDE_INT)1) << (field_size - 1)))) - { - /* Zero extension. Build a mask with the lower 'field_size' bits - set and a BIT_AND_EXPR node to clear the high order bits of - the value. */ - for (i = 0, mask = 0; i < field_size; i++) - mask |= ((HOST_WIDE_INT) 1) << i; - - wide_val = fold_build2 (BIT_AND_EXPR, TREE_TYPE (var), val, - build_int_cst (TREE_TYPE (var), mask)); - } - else - { - /* Sign extension. Create a mask with the upper 'field_size' - bits set and a BIT_IOR_EXPR to set the high order bits of the - value. */ - for (i = 0, mask = 0; i < (var_size - field_size); i++) - mask |= ((HOST_WIDE_INT) 1) << (var_size - i - 1); - - wide_val = fold_build2 (BIT_IOR_EXPR, TREE_TYPE (var), val, - build_int_cst (TREE_TYPE (var), mask)); - } - - return wide_val; -} - - -/* A subroutine of fold_stmt_r. Attempts to fold *(A+O) to A[X]. - BASE is an array type. OFFSET is a byte displacement. ORIG_TYPE - is the desired result type. */ - -static tree -maybe_fold_offset_to_array_ref (tree base, tree offset, tree orig_type) -{ - tree min_idx, idx, elt_offset = integer_zero_node; - tree array_type, elt_type, elt_size; - - /* If BASE is an ARRAY_REF, we can pick up another offset (this time - measured in units of the size of elements type) from that ARRAY_REF). - We can't do anything if either is variable. - - The case we handle here is *(&A[N]+O). */ - if (TREE_CODE (base) == ARRAY_REF) - { - tree low_bound = array_ref_low_bound (base); - - elt_offset = TREE_OPERAND (base, 1); - if (TREE_CODE (low_bound) != INTEGER_CST - || TREE_CODE (elt_offset) != INTEGER_CST) - return NULL_TREE; - - elt_offset = int_const_binop (MINUS_EXPR, elt_offset, low_bound, 0); - base = TREE_OPERAND (base, 0); - } - - /* Ignore stupid user tricks of indexing non-array variables. */ - array_type = TREE_TYPE (base); - if (TREE_CODE (array_type) != ARRAY_TYPE) - return NULL_TREE; - elt_type = TREE_TYPE (array_type); - if (!lang_hooks.types_compatible_p (orig_type, elt_type)) - return NULL_TREE; - - /* If OFFSET and ELT_OFFSET are zero, we don't care about the size of the - element type (so we can use the alignment if it's not constant). - Otherwise, compute the offset as an index by using a division. If the - division isn't exact, then don't do anything. */ - elt_size = TYPE_SIZE_UNIT (elt_type); - if (integer_zerop (offset)) - { - if (TREE_CODE (elt_size) != INTEGER_CST) - elt_size = size_int (TYPE_ALIGN (elt_type)); - - idx = integer_zero_node; - } - else - { - unsigned HOST_WIDE_INT lquo, lrem; - HOST_WIDE_INT hquo, hrem; - - if (TREE_CODE (elt_size) != INTEGER_CST - || div_and_round_double (TRUNC_DIV_EXPR, 1, - TREE_INT_CST_LOW (offset), - TREE_INT_CST_HIGH (offset), - TREE_INT_CST_LOW (elt_size), - TREE_INT_CST_HIGH (elt_size), - &lquo, &hquo, &lrem, &hrem) - || lrem || hrem) - return NULL_TREE; - - idx = build_int_cst_wide (NULL_TREE, lquo, hquo); - } - - /* Assume the low bound is zero. If there is a domain type, get the - low bound, if any, convert the index into that type, and add the - low bound. */ - min_idx = integer_zero_node; - if (TYPE_DOMAIN (array_type)) - { - if (TYPE_MIN_VALUE (TYPE_DOMAIN (array_type))) - min_idx = TYPE_MIN_VALUE (TYPE_DOMAIN (array_type)); - else - min_idx = fold_convert (TYPE_DOMAIN (array_type), min_idx); - - if (TREE_CODE (min_idx) != INTEGER_CST) - return NULL_TREE; - - idx = fold_convert (TYPE_DOMAIN (array_type), idx); - elt_offset = fold_convert (TYPE_DOMAIN (array_type), elt_offset); - } - - if (!integer_zerop (min_idx)) - idx = int_const_binop (PLUS_EXPR, idx, min_idx, 0); - if (!integer_zerop (elt_offset)) - idx = int_const_binop (PLUS_EXPR, idx, elt_offset, 0); - - return build4 (ARRAY_REF, orig_type, base, idx, min_idx, - size_int (tree_low_cst (elt_size, 1) - / (TYPE_ALIGN_UNIT (elt_type)))); -} - - -/* A subroutine of fold_stmt_r. Attempts to fold *(S+O) to S.X. - BASE is a record type. OFFSET is a byte displacement. ORIG_TYPE - is the desired result type. */ -/* ??? This doesn't handle class inheritance. */ - -static tree -maybe_fold_offset_to_component_ref (tree record_type, tree base, tree offset, - tree orig_type, bool base_is_ptr) -{ - tree f, t, field_type, tail_array_field, field_offset; - - if (TREE_CODE (record_type) != RECORD_TYPE - && TREE_CODE (record_type) != UNION_TYPE - && TREE_CODE (record_type) != QUAL_UNION_TYPE) - return NULL_TREE; - - /* Short-circuit silly cases. */ - if (lang_hooks.types_compatible_p (record_type, orig_type)) - return NULL_TREE; - - tail_array_field = NULL_TREE; - for (f = TYPE_FIELDS (record_type); f ; f = TREE_CHAIN (f)) - { - int cmp; - - if (TREE_CODE (f) != FIELD_DECL) - continue; - if (DECL_BIT_FIELD (f)) - continue; - - field_offset = byte_position (f); - if (TREE_CODE (field_offset) != INTEGER_CST) - continue; - - /* ??? Java creates "interesting" fields for representing base classes. - They have no name, and have no context. With no context, we get into - trouble with nonoverlapping_component_refs_p. Skip them. */ - if (!DECL_FIELD_CONTEXT (f)) - continue; - - /* The previous array field isn't at the end. */ - tail_array_field = NULL_TREE; - - /* Check to see if this offset overlaps with the field. */ - cmp = tree_int_cst_compare (field_offset, offset); - if (cmp > 0) - continue; - - field_type = TREE_TYPE (f); - - /* Here we exactly match the offset being checked. If the types match, - then we can return that field. */ - if (cmp == 0 - && lang_hooks.types_compatible_p (orig_type, field_type)) - { - if (base_is_ptr) - base = build1 (INDIRECT_REF, record_type, base); - t = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE); - return t; - } - - /* Don't care about offsets into the middle of scalars. */ - if (!AGGREGATE_TYPE_P (field_type)) - continue; - - /* Check for array at the end of the struct. This is often - used as for flexible array members. We should be able to - turn this into an array access anyway. */ - if (TREE_CODE (field_type) == ARRAY_TYPE) - tail_array_field = f; - - /* Check the end of the field against the offset. */ - if (!DECL_SIZE_UNIT (f) - || TREE_CODE (DECL_SIZE_UNIT (f)) != INTEGER_CST) - continue; - t = int_const_binop (MINUS_EXPR, offset, field_offset, 1); - if (!tree_int_cst_lt (t, DECL_SIZE_UNIT (f))) - continue; - - /* If we matched, then set offset to the displacement into - this field. */ - offset = t; - goto found; - } - - if (!tail_array_field) - return NULL_TREE; - - f = tail_array_field; - field_type = TREE_TYPE (f); - offset = int_const_binop (MINUS_EXPR, offset, byte_position (f), 1); - - found: - /* If we get here, we've got an aggregate field, and a possibly - nonzero offset into them. Recurse and hope for a valid match. */ - if (base_is_ptr) - base = build1 (INDIRECT_REF, record_type, base); - base = build3 (COMPONENT_REF, field_type, base, f, NULL_TREE); - - t = maybe_fold_offset_to_array_ref (base, offset, orig_type); - if (t) - return t; - return maybe_fold_offset_to_component_ref (field_type, base, offset, - orig_type, false); -} - - -/* A subroutine of fold_stmt_r. Attempt to simplify *(BASE+OFFSET). - Return the simplified expression, or NULL if nothing could be done. */ - -static tree -maybe_fold_stmt_indirect (tree expr, tree base, tree offset) -{ - tree t; - - /* We may well have constructed a double-nested PLUS_EXPR via multiple - substitutions. Fold that down to one. Remove NON_LVALUE_EXPRs that - are sometimes added. */ - base = fold (base); - STRIP_TYPE_NOPS (base); - TREE_OPERAND (expr, 0) = base; - - /* One possibility is that the address reduces to a string constant. */ - t = fold_read_from_constant_string (expr); - if (t) - return t; - - /* Add in any offset from a PLUS_EXPR. */ - if (TREE_CODE (base) == PLUS_EXPR) - { - tree offset2; - - offset2 = TREE_OPERAND (base, 1); - if (TREE_CODE (offset2) != INTEGER_CST) - return NULL_TREE; - base = TREE_OPERAND (base, 0); - - offset = int_const_binop (PLUS_EXPR, offset, offset2, 1); - } - - if (TREE_CODE (base) == ADDR_EXPR) - { - /* Strip the ADDR_EXPR. */ - base = TREE_OPERAND (base, 0); - - /* Fold away CONST_DECL to its value, if the type is scalar. */ - if (TREE_CODE (base) == CONST_DECL - && ccp_decl_initial_min_invariant (DECL_INITIAL (base))) - return DECL_INITIAL (base); - - /* Try folding *(&B+O) to B[X]. */ - t = maybe_fold_offset_to_array_ref (base, offset, TREE_TYPE (expr)); - if (t) - return t; - - /* Try folding *(&B+O) to B.X. */ - t = maybe_fold_offset_to_component_ref (TREE_TYPE (base), base, offset, - TREE_TYPE (expr), false); - if (t) - return t; - - /* Fold *&B to B. We can only do this if EXPR is the same type - as BASE. We can't do this if EXPR is the element type of an array - and BASE is the array. */ - if (integer_zerop (offset) - && lang_hooks.types_compatible_p (TREE_TYPE (base), - TREE_TYPE (expr))) - return base; - } - else - { - /* We can get here for out-of-range string constant accesses, - such as "_"[3]. Bail out of the entire substitution search - and arrange for the entire statement to be replaced by a - call to __builtin_trap. In all likelihood this will all be - constant-folded away, but in the meantime we can't leave with - something that get_expr_operands can't understand. */ - - t = base; - STRIP_NOPS (t); - if (TREE_CODE (t) == ADDR_EXPR - && TREE_CODE (TREE_OPERAND (t, 0)) == STRING_CST) - { - /* FIXME: Except that this causes problems elsewhere with dead - code not being deleted, and we die in the rtl expanders - because we failed to remove some ssa_name. In the meantime, - just return zero. */ - /* FIXME2: This condition should be signaled by - fold_read_from_constant_string directly, rather than - re-checking for it here. */ - return integer_zero_node; - } - - /* Try folding *(B+O) to B->X. Still an improvement. */ - if (POINTER_TYPE_P (TREE_TYPE (base))) - { - t = maybe_fold_offset_to_component_ref (TREE_TYPE (TREE_TYPE (base)), - base, offset, - TREE_TYPE (expr), true); - if (t) - return t; - } - } - - /* Otherwise we had an offset that we could not simplify. */ - return NULL_TREE; -} - - -/* A subroutine of fold_stmt_r. EXPR is a PLUS_EXPR. - - A quaint feature extant in our address arithmetic is that there - can be hidden type changes here. The type of the result need - not be the same as the type of the input pointer. - - What we're after here is an expression of the form - (T *)(&array + const) - where the cast doesn't actually exist, but is implicit in the - type of the PLUS_EXPR. We'd like to turn this into - &array[x] - which may be able to propagate further. */ - -static tree -maybe_fold_stmt_addition (tree expr) -{ - tree op0 = TREE_OPERAND (expr, 0); - tree op1 = TREE_OPERAND (expr, 1); - tree ptr_type = TREE_TYPE (expr); - tree ptd_type; - tree t; - bool subtract = (TREE_CODE (expr) == MINUS_EXPR); - - /* We're only interested in pointer arithmetic. */ - if (!POINTER_TYPE_P (ptr_type)) - return NULL_TREE; - /* Canonicalize the integral operand to op1. */ - if (INTEGRAL_TYPE_P (TREE_TYPE (op0))) - { - if (subtract) - return NULL_TREE; - t = op0, op0 = op1, op1 = t; - } - /* It had better be a constant. */ - if (TREE_CODE (op1) != INTEGER_CST) - return NULL_TREE; - /* The first operand should be an ADDR_EXPR. */ - if (TREE_CODE (op0) != ADDR_EXPR) - return NULL_TREE; - op0 = TREE_OPERAND (op0, 0); - - /* If the first operand is an ARRAY_REF, expand it so that we can fold - the offset into it. */ - while (TREE_CODE (op0) == ARRAY_REF) - { - tree array_obj = TREE_OPERAND (op0, 0); - tree array_idx = TREE_OPERAND (op0, 1); - tree elt_type = TREE_TYPE (op0); - tree elt_size = TYPE_SIZE_UNIT (elt_type); - tree min_idx; - - if (TREE_CODE (array_idx) != INTEGER_CST) - break; - if (TREE_CODE (elt_size) != INTEGER_CST) - break; - - /* Un-bias the index by the min index of the array type. */ - min_idx = TYPE_DOMAIN (TREE_TYPE (array_obj)); - if (min_idx) - { - min_idx = TYPE_MIN_VALUE (min_idx); - if (min_idx) - { - if (TREE_CODE (min_idx) != INTEGER_CST) - break; - - array_idx = fold_convert (TREE_TYPE (min_idx), array_idx); - if (!integer_zerop (min_idx)) - array_idx = int_const_binop (MINUS_EXPR, array_idx, - min_idx, 0); - } - } - - /* Convert the index to a byte offset. */ - array_idx = fold_convert (sizetype, array_idx); - array_idx = int_const_binop (MULT_EXPR, array_idx, elt_size, 0); - - /* Update the operands for the next round, or for folding. */ - /* If we're manipulating unsigned types, then folding into negative - values can produce incorrect results. Particularly if the type - is smaller than the width of the pointer. */ - if (subtract - && TYPE_UNSIGNED (TREE_TYPE (op1)) - && tree_int_cst_lt (array_idx, op1)) - return NULL; - op1 = int_const_binop (subtract ? MINUS_EXPR : PLUS_EXPR, - array_idx, op1, 0); - subtract = false; - op0 = array_obj; - } - - /* If we weren't able to fold the subtraction into another array reference, - canonicalize the integer for passing to the array and component ref - simplification functions. */ - if (subtract) - { - if (TYPE_UNSIGNED (TREE_TYPE (op1))) - return NULL; - op1 = fold_unary (NEGATE_EXPR, TREE_TYPE (op1), op1); - /* ??? In theory fold should always produce another integer. */ - if (op1 == NULL || TREE_CODE (op1) != INTEGER_CST) - return NULL; - } - - ptd_type = TREE_TYPE (ptr_type); - - /* At which point we can try some of the same things as for indirects. */ - t = maybe_fold_offset_to_array_ref (op0, op1, ptd_type); - if (!t) - t = maybe_fold_offset_to_component_ref (TREE_TYPE (op0), op0, op1, - ptd_type, false); - if (t) - t = build1 (ADDR_EXPR, ptr_type, t); - - return t; -} - -/* For passing state through walk_tree into fold_stmt_r and its - children. */ - -struct fold_stmt_r_data -{ - tree stmt; - bool *changed_p; - bool *inside_addr_expr_p; -}; - -/* Subroutine of fold_stmt called via walk_tree. We perform several - simplifications of EXPR_P, mostly having to do with pointer arithmetic. */ - -static tree -fold_stmt_r (tree *expr_p, int *walk_subtrees, void *data) -{ - struct fold_stmt_r_data *fold_stmt_r_data = (struct fold_stmt_r_data *) data; - bool *inside_addr_expr_p = fold_stmt_r_data->inside_addr_expr_p; - bool *changed_p = fold_stmt_r_data->changed_p; - tree expr = *expr_p, t; - - /* ??? It'd be nice if walk_tree had a pre-order option. */ - switch (TREE_CODE (expr)) - { - case INDIRECT_REF: - t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); - if (t) - return t; - *walk_subtrees = 0; - - t = maybe_fold_stmt_indirect (expr, TREE_OPERAND (expr, 0), - integer_zero_node); - break; - - /* ??? Could handle more ARRAY_REFs here, as a variant of INDIRECT_REF. - We'd only want to bother decomposing an existing ARRAY_REF if - the base array is found to have another offset contained within. - Otherwise we'd be wasting time. */ - case ARRAY_REF: - /* If we are not processing expressions found within an - ADDR_EXPR, then we can fold constant array references. */ - if (!*inside_addr_expr_p) - t = fold_read_from_constant_string (expr); - else - t = NULL; - break; - - case ADDR_EXPR: - *inside_addr_expr_p = true; - t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); - *inside_addr_expr_p = false; - if (t) - return t; - *walk_subtrees = 0; - - /* Set TREE_INVARIANT properly so that the value is properly - considered constant, and so gets propagated as expected. */ - if (*changed_p) - recompute_tree_invariant_for_addr_expr (expr); - return NULL_TREE; - - case PLUS_EXPR: - case MINUS_EXPR: - t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); - if (t) - return t; - t = walk_tree (&TREE_OPERAND (expr, 1), fold_stmt_r, data, NULL); - if (t) - return t; - *walk_subtrees = 0; - - t = maybe_fold_stmt_addition (expr); - break; - - case COMPONENT_REF: - t = walk_tree (&TREE_OPERAND (expr, 0), fold_stmt_r, data, NULL); - if (t) - return t; - *walk_subtrees = 0; - - /* Make sure the FIELD_DECL is actually a field in the type on the lhs. - We've already checked that the records are compatible, so we should - come up with a set of compatible fields. */ - { - tree expr_record = TREE_TYPE (TREE_OPERAND (expr, 0)); - tree expr_field = TREE_OPERAND (expr, 1); - - if (DECL_FIELD_CONTEXT (expr_field) != TYPE_MAIN_VARIANT (expr_record)) - { - expr_field = find_compatible_field (expr_record, expr_field); - TREE_OPERAND (expr, 1) = expr_field; - } - } - break; - - case TARGET_MEM_REF: - t = maybe_fold_tmr (expr); - break; - - case COND_EXPR: - if (COMPARISON_CLASS_P (TREE_OPERAND (expr, 0))) - { - tree op0 = TREE_OPERAND (expr, 0); - tree tem; - bool set; - - fold_defer_overflow_warnings (); - tem = fold_binary (TREE_CODE (op0), TREE_TYPE (op0), - TREE_OPERAND (op0, 0), - TREE_OPERAND (op0, 1)); - set = tem && is_gimple_condexpr (tem); - fold_undefer_overflow_warnings (set, fold_stmt_r_data->stmt, 0); - if (set) - TREE_OPERAND (expr, 0) = tem; - t = expr; - break; - } - - default: - return NULL_TREE; - } - - if (t) - { - *expr_p = t; - *changed_p = true; - } - - return NULL_TREE; -} - - -/* Return the string length, maximum string length or maximum value of - ARG in LENGTH. - If ARG is an SSA name variable, follow its use-def chains. If LENGTH - is not NULL and, for TYPE == 0, its value is not equal to the length - we determine or if we are unable to determine the length or value, - return false. VISITED is a bitmap of visited variables. - TYPE is 0 if string length should be returned, 1 for maximum string - length and 2 for maximum value ARG can have. */ - -static bool -get_maxval_strlen (tree arg, tree *length, bitmap visited, int type) -{ - tree var, def_stmt, val; - - if (TREE_CODE (arg) != SSA_NAME) - { - if (type == 2) - { - val = arg; - if (TREE_CODE (val) != INTEGER_CST - || tree_int_cst_sgn (val) < 0) - return false; - } - else - val = c_strlen (arg, 1); - if (!val) - return false; - - if (*length) - { - if (type > 0) - { - if (TREE_CODE (*length) != INTEGER_CST - || TREE_CODE (val) != INTEGER_CST) - return false; - - if (tree_int_cst_lt (*length, val)) - *length = val; - return true; - } - else if (simple_cst_equal (val, *length) != 1) - return false; - } - - *length = val; - return true; - } - - /* If we were already here, break the infinite cycle. */ - if (bitmap_bit_p (visited, SSA_NAME_VERSION (arg))) - return true; - bitmap_set_bit (visited, SSA_NAME_VERSION (arg)); - - var = arg; - def_stmt = SSA_NAME_DEF_STMT (var); - - switch (TREE_CODE (def_stmt)) - { - case MODIFY_EXPR: - { - tree rhs; - - /* The RHS of the statement defining VAR must either have a - constant length or come from another SSA_NAME with a constant - length. */ - rhs = TREE_OPERAND (def_stmt, 1); - STRIP_NOPS (rhs); - return get_maxval_strlen (rhs, length, visited, type); - } - - case PHI_NODE: - { - /* All the arguments of the PHI node must have the same constant - length. */ - int i; - - for (i = 0; i < PHI_NUM_ARGS (def_stmt); i++) - { - tree arg = PHI_ARG_DEF (def_stmt, i); - - /* If this PHI has itself as an argument, we cannot - determine the string length of this argument. However, - if we can find a constant string length for the other - PHI args then we can still be sure that this is a - constant string length. So be optimistic and just - continue with the next argument. */ - if (arg == PHI_RESULT (def_stmt)) - continue; - - if (!get_maxval_strlen (arg, length, visited, type)) - return false; - } - - return true; - } - - default: - break; - } - - - return false; -} - - -/* Fold builtin call FN in statement STMT. If it cannot be folded into a - constant, return NULL_TREE. Otherwise, return its constant value. */ - -static tree -ccp_fold_builtin (tree stmt, tree fn) -{ - tree result, val[3]; - tree callee, arglist, a; - int arg_mask, i, type; - bitmap visited; - bool ignore; - - ignore = TREE_CODE (stmt) != MODIFY_EXPR; - - /* First try the generic builtin folder. If that succeeds, return the - result directly. */ - callee = get_callee_fndecl (fn); - arglist = TREE_OPERAND (fn, 1); - result = fold_builtin (callee, arglist, ignore); - if (result) - { - if (ignore) - STRIP_NOPS (result); - return result; - } - - /* Ignore MD builtins. */ - if (DECL_BUILT_IN_CLASS (callee) == BUILT_IN_MD) - return NULL_TREE; - - /* If the builtin could not be folded, and it has no argument list, - we're done. */ - if (!arglist) - return NULL_TREE; - - /* Limit the work only for builtins we know how to simplify. */ - switch (DECL_FUNCTION_CODE (callee)) - { - case BUILT_IN_STRLEN: - case BUILT_IN_FPUTS: - case BUILT_IN_FPUTS_UNLOCKED: - arg_mask = 1; - type = 0; - break; - case BUILT_IN_STRCPY: - case BUILT_IN_STRNCPY: - arg_mask = 2; - type = 0; - break; - case BUILT_IN_MEMCPY_CHK: - case BUILT_IN_MEMPCPY_CHK: - case BUILT_IN_MEMMOVE_CHK: - case BUILT_IN_MEMSET_CHK: - case BUILT_IN_STRNCPY_CHK: - arg_mask = 4; - type = 2; - break; - case BUILT_IN_STRCPY_CHK: - case BUILT_IN_STPCPY_CHK: - arg_mask = 2; - type = 1; - break; - case BUILT_IN_SNPRINTF_CHK: - case BUILT_IN_VSNPRINTF_CHK: - arg_mask = 2; - type = 2; - break; - default: - return NULL_TREE; - } - - /* Try to use the dataflow information gathered by the CCP process. */ - visited = BITMAP_ALLOC (NULL); - - memset (val, 0, sizeof (val)); - for (i = 0, a = arglist; - arg_mask; - i++, arg_mask >>= 1, a = TREE_CHAIN (a)) - if (arg_mask & 1) - { - bitmap_clear (visited); - if (!get_maxval_strlen (TREE_VALUE (a), &val[i], visited, type)) - val[i] = NULL_TREE; - } - - BITMAP_FREE (visited); - - result = NULL_TREE; - switch (DECL_FUNCTION_CODE (callee)) - { - case BUILT_IN_STRLEN: - if (val[0]) - { - tree new = fold_convert (TREE_TYPE (fn), val[0]); - - /* If the result is not a valid gimple value, or not a cast - of a valid gimple value, then we can not use the result. */ - if (is_gimple_val (new) - || (is_gimple_cast (new) - && is_gimple_val (TREE_OPERAND (new, 0)))) - return new; - } - break; - - case BUILT_IN_STRCPY: - if (val[1] && is_gimple_val (val[1])) - result = fold_builtin_strcpy (callee, arglist, val[1]); - break; - - case BUILT_IN_STRNCPY: - if (val[1] && is_gimple_val (val[1])) - result = fold_builtin_strncpy (callee, arglist, val[1]); - break; - - case BUILT_IN_FPUTS: - result = fold_builtin_fputs (arglist, - TREE_CODE (stmt) != MODIFY_EXPR, 0, - val[0]); - break; - - case BUILT_IN_FPUTS_UNLOCKED: - result = fold_builtin_fputs (arglist, - TREE_CODE (stmt) != MODIFY_EXPR, 1, - val[0]); - break; - - case BUILT_IN_MEMCPY_CHK: - case BUILT_IN_MEMPCPY_CHK: - case BUILT_IN_MEMMOVE_CHK: - case BUILT_IN_MEMSET_CHK: - if (val[2] && is_gimple_val (val[2])) - result = fold_builtin_memory_chk (callee, arglist, val[2], ignore, - DECL_FUNCTION_CODE (callee)); - break; - - case BUILT_IN_STRCPY_CHK: - case BUILT_IN_STPCPY_CHK: - if (val[1] && is_gimple_val (val[1])) - result = fold_builtin_stxcpy_chk (callee, arglist, val[1], ignore, - DECL_FUNCTION_CODE (callee)); - break; - - case BUILT_IN_STRNCPY_CHK: - if (val[2] && is_gimple_val (val[2])) - result = fold_builtin_strncpy_chk (arglist, val[2]); - break; - - case BUILT_IN_SNPRINTF_CHK: - case BUILT_IN_VSNPRINTF_CHK: - if (val[1] && is_gimple_val (val[1])) - result = fold_builtin_snprintf_chk (arglist, val[1], - DECL_FUNCTION_CODE (callee)); - break; - - default: - gcc_unreachable (); - } - - if (result && ignore) - result = fold_ignored_result (result); - return result; -} - - -/* Fold the statement pointed to by STMT_P. In some cases, this function may - replace the whole statement with a new one. Returns true iff folding - makes any changes. */ - -bool -fold_stmt (tree *stmt_p) -{ - tree rhs, result, stmt; - struct fold_stmt_r_data fold_stmt_r_data; - bool changed = false; - bool inside_addr_expr = false; - - stmt = *stmt_p; - - fold_stmt_r_data.stmt = stmt; - fold_stmt_r_data.changed_p = &changed; - fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr; - - /* If we replaced constants and the statement makes pointer dereferences, - then we may need to fold instances of *&VAR into VAR, etc. */ - if (walk_tree (stmt_p, fold_stmt_r, &fold_stmt_r_data, NULL)) - { - *stmt_p - = build_function_call_expr (implicit_built_in_decls[BUILT_IN_TRAP], - NULL); - return true; - } - - rhs = get_rhs (stmt); - if (!rhs) - return changed; - result = NULL_TREE; - - if (TREE_CODE (rhs) == CALL_EXPR) - { - tree callee; - - /* Check for builtins that CCP can handle using information not - available in the generic fold routines. */ - callee = get_callee_fndecl (rhs); - if (callee && DECL_BUILT_IN (callee)) - result = ccp_fold_builtin (stmt, rhs); - else - { - /* Check for resolvable OBJ_TYPE_REF. The only sorts we can resolve - here are when we've propagated the address of a decl into the - object slot. */ - /* ??? Should perhaps do this in fold proper. However, doing it - there requires that we create a new CALL_EXPR, and that requires - copying EH region info to the new node. Easier to just do it - here where we can just smash the call operand. Also - CALL_EXPR_RETURN_SLOT_OPT needs to be handled correctly and - copied, fold_ternary does not have not information. */ - callee = TREE_OPERAND (rhs, 0); - if (TREE_CODE (callee) == OBJ_TYPE_REF - && lang_hooks.fold_obj_type_ref - && TREE_CODE (OBJ_TYPE_REF_OBJECT (callee)) == ADDR_EXPR - && DECL_P (TREE_OPERAND - (OBJ_TYPE_REF_OBJECT (callee), 0))) - { - tree t; - - /* ??? Caution: Broken ADDR_EXPR semantics means that - looking at the type of the operand of the addr_expr - can yield an array type. See silly exception in - check_pointer_types_r. */ - - t = TREE_TYPE (TREE_TYPE (OBJ_TYPE_REF_OBJECT (callee))); - t = lang_hooks.fold_obj_type_ref (callee, t); - if (t) - { - TREE_OPERAND (rhs, 0) = t; - changed = true; - } - } - } - } - - /* If we couldn't fold the RHS, hand over to the generic fold routines. */ - if (result == NULL_TREE) - result = fold (rhs); - - /* Strip away useless type conversions. Both the NON_LVALUE_EXPR that - may have been added by fold, and "useless" type conversions that might - now be apparent due to propagation. */ - STRIP_USELESS_TYPE_CONVERSION (result); - - if (result != rhs) - changed |= set_rhs (stmt_p, result); - - return changed; -} - -/* Perform the minimal folding on statement STMT. Only operations like - *&x created by constant propagation are handled. The statement cannot - be replaced with a new one. */ - -bool -fold_stmt_inplace (tree stmt) -{ - tree old_stmt = stmt, rhs, new_rhs; - struct fold_stmt_r_data fold_stmt_r_data; - bool changed = false; - bool inside_addr_expr = false; - - fold_stmt_r_data.stmt = stmt; - fold_stmt_r_data.changed_p = &changed; - fold_stmt_r_data.inside_addr_expr_p = &inside_addr_expr; - - walk_tree (&stmt, fold_stmt_r, &fold_stmt_r_data, NULL); - gcc_assert (stmt == old_stmt); - - rhs = get_rhs (stmt); - if (!rhs || rhs == stmt) - return changed; - - new_rhs = fold (rhs); - STRIP_USELESS_TYPE_CONVERSION (new_rhs); - if (new_rhs == rhs) - return changed; - - changed |= set_rhs (&stmt, new_rhs); - gcc_assert (stmt == old_stmt); - - return changed; -} - -/* Convert EXPR into a GIMPLE value suitable for substitution on the - RHS of an assignment. Insert the necessary statements before - iterator *SI_P. */ - -static tree -convert_to_gimple_builtin (block_stmt_iterator *si_p, tree expr) -{ - tree_stmt_iterator ti; - tree stmt = bsi_stmt (*si_p); - tree tmp, stmts = NULL; - - push_gimplify_context (); - tmp = get_initialized_tmp_var (expr, &stmts, NULL); - pop_gimplify_context (NULL); - - if (EXPR_HAS_LOCATION (stmt)) - annotate_all_with_locus (&stmts, EXPR_LOCATION (stmt)); - - /* The replacement can expose previously unreferenced variables. */ - for (ti = tsi_start (stmts); !tsi_end_p (ti); tsi_next (&ti)) - { - tree new_stmt = tsi_stmt (ti); - find_new_referenced_vars (tsi_stmt_ptr (ti)); - bsi_insert_before (si_p, new_stmt, BSI_NEW_STMT); - mark_new_vars_to_rename (bsi_stmt (*si_p)); - bsi_next (si_p); - } - - return tmp; -} - - -/* 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; - FOR_EACH_BB (bb) - { - block_stmt_iterator i; - for (i = bsi_start (bb); !bsi_end_p (i); ) - { - tree *stmtp = bsi_stmt_ptr (i); - tree old_stmt = *stmtp; - tree call = get_rhs (*stmtp); - tree callee, result; - enum built_in_function fcode; - - if (!call || TREE_CODE (call) != CALL_EXPR) - { - bsi_next (&i); - continue; - } - callee = get_callee_fndecl (call); - if (!callee || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL) - { - bsi_next (&i); - continue; - } - fcode = DECL_FUNCTION_CODE (callee); - - result = ccp_fold_builtin (*stmtp, call); - 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; - - default: - bsi_next (&i); - continue; - } - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "Simplified\n "); - print_generic_stmt (dump_file, *stmtp, dump_flags); - } - - if (!set_rhs (stmtp, result)) - { - result = convert_to_gimple_builtin (&i, result); - if (result) - { - bool ok = set_rhs (stmtp, result); - - gcc_assert (ok); - } - } - mark_new_vars_to_rename (*stmtp); - if (maybe_clean_or_replace_eh_stmt (old_stmt, *stmtp) - && tree_purge_dead_eh_edges (bb)) - cfg_changed = true; - - if (dump_file && (dump_flags & TDF_DETAILS)) - { - fprintf (dump_file, "to\n "); - print_generic_stmt (dump_file, *stmtp, dump_flags); - fprintf (dump_file, "\n"); - } - - /* Retry the same statement if it changed into another - builtin, there might be new opportunities now. */ - call = get_rhs (*stmtp); - if (!call || TREE_CODE (call) != CALL_EXPR) - { - bsi_next (&i); - continue; - } - callee = get_callee_fndecl (call); - if (!callee - || DECL_BUILT_IN_CLASS (callee) != BUILT_IN_NORMAL - || DECL_FUNCTION_CODE (callee) == fcode) - bsi_next (&i); - } - } - - /* Delete unreachable blocks. */ - if (cfg_changed) - cleanup_tree_cfg (); - return 0; -} - - -struct tree_opt_pass pass_fold_builtins = -{ - "fab", /* name */ - NULL, /* gate */ - execute_fold_all_builtins, /* execute */ - NULL, /* sub */ - NULL, /* next */ - 0, /* static_pass_number */ - 0, /* tv_id */ - PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ - 0, /* properties_provided */ - 0, /* properties_destroyed */ - 0, /* todo_flags_start */ - TODO_dump_func - | TODO_verify_ssa - | TODO_update_ssa, /* todo_flags_finish */ - 0 /* letter */ -}; |