1 /* Data flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 Contributed by Diego Novillo <dnovillo@redhat.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING. If not, write to
19 the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20 Boston, MA 02110-1301, USA. */
24 #include "coretypes.h"
27 #include "pointer-set.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
37 #include "langhooks.h"
40 #include "diagnostic.h"
41 #include "tree-dump.h"
42 #include "tree-gimple.h"
43 #include "tree-flow.h"
44 #include "tree-inline.h"
45 #include "tree-pass.h"
50 /* Build and maintain data flow information for trees. */
52 /* Counters used to display DFA and SSA statistics. */
68 /* Local functions. */
69 static void collect_dfa_stats (struct dfa_stats_d
*);
70 static tree
collect_dfa_stats_r (tree
*, int *, void *);
71 static tree
find_vars_r (tree
*, int *, void *);
74 /* Global declarations. */
76 /* Array of all variables referenced in the function. */
77 htab_t referenced_vars
;
78 /* List of referenced variables with duplicate UID's. */
79 VEC(tree
,gc
) *referenced_vars_dup_list
;
81 /* Default definition for this symbols. If set for symbol, it
82 means that the first reference to this variable in the function is a
83 USE or a VUSE. In those cases, the SSA renamer creates an SSA name
84 for this variable with an empty defining statement. */
88 /*---------------------------------------------------------------------------
89 Dataflow analysis (DFA) routines
90 ---------------------------------------------------------------------------*/
91 /* Find all the variables referenced in the function. This function
92 builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
94 Note that this function does not look for statement operands, it simply
95 determines what variables are referenced in the program and detects
96 various attributes for each variable used by alias analysis and the
100 find_referenced_vars (void)
103 block_stmt_iterator si
;
105 gcc_assert (VEC_length (tree
, referenced_vars_dup_list
) == 0);
107 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
109 tree
*stmt_p
= bsi_stmt_ptr (si
);
110 walk_tree (stmt_p
, find_vars_r
, NULL
, NULL
);
116 struct tree_opt_pass pass_referenced_vars
=
120 find_referenced_vars
, /* execute */
123 0, /* static_pass_number */
124 TV_FIND_REFERENCED_VARS
, /* tv_id */
125 PROP_gimple_leh
| PROP_cfg
, /* properties_required */
126 PROP_referenced_vars
, /* properties_provided */
127 0, /* properties_destroyed */
128 0, /* todo_flags_start */
129 0, /* todo_flags_finish */
134 /*---------------------------------------------------------------------------
136 ---------------------------------------------------------------------------*/
137 /* Create a new annotation for a _DECL node T. */
140 create_var_ann (tree t
)
145 gcc_assert (DECL_P (t
));
146 gcc_assert (!t
->common
.ann
|| t
->common
.ann
->common
.type
== VAR_ANN
);
148 ann
= GGC_NEW (struct var_ann_d
);
149 memset ((void *) ann
, 0, sizeof (*ann
));
151 ann
->common
.type
= VAR_ANN
;
153 t
->common
.ann
= (tree_ann_t
) ann
;
158 /* Create a new annotation for a FUNCTION_DECL node T. */
161 create_function_ann (tree t
)
166 gcc_assert (TREE_CODE (t
) == FUNCTION_DECL
);
167 gcc_assert (!t
->common
.ann
|| t
->common
.ann
->common
.type
== FUNCTION_ANN
);
169 ann
= ggc_alloc (sizeof (*ann
));
170 memset ((void *) ann
, 0, sizeof (*ann
));
172 ann
->common
.type
= FUNCTION_ANN
;
174 t
->common
.ann
= (tree_ann_t
) ann
;
179 /* Create a new annotation for a statement node T. */
182 create_stmt_ann (tree t
)
186 gcc_assert (is_gimple_stmt (t
));
187 gcc_assert (!t
->common
.ann
|| t
->common
.ann
->common
.type
== STMT_ANN
);
189 ann
= GGC_NEW (struct stmt_ann_d
);
190 memset ((void *) ann
, 0, sizeof (*ann
));
192 ann
->common
.type
= STMT_ANN
;
194 /* Since we just created the annotation, mark the statement modified. */
195 ann
->modified
= true;
197 t
->common
.ann
= (tree_ann_t
) ann
;
202 /* Create a new annotation for a tree T. */
205 create_tree_ann (tree t
)
210 gcc_assert (!t
->common
.ann
|| t
->common
.ann
->common
.type
== TREE_ANN_COMMON
);
212 ann
= GGC_NEW (union tree_ann_d
);
213 memset ((void *) ann
, 0, sizeof (*ann
));
215 ann
->common
.type
= TREE_ANN_COMMON
;
221 /* Build a temporary. Make sure and register it to be renamed. */
224 make_rename_temp (tree type
, const char *prefix
)
226 tree t
= create_tmp_var (type
, prefix
);
228 if (TREE_CODE (type
) == COMPLEX_TYPE
)
229 DECL_COMPLEX_GIMPLE_REG_P (t
) = 1;
233 add_referenced_var (t
);
234 mark_sym_for_renaming (t
);
242 /*---------------------------------------------------------------------------
244 ---------------------------------------------------------------------------*/
245 /* Dump the list of all the referenced variables in the current function to
249 dump_referenced_vars (FILE *file
)
252 referenced_var_iterator rvi
;
254 fprintf (file
, "\nReferenced variables in %s: %u\n\n",
255 get_name (current_function_decl
), (unsigned) num_referenced_vars
);
257 FOR_EACH_REFERENCED_VAR (var
, rvi
)
259 fprintf (file
, "Variable: ");
260 dump_variable (file
, var
);
261 fprintf (file
, "\n");
266 /* Dump the list of all the referenced variables to stderr. */
269 debug_referenced_vars (void)
271 dump_referenced_vars (stderr
);
275 /* Dump sub-variables for VAR to FILE. */
278 dump_subvars_for (FILE *file
, tree var
)
280 subvar_t sv
= get_subvars_for_var (var
);
285 fprintf (file
, "{ ");
287 for (; sv
; sv
= sv
->next
)
289 print_generic_expr (file
, sv
->var
, dump_flags
);
297 /* Dumb sub-variables for VAR to stderr. */
300 debug_subvars_for (tree var
)
302 dump_subvars_for (stderr
, var
);
306 /* Dump variable VAR and its may-aliases to FILE. */
309 dump_variable (FILE *file
, tree var
)
313 if (TREE_CODE (var
) == SSA_NAME
)
315 if (POINTER_TYPE_P (TREE_TYPE (var
)))
316 dump_points_to_info_for (file
, var
);
317 var
= SSA_NAME_VAR (var
);
320 if (var
== NULL_TREE
)
322 fprintf (file
, "<nil>");
326 print_generic_expr (file
, var
, dump_flags
);
330 fprintf (file
, ", UID %u", (unsigned) DECL_UID (var
));
332 fprintf (file
, ", ");
333 print_generic_expr (file
, TREE_TYPE (var
), dump_flags
);
335 if (ann
&& ann
->symbol_mem_tag
)
337 fprintf (file
, ", symbol memory tag: ");
338 print_generic_expr (file
, ann
->symbol_mem_tag
, dump_flags
);
341 if (ann
&& ann
->is_aliased
)
342 fprintf (file
, ", is aliased");
344 if (TREE_ADDRESSABLE (var
))
345 fprintf (file
, ", is addressable");
347 if (is_global_var (var
))
348 fprintf (file
, ", is global");
350 if (TREE_THIS_VOLATILE (var
))
351 fprintf (file
, ", is volatile");
353 if (is_call_clobbered (var
))
355 fprintf (file
, ", call clobbered");
356 if (dump_flags
& TDF_DETAILS
)
358 var_ann_t va
= var_ann (var
);
359 unsigned int escape_mask
= va
->escape_mask
;
361 fprintf (file
, " (");
362 if (escape_mask
& ESCAPE_STORED_IN_GLOBAL
)
363 fprintf (file
, ", stored in global");
364 if (escape_mask
& ESCAPE_TO_ASM
)
365 fprintf (file
, ", goes through ASM");
366 if (escape_mask
& ESCAPE_TO_CALL
)
367 fprintf (file
, ", passed to call");
368 if (escape_mask
& ESCAPE_BAD_CAST
)
369 fprintf (file
, ", bad cast");
370 if (escape_mask
& ESCAPE_TO_RETURN
)
371 fprintf (file
, ", returned from func");
372 if (escape_mask
& ESCAPE_TO_PURE_CONST
)
373 fprintf (file
, ", passed to pure/const");
374 if (escape_mask
& ESCAPE_IS_GLOBAL
)
375 fprintf (file
, ", is global var");
376 if (escape_mask
& ESCAPE_IS_PARM
)
377 fprintf (file
, ", is incoming pointer");
378 if (escape_mask
& ESCAPE_UNKNOWN
)
379 fprintf (file
, ", unknown escape");
380 fprintf (file
, " )");
384 if (default_def (var
))
386 fprintf (file
, ", default def: ");
387 print_generic_expr (file
, default_def (var
), dump_flags
);
390 if (may_aliases (var
))
392 fprintf (file
, ", may aliases: ");
393 dump_may_aliases_for (file
, var
);
396 if (get_subvars_for_var (var
))
398 fprintf (file
, ", sub-vars: ");
399 dump_subvars_for (file
, var
);
402 fprintf (file
, "\n");
406 /* Dump variable VAR and its may-aliases to stderr. */
409 debug_variable (tree var
)
411 dump_variable (stderr
, var
);
415 /* Dump various DFA statistics to FILE. */
418 dump_dfa_stats (FILE *file
)
420 struct dfa_stats_d dfa_stats
;
422 unsigned long size
, total
= 0;
423 const char * const fmt_str
= "%-30s%-13s%12s\n";
424 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
425 const char * const fmt_str_3
= "%-43s%11lu%c\n";
427 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
429 collect_dfa_stats (&dfa_stats
);
431 fprintf (file
, "\nDFA Statistics for %s\n\n", funcname
);
433 fprintf (file
, "---------------------------------------------------------\n");
434 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
435 fprintf (file
, fmt_str
, "", " instances ", "used ");
436 fprintf (file
, "---------------------------------------------------------\n");
438 size
= num_referenced_vars
* sizeof (tree
);
440 fprintf (file
, fmt_str_1
, "Referenced variables", (unsigned long)num_referenced_vars
,
441 SCALE (size
), LABEL (size
));
443 size
= dfa_stats
.num_stmt_anns
* sizeof (struct stmt_ann_d
);
445 fprintf (file
, fmt_str_1
, "Statements annotated", dfa_stats
.num_stmt_anns
,
446 SCALE (size
), LABEL (size
));
448 size
= dfa_stats
.num_var_anns
* sizeof (struct var_ann_d
);
450 fprintf (file
, fmt_str_1
, "Variables annotated", dfa_stats
.num_var_anns
,
451 SCALE (size
), LABEL (size
));
453 size
= dfa_stats
.num_uses
* sizeof (tree
*);
455 fprintf (file
, fmt_str_1
, "USE operands", dfa_stats
.num_uses
,
456 SCALE (size
), LABEL (size
));
458 size
= dfa_stats
.num_defs
* sizeof (tree
*);
460 fprintf (file
, fmt_str_1
, "DEF operands", dfa_stats
.num_defs
,
461 SCALE (size
), LABEL (size
));
463 size
= dfa_stats
.num_vuses
* sizeof (tree
*);
465 fprintf (file
, fmt_str_1
, "VUSE operands", dfa_stats
.num_vuses
,
466 SCALE (size
), LABEL (size
));
468 size
= dfa_stats
.num_v_may_defs
* sizeof (tree
*);
470 fprintf (file
, fmt_str_1
, "V_MAY_DEF operands", dfa_stats
.num_v_may_defs
,
471 SCALE (size
), LABEL (size
));
473 size
= dfa_stats
.num_v_must_defs
* sizeof (tree
*);
475 fprintf (file
, fmt_str_1
, "V_MUST_DEF operands", dfa_stats
.num_v_must_defs
,
476 SCALE (size
), LABEL (size
));
478 size
= dfa_stats
.num_phis
* sizeof (struct tree_phi_node
);
480 fprintf (file
, fmt_str_1
, "PHI nodes", dfa_stats
.num_phis
,
481 SCALE (size
), LABEL (size
));
483 size
= dfa_stats
.num_phi_args
* sizeof (struct phi_arg_d
);
485 fprintf (file
, fmt_str_1
, "PHI arguments", dfa_stats
.num_phi_args
,
486 SCALE (size
), LABEL (size
));
488 fprintf (file
, "---------------------------------------------------------\n");
489 fprintf (file
, fmt_str_3
, "Total memory used by DFA/SSA data", SCALE (total
),
491 fprintf (file
, "---------------------------------------------------------\n");
492 fprintf (file
, "\n");
494 if (dfa_stats
.num_phis
)
495 fprintf (file
, "Average number of arguments per PHI node: %.1f (max: %d)\n",
496 (float) dfa_stats
.num_phi_args
/ (float) dfa_stats
.num_phis
,
497 dfa_stats
.max_num_phi_args
);
499 fprintf (file
, "\n");
503 /* Dump DFA statistics on stderr. */
506 debug_dfa_stats (void)
508 dump_dfa_stats (stderr
);
512 /* Collect DFA statistics and store them in the structure pointed to by
516 collect_dfa_stats (struct dfa_stats_d
*dfa_stats_p
)
518 struct pointer_set_t
*pset
;
520 block_stmt_iterator i
;
522 gcc_assert (dfa_stats_p
);
524 memset ((void *)dfa_stats_p
, 0, sizeof (struct dfa_stats_d
));
526 /* Walk all the trees in the function counting references. Start at
527 basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */
528 pset
= pointer_set_create ();
530 for (i
= bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS
));
531 !bsi_end_p (i
); bsi_next (&i
))
532 walk_tree (bsi_stmt_ptr (i
), collect_dfa_stats_r
, (void *) dfa_stats_p
,
535 pointer_set_destroy (pset
);
540 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
542 dfa_stats_p
->num_phis
++;
543 dfa_stats_p
->num_phi_args
+= PHI_NUM_ARGS (phi
);
544 if (PHI_NUM_ARGS (phi
) > dfa_stats_p
->max_num_phi_args
)
545 dfa_stats_p
->max_num_phi_args
= PHI_NUM_ARGS (phi
);
551 /* Callback for walk_tree to collect DFA statistics for a tree and its
555 collect_dfa_stats_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
559 struct dfa_stats_d
*dfa_stats_p
= (struct dfa_stats_d
*)data
;
563 switch (ann_type (t
->common
.ann
))
567 dfa_stats_p
->num_stmt_anns
++;
568 dfa_stats_p
->num_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_DEF
);
569 dfa_stats_p
->num_uses
+= NUM_SSA_OPERANDS (t
, SSA_OP_USE
);
570 dfa_stats_p
->num_v_may_defs
+= NUM_SSA_OPERANDS (t
, SSA_OP_VMAYDEF
);
571 dfa_stats_p
->num_vuses
+= NUM_SSA_OPERANDS (t
, SSA_OP_VUSE
);
572 dfa_stats_p
->num_v_must_defs
+=
573 NUM_SSA_OPERANDS (t
, SSA_OP_VMUSTDEF
);
578 dfa_stats_p
->num_var_anns
++;
590 /*---------------------------------------------------------------------------
591 Miscellaneous helpers
592 ---------------------------------------------------------------------------*/
593 /* Callback for walk_tree. Used to collect variables referenced in
597 find_vars_r (tree
*tp
, int *walk_subtrees
, void *data ATTRIBUTE_UNUSED
)
599 /* If T is a regular variable that the optimizers are interested
600 in, add it to the list of variables. */
602 add_referenced_var (*tp
);
604 /* Type, _DECL and constant nodes have no interesting children.
606 else if (IS_TYPE_OR_DECL_P (*tp
) || CONSTANT_CLASS_P (*tp
))
612 /* Lookup UID in the referenced_vars hashtable and return the associated
616 referenced_var_lookup (unsigned int uid
)
618 struct int_tree_map
*h
, in
;
620 h
= (struct int_tree_map
*) htab_find_with_hash (referenced_vars
, &in
, uid
);
621 gcc_assert (h
|| uid
== 0);
627 /* Check if TO is in the referenced_vars hash table and insert it if not.
628 Return true if it required insertion. */
631 referenced_var_check_and_insert (tree to
)
633 struct int_tree_map
*h
, in
;
635 unsigned int uid
= DECL_UID (to
);
639 h
= (struct int_tree_map
*) htab_find_with_hash (referenced_vars
, &in
, uid
);
646 /* DECL_UID has already been entered in the table. Verify that it is
647 the same entry as TO. */
648 gcc_assert (h
->to
!= NULL
);
652 /* PRs 26757 and 27793. Maintain a list of duplicate variable pointers
653 with the same DECL_UID. There isn't usually very many.
654 TODO. Once the C++ front end doesn't create duplicate DECL UID's, this
655 code can be removed. */
656 for (u
= 0; u
< VEC_length (tree
, referenced_vars_dup_list
); u
++)
658 t
= VEC_index (tree
, referenced_vars_dup_list
, u
);
663 VEC_safe_push (tree
, gc
, referenced_vars_dup_list
, to
);
667 h
= GGC_NEW (struct int_tree_map
);
670 loc
= htab_find_slot_with_hash (referenced_vars
, h
, uid
, INSERT
);
671 *(struct int_tree_map
**) loc
= h
;
675 /* Lookup VAR UID in the default_defs hashtable and return the associated
679 default_def (tree var
)
681 struct int_tree_map
*h
, in
;
682 gcc_assert (SSA_VAR_P (var
));
683 in
.uid
= DECL_UID (var
);
684 h
= (struct int_tree_map
*) htab_find_with_hash (default_defs
, &in
,
691 /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
694 set_default_def (tree var
, tree def
)
696 struct int_tree_map in
;
697 struct int_tree_map
*h
;
700 gcc_assert (SSA_VAR_P (var
));
701 in
.uid
= DECL_UID (var
);
702 if (!def
&& default_def (var
))
704 loc
= htab_find_slot_with_hash (default_defs
, &in
, DECL_UID (var
), INSERT
);
705 htab_remove_elt (default_defs
, *loc
);
708 gcc_assert (TREE_CODE (def
) == SSA_NAME
);
709 loc
= htab_find_slot_with_hash (default_defs
, &in
, DECL_UID (var
), INSERT
);
710 /* Default definition might be changed by tail call optimization. */
713 h
= GGC_NEW (struct int_tree_map
);
714 h
->uid
= DECL_UID (var
);
716 *(struct int_tree_map
**) loc
= h
;
720 h
= (struct int_tree_map
*) *loc
;
725 /* Add VAR to the list of referenced variables if it isn't already there. */
728 add_referenced_var (tree var
)
732 v_ann
= get_var_ann (var
);
733 gcc_assert (DECL_P (var
));
735 /* Insert VAR into the referenced_vars has table if it isn't present. */
736 if (referenced_var_check_and_insert (var
))
738 /* This is the first time we found this variable, annotate it with
739 attributes that are intrinsic to the variable. */
741 /* Tag's don't have DECL_INITIAL. */
745 /* Scan DECL_INITIAL for pointer variables as they may contain
746 address arithmetic referencing the address of other
748 if (DECL_INITIAL (var
)
749 /* Initializers of external variables are not useful to the
751 && !DECL_EXTERNAL (var
)
752 /* It's not necessary to walk the initial value of non-constant
753 variables because it cannot be propagated by the
755 && (TREE_CONSTANT (var
) || TREE_READONLY (var
)))
756 walk_tree (&DECL_INITIAL (var
), find_vars_r
, NULL
, 0);
761 /* Return the virtual variable associated to the non-scalar variable VAR. */
764 get_virtual_var (tree var
)
768 if (TREE_CODE (var
) == SSA_NAME
)
769 var
= SSA_NAME_VAR (var
);
771 while (TREE_CODE (var
) == REALPART_EXPR
|| TREE_CODE (var
) == IMAGPART_EXPR
772 || handled_component_p (var
))
773 var
= TREE_OPERAND (var
, 0);
775 /* Treating GIMPLE registers as virtual variables makes no sense.
776 Also complain if we couldn't extract a _DECL out of the original
778 gcc_assert (SSA_VAR_P (var
));
779 gcc_assert (!is_gimple_reg (var
));
784 /* Mark all the non-SSA variables found in STMT's operands to be
785 processed by update_ssa. */
788 mark_new_vars_to_rename (tree stmt
)
792 bitmap vars_in_vops_to_rename
;
793 bool found_exposed_symbol
= false;
794 int v_may_defs_before
, v_may_defs_after
;
795 int v_must_defs_before
, v_must_defs_after
;
797 if (TREE_CODE (stmt
) == PHI_NODE
)
801 vars_in_vops_to_rename
= BITMAP_ALLOC (NULL
);
803 /* Before re-scanning the statement for operands, mark the existing
804 virtual operands to be renamed again. We do this because when new
805 symbols are exposed, the virtual operands that were here before due to
806 aliasing will probably be removed by the call to get_stmt_operand.
807 Therefore, we need to flag them to be renamed beforehand.
809 We flag them in a separate bitmap because we don't really want to
810 rename them if there are not any newly exposed symbols in the
811 statement operands. */
812 v_may_defs_before
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
);
813 v_must_defs_before
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMUSTDEF
);
815 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
,
816 SSA_OP_VMAYDEF
| SSA_OP_VUSE
| SSA_OP_VMUSTDEF
)
819 val
= SSA_NAME_VAR (val
);
820 bitmap_set_bit (vars_in_vops_to_rename
, DECL_UID (val
));
823 /* Now force an operand re-scan on the statement and mark any newly
824 exposed variables. */
827 v_may_defs_after
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMAYDEF
);
828 v_must_defs_after
= NUM_SSA_OPERANDS (stmt
, SSA_OP_VMUSTDEF
);
830 FOR_EACH_SSA_TREE_OPERAND (val
, stmt
, iter
, SSA_OP_ALL_OPERANDS
)
833 found_exposed_symbol
= true;
834 mark_sym_for_renaming (val
);
837 /* If we found any newly exposed symbols, or if there are fewer VDEF
838 operands in the statement, add the variables we had set in
839 VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME. We need to check for
840 vanishing VDEFs because in those cases, the names that were formerly
841 generated by this statement are not going to be available anymore. */
842 if (found_exposed_symbol
843 || v_may_defs_before
> v_may_defs_after
844 || v_must_defs_before
> v_must_defs_after
)
845 mark_set_for_renaming (vars_in_vops_to_rename
);
847 BITMAP_FREE (vars_in_vops_to_rename
);
850 /* Find all variables within the gimplified statement that were not previously
851 visible to the function and add them to the referenced variables list. */
854 find_new_referenced_vars_1 (tree
*tp
, int *walk_subtrees
,
855 void *data ATTRIBUTE_UNUSED
)
859 if (TREE_CODE (t
) == VAR_DECL
&& !var_ann (t
))
861 add_referenced_var (t
);
862 mark_sym_for_renaming (t
);
865 if (IS_TYPE_OR_DECL_P (t
))
872 find_new_referenced_vars (tree
*stmt_p
)
874 walk_tree (stmt_p
, find_new_referenced_vars_1
, NULL
, NULL
);
878 /* If REF is a handled component reference for a structure, return the
879 base variable. The access range is delimited by bit positions *POFFSET and
880 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
881 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
882 and *PMAX_SIZE are equal, the access is non-variable. */
885 get_ref_base_and_extent (tree exp
, HOST_WIDE_INT
*poffset
,
886 HOST_WIDE_INT
*psize
,
887 HOST_WIDE_INT
*pmax_size
)
889 HOST_WIDE_INT bitsize
= -1;
890 HOST_WIDE_INT maxsize
= -1;
891 tree size_tree
= NULL_TREE
;
892 tree bit_offset
= bitsize_zero_node
;
893 bool seen_variable_array_ref
= false;
895 gcc_assert (!SSA_VAR_P (exp
));
897 /* First get the final access size from just the outermost expression. */
898 if (TREE_CODE (exp
) == COMPONENT_REF
)
899 size_tree
= DECL_SIZE (TREE_OPERAND (exp
, 1));
900 else if (TREE_CODE (exp
) == BIT_FIELD_REF
)
901 size_tree
= TREE_OPERAND (exp
, 1);
904 enum machine_mode mode
= TYPE_MODE (TREE_TYPE (exp
));
906 size_tree
= TYPE_SIZE (TREE_TYPE (exp
));
908 bitsize
= GET_MODE_BITSIZE (mode
);
910 if (size_tree
!= NULL_TREE
)
912 if (! host_integerp (size_tree
, 1))
915 bitsize
= TREE_INT_CST_LOW (size_tree
);
918 /* Initially, maxsize is the same as the accessed element size.
919 In the following it will only grow (or become -1). */
922 /* Compute cumulative bit-offset for nested component-refs and array-refs,
923 and find the ultimate containing object. */
926 switch (TREE_CODE (exp
))
929 bit_offset
= size_binop (PLUS_EXPR
, bit_offset
,
930 TREE_OPERAND (exp
, 2));
935 tree field
= TREE_OPERAND (exp
, 1);
936 tree this_offset
= component_ref_field_offset (exp
);
938 if (this_offset
&& TREE_CODE (this_offset
) == INTEGER_CST
)
940 this_offset
= size_binop (MULT_EXPR
,
941 fold_convert (bitsizetype
,
944 bit_offset
= size_binop (PLUS_EXPR
,
945 bit_offset
, this_offset
);
946 bit_offset
= size_binop (PLUS_EXPR
, bit_offset
,
947 DECL_FIELD_BIT_OFFSET (field
));
951 tree csize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
952 /* We need to adjust maxsize to the whole structure bitsize.
953 But we can subtract any constant offset seen sofar,
954 because that would get us out of the structure otherwise. */
956 && csize
&& host_integerp (csize
, 1))
958 maxsize
= (TREE_INT_CST_LOW (csize
)
959 - TREE_INT_CST_LOW (bit_offset
));
968 case ARRAY_RANGE_REF
:
970 tree index
= TREE_OPERAND (exp
, 1);
971 tree low_bound
= array_ref_low_bound (exp
);
972 tree unit_size
= array_ref_element_size (exp
);
974 if (! integer_zerop (low_bound
))
975 index
= fold_build2 (MINUS_EXPR
, TREE_TYPE (index
),
977 index
= size_binop (MULT_EXPR
,
978 fold_convert (sizetype
, index
), unit_size
);
979 if (TREE_CODE (index
) == INTEGER_CST
)
981 index
= size_binop (MULT_EXPR
,
982 fold_convert (bitsizetype
, index
),
984 bit_offset
= size_binop (PLUS_EXPR
, bit_offset
, index
);
986 /* An array ref with a constant index up in the structure
987 hierarchy will constrain the size of any variable array ref
988 lower in the access hierarchy. */
989 seen_variable_array_ref
= false;
993 tree asize
= TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp
, 0)));
994 /* We need to adjust maxsize to the whole array bitsize.
995 But we can subtract any constant offset seen sofar,
996 because that would get us outside of the array otherwise. */
998 && asize
&& host_integerp (asize
, 1))
1000 maxsize
= (TREE_INT_CST_LOW (asize
)
1001 - TREE_INT_CST_LOW (bit_offset
));
1006 /* Remember that we have seen an array ref with a variable
1008 seen_variable_array_ref
= true;
1017 bit_offset
= size_binop (PLUS_EXPR
, bit_offset
,
1018 bitsize_int (bitsize
));
1021 case VIEW_CONVERT_EXPR
:
1022 /* ??? We probably should give up here and bail out. */
1029 exp
= TREE_OPERAND (exp
, 0);
1033 /* We need to deal with variable arrays ending structures such as
1034 struct { int length; int a[1]; } x; x.a[d]
1035 struct { struct { int a; int b; } a[1]; } x; x.a[d].a
1036 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
1037 where we do not know maxsize for variable index accesses to
1038 the array. The simplest way to conservatively deal with this
1039 is to punt in the case that offset + maxsize reaches the
1040 base type boundary. */
1041 if (seen_variable_array_ref
1043 && host_integerp (TYPE_SIZE (TREE_TYPE (exp
)), 1)
1044 && TREE_INT_CST_LOW (bit_offset
) + maxsize
1045 == TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp
))))
1048 /* ??? Due to negative offsets in ARRAY_REF we can end up with
1049 negative bit_offset here. We might want to store a zero offset
1051 *poffset
= TREE_INT_CST_LOW (bit_offset
);
1053 *pmax_size
= maxsize
;