libfuncs.h (LTI_synchronize): New libfunc_index.
[official-gcc.git] / gcc / tree-dfa.c
bloba1780399cc6c5fc6002396dc845e3b63a9970865
1 /* Data flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008 Free Software
3 Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
11 any later version.
13 GCC is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "hashtab.h"
27 #include "pointer-set.h"
28 #include "tree.h"
29 #include "rtl.h"
30 #include "tm_p.h"
31 #include "hard-reg-set.h"
32 #include "basic-block.h"
33 #include "output.h"
34 #include "timevar.h"
35 #include "expr.h"
36 #include "ggc.h"
37 #include "langhooks.h"
38 #include "flags.h"
39 #include "function.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"
46 #include "convert.h"
47 #include "params.h"
48 #include "cgraph.h"
50 /* Build and maintain data flow information for trees. */
52 /* Counters used to display DFA and SSA statistics. */
53 struct dfa_stats_d
55 long num_stmt_anns;
56 long num_var_anns;
57 long num_defs;
58 long num_uses;
59 long num_phis;
60 long num_phi_args;
61 int max_num_phi_args;
62 long num_vdefs;
63 long num_vuses;
67 /* Local functions. */
68 static void collect_dfa_stats (struct dfa_stats_d *);
69 static tree collect_dfa_stats_r (tree *, int *, void *);
70 static tree find_vars_r (tree *, int *, void *);
73 /*---------------------------------------------------------------------------
74 Dataflow analysis (DFA) routines
75 ---------------------------------------------------------------------------*/
76 /* Find all the variables referenced in the function. This function
77 builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
79 Note that this function does not look for statement operands, it simply
80 determines what variables are referenced in the program and detects
81 various attributes for each variable used by alias analysis and the
82 optimizer. */
84 static unsigned int
85 find_referenced_vars (void)
87 basic_block bb;
88 block_stmt_iterator si;
89 tree phi;
91 FOR_EACH_BB (bb)
93 for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
95 tree *stmt_p = bsi_stmt_ptr (si);
96 walk_tree (stmt_p, find_vars_r, NULL, NULL);
99 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
101 int len = PHI_NUM_ARGS (phi);
102 int i;
104 walk_tree (&phi, find_vars_r, NULL, NULL);
106 for (i = 0; i < len; i++)
108 tree arg = PHI_ARG_DEF (phi, i);
109 walk_tree (&arg, find_vars_r, NULL, NULL);
114 return 0;
117 struct gimple_opt_pass pass_referenced_vars =
120 GIMPLE_PASS,
121 NULL, /* name */
122 NULL, /* gate */
123 find_referenced_vars, /* execute */
124 NULL, /* sub */
125 NULL, /* next */
126 0, /* static_pass_number */
127 TV_FIND_REFERENCED_VARS, /* tv_id */
128 PROP_gimple_leh | PROP_cfg, /* properties_required */
129 PROP_referenced_vars, /* properties_provided */
130 0, /* properties_destroyed */
131 TODO_dump_func, /* todo_flags_start */
132 TODO_dump_func /* todo_flags_finish */
137 /*---------------------------------------------------------------------------
138 Manage annotations
139 ---------------------------------------------------------------------------*/
140 /* Create a new annotation for a _DECL node T. */
142 var_ann_t
143 create_var_ann (tree t)
145 var_ann_t ann;
147 gcc_assert (t);
148 gcc_assert (DECL_P (t));
149 gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
151 ann = GGC_CNEW (struct var_ann_d);
152 ann->common.type = VAR_ANN;
153 t->base.ann = (tree_ann_t) ann;
155 return ann;
158 /* Create a new annotation for a FUNCTION_DECL node T. */
160 function_ann_t
161 create_function_ann (tree t)
163 function_ann_t ann;
165 gcc_assert (t);
166 gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
167 gcc_assert (!t->base.ann || t->base.ann->common.type == FUNCTION_ANN);
169 ann = (function_ann_t) ggc_alloc (sizeof (*ann));
170 memset ((void *) ann, 0, sizeof (*ann));
172 ann->common.type = FUNCTION_ANN;
174 t->base.ann = (tree_ann_t) ann;
176 return ann;
179 /* Create a new annotation for a statement node T. */
181 stmt_ann_t
182 create_stmt_ann (tree t)
184 stmt_ann_t ann;
186 gcc_assert (is_gimple_stmt (t));
187 gcc_assert (!t->base.ann || t->base.ann->common.type == STMT_ANN);
189 ann = GGC_CNEW (struct stmt_ann_d);
191 ann->common.type = STMT_ANN;
193 /* Since we just created the annotation, mark the statement modified. */
194 ann->modified = true;
196 ann->uid = inc_gimple_stmt_max_uid (cfun);
197 t->base.ann = (tree_ann_t) ann;
199 return ann;
202 /* Renumber all of the gimple stmt uids. */
204 void
205 renumber_gimple_stmt_uids (void)
207 basic_block bb;
209 set_gimple_stmt_max_uid (cfun, 0);
210 FOR_ALL_BB (bb)
212 block_stmt_iterator bsi;
213 for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
215 tree stmt = bsi_stmt (bsi);
216 /* If the stmt has an annotation, then overwrite it, if not,
217 the process of getting it will set the number
218 properly. */
219 if (has_stmt_ann (stmt))
220 set_gimple_stmt_uid (stmt, inc_gimple_stmt_max_uid (cfun));
221 else
222 get_stmt_ann (stmt);
227 /* Create a new annotation for a tree T. */
229 tree_ann_common_t
230 create_tree_common_ann (tree t)
232 tree_ann_common_t ann;
234 gcc_assert (t);
235 gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
237 ann = GGC_CNEW (struct tree_ann_common_d);
239 ann->type = TREE_ANN_COMMON;
240 t->base.ann = (tree_ann_t) ann;
242 return ann;
245 /* Build a temporary. Make sure and register it to be renamed. */
247 tree
248 make_rename_temp (tree type, const char *prefix)
250 tree t = create_tmp_var (type, prefix);
252 if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
253 || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
254 DECL_GIMPLE_REG_P (t) = 1;
256 if (gimple_referenced_vars (cfun))
258 add_referenced_var (t);
259 mark_sym_for_renaming (t);
262 return t;
267 /*---------------------------------------------------------------------------
268 Debugging functions
269 ---------------------------------------------------------------------------*/
270 /* Dump the list of all the referenced variables in the current function to
271 FILE. */
273 void
274 dump_referenced_vars (FILE *file)
276 tree var;
277 referenced_var_iterator rvi;
279 fprintf (file, "\nReferenced variables in %s: %u\n\n",
280 get_name (current_function_decl), (unsigned) num_referenced_vars);
282 FOR_EACH_REFERENCED_VAR (var, rvi)
284 fprintf (file, "Variable: ");
285 dump_variable (file, var);
286 fprintf (file, "\n");
291 /* Dump the list of all the referenced variables to stderr. */
293 void
294 debug_referenced_vars (void)
296 dump_referenced_vars (stderr);
300 /* Dump variable VAR and its may-aliases to FILE. */
302 void
303 dump_variable (FILE *file, tree var)
305 var_ann_t ann;
307 if (TREE_CODE (var) == SSA_NAME)
309 if (POINTER_TYPE_P (TREE_TYPE (var)))
310 dump_points_to_info_for (file, var);
311 var = SSA_NAME_VAR (var);
314 if (var == NULL_TREE)
316 fprintf (file, "<nil>");
317 return;
320 print_generic_expr (file, var, dump_flags);
322 ann = var_ann (var);
324 fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
326 fprintf (file, ", ");
327 print_generic_expr (file, TREE_TYPE (var), dump_flags);
329 if (ann && ann->symbol_mem_tag)
331 fprintf (file, ", symbol memory tag: ");
332 print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
335 if (TREE_ADDRESSABLE (var))
336 fprintf (file, ", is addressable");
338 if (is_global_var (var))
339 fprintf (file, ", is global");
341 if (TREE_THIS_VOLATILE (var))
342 fprintf (file, ", is volatile");
344 dump_mem_sym_stats_for_var (file, var);
346 if (is_call_clobbered (var))
348 const char *s = "";
349 var_ann_t va = var_ann (var);
350 unsigned int escape_mask = va->escape_mask;
352 fprintf (file, ", call clobbered");
353 fprintf (file, " (");
354 if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
355 { fprintf (file, "%sstored in global", s); s = ", "; }
356 if (escape_mask & ESCAPE_TO_ASM)
357 { fprintf (file, "%sgoes through ASM", s); s = ", "; }
358 if (escape_mask & ESCAPE_TO_CALL)
359 { fprintf (file, "%spassed to call", s); s = ", "; }
360 if (escape_mask & ESCAPE_BAD_CAST)
361 { fprintf (file, "%sbad cast", s); s = ", "; }
362 if (escape_mask & ESCAPE_TO_RETURN)
363 { fprintf (file, "%sreturned from func", s); s = ", "; }
364 if (escape_mask & ESCAPE_TO_PURE_CONST)
365 { fprintf (file, "%spassed to pure/const", s); s = ", "; }
366 if (escape_mask & ESCAPE_IS_GLOBAL)
367 { fprintf (file, "%sis global var", s); s = ", "; }
368 if (escape_mask & ESCAPE_IS_PARM)
369 { fprintf (file, "%sis incoming pointer", s); s = ", "; }
370 if (escape_mask & ESCAPE_UNKNOWN)
371 { fprintf (file, "%sunknown escape", s); s = ", "; }
372 fprintf (file, ")");
375 if (ann->noalias_state == NO_ALIAS)
376 fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
377 else if (ann->noalias_state == NO_ALIAS_GLOBAL)
378 fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
379 " and global vars)");
380 else if (ann->noalias_state == NO_ALIAS_ANYTHING)
381 fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
383 if (gimple_default_def (cfun, var))
385 fprintf (file, ", default def: ");
386 print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
389 if (MTAG_P (var) && may_aliases (var))
391 fprintf (file, ", may aliases: ");
392 dump_may_aliases_for (file, var);
395 if (!is_gimple_reg (var))
397 if (memory_partition (var))
399 fprintf (file, ", belongs to partition: ");
400 print_generic_expr (file, memory_partition (var), dump_flags);
403 if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
405 fprintf (file, ", partition symbols: ");
406 dump_decl_set (file, MPT_SYMBOLS (var));
410 fprintf (file, "\n");
414 /* Dump variable VAR and its may-aliases to stderr. */
416 void
417 debug_variable (tree var)
419 dump_variable (stderr, var);
423 /* Dump various DFA statistics to FILE. */
425 void
426 dump_dfa_stats (FILE *file)
428 struct dfa_stats_d dfa_stats;
430 unsigned long size, total = 0;
431 const char * const fmt_str = "%-30s%-13s%12s\n";
432 const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
433 const char * const fmt_str_3 = "%-43s%11lu%c\n";
434 const char *funcname
435 = lang_hooks.decl_printable_name (current_function_decl, 2);
437 collect_dfa_stats (&dfa_stats);
439 fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
441 fprintf (file, "---------------------------------------------------------\n");
442 fprintf (file, fmt_str, "", " Number of ", "Memory");
443 fprintf (file, fmt_str, "", " instances ", "used ");
444 fprintf (file, "---------------------------------------------------------\n");
446 size = num_referenced_vars * sizeof (tree);
447 total += size;
448 fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
449 SCALE (size), LABEL (size));
451 size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
452 total += size;
453 fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
454 SCALE (size), LABEL (size));
456 size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
457 total += size;
458 fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
459 SCALE (size), LABEL (size));
461 size = dfa_stats.num_uses * sizeof (tree *);
462 total += size;
463 fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
464 SCALE (size), LABEL (size));
466 size = dfa_stats.num_defs * sizeof (tree *);
467 total += size;
468 fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
469 SCALE (size), LABEL (size));
471 size = dfa_stats.num_vuses * sizeof (tree *);
472 total += size;
473 fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
474 SCALE (size), LABEL (size));
476 size = dfa_stats.num_vdefs * sizeof (tree *);
477 total += size;
478 fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
479 SCALE (size), LABEL (size));
481 size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
482 total += size;
483 fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
484 SCALE (size), LABEL (size));
486 size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
487 total += size;
488 fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
489 SCALE (size), LABEL (size));
491 fprintf (file, "---------------------------------------------------------\n");
492 fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
493 LABEL (total));
494 fprintf (file, "---------------------------------------------------------\n");
495 fprintf (file, "\n");
497 if (dfa_stats.num_phis)
498 fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
499 (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
500 dfa_stats.max_num_phi_args);
502 fprintf (file, "\n");
506 /* Dump DFA statistics on stderr. */
508 void
509 debug_dfa_stats (void)
511 dump_dfa_stats (stderr);
515 /* Collect DFA statistics and store them in the structure pointed to by
516 DFA_STATS_P. */
518 static void
519 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
521 struct pointer_set_t *pset;
522 basic_block bb;
523 block_stmt_iterator i;
525 gcc_assert (dfa_stats_p);
527 memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
529 /* Walk all the trees in the function counting references. Start at
530 basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries. */
531 pset = pointer_set_create ();
533 for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
534 !bsi_end_p (i); bsi_next (&i))
535 walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
536 pset);
538 pointer_set_destroy (pset);
540 FOR_EACH_BB (bb)
542 tree phi;
543 for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
545 dfa_stats_p->num_phis++;
546 dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
547 if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
548 dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
554 /* Callback for walk_tree to collect DFA statistics for a tree and its
555 children. */
557 static tree
558 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
559 void *data)
561 tree t = *tp;
562 struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
564 if (t->base.ann)
566 switch (ann_type (t->base.ann))
568 case STMT_ANN:
570 dfa_stats_p->num_stmt_anns++;
571 dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
572 dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
573 dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (t, SSA_OP_VDEF);
574 dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
575 break;
578 case VAR_ANN:
579 dfa_stats_p->num_var_anns++;
580 break;
582 default:
583 break;
587 return NULL;
591 /*---------------------------------------------------------------------------
592 Miscellaneous helpers
593 ---------------------------------------------------------------------------*/
594 /* Callback for walk_tree. Used to collect variables referenced in
595 the function. */
597 static tree
598 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
600 /* If we are reading the lto info back in, we need to rescan the
601 referenced vars. */
602 if (TREE_CODE (*tp) == SSA_NAME)
603 add_referenced_var (SSA_NAME_VAR (*tp));
605 /* If T is a regular variable that the optimizers are interested
606 in, add it to the list of variables. */
607 else if (SSA_VAR_P (*tp))
608 add_referenced_var (*tp);
610 /* Type, _DECL and constant nodes have no interesting children.
611 Ignore them. */
612 else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
613 *walk_subtrees = 0;
615 return NULL_TREE;
618 /* Lookup UID in the referenced_vars hashtable and return the associated
619 variable. */
621 tree
622 referenced_var_lookup (unsigned int uid)
624 tree h;
625 struct tree_decl_minimal in;
626 in.uid = uid;
627 h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
628 gcc_assert (h || uid == 0);
629 return h;
632 /* Check if TO is in the referenced_vars hash table and insert it if not.
633 Return true if it required insertion. */
635 bool
636 referenced_var_check_and_insert (tree to)
638 tree h, *loc;
639 struct tree_decl_minimal in;
640 unsigned int uid = DECL_UID (to);
642 in.uid = uid;
643 h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
644 if (h)
646 /* DECL_UID has already been entered in the table. Verify that it is
647 the same entry as TO. See PR 27793. */
648 gcc_assert (h == to);
649 return false;
652 loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
653 &in, uid, INSERT);
654 *loc = to;
655 return true;
658 /* Lookup VAR UID in the default_defs hashtable and return the associated
659 variable. */
661 tree
662 gimple_default_def (struct function *fn, tree var)
664 struct tree_decl_minimal ind;
665 struct tree_ssa_name in;
666 gcc_assert (SSA_VAR_P (var));
667 in.var = (tree)&ind;
668 ind.uid = DECL_UID (var);
669 return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
672 /* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
674 void
675 set_default_def (tree var, tree def)
677 struct tree_decl_minimal ind;
678 struct tree_ssa_name in;
679 void **loc;
681 gcc_assert (SSA_VAR_P (var));
682 in.var = (tree)&ind;
683 ind.uid = DECL_UID (var);
684 if (!def)
686 loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
687 DECL_UID (var), INSERT);
688 gcc_assert (*loc);
689 htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
690 return;
692 gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
693 loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
694 DECL_UID (var), INSERT);
696 /* Default definition might be changed by tail call optimization. */
697 if (*loc)
698 SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
699 *(tree *) loc = def;
701 /* Mark DEF as the default definition for VAR. */
702 SSA_NAME_IS_DEFAULT_DEF (def) = true;
705 /* Add VAR to the list of referenced variables if it isn't already there. */
707 void
708 add_referenced_var (tree var)
710 var_ann_t v_ann;
712 v_ann = get_var_ann (var);
713 gcc_assert (DECL_P (var));
715 /* Insert VAR into the referenced_vars has table if it isn't present. */
716 if (referenced_var_check_and_insert (var))
718 /* This is the first time we found this variable, annotate it with
719 attributes that are intrinsic to the variable. */
721 /* Tag's don't have DECL_INITIAL. */
722 if (MTAG_P (var))
723 return;
725 /* Scan DECL_INITIAL for pointer variables as they may contain
726 address arithmetic referencing the address of other
727 variables.
728 Even non-constant initializers need to be walked, because
729 IPA passes might prove that their are invariant later on. */
730 if (DECL_INITIAL (var)
731 /* Initializers of external variables are not useful to the
732 optimizers. */
733 && !DECL_EXTERNAL (var))
734 walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
738 /* Remove VAR from the list. */
740 void
741 remove_referenced_var (tree var)
743 var_ann_t v_ann;
744 struct tree_decl_minimal in;
745 void **loc;
746 unsigned int uid = DECL_UID (var);
748 clear_call_clobbered (var);
749 if ((v_ann = var_ann (var)))
751 /* Preserve var_anns of globals, but clear their alias info. */
752 if (MTAG_P (var)
753 || (!TREE_STATIC (var) && !DECL_EXTERNAL (var)))
755 ggc_free (v_ann);
756 var->base.ann = NULL;
758 else
760 v_ann->mpt = NULL_TREE;
761 v_ann->symbol_mem_tag = NULL_TREE;
764 gcc_assert (DECL_P (var));
765 in.uid = uid;
766 loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
767 NO_INSERT);
768 htab_clear_slot (gimple_referenced_vars (cfun), loc);
772 /* Return the virtual variable associated to the non-scalar variable VAR. */
774 tree
775 get_virtual_var (tree var)
777 STRIP_NOPS (var);
779 if (TREE_CODE (var) == SSA_NAME)
780 var = SSA_NAME_VAR (var);
782 while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
783 || handled_component_p (var))
784 var = TREE_OPERAND (var, 0);
786 /* Treating GIMPLE registers as virtual variables makes no sense.
787 Also complain if we couldn't extract a _DECL out of the original
788 expression. */
789 gcc_assert (SSA_VAR_P (var));
790 gcc_assert (!is_gimple_reg (var));
792 return var;
795 /* Mark all the naked symbols in STMT for SSA renaming.
797 NOTE: This function should only be used for brand new statements.
798 If the caller is modifying an existing statement, it should use the
799 combination push_stmt_changes/pop_stmt_changes. */
801 void
802 mark_symbols_for_renaming (tree stmt)
804 tree op;
805 ssa_op_iter iter;
807 update_stmt (stmt);
809 /* Mark all the operands for renaming. */
810 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
811 if (DECL_P (op))
812 mark_sym_for_renaming (op);
816 /* Find all variables within the gimplified statement that were not previously
817 visible to the function and add them to the referenced variables list. */
819 static tree
820 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
821 void *data ATTRIBUTE_UNUSED)
823 tree t = *tp;
825 if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
827 add_referenced_var (t);
828 mark_sym_for_renaming (t);
831 if (IS_TYPE_OR_DECL_P (t))
832 *walk_subtrees = 0;
834 return NULL;
837 void
838 find_new_referenced_vars (tree *stmt_p)
840 walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
844 /* If EXP is a handled component reference for a structure, return the
845 base variable. The access range is delimited by bit positions *POFFSET and
846 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
847 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
848 and *PMAX_SIZE are equal, the access is non-variable. */
850 tree
851 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
852 HOST_WIDE_INT *psize,
853 HOST_WIDE_INT *pmax_size)
855 HOST_WIDE_INT bitsize = -1;
856 HOST_WIDE_INT maxsize = -1;
857 tree size_tree = NULL_TREE;
858 HOST_WIDE_INT bit_offset = 0;
859 bool seen_variable_array_ref = false;
861 gcc_assert (!SSA_VAR_P (exp));
863 /* First get the final access size from just the outermost expression. */
864 if (TREE_CODE (exp) == COMPONENT_REF)
865 size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
866 else if (TREE_CODE (exp) == BIT_FIELD_REF)
867 size_tree = TREE_OPERAND (exp, 1);
868 else
870 enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
871 if (mode == BLKmode)
872 size_tree = TYPE_SIZE (TREE_TYPE (exp));
873 else
874 bitsize = GET_MODE_BITSIZE (mode);
876 if (size_tree != NULL_TREE)
878 if (! host_integerp (size_tree, 1))
879 bitsize = -1;
880 else
881 bitsize = TREE_INT_CST_LOW (size_tree);
884 /* Initially, maxsize is the same as the accessed element size.
885 In the following it will only grow (or become -1). */
886 maxsize = bitsize;
888 /* Compute cumulative bit-offset for nested component-refs and array-refs,
889 and find the ultimate containing object. */
890 while (1)
892 switch (TREE_CODE (exp))
894 case BIT_FIELD_REF:
895 bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
896 break;
898 case COMPONENT_REF:
900 tree field = TREE_OPERAND (exp, 1);
901 tree this_offset = component_ref_field_offset (exp);
903 if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
905 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
907 hthis_offset *= BITS_PER_UNIT;
908 bit_offset += hthis_offset;
909 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
911 else
913 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
914 /* We need to adjust maxsize to the whole structure bitsize.
915 But we can subtract any constant offset seen so far,
916 because that would get us out of the structure otherwise. */
917 if (maxsize != -1 && csize && host_integerp (csize, 1))
918 maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
919 else
920 maxsize = -1;
923 break;
925 case ARRAY_REF:
926 case ARRAY_RANGE_REF:
928 tree index = TREE_OPERAND (exp, 1);
929 tree low_bound = array_ref_low_bound (exp);
930 tree unit_size = array_ref_element_size (exp);
932 /* If the resulting bit-offset is constant, track it. */
933 if (host_integerp (index, 0)
934 && host_integerp (low_bound, 0)
935 && host_integerp (unit_size, 1))
937 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
939 hindex -= tree_low_cst (low_bound, 0);
940 hindex *= tree_low_cst (unit_size, 1);
941 hindex *= BITS_PER_UNIT;
942 bit_offset += hindex;
944 /* An array ref with a constant index up in the structure
945 hierarchy will constrain the size of any variable array ref
946 lower in the access hierarchy. */
947 seen_variable_array_ref = false;
949 else
951 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
952 /* We need to adjust maxsize to the whole array bitsize.
953 But we can subtract any constant offset seen so far,
954 because that would get us outside of the array otherwise. */
955 if (maxsize != -1 && asize && host_integerp (asize, 1))
956 maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
957 else
958 maxsize = -1;
960 /* Remember that we have seen an array ref with a variable
961 index. */
962 seen_variable_array_ref = true;
965 break;
967 case REALPART_EXPR:
968 break;
970 case IMAGPART_EXPR:
971 bit_offset += bitsize;
972 break;
974 case VIEW_CONVERT_EXPR:
975 /* ??? We probably should give up here and bail out. */
976 break;
978 default:
979 goto done;
982 exp = TREE_OPERAND (exp, 0);
984 done:
986 /* We need to deal with variable arrays ending structures such as
987 struct { int length; int a[1]; } x; x.a[d]
988 struct { struct { int a; int b; } a[1]; } x; x.a[d].a
989 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
990 where we do not know maxsize for variable index accesses to
991 the array. The simplest way to conservatively deal with this
992 is to punt in the case that offset + maxsize reaches the
993 base type boundary. */
994 if (seen_variable_array_ref
995 && maxsize != -1
996 && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
997 && bit_offset + maxsize
998 == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
999 maxsize = -1;
1001 /* ??? Due to negative offsets in ARRAY_REF we can end up with
1002 negative bit_offset here. We might want to store a zero offset
1003 in this case. */
1004 *poffset = bit_offset;
1005 *psize = bitsize;
1006 *pmax_size = maxsize;
1008 return exp;
1011 /* Returns true if STMT references an SSA_NAME that has
1012 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
1014 bool
1015 stmt_references_abnormal_ssa_name (tree stmt)
1017 ssa_op_iter oi;
1018 use_operand_p use_p;
1020 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
1022 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
1023 return true;
1026 return false;
1029 /* Return true, if the two memory references REF1 and REF2 may alias. */
1031 bool
1032 refs_may_alias_p (tree ref1, tree ref2)
1034 tree base1, base2;
1035 HOST_WIDE_INT offset1 = 0, offset2 = 0;
1036 HOST_WIDE_INT size1 = -1, size2 = -1;
1037 HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
1038 bool strict_aliasing_applies;
1040 gcc_assert ((SSA_VAR_P (ref1)
1041 || handled_component_p (ref1)
1042 || INDIRECT_REF_P (ref1)
1043 || TREE_CODE (ref1) == TARGET_MEM_REF)
1044 && (SSA_VAR_P (ref2)
1045 || handled_component_p (ref2)
1046 || INDIRECT_REF_P (ref2)
1047 || TREE_CODE (ref2) == TARGET_MEM_REF));
1049 /* Defer to TBAA if possible. */
1050 if (flag_strict_aliasing
1051 && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
1052 return false;
1054 /* Decompose the references into their base objects and the access. */
1055 base1 = ref1;
1056 if (handled_component_p (ref1))
1057 base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
1058 base2 = ref2;
1059 if (handled_component_p (ref2))
1060 base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
1062 /* If both references are based on different variables, they cannot alias.
1063 If both references are based on the same variable, they cannot alias if
1064 the accesses do not overlap. */
1065 if (SSA_VAR_P (base1)
1066 && SSA_VAR_P (base2))
1068 if (!operand_equal_p (base1, base2, 0))
1069 return false;
1070 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1073 /* If one base is a ref-all pointer weird things are allowed. */
1074 strict_aliasing_applies = (flag_strict_aliasing
1075 && (!INDIRECT_REF_P (base1)
1076 || get_alias_set (base1) != 0)
1077 && (!INDIRECT_REF_P (base2)
1078 || get_alias_set (base2) != 0));
1080 /* If strict aliasing applies the only way to access a scalar variable
1081 is through a pointer dereference or through a union (gcc extension). */
1082 if (strict_aliasing_applies
1083 && ((SSA_VAR_P (ref2)
1084 && !AGGREGATE_TYPE_P (TREE_TYPE (ref2))
1085 && !INDIRECT_REF_P (ref1)
1086 && TREE_CODE (TREE_TYPE (base1)) != UNION_TYPE)
1087 || (SSA_VAR_P (ref1)
1088 && !AGGREGATE_TYPE_P (TREE_TYPE (ref1))
1089 && !INDIRECT_REF_P (ref2)
1090 && TREE_CODE (TREE_TYPE (base2)) != UNION_TYPE)))
1091 return false;
1093 /* If both references are through the same type, or if strict aliasing
1094 doesn't apply they are through two same pointers, they do not alias
1095 if the accesses do not overlap. */
1096 if ((strict_aliasing_applies
1097 && (TYPE_MAIN_VARIANT (TREE_TYPE (base1))
1098 == TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1099 || (TREE_CODE (base1) == INDIRECT_REF
1100 && TREE_CODE (base2) == INDIRECT_REF
1101 && operand_equal_p (TREE_OPERAND (base1, 0),
1102 TREE_OPERAND (base2, 0), 0)))
1103 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1105 /* If both are component references through pointers try to find a
1106 common base and apply offset based disambiguation. This handles
1107 for example
1108 struct A { int i; int j; } *q;
1109 struct B { struct A a; int k; } *p;
1110 disambiguating q->i and p->a.j. */
1111 if (strict_aliasing_applies
1112 && (TREE_CODE (base1) == INDIRECT_REF
1113 || TREE_CODE (base2) == INDIRECT_REF)
1114 && handled_component_p (ref1)
1115 && handled_component_p (ref2))
1117 tree *refp;
1118 /* Now search for the type of base1 in the access path of ref2. This
1119 would be a common base for doing offset based disambiguation on. */
1120 refp = &ref2;
1121 while (handled_component_p (*refp)
1122 /* Note that the following is only conservative if there are
1123 never copies of types appearing as sub-structures. */
1124 && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1125 != TYPE_MAIN_VARIANT (TREE_TYPE (base1))))
1126 refp = &TREE_OPERAND (*refp, 0);
1127 if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1128 == TYPE_MAIN_VARIANT (TREE_TYPE (base1)))
1130 HOST_WIDE_INT offadj, sztmp, msztmp;
1131 get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1132 offset2 -= offadj;
1133 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1135 /* The other way around. */
1136 refp = &ref1;
1137 while (handled_component_p (*refp)
1138 && (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1139 != TYPE_MAIN_VARIANT (TREE_TYPE (base2))))
1140 refp = &TREE_OPERAND (*refp, 0);
1141 if (TYPE_MAIN_VARIANT (TREE_TYPE (*refp))
1142 == TYPE_MAIN_VARIANT (TREE_TYPE (base2)))
1144 HOST_WIDE_INT offadj, sztmp, msztmp;
1145 get_ref_base_and_extent (*refp, &offadj, &sztmp, &msztmp);
1146 offset1 -= offadj;
1147 return ranges_overlap_p (offset1, max_size1, offset2, max_size2);
1149 /* If we can be sure to catch all equivalent types in the search
1150 for the common base then we could return false here. In that
1151 case we would be able to disambiguate q->i and p->k. */
1154 return true;
1157 /* Given a stmt STMT that references memory, return the single stmt
1158 that is reached by following the VUSE -> VDEF link. Returns
1159 NULL_TREE, if there is no single stmt that defines all VUSEs of
1160 STMT.
1161 Note that for a stmt with a single virtual operand this may return
1162 a PHI node as well. Note that if all VUSEs are default definitions
1163 this function will return an empty statement. */
1165 tree
1166 get_single_def_stmt (tree stmt)
1168 tree def_stmt = NULL_TREE;
1169 tree use;
1170 ssa_op_iter iter;
1172 FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
1174 tree tmp = SSA_NAME_DEF_STMT (use);
1176 /* ??? This is too simplistic for multiple virtual operands
1177 reaching different PHI nodes of the same basic blocks or for
1178 reaching all default definitions. */
1179 if (def_stmt
1180 && def_stmt != tmp
1181 && !(IS_EMPTY_STMT (def_stmt)
1182 && IS_EMPTY_STMT (tmp)))
1183 return NULL_TREE;
1185 def_stmt = tmp;
1188 return def_stmt;
1191 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1192 reached definitions if they do not alias REF and returns the
1193 defining statement of the single virtual operand that flows in
1194 from a non-backedge. Returns NULL_TREE if such statement within
1195 the above conditions cannot be found. */
1197 tree
1198 get_single_def_stmt_from_phi (tree ref, tree phi)
1200 tree def_arg = NULL_TREE;
1201 int i;
1203 /* Find the single PHI argument that is not flowing in from a
1204 back edge and verify that the loop-carried definitions do
1205 not alias the reference we look for. */
1206 for (i = 0; i < PHI_NUM_ARGS (phi); ++i)
1208 tree arg = PHI_ARG_DEF (phi, i);
1209 tree def_stmt;
1211 if (!(PHI_ARG_EDGE (phi, i)->flags & EDGE_DFS_BACK))
1213 /* Multiple non-back edges? Do not try to handle this. */
1214 if (def_arg)
1215 return NULL_TREE;
1216 def_arg = arg;
1217 continue;
1220 /* Follow the definitions back to the original PHI node. Bail
1221 out once a definition is found that may alias REF. */
1222 def_stmt = SSA_NAME_DEF_STMT (arg);
1225 if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
1226 || refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
1227 return NULL_TREE;
1228 /* ??? This will only work, reaching the PHI node again if
1229 there is a single virtual operand on def_stmt. */
1230 def_stmt = get_single_def_stmt (def_stmt);
1231 if (!def_stmt)
1232 return NULL_TREE;
1234 while (def_stmt != phi);
1237 return SSA_NAME_DEF_STMT (def_arg);
1240 /* Return the single reference statement defining all virtual uses
1241 on STMT or NULL_TREE, if there are multiple defining statements.
1242 Take into account only definitions that alias REF if following
1243 back-edges when looking through a loop PHI node. */
1245 tree
1246 get_single_def_stmt_with_phi (tree ref, tree stmt)
1248 switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
1250 case 0:
1251 gcc_unreachable ();
1253 case 1:
1255 tree def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1256 (stmt, SSA_OP_VIRTUAL_USES));
1257 /* We can handle lookups over PHI nodes only for a single
1258 virtual operand. */
1259 if (TREE_CODE (def_stmt) == PHI_NODE)
1260 return get_single_def_stmt_from_phi (ref, def_stmt);
1261 return def_stmt;
1264 default:
1265 return get_single_def_stmt (stmt);