diff options
Diffstat (limited to 'gcc-4.2.1-5666.3/gcc/ipa-pure-const.c')
| -rw-r--r-- | gcc-4.2.1-5666.3/gcc/ipa-pure-const.c | 754 |
1 files changed, 754 insertions, 0 deletions
diff --git a/gcc-4.2.1-5666.3/gcc/ipa-pure-const.c b/gcc-4.2.1-5666.3/gcc/ipa-pure-const.c new file mode 100644 index 000000000..fdaff50d5 --- /dev/null +++ b/gcc-4.2.1-5666.3/gcc/ipa-pure-const.c @@ -0,0 +1,754 @@ +/* Callgraph based analysis of static variables. + Copyright (C) 2004, 2005 Free Software Foundation, Inc. + Contributed by Kenneth Zadeck <zadeck@naturalbridge.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. */ + +/* This file mark functions as being either const (TREE_READONLY) or + pure (DECL_IS_PURE). + + This must be run after inlining decisions have been made since + otherwise, the local sets will not contain information that is + consistent with post inlined state. The global sets are not prone + to this problem since they are by definition transitive. */ + +/* The code in this module is called by the ipa pass manager. It + should be one of the later passes since it's information is used by + the rest of the compilation. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "tree-flow.h" +#include "tree-inline.h" +#include "tree-pass.h" +#include "langhooks.h" +#include "pointer-set.h" +#include "ggc.h" +#include "ipa-utils.h" +#include "c-common.h" +#include "tree-gimple.h" +#include "cgraph.h" +#include "output.h" +#include "flags.h" +#include "timevar.h" +#include "diagnostic.h" +#include "langhooks.h" +#include "target.h" + +static struct pointer_set_t *visited_nodes; + +/* Lattice values for const and pure functions. Everything starts out + being const, then may drop to pure and then neither depending on + what is found. */ +enum pure_const_state_e +{ + IPA_CONST, + IPA_PURE, + IPA_NEITHER +}; + +/* Holder inserted into the ipa_dfs_info aux field to hold the + const_state. */ +struct funct_state_d +{ + enum pure_const_state_e pure_const_state; + bool state_set_in_source; +}; + +typedef struct funct_state_d * funct_state; + +/* Return the function state from NODE. */ + +static inline funct_state +get_function_state (struct cgraph_node *node) +{ + struct ipa_dfs_info * info = node->aux; + return info->aux; +} + +/* Check to see if the use (or definition when CHECHING_WRITE is true) + variable T is legal in a function that is either pure or const. */ + +static inline void +check_decl (funct_state local, + tree t, bool checking_write) +{ + /* If the variable has the "used" attribute, treat it as if it had a + been touched by the devil. */ + if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) + { + local->pure_const_state = IPA_NEITHER; + return; + } + + /* Do not want to do anything with volatile except mark any + function that uses one to be not const or pure. */ + if (TREE_THIS_VOLATILE (t)) + { + local->pure_const_state = IPA_NEITHER; + return; + } + + /* Do not care about a local automatic that is not static. */ + if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) + return; + + /* Since we have dealt with the locals and params cases above, if we + are CHECKING_WRITE, this cannot be a pure or constant + function. */ + if (checking_write) + local->pure_const_state = IPA_NEITHER; + + if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) + { + /* If the front end set the variable to be READONLY and + constant, we can allow this variable in pure or const + functions but the scope is too large for our analysis to set + these bits ourselves. */ + + if (TREE_READONLY (t) + && DECL_INITIAL (t) + && is_gimple_min_invariant (DECL_INITIAL (t))) + ; /* Read of a constant, do not change the function state. */ + else + { + /* Just a regular read. */ + if (local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; + } + } + + /* Compilation level statics can be read if they are readonly + variables. */ + if (TREE_READONLY (t)) + return; + + /* Just a regular read. */ + if (local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; +} + +/* If T is a VAR_DECL check to see if it is an allowed reference. */ + +static void +check_operand (funct_state local, + tree t, bool checking_write) +{ + if (!t) return; + + if (TREE_CODE (t) == VAR_DECL) + check_decl (local, t, checking_write); +} + +/* Examine tree T for references. */ + +static void +check_tree (funct_state local, tree t, bool checking_write) +{ + if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) + return; + + /* Any tree which is volatile disqualifies thie function from being + const or pure. */ + if (TREE_THIS_VOLATILE (t)) + { + local->pure_const_state = IPA_NEITHER; + return; + } + + while (TREE_CODE (t) == REALPART_EXPR + || TREE_CODE (t) == IMAGPART_EXPR + || handled_component_p (t)) + { + if (TREE_CODE (t) == ARRAY_REF) + check_operand (local, TREE_OPERAND (t, 1), false); + t = TREE_OPERAND (t, 0); + } + + /* The bottom of an indirect reference can only be read, not + written. */ + if (INDIRECT_REF_P (t)) + { + check_tree (local, TREE_OPERAND (t, 0), false); + + /* Any indirect reference that occurs on the lhs + disqualifies the function from being pure or const. Any + indirect reference that occurs on the rhs disqualifies the + function from being const. */ + if (checking_write) + { + local->pure_const_state = IPA_NEITHER; + return; + } + else if (local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; + } + + if (SSA_VAR_P (t)) + check_operand (local, t, checking_write); +} + +/* Scan tree T to see if there are any addresses taken in within T. */ + +static void +look_for_address_of (funct_state local, tree t) +{ + if (TREE_CODE (t) == ADDR_EXPR) + { + tree x = get_base_var (t); + if (TREE_CODE (x) == VAR_DECL) + { + check_decl (local, x, false); + + /* Taking the address of something appears to be reasonable + in PURE code. Not allowed in const. */ + if (local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; + } + } +} + +/* Check to see if T is a read or address of operation on a var we are + interested in analyzing. LOCAL is passed in to get access to its + bit vectors. */ + +static void +check_rhs_var (funct_state local, tree t) +{ + look_for_address_of (local, t); + + /* Memcmp and strlen can both trap and they are declared pure. */ + if (tree_could_trap_p (t) + && local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; + + check_tree(local, t, false); +} + +/* Check to see if T is an assignment to a var we are interested in + analyzing. LOCAL is passed in to get access to its bit vectors. */ + +static void +check_lhs_var (funct_state local, tree t) +{ + /* Memcmp and strlen can both trap and they are declared pure. + Which seems to imply that we can apply the same rule here. */ + if (tree_could_trap_p (t) + && local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; + + check_tree(local, t, true); +} + +/* This is a scaled down version of get_asm_expr_operands from + tree_ssa_operands.c. The version there runs much later and assumes + that aliasing information is already available. Here we are just + trying to find if the set of inputs and outputs contain references + or address of operations to local static variables. STMT is the + actual asm statement. */ + +static void +get_asm_expr_operands (funct_state local, tree stmt) +{ + int noutputs = list_length (ASM_OUTPUTS (stmt)); + const char **oconstraints + = (const char **) alloca ((noutputs) * sizeof (const char *)); + int i; + tree link; + const char *constraint; + bool allows_mem, allows_reg, is_inout; + + for (i=0, link = ASM_OUTPUTS (stmt); link; ++i, link = TREE_CHAIN (link)) + { + oconstraints[i] = constraint + = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); + parse_output_constraint (&constraint, i, 0, 0, + &allows_mem, &allows_reg, &is_inout); + + check_lhs_var (local, TREE_VALUE (link)); + } + + for (link = ASM_INPUTS (stmt); link; link = TREE_CHAIN (link)) + { + constraint + = TREE_STRING_POINTER (TREE_VALUE (TREE_PURPOSE (link))); + parse_input_constraint (&constraint, 0, 0, noutputs, 0, + oconstraints, &allows_mem, &allows_reg); + + check_rhs_var (local, TREE_VALUE (link)); + } + + for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link)) + if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1) + /* Abandon all hope, ye who enter here. */ + local->pure_const_state = IPA_NEITHER; + + if (ASM_VOLATILE_P (stmt)) + local->pure_const_state = IPA_NEITHER; +} + +/* Check the parameters of a function call to CALL_EXPR to see if + there are any references in the parameters that are not allowed for + pure or const functions. Also check to see if this is either an + indirect call, a call outside the compilation unit, or has special + attributes that may also effect the purity. The CALL_EXPR node for + the entire call expression. */ + +static void +check_call (funct_state local, tree call_expr) +{ + int flags = call_expr_flags(call_expr); + tree operand_list = TREE_OPERAND (call_expr, 1); + tree operand; + tree callee_t = get_callee_fndecl (call_expr); + struct cgraph_node* callee; + enum availability avail = AVAIL_NOT_AVAILABLE; + + for (operand = operand_list; + operand != NULL_TREE; + operand = TREE_CHAIN (operand)) + { + tree argument = TREE_VALUE (operand); + check_rhs_var (local, argument); + } + + /* The const and pure flags are set by a variety of places in the + compiler (including here). If someone has already set the flags + for the callee, (such as for some of the builtins) we will use + them, otherwise we will compute our own information. + + Const and pure functions have less clobber effects than other + functions so we process these first. Otherwise if it is a call + outside the compilation unit or an indirect call we punt. This + leaves local calls which will be processed by following the call + graph. */ + if (callee_t) + { + callee = cgraph_node(callee_t); + avail = cgraph_function_body_availability (callee); + + /* When bad things happen to bad functions, they cannot be const + or pure. */ + if (setjmp_call_p (callee_t)) + local->pure_const_state = IPA_NEITHER; + + if (DECL_BUILT_IN_CLASS (callee_t) == BUILT_IN_NORMAL) + switch (DECL_FUNCTION_CODE (callee_t)) + { + case BUILT_IN_LONGJMP: + case BUILT_IN_NONLOCAL_GOTO: + local->pure_const_state = IPA_NEITHER; + break; + default: + break; + } + } + + /* The callee is either unknown (indirect call) or there is just no + scannable code for it (external call) . We look to see if there + are any bits available for the callee (such as by declaration or + because it is builtin) and process solely on the basis of those + bits. */ + if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) + { + if (flags & ECF_PURE) + { + if (local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; + } + else + local->pure_const_state = IPA_NEITHER; + } + else + { + /* We have the code and we will scan it for the effects. */ + if (flags & ECF_PURE) + { + if (local->pure_const_state == IPA_CONST) + local->pure_const_state = IPA_PURE; + } + } +} + +/* TP is the part of the tree currently under the microscope. + WALK_SUBTREES is part of the walk_tree api but is unused here. + DATA is cgraph_node of the function being walked. */ + +/* FIXME: When this is converted to run over SSA form, this code + should be converted to use the operand scanner. */ + +static tree +scan_function (tree *tp, + int *walk_subtrees, + void *data) +{ + struct cgraph_node *fn = data; + tree t = *tp; + funct_state local = get_function_state (fn); + + switch (TREE_CODE (t)) + { + case VAR_DECL: + if (DECL_INITIAL (t)) + walk_tree (&DECL_INITIAL (t), scan_function, fn, visited_nodes); + *walk_subtrees = 0; + break; + + case MODIFY_EXPR: + { + /* First look on the lhs and see what variable is stored to */ + tree lhs = TREE_OPERAND (t, 0); + tree rhs = TREE_OPERAND (t, 1); + check_lhs_var (local, lhs); + + /* For the purposes of figuring out what the cast affects */ + + /* Next check the operands on the rhs to see if they are ok. */ + switch (TREE_CODE_CLASS (TREE_CODE (rhs))) + { + case tcc_binary: + { + tree op0 = TREE_OPERAND (rhs, 0); + tree op1 = TREE_OPERAND (rhs, 1); + check_rhs_var (local, op0); + check_rhs_var (local, op1); + } + break; + case tcc_unary: + { + tree op0 = TREE_OPERAND (rhs, 0); + check_rhs_var (local, op0); + } + + break; + case tcc_reference: + check_rhs_var (local, rhs); + break; + case tcc_declaration: + check_rhs_var (local, rhs); + break; + case tcc_expression: + switch (TREE_CODE (rhs)) + { + case ADDR_EXPR: + check_rhs_var (local, rhs); + break; + case CALL_EXPR: + check_call (local, rhs); + break; + default: + break; + } + break; + default: + break; + } + *walk_subtrees = 0; + } + break; + + case ADDR_EXPR: + /* This case is here to find addresses on rhs of constructors in + decl_initial of static variables. */ + check_rhs_var (local, t); + *walk_subtrees = 0; + break; + + case LABEL_EXPR: + if (DECL_NONLOCAL (TREE_OPERAND (t, 0))) + /* Target of long jump. */ + local->pure_const_state = IPA_NEITHER; + break; + + case CALL_EXPR: + check_call (local, t); + *walk_subtrees = 0; + break; + + case ASM_EXPR: + get_asm_expr_operands (local, t); + *walk_subtrees = 0; + break; + + default: + break; + } + return NULL; +} + +/* This is the main routine for finding the reference patterns for + global variables within a function FN. */ + +static void +analyze_function (struct cgraph_node *fn) +{ + funct_state l = XCNEW (struct funct_state_d); + tree decl = fn->decl; + struct ipa_dfs_info * w_info = fn->aux; + + w_info->aux = l; + + l->pure_const_state = IPA_CONST; + l->state_set_in_source = false; + + /* If this function does not return normally or does not bind local, + do not touch this unless it has been marked as const or pure by the + front end. */ + if (TREE_THIS_VOLATILE (decl) + || !targetm.binds_local_p (decl)) + { + l->pure_const_state = IPA_NEITHER; + return; + } + + if (TREE_READONLY (decl)) + { + l->pure_const_state = IPA_CONST; + l->state_set_in_source = true; + } + if (DECL_IS_PURE (decl)) + { + l->pure_const_state = IPA_PURE; + l->state_set_in_source = true; + } + + if (dump_file) + { + fprintf (dump_file, "\n local analysis of %s with initial value = %d\n ", + cgraph_node_name (fn), + l->pure_const_state); + } + + if (!l->state_set_in_source) + { + struct function *this_cfun = DECL_STRUCT_FUNCTION (decl); + basic_block this_block; + + FOR_EACH_BB_FN (this_block, this_cfun) + { + block_stmt_iterator bsi; + for (bsi = bsi_start (this_block); !bsi_end_p (bsi); bsi_next (&bsi)) + { + walk_tree (bsi_stmt_ptr (bsi), scan_function, + fn, visited_nodes); + if (l->pure_const_state == IPA_NEITHER) + goto end; + } + } + + if (l->pure_const_state != IPA_NEITHER) + { + tree old_decl = current_function_decl; + /* Const functions cannot have back edges (an + indication of possible infinite loop side + effect. */ + + current_function_decl = fn->decl; + + /* The C++ front end, has a tendency to some times jerk away + a function after it has created it. This should have + been fixed. */ + gcc_assert (DECL_STRUCT_FUNCTION (fn->decl)); + + push_cfun (DECL_STRUCT_FUNCTION (fn->decl)); + + if (mark_dfs_back_edges ()) + l->pure_const_state = IPA_NEITHER; + + current_function_decl = old_decl; + pop_cfun (); + } + } + +end: + if (dump_file) + { + fprintf (dump_file, "after local analysis of %s with initial value = %d\n ", + cgraph_node_name (fn), + l->pure_const_state); + } +} + + +/* Produce the global information by preforming a transitive closure + on the local information that was produced by ipa_analyze_function + and ipa_analyze_variable. */ + +static unsigned int +static_execute (void) +{ + struct cgraph_node *node; + struct cgraph_node *w; + struct cgraph_node **order = + XCNEWVEC (struct cgraph_node *, cgraph_n_nodes); + int order_pos = order_pos = ipa_utils_reduced_inorder (order, true, false); + int i; + struct ipa_dfs_info * w_info; + + if (!memory_identifier_string) + memory_identifier_string = build_string(7, "memory"); + + /* There are some shared nodes, in particular the initializers on + static declarations. We do not need to scan them more than once + since all we would be interested in are the addressof + operations. */ + visited_nodes = pointer_set_create (); + + /* Process all of the functions. + + We do not want to process any of the clones so we check that this + is a master clone. However, we do NOT process any + AVAIL_OVERWRITABLE functions (these are never clones) we cannot + guarantee that what we learn about the one we see will be true + for the one that overriders it. + */ + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed && cgraph_is_master_clone (node)) + analyze_function (node); + + pointer_set_destroy (visited_nodes); + visited_nodes = NULL; + if (dump_file) + { + dump_cgraph (dump_file); + ipa_utils_print_order(dump_file, "reduced", order, order_pos); + } + + /* Propagate the local information thru the call graph to produce + the global information. All the nodes within a cycle will have + the same info so we collapse cycles first. Then we can do the + propagation in one pass from the leaves to the roots. */ + for (i = 0; i < order_pos; i++ ) + { + enum pure_const_state_e pure_const_state = IPA_CONST; + node = order[i]; + + /* Find the worst state for any node in the cycle. */ + w = node; + while (w) + { + funct_state w_l = get_function_state (w); + if (pure_const_state < w_l->pure_const_state) + pure_const_state = w_l->pure_const_state; + + if (pure_const_state == IPA_NEITHER) + break; + + if (!w_l->state_set_in_source) + { + struct cgraph_edge *e; + for (e = w->callees; e; e = e->next_callee) + { + struct cgraph_node *y = e->callee; + /* Only look at the master nodes and skip external nodes. */ + y = cgraph_master_clone (y); + if (y) + { + funct_state y_l = get_function_state (y); + if (pure_const_state < y_l->pure_const_state) + pure_const_state = y_l->pure_const_state; + if (pure_const_state == IPA_NEITHER) + break; + } + } + } + w_info = w->aux; + w = w_info->next_cycle; + } + + /* Copy back the region's pure_const_state which is shared by + all nodes in the region. */ + w = node; + while (w) + { + funct_state w_l = get_function_state (w); + + /* All nodes within a cycle share the same info. */ + if (!w_l->state_set_in_source) + { + w_l->pure_const_state = pure_const_state; + switch (pure_const_state) + { + case IPA_CONST: + TREE_READONLY (w->decl) = 1; + if (dump_file) + fprintf (dump_file, "Function found to be const: %s\n", + lang_hooks.decl_printable_name(w->decl, 2)); + break; + + case IPA_PURE: + DECL_IS_PURE (w->decl) = 1; + if (dump_file) + fprintf (dump_file, "Function found to be pure: %s\n", + lang_hooks.decl_printable_name(w->decl, 2)); + break; + + default: + break; + } + } + w_info = w->aux; + w = w_info->next_cycle; + } + } + + /* Cleanup. */ + for (node = cgraph_nodes; node; node = node->next) + /* Get rid of the aux information. */ + if (node->aux) + { + w_info = node->aux; + if (w_info->aux) + free (w_info->aux); + free (node->aux); + node->aux = NULL; + } + + free (order); + return 0; +} + +static bool +gate_pure_const (void) +{ + return (flag_unit_at_a_time != 0 && flag_ipa_pure_const + /* Don't bother doing anything if the program has errors. */ + && !(errorcount || sorrycount)); +} + +struct tree_opt_pass pass_ipa_pure_const = +{ + "pure-const", /* name */ + gate_pure_const, /* gate */ + static_execute, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_IPA_PURE_CONST, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ + 0 /* letter */ +}; + + |