1 /* Data flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004 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, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA. */
24 #include "coretypes.h"
30 #include "hard-reg-set.h"
31 #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-alias-common.h"
46 #include "tree-pass.h"
50 /* Build and maintain data flow information for trees. */
52 /* Counters used to display DFA and SSA statistics. */
68 /* State information for find_vars_r. */
71 /* Hash table used to avoid adding the same variable more than once. */
76 /* Local functions. */
77 static void collect_dfa_stats (struct dfa_stats_d
*);
78 static tree
collect_dfa_stats_r (tree
*, int *, void *);
79 static void add_immediate_use (tree
, tree
);
80 static tree
find_vars_r (tree
*, int *, void *);
81 static void add_referenced_var (tree
, struct walk_state
*);
82 static void compute_immediate_uses_for_phi (tree
, bool (*)(tree
));
83 static void compute_immediate_uses_for_stmt (tree
, int, bool (*)(tree
));
84 static void find_hidden_use_vars (tree
);
85 static tree
find_hidden_use_vars_r (tree
*, int *, void *);
88 /* Global declarations. */
90 /* Array of all variables referenced in the function. */
91 varray_type referenced_vars
;
94 /*---------------------------------------------------------------------------
95 Dataflow analysis (DFA) routines
96 ---------------------------------------------------------------------------*/
97 /* Find all the variables referenced in the function. This function
98 builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
100 Note that this function does not look for statement operands, it simply
101 determines what variables are referenced in the program and detects
102 various attributes for each variable used by alias analysis and the
106 find_referenced_vars (void)
110 block_stmt_iterator si
;
111 struct walk_state walk_state
;
114 /* Walk the lexical blocks in the function looking for variables that may
115 have been used to declare VLAs and for nested functions. Both
116 constructs create hidden uses of variables.
118 Note that at this point we may have multiple blocks hung off
119 DECL_INITIAL chained through the BLOCK_CHAIN field due to
120 how inlining works. Egad. */
121 block
= DECL_INITIAL (current_function_decl
);
124 find_hidden_use_vars (block
);
125 block
= BLOCK_CHAIN (block
);
128 vars_found
= htab_create (50, htab_hash_pointer
, htab_eq_pointer
, NULL
);
129 memset (&walk_state
, 0, sizeof (walk_state
));
130 walk_state
.vars_found
= vars_found
;
133 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
135 tree
*stmt_p
= bsi_stmt_ptr (si
);
136 walk_tree (stmt_p
, find_vars_r
, &walk_state
, NULL
);
139 htab_delete (vars_found
);
142 struct tree_opt_pass pass_referenced_vars
=
146 find_referenced_vars
, /* execute */
149 0, /* static_pass_number */
151 PROP_gimple_leh
| PROP_cfg
, /* properties_required */
152 PROP_referenced_vars
, /* properties_provided */
153 0, /* properties_destroyed */
154 0, /* todo_flags_start */
155 0, /* todo_flags_finish */
159 /* Compute immediate uses.
161 CALC_FOR is an optional function pointer which indicates whether
162 immediate uses information should be calculated for a given SSA
163 variable. If NULL, then information is computed for all
166 FLAGS is one of {TDFA_USE_OPS, TDFA_USE_VOPS}. It is used by
167 compute_immediate_uses_for_stmt to determine whether to look at
168 virtual and/or real operands while computing def-use chains. */
171 compute_immediate_uses (int flags
, bool (*calc_for
)(tree
))
174 block_stmt_iterator si
;
180 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
181 compute_immediate_uses_for_phi (phi
, calc_for
);
183 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
185 tree stmt
= bsi_stmt (si
);
186 get_stmt_operands (stmt
);
187 compute_immediate_uses_for_stmt (stmt
, flags
, calc_for
);
193 /* Invalidates dataflow information for a statement STMT. */
196 free_df_for_stmt (tree stmt
)
198 stmt_ann_t ann
= stmt_ann (stmt
);
202 /* If we have a varray of immediate uses, then go ahead and release
204 if (ann
->df
->immediate_uses
)
205 ggc_free (ann
->df
->immediate_uses
);
207 /* Similarly for the main dataflow structure. */
214 /* Invalidate dataflow information for the whole function. */
220 block_stmt_iterator si
;
226 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
227 free_df_for_stmt (phi
);
229 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
231 tree stmt
= bsi_stmt (si
);
232 free_df_for_stmt (stmt
);
238 /* Helper for compute_immediate_uses. Check all the USE and/or VUSE
239 operands in phi node PHI and add a def-use edge between their
240 defining statement and PHI. CALC_FOR is as in
241 compute_immediate_uses.
243 PHI nodes are easy, we only need to look at their arguments. */
246 compute_immediate_uses_for_phi (tree phi
, bool (*calc_for
)(tree
))
250 #ifdef ENABLE_CHECKING
251 if (TREE_CODE (phi
) != PHI_NODE
)
255 for (i
= 0; i
< PHI_NUM_ARGS (phi
); i
++)
257 tree arg
= PHI_ARG_DEF (phi
, i
);
259 if (TREE_CODE (arg
) == SSA_NAME
&& (!calc_for
|| calc_for (arg
)))
261 tree imm_rdef_stmt
= SSA_NAME_DEF_STMT (PHI_ARG_DEF (phi
, i
));
262 if (!IS_EMPTY_STMT (imm_rdef_stmt
))
263 add_immediate_use (imm_rdef_stmt
, phi
);
269 /* Another helper for compute_immediate_uses. Depending on the value
270 of FLAGS, check all the USE and/or VUSE operands in STMT and add a
271 def-use edge between their defining statement and STMT. CALC_FOR
272 is as in compute_immediate_uses. */
275 compute_immediate_uses_for_stmt (tree stmt
, int flags
, bool (*calc_for
)(tree
))
280 v_may_def_optype v_may_defs
;
283 #ifdef ENABLE_CHECKING
284 /* PHI nodes are handled elsewhere. */
285 if (TREE_CODE (stmt
) == PHI_NODE
)
289 /* Look at USE_OPS or VUSE_OPS according to FLAGS. */
290 ann
= stmt_ann (stmt
);
291 if (flags
& TDFA_USE_OPS
)
293 uses
= USE_OPS (ann
);
294 for (i
= 0; i
< NUM_USES (uses
); i
++)
296 tree use
= USE_OP (uses
, i
);
297 tree imm_stmt
= SSA_NAME_DEF_STMT (use
);
298 if (!IS_EMPTY_STMT (imm_stmt
) && (!calc_for
|| calc_for (use
)))
299 add_immediate_use (imm_stmt
, stmt
);
303 if (flags
& TDFA_USE_VOPS
)
305 vuses
= VUSE_OPS (ann
);
306 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
308 tree vuse
= VUSE_OP (vuses
, i
);
309 tree imm_rdef_stmt
= SSA_NAME_DEF_STMT (vuse
);
310 if (!IS_EMPTY_STMT (imm_rdef_stmt
) && (!calc_for
|| calc_for (vuse
)))
311 add_immediate_use (imm_rdef_stmt
, stmt
);
314 v_may_defs
= V_MAY_DEF_OPS (ann
);
315 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
317 tree vuse
= V_MAY_DEF_OP (v_may_defs
, i
);
318 tree imm_rdef_stmt
= SSA_NAME_DEF_STMT (vuse
);
319 if (!IS_EMPTY_STMT (imm_rdef_stmt
) && (!calc_for
|| calc_for (vuse
)))
320 add_immediate_use (imm_rdef_stmt
, stmt
);
326 /* Add statement USE_STMT to the list of statements that use definitions
330 add_immediate_use (tree stmt
, tree use_stmt
)
332 stmt_ann_t ann
= get_stmt_ann (stmt
);
333 struct dataflow_d
*df
;
338 df
= ann
->df
= ggc_alloc (sizeof (struct dataflow_d
));
339 memset ((void *) df
, 0, sizeof (struct dataflow_d
));
340 df
->uses
[0] = use_stmt
;
346 df
->uses
[1] = use_stmt
;
350 if (ann
->df
->immediate_uses
== NULL
)
351 VARRAY_TREE_INIT (ann
->df
->immediate_uses
, 4, "immediate_uses");
353 VARRAY_PUSH_TREE (ann
->df
->immediate_uses
, use_stmt
);
357 /* If the immediate use of USE points to OLD, then redirect it to NEW. */
360 redirect_immediate_use (tree use
, tree old
, tree
new)
362 tree imm_stmt
= SSA_NAME_DEF_STMT (use
);
363 struct dataflow_d
*df
= get_stmt_ann (imm_stmt
)->df
;
364 unsigned int num_uses
= num_immediate_uses (df
);
367 for (i
= 0; i
< num_uses
; i
++)
369 if (immediate_use (df
, i
) == old
)
371 if (i
== 0 || i
== 1)
374 VARRAY_TREE (df
->immediate_uses
, i
- 2) = new;
380 /* Redirect all immediate uses for operands in OLD so that they point
381 to NEW. This routine should have no knowledge of how immediate
385 redirect_immediate_uses (tree old
, tree
new)
387 stmt_ann_t ann
= get_stmt_ann (old
);
388 use_optype uses
= USE_OPS (ann
);
389 vuse_optype vuses
= VUSE_OPS (ann
);
390 v_may_def_optype v_may_defs
= V_MAY_DEF_OPS (ann
);
393 /* Look at USE_OPS or VUSE_OPS according to FLAGS. */
394 for (i
= 0; i
< NUM_USES (uses
); i
++)
395 redirect_immediate_use (USE_OP (uses
, i
), old
, new);
397 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
398 redirect_immediate_use (VUSE_OP (vuses
, i
), old
, new);
400 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
401 redirect_immediate_use (V_MAY_DEF_OP (v_may_defs
, i
), old
, new);
405 /*---------------------------------------------------------------------------
407 ---------------------------------------------------------------------------*/
408 /* Create a new annotation for a _DECL node T. */
411 create_var_ann (tree t
)
415 #if defined ENABLE_CHECKING
419 && t
->common
.ann
->common
.type
!= VAR_ANN
))
423 ann
= ggc_alloc (sizeof (*ann
));
424 memset ((void *) ann
, 0, sizeof (*ann
));
426 ann
->common
.type
= VAR_ANN
;
428 t
->common
.ann
= (tree_ann_t
) ann
;
434 /* Create a new annotation for a statement node T. */
437 create_stmt_ann (tree t
)
441 #if defined ENABLE_CHECKING
442 if ((!is_gimple_stmt (t
))
444 && t
->common
.ann
->common
.type
!= STMT_ANN
))
448 ann
= ggc_alloc (sizeof (*ann
));
449 memset ((void *) ann
, 0, sizeof (*ann
));
451 ann
->common
.type
= STMT_ANN
;
453 /* Since we just created the annotation, mark the statement modified. */
454 ann
->modified
= true;
456 t
->common
.ann
= (tree_ann_t
) ann
;
462 /* Create a new annotation for a tree T. */
465 create_tree_ann (tree t
)
469 #if defined ENABLE_CHECKING
472 && t
->common
.ann
->common
.type
!= TREE_ANN_COMMON
))
476 ann
= ggc_alloc (sizeof (*ann
));
477 memset ((void *) ann
, 0, sizeof (*ann
));
479 ann
->common
.type
= TREE_ANN_COMMON
;
485 /* Build a temporary. Make sure and register it to be renamed. */
488 make_rename_temp (tree type
, const char *prefix
)
490 tree t
= create_tmp_var (type
, prefix
);
491 add_referenced_tmp_var (t
);
492 bitmap_set_bit (vars_to_rename
, var_ann (t
)->uid
);
498 /*---------------------------------------------------------------------------
500 ---------------------------------------------------------------------------*/
501 /* Dump the list of all the referenced variables in the current function to
505 dump_referenced_vars (FILE *file
)
509 fprintf (file
, "\nReferenced variables in %s: %u\n\n",
510 get_name (current_function_decl
), (unsigned) num_referenced_vars
);
512 for (i
= 0; i
< num_referenced_vars
; i
++)
514 tree var
= referenced_var (i
);
515 fprintf (file
, "Variable: ");
516 dump_variable (file
, var
);
517 fprintf (file
, "\n");
522 /* Dump the list of all the referenced variables to stderr. */
525 debug_referenced_vars (void)
527 dump_referenced_vars (stderr
);
531 /* Dump variable VAR and its may-aliases to FILE. */
534 dump_variable (FILE *file
, tree var
)
538 if (var
== NULL_TREE
)
540 fprintf (file
, "<nil>");
544 print_generic_expr (file
, var
, dump_flags
);
546 if (TREE_CODE (var
) == SSA_NAME
)
547 var
= SSA_NAME_VAR (var
);
551 fprintf (file
, ", UID %u", (unsigned) ann
->uid
);
553 if (ann
->has_hidden_use
)
554 fprintf (file
, ", has hidden uses");
556 if (ann
->type_mem_tag
)
558 fprintf (file
, ", type memory tag: ");
559 print_generic_expr (file
, ann
->type_mem_tag
, dump_flags
);
562 if (ann
->is_alias_tag
)
563 fprintf (file
, ", is an alias tag");
565 if (needs_to_live_in_memory (var
))
566 fprintf (file
, ", is %s", TREE_STATIC (var
) ? "static" : "global");
568 if (is_call_clobbered (var
))
569 fprintf (file
, ", call clobbered");
571 if (ann
->default_def
)
573 fprintf (file
, ", default def: ");
574 print_generic_expr (file
, ann
->default_def
, dump_flags
);
577 if (ann
->may_aliases
)
579 fprintf (file
, ", may aliases: ");
580 dump_may_aliases_for (file
, var
);
583 fprintf (file
, "\n");
587 /* Dump variable VAR and its may-aliases to stderr. */
590 debug_variable (tree var
)
592 dump_variable (stderr
, var
);
596 /* Dump def-use edges on FILE. */
599 dump_immediate_uses (FILE *file
)
602 block_stmt_iterator si
;
604 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
606 fprintf (file
, "\nDef-use edges for function %s\n", funcname
);
612 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
613 dump_immediate_uses_for (file
, phi
);
615 for (si
= bsi_start (bb
); !bsi_end_p (si
); bsi_next (&si
))
616 dump_immediate_uses_for (file
, bsi_stmt (si
));
619 fprintf (file
, "\n");
623 /* Dump def-use edges on stderr. */
626 debug_immediate_uses (void)
628 dump_immediate_uses (stderr
);
632 /* Dump all immediate uses for STMT on FILE. */
635 dump_immediate_uses_for (FILE *file
, tree stmt
)
637 dataflow_t df
= get_immediate_uses (stmt
);
638 int num_imm_uses
= num_immediate_uses (df
);
640 if (num_imm_uses
> 0)
644 fprintf (file
, "-> ");
645 print_generic_stmt (file
, stmt
, TDF_SLIM
);
646 fprintf (file
, "\n");
648 for (i
= 0; i
< num_imm_uses
; i
++)
650 fprintf (file
, "\t");
651 print_generic_stmt (file
, immediate_use (df
, i
), TDF_SLIM
);
652 fprintf (file
, "\n");
655 fprintf (file
, "\n");
660 /* Dump immediate uses for STMT on stderr. */
663 debug_immediate_uses_for (tree stmt
)
665 dump_immediate_uses_for (stderr
, stmt
);
669 /* Dump various DFA statistics to FILE. */
672 dump_dfa_stats (FILE *file
)
674 struct dfa_stats_d dfa_stats
;
676 unsigned long size
, total
= 0;
677 const char * const fmt_str
= "%-30s%-13s%12s\n";
678 const char * const fmt_str_1
= "%-30s%13lu%11lu%c\n";
679 const char * const fmt_str_3
= "%-43s%11lu%c\n";
681 = lang_hooks
.decl_printable_name (current_function_decl
, 2);
683 collect_dfa_stats (&dfa_stats
);
685 fprintf (file
, "\nDFA Statistics for %s\n\n", funcname
);
687 fprintf (file
, "---------------------------------------------------------\n");
688 fprintf (file
, fmt_str
, "", " Number of ", "Memory");
689 fprintf (file
, fmt_str
, "", " instances ", "used ");
690 fprintf (file
, "---------------------------------------------------------\n");
692 size
= num_referenced_vars
* sizeof (tree
);
694 fprintf (file
, fmt_str_1
, "Referenced variables", num_referenced_vars
,
695 SCALE (size
), LABEL (size
));
697 size
= dfa_stats
.num_stmt_anns
* sizeof (struct stmt_ann_d
);
699 fprintf (file
, fmt_str_1
, "Statements annotated", dfa_stats
.num_stmt_anns
,
700 SCALE (size
), LABEL (size
));
702 size
= dfa_stats
.num_var_anns
* sizeof (struct var_ann_d
);
704 fprintf (file
, fmt_str_1
, "Variables annotated", dfa_stats
.num_var_anns
,
705 SCALE (size
), LABEL (size
));
707 size
= dfa_stats
.num_uses
* sizeof (tree
*);
709 fprintf (file
, fmt_str_1
, "USE operands", dfa_stats
.num_uses
,
710 SCALE (size
), LABEL (size
));
712 size
= dfa_stats
.num_defs
* sizeof (tree
*);
714 fprintf (file
, fmt_str_1
, "DEF operands", dfa_stats
.num_defs
,
715 SCALE (size
), LABEL (size
));
717 size
= dfa_stats
.num_vuses
* sizeof (tree
*);
719 fprintf (file
, fmt_str_1
, "VUSE operands", dfa_stats
.num_vuses
,
720 SCALE (size
), LABEL (size
));
722 size
= dfa_stats
.num_v_may_defs
* sizeof (tree
*);
724 fprintf (file
, fmt_str_1
, "V_MAY_DEF operands", dfa_stats
.num_v_may_defs
,
725 SCALE (size
), LABEL (size
));
727 size
= dfa_stats
.num_v_must_defs
* sizeof (tree
*);
729 fprintf (file
, fmt_str_1
, "V_MUST_DEF operands", dfa_stats
.num_v_must_defs
,
730 SCALE (size
), LABEL (size
));
732 size
= dfa_stats
.num_phis
* sizeof (struct tree_phi_node
);
734 fprintf (file
, fmt_str_1
, "PHI nodes", dfa_stats
.num_phis
,
735 SCALE (size
), LABEL (size
));
737 size
= dfa_stats
.num_phi_args
* sizeof (struct phi_arg_d
);
739 fprintf (file
, fmt_str_1
, "PHI arguments", dfa_stats
.num_phi_args
,
740 SCALE (size
), LABEL (size
));
742 fprintf (file
, "---------------------------------------------------------\n");
743 fprintf (file
, fmt_str_3
, "Total memory used by DFA/SSA data", SCALE (total
),
745 fprintf (file
, "---------------------------------------------------------\n");
746 fprintf (file
, "\n");
748 if (dfa_stats
.num_phis
)
749 fprintf (file
, "Average number of arguments per PHI node: %.1f (max: %d)\n",
750 (float) dfa_stats
.num_phi_args
/ (float) dfa_stats
.num_phis
,
751 dfa_stats
.max_num_phi_args
);
753 fprintf (file
, "\n");
757 /* Dump DFA statistics on stderr. */
760 debug_dfa_stats (void)
762 dump_dfa_stats (stderr
);
766 /* Collect DFA statistics and store them in the structure pointed by
770 collect_dfa_stats (struct dfa_stats_d
*dfa_stats_p
)
774 block_stmt_iterator i
;
776 if (dfa_stats_p
== NULL
)
779 memset ((void *)dfa_stats_p
, 0, sizeof (struct dfa_stats_d
));
781 /* Walk all the trees in the function counting references. Start at
782 basic block 0, but don't stop at block boundaries. */
783 htab
= htab_create (30, htab_hash_pointer
, htab_eq_pointer
, NULL
);
785 for (i
= bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i
); bsi_next (&i
))
786 walk_tree (bsi_stmt_ptr (i
), collect_dfa_stats_r
, (void *) dfa_stats_p
,
794 for (phi
= phi_nodes (bb
); phi
; phi
= PHI_CHAIN (phi
))
796 dfa_stats_p
->num_phis
++;
797 dfa_stats_p
->num_phi_args
+= PHI_NUM_ARGS (phi
);
798 if (PHI_NUM_ARGS (phi
) > dfa_stats_p
->max_num_phi_args
)
799 dfa_stats_p
->max_num_phi_args
= PHI_NUM_ARGS (phi
);
805 /* Callback for walk_tree to collect DFA statistics for a tree and its
809 collect_dfa_stats_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
813 struct dfa_stats_d
*dfa_stats_p
= (struct dfa_stats_d
*)data
;
817 switch (ann_type (t
->common
.ann
))
821 stmt_ann_t ann
= (stmt_ann_t
) t
->common
.ann
;
822 dfa_stats_p
->num_stmt_anns
++;
823 dfa_stats_p
->num_defs
+= NUM_DEFS (DEF_OPS (ann
));
824 dfa_stats_p
->num_uses
+= NUM_USES (USE_OPS (ann
));
825 dfa_stats_p
->num_v_may_defs
+=
826 NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann
));
827 dfa_stats_p
->num_vuses
+= NUM_VUSES (VUSE_OPS (ann
));
828 dfa_stats_p
->num_v_must_defs
+=
829 NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann
));
834 dfa_stats_p
->num_var_anns
++;
846 /*---------------------------------------------------------------------------
847 Miscellaneous helpers
848 ---------------------------------------------------------------------------*/
849 /* Callback for walk_tree. Used to collect variables referenced in
853 find_vars_r (tree
*tp
, int *walk_subtrees
, void *data
)
855 struct walk_state
*walk_state
= (struct walk_state
*) data
;
857 /* If T is a regular variable that the optimizers are interested
858 in, add it to the list of variables. */
860 add_referenced_var (*tp
, walk_state
);
862 /* Type, _DECL and constant nodes have no interesting children.
864 else if (DECL_P (*tp
)
866 || TREE_CODE_CLASS (TREE_CODE (*tp
)) == 'c')
873 /* Add VAR to the list of dereferenced variables.
875 WALK_STATE contains a hash table used to avoid adding the same
876 variable more than once. Note that this function assumes that
877 VAR is a valid SSA variable. If WALK_STATE is NULL, no
878 duplicate checking is done. */
881 add_referenced_var (tree var
, struct walk_state
*walk_state
)
886 v_ann
= get_var_ann (var
);
889 slot
= htab_find_slot (walk_state
->vars_found
, (void *) var
, INSERT
);
893 if (slot
== NULL
|| *slot
== NULL
)
895 /* This is the first time we find this variable, add it to the
896 REFERENCED_VARS array and annotate it with attributes that are
897 intrinsic to the variable. */
899 *slot
= (void *) var
;
900 v_ann
->uid
= num_referenced_vars
;
901 VARRAY_PUSH_TREE (referenced_vars
, var
);
903 /* Global and static variables are call-clobbered, always. */
904 if (needs_to_live_in_memory (var
))
905 mark_call_clobbered (var
);
907 /* DECL_NONLOCAL variables should not be removed, as they are needed
908 to emit nested functions. */
909 if (DECL_NONLOCAL (var
))
915 /* Return the virtual variable associated to the non-scalar variable VAR. */
918 get_virtual_var (tree var
)
922 if (TREE_CODE (var
) == SSA_NAME
)
923 var
= SSA_NAME_VAR (var
);
925 while (TREE_CODE (var
) == REALPART_EXPR
|| TREE_CODE (var
) == IMAGPART_EXPR
926 || handled_component_p (var
))
927 var
= TREE_OPERAND (var
, 0);
929 #ifdef ENABLE_CHECKING
930 /* Treating GIMPLE registers as virtual variables makes no sense.
931 Also complain if we couldn't extract a _DECL out of the original
934 || is_gimple_reg (var
))
942 /* Mark variables in BLOCK that have hidden uses. A hidden use can
943 occur due to VLA declarations or nested functions. */
946 find_hidden_use_vars (tree block
)
950 /* Check all the arrays declared in the block for VLAs.
951 While scanning the block's variables, also see if there is
952 a nested function at this scope. */
953 for (decl
= BLOCK_VARS (block
); decl
; decl
= TREE_CHAIN (decl
))
956 walk_tree (&decl
, find_hidden_use_vars_r
, &inside_vla
, NULL
);
959 /* Now repeat the search in any sub-blocks. */
960 for (sub
= BLOCK_SUBBLOCKS (block
); sub
; sub
= TREE_CHAIN (sub
))
961 find_hidden_use_vars (sub
);
963 /* A VLA parameter may use a variable which as set from another
964 parameter to declare the size of the VLA. We need to mark the
965 variable as having a hidden use since it is used to declare the
966 VLA parameter and that declaration is not seen by the SSA code.
968 Note get_pending_sizes clears the PENDING_SIZES chain, so we
970 tem
= get_pending_sizes ();
971 put_pending_sizes (tem
);
972 for (; tem
; tem
= TREE_CHAIN (tem
))
975 walk_tree (&TREE_VALUE (tem
), find_hidden_use_vars_r
, &inside_vla
, NULL
);
980 /* Callback for walk_tree used by find_hidden_use_vars to analyze each
981 variable in a lexical block. If the variable's size has a variable
982 size, then mark all objects needed to compute the variable's size
983 as having hidden uses. */
986 find_hidden_use_vars_r (tree
*tp
, int *walk_subtrees ATTRIBUTE_UNUSED
,
987 void *data ATTRIBUTE_UNUSED
)
989 int *inside_vla
= (int *) data
;
991 /* We need to look for hidden uses due to VLAs in variable
992 definitions. We originally used to look for these hidden
993 uses in the variable's type, but that's unreliable if the
994 type's size contains a SAVE_EXPR for a different function
995 context than the variable is used within. */
998 && ! really_constant_p (DECL_SIZE (*tp
)))
999 || (DECL_SIZE_UNIT (*tp
)
1000 && ! really_constant_p (DECL_SIZE_UNIT (*tp
)))))
1002 int save
= *inside_vla
;
1005 walk_tree (&DECL_SIZE (*tp
), find_hidden_use_vars_r
, inside_vla
, NULL
);
1006 walk_tree (&DECL_SIZE_UNIT (*tp
), find_hidden_use_vars_r
,
1010 else if (*inside_vla
&& SSA_VAR_P (*tp
))
1011 set_has_hidden_use (*tp
);
1017 /* Add a temporary variable to REFERENCED_VARS. This is similar to
1018 add_referenced_var, but is used by passes that need to add new temps to
1019 the REFERENCED_VARS array after the program has been scanned for
1020 variables. The variable will just receive a new UID and be added
1021 to the REFERENCED_VARS array without checking for duplicates. */
1024 add_referenced_tmp_var (tree var
)
1026 add_referenced_var (var
, NULL
);
1029 /* Return true if V_MAY_DEFS_AFTER contains fewer entries than
1030 V_MAY_DEFS_BEFORE. Note that this assumes that both varrays
1031 are V_MAY_DEF operands for the same statement. */
1034 v_may_defs_disappeared_p (v_may_def_optype v_may_defs_before
,
1035 v_may_def_optype v_may_defs_after
)
1037 /* If there was nothing before, nothing could've disappeared. */
1038 if (v_may_defs_before
== NULL
)
1041 /* All/some of them gone. */
1042 if (v_may_defs_after
== NULL
1043 || NUM_V_MAY_DEFS (v_may_defs_before
) >
1044 NUM_V_MAY_DEFS (v_may_defs_after
))
1050 /* Return true if V_MUST_DEFS_AFTER contains fewer entries than
1051 V_MUST_DEFS_BEFORE. Note that this assumes that both varrays
1052 are V_MUST_DEF operands for the same statement. */
1055 v_must_defs_disappeared_p (v_must_def_optype v_must_defs_before
,
1056 v_must_def_optype v_must_defs_after
)
1058 /* If there was nothing before, nothing could've disappeared. */
1059 if (v_must_defs_before
== NULL
)
1062 /* All/some of them gone. */
1063 if (v_must_defs_after
== NULL
1064 || NUM_V_MUST_DEFS (v_must_defs_before
) >
1065 NUM_V_MUST_DEFS (v_must_defs_after
))
1072 /* Add all the non-SSA variables found in STMT's operands to the bitmap
1076 mark_new_vars_to_rename (tree stmt
, bitmap vars_to_rename
)
1080 v_may_def_optype v_may_defs
;
1082 v_must_def_optype v_must_defs
;
1084 bitmap vars_in_vops_to_rename
;
1085 bool found_exposed_symbol
= false;
1086 v_may_def_optype v_may_defs_before
, v_may_defs_after
;
1087 v_must_def_optype v_must_defs_before
, v_must_defs_after
;
1090 vars_in_vops_to_rename
= BITMAP_XMALLOC ();
1092 /* Before re-scanning the statement for operands, mark the existing
1093 virtual operands to be renamed again. We do this because when new
1094 symbols are exposed, the virtual operands that were here before due to
1095 aliasing will probably be removed by the call to get_stmt_operand.
1096 Therefore, we need to flag them to be renamed beforehand.
1098 We flag them in a separate bitmap because we don't really want to
1099 rename them if there are not any newly exposed symbols in the
1100 statement operands. */
1101 ann
= stmt_ann (stmt
);
1102 v_may_defs_before
= v_may_defs
= V_MAY_DEF_OPS (ann
);
1103 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
1105 tree var
= V_MAY_DEF_RESULT (v_may_defs
, i
);
1107 var
= SSA_NAME_VAR (var
);
1108 bitmap_set_bit (vars_in_vops_to_rename
, var_ann (var
)->uid
);
1111 vuses
= VUSE_OPS (ann
);
1112 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
1114 tree var
= VUSE_OP (vuses
, i
);
1116 var
= SSA_NAME_VAR (var
);
1117 bitmap_set_bit (vars_in_vops_to_rename
, var_ann (var
)->uid
);
1120 v_must_defs_before
= v_must_defs
= V_MUST_DEF_OPS (ann
);
1121 for (i
= 0; i
< NUM_V_MUST_DEFS (v_must_defs
); i
++)
1123 tree var
= V_MUST_DEF_OP (v_must_defs
, i
);
1125 var
= SSA_NAME_VAR (var
);
1126 bitmap_set_bit (vars_in_vops_to_rename
, var_ann (var
)->uid
);
1129 /* Now force an operand re-scan on the statement and mark any newly
1130 exposed variables. */
1132 get_stmt_operands (stmt
);
1134 defs
= DEF_OPS (ann
);
1135 for (i
= 0; i
< NUM_DEFS (defs
); i
++)
1137 tree var
= DEF_OP (defs
, i
);
1140 found_exposed_symbol
= true;
1141 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1145 uses
= USE_OPS (ann
);
1146 for (i
= 0; i
< NUM_USES (uses
); i
++)
1148 tree var
= USE_OP (uses
, i
);
1151 found_exposed_symbol
= true;
1152 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1156 v_may_defs_after
= v_may_defs
= V_MAY_DEF_OPS (ann
);
1157 for (i
= 0; i
< NUM_V_MAY_DEFS (v_may_defs
); i
++)
1159 tree var
= V_MAY_DEF_RESULT (v_may_defs
, i
);
1162 found_exposed_symbol
= true;
1163 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1167 vuses
= VUSE_OPS (ann
);
1168 for (i
= 0; i
< NUM_VUSES (vuses
); i
++)
1170 tree var
= VUSE_OP (vuses
, i
);
1173 found_exposed_symbol
= true;
1174 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1178 v_must_defs_after
= v_must_defs
= V_MUST_DEF_OPS (ann
);
1179 for (i
= 0; i
< NUM_V_MUST_DEFS (v_must_defs
); i
++)
1181 tree var
= V_MUST_DEF_OP (v_must_defs
, i
);
1184 found_exposed_symbol
= true;
1185 bitmap_set_bit (vars_to_rename
, var_ann (var
)->uid
);
1189 /* If we found any newly exposed symbols, or if there are fewer VDEF
1190 operands in the statement, add the variables we had set in
1191 VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME. We need to check for
1192 vanishing VDEFs because in those cases, the names that were formerly
1193 generated by this statement are not going to be available anymore. */
1194 if (found_exposed_symbol
1195 || v_may_defs_disappeared_p (v_may_defs_before
, v_may_defs_after
)
1196 || v_must_defs_disappeared_p (v_must_defs_before
, v_must_defs_after
))
1197 bitmap_a_or_b (vars_to_rename
, vars_to_rename
, vars_in_vops_to_rename
);
1199 BITMAP_XFREE (vars_in_vops_to_rename
);