diff options
| -rw-r--r-- | ChangeLog | 50 | ||||
| -rw-r--r-- | gcc/Makefile.in | 43 | ||||
| -rw-r--r-- | gcc/alias.c | 475 | ||||
| -rw-r--r-- | gcc/calls.c | 9 | ||||
| -rw-r--r-- | gcc/cgraph.h | 2 | ||||
| -rw-r--r-- | gcc/common.opt | 16 | ||||
| -rw-r--r-- | gcc/ipa-pure-const.c | 729 | ||||
| -rw-r--r-- | gcc/ipa-reference.c | 1317 | ||||
| -rw-r--r-- | gcc/ipa-reference.h | 83 | ||||
| -rw-r--r-- | gcc/ipa-type-escape.c | 1854 | ||||
| -rw-r--r-- | gcc/ipa-type-escape.h | 33 | ||||
| -rw-r--r-- | gcc/ipa-utils.c | 228 | ||||
| -rw-r--r-- | gcc/ipa-utils.h | 49 | ||||
| -rw-r--r-- | gcc/opts.c | 4 | ||||
| -rw-r--r-- | gcc/passes.c | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c | 8 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/sra-2.c | 4 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-2.c | 2 | ||||
| -rw-r--r-- | gcc/testsuite/gcc.dg/vect/vect-92.c | 2 | ||||
| -rw-r--r-- | gcc/timevar.def | 4 | ||||
| -rw-r--r-- | gcc/tree-dfa.c | 14 | ||||
| -rw-r--r-- | gcc/tree-flow.h | 11 | ||||
| -rw-r--r-- | gcc/tree-pass.h | 4 | ||||
| -rw-r--r-- | gcc/tree-promote-statics.c | 597 | ||||
| -rw-r--r-- | gcc/tree-sra.c | 25 | ||||
| -rw-r--r-- | gcc/tree-ssa-alias.c | 79 | ||||
| -rw-r--r-- | gcc/tree-ssa-operands.c | 99 |
27 files changed, 5284 insertions, 461 deletions
diff --git a/ChangeLog b/ChangeLog index fab8bd58574..c7eed293724 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,3 +1,53 @@ +2005-07-16 Danny Berlin <dberlin@dberlin.org> + Kenneth Zadeck <zadeck@naturalbridge.com> + + * Makefile.in: Added rules for ipa-pure-const.c, ipa-reference.c, + ipa-reference.h, ipa-utils.c, ipa-utils.h, ipa-type-escape.c, + ipa-type-escape.h, tree-promote-statics.c + * ipa-pure-const.c, ipa-reference.c, ipa-reference.h, ipa-utils.c, + ipa-utils.h, ipa-type-escape.c, ipa-type-escape.h, + tree-promote-statics.c: new files. + * alias.c: (nonlocal_mentioned_p_1, nonlocal_mentioned_p, + nonlocal_referenced_p_1, nonlocal_referenced_p, nonlocal_set_p_1, + int nonlocal_set_p, mark_constant_function): Deleted. + (rest_of_handle_cfg): Removed call to mark_constant_function. + (nonoverlapping_component_refs_p): Added calls to support + type based aliasing. + * tree-ssa-alias.c (may_alias_p, + compute_flow_insensitive_aliasing): Ditto. + * calls.c (flags_from_decl_or_type): Removed reference to + cgraph_rtl_info. + (flags_from_decl_or_type): Support ECF_POINTER_NO_CAPTURE attribute. + * c-common.c (handle_pointer_no_capture_attribute): New function + and added pointer_no_capture attribute. + * c-typeck.c (convert_arguments): Make builtins tolerant of having + too many arguments. This is necessary for Spec 2000. + * cgraph.h (const_function, pure_function): Removed. + * common.opt: Added "fipa-pure-const", "fipa-reference", + "fipa-type-escape", and "ftree-promote-static". + * opts.c: Ditto. + * passes.c: Added ipa and tree-promote-statics passes. + * timevar.def: Added TV_IPA_PURE_CONST, TV_IPA_REFERENCE, + TV_IPA_TYPE_ESCAPE, and TV_PROMOTE_STATICS. + * tree.h: Support ECF_POINTER_NO_CAPTURE attribute. + * tree-dfa.c (referenced_var_lookup_if_exists): New function. + * tree-flow.h: Added exposed sra calls and addition of + reference_vars_info field for FUNCTION_DECLS. + * tree-pass.h: Added passes. + * tree-sra.c: (sra_init_cache): New function. + (sra_insert_before, sra_insert_after) Made public. + (type_can_be_decomposed_p): Renamed from type_can_be_decomposed_p + and made public. + * tree-ssa-alias.c (dump_alias_stats): Added stats for type based + aliasing. (may_alias_p): Added code to use type escape analysis to + improve alias sets. + * tree-ssa-operands.c (add_call_clobber_ops): Added parameter and + code to prune clobbers of static variables based on information + produced in ipa-reference pass. Changed call clobbering so that + statics are not marked as clobbered if the call does not clobber + them. + + 2005-07-16 Kelley Cook <kcook@gcc.gnu.org> * all files: Update FSF address. diff --git a/gcc/Makefile.in b/gcc/Makefile.in index 3d8b8bc7c25..910cdc8b89f 100644 --- a/gcc/Makefile.in +++ b/gcc/Makefile.in @@ -729,6 +729,9 @@ SCHED_INT_H = sched-int.h $(INSN_ATTR_H) $(BASIC_BLOCK_H) $(RTL_H) INTEGRATE_H = integrate.h varray.h CFGLAYOUT_H = cfglayout.h $(BASIC_BLOCK_H) CFGLOOP_H = cfgloop.h $(BASIC_BLOCK_H) $(RTL_H) +IPA_UTILS_H = ipa-utils.h $(TREE_H) $(CGRAPH_H) +IPA_REFERENCE_H = ipa-reference.h bitmap.h $(TREE_H) +IPA_TYPE_ESCAPE_H = ipa-type-escape.h $(TREE_H) CGRAPH_H = cgraph.h tree.h DF_H = df.h bitmap.h sbitmap.h $(BASIC_BLOCK_H) DDG_H = ddg.h sbitmap.h $(DF_H) @@ -750,7 +753,7 @@ TREE_DUMP_H = tree-dump.h $(SPLAY_TREE_H) TREE_GIMPLE_H = tree-gimple.h tree-iterator.h TREE_FLOW_H = tree-flow.h tree-flow-inline.h tree-ssa-operands.h \ bitmap.h $(BASIC_BLOCK_H) hard-reg-set.h $(TREE_GIMPLE_H) \ - $(HASHTAB_H) $(CGRAPH_H) + $(HASHTAB_H) $(CGRAPH_H) $(IPA_REFERENCE_H) TREE_SSA_LIVE_H = tree-ssa-live.h $(PARTITION_H) PRETTY_PRINT_H = pretty-print.h input.h $(OBSTACK_H) DIAGNOSTIC_H = diagnostic.h diagnostic.def $(PRETTY_PRINT_H) @@ -945,7 +948,7 @@ OBJS-common = \ integrate.o intl.o jump.o langhooks.o lcm.o lists.o local-alloc.o \ loop.o mode-switching.o modulo-sched.o optabs.o options.o opts.o \ params.o postreload.o postreload-gcse.o predict.o \ - insn-preds.o pointer-set.o \ + insn-preds.o pointer-set.o tree-promote-statics.o \ print-rtl.o print-tree.o profile.o value-prof.o var-tracking.o \ real.o recog.o reg-stack.o regclass.o regmove.o regrename.o \ reload.o reload1.o reorg.o resource.o rtl.o rtlanal.o rtl-error.o \ @@ -962,7 +965,8 @@ OBJS-common = \ OBJS-md = $(out_object_file) OBJS-archive = $(EXTRA_OBJS) $(host_hook_obj) tree-inline.o \ - cgraph.o cgraphunit.o tree-nomudflap.o ipa.o ipa-inline.o + cgraph.o cgraphunit.o tree-nomudflap.o ipa.o ipa-inline.o \ + ipa-utils.o ipa-reference.o ipa-pure-const.o ipa-type-escape.o OBJS = $(OBJS-common) $(out_object_file) $(OBJS-archive) @@ -1837,11 +1841,12 @@ tree-dfa.o : tree-dfa.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ tree-inline.h $(HASHTAB_H) pointer-set.h $(FLAGS_H) function.h \ $(TIMEVAR_H) convert.h $(TM_H) coretypes.h langhooks.h $(TREE_DUMP_H) \ tree-pass.h $(PARAMS_H) $(CGRAPH_H) $(BASIC_BLOCK_H) hard-reg-set.h \ - $(TREE_GIMPLE_H) + $(TREE_GIMPLE_H) tree-ssa-operands.o : tree-ssa-operands.c $(TREE_FLOW_H) $(CONFIG_H) \ - $(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) tree-inline.h \ + $(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) errors.h tree-inline.h \ $(FLAGS_H) function.h $(TM_H) $(TIMEVAR_H) tree-pass.h toplev.h \ - gt-tree-ssa-operands.h coretypes.h langhooks.h tree-ssa-opfinalize.h + gt-tree-ssa-operands.h coretypes.h langhooks.h tree-ssa-opfinalize.h \ + $(IPA_REFERENCE_H) tree-eh.o : tree-eh.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_H) $(FLAGS_H) function.h except.h langhooks.h \ $(GGC_H) tree-pass.h coretypes.h $(TIMEVAR_H) $(TM_P_H) \ @@ -1895,7 +1900,8 @@ tree-ssa-alias.o : tree-ssa-alias.c $(TREE_FLOW_H) $(CONFIG_H) $(SYSTEM_H) \ $(RTL_H) $(TREE_H) $(TM_P_H) $(EXPR_H) $(GGC_H) tree-inline.h $(FLAGS_H) \ function.h $(TIMEVAR_H) convert.h $(TM_H) coretypes.h langhooks.h \ $(TREE_DUMP_H) tree-pass.h $(PARAMS_H) $(BASIC_BLOCK_H) $(DIAGNOSTIC_H) \ - hard-reg-set.h $(TREE_GIMPLE_H) vec.h tree-ssa-structalias.h + hard-reg-set.h $(TREE_GIMPLE_H) vec.h tree-ssa-structalias.h \ + $(IPA_TYPE_ESCAPE_H) tree-ssa-reassoc.o : tree-ssa-reassoc.c $(TREE_FLOW_H) $(CONFIG_H) \ $(SYSTEM_H) $(TREE_H) $(GGC_H) $(DIAGNOSTIC_H) errors.h $(TIMEVAR_H) \ $(TM_H) coretypes.h $(TREE_DUMP_H) tree-pass.h $(FLAGS_H) tree-iterator.h\ @@ -2142,6 +2148,22 @@ ipa-inline.o : ipa-inline.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \ $(TREE_H) langhooks.h tree-inline.h $(FLAGS_H) $(CGRAPH_H) intl.h \ $(DIAGNOSTIC_H) $(FIBHEAP_H) $(PARAMS_H) $(TIMEVAR_H) tree-pass.h \ $(COVERAGE_H) $(HASHTAB_H) +ipa-utils.o : ipa-utils.c $(IPA_UTILS_H) $(CONFIG_H) $(SYSTEM_H) \ + coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) tree-inline.h langhooks.h \ + pointer-set.h $(GGC_H) $(C_COMMON_H) $(TREE_GIMPLE_H) \ + $(CGRAPH_H) output.h $(FLAGS_H) tree-pass.h $(DIAGNOSTIC_H) +ipa-reference.o : ipa-reference.c $(CONFIG_H) $(SYSTEM_H) \ + coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) tree-inline.h langhooks.h \ + pointer-set.h $(GGC_H) $(IPA_REFERENCE_H) $(IPA_UTILS_H) $(C_COMMON_H) \ + $(TREE_GIMPLE_H) $(CGRAPH_H) output.h $(FLAGS_H) tree-pass.h $(DIAGNOSTIC_H) +ipa-pure-const.o : ipa-pure-const.c $(CONFIG_H) $(SYSTEM_H) \ + coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) tree-inline.h langhooks.h \ + pointer-set.h $(GGC_H) $(IPA_UTILS_H) $(C_COMMON_H) \ + $(TREE_GIMPLE_H) $(CGRAPH_H) output.h $(FLAGS_H) tree-pass.h $(DIAGNOSTIC_H) +ipa-type-escape.o : ipa-type-escape.c $(CONFIG_H) $(SYSTEM_H) \ + coretypes.h $(TM_H) $(TREE_H) $(TREE_FLOW_H) tree-inline.h langhooks.h \ + pointer-set.h $(GGC_H) $(IPA_TYPE_ESCAPE_H) $(IPA_UTILS_H) $(C_COMMON_H) \ + $(TREE_GIMPLE_H) $(CGRAPH_H) output.h $(FLAGS_H) tree-pass.h $(DIAGNOSTIC_H) coverage.o : coverage.c $(GCOV_IO_H) $(CONFIG_H) $(SYSTEM_H) coretypes.h \ $(TM_H) $(RTL_H) $(TREE_H) $(FLAGS_H) output.h $(REGS_H) $(EXPR_H) \ function.h toplev.h $(GGC_H) langhooks.h $(COVERAGE_H) gt-coverage.h \ @@ -2196,6 +2218,9 @@ tree-vect-generic.o : tree-vect-generic.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) \ $(FLAGS_H) $(OPTABS_H) $(RTL_H) $(MACHMODE_H) $(EXPR_H) \ langhooks.h $(FLAGS_H) $(DIAGNOSTIC_H) gt-tree-vect-generic.h $(GGC_H) \ coretypes.h insn-codes.h +tree-promote-statics.o : tree-promote-statics.c $(CONFIG_H) system.h \ + $(TREE_H) $(TM_H) $(BASIC_BLOCK_H) $(TREE_FLOW_H) $(IPA_UTILS_H) \ + $(IPA_REFERENCE_H) bitmap.h tree-pass.h $(FLAGS_H) $(TIMEVAR_H) df.o : df.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ insn-config.h $(RECOG_H) function.h $(REGS_H) alloc-pool.h hard-reg-set.h \ $(BASIC_BLOCK_H) $(DF_H) bitmap.h sbitmap.h $(TM_P_H) @@ -2345,7 +2370,7 @@ alias.o : alias.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ $(FLAGS_H) hard-reg-set.h $(BASIC_BLOCK_H) $(REGS_H) toplev.h output.h \ $(ALIAS_H) $(EMIT_RTL_H) $(GGC_H) function.h cselib.h $(TREE_H) $(TM_P_H) \ langhooks.h $(TARGET_H) gt-alias.h $(TIMEVAR_H) $(CGRAPH_H) \ - $(SPLAY_TREE_H) $(VARRAY_H) tree-pass.h + $(SPLAY_TREE_H) $(VARRAY_H) $(IPA_TYPE_ESCAPE_H) tree-pass.h regmove.o : regmove.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \ insn-config.h timevar.h tree-pass.h \ $(RECOG_H) output.h $(REGS_H) hard-reg-set.h $(FLAGS_H) function.h \ @@ -2682,6 +2707,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/coverage.c $(srcdir)/function.h $(srcdir)/rtl.h \ $(srcdir)/optabs.h $(srcdir)/tree.h $(srcdir)/libfuncs.h $(SYMTAB_H) \ $(srcdir)/real.h $(srcdir)/varray.h $(srcdir)/insn-addr.h $(srcdir)/hwint.h \ + $(srcdir)/ipa-reference.h \ $(srcdir)/cselib.h $(srcdir)/basic-block.h $(srcdir)/cgraph.h \ $(srcdir)/c-common.h $(srcdir)/c-tree.h $(srcdir)/reload.h \ $(srcdir)/alias.c $(srcdir)/bitmap.c $(srcdir)/cselib.c $(srcdir)/cgraph.c \ @@ -2703,6 +2729,7 @@ GTFILES = $(srcdir)/input.h $(srcdir)/coretypes.h \ $(srcdir)/tree-chrec.h $(srcdir)/tree-vect-generic.c \ $(srcdir)/tree-ssa-operands.h $(srcdir)/tree-ssa-operands.c \ $(srcdir)/tree-profile.c $(srcdir)/rtl-profile.c $(srcdir)/tree-nested.c \ + $(srcdir)/ipa-reference.c \ $(srcdir)/targhooks.c $(out_file) \ @all_gtfiles@ diff --git a/gcc/alias.c b/gcc/alias.c index 9bc11d72049..cdbb94dfceb 100644 --- a/gcc/alias.c +++ b/gcc/alias.c @@ -45,6 +45,58 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA #include "cgraph.h" #include "varray.h" #include "tree-pass.h" +#include "ipa-type-escape.h" + +/* The aliasing API provided here solves related but different problems: + + Say there exists (in c) + + struct X { + struct Y y1; + struct Z z2; + } x1, *px1, *px2; + + struct Y y2, *py; + struct Z z2, *pz; + + + py = &px1.y1; + px2 = &x1; + + Consider the four questions: + + Can a store to x1 interfere with px2->y1? + Can a store to x1 interfere with px2->z2? + (*px2).z2 + Can a store to x1 change the value pointed to by with py? + Can a store to x1 change the value pointed to by with pz? + + The answer to these questions can be yes, yes, yes, and maybe. + + The first two questions can be answered with a simple examination + of the type system. If structure X contains a field of type Y then + a store thru a pointer to an X can overwrite any field that is + contained (recursively) in an X (unless we know that px1 != px2). + + The last two of the questions can be solved in the same way as the + first two questions but this is too conservative. The observation + is that in some cases analysis we can know if which (if any) fields + are addressed and if those addresses are used in bad ways. This + analysis may be language specific. In C, arbitrary operations may + be applied to pointers. However, there is some indication that + this may be too conservative for some C++ types. + + The pass ipa-type-escape does this analysis for the types whose + instances do not escape across the compilation boundary. + + Historically in GCC, these two problems were combined and a single + data structure was used to represent the solution to these + problems. We now have two similar but different data structures, + The data structure to solve the last two question is similar to the + first, but does not contain have the fields in it whose address are + never taken. For types that do escape the compilation unit, the + data structures will have identical information. +*/ /* The alias sets assigned to MEMs assist the back-end in determining which MEMs can alias which other MEMs. In general, two MEMs in @@ -116,12 +168,6 @@ static rtx adjust_offset_for_component_ref (tree, rtx); static int nonoverlapping_memrefs_p (rtx, rtx); static int write_dependence_p (rtx, rtx, int); -static int nonlocal_mentioned_p_1 (rtx *, void *); -static int nonlocal_mentioned_p (rtx); -static int nonlocal_referenced_p_1 (rtx *, void *); -static int nonlocal_referenced_p (rtx); -static int nonlocal_set_p_1 (rtx *, void *); -static int nonlocal_set_p (rtx); static void memory_modified_1 (rtx, rtx, void *); static void record_alias_subset (HOST_WIDE_INT, HOST_WIDE_INT); @@ -1924,9 +1970,8 @@ nonoverlapping_component_refs_p (tree x, tree y) x = TREE_OPERAND (x, 0); } while (x && TREE_CODE (x) == COMPONENT_REF); - /* Never found a common type. */ - return false; + return true; found: /* If we're left with accessing different fields of a structure, @@ -2006,22 +2051,34 @@ nonoverlapping_memrefs_p (rtx x, rtx y) /* Unless both have exprs, we can't tell anything. */ if (exprx == 0 || expry == 0) return 0; - + /* If both are field references, we may be able to determine something. */ if (TREE_CODE (exprx) == COMPONENT_REF && TREE_CODE (expry) == COMPONENT_REF && nonoverlapping_component_refs_p (exprx, expry)) return 1; + /* If the field reference test failed, look at the DECLs involved. */ moffsetx = MEM_OFFSET (x); if (TREE_CODE (exprx) == COMPONENT_REF) { - tree t = decl_for_component_ref (exprx); - if (! t) - return 0; - moffsetx = adjust_offset_for_component_ref (exprx, moffsetx); - exprx = t; + if (TREE_CODE (expry) == VAR_DECL + && POINTER_TYPE_P (TREE_TYPE (expry))) + { + tree field = TREE_OPERAND (exprx, 1); + tree fieldcontext = DECL_FIELD_CONTEXT (field); + if (ipa_type_escape_field_does_not_clobber_p (fieldcontext, + TREE_TYPE (field))) + return 1; + } + { + tree t = decl_for_component_ref (exprx); + if (! t) + return 0; + moffsetx = adjust_offset_for_component_ref (exprx, moffsetx); + exprx = t; + } } else if (INDIRECT_REF_P (exprx)) { @@ -2034,11 +2091,22 @@ nonoverlapping_memrefs_p (rtx x, rtx y) moffsety = MEM_OFFSET (y); if (TREE_CODE (expry) == COMPONENT_REF) { - tree t = decl_for_component_ref (expry); - if (! t) - return 0; - moffsety = adjust_offset_for_component_ref (expry, moffsety); - expry = t; + if (TREE_CODE (exprx) == VAR_DECL + && POINTER_TYPE_P (TREE_TYPE (exprx))) + { + tree field = TREE_OPERAND (expry, 1); + tree fieldcontext = DECL_FIELD_CONTEXT (field); + if (ipa_type_escape_field_does_not_clobber_p (fieldcontext, + TREE_TYPE (field))) + return 1; + } + { + tree t = decl_for_component_ref (expry); + if (! t) + return 0; + moffsety = adjust_offset_for_component_ref (expry, moffsety); + expry = t; + } } else if (INDIRECT_REF_P (expry)) { @@ -2326,353 +2394,6 @@ output_dependence (rtx mem, rtx x) return write_dependence_p (mem, x, /*writep=*/1); } -/* A subroutine of nonlocal_mentioned_p, returns 1 if *LOC mentions - something which is not local to the function and is not constant. */ - -static int -nonlocal_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED) -{ - rtx x = *loc; - rtx base; - int regno; - - if (! x) - return 0; - - switch (GET_CODE (x)) - { - case SUBREG: - if (REG_P (SUBREG_REG (x))) - { - /* Global registers are not local. */ - if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER - && global_regs[subreg_regno (x)]) - return 1; - return 0; - } - break; - - case REG: - regno = REGNO (x); - /* Global registers are not local. */ - if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) - return 1; - return 0; - - case SCRATCH: - case PC: - case CC0: - case CONST_INT: - case CONST_DOUBLE: - case CONST_VECTOR: - case CONST: - case LABEL_REF: - return 0; - - case SYMBOL_REF: - /* Constants in the function's constants pool are constant. */ - if (CONSTANT_POOL_ADDRESS_P (x)) - return 0; - return 1; - - case CALL: - /* Non-constant calls and recursion are not local. */ - return 1; - - case MEM: - /* Be overly conservative and consider any volatile memory - reference as not local. */ - if (MEM_VOLATILE_P (x)) - return 1; - base = find_base_term (XEXP (x, 0)); - if (base) - { - /* A Pmode ADDRESS could be a reference via the structure value - address or static chain. Such memory references are nonlocal. - - Thus, we have to examine the contents of the ADDRESS to find - out if this is a local reference or not. */ - if (GET_CODE (base) == ADDRESS - && GET_MODE (base) == Pmode - && (XEXP (base, 0) == stack_pointer_rtx - || XEXP (base, 0) == arg_pointer_rtx -#if HARD_FRAME_POINTER_REGNUM != FRAME_POINTER_REGNUM - || XEXP (base, 0) == hard_frame_pointer_rtx -#endif - || XEXP (base, 0) == frame_pointer_rtx)) - return 0; - /* Constants in the function's constant pool are constant. */ - if (GET_CODE (base) == SYMBOL_REF && CONSTANT_POOL_ADDRESS_P (base)) - return 0; - } - return 1; - - case UNSPEC_VOLATILE: - case ASM_INPUT: - return 1; - - case ASM_OPERANDS: - if (MEM_VOLATILE_P (x)) - return 1; - - /* Fall through. */ - - default: - break; - } - - return 0; -} - -/* Returns nonzero if X might mention something which is not - local to the function and is not constant. */ - -static int -nonlocal_mentioned_p (rtx x) -{ - if (INSN_P (x)) - { - if (CALL_P (x)) - { - if (! CONST_OR_PURE_CALL_P (x)) - return 1; - x = CALL_INSN_FUNCTION_USAGE (x); - if (x == 0) - return 0; - } - else - x = PATTERN (x); - } - - return for_each_rtx (&x, nonlocal_mentioned_p_1, NULL); -} - -/* A subroutine of nonlocal_referenced_p, returns 1 if *LOC references - something which is not local to the function and is not constant. */ - -static int -nonlocal_referenced_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED) -{ - rtx x = *loc; - - if (! x) - return 0; - - switch (GET_CODE (x)) - { - case MEM: - case REG: - case SYMBOL_REF: - case SUBREG: - return nonlocal_mentioned_p (x); - - case CALL: - /* Non-constant calls and recursion are not local. */ - return 1; - - case SET: - if (nonlocal_mentioned_p (SET_SRC (x))) - return 1; - - if (MEM_P (SET_DEST (x))) - return nonlocal_mentioned_p (XEXP (SET_DEST (x), 0)); - - /* If the destination is anything other than a CC0, PC, - MEM, REG, or a SUBREG of a REG that occupies all of - the REG, then X references nonlocal memory if it is - mentioned in the destination. */ - if (GET_CODE (SET_DEST (x)) != CC0 - && GET_CODE (SET_DEST (x)) != PC - && !REG_P (SET_DEST (x)) - && ! (GET_CODE (SET_DEST (x)) == SUBREG - && REG_P (SUBREG_REG (SET_DEST (x))) - && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (x)))) - + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD) - == ((GET_MODE_SIZE (GET_MODE (SET_DEST (x))) - + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD)))) - return nonlocal_mentioned_p (SET_DEST (x)); - return 0; - - case CLOBBER: - if (MEM_P (XEXP (x, 0))) - return nonlocal_mentioned_p (XEXP (XEXP (x, 0), 0)); - return 0; - - case USE: - return nonlocal_mentioned_p (XEXP (x, 0)); - - case ASM_INPUT: - case UNSPEC_VOLATILE: - return 1; - - case ASM_OPERANDS: - if (MEM_VOLATILE_P (x)) - return 1; - - /* Fall through. */ - - default: - break; - } - - return 0; -} - -/* Returns nonzero if X might reference something which is not - local to the function and is not constant. */ - -static int -nonlocal_referenced_p (rtx x) -{ - if (INSN_P (x)) - { - if (CALL_P (x)) - { - if (! CONST_OR_PURE_CALL_P (x)) - return 1; - x = CALL_INSN_FUNCTION_USAGE (x); - if (x == 0) - return 0; - } - else - x = PATTERN (x); - } - - return for_each_rtx (&x, nonlocal_referenced_p_1, NULL); -} - -/* A subroutine of nonlocal_set_p, returns 1 if *LOC sets - something which is not local to the function and is not constant. */ - -static int -nonlocal_set_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED) -{ - rtx x = *loc; - - if (! x) - return 0; - - switch (GET_CODE (x)) - { - case CALL: - /* Non-constant calls and recursion are not local. */ - return 1; - - case PRE_INC: - case PRE_DEC: - case POST_INC: - case POST_DEC: - case PRE_MODIFY: - case POST_MODIFY: - return nonlocal_mentioned_p (XEXP (x, 0)); - - case SET: - if (nonlocal_mentioned_p (SET_DEST (x))) - return 1; - return nonlocal_set_p (SET_SRC (x)); - - case CLOBBER: - return nonlocal_mentioned_p (XEXP (x, 0)); - - case USE: - return 0; - - case ASM_INPUT: - case UNSPEC_VOLATILE: - return 1; - - case ASM_OPERANDS: - if (MEM_VOLATILE_P (x)) - return 1; - - /* Fall through. */ - - default: - break; - } - - return 0; -} - -/* Returns nonzero if X might set something which is not - local to the function and is not constant. */ - -static int -nonlocal_set_p (rtx x) -{ - if (INSN_P (x)) - { - if (CALL_P (x)) - { - if (! CONST_OR_PURE_CALL_P (x)) - return 1; - x = CALL_INSN_FUNCTION_USAGE (x); - if (x == 0) - return 0; - } - else - x = PATTERN (x); - } - - return for_each_rtx (&x, nonlocal_set_p_1, NULL); -} - -/* Mark the function if it is pure or constant. */ - -void -mark_constant_function (void) -{ - rtx insn; - int nonlocal_memory_referenced; - - if (TREE_READONLY (current_function_decl) - || DECL_IS_PURE (current_function_decl) - || TREE_THIS_VOLATILE (current_function_decl) - || current_function_has_nonlocal_goto - || !targetm.binds_local_p (current_function_decl)) - return; - - /* A loop might not return which counts as a side effect. */ - if (mark_dfs_back_edges ()) - return; - - nonlocal_memory_referenced = 0; - - init_alias_analysis (); - - /* Determine if this is a constant or pure function. */ - - for (insn = get_insns (); insn; insn = NEXT_INSN (insn)) - { - if (! INSN_P (insn)) - continue; - - if (nonlocal_set_p (insn) || global_reg_mentioned_p (insn) - || volatile_refs_p (PATTERN (insn))) - break; - - if (! nonlocal_memory_referenced) - nonlocal_memory_referenced = nonlocal_referenced_p (insn); - } - - end_alias_analysis (); - - /* Mark the function. */ - - if (insn) - ; - else if (nonlocal_memory_referenced) - { - cgraph_rtl_info (current_function_decl)->pure_function = 1; - DECL_IS_PURE (current_function_decl) = 1; - } - else - { - cgraph_rtl_info (current_function_decl)->const_function = 1; - TREE_READONLY (current_function_decl) = 1; - } -} - void init_alias_once (void) @@ -2979,28 +2700,6 @@ rest_of_handle_cfg (void) if (optimize) cleanup_cfg (CLEANUP_EXPENSIVE | (flag_thread_jumps ? CLEANUP_THREADING : 0)); - - /* It may make more sense to mark constant functions after dead code is - eliminated by life_analysis, but we need to do it early, as -fprofile-arcs - may insert code making function non-constant, but we still must consider - it as constant, otherwise -fbranch-probabilities will not read data back. - - life_analysis rarely eliminates modification of external memory. - - FIXME: now with tree based profiling we are in the trap described above - again. It seems to be easiest to disable the optimization for time - being before the problem is either solved by moving the transformation - to the IPA level (we need the CFG for this) or the very early optimization - passes are made to ignore the const/pure flags so code does not change. */ - if (optimize - && (!flag_tree_based_profiling - || (!profile_arc_flag && !flag_branch_probabilities))) - { - /* Alias analysis depends on this information and mark_constant_function - depends on alias analysis. */ - reg_scan (get_insns (), max_reg_num ()); - mark_constant_function (); - } } struct tree_opt_pass pass_cfg = diff --git a/gcc/calls.c b/gcc/calls.c index 89f747fe2eb..f21426fa995 100644 --- a/gcc/calls.c +++ b/gcc/calls.c @@ -570,17 +570,8 @@ flags_from_decl_or_type (tree exp) if (DECL_P (exp)) { - struct cgraph_rtl_info *i = cgraph_rtl_info (exp); type = TREE_TYPE (exp); - if (i) - { - if (i->pure_function) - flags |= ECF_PURE | ECF_LIBCALL_BLOCK; - if (i->const_function) - flags |= ECF_CONST | ECF_LIBCALL_BLOCK; - } - /* The function exp may have the `malloc' attribute. */ if (DECL_IS_MALLOC (exp)) flags |= ECF_MALLOC; diff --git a/gcc/cgraph.h b/gcc/cgraph.h index 40a2648b36e..d063d41906d 100644 --- a/gcc/cgraph.h +++ b/gcc/cgraph.h @@ -107,8 +107,6 @@ struct cgraph_global_info GTY(()) struct cgraph_rtl_info GTY(()) { int preferred_incoming_stack_boundary; - bool const_function; - bool pure_function; }; /* The cgraph data structure. diff --git a/gcc/common.opt b/gcc/common.opt index ddac0b4f0a3..9d2b6712c47 100644 --- a/gcc/common.opt +++ b/gcc/common.opt @@ -491,6 +491,18 @@ finstrument-functions Common Report Var(flag_instrument_function_entry_exit) Instrument function entry and exit with profiling calls +fipa-pure-const +Common Report Var(flag_ipa_pure_const) Init(0) +Discover pure and const functions + +fipa-reference +Common Report Var(flag_ipa_reference) Init(0) +Discover readonly and non addressable static variables + +fipa-type-escape +Common Report Var(flag_ipa_type_escape) Init(0) +Type based escape and alias analysis + fivopts Common Report Var(flag_ivopts) Init(1) Optimize induction variables on trees @@ -915,6 +927,10 @@ ftree-pre Common Report Var(flag_tree_pre) Enable SSA-PRE optimization on trees +ftree-promote-statics +Common Report Var(flag_tree_promote_statics) Init(0) +Enable promotion of static variables + ftree-salias Common Report Var(flag_tree_salias) Perform structural alias analysis diff --git a/gcc/ipa-pure-const.c b/gcc/ipa-pure-const.c new file mode 100644 index 00000000000..1402607aa8b --- /dev/null +++ b/gcc/ipa-pure-const.c @@ -0,0 +1,729 @@ +/* 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, 59 Temple Place - Suite 330, Boston, MA +02111-1307, 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" + +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; + + 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; + 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 = xcalloc (1, sizeof (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 is a volatile function, do not touch this unless it has + been marked as const or pure by the front end. */ + if (TREE_THIS_VOLATILE (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) + return; + } + } + + 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 (); + } + } +} + + +/* 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 void +static_execute (void) +{ + struct cgraph_node *node; + struct cgraph_node *w; + struct cgraph_node **order = + xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); + 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) + { + free (node->aux); + node->aux = NULL; + } + + free (order); +} + +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 = +{ + "ipa-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 */ +}; + + diff --git a/gcc/ipa-reference.c b/gcc/ipa-reference.c new file mode 100644 index 00000000000..223a56ac680 --- /dev/null +++ b/gcc/ipa-reference.c @@ -0,0 +1,1317 @@ +/* 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, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. +*/ + +/* This file gathers information about how variables whose scope is + confined to the compilation unit are used. + + There are two categories of information produced by this pass: + + 1) The addressable (TREE_ADDRESSABLE) bit and readonly + (TREE_READONLY) bit associated with these variables is properly set + based on scanning all of the code withing the compilation unit. + + 2) The transitive call site specific clobber effects are computed + for the variables whose scope is contained within this compilation + unit. + + First each function and static variable initialization is analyzed + to determine which local static variables are either read, written, + or have their address taken. Any local static that has its address + taken is removed from consideration. Once the local read and + writes are determined, a transitive closure of this information is + performed over the call graph to determine the worst case set of + side effects of each call. In later parts of the compiler, these + local and global sets are examined to make the call clobbering less + traumatic, promote some statics to registers, and improve aliasing + information. + + Currently 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. +*/ + +#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 "ipa-reference.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" + +/* This splay tree contains all of the static variables that are + being considered by the compilation level alias analysis. For + module_at_a_time compilation, this is the set of static but not + public variables. Any variables that either have their address + taken or participate in otherwise unsavory operations are deleted + from this list. */ +static GTY((param1_is(int), param2_is(tree))) + splay_tree reference_vars_to_consider; + +/* This bitmap is used to knock out the module static variables whose + addresses have been taken and passed around. */ +static bitmap module_statics_escape; + +/* This bitmap is used to knock out the module static variables that + are not readonly. */ +static bitmap module_statics_written; + +/* A bit is set for every module static we are considering. This is + ored into the local info when asm code is found that clobbers all + memory. */ +static bitmap all_module_statics; + +static struct pointer_set_t *visited_nodes; + +static bitmap_obstack ipa_obstack; + +enum initialization_status_t +{ + UNINITIALIZED, + RUNNING, + FINISHED +}; + +tree memory_identifier_string; + +/* Return the ipa_reference_vars structure starting from the cgraph NODE. */ +static inline ipa_reference_vars_info_t +get_reference_vars_info_from_cgraph (struct cgraph_node * node) +{ + return get_var_ann (node->decl)->reference_vars_info; +} + +/* Get a bitmap that contains all of the locally referenced static + variables for function FN. */ +static ipa_reference_local_vars_info_t +get_local_reference_vars_info (tree fn) +{ + ipa_reference_vars_info_t info = get_var_ann (fn)->reference_vars_info; + + if (info) + return info->local; + else + /* This phase was not run. */ + return NULL; +} + +/* Get a bitmap that contains all of the globally referenced static + variables for function FN. */ + +static ipa_reference_global_vars_info_t +get_global_reference_vars_info (tree fn) +{ + ipa_reference_vars_info_t info = get_var_ann (fn)->reference_vars_info; + + if (info) + return info->global; + else + /* This phase was not run. */ + return NULL; +} + +/* Return a bitmap indexed by VAR_DECL uid for the static variables + that may be read locally by the execution of the function fn. + Returns NULL if no data is available. */ + +bitmap +ipa_reference_get_read_local (tree fn) +{ + ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn); + if (l) + return l->statics_read; + else + return NULL; +} + +/* Return a bitmap indexed by VAR_DECL uid for the static variables + that may be written locally by the execution of the function fn. + Returns NULL if no data is available. */ + +bitmap +ipa_reference_get_written_local (tree fn) +{ + ipa_reference_local_vars_info_t l = get_local_reference_vars_info (fn); + if (l) + return l->statics_written; + else + return NULL; +} + +/* Return a bitmap indexed by VAR_DECL uid for the static variables + that are read during the execution of the function FN. Returns + NULL if no data is available. */ + +bitmap +ipa_reference_get_read_global (tree fn) +{ + ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); + if (g) + return g->statics_read; + else + return NULL; +} + +/* Return a bitmap indexed by VAR_DECL uid for the static variables + that are written during the execution of the function FN. Note + that variables written may or may not be read during the function + call. Returns NULL if no data is available. */ + +bitmap +ipa_reference_get_written_global (tree fn) +{ + ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); + if (g) + return g->statics_written; + else + return NULL; +} + +/* Return a bitmap indexed by_DECL_UID uid for the static variables + that are not read during the execution of the function FN. Returns + NULL if no data is available. */ + +bitmap +ipa_reference_get_not_read_global (tree fn) +{ + ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); + if (g) + return g->statics_not_read; + else + return NULL; +} + +/* Return a bitmap indexed by DECL_UID uid for the static variables + that are not written during the execution of the function FN. Note + that variables written may or may not be read during the function + call. Returns NULL if no data is available. */ + +bitmap +ipa_reference_get_not_written_global (tree fn) +{ + ipa_reference_global_vars_info_t g = get_global_reference_vars_info (fn); + if (g) + return g->statics_not_written; + else + return NULL; +} + + + +/* Add VAR to all_module_statics and the two + reference_vars_to_consider* sets. */ + +static inline void +add_static_var (tree var) +{ + int uid = DECL_UID (var); + if (!bitmap_bit_p (all_module_statics, uid)) + { + splay_tree_insert (reference_vars_to_consider, + uid, (splay_tree_value)var); + bitmap_set_bit (all_module_statics, uid); + } +} + +/* Return true if the variable T is the right kind of static variable to + perform compilation unit scope escape analysis. */ + +static inline bool +has_proper_scope_for_analysis (tree t) +{ + /* 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))) + return false; + + /* 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)) + return false; + + /* Do not care about a local automatic that is not static. */ + if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) + return false; + + if (DECL_EXTERNAL (t) || TREE_PUBLIC (t)) + return false; + + /* This is a variable we care about. Check if we have seen it + before, and if not add it the set of variables we care about. */ + if (!bitmap_bit_p (all_module_statics, DECL_UID (t))) + add_static_var (t); + + return true; +} + +/* If T is a VAR_DECL for a static that we are interested in, add the + uid to the bitmap. */ + +static void +check_operand (ipa_reference_local_vars_info_t local, + tree t, bool checking_write) +{ + if (!t) return; + + if ((TREE_CODE (t) == VAR_DECL) + && (has_proper_scope_for_analysis (t))) + { + if (checking_write) + { + if (local) + bitmap_set_bit (local->statics_written, DECL_UID (t)); + /* Mark the write so we can tell which statics are + readonly. */ + bitmap_set_bit (module_statics_written, DECL_UID (t)); + } + else if (local) + bitmap_set_bit (local->statics_read, DECL_UID (t)); + } +} + +/* Examine tree T for references to static variables. All internal + references like array references or indirect references are added + to the READ_BM. Direct references are added to either READ_BM or + WRITE_BM depending on the value of CHECKING_WRITE. */ + +static void +check_tree (ipa_reference_local_vars_info_t local, tree t, bool checking_write) +{ + if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) + 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. So just recurse and whatever we find, check it against + the read bitmaps. */ + + /* if (INDIRECT_REF_P (t) || TREE_CODE (t) == MEM_REF) */ + /* FIXME when we have array_ref's of pointers. */ + if (INDIRECT_REF_P (t)) + check_tree (local, TREE_OPERAND (t, 0), false); + + 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 (tree t) +{ + if (TREE_CODE (t) == ADDR_EXPR) + { + tree x = get_base_var (t); + if (TREE_CODE (x) == VAR_DECL) + if (has_proper_scope_for_analysis (x)) + bitmap_set_bit (module_statics_escape, DECL_UID (x)); + } +} + +/* Check to see if T is a read or address of operation on a static var + we are interested in analyzing. LOCAL is passed in to get access + to its bit vectors. Local is NULL if this is called from a static + initializer. */ + +static void +check_rhs_var (ipa_reference_local_vars_info_t local, tree t) +{ + look_for_address_of (t); + + if (local == NULL) + return; + + check_tree(local, t, false); +} + +/* Check to see if T is an assignment to a static var we are + interested in analyzing. LOCAL is passed in to get access to its bit + vectors. */ + +static void +check_lhs_var (ipa_reference_local_vars_info_t local, tree t) +{ + if (local == NULL) + return; + + 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. FN is the + function being analyzed and STMT is the actual asm statement. */ + +static void +get_asm_expr_operands (ipa_reference_local_vars_info_t 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->calls_read_all = true; + local->calls_write_all = true; + } +} + +/* Check the parameters of a function call from CALLER to CALL_EXPR to + see if any of them are static vars. Also check to see if this is + either an indirect call, a call outside the compilation unit, or + has special attributes that effect the clobbers. The caller + parameter is the tree node for the caller and the second operand is + the tree node for the entire call expression. */ + +static void +check_call (ipa_reference_local_vars_info_t 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); + 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); + } + + if (callee_t) + { + struct cgraph_node* callee = cgraph_node(callee_t); + avail = cgraph_function_body_availability (callee); + } + + if (avail == AVAIL_NOT_AVAILABLE || avail == AVAIL_OVERWRITABLE) + if (local) + { + if (flags & ECF_PURE) + local->calls_read_all = true; + else + { + local->calls_read_all = true; + local->calls_write_all = true; + } + } +} + +/* 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_for_static_refs (tree *tp, + int *walk_subtrees, + void *data) +{ + struct cgraph_node *fn = data; + tree t = *tp; + ipa_reference_local_vars_info_t local = NULL; + if (fn) + local = get_reference_vars_info_from_cgraph (fn)->local; + + switch (TREE_CODE (t)) + { + case VAR_DECL: + if (DECL_INITIAL (t)) + walk_tree (&DECL_INITIAL (t), scan_for_static_refs, 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->calls_read_all = true; + local->calls_write_all = true; + } + 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; +} + + +/* Lookup the tree node for the static variable that has UID. */ +static tree +get_static_decl (int index) +{ + splay_tree_node stn = + splay_tree_lookup (reference_vars_to_consider, index); + if (stn) + return (tree)stn->value; + return NULL; +} + +/* Lookup the tree node for the static variable that has UID and + conver the name to a string for debugging. */ + +static const char * +get_static_name (int index) +{ + splay_tree_node stn = + splay_tree_lookup (reference_vars_to_consider, index); + if (stn) + return lang_hooks.decl_printable_name ((tree)(stn->value), 2); + return NULL; +} + +/* Or in all of the bits from every callee into X, the caller's, bit + vector. There are several cases to check to avoid the sparse + bitmap oring. */ + +static void +propagate_bits (struct cgraph_node *x) +{ + ipa_reference_vars_info_t x_info = get_reference_vars_info_from_cgraph (x); + ipa_reference_global_vars_info_t x_global = x_info->global; + + struct cgraph_edge *e; + for (e = x->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) + { + if (get_reference_vars_info_from_cgraph (y)) + { + ipa_reference_vars_info_t y_info = get_reference_vars_info_from_cgraph (y); + ipa_reference_global_vars_info_t y_global = y_info->global; + + if (x_global->statics_read + != all_module_statics) + { + if (y_global->statics_read + == all_module_statics) + { + BITMAP_FREE (x_global->statics_read); + x_global->statics_read + = all_module_statics; + } + /* Skip bitmaps that are pointer equal to node's bitmap + (no reason to spin within the cycle). */ + else if (x_global->statics_read + != y_global->statics_read) + bitmap_ior_into (x_global->statics_read, + y_global->statics_read); + } + + if (x_global->statics_written + != all_module_statics) + { + if (y_global->statics_written + == all_module_statics) + { + BITMAP_FREE (x_global->statics_written); + x_global->statics_written + = all_module_statics; + } + /* Skip bitmaps that are pointer equal to node's bitmap + (no reason to spin within the cycle). */ + else if (x_global->statics_written + != y_global->statics_written) + bitmap_ior_into (x_global->statics_written, + y_global->statics_written); + } + } + else + { + gcc_unreachable (); + } + } + } +} + +/* Look at all of the callees of X to see which ones represent inlined + calls. For each of these callees, merge their local info into + TARGET and check their children recursively. + + This function goes away when Jan changes the inliner and IPA + analysis so that this is not run between the time when inlining + decisions are made and when the inlining actually occurs. */ + +static void +merge_callee_local_info (struct cgraph_node *target, + struct cgraph_node *x) +{ + struct cgraph_edge *e; + ipa_reference_local_vars_info_t x_l = + get_reference_vars_info_from_cgraph (target)->local; + + /* Make the world safe for tail recursion. */ + struct ipa_dfs_info *node_info = x->aux; + + if (node_info->aux) + return; + + node_info->aux = x; + + for (e = x->callees; e; e = e->next_callee) + { + struct cgraph_node *y = e->callee; + if (y->global.inlined_to) + { + ipa_reference_vars_info_t y_info; + ipa_reference_local_vars_info_t y_l; + struct cgraph_node* orig_y = y; + + y = cgraph_master_clone (y); + if (y) + { + y_info = get_reference_vars_info_from_cgraph (y); + y_l = y_info->local; + if (x_l != y_l) + { + bitmap_ior_into (x_l->statics_read, + y_l->statics_read); + bitmap_ior_into (x_l->statics_written, + y_l->statics_written); + } + x_l->calls_read_all |= y_l->calls_read_all; + x_l->calls_write_all |= y_l->calls_write_all; + merge_callee_local_info (target, y); + } + else + { + fprintf(stderr, "suspect inlining of "); + dump_cgraph_node (stderr, orig_y); + fprintf(stderr, "\ninto "); + dump_cgraph_node (stderr, target); + dump_cgraph (stderr); + gcc_assert(false); + } + } + } + + node_info->aux = NULL; +} + +/* The init routine for analyzing global static variable usage. See + comments at top for description. */ +static void +ipa_init (void) +{ + memory_identifier_string = build_string(7, "memory"); + + reference_vars_to_consider = + splay_tree_new_ggc (splay_tree_compare_ints); + + bitmap_obstack_initialize (&ipa_obstack); + module_statics_escape = BITMAP_ALLOC (&ipa_obstack); + module_statics_written = BITMAP_ALLOC (&ipa_obstack); + all_module_statics = BITMAP_ALLOC (&ipa_obstack); + + /* 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 (); +} + +/* Check out the rhs of a static or global initialization VNODE to see + if any of them contain addressof operations. Note that some of + these variables may not even be referenced in the code in this + compilation unit but their right hand sides may contain references + to variables defined within this unit. */ + +static void +analyze_variable (struct cgraph_varpool_node *vnode) +{ + tree global = vnode->decl; + if (TREE_CODE (global) == VAR_DECL) + { + if (DECL_INITIAL (global)) + walk_tree (&DECL_INITIAL (global), scan_for_static_refs, + NULL, visited_nodes); + } + else gcc_unreachable (); +} + +/* 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) +{ + ipa_reference_vars_info_t info + = xcalloc (1, sizeof (struct ipa_reference_vars_info_d)); + ipa_reference_local_vars_info_t l + = xcalloc (1, sizeof (struct ipa_reference_local_vars_info_d)); + tree decl = fn->decl; + + /* Add the info to the tree's annotation. */ + get_var_ann (fn->decl)->reference_vars_info = info; + + info->local = l; + l->statics_read = BITMAP_ALLOC (&ipa_obstack); + l->statics_written = BITMAP_ALLOC (&ipa_obstack); + + if (dump_file) + fprintf (dump_file, "\n local analysis of %s\n", cgraph_node_name (fn)); + + { + 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_for_static_refs, + fn, visited_nodes); + } + } + + /* There may be const decls with interesting right hand sides. */ + if (DECL_STRUCT_FUNCTION (decl)) + { + tree step; + for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list; + step; + step = TREE_CHAIN (step)) + { + tree var = TREE_VALUE (step); + if (TREE_CODE (var) == VAR_DECL + && DECL_INITIAL (var) + && !TREE_STATIC (var)) + walk_tree (&DECL_INITIAL (var), scan_for_static_refs, + fn, visited_nodes); + } + } +} + +/* If FN is avail == AVAIL_OVERWRITABLE, replace the effects bit + vectors with worst case bit vectors. We had to analyze it above to + find out if it took the address of any statics. However, now that + we know that, we can get rid of all of the other side effects. */ + +static void +clean_function (struct cgraph_node *fn) +{ + ipa_reference_vars_info_t info = get_reference_vars_info_from_cgraph (fn); + ipa_reference_local_vars_info_t l = info->local; + ipa_reference_global_vars_info_t g = info->global; + + if (l) + { + if (l->statics_read + && l->statics_read != all_module_statics) + BITMAP_FREE (l->statics_read); + if (l->statics_written + &&l->statics_written != all_module_statics) + BITMAP_FREE (l->statics_written); + free (l); + } + + if (g) + { + if (g->statics_read + && g->statics_read != all_module_statics) + BITMAP_FREE (g->statics_read); + + if (g->statics_written + && g->statics_written != all_module_statics) + BITMAP_FREE (g->statics_written); + + if (g->statics_not_read + && g->statics_not_read != all_module_statics) + BITMAP_FREE (g->statics_not_read); + + if (g->statics_not_written + && g->statics_not_written != all_module_statics) + BITMAP_FREE (g->statics_not_written); + free (g); + } + + + free (get_var_ann (fn->decl)->reference_vars_info); + get_var_ann (fn->decl)->reference_vars_info = NULL; +} + + +/* 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 void +static_execute (void) +{ + struct cgraph_node *node; + struct cgraph_varpool_node *vnode; + struct cgraph_node *w; + struct cgraph_node **order = + xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); + int order_pos = order_pos = ipa_utils_reduced_inorder (order, false, true); + int i; + + ipa_init (); + + /* Process all of the variables first. */ + for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) + analyze_variable (vnode); + + /* Process all of the functions next. + + We do not want to process any of the clones so we check that this + is a master clone. However, we do need to process any + AVAIL_OVERWRITABLE functions (these are never clones) because + they may cause a static variable to escape. The code that can + overwrite such a function cannot access the statics because it + would not be in the same compilation unit. When the analysis is + finished, the computed information of these AVAIL_OVERWRITABLE is + replaced with worst case info. + */ + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed + && (cgraph_is_master_clone (node) + || (cgraph_function_body_availability (node) + == AVAIL_OVERWRITABLE))) + analyze_function (node); + + pointer_set_destroy (visited_nodes); + visited_nodes = NULL; + if (dump_file) + dump_cgraph (dump_file); + + /* Prune out the variables that were found to behave badly + (i.e. have their address taken). */ + { + unsigned int index; + bitmap_iterator bi; + bitmap module_statics_readonly = BITMAP_ALLOC (&ipa_obstack); + bitmap module_statics_const = BITMAP_ALLOC (&ipa_obstack); + bitmap bm_temp = BITMAP_ALLOC (&ipa_obstack); + + EXECUTE_IF_SET_IN_BITMAP (module_statics_escape, 0, index, bi) + { + splay_tree_remove (reference_vars_to_consider, index); + } + + bitmap_and_compl_into (all_module_statics, + module_statics_escape); + + bitmap_and_compl (module_statics_readonly, all_module_statics, + module_statics_written); + + /* If the address is not taken, we can unset the addressable bit + on this variable. */ + EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi) + { + tree var = get_static_decl (index); + TREE_ADDRESSABLE (var) = 0; + if (dump_file) + fprintf (dump_file, "Not TREE_ADDRESSABLE var %s\n", + get_static_name (index)); + } + + /* If the variable is never written, we can set the TREE_READONLY + flag. Additionally if it has a DECL_INITIAL that is made up of + constants we can treat the entire global as a constant. */ + + bitmap_and_compl (module_statics_readonly, all_module_statics, + module_statics_written); + EXECUTE_IF_SET_IN_BITMAP (module_statics_readonly, 0, index, bi) + { + tree var = get_static_decl (index); + TREE_READONLY (var) = 1; + if (dump_file) + fprintf (dump_file, "read-only var %s\n", + get_static_name (index)); + if (DECL_INITIAL (var) + && is_gimple_min_invariant (DECL_INITIAL (var))) + { + bitmap_set_bit (module_statics_const, index); + if (dump_file) + fprintf (dump_file, "read-only constant %s\n", + get_static_name (index)); + } + } + + BITMAP_FREE(module_statics_escape); + BITMAP_FREE(module_statics_written); + + if (dump_file) + EXECUTE_IF_SET_IN_BITMAP (all_module_statics, 0, index, bi) + { + fprintf (dump_file, "\nPromotable global:%s", + get_static_name (index)); + } + + for (i = 0; i < order_pos; i++ ) + { + ipa_reference_local_vars_info_t l; + node = order[i]; + l = get_reference_vars_info_from_cgraph (node)->local; + + /* Any variables that are not in all_module_statics are + removed from the local maps. This will include all of the + variables that were found to escape in the function + scanning. */ + bitmap_and_into (l->statics_read, + all_module_statics); + bitmap_and_into (l->statics_written, + all_module_statics); + } + + BITMAP_FREE(module_statics_readonly); + BITMAP_FREE(module_statics_const); + BITMAP_FREE(bm_temp); + } + + if (dump_file) + { + for (i = 0; i < order_pos; i++ ) + { + unsigned int index; + ipa_reference_local_vars_info_t l; + bitmap_iterator bi; + + node = order[i]; + l = get_reference_vars_info_from_cgraph (node)->local; + fprintf (dump_file, + "\nFunction name:%s/%i:", + cgraph_node_name (node), node->uid); + fprintf (dump_file, "\n locals read: "); + EXECUTE_IF_SET_IN_BITMAP (l->statics_read, + 0, index, bi) + { + fprintf (dump_file, "%s ", + get_static_name (index)); + } + fprintf (dump_file, "\n locals written: "); + EXECUTE_IF_SET_IN_BITMAP (l->statics_written, + 0, index, bi) + { + fprintf(dump_file, "%s ", + get_static_name (index)); + } + } + } + + /* 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. */ + order_pos = ipa_utils_reduced_inorder (order, true, true); + if (dump_file) + ipa_utils_print_order(dump_file, "reduced", order, order_pos); + + for (i = 0; i < order_pos; i++ ) + { + ipa_reference_vars_info_t node_info; + ipa_reference_global_vars_info_t node_g = + xcalloc (1, sizeof (struct ipa_reference_global_vars_info_d)); + ipa_reference_local_vars_info_t node_l; + + bool read_all; + bool write_all; + struct ipa_dfs_info * w_info; + + node = order[i]; + node_info = get_reference_vars_info_from_cgraph (node); + if (!node_info) + { + dump_cgraph_node (stderr, node); + dump_cgraph (stderr); + gcc_unreachable (); + } + + node_info->global = node_g; + node_l = node_info->local; + + read_all = node_l->calls_read_all; + write_all = node_l->calls_write_all; + + /* If any node in a cycle is calls_read_all or calls_write_all + they all are. */ + w_info = node->aux; + w = w_info->next_cycle; + while (w) + { + ipa_reference_local_vars_info_t w_l = + get_reference_vars_info_from_cgraph (w)->local; + read_all |= w_l->calls_read_all; + write_all |= w_l->calls_write_all; + + w_info = w->aux; + w = w_info->next_cycle; + } + + /* Initialized the bitmaps for the reduced nodes */ + if (read_all) + node_g->statics_read = all_module_statics; + else + { + node_g->statics_read = BITMAP_ALLOC (&ipa_obstack); + bitmap_copy (node_g->statics_read, + node_l->statics_read); + } + + if (write_all) + node_g->statics_written = all_module_statics; + else + { + node_g->statics_written = BITMAP_ALLOC (&ipa_obstack); + bitmap_copy (node_g->statics_written, + node_l->statics_written); + } + + w_info = node->aux; + w = w_info->next_cycle; + while (w) + { + ipa_reference_vars_info_t w_ri = + get_reference_vars_info_from_cgraph (w); + ipa_reference_local_vars_info_t w_l = w_ri->local; + + /* All nodes within a cycle share the same global info bitmaps. */ + w_ri->global = node_g; + + /* These global bitmaps are initialized from the local info + of all of the nodes in the region. However there is no + need to do any work if the bitmaps were set to + all_module_statics. */ + if (!read_all) + bitmap_ior_into (node_g->statics_read, + w_l->statics_read); + if (!write_all) + bitmap_ior_into (node_g->statics_written, + w_l->statics_written); + w_info = w->aux; + w = w_info->next_cycle; + } + + w = node; + while (w) + { + propagate_bits (w); + w_info = w->aux; + w = w_info->next_cycle; + } + } + + /* Need to fix up the local information sets. The information that + has been gathered so far is preinlining. However, the + compilation will progress post inlining so the local sets for the + inlined calls need to be merged into the callers. Note that the + local sets are not shared between all of the nodes in a cycle so + those nodes in the cycle must be processed explicitly. */ + for (i = 0; i < order_pos; i++ ) + { + struct ipa_dfs_info * w_info; + node = order[i]; + merge_callee_local_info (node, node); + + w_info = node->aux; + w = w_info->next_cycle; + while (w) + { + merge_callee_local_info (w, w); + w_info = w->aux; + w = w_info->next_cycle; + } + } + + if (dump_file) + { + for (i = 0; i < order_pos; i++ ) + { + ipa_reference_vars_info_t node_info; + ipa_reference_global_vars_info_t node_g; + ipa_reference_local_vars_info_t node_l; + unsigned int index; + bitmap_iterator bi; + struct ipa_dfs_info * w_info; + + node = order[i]; + node_info = get_reference_vars_info_from_cgraph (node); + node_g = node_info->global; + node_l = node_info->local; + fprintf (dump_file, + "\nFunction name:%s/%i:", + cgraph_node_name (node), node->uid); + fprintf (dump_file, "\n locals read: "); + EXECUTE_IF_SET_IN_BITMAP (node_l->statics_read, + 0, index, bi) + { + fprintf (dump_file, "%s ", + get_static_name (index)); + } + fprintf (dump_file, "\n locals written: "); + EXECUTE_IF_SET_IN_BITMAP (node_l->statics_written, + 0, index, bi) + { + fprintf(dump_file, "%s ", + get_static_name (index)); + } + + w_info = node->aux; + w = w_info->next_cycle; + while (w) + { + ipa_reference_vars_info_t w_ri = + get_reference_vars_info_from_cgraph (w); + ipa_reference_local_vars_info_t w_l = w_ri->local; + fprintf (dump_file, "\n next cycle: %s/%i ", + cgraph_node_name (w), w->uid); + fprintf (dump_file, "\n locals read: "); + EXECUTE_IF_SET_IN_BITMAP (w_l->statics_read, + 0, index, bi) + { + fprintf (dump_file, "%s ", + get_static_name (index)); + } + + fprintf (dump_file, "\n locals written: "); + EXECUTE_IF_SET_IN_BITMAP (w_l->statics_written, + 0, index, bi) + { + fprintf(dump_file, "%s ", + get_static_name (index)); + } + + + w_info = w->aux; + w = w_info->next_cycle; + } + fprintf (dump_file, "\n globals read: "); + EXECUTE_IF_SET_IN_BITMAP (node_g->statics_read, + 0, index, bi) + { + fprintf (dump_file, "%s ", + get_static_name (index)); + } + fprintf (dump_file, "\n globals written: "); + EXECUTE_IF_SET_IN_BITMAP (node_g->statics_written, + 0, index, bi) + { + fprintf (dump_file, "%s ", + get_static_name (index)); + } + } + } + + /* Cleanup. */ + for (i = 0; i < order_pos; i++ ) + { + ipa_reference_vars_info_t node_info; + ipa_reference_global_vars_info_t node_g; + node = order[i]; + node_info = get_reference_vars_info_from_cgraph (node); + node_g = node_info->global; + + /* Create the complimentary sets. These are more useful for + certain apis. */ + node_g->statics_not_read = BITMAP_ALLOC (&ipa_obstack); + node_g->statics_not_written = BITMAP_ALLOC (&ipa_obstack); + + if (node_g->statics_read != all_module_statics) + { + bitmap_and_compl (node_g->statics_not_read, + all_module_statics, + node_g->statics_read); + } + + if (node_g->statics_written + != all_module_statics) + bitmap_and_compl (node_g->statics_not_written, + all_module_statics, + node_g->statics_written); + } + + free (order); + + for (node = cgraph_nodes; node; node = node->next) + { + /* Get rid of the aux information. */ + + if (node->aux) + { + free (node->aux); + node->aux = NULL; + } + + if (node->analyzed + && (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE)) + clean_function (node); + } +} + + +static bool +gate_reference (void) +{ + return (flag_unit_at_a_time != 0 && flag_ipa_reference + /* Don't bother doing anything if the program has errors. */ + && !(errorcount || sorrycount)); +} + +struct tree_opt_pass pass_ipa_reference = +{ + "static-var", /* name */ + gate_reference, /* gate */ + static_execute, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_IPA_REFERENCE, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ + 0 /* letter */ +}; + +#include "gt-ipa-reference.h" + diff --git a/gcc/ipa-reference.h b/gcc/ipa-reference.h new file mode 100644 index 00000000000..26dce15afc4 --- /dev/null +++ b/gcc/ipa-reference.h @@ -0,0 +1,83 @@ +/* IPA handling of references. + 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, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#ifndef GCC_IPA_REFERENCE_H +#define GCC_IPA_REFERENCE_H +#include "bitmap.h" +#include "tree.h" + +/* The static variables defined within the compilation unit that are + loaded or stored directly by function that owns this structure. */ + +struct ipa_reference_local_vars_info_d +{ + bitmap statics_read; + bitmap statics_written; + + /* Set when this function calls another function external to the + compilation unit or if the function has a asm clobber of memory. + In general, such calls are modeled as reading and writing all + variables (both bits on) but sometime there are attributes on the + called function so we can do better. */ + bool calls_read_all; + bool calls_write_all; +}; + +struct ipa_reference_global_vars_info_d +{ + bitmap statics_read; + bitmap statics_written; + bitmap statics_not_read; + bitmap statics_not_written; +}; + +/* Statics that are read and written by some set of functions. The + local ones are based on the loads and stores local to the function. + The global ones are based on the local info as well as the + transitive closure of the functions that are called. The + structures are separated to allow the global structures to be + shared between several functions since every function within a + strongly connected component will have the same information. This + sharing saves both time and space in the computation of the vectors + as well as their translation from decl_uid form to ann_uid + form. */ + +typedef struct ipa_reference_local_vars_info_d *ipa_reference_local_vars_info_t; +typedef struct ipa_reference_global_vars_info_d *ipa_reference_global_vars_info_t; + +struct ipa_reference_vars_info_d +{ + ipa_reference_local_vars_info_t local; + ipa_reference_global_vars_info_t global; +}; + +typedef struct ipa_reference_vars_info_d *ipa_reference_vars_info_t; + +/* In ipa-reference.c */ +bitmap ipa_reference_get_read_local (tree fn); +bitmap ipa_reference_get_written_local (tree fn); +bitmap ipa_reference_get_read_global (tree fn); +bitmap ipa_reference_get_written_global (tree fn); +bitmap ipa_reference_get_not_read_global (tree fn); +bitmap ipa_reference_get_not_written_global (tree fn); + +#endif /* GCC_IPA_REFERENCE_H */ + diff --git a/gcc/ipa-type-escape.c b/gcc/ipa-type-escape.c new file mode 100644 index 00000000000..289598d4bb8 --- /dev/null +++ b/gcc/ipa-type-escape.c @@ -0,0 +1,1854 @@ +/* Type based alias analysis. + 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, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +/* This pass determines which types in the program contain only + instances that are completely encapsulated by the compilation unit. + Those types that are encapsulated must also pass the further + requirement that there be no bad operations on any instances of + those types. + + A great deal of freedom in compilation is allowed for the instances + of those types that pass these conditions. +*/ + +/* The code in this module is called by the ipa pass manager. It + should be one of the later passes since its 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 "ipa-type-escape.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" + +/* Some of the aliasing is called very early, before this phase is + called. To assure that this is not a problem, we keep track of if + this phase has been run. */ +static bool initialized = false; + +/* This bitmap contains the set of local vars that are the lhs of + calls to mallocs. These variables, when seen on the rhs as part of + a cast, the cast are not marked as doing bad things to the type + even though they are generally of the form + "foo = (type_of_foo)void_temp". */ +static bitmap results_of_malloc; + +/* Scratch bitmap for avoiding work. */ +static bitmap been_there_done_that; +static bitmap bitmap_tmp; + +/* There are two levels of escape that types can undergo. + + EXPOSED_PARAMETER - some instance of the variable is + passed by value into an externally visible function or some + instance of the variable is passed out of an externally visible + function as a return value. In this case any of the fields of the + variable that are pointer types end up having their types marked as + FULL_ESCAPE. + + FULL_ESCAPE - when bad things happen to good types. One of the + following things happens to the type: (a) either an instance of the + variable has its address passed to an externally visible function, + (b) the address is taken and some bad cast happens to the address + or (c) explicit arithmetic is done to the address. +*/ + +enum escape_t +{ + EXPOSED_PARAMETER, + FULL_ESCAPE +}; + +/* The following two bit vectors global_types_* correspond to + previous cases above. During the analysis phase, a bit is set in + one of these vectors if an operation of the offending class is + discovered to happen on the associated type. */ + +static bitmap global_types_exposed_parameter; +static bitmap global_types_full_escape; + +/* All of the types seen in this compilation unit. */ +static bitmap global_types_seen; +/* Reverse map to take a canon uid and map it to a canon type. Uid's + are never manipulated unless they are associated with a canon + type. */ +static splay_tree uid_to_canon_type; + +/* Internal structure of type mapping code. This maps a canon type + name to its canon type. */ +static splay_tree all_canon_types; + +/* Map from type clones to the single canon type. */ +static splay_tree type_to_canon_type; + +/* A splay tree of bitmaps. An element X in the splay tree has a bit + set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (Y)) if there was + an operation in the program of the form "&X.Y". */ +static splay_tree uid_to_addressof_down_map; + +/* A splay tree of bitmaps. An element Y in the splay tree has a bit + set in its bitmap at TYPE_UID (TYPE_MAIN_VARIANT (X)) if there was + an operation in the program of the form "&X.Y". */ +static splay_tree uid_to_addressof_up_map; + +/* Tree to hold the subtype maps used to mark subtypes of escaped + types. */ +static splay_tree uid_to_subtype_map; + +/* Records tree nodes seen in cgraph_create_edges. Simply using + walk_tree_without_duplicates doesn't guarantee each node is visited + once because it gets a new htab upon each recursive call from + scan_for_refs. */ +static struct pointer_set_t *visited_nodes; + +static bitmap_obstack ipa_obstack; + +/* Get the name of TYPE or return the string "<UNNAMED>". */ +static char* +get_name_of_type (tree type) +{ + tree name = TYPE_NAME (type); + + if (!name) + /* Unnamed type, do what you like here. */ + return (char*)"<UNNAMED>"; + + /* It will be a TYPE_DECL in the case of a typedef, otherwise, an + identifier_node */ + if (TREE_CODE (name) == TYPE_DECL) + { + /* Each DECL has a DECL_NAME field which contains an + IDENTIFIER_NODE. (Some decls, most often labels, may have + zero as the DECL_NAME). */ + if (DECL_NAME (name)) + return (char*)IDENTIFIER_POINTER (DECL_NAME (name)); + else + /* Unnamed type, do what you like here. */ + return (char*)"<UNNAMED>"; + } + else if (TREE_CODE (name) == IDENTIFIER_NODE) + return (char*)IDENTIFIER_POINTER (name); + else + return (char*)"<UNNAMED>"; +} + +struct type_brand_s +{ + char* name; + int seq; +}; + +/* Splay tree comparison function on type_brand_s structures. */ + +static int +compare_type_brand (splay_tree_key sk1, splay_tree_key sk2) +{ + struct type_brand_s * k1 = (struct type_brand_s *) sk1; + struct type_brand_s * k2 = (struct type_brand_s *) sk2; + + int value = strcmp(k1->name, k2->name); + if (value == 0) + return k2->seq - k1->seq; + else + return value; +} + +/* All of the "unique_type" code is a hack to get around the sleazy + implementation used to compile more than file. Currently gcc does + not get rid of multiple instances of the same type that have been + collected from different compilation units. */ +/* This is a trivial algorithm for removing duplicate types. This + would not work for any language that used structural equivalence as + the basis of its type system. */ +/* Return either TYPE if this is first time TYPE has been seen an + compatible TYPE that has already been processed. */ + +static tree +discover_unique_type (tree type) +{ + struct type_brand_s * brand = xmalloc(sizeof(struct type_brand_s)); + int i = 0; + splay_tree_node result; + + while (1) + { + brand->name = get_name_of_type (type); + brand->seq = i; + result = splay_tree_lookup (all_canon_types, (splay_tree_key) brand); + if (result) + { + /* Create an alias since this is just the same as + other_type. */ + tree other_type = (tree) result->value; + if (lang_hooks.types_compatible_p (type, other_type) == 1) + { + free (brand); + /* Insert this new type as an alias for other_type. */ + splay_tree_insert (type_to_canon_type, + (splay_tree_key) type, + (splay_tree_value) other_type); + return other_type; + } + /* Not compatible, look for next instance with same name. */ + } + else + { + /* No more instances, create new one since this is the first + time we saw this type. */ + brand->seq = i++; + /* Insert the new brand. */ + splay_tree_insert (all_canon_types, + (splay_tree_key) brand, + (splay_tree_value) type); + + /* Insert this new type as an alias for itself. */ + splay_tree_insert (type_to_canon_type, + (splay_tree_key) type, + (splay_tree_value) type); + + /* Insert the uid for reverse lookup; */ + splay_tree_insert (uid_to_canon_type, + (splay_tree_key) TYPE_UID (type), + (splay_tree_value) type); + + bitmap_set_bit (global_types_seen, TYPE_UID (type)); + return type; + } + i++; + } +} + +/* Return true if TYPE is one of the type classes that we are willing + to analyze. This skips the goofy types like arrays of pointers to + methods. */ +static bool +type_to_consider (tree type) +{ + /* Strip the *'s off. */ + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + + switch (TREE_CODE (type)) + { + case BOOLEAN_TYPE: + case CHAR_TYPE: + case COMPLEX_TYPE: + case ENUMERAL_TYPE: + case INTEGER_TYPE: + case QUAL_UNION_TYPE: + case REAL_TYPE: + case RECORD_TYPE: + case UNION_TYPE: + case VECTOR_TYPE: + case VOID_TYPE: + return true; + + default: + return false; + } +} + +/* Get the canon type of TYPE. If SEE_THRU_PTRS is true, remove all + the POINTER_TOs and if SEE_THRU_ARRAYS is true, remove all of the + ARRAY_OFs and POINTER_TOs. */ + +static tree +get_canon_type (tree type, bool see_thru_ptrs, bool see_thru_arrays) +{ + splay_tree_node result; + /* Strip the *'s off. */ + if (!type || !type_to_consider (type)) + return NULL; + + type = TYPE_MAIN_VARIANT (type); + if (see_thru_arrays) + while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + + else if (see_thru_ptrs) + while (POINTER_TYPE_P (type)) + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + + result = splay_tree_lookup(type_to_canon_type, (splay_tree_key) type); + + if (result == NULL) + return discover_unique_type (type); + else return (tree) result->value; +} + +/* Same as GET_CANON_TYPE, except return the TYPE_ID rather than the + TYPE. */ + +static int +get_canon_type_uid (tree type, bool see_thru_ptrs, bool see_thru_arrays) +{ + type = get_canon_type (type, see_thru_ptrs, see_thru_arrays); + if (type) + return TYPE_UID(type); + else return 0; +} + +/* Return 0 if TYPE is a record or union type. Return a positive + number if TYPE is a pointer to a record or union. The number is + the number of pointer types stripped to get to the record or union + type. Return -1 if TYPE is none of the above. */ + +int +ipa_type_escape_star_count_of_interesting_type (tree type) +{ + int count = 0; + /* Strip the *'s off. */ + if (!type) + return -1; + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type)) + { + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + count++; + } + + /* We are interested in records, and unions only. */ + if (TREE_CODE (type) == RECORD_TYPE + || TREE_CODE (type) == QUAL_UNION_TYPE + || TREE_CODE (type) == UNION_TYPE) + return count; + else + return -1; +} + + +/* Return 0 if TYPE is a record or union type. Return a positive + number if TYPE is a pointer to a record or union. The number is + the number of pointer types stripped to get to the record or union + type. Return -1 if TYPE is none of the above. */ + +int +ipa_type_escape_star_count_of_interesting_or_array_type (tree type) +{ + int count = 0; + /* Strip the *'s off. */ + if (!type) + return -1; + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type) || TREE_CODE (type) == ARRAY_TYPE) + { + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + count++; + } + + /* We are interested in records, and unions only. */ + if (TREE_CODE (type) == RECORD_TYPE + || TREE_CODE (type) == QUAL_UNION_TYPE + || TREE_CODE (type) == UNION_TYPE) + return count; + else + return -1; +} + + +/* Return true if the record, or union TYPE passed in escapes this + compilation unit. Note that all of the pointer-to's are removed + before testing since these may not be correct. */ + +bool +ipa_type_escape_type_contained_p (tree type) +{ + if (!initialized) + return false; + return !bitmap_bit_p (global_types_full_escape, + get_canon_type_uid (type, true, false)); +} + +/* Return true a modification to a field of type FIELD_TYPE cannot + clobber a record of RECORD_TYPE. */ + +bool +ipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type) +{ + splay_tree_node result; + int uid; + + if (!initialized) + return false; + + /* Strip off all of the pointer tos on the record type. Strip the + same number of pointer tos from the field type. If the field + type has fewer, it could not have been aliased. */ + record_type = TYPE_MAIN_VARIANT (record_type); + field_type = TYPE_MAIN_VARIANT (field_type); + while (POINTER_TYPE_P (record_type)) + { + record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); + if (POINTER_TYPE_P (field_type)) + field_type = TYPE_MAIN_VARIANT (TREE_TYPE (field_type)); + else + /* However, if field_type is a union, this quick test is not + correct since one of the variants of the union may be a + pointer to type and we cannot see across that here. So we + just strip the remaining pointer tos off the record type + and fall thru to the more precise code. */ + if (TREE_CODE (field_type) == QUAL_UNION_TYPE + || TREE_CODE (field_type) == UNION_TYPE) + { + while (POINTER_TYPE_P (record_type)) + record_type = TYPE_MAIN_VARIANT (TREE_TYPE (record_type)); + break; + } + else + return true; + } + + record_type = get_canon_type (record_type, true, true); + /* The record type must be contained. The field type may + escape. */ + if (!ipa_type_escape_type_contained_p (record_type)) + return false; + + uid = TYPE_UID (record_type); + result = splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); + + if (result) + { + bitmap field_type_map = (bitmap) result->value; + uid = get_canon_type_uid (field_type, true, true); + /* If the bit is there, the address was taken. If not, it + wasn't. */ + return !bitmap_bit_p (field_type_map, uid); + } + else + /* No bitmap means no addresses were taken. */ + return true; +} + + +/* Add TYPE to the suspect type set. Return true if the bit needed to + be marked. */ + +static tree +mark_type (tree type, enum escape_t escape_status) +{ + bitmap map = NULL; + int uid; + + type = get_canon_type (type, true, true); + if (!type) + return NULL; + + switch (escape_status) + { + case EXPOSED_PARAMETER: + map = global_types_exposed_parameter; + break; + case FULL_ESCAPE: + map = global_types_full_escape; + break; + } + + uid = TYPE_UID (type); + if (bitmap_bit_p (map, uid)) + return type; + else + { + bitmap_set_bit (map, uid); + if (escape_status == FULL_ESCAPE) + { + /* Effeciency hack. When things are bad, do not mess around + with this type anymore. */ + bitmap_set_bit (global_types_exposed_parameter, uid); + } + } + return type; +} + +/* Add interesting TYPE to the suspect type set. If the set is + EXPOSED_PARAMETER and the TYPE is a pointer type, the set is + changed to FULL_ESCAPE. */ + +static void +mark_interesting_type (tree type, enum escape_t escape_status) +{ + if (!type) return; + if (ipa_type_escape_star_count_of_interesting_type (type) >= 0) + { + if ((escape_status == EXPOSED_PARAMETER) + && POINTER_TYPE_P (type)) + /* EXPOSED_PARAMETERs are only structs or unions are passed by + value. Anything passed by reference to an external + function fully exposes the type. */ + mark_type (type, FULL_ESCAPE); + else + mark_type (type, escape_status); + } +} + +/* Return true if PARENT is supertype of CHILD. Both types must be + known to be structures or unions. */ + +static bool +parent_type_p (tree parent, tree child) +{ + int i; + tree binfo, base_binfo; + if (TYPE_BINFO (parent)) + for (binfo = TYPE_BINFO (parent), i = 0; + BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) + { + tree binfotype = BINFO_TYPE (base_binfo); + if (binfotype == child) + return true; + else if (parent_type_p (binfotype, child)) + return true; + } + if (TREE_CODE (parent) == UNION_TYPE + || TREE_CODE (parent) == QUAL_UNION_TYPE) + { + tree field; + /* Search all of the variants in the union to see if one of them + is the child. */ + for (field = TYPE_FIELDS (parent); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (field_type == child) + return true; + } + + /* If we did not find it, recursively ask the variants if one of + their children is the child type. */ + for (field = TYPE_FIELDS (parent); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (TREE_CODE (field_type) == RECORD_TYPE + || TREE_CODE (field_type) == QUAL_UNION_TYPE + || TREE_CODE (field_type) == UNION_TYPE) + if (parent_type_p (field_type, child)) + return true; + } + } + + if (TREE_CODE (parent) == RECORD_TYPE) + { + tree field; + for (field = TYPE_FIELDS (parent); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (field_type == child) + return true; + /* You can only cast to the first field so if it does not + match, quit. */ + if (TREE_CODE (field_type) == RECORD_TYPE + || TREE_CODE (field_type) == QUAL_UNION_TYPE + || TREE_CODE (field_type) == UNION_TYPE) + { + if (parent_type_p (field_type, child)) + return true; + else + break; + } + } + } + return false; +} + +/* Return the number of pointer tos for TYPE and return TYPE with all + of these stripped off. */ + +static int +count_stars (tree* type_ptr) +{ + tree type = *type_ptr; + int i = 0; + type = TYPE_MAIN_VARIANT (type); + while (POINTER_TYPE_P (type)) + { + type = TYPE_MAIN_VARIANT (TREE_TYPE (type)); + i++; + } + + *type_ptr = type; + return i; +} + +enum cast_type { + CT_UP, + CT_DOWN, + CT_SIDEWAYS, + CT_USELESS +}; + +/* Check the cast FROM_TYPE to TO_TYPE. This function requires that + the two types have already passed the + ipa_type_escape_star_count_of_interesting_type test. */ + +static enum cast_type +check_cast_type (tree to_type, tree from_type) +{ + int to_stars = count_stars (&to_type); + int from_stars = count_stars (&from_type); + if (to_stars != from_stars) + return CT_SIDEWAYS; + + if (to_type == from_type) + return CT_USELESS; + + if (parent_type_p (to_type, from_type)) return CT_UP; + if (parent_type_p (from_type, to_type)) return CT_DOWN; + return CT_SIDEWAYS; +} + +/* Check a cast FROM this variable, TO_TYPE. Mark the escaping types + if appropriate. */ +static void +check_cast (tree to_type, tree from) +{ + tree from_type = get_canon_type (TREE_TYPE (from), false, false); + bool to_interesting_type, from_interesting_type; + + to_type = get_canon_type (to_type, false, false); + if (!from_type || !to_type || from_type == to_type) + return; + + to_interesting_type = + ipa_type_escape_star_count_of_interesting_type (to_type) >= 0; + from_interesting_type = + ipa_type_escape_star_count_of_interesting_type (from_type) >= 0; + + if (to_interesting_type) + if (from_interesting_type) + { + /* Both types are interesting. This can be one of four types + of cast: useless, up, down, or sideways. We do not care + about up or useless. Sideways casts are always bad and + both sides get marked as escaping. Downcasts are not + interesting here because if type is marked as escaping, all + of its subtypes escape. */ + switch (check_cast_type (to_type, from_type)) + { + case CT_UP: + case CT_USELESS: + case CT_DOWN: + break; + + case CT_SIDEWAYS: + mark_type (to_type, FULL_ESCAPE); + mark_type (from_type, FULL_ESCAPE); + break; + } + } + else + { + /* If this is a cast from the local that is a result from a + call to malloc, do not mark the cast as bad. */ + if (DECL_P (from) && !bitmap_bit_p (results_of_malloc, DECL_UID (from))) + mark_type (to_type, FULL_ESCAPE); + } + else if (from_interesting_type) + mark_type (from_type, FULL_ESCAPE); +} + +/* Register the parameter and return types of function FN. The type + ESCAPES if the function is visible outside of the compilation + unit. */ +static void +check_function_parameter_and_return_types (tree fn, bool escapes) +{ + tree arg; + + if (TYPE_ARG_TYPES (TREE_TYPE (fn))) + { + for (arg = TYPE_ARG_TYPES (TREE_TYPE (fn)); + arg && TREE_VALUE (arg) != void_type_node; + arg = TREE_CHAIN (arg)) + { + tree type = get_canon_type (TREE_VALUE (arg), false, false); + if (escapes) + mark_interesting_type (type, EXPOSED_PARAMETER); + } + } + else + { + /* FIXME - According to Geoff Keating, we should never have to + do this; the front ends should always process the arg list + from the TYPE_ARG_LIST. However, Geoff is wrong, this code + does seem to be live. */ + + for (arg = DECL_ARGUMENTS (fn); arg; arg = TREE_CHAIN (arg)) + { + tree type = get_canon_type (TREE_TYPE (arg), false, false); + if (escapes) + mark_interesting_type (type, EXPOSED_PARAMETER); + } + } + if (escapes) + { + tree type = get_canon_type (TREE_TYPE (TREE_TYPE (fn)), false, false); + mark_interesting_type (type, EXPOSED_PARAMETER); + } +} + +/* Return true if the variable T is the right kind of static variable to + perform compilation unit scope escape analysis. */ + +static inline void +has_proper_scope_for_analysis (tree t) +{ + /* If the variable has the "used" attribute, treat it as if it had a + been touched by the devil. */ + tree type = get_canon_type (TREE_TYPE (t), false, false); + if (!type) return; + + if (lookup_attribute ("used", DECL_ATTRIBUTES (t))) + { + mark_interesting_type (type, FULL_ESCAPE); + 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)) + return; + + /* Do not care about a local automatic that is not static. */ + if (!TREE_STATIC (t) && !DECL_EXTERNAL (t)) + return; + + 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 + { + /* The type escapes for all public and externs. */ + mark_interesting_type (type, FULL_ESCAPE); + } + } +} + +/* If T is a VAR_DECL for a static that we are interested in, add the + uid to the bitmap. */ + +static void +check_operand (tree t) +{ + if (!t) return; + + /* This is an assignment from a function, register the types as + escaping. */ + if (TREE_CODE (t) == FUNCTION_DECL) + check_function_parameter_and_return_types (t, true); + + else if (TREE_CODE (t) == VAR_DECL) + has_proper_scope_for_analysis (t); +} + +/* Examine tree T for references. */ + +static void +check_tree (tree t) +{ + if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) + return; + + while (TREE_CODE (t) == REALPART_EXPR + || TREE_CODE (t) == IMAGPART_EXPR + || handled_component_p (t)) + { + if (TREE_CODE (t) == ARRAY_REF) + check_operand (TREE_OPERAND (t, 1)); + t = TREE_OPERAND (t, 0); + } + + if (INDIRECT_REF_P (t)) +/* || TREE_CODE (t) == MEM_REF) */ + check_tree (TREE_OPERAND (t, 0)); + + if (SSA_VAR_P (t) || (TREE_CODE (t) == FUNCTION_DECL)) + check_operand (t); +} + +/* Create an address_of edge FROM_TYPE.TO_TYPE. */ +static void +mark_interesting_addressof (tree to_type, tree from_type) +{ + int from_uid; + int to_uid; + bitmap type_map; + splay_tree_node result; + + from_type = get_canon_type (from_type, false, false); + to_type = get_canon_type (to_type, false, false); + + if (!from_type || !to_type) + return; + + from_uid = TYPE_UID (from_type); + to_uid = TYPE_UID (to_type); + + gcc_assert (ipa_type_escape_star_count_of_interesting_type (from_type) == 0); + + /* Process the Y into X map pointer. */ + result = splay_tree_lookup (uid_to_addressof_down_map, + (splay_tree_key) from_uid); + + if (result) + type_map = (bitmap) result->value; + else + { + type_map = BITMAP_ALLOC (&ipa_obstack); + splay_tree_insert (uid_to_addressof_down_map, + from_uid, + (splay_tree_value)type_map); + } + bitmap_set_bit (type_map, TYPE_UID (to_type)); + + /* Process the X into Y reverse map pointer. */ + result = + splay_tree_lookup (uid_to_addressof_up_map, (splay_tree_key) to_uid); + + if (result) + type_map = (bitmap) result->value; + else + { + type_map = BITMAP_ALLOC (&ipa_obstack); + splay_tree_insert (uid_to_addressof_up_map, + to_uid, + (splay_tree_value)type_map); + } + bitmap_set_bit (type_map, TYPE_UID (to_type)); +} + +/* Scan tree T to see if there are any addresses taken in within T. */ + +static void +look_for_address_of (tree t) +{ + if (TREE_CODE (t) == ADDR_EXPR) + { + tree x = get_base_var (t); + tree cref = TREE_OPERAND (t, 0); + + /* If we have an expression of the form "&a.b.c.d", mark a.b, + b.c and c.d. as having its address taken. */ + tree fielddecl = NULL_TREE; + while (cref!= x) + { + if (TREE_CODE (cref) == COMPONENT_REF) + { + fielddecl = TREE_OPERAND (cref, 1); + mark_interesting_addressof (TREE_TYPE (fielddecl), + DECL_FIELD_CONTEXT (fielddecl)); + } + else if (TREE_CODE (cref) == ARRAY_REF) + get_canon_type (TREE_TYPE (cref), false, false); + + cref = TREE_OPERAND (cref, 0); + } + + if (TREE_CODE (x) == VAR_DECL) + has_proper_scope_for_analysis (x); + } +} + + +/* Scan tree T to see if there are any casts within it. + LHS Is the LHS of the expression involving the cast. */ + +static void +look_for_casts (tree lhs __attribute__((unused)), tree t) +{ + if (is_gimple_cast (t) || TREE_CODE (t) == VIEW_CONVERT_EXPR) + { + tree castfromvar = TREE_OPERAND (t, 0); + check_cast (TREE_TYPE (t), castfromvar); + } + else if (TREE_CODE (t) == COMPONENT_REF + || TREE_CODE (t) == INDIRECT_REF + || TREE_CODE (t) == BIT_FIELD_REF) + { + tree base = get_base_address (t); + while (t != base) + { + t = TREE_OPERAND (t, 0); + if (TREE_CODE (t) == VIEW_CONVERT_EXPR) + { + /* This may be some part of a component ref. + IE it may be a.b.VIEW_CONVERT_EXPR<weird_type>(c).d, AFAIK. + castfromref will give you a.b.c, not a. */ + tree castfromref = TREE_OPERAND (t, 0); + check_cast (TREE_TYPE (t), castfromref); + } + else if (TREE_CODE (t) == COMPONENT_REF) + get_canon_type (TREE_TYPE (TREE_OPERAND (t, 1)), false, false); + } + } +} + +/* Check to see if T is a read or address of operation on a static var + we are interested in analyzing. */ + +static void +check_rhs_var (tree t) +{ + look_for_address_of (t); + check_tree(t); +} + +/* Check to see if T is an assignment to a static var we are + interested in analyzing. */ + +static void +check_lhs_var (tree t) +{ + check_tree(t); +} + +/* 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. FN is the function being + analyzed and STMT is the actual asm statement. */ + +static void +get_asm_expr_operands (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 (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 (TREE_VALUE (link)); + } + + /* There is no code here to check for asm memory clobbers. The + casual maintainer might think that such code would be necessary, + but that appears to be wrong. In other parts of the compiler, + the asm memory clobbers are assumed to only clobber variables + that are addressable. All types with addressable instances are + assumed to already escape. So, we are protected here. */ +} + +/* Check the parameters of a function call to CALL_EXPR to mark the + types that pass across the function boundary. Also check to see if + this is either an indirect call, a call outside the compilation + unit. */ + +static bool +check_call (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); + tree argument; + 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 (argument); + } + + if (callee_t) + { + tree arg_type; + tree last_arg_type = NULL; + callee = cgraph_node(callee_t); + avail = cgraph_function_body_availability (callee); + + /* Check that there are no implicit casts in the passing of + parameters. */ + if (TYPE_ARG_TYPES (TREE_TYPE (callee_t))) + { + operand = operand_list; + for (arg_type = TYPE_ARG_TYPES (TREE_TYPE (callee_t)); + arg_type && TREE_VALUE (arg_type) != void_type_node; + arg_type = TREE_CHAIN (arg_type)) + { + if (operand) + { + argument = TREE_VALUE (operand); + last_arg_type = TREE_VALUE(arg_type); + check_cast (last_arg_type, argument); + operand = TREE_CHAIN (operand); + } + else + /* The code reaches here for some unfortunate + builtin functions that do not have a list of + argument types. */ + break; + } + } + else + { + /* FIXME - According to Geoff Keating, we should never + have to do this; the front ends should always process + the arg list from the TYPE_ARG_LIST. */ + operand = operand_list; + for (arg_type = DECL_ARGUMENTS (callee_t); + arg_type; + arg_type = TREE_CHAIN (arg_type)) + { + if (operand) + { + argument = TREE_VALUE (operand); + last_arg_type = TREE_TYPE(arg_type); + check_cast (last_arg_type, argument); + operand = TREE_CHAIN (operand); + } + else + /* The code reaches here for some unfortunate + builtin functions that do not have a list of + argument types. */ + break; + } + } + + /* In the case where we have a var_args function, we need to + check the remaining parameters against the last argument. */ + arg_type = last_arg_type; + for (; + operand != NULL_TREE; + operand = TREE_CHAIN (operand)) + { + argument = TREE_VALUE (operand); + if (arg_type) + check_cast (arg_type, argument); + else + { + /* The code reaches here for some unfortunate + builtin functions that do not have a list of + argument types. Most of these functions have + been marked as having their parameters not + escape, but for the rest, the type is doomed. */ + tree type = get_canon_type (TREE_TYPE (argument), false, false); + mark_interesting_type (type, FULL_ESCAPE); + } + } + } + + /* 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 this is a direct call to an external function, mark all of + the parameter and return types. */ + for (operand = operand_list; + operand != NULL_TREE; + operand = TREE_CHAIN (operand)) + { + tree type = + get_canon_type (TREE_TYPE (TREE_VALUE (operand)), false, false); + mark_interesting_type (type, EXPOSED_PARAMETER); + } + + if (callee_t) + { + tree type = + get_canon_type (TREE_TYPE (TREE_TYPE (callee_t)), false, false); + mark_interesting_type (type, EXPOSED_PARAMETER); + } + } + return (flags & ECF_MALLOC); +} + +/* CODE is the operation on OP0 and OP1. OP0 is the operand that we + *know* is a pointer type. OP1 may be a pointer type. */ +static bool +okay_pointer_operation (enum tree_code code, tree op0, tree op1) +{ + tree op0type = TYPE_MAIN_VARIANT (TREE_TYPE (op0)); + tree op1type = TYPE_MAIN_VARIANT (TREE_TYPE (op1)); + if (POINTER_TYPE_P (op1type)) + return false; + switch (code) + { + case MULT_EXPR: + case PLUS_EXPR: + case MINUS_EXPR: + /* TODO: Handle multiples of op0 size as well */ + if (operand_equal_p (size_in_bytes (op0type), op1, 0)) + return true; + /* fallthrough */ + + default: + return false; + } + return false; +} + +/* 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_for_refs (tree *tp, int *walk_subtrees, void *data) +{ + struct cgraph_node *fn = data; + tree t = *tp; + + switch (TREE_CODE (t)) + { + case VAR_DECL: + if (DECL_INITIAL (t)) + walk_tree (&DECL_INITIAL (t), scan_for_refs, 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 (lhs); + check_cast (TREE_TYPE (lhs), rhs); + + /* 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 type0 = get_canon_type (TREE_TYPE (op0), false, false); + tree op1 = TREE_OPERAND (rhs, 1); + tree type1 = get_canon_type (TREE_TYPE (op1), false, false); + + /* If this is pointer arithmetic of any bad sort, then + we need to mark the types as bad. For binary + operations, no binary operator we currently support + is always "safe" in regard to what it would do to + pointers for purposes of determining which types + escape, except operations of the size of the type. + It is possible that min and max under the right set + of circumstances and if the moon is in the correct + place could be safe, but it is hard to see how this + is worth the effort. */ + + if (type0 && POINTER_TYPE_P (type0) + && !okay_pointer_operation (TREE_CODE (rhs), op0, op1)) + mark_interesting_type (type0, FULL_ESCAPE); + if (type1 && POINTER_TYPE_P (type1) + && !okay_pointer_operation (TREE_CODE (rhs), op1, op0)) + mark_interesting_type (type1, FULL_ESCAPE); + + look_for_casts (lhs, op0); + look_for_casts (lhs, op1); + check_rhs_var (op0); + check_rhs_var (op1); + } + break; + case tcc_unary: + { + tree op0 = TREE_OPERAND (rhs, 0); + tree type0 = get_canon_type (TREE_TYPE (op0), false, false); + /* For unary operations, if the operation is NEGATE or + ABS on a pointer, this is also considered pointer + arithmetic and thus, bad for business. */ + if (type0 && (TREE_CODE (op0) == NEGATE_EXPR + || TREE_CODE (op0) == ABS_EXPR) + && POINTER_TYPE_P (type0)) + { + mark_interesting_type (type0, FULL_ESCAPE); + } + check_rhs_var (op0); + look_for_casts (lhs, op0); + look_for_casts (lhs, rhs); + } + + break; + case tcc_reference: + look_for_casts (lhs, rhs); + check_rhs_var (rhs); + break; + case tcc_declaration: + check_rhs_var (rhs); + break; + case tcc_expression: + switch (TREE_CODE (rhs)) + { + case ADDR_EXPR: + look_for_casts (lhs, TREE_OPERAND (rhs, 0)); + check_rhs_var (rhs); + break; + case CALL_EXPR: + /* If this is a call to malloc, squirrel away the + result so we do mark the resulting cast as being + bad. */ + if (check_call (rhs)) + bitmap_set_bit (results_of_malloc, DECL_UID (lhs)); + 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 (t); + *walk_subtrees = 0; + break; + + case CALL_EXPR: + check_call (t); + *walk_subtrees = 0; + break; + + case ASM_EXPR: + get_asm_expr_operands (t); + *walk_subtrees = 0; + break; + + default: + break; + } + return NULL; +} + + +/* The init routine for analyzing global static variable usage. See + comments at top for description. */ +static void +ipa_init (void) +{ + bitmap_obstack_initialize (&ipa_obstack); + global_types_exposed_parameter = BITMAP_ALLOC (&ipa_obstack); + global_types_full_escape = BITMAP_ALLOC (&ipa_obstack); + global_types_seen = BITMAP_ALLOC (&ipa_obstack); + results_of_malloc = BITMAP_ALLOC (&ipa_obstack); + + uid_to_canon_type = splay_tree_new (splay_tree_compare_ints, 0, 0); + all_canon_types = splay_tree_new (compare_type_brand, 0, 0); + type_to_canon_type = splay_tree_new (splay_tree_compare_pointers, 0, 0); + uid_to_subtype_map = splay_tree_new (splay_tree_compare_ints, 0, 0); + uid_to_addressof_down_map = splay_tree_new (splay_tree_compare_ints, 0, 0); + uid_to_addressof_up_map = splay_tree_new (splay_tree_compare_ints, 0, 0); + + /* 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 (); + initialized = true; +} + +/* Check out the rhs of a static or global initialization VNODE to see + if any of them contain addressof operations. Note that some of + these variables may not even be referenced in the code in this + compilation unit but their right hand sides may contain references + to variables defined within this unit. */ + +static void +analyze_variable (struct cgraph_varpool_node *vnode) +{ + tree global = vnode->decl; + tree type = get_canon_type (TREE_TYPE (global), false, false); + + /* If this variable has exposure beyond the compilation unit, add + its type to the global types. */ + + if (vnode->externally_visible) + mark_interesting_type (type, FULL_ESCAPE); + + if (TREE_CODE (global) == VAR_DECL) + { + if (DECL_INITIAL (global)) + walk_tree (&DECL_INITIAL (global), scan_for_refs, + NULL, visited_nodes); + } + else abort(); +} + +/* 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) +{ + tree decl = fn->decl; + check_function_parameter_and_return_types (decl, + fn->local.externally_visible); + if (dump_file) + fprintf (dump_file, "\n local analysis of %s", cgraph_node_name (fn)); + + { + 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_for_refs, + fn, visited_nodes); + } + } + + /* There may be const decls with interesting right hand sides. */ + if (DECL_STRUCT_FUNCTION (decl)) + { + tree step; + for (step = DECL_STRUCT_FUNCTION (decl)->unexpanded_var_list; + step; + step = TREE_CHAIN (step)) + { + tree var = TREE_VALUE (step); + if (TREE_CODE (var) == VAR_DECL + && DECL_INITIAL (var) + && !TREE_STATIC (var)) + walk_tree (&DECL_INITIAL (var), scan_for_refs, + fn, visited_nodes); + get_canon_type (TREE_TYPE (var), false, false); + } + } +} + + + +/* Convert a type_UID into a type. */ +static tree +type_for_uid (int uid) +{ + splay_tree_node result = + splay_tree_lookup (uid_to_canon_type, (splay_tree_key) uid); + + if (result) + return (tree) result->value; + else return NULL; +} + +/* Return the a bitmap with the subtypes of the type for UID. If it + does not exist, return either NULL or a new bitmap depending on the + value of CREATE. */ + +static bitmap +subtype_map_for_uid (int uid, bool create) +{ + splay_tree_node result = splay_tree_lookup (uid_to_subtype_map, + (splay_tree_key) uid); + + if (result) + return (bitmap) result->value; + else if (create) + { + bitmap subtype_map = BITMAP_ALLOC (&ipa_obstack); + splay_tree_insert (uid_to_subtype_map, + uid, + (splay_tree_value)subtype_map); + return subtype_map; + } + else return NULL; +} + +/* Mark all of the supertypes and field types of TYPE as being seen. + Also accumulate the subtypes for each type so that + close_types_full_escape can mark a subtype as escaping if the + supertype escapes. */ + +static void +close_type_seen (tree type) +{ + tree field; + int i, uid; + tree binfo, base_binfo; + + /* See thru all pointer tos and array ofs. */ + type = get_canon_type (type, true, true); + if (!type) + return; + + uid = TYPE_UID (type); + + if (bitmap_bit_p (been_there_done_that, uid)) + return; + bitmap_set_bit (been_there_done_that, uid); + + /* If we are doing a language with a type heirarchy, mark all of + the superclasses. */ + if (TYPE_BINFO (type)) + for (binfo = TYPE_BINFO (type), i = 0; + BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) + { + tree binfo_type = BINFO_TYPE (base_binfo); + bitmap subtype_map = subtype_map_for_uid + (TYPE_UID (TYPE_MAIN_VARIANT (binfo_type)), true); + bitmap_set_bit (subtype_map, uid); + close_type_seen (get_canon_type (binfo_type, true, true)); + } + + /* If the field is a struct or union type, mark all of the + subfields. */ + for (field = TYPE_FIELDS (type); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) + close_type_seen (get_canon_type (field_type, true, true)); + } +} + +/* Take a TYPE that has been passed by value to an external function + and mark all of the fields that have pointer types as escaping. For + any of the non pointer types that are structures or unions, + recurse. TYPE is never a pointer type. */ + +static void +close_type_exposed_parameter (tree type) +{ + tree field; + int uid; + + type = get_canon_type (type, false, false); + if (!type) + return; + uid = TYPE_UID (type); + gcc_assert (!POINTER_TYPE_P (type)); + + if (bitmap_bit_p (been_there_done_that, uid)) + return; + bitmap_set_bit (been_there_done_that, uid); + + /* If the field is a struct or union type, mark all of the + subfields. */ + for (field = TYPE_FIELDS (type); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = get_canon_type (TREE_TYPE (field), false, false); + mark_interesting_type (field_type, EXPOSED_PARAMETER); + + /* Only recurse for non pointer types of structures and unions. */ + if (ipa_type_escape_star_count_of_interesting_type (field_type) == 0) + close_type_exposed_parameter (field_type); + } +} + +/* The next function handles the case where a type fully escapes. + This means that not only does the type itself escape, + + a) the type of every field recursively escapes + b) the type of every subtype escapes as well as the super as well + as all of the pointer to types for each field. + + Note that pointer to types are not marked as escaping. If the + pointed to type escapes, the pointer to type also escapes. + + Take a TYPE that has had the address taken for an instance of it + and mark all of the types for its fields as having their addresses + taken. */ + +static void +close_type_full_escape (tree type) +{ + tree field; + unsigned int i; + int uid; + tree binfo, base_binfo; + bitmap_iterator bi; + bitmap subtype_map; + splay_tree_node address_result; + + /* Strip off any pointer or array types. */ + type = get_canon_type (type, true, true); + if (!type) + return; + uid = TYPE_UID (type); + + if (bitmap_bit_p (been_there_done_that, uid)) + return; + bitmap_set_bit (been_there_done_that, uid); + + subtype_map = subtype_map_for_uid (uid, false); + + /* If we are doing a language with a type heirarchy, mark all of + the superclasses. */ + if (TYPE_BINFO (type)) + for (binfo = TYPE_BINFO (type), i = 0; + BINFO_BASE_ITERATE (binfo, i, base_binfo); i++) + { + tree binfotype = BINFO_TYPE (base_binfo); + binfotype = mark_type (binfotype, FULL_ESCAPE); + close_type_full_escape (binfotype); + } + + /* Mark as escaped any types that have been down casted to + this type. */ + if (subtype_map) + EXECUTE_IF_SET_IN_BITMAP (subtype_map, 0, i, bi) + { + tree subtype = type_for_uid (i); + subtype = mark_type (subtype, FULL_ESCAPE); + close_type_full_escape (subtype); + } + + /* If the field is a struct or union type, mark all of the + subfields. */ + for (field = TYPE_FIELDS (type); + field; + field = TREE_CHAIN (field)) + { + tree field_type; + if (TREE_CODE (field) != FIELD_DECL) + continue; + + field_type = TREE_TYPE (field); + if (ipa_type_escape_star_count_of_interesting_or_array_type (field_type) >= 0) + { + field_type = mark_type (field_type, FULL_ESCAPE); + close_type_full_escape (field_type); + } + } + + /* For all of the types A that contain this type B and were part of + an expression like "&...A.B...", mark the A's as escaping. */ + address_result = splay_tree_lookup (uid_to_addressof_up_map, + (splay_tree_key) uid); + if (address_result) + { + bitmap containing_classes = (bitmap) address_result->value; + EXECUTE_IF_SET_IN_BITMAP (containing_classes, 0, i, bi) + { + close_type_full_escape (type_for_uid (i)); + } + } +} + +/* Transitively close the addressof bitmap for the type with UID. + This means that if we had a.b and b.c, a would have both b an c in + its maps. */ + +static bitmap +close_addressof_down (int uid) +{ + bitmap_iterator bi; + splay_tree_node result = + splay_tree_lookup (uid_to_addressof_down_map, (splay_tree_key) uid); + bitmap map = NULL; + bitmap new_map; + unsigned int i; + + if (result) + map = (bitmap) result->value; + else + return NULL; + + if (bitmap_bit_p (been_there_done_that, uid)) + return map; + bitmap_set_bit (been_there_done_that, uid); + + /* If the type escapes, get rid of the addressof map, it will not be + needed. */ + if (bitmap_bit_p (global_types_full_escape, uid)) + { + BITMAP_FREE (map); + splay_tree_remove (uid_to_addressof_down_map, (splay_tree_key) uid); + return NULL; + } + + /* The new_map will have all of the bits for the enclosed fields and + will have the unique id version of the old map. */ + new_map = BITMAP_ALLOC (&ipa_obstack); + + EXECUTE_IF_SET_IN_BITMAP (map, 0, i, bi) + { + bitmap submap = close_addressof_down (i); + bitmap_set_bit (new_map, i); + if (submap) + bitmap_ior_into (new_map, submap); + } + result->value = (splay_tree_value) new_map; + + BITMAP_FREE (map); + return new_map; +} + + +/* The main entry point for type escape analysis. */ + +static void +type_escape_execute (void) +{ + struct cgraph_node *node; + struct cgraph_varpool_node *vnode; + unsigned int i; + bitmap_iterator bi; + splay_tree_node result; + + ipa_init (); + + /* Process all of the variables first. */ + for (vnode = cgraph_varpool_nodes_queue; vnode; vnode = vnode->next_needed) + analyze_variable (vnode); + + /* Process all of the functions. next + + We do not want to process any of the clones so we check that this + is a master clone. However, we do need to process any + AVAIL_OVERWRITABLE functions (these are never clones) because + they may cause a type variable to escape. + */ + for (node = cgraph_nodes; node; node = node->next) + if (node->analyzed + && (cgraph_is_master_clone (node) + || (cgraph_function_body_availability (node) == AVAIL_OVERWRITABLE))) + analyze_function (node); + + + pointer_set_destroy (visited_nodes); + visited_nodes = NULL; + + /* Do all of the closures to discover which types escape the + compilation unit. */ + + been_there_done_that = BITMAP_ALLOC (&ipa_obstack); + bitmap_tmp = BITMAP_ALLOC (&ipa_obstack); + + /* Examine the types that we have directly seen in scanning the code + and add to that any contained types or superclasses. */ + + bitmap_copy (bitmap_tmp, global_types_seen); + EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) + { + tree type = type_for_uid (i); + /* Only look at records and unions and pointer tos. */ + if (ipa_type_escape_star_count_of_interesting_or_array_type (type) >= 0) + close_type_seen (type); + } + bitmap_clear (been_there_done_that); + + /* Examine all of the types passed by value and mark any enclosed + pointer types as escaping. */ + bitmap_copy (bitmap_tmp, global_types_exposed_parameter); + EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) + { + close_type_exposed_parameter (type_for_uid (i)); + } + bitmap_clear (been_there_done_that); + + /* Close the types for escape. If something escapes, then any + enclosed types escape as well as any subtypes. */ + bitmap_copy (bitmap_tmp, global_types_full_escape); + EXECUTE_IF_SET_IN_BITMAP (bitmap_tmp, 0, i, bi) + { + close_type_full_escape (type_for_uid (i)); + } + bitmap_clear (been_there_done_that); + + /* Before this pass, the uid_to_addressof_down_map for type X + contained an entry for Y if there had been an operation of the + form &X.Y. This step adds all of the fields contained within Y + (recursively) to X's map. */ + + result = splay_tree_min (uid_to_addressof_down_map); + while (result) + { + int uid = result->key; + /* Close the addressof map, i.e. copy all of the transitive + substructures up to this level. */ + close_addressof_down (uid); + result = splay_tree_successor (uid_to_addressof_down_map, uid); + } + + /* Do not need the array types and pointer types in the persistent + data structures. */ + result = splay_tree_min (all_canon_types); + while (result) + { + tree type = (tree) result->value; + tree key = (tree) result->key; + if (POINTER_TYPE_P (type) + || TREE_CODE (type) == ARRAY_TYPE) + { + splay_tree_remove (all_canon_types, (splay_tree_key) result->key); + splay_tree_remove (type_to_canon_type, (splay_tree_key) type); + splay_tree_remove (uid_to_canon_type, (splay_tree_key) TYPE_UID (type)); + bitmap_clear_bit (global_types_seen, TYPE_UID (type)); + } + result = splay_tree_successor (all_canon_types, (splay_tree_key) key); + } + +/* { */ +/* FILE * tmp = dump_file; */ +/* dump_file = stderr; */ + if (dump_file) + { + EXECUTE_IF_SET_IN_BITMAP (global_types_seen, 0, i, bi) + { + /* The pointer types are in the global_types_full_escape + bitmap but not in the backwards map. They also contain + no useful information since they are not marked. */ + tree type = type_for_uid (i); + fprintf(dump_file, "type %d ", i); + print_generic_expr (dump_file, type, 0); + if (bitmap_bit_p (global_types_full_escape, i)) + fprintf(dump_file, " escaped\n"); + else + fprintf(dump_file, " contained\n"); + } + } +/* dump_file = tmp; */ +/* } */ + + /* Get rid of uid_to_addressof_up_map and its bitmaps. */ + result = splay_tree_min (uid_to_addressof_up_map); + while (result) + { + int uid = (int)result->key; + bitmap bm = (bitmap)result->value; + + BITMAP_FREE (bm); + splay_tree_remove (uid_to_addressof_up_map, (splay_tree_key) uid); + result = splay_tree_successor (uid_to_addressof_up_map, uid); + } + + /* Get rid of the subtype map. */ + result = splay_tree_min (uid_to_subtype_map); + while (result) + { + bitmap b = (bitmap)result->value; + BITMAP_FREE(b); + splay_tree_remove (uid_to_subtype_map, result->key); + result = splay_tree_min (uid_to_subtype_map); + } + splay_tree_delete (uid_to_subtype_map); + uid_to_subtype_map = NULL; + + BITMAP_FREE (global_types_exposed_parameter); + BITMAP_FREE (been_there_done_that); + BITMAP_FREE (bitmap_tmp); + BITMAP_FREE (results_of_malloc); +} + +static bool +gate_type_escape_vars (void) +{ + return (flag_unit_at_a_time != 0 && flag_ipa_type_escape + /* Don't bother doing anything if the program has errors. */ + && !(errorcount || sorrycount)); +} + +struct tree_opt_pass pass_ipa_type_escape = +{ + "type-escape-var", /* name */ + gate_type_escape_vars, /* gate */ + type_escape_execute, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_IPA_TYPE_ESCAPE, /* tv_id */ + 0, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + 0, /* todo_flags_finish */ + 0 /* letter */ +}; + diff --git a/gcc/ipa-type-escape.h b/gcc/ipa-type-escape.h new file mode 100644 index 00000000000..76a7b7b485b --- /dev/null +++ b/gcc/ipa-type-escape.h @@ -0,0 +1,33 @@ +/* Type based alias analysis. + Copyright (C) 2004 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, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#ifndef GCC_IPA_TYPE_ESCAPE_H +#define GCC_IPA_TYPE_ESCAPE_H +#include "tree.h" + +bool ipa_type_escape_type_contained_p (tree type); +bool ipa_type_escape_field_does_not_clobber_p (tree record_type, tree field_type); +int ipa_type_escape_star_count_of_interesting_type (tree type); +int ipa_type_escape_star_count_of_interesting_or_array_type (tree type); + + +#endif /* GCC_IPA_TYPE_ESCAPE_H */ + diff --git a/gcc/ipa-utils.c b/gcc/ipa-utils.c new file mode 100644 index 00000000000..b758031adbe --- /dev/null +++ b/gcc/ipa-utils.c @@ -0,0 +1,228 @@ +/* Utilities for ipa analysis. + Copyright (C) 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, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. +*/ + +#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 "ipa-reference.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" + +/* Debugging function for postorder and inorder code. NOTE is a string + that is printed before the nodes are printed. ORDER is an array of + cgraph_nodes that has COUNT useful nodes in it. */ + +void +ipa_utils_print_order (FILE* out, + const char * note, + struct cgraph_node** order, + int count) +{ + int i; + fprintf (out, "\n\n ordered call graph: %s\n", note); + + for (i = count - 1; i >= 0; i--) + dump_cgraph_node(dump_file, order[i]); + fprintf (out, "\n"); + fflush(out); +} + + +struct searchc_env { + struct cgraph_node **stack; + int stack_size; + struct cgraph_node **result; + int order_pos; + splay_tree nodes_marked_new; + bool reduce; + int count; +}; + +/* This is an implementation of Tarjan's strongly connected region + finder as reprinted in Aho Hopcraft and Ullman's The Design and + Analysis of Computer Programs (1975) pages 192-193. This version + has been customized for cgraph_nodes. The env parameter is because + it is recursive and there are no nested functions here. This + function should only be called from itself or + cgraph_reduced_inorder. ENV is a stack env and would be + unnecessary if C had nested functions. V is the node to start + searching from. */ + +static void +searchc (struct searchc_env* env, struct cgraph_node *v) +{ + struct cgraph_edge *edge; + struct ipa_dfs_info *v_info = v->aux; + + /* mark node as old */ + v_info->new = false; + splay_tree_remove (env->nodes_marked_new, v->uid); + + v_info->dfn_number = env->count; + v_info->low_link = env->count; + env->count++; + env->stack[(env->stack_size)++] = v; + v_info->on_stack = true; + + for (edge = v->callees; edge; edge = edge->next_callee) + { + struct ipa_dfs_info * w_info; + struct cgraph_node *w = edge->callee; + /* Bypass the clones and only look at the master node. Skip + external and other bogus nodes. */ + w = cgraph_master_clone (w); + if (w && w->aux) + { + w_info = w->aux; + if (w_info->new) + { + searchc (env, w); + v_info->low_link = + (v_info->low_link < w_info->low_link) ? + v_info->low_link : w_info->low_link; + } + else + if ((w_info->dfn_number < v_info->dfn_number) + && (w_info->on_stack)) + v_info->low_link = + (w_info->dfn_number < v_info->low_link) ? + w_info->dfn_number : v_info->low_link; + } + } + + + if (v_info->low_link == v_info->dfn_number) + { + struct cgraph_node *last = NULL; + struct cgraph_node *x; + struct ipa_dfs_info *x_info; + do { + x = env->stack[--(env->stack_size)]; + x_info = x->aux; + x_info->on_stack = false; + + if (env->reduce) + { + x_info->next_cycle = last; + last = x; + } + else + env->result[env->order_pos++] = x; + } + while (v != x); + if (env->reduce) + env->result[env->order_pos++] = v; + } +} + +/* Topsort the call graph by caller relation. Put the result in ORDER. + + The REDUCE flag is true if you want the cycles reduced to single + nodes. Only consider nodes that have the output bit set. */ + +int +ipa_utils_reduced_inorder (struct cgraph_node **order, + bool reduce, bool allow_overwritable) +{ + struct cgraph_node *node; + struct searchc_env env; + splay_tree_node result; + env.stack = xcalloc (cgraph_n_nodes, sizeof (struct cgraph_node *)); + env.stack_size = 0; + env.result = order; + env.order_pos = 0; + env.nodes_marked_new = splay_tree_new (splay_tree_compare_ints, 0, 0); + env.count = 1; + env.reduce = reduce; + + for (node = cgraph_nodes; node; node = node->next) + if ((node->analyzed) + && (cgraph_is_master_clone (node) + || (allow_overwritable + && (cgraph_function_body_availability (node) == + AVAIL_OVERWRITABLE)))) + { + /* Reuse the info if it is already there. */ + struct ipa_dfs_info *info = node->aux; + if (!info) + info = xcalloc (1, sizeof (struct ipa_dfs_info)); + info->new = true; + info->on_stack = false; + info->next_cycle = NULL; + node->aux = info; + + splay_tree_insert (env.nodes_marked_new, + (splay_tree_key)node->uid, + (splay_tree_value)node); + } + else + node->aux = NULL; + result = splay_tree_min (env.nodes_marked_new); + while (result) + { + node = (struct cgraph_node *)result->value; + searchc (&env, node); + result = splay_tree_min (env.nodes_marked_new); + } + splay_tree_delete (env.nodes_marked_new); + free (env.stack); + + return env.order_pos; +} + + +/* Given a memory reference T, will return the variable at the bottom + of the access. Unlike get_base_address, this will recurse thru + INDIRECT_REFS. */ + +tree +get_base_var (tree t) +{ + if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) + return t; + + while (!SSA_VAR_P (t) + && (!CONSTANT_CLASS_P (t)) + && TREE_CODE (t) != LABEL_DECL + && TREE_CODE (t) != FUNCTION_DECL + && TREE_CODE (t) != CONST_DECL) + { + t = TREE_OPERAND (t, 0); + } + return t; +} + diff --git a/gcc/ipa-utils.h b/gcc/ipa-utils.h new file mode 100644 index 00000000000..e3b31fb6101 --- /dev/null +++ b/gcc/ipa-utils.h @@ -0,0 +1,49 @@ +/* Utilities for ipa analysis. + 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, 59 Temple Place - Suite 330, Boston, MA +02111-1307, USA. */ + +#ifndef GCC_IPA_UTILS_H +#define GCC_IPA_UTILS_H +#include "tree.h" +#include "cgraph.h" + +/* Used for parsing attributes of asm code. */ +extern tree memory_identifier_string; + +struct ipa_dfs_info { + int dfn_number; + int low_link; + bool new; + bool on_stack; + struct cgraph_node* next_cycle; + PTR aux; +}; + + + +/* In ipa-utils.c */ +void ipa_utils_print_order (FILE*, const char *, struct cgraph_node**, int); +int ipa_utils_reduced_inorder (struct cgraph_node **, bool, bool); +tree get_base_var (tree); + + +#endif /* GCC_IPA_UTILS_H */ + + diff --git a/gcc/opts.c b/gcc/opts.c index e5e490d16eb..b7948f63e92 100644 --- a/gcc/opts.c +++ b/gcc/opts.c @@ -523,6 +523,8 @@ decode_options (unsigned int argc, const char **argv) flag_loop_optimize = 1; flag_if_conversion = 1; flag_if_conversion2 = 1; + flag_ipa_pure_const = 1; + flag_ipa_reference = 1; flag_tree_ccp = 1; flag_tree_dce = 1; flag_tree_dom = 1; @@ -556,6 +558,7 @@ decode_options (unsigned int argc, const char **argv) flag_cse_skip_blocks = 1; flag_gcse = 1; flag_expensive_optimizations = 1; + flag_ipa_type_escape = 1; flag_strength_reduce = 1; flag_rerun_cse_after_loop = 1; flag_rerun_loop_opt = 1; @@ -583,6 +586,7 @@ decode_options (unsigned int argc, const char **argv) if (optimize >= 3) { + flag_tree_promote_statics = 1; flag_inline_functions = 1; flag_unswitch_loops = 1; flag_gcse_after_reload = 1; diff --git a/gcc/passes.c b/gcc/passes.c index 1356dc171a8..41617232fbb 100644 --- a/gcc/passes.c +++ b/gcc/passes.c @@ -431,6 +431,9 @@ init_optimization_passes (void) NEXT_PASS (pass_early_ipa_inline); NEXT_PASS (pass_early_local_passes); NEXT_PASS (pass_ipa_inline); + NEXT_PASS (pass_ipa_reference); + NEXT_PASS (pass_ipa_pure_const); + NEXT_PASS (pass_ipa_type_escape); *p = NULL; /* All passes needed to lower the function into shape optimizers can operate @@ -469,6 +472,7 @@ init_optimization_passes (void) p = &pass_all_optimizations.sub; NEXT_PASS (pass_referenced_vars); + NEXT_PASS (pass_promote_statics); NEXT_PASS (pass_create_structure_vars); NEXT_PASS (pass_build_ssa); NEXT_PASS (pass_may_alias); diff --git a/gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c b/gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c index 3f14763919a..34fb26697d3 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/20030714-1.c @@ -34,13 +34,13 @@ find_base_value (src) } -/* There should be six IF conditionals. */ -/* { dg-final { scan-tree-dump-times "if " 6 "dom3"} } */ +/* There should be four IF conditionals. */ +/* { dg-final { scan-tree-dump-times "if " 4 "dom3"} } */ /* There should be no casts to short unsigned int. */ /* { dg-final { scan-tree-dump-times "\\(short unsigned int\\)" 0 "dom3"} } */ -/* There should be three loads of ->code. */ -/* { dg-final { scan-tree-dump-times "->code" 3 "dom3"} } */ +/* There should be two loads of ->code. */ +/* { dg-final { scan-tree-dump-times "->code" 2 "dom3"} } */ /* { dg-final { cleanup-tree-dump "dom3" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/sra-2.c b/gcc/testsuite/gcc.dg/tree-ssa/sra-2.c index ac4c1c61c6b..82f03c264dd 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/sra-2.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/sra-2.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O1 -fdump-tree-optimized" } */ +/* { dg-options "-O3 -fdump-tree-optimized" } */ /* Test for SRA. */ @@ -22,5 +22,5 @@ copystruct11 (teststruct *param) /* There should be no reference to link_error. */ -/* { dg-final { scan-tree-dump-times "link_error" 0 "optimized" { xfail *-*-* } } } */ +/* { dg-final { scan-tree-dump-times "link_error" 0 "optimized" } } */ /* { dg-final { cleanup-tree-dump "optimized" } } */ diff --git a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-2.c b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-2.c index 213c521d8a3..81a11a97bda 100644 --- a/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-2.c +++ b/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-2.c @@ -1,5 +1,5 @@ /* { dg-do compile } */ -/* { dg-options "-O1 -fdump-tree-dce3" } */ +/* { dg-options "-O2 -fdump-tree-dce3" } */ /* We should notice constantness of this function. */ int t(int a) diff --git a/gcc/testsuite/gcc.dg/vect/vect-92.c b/gcc/testsuite/gcc.dg/vect/vect-92.c index e9360ffa38b..a2c57407ed1 100644 --- a/gcc/testsuite/gcc.dg/vect/vect-92.c +++ b/gcc/testsuite/gcc.dg/vect/vect-92.c @@ -80,7 +80,7 @@ int main (void) main1 (a,b,c); main2 (a,b,c); - main3 (a,b,c,N); + main3 (a,b,c,N-1); return 0; } diff --git a/gcc/timevar.def b/gcc/timevar.def index 0f9040aa84e..66574f5b6ab 100644 --- a/gcc/timevar.def +++ b/gcc/timevar.def @@ -42,6 +42,9 @@ DEFTIMEVAR (TV_DUMP , "dump files") DEFTIMEVAR (TV_CGRAPH , "callgraph construction") DEFTIMEVAR (TV_CGRAPHOPT , "callgraph optimization") +DEFTIMEVAR (TV_IPA_REFERENCE , "ipa reference") +DEFTIMEVAR (TV_IPA_PURE_CONST , "ipa pure const") +DEFTIMEVAR (TV_IPA_TYPE_ESCAPE , "ipa type escape") /* Time spent by constructing CFG. */ DEFTIMEVAR (TV_CFG , "cfg construction") /* Time spent by cleaning up CFG. */ @@ -66,6 +69,7 @@ DEFTIMEVAR (TV_TREE_GIMPLIFY , "tree gimplify") DEFTIMEVAR (TV_TREE_EH , "tree eh") DEFTIMEVAR (TV_TREE_CFG , "tree CFG construction") DEFTIMEVAR (TV_TREE_CLEANUP_CFG , "tree CFG cleanup") +DEFTIMEVAR (TV_TREE_PROMOTE_STATICS , "tree promote statics") DEFTIMEVAR (TV_TREE_VRP , "tree VRP") DEFTIMEVAR (TV_TREE_COPY_PROP , "tree copy propagation") DEFTIMEVAR (TV_TREE_STORE_COPY_PROP , "tree store copy prop") diff --git a/gcc/tree-dfa.c b/gcc/tree-dfa.c index c745ed02015..b9fecfbb890 100644 --- a/gcc/tree-dfa.c +++ b/gcc/tree-dfa.c @@ -566,6 +566,20 @@ find_vars_r (tree *tp, int *walk_subtrees, void *data) /* Lookup UID in the referenced_vars hashtable and return the associated + variable or NULL if it is not there. */ + +tree +referenced_var_lookup_if_exists (unsigned int uid) +{ + struct int_tree_map *h, in; + in.uid = uid; + h = htab_find_with_hash (referenced_vars, &in, uid); + if (h) + return h->to; + return NULL_TREE; +} + +/* Lookup UID in the referenced_vars hashtable and return the associated variable. */ tree diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h index e45793033f8..2bf40df5fa3 100644 --- a/gcc/tree-flow.h +++ b/gcc/tree-flow.h @@ -29,6 +29,7 @@ Boston, MA 02110-1301, USA. */ #include "tree-gimple.h" #include "tree-ssa-operands.h" #include "cgraph.h" +#include "ipa-reference.h" /* Forward declare structures for the garbage collector GTY markers. */ #ifndef GCC_BASIC_BLOCK_H @@ -239,6 +240,11 @@ struct var_ann_d GTY(()) current version of this variable (an SSA_NAME). */ tree current_def; + /* Pointer to the structure that contains the sets of global + variables modified by function calls. This field is only used + for FUNCTION_DECLs. */ + ipa_reference_vars_info_t GTY ((skip)) reference_vars_info; + /* If this variable is a structure, this fields holds a list of symbols representing each of the fields of the structure. */ subvar_t subvars; @@ -392,6 +398,7 @@ typedef struct extern GTY((param_is (struct int_tree_map))) htab_t referenced_vars; extern tree referenced_var_lookup (unsigned int); +extern tree referenced_var_lookup_if_exists (unsigned int); #define num_referenced_vars htab_elements (referenced_vars) #define referenced_var(i) referenced_var_lookup (i) @@ -772,6 +779,10 @@ bool is_hidden_global_store (tree); /* In tree-sra.c */ void insert_edge_copies (tree, basic_block); +void sra_insert_before (block_stmt_iterator *, tree); +void sra_insert_after (block_stmt_iterator *, tree); +void sra_init_cache (void); +bool sra_type_can_be_decomposed_p (tree); /* In tree-loop-linear.c */ extern void linear_transform_loops (struct loops *); diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h index 92d52bda0b3..db9a8a5af88 100644 --- a/gcc/tree-pass.h +++ b/gcc/tree-pass.h @@ -278,6 +278,7 @@ extern struct tree_opt_pass pass_store_copy_prop; extern struct tree_opt_pass pass_vrp; extern struct tree_opt_pass pass_create_structure_vars; extern struct tree_opt_pass pass_uncprop; +extern struct tree_opt_pass pass_promote_statics; extern struct tree_opt_pass pass_return_slot; extern struct tree_opt_pass pass_reassoc; extern struct tree_opt_pass pass_rebuild_cgraph_edges; @@ -285,6 +286,9 @@ extern struct tree_opt_pass pass_rebuild_cgraph_edges; /* IPA Passes */ extern struct tree_opt_pass pass_ipa_inline; extern struct tree_opt_pass pass_early_ipa_inline; +extern struct tree_opt_pass pass_ipa_reference; +extern struct tree_opt_pass pass_ipa_pure_const; +extern struct tree_opt_pass pass_ipa_type_escape; extern struct tree_opt_pass pass_early_local_passes; extern struct tree_opt_pass pass_all_optimizations; diff --git a/gcc/tree-promote-statics.c b/gcc/tree-promote-statics.c new file mode 100644 index 00000000000..521bdf52689 --- /dev/null +++ b/gcc/tree-promote-statics.c @@ -0,0 +1,597 @@ +/* Promotion of static variables to ssa registers + 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, 59 Temple Place - Suite 330, +Boston, MA 02111-1307, USA. */ + +#include "config.h" +#include "system.h" +#include "coretypes.h" +#include "tm.h" +#include "tree.h" +#include "basic-block.h" +#include "tree-flow.h" +#include "ipa-utils.h" +#include "ipa-reference.h" +#include "bitmap.h" +#include "tree-pass.h" +#include "flags.h" +#include "timevar.h" +#include "langhooks.h" + +/* +The main idea is to promote some static variables from memory to SSA +registers. This transformation is only applied to those static +variables for which the effects of subroutine calls can be understood. +Such infomation is provided by functions in cgraphunit.c. + +The following table shows the actions that are taken to promote +variables. The analysis in cgraphunit constructs information about +both local usage and the effect of any particular call. Variables are +broken into 4 categories: only-read, only-write, read-write, and no +information. (No information variables are never promoted.) + +All information is of the "may" variety: if a function is marked read, +it means the call may read the variable, but it also may not read the +variable. + +There are two possible ways to perform the promotion: assume that the +static is live everywhere or compute the minimal live range for the +static variable. + +The minimal live range path has a lot of problems: + +1) live variables and upwards exposed uses must be first comuputed. +2) new machiney must be invented to prevent code motion algorithms +from floating a use of the surrogate register across a register +function call that clobbers the variable, but was not in any minimal +live range at the time of this analysis. + +While the first problem is simply a lot of code, the second problem +requires a new mechanism for pinning code and teaching all passes that +can move code to obey this new fenceposts. + +The maximum live range path has the problem that this technique can +create many false live ranges where the register is loaded after on +call only to be stored back right before the next call. This will eat +a certain amount of space and requires special smarts to get rid of them. + +There are really 7 situations to cover in the following table. + +action read write read-write + + -+--------------------------------------------------------------- + +entry | load load load + | +load | getfromreg xxxxx getfromreg + | +store | xxxx puttoreg puttoreg + | +call-read | noaction store before store before + | +call-write | load after store before store before + | load after load after +call-readwrite| load after store before store before + | load after load after + | +return | no action store store + + +l-r l-w c-r c-w store-b load-a + +0 0 0 0 | 0 0 +0 0 0 1 | 0 0 +0 0 1 0 | 0 0 +0 0 1 1 | 0 0 +0 1 0 0 | 0 0 +0 1 0 1 | 1 1 +0 1 1 0 | 1 0 +0 1 1 1 | 1 1 +1 0 0 0 | 0 0 +1 0 0 1 | 0 1 +1 0 1 0 | 0 0 +1 0 1 1 | 0 1 +1 1 0 0 | 0 0 +1 1 0 1 | 1 1 +1 1 1 0 | 1 0 +1 1 1 1 | 1 1 + +store_before = local_written & (callee_read | callee_written) +load_after = (local_read | local_written) & callee_written +*/ + +static bitmap_obstack promote_obstack; + +/* All of the static variables under consideration by this pass that + do reads or writes withing this function. */ +static bitmap local_read; +static bitmap local_written; +static bitmap local_all; + +/* Return true if the asm STMT clobbers memory. */ + +static bool +asm_clobbers_mem (tree stmt) +{ + tree link; + for (link = ASM_CLOBBERS (stmt); link; link = TREE_CHAIN (link)) + if (simple_cst_equal(TREE_VALUE (link), memory_identifier_string) == 1) + return true; + + return false; +} + +/* Return a INPUT_BITMAP for the asm inputs and OUTPUT_BITMAP for the + asm outputs of variables written by the asm STMT. */ + +static void +get_asm_read_and_write (bitmap input_bitmap, bitmap output_bitmap, 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); + + /* The variable is only added to the bitmap if there is an aux + field, ie.this is a variable we care about. */ + if (!allows_reg && allows_mem) + { + tree var = TREE_VALUE (link); + var = get_base_address (var); + if (TREE_CODE (var) == VAR_DECL) + { + var_ann_t va = var_ann (var); + if (va && va->common.aux) + bitmap_set_bit(output_bitmap, DECL_UID (var)); + } + } + } + + 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); + + /* The variable is only added to the bitmap if there is an aux + field, ie.this is a variable we care about. */ + if (!allows_reg && allows_mem) + { + tree var = TREE_VALUE (link); + var = get_base_address (var); + if (TREE_CODE (var) == VAR_DECL) + { + var_ann_t va = var_ann (var); + if (va && va->common.aux) + bitmap_set_bit(input_bitmap, DECL_UID (var)); + } + } + } +} + +/* Generate a series of loads from the static variables pointed to by + B1 && B2 or just B1 (if B2 is NULL) and insert them after + BSI). */ + +static void +gen_loads (bitmap b1, bitmap b2, block_stmt_iterator *bsi) +{ + bitmap result; + bitmap_iterator bi; + unsigned int index; + tree list = NULL; + + if (b2) + { + result = BITMAP_ALLOC (&promote_obstack); + bitmap_and (result, b1, b2); + } + else + result = b1; + + EXECUTE_IF_SET_IN_BITMAP(result, 0, index, bi) + { + tree src = referenced_var (index); + tree dest = (tree) (var_ann (src)->common.aux); + tree stmt = build (MODIFY_EXPR, TREE_TYPE (src), dest, src); + append_to_statement_list (stmt, &list); + } + + if (list) + sra_insert_after (bsi, list); + + if (b2) + BITMAP_FREE (result); +} + +/* Generate a series of stores to the static variables pointed to by + B1 && B2 or just B1 (if B2 is NULL) and insert them before + BSI). */ + +static void +gen_stores (bitmap b1, bitmap b2, block_stmt_iterator *bsi) +{ + bitmap result; + bitmap_iterator bi; + unsigned int index; + tree list = NULL; + + if (b2) + { + result = BITMAP_ALLOC (&promote_obstack); + bitmap_and (result, b1, b2); + } + else + result = b1; + + EXECUTE_IF_SET_IN_BITMAP(result, 0, index, bi) + { + tree dest = referenced_var (index); + tree src = (tree) (var_ann (dest)->common.aux); + tree stmt = build (MODIFY_EXPR, TREE_TYPE (src), dest, src); + append_to_statement_list (stmt, &list); + } + + if (list) + sra_insert_before (bsi, list); + + if (b2) + BITMAP_FREE (result); +} + +/* Replace the static references if it exists in the TPTR. */ + +static void +try_replace_operand(tree * tptr) +{ + tree t = *tptr; + if (TREE_CODE (t) == VAR_DECL) + { + var_ann_t va = var_ann (t); + tree replacement = (tree) (va->common.aux); + if (replacement) + *tptr = replacement; + } +} + +/* Walk an expression TPTR replacing all of the static references. */ + +static void +try_replace (tree *tptr) +{ + tree t = *tptr; + if ((TREE_CODE (t) == EXC_PTR_EXPR) || (TREE_CODE (t) == FILTER_EXPR)) + return; + + /* The INTEGER_CST is because some people use cute things like &0->a + for offsetof. */ + while (t && !SSA_VAR_P (t) + && (!CONSTANT_CLASS_P (t)) + && TREE_CODE (t) != LABEL_DECL + && TREE_CODE (t) != CONST_DECL + && TREE_CODE (t) != FUNCTION_DECL + && TREE_CODE (t) != EXC_PTR_EXPR) + { + if (TREE_CODE (t) == ARRAY_REF) + try_replace_operand (&TREE_OPERAND (t, 1)); + + tptr = &TREE_OPERAND (t, 0); + t = *tptr; + } + if (t) + try_replace_operand (tptr); +} + +/* Repalce the static references that exist in a constructor. */ + +static void +try_replace_constructor (tree ctor) +{ + tree t; + for (t = TREE_OPERAND (ctor, 0); t; t = TREE_CHAIN (t)) + { + try_replace (&TREE_VALUE (t)); + } +} + +/* Replace all the static references in the operand list of + CALL_EXPR. */ + +static void +try_replace_call_operands (tree call_expr) +{ + tree operandList = TREE_OPERAND (call_expr, 1); + tree operand; + + for (operand = operandList; + operand != NULL_TREE; + operand = TREE_CHAIN (operand)) + + if (TREE_CODE(TREE_VALUE (operand)) != FUNCTION_DECL) + try_replace (&TREE_VALUE (operand)); +} + +/* Generate loads and stores and replace all the static references in + function FN using statement iterator SI. This form is used when + there is not info available about the caller. */ + +static void +gen_dumb_call (tree fn, block_stmt_iterator si) +{ + gen_stores (local_written, NULL, &si); + try_replace (&TREE_OPERAND (fn, 0)); + try_replace_call_operands (fn); + gen_loads (local_all, NULL, &si); +} + + +/* Generate loads and stores and replace all the static references in + function FN using statement iterator SI. */ + +static void +try_replace_call (tree fn, block_stmt_iterator si) +{ + /* Store intersection of call_read and local_written + registers back to memory before calling. */ + /* int call_flags = call_expr_flags (fn); */ + tree callee = get_callee_fndecl (fn); + if (callee) + { + bitmap callee_all = BITMAP_ALLOC (&promote_obstack); + bitmap callee_written = ipa_reference_get_written_global (callee); + if (callee_written) + { + bitmap_ior (callee_all, + ipa_reference_get_read_global (callee), + callee_written); + + gen_stores (local_written, callee_all, &si); + + if (TREE_CODE (callee) != FUNCTION_DECL) + try_replace (&TREE_OPERAND (fn, 0)); + try_replace_call_operands (fn); + + /* This is a hack required because the call_flags are set on a + function by function basis during compilation. Thus these + flags are only set if the callee has already been compiled. */ + /* if (!(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN))) */ + gen_loads (local_all, callee_written, &si); + BITMAP_FREE (callee_all); + } + else + gen_dumb_call (fn, si); + } + else + gen_dumb_call (fn, si); +} + + +/* Walk the entire function looking uses or stores to global variables + and changing them to use ssa shadow registers. */ + +static void +walk_function (void) +{ + basic_block bb; + block_stmt_iterator si, ni; + + FOR_EACH_BB (bb) + for (si = bsi_start (bb); !bsi_end_p (si); si = ni) + { + tree stmt = bsi_stmt (si); + + ni = si; + bsi_next (&ni); + + switch (TREE_CODE (stmt)) + { + case RETURN_EXPR: + /* Store all of the local_written registers back to memory + before returning. */ + gen_stores (local_written, NULL, &si); + break; + + case MODIFY_EXPR: + /* Change load of static to use of reg. Change store of + static to store of reg. */ + { + tree rhs = TREE_OPERAND (stmt, 1); + tree *rhsp = &TREE_OPERAND (stmt, 1); + tree *lhsp = &TREE_OPERAND (stmt, 0); + + /* If we have a call on the rhs, try to replace the arguments. + Otherwise, try to replace the operand on the LHS and the operand on + the RHS. */ + if (TREE_CODE (rhs) == CALL_EXPR) + try_replace_call (rhs, si); + else if (TREE_CODE (rhs) == CONSTRUCTOR) + try_replace_constructor (rhs); + else + try_replace (rhsp); + try_replace (lhsp); + } + break; + case CALL_EXPR: + try_replace_call (stmt, si); + + break; + case ASM_EXPR: + /* If the asm clobbers memory, just store everything and + load it back. */ + if (asm_clobbers_mem (stmt)) + { + gen_stores (local_written, NULL, &si); + gen_loads (local_all, NULL, &si); + } + else + { + bitmap store_bitmap = BITMAP_ALLOC (&promote_obstack); + bitmap load_bitmap = BITMAP_ALLOC (&promote_obstack); + bitmap all_bitmap = BITMAP_ALLOC (&promote_obstack); + /* The asm read generates a stores before, and the asm + write generates loads after. */ + get_asm_read_and_write (store_bitmap, load_bitmap, stmt); + bitmap_ior (all_bitmap, store_bitmap, load_bitmap); + + gen_stores (local_written, all_bitmap , &si); + gen_loads (local_all, load_bitmap, &si); + + BITMAP_FREE (store_bitmap); + BITMAP_FREE (load_bitmap); + BITMAP_FREE (all_bitmap); + } + break; + + default: + break; + } + } +} + +/* Main entry point for the promotion of statics to ssa regsisters. */ + +static void +execute_promote_statics (void) +{ + unsigned int index; + bitmap_iterator bi; + bitmap tb = ipa_reference_get_read_local (current_function_decl); + + + /* There are some options that cause this pass to run even if file + at a time is not set. */ + if (!tb) + return; + + bitmap_obstack_initialize (&promote_obstack); + sra_init_cache (); + + local_read = BITMAP_ALLOC (&promote_obstack); + bitmap_copy (local_read, tb); + tb = ipa_reference_get_written_local (current_function_decl); + local_written = BITMAP_ALLOC (&promote_obstack); + bitmap_copy (local_written, tb); + + local_all = BITMAP_ALLOC (&promote_obstack); + tb = BITMAP_ALLOC (&promote_obstack); + bitmap_ior (local_all, local_read, local_written); + + if (dump_file) + fprintf (dump_file, "promoting in %s\n", + lang_hooks.decl_printable_name (current_function_decl, 2)); + + EXECUTE_IF_SET_IN_BITMAP (local_all, 0, index, bi) + { + tree svar = referenced_var_lookup_if_exists (index); + if (svar) + { + tree type = TREE_TYPE (svar); + /* We only promote variables that are either scalars or if + they are aggregrates, they must be a type that sra is + willing to scalarize. Otherwise there is no reason to + promote it a register. + + We also do not promote anything that is marked READONLY + since there is little gain. The optimizations should + generally be able to look thru the operations and find the + constants. */ + if ((!TREE_READONLY(svar)) + && (TREE_CODE (type) != ARRAY_TYPE) + && ((!AGGREGATE_TYPE_P (type)) + || (sra_type_can_be_decomposed_p (type)))) + { + tree tmp = create_tmp_var (type, get_name (svar)); + add_referenced_tmp_var (tmp); + var_ann (svar)->common.aux = tmp; + + /* Insert loads from all read statics in the entry + block. */ + insert_edge_copies (build (MODIFY_EXPR, TREE_TYPE (svar), + tmp, svar), + ENTRY_BLOCK_PTR); + if (dump_file) + fprintf (dump_file, " var=%s, read=%d,write=%d\n", + get_name (svar), + bitmap_bit_p (local_read, index), + bitmap_bit_p (local_written, index)); + } + else + /* There is nothing to be done with this variable. */ + bitmap_set_bit (tb, index); + } + else + /* There is nothing to be done with this variable because the + reference was optimized out before we got here. */ + bitmap_set_bit (tb, index); + } + + /* Clear the to be ignored variables from the local maps. */ + bitmap_and_compl_into (local_read, tb); + bitmap_and_compl_into (local_written, tb); + bitmap_and_compl_into (local_all, tb); + + walk_function (); + bsi_commit_edge_inserts (); + + EXECUTE_IF_SET_IN_BITMAP (local_all, 0, index, bi) + { + tree svar = referenced_var (index); + var_ann (svar)->common.aux = NULL; + } + + bitmap_obstack_release (&promote_obstack); +} + +static bool +gate_promote_statics (void) +{ + return flag_unit_at_a_time != 0 + && flag_ipa_reference + && flag_tree_promote_statics; +} + +struct tree_opt_pass pass_promote_statics = +{ + "tree-promote-static", /* name */ + gate_promote_statics, /* gate */ + execute_promote_statics, /* execute */ + NULL, /* sub */ + NULL, /* next */ + 0, /* static_pass_number */ + TV_TREE_PROMOTE_STATICS, /* tv_id */ + PROP_cfg, /* properties_required */ + 0, /* properties_provided */ + 0, /* properties_destroyed */ + 0, /* todo_flags_start */ + TODO_dump_func, /* todo_flags_finish */ + 0 /* letter */ +}; + + diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c index 62b45e2b304..b3494af5c92 100644 --- a/gcc/tree-sra.c +++ b/gcc/tree-sra.c @@ -172,8 +172,8 @@ is_sra_scalar_type (tree type) instantiated, just that if we decide to break up the type into separate pieces that it can be done. */ -static bool -type_can_be_decomposed_p (tree type) +bool +sra_type_can_be_decomposed_p (tree type) { unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2; tree t; @@ -275,7 +275,7 @@ decl_can_be_decomposed_p (tree var) } /* We must be able to decompose the variable's type. */ - if (!type_can_be_decomposed_p (TREE_TYPE (var))) + if (!sra_type_can_be_decomposed_p (TREE_TYPE (var))) { if (dump_file && (dump_flags & TDF_DETAILS)) { @@ -296,7 +296,7 @@ type_can_instantiate_all_elements (tree type) { if (is_sra_scalar_type (type)) return true; - if (!type_can_be_decomposed_p (type)) + if (!sra_type_can_be_decomposed_p (type)) return false; switch (TREE_CODE (type)) @@ -1769,7 +1769,7 @@ insert_edge_copies (tree stmt, basic_block bb) /* Helper function to insert LIST before BSI, and set up line number info. */ -static void +void sra_insert_before (block_stmt_iterator *bsi, tree list) { tree stmt = bsi_stmt (*bsi); @@ -1781,7 +1781,7 @@ sra_insert_before (block_stmt_iterator *bsi, tree list) /* Similarly, but insert after BSI. Handles insertion onto edges as well. */ -static void +void sra_insert_after (block_stmt_iterator *bsi, tree list) { tree stmt = bsi_stmt (*bsi); @@ -2138,6 +2138,16 @@ debug_sra_elt_name (struct sra_elt *elt) fputc ('\n', stderr); } +void +sra_init_cache (void) +{ + if (sra_type_decomp_cache) + return; + + sra_type_decomp_cache = BITMAP_ALLOC (NULL); + sra_type_inst_cache = BITMAP_ALLOC (NULL); +} + /* Main entry point. */ static void @@ -2147,8 +2157,7 @@ tree_sra (void) gcc_obstack_init (&sra_obstack); sra_candidates = BITMAP_ALLOC (NULL); needs_copy_in = BITMAP_ALLOC (NULL); - sra_type_decomp_cache = BITMAP_ALLOC (NULL); - sra_type_inst_cache = BITMAP_ALLOC (NULL); + sra_init_cache (); sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, NULL); /* Scan. If we find anything, instantiate and scalarize. */ diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c index 75dbbb43880..387a6961cd5 100644 --- a/gcc/tree-ssa-alias.c +++ b/gcc/tree-ssa-alias.c @@ -43,6 +43,7 @@ Boston, MA 02110-1301, USA. */ #include "tree-ssa-structalias.h" #include "convert.h" #include "params.h" +#include "ipa-type-escape.h" #include "vec.h" #include "bitmap.h" @@ -86,6 +87,8 @@ struct alias_stats_d unsigned int simple_resolved; unsigned int tbaa_queries; unsigned int tbaa_resolved; + unsigned int structnoaddress_queries; + unsigned int structnoaddress_resolved; }; @@ -95,7 +98,7 @@ static struct alias_stats_d alias_stats; /* Local functions. */ static void compute_flow_insensitive_aliasing (struct alias_info *); static void dump_alias_stats (FILE *); -static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT); +static bool may_alias_p (tree, HOST_WIDE_INT, tree, HOST_WIDE_INT, bool); static tree create_memory_tag (tree type, bool is_type_tag); static tree get_tmt_for (tree, struct alias_info *); static tree get_nmt_for (tree); @@ -346,6 +349,7 @@ count_ptr_derefs (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED, void *data) struct count_ptr_d *count_p = (struct count_ptr_d *) data; if (INDIRECT_REF_P (*tp) && TREE_OPERAND (*tp, 0) == count_p->ptr) +/* || (TREE_CODE (*tp) == MEM_REF && MEM_REF_SYMBOL (*tp) == count_p->ptr)) */ count_p->count++; return NULL_TREE; @@ -433,7 +437,6 @@ count_uses_and_derefs (tree ptr, tree stmt, unsigned *num_uses_p, gcc_assert (*num_uses_p >= *num_derefs_p); } - /* Initialize the data structures used for alias analysis. */ static struct alias_info * @@ -780,8 +783,8 @@ compute_flow_insensitive_aliasing (struct alias_info *ai) || bitmap_bit_p (ai->written_vars, DECL_UID (var)); if (!tag_stored_p && !var_stored_p) continue; - - if (may_alias_p (p_map->var, p_map->set, var, v_map->set)) + + if (may_alias_p (p_map->var, p_map->set, var, v_map->set, false)) { subvar_t svars; size_t num_tag_refs, num_var_refs; @@ -862,7 +865,7 @@ compute_flow_insensitive_aliasing (struct alias_info *ai) bitmap may_aliases2 = p_map2->may_aliases; /* If the pointers may not point to each other, do nothing. */ - if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set)) + if (!may_alias_p (p_map1->var, p_map1->set, tag2, p_map2->set, true)) continue; /* The two pointers may alias each other. If they already have @@ -1453,7 +1456,8 @@ maybe_create_global_var (struct alias_info *ai) static bool may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set, - tree var, HOST_WIDE_INT var_alias_set) + tree var, HOST_WIDE_INT var_alias_set, + bool alias_set_only) { tree mem; var_ann_t m_ann; @@ -1520,6 +1524,65 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set, alias_stats.tbaa_resolved++; return false; } + + /* If var is a record or union type, ptr cannot point into var + unless there is some operation explicit address operation in the + program that can reference a field of the ptr's dereferenced + type. This also assumes that the types of both var and ptr are + contained within the compilation unit, and that there is no fancy + addressing arithmetic associated with any of the types + involved. */ + + if ((mem_alias_set != 0) && (var_alias_set != 0)) + { + tree ptr_type = TREE_TYPE (ptr); + tree var_type = TREE_TYPE (var); + + /* The star count is -1 if the type at the end of the pointer_to + chain is not a record or union type. */ + if ((!alias_set_only) && + ipa_type_escape_star_count_of_interesting_type (var_type) >= 0) + { + int ptr_star_count = 0; + + /* Ipa_type_escape_star_count_of_interesting_type is a little to + restrictive for the pointer type, need to allow pointers to + primitive types as long as those types cannot be pointers + to everything. */ + while (POINTER_TYPE_P (ptr_type)) + /* Strip the *'s off. */ + { + ptr_type = TREE_TYPE (ptr_type); + ptr_star_count++; + } + + /* There does not appear to be a better test to see if the + pointer type was one of the pointer to everything + types. */ + + if (ptr_star_count > 0) + { + alias_stats.structnoaddress_queries++; + if (ipa_type_escape_field_does_not_clobber_p (var_type, + TREE_TYPE (ptr))) + { + alias_stats.structnoaddress_resolved++; + alias_stats.alias_noalias++; + return false; + } + } + else if (ptr_star_count == 0) + { + /* If ptr_type was not really a pointer to type, it cannot + alias. */ + alias_stats.structnoaddress_queries++; + alias_stats.structnoaddress_resolved++; + alias_stats.alias_noalias++; + return false; + } + } + } + alias_stats.alias_mayalias++; return true; } @@ -1851,6 +1914,10 @@ dump_alias_stats (FILE *file) alias_stats.tbaa_queries); fprintf (file, "Total TBAA resolved:\t%u\n", alias_stats.tbaa_resolved); + fprintf (file, "Total non-addressable structure type queries:\t%u\n", + alias_stats.structnoaddress_queries); + fprintf (file, "Total non-addressable structure type resolved:\t%u\n", + alias_stats.structnoaddress_resolved); } diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c index f4eb109c5c7..609fa0f947c 100644 --- a/gcc/tree-ssa-operands.c +++ b/gcc/tree-ssa-operands.c @@ -33,6 +33,7 @@ Boston, MA 02110-1301, USA. */ #include "timevar.h" #include "toplev.h" #include "langhooks.h" +#include "ipa-reference.h" /* This file contains the code required to manage the operands cache of the SSA optimizer. For every stmt, we maintain an operand cache in the stmt @@ -156,7 +157,7 @@ static inline void append_def (tree *); static inline void append_use (tree *); static void append_v_may_def (tree); static void append_v_must_def (tree); -static void add_call_clobber_ops (tree); +static void add_call_clobber_ops (tree, tree); static void add_call_read_ops (tree); static void add_stmt_operand (tree *, stmt_ann_t, int); static void build_ssa_operands (tree stmt); @@ -1727,7 +1728,7 @@ get_call_expr_operands (tree stmt, tree expr) there is no point in recording that. */ if (TREE_SIDE_EFFECTS (expr) && !(call_flags & (ECF_PURE | ECF_CONST | ECF_NORETURN))) - add_call_clobber_ops (stmt); + add_call_clobber_ops (stmt, get_callee_fndecl (expr)); else if (!(call_flags & ECF_CONST)) add_call_read_ops (stmt); } @@ -1944,7 +1945,7 @@ add_to_addressable_set (tree ref, bitmap *addresses_taken) clobbered variables in the function. */ static void -add_call_clobber_ops (tree stmt) +add_call_clobber_ops (tree stmt, tree callee) { int i; unsigned u; @@ -1952,6 +1953,7 @@ add_call_clobber_ops (tree stmt) bitmap_iterator bi; stmt_ann_t s_ann = stmt_ann (stmt); struct stmt_ann_d empty_ann; + bitmap not_read_b, not_written_b; /* Functions that are not const, pure or never return may clobber call-clobbered variables. */ @@ -1966,8 +1968,22 @@ add_call_clobber_ops (tree stmt) return; } + /* FIXME - if we have better information from the static vars + analysis, we need to make the cache call site specific. This way + we can have the performance benefits even if we are doing good + optimization. */ + + /* Get info for local and module level statics. There is a bit + set for each static if the call being processed does not read + or write that variable. */ + + not_read_b = callee ? ipa_reference_get_not_read_global (callee) : NULL; + not_written_b = callee ? ipa_reference_get_not_written_global (callee) : NULL; + /* If cache is valid, copy the elements into the build vectors. */ - if (ssa_call_clobbered_cache_valid) + if (ssa_call_clobbered_cache_valid + && (!not_read_b || bitmap_empty_p (not_read_b)) + && (!not_written_b || bitmap_empty_p (not_written_b))) { /* Process the caches in reverse order so we are always inserting at the head of the list. */ @@ -2002,43 +2018,62 @@ add_call_clobber_ops (tree stmt) if (unmodifiable_var_p (var)) add_stmt_operand (&var, &empty_ann, opf_none); else - add_stmt_operand (&var, &empty_ann, opf_is_def | opf_non_specific); + { + bool not_read + = not_read_b ? bitmap_bit_p (not_read_b, u) : false; + bool not_written + = not_written_b ? bitmap_bit_p (not_written_b, u) : false; + + if ((TREE_READONLY (var) + && (TREE_STATIC (var) || DECL_EXTERNAL (var))) + || not_written) + { + if (!not_read) + add_stmt_operand (&var, &empty_ann, opf_none); + } + else + add_stmt_operand (&var, &empty_ann, opf_is_def); + } } - clobbered_aliased_loads = empty_ann.makes_aliased_loads; - clobbered_aliased_stores = empty_ann.makes_aliased_stores; - - /* Set the flags for a stmt's annotation. */ - if (s_ann) + if ((!not_read_b || bitmap_empty_p (not_read_b)) + && (!not_written_b || bitmap_empty_p (not_written_b))) { - s_ann->makes_aliased_loads = empty_ann.makes_aliased_loads; - s_ann->makes_aliased_stores = empty_ann.makes_aliased_stores; - } + clobbered_aliased_loads = empty_ann.makes_aliased_loads; + clobbered_aliased_stores = empty_ann.makes_aliased_stores; - /* Prepare empty cache vectors. */ - VEC_truncate (tree, clobbered_vuses, 0); - VEC_truncate (tree, clobbered_v_may_defs, 0); + /* Set the flags for a stmt's annotation. */ + if (s_ann) + { + s_ann->makes_aliased_loads = empty_ann.makes_aliased_loads; + s_ann->makes_aliased_stores = empty_ann.makes_aliased_stores; + } - /* Now fill the clobbered cache with the values that have been found. */ - for (i = opbuild_first (&build_vuses); - i != OPBUILD_LAST; - i = opbuild_next (&build_vuses, i)) - VEC_safe_push (tree, heap, clobbered_vuses, - opbuild_elem_virtual (&build_vuses, i)); + /* Prepare empty cache vectors. */ + VEC_truncate (tree, clobbered_vuses, 0); + VEC_truncate (tree, clobbered_v_may_defs, 0); - gcc_assert (opbuild_num_elems (&build_vuses) - == VEC_length (tree, clobbered_vuses)); + /* Now fill the clobbered cache with the values that have been found. */ + for (i = opbuild_first (&build_vuses); + i != OPBUILD_LAST; + i = opbuild_next (&build_vuses, i)) + VEC_safe_push (tree, heap, clobbered_vuses, + opbuild_elem_virtual (&build_vuses, i)); - for (i = opbuild_first (&build_v_may_defs); - i != OPBUILD_LAST; - i = opbuild_next (&build_v_may_defs, i)) - VEC_safe_push (tree, heap, clobbered_v_may_defs, - opbuild_elem_virtual (&build_v_may_defs, i)); + gcc_assert (opbuild_num_elems (&build_vuses) + == VEC_length (tree, clobbered_vuses)); + + for (i = opbuild_first (&build_v_may_defs); + i != OPBUILD_LAST; + i = opbuild_next (&build_v_may_defs, i)) + VEC_safe_push (tree, heap, clobbered_v_may_defs, + opbuild_elem_virtual (&build_v_may_defs, i)); - gcc_assert (opbuild_num_elems (&build_v_may_defs) - == VEC_length (tree, clobbered_v_may_defs)); + gcc_assert (opbuild_num_elems (&build_v_may_defs) + == VEC_length (tree, clobbered_v_may_defs)); - ssa_call_clobbered_cache_valid = true; + ssa_call_clobbered_cache_valid = true; + } } |