OSDN Git Service

2008-05-16 Kenneth Zadeck <zadeck@naturalbridge.com>
[pf3gnuchains/gcc-fork.git] / gcc / tree-dfa.c
1 /* Data flow functions for trees.
2    Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
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 3, or (at your option)
10 any later version.
11
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.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hashtab.h"
26 #include "pointer-set.h"
27 #include "tree.h"
28 #include "rtl.h"
29 #include "tm_p.h"
30 #include "hard-reg-set.h"
31 #include "basic-block.h"
32 #include "output.h"
33 #include "timevar.h"
34 #include "expr.h"
35 #include "ggc.h"
36 #include "langhooks.h"
37 #include "flags.h"
38 #include "function.h"
39 #include "diagnostic.h"
40 #include "tree-dump.h"
41 #include "tree-gimple.h"
42 #include "tree-flow.h"
43 #include "tree-inline.h"
44 #include "tree-pass.h"
45 #include "convert.h"
46 #include "params.h"
47 #include "cgraph.h"
48
49 /* Build and maintain data flow information for trees.  */
50
51 /* Counters used to display DFA and SSA statistics.  */
52 struct dfa_stats_d
53 {
54   long num_stmt_anns;
55   long num_var_anns;
56   long num_defs;
57   long num_uses;
58   long num_phis;
59   long num_phi_args;
60   int max_num_phi_args;
61   long num_vdefs;
62   long num_vuses;
63 };
64
65
66 /* Local functions.  */
67 static void collect_dfa_stats (struct dfa_stats_d *);
68 static tree collect_dfa_stats_r (tree *, int *, void *);
69 static tree find_vars_r (tree *, int *, void *);
70
71
72 /*---------------------------------------------------------------------------
73                         Dataflow analysis (DFA) routines
74 ---------------------------------------------------------------------------*/
75 /* Find all the variables referenced in the function.  This function
76    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
77
78    Note that this function does not look for statement operands, it simply
79    determines what variables are referenced in the program and detects
80    various attributes for each variable used by alias analysis and the
81    optimizer.  */
82
83 static unsigned int
84 find_referenced_vars (void)
85 {
86   basic_block bb;
87   block_stmt_iterator si;
88   tree phi;
89
90   FOR_EACH_BB (bb)
91     {
92       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
93         {
94           tree *stmt_p = bsi_stmt_ptr (si);
95           walk_tree (stmt_p, find_vars_r, NULL, NULL);
96         }
97
98       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
99         {
100           int len = PHI_NUM_ARGS (phi);
101           int i;
102
103           walk_tree (&phi, find_vars_r, NULL, NULL);
104
105           for (i = 0; i < len; i++)
106             {
107               tree arg = PHI_ARG_DEF (phi, i);
108               walk_tree (&arg, find_vars_r, NULL, NULL);
109             }
110         }
111     }
112
113   return 0;
114 }
115
116 struct gimple_opt_pass pass_referenced_vars =
117 {
118  {
119   GIMPLE_PASS,
120   NULL,                                 /* name */
121   NULL,                                 /* gate */
122   find_referenced_vars,                 /* execute */
123   NULL,                                 /* sub */
124   NULL,                                 /* next */
125   0,                                    /* static_pass_number */
126   TV_FIND_REFERENCED_VARS,              /* tv_id */
127   PROP_gimple_leh | PROP_cfg,           /* properties_required */
128   PROP_referenced_vars,                 /* properties_provided */
129   0,                                    /* properties_destroyed */
130   TODO_dump_func,                       /* todo_flags_start */
131   TODO_dump_func                        /* todo_flags_finish */
132  }
133 };
134
135
136 /*---------------------------------------------------------------------------
137                             Manage annotations
138 ---------------------------------------------------------------------------*/
139 /* Create a new annotation for a _DECL node T.  */
140
141 var_ann_t
142 create_var_ann (tree t)
143 {
144   var_ann_t ann;
145   struct static_var_ann_d *sann = NULL;
146
147   gcc_assert (t);
148   gcc_assert (DECL_P (t));
149   gcc_assert (!t->base.ann || t->base.ann->common.type == VAR_ANN);
150
151   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
152     {
153       sann = GGC_CNEW (struct static_var_ann_d);
154       ann = &sann->ann;
155     }
156   else
157     ann = GGC_CNEW (struct var_ann_d);
158
159   ann->common.type = VAR_ANN;
160
161   if (!MTAG_P (t) && (TREE_STATIC (t) || DECL_EXTERNAL (t)))
162     {
163        void **slot;
164        sann->uid = DECL_UID (t);
165        slot = htab_find_slot_with_hash (gimple_var_anns (cfun),
166                                         t, DECL_UID (t), INSERT);
167        gcc_assert (!*slot);
168        *slot = sann;
169     }
170   else
171     t->base.ann = (tree_ann_t) ann;
172
173   return ann;
174 }
175
176 /* Create a new annotation for a FUNCTION_DECL node T.  */
177
178 function_ann_t
179 create_function_ann (tree t)
180 {
181   function_ann_t ann;
182
183   gcc_assert (t);
184   gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
185   gcc_assert (!t->base.ann || t->base.ann->common.type == FUNCTION_ANN);
186
187   ann = ggc_alloc (sizeof (*ann));
188   memset ((void *) ann, 0, sizeof (*ann));
189
190   ann->common.type = FUNCTION_ANN;
191
192   t->base.ann = (tree_ann_t) ann;
193
194   return ann;
195 }
196
197 /* Create a new annotation for a statement node T.  */
198
199 stmt_ann_t
200 create_stmt_ann (tree t)
201 {
202   stmt_ann_t ann;
203
204   gcc_assert (is_gimple_stmt (t));
205   gcc_assert (!t->base.ann || t->base.ann->common.type == STMT_ANN);
206
207   ann = GGC_CNEW (struct stmt_ann_d);
208
209   ann->common.type = STMT_ANN;
210
211   /* Since we just created the annotation, mark the statement modified.  */
212   ann->modified = true;
213
214   ann->uid = inc_gimple_stmt_max_uid (cfun);
215   t->base.ann = (tree_ann_t) ann;
216
217   return ann;
218 }
219
220 /* Renumber all of the gimple stmt uids.  */
221
222 void 
223 renumber_gimple_stmt_uids (void)
224 {
225   basic_block bb;
226
227   set_gimple_stmt_max_uid (cfun, 0);
228   FOR_ALL_BB (bb)
229     {
230       block_stmt_iterator bsi;
231       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
232         {
233           tree stmt = bsi_stmt (bsi);
234           /* If the stmt has an annotation, then overwrite it, if not,
235              the process of getting it will set the number
236              properly.  */
237           if (has_stmt_ann (stmt))
238             set_gimple_stmt_uid (stmt, inc_gimple_stmt_max_uid (cfun));
239           else
240             get_stmt_ann (stmt);
241         }
242     }
243 }
244
245 /* Create a new annotation for a tree T.  */
246
247 tree_ann_common_t
248 create_tree_common_ann (tree t)
249 {
250   tree_ann_common_t ann;
251
252   gcc_assert (t);
253   gcc_assert (!t->base.ann || t->base.ann->common.type == TREE_ANN_COMMON);
254
255   ann = GGC_CNEW (struct tree_ann_common_d);
256
257   ann->type = TREE_ANN_COMMON;
258   t->base.ann = (tree_ann_t) ann;
259
260   return ann;
261 }
262
263 /* Build a temporary.  Make sure and register it to be renamed.  */
264
265 tree
266 make_rename_temp (tree type, const char *prefix)
267 {
268   tree t = create_tmp_var (type, prefix);
269
270   if (TREE_CODE (TREE_TYPE (t)) == COMPLEX_TYPE
271       || TREE_CODE (TREE_TYPE (t)) == VECTOR_TYPE)
272     DECL_GIMPLE_REG_P (t) = 1;
273
274   if (gimple_referenced_vars (cfun))
275     {
276       add_referenced_var (t);
277       mark_sym_for_renaming (t);
278     }
279
280   return t;
281 }
282
283
284
285 /*---------------------------------------------------------------------------
286                               Debugging functions
287 ---------------------------------------------------------------------------*/
288 /* Dump the list of all the referenced variables in the current function to
289    FILE.  */
290
291 void
292 dump_referenced_vars (FILE *file)
293 {
294   tree var;
295   referenced_var_iterator rvi;
296   
297   fprintf (file, "\nReferenced variables in %s: %u\n\n",
298            get_name (current_function_decl), (unsigned) num_referenced_vars);
299   
300   FOR_EACH_REFERENCED_VAR (var, rvi)
301     {
302       fprintf (file, "Variable: ");
303       dump_variable (file, var);
304       fprintf (file, "\n");
305     }
306 }
307
308
309 /* Dump the list of all the referenced variables to stderr.  */
310
311 void
312 debug_referenced_vars (void)
313 {
314   dump_referenced_vars (stderr);
315 }
316
317
318 /* Dump variable VAR and its may-aliases to FILE.  */
319
320 void
321 dump_variable (FILE *file, tree var)
322 {
323   var_ann_t ann;
324
325   if (TREE_CODE (var) == SSA_NAME)
326     {
327       if (POINTER_TYPE_P (TREE_TYPE (var)))
328         dump_points_to_info_for (file, var);
329       var = SSA_NAME_VAR (var);
330     }
331
332   if (var == NULL_TREE)
333     {
334       fprintf (file, "<nil>");
335       return;
336     }
337
338   print_generic_expr (file, var, dump_flags);
339
340   ann = var_ann (var);
341
342   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
343
344   fprintf (file, ", ");
345   print_generic_expr (file, TREE_TYPE (var), dump_flags);
346
347   if (ann && ann->symbol_mem_tag)
348     {
349       fprintf (file, ", symbol memory tag: ");
350       print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
351     }
352
353   if (TREE_ADDRESSABLE (var))
354     fprintf (file, ", is addressable");
355   
356   if (is_global_var (var))
357     fprintf (file, ", is global");
358
359   if (TREE_THIS_VOLATILE (var))
360     fprintf (file, ", is volatile");
361
362   dump_mem_sym_stats_for_var (file, var);
363
364   if (is_call_clobbered (var))
365     {
366       const char *s = "";
367       var_ann_t va = var_ann (var);
368       unsigned int escape_mask = va->escape_mask;
369
370       fprintf (file, ", call clobbered");
371       fprintf (file, " (");
372       if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
373         { fprintf (file, "%sstored in global", s); s = ", "; }
374       if (escape_mask & ESCAPE_TO_ASM)
375         { fprintf (file, "%sgoes through ASM", s); s = ", "; }
376       if (escape_mask & ESCAPE_TO_CALL)
377         { fprintf (file, "%spassed to call", s); s = ", "; }
378       if (escape_mask & ESCAPE_BAD_CAST)
379         { fprintf (file, "%sbad cast", s); s = ", "; }
380       if (escape_mask & ESCAPE_TO_RETURN)
381         { fprintf (file, "%sreturned from func", s); s = ", "; }
382       if (escape_mask & ESCAPE_TO_PURE_CONST)
383         { fprintf (file, "%spassed to pure/const", s); s = ", "; }
384       if (escape_mask & ESCAPE_IS_GLOBAL)
385         { fprintf (file, "%sis global var", s); s = ", "; }
386       if (escape_mask & ESCAPE_IS_PARM)
387         { fprintf (file, "%sis incoming pointer", s); s = ", "; }
388       if (escape_mask & ESCAPE_UNKNOWN)
389         { fprintf (file, "%sunknown escape", s); s = ", "; }
390       fprintf (file, ")");
391     }
392
393   if (ann->noalias_state == NO_ALIAS)
394     fprintf (file, ", NO_ALIAS (does not alias other NO_ALIAS symbols)");
395   else if (ann->noalias_state == NO_ALIAS_GLOBAL)
396     fprintf (file, ", NO_ALIAS_GLOBAL (does not alias other NO_ALIAS symbols"
397                    " and global vars)");
398   else if (ann->noalias_state == NO_ALIAS_ANYTHING)
399     fprintf (file, ", NO_ALIAS_ANYTHING (does not alias any other symbols)");
400
401   if (gimple_default_def (cfun, var))
402     {
403       fprintf (file, ", default def: ");
404       print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
405     }
406
407   if (MTAG_P (var) && may_aliases (var))
408     {
409       fprintf (file, ", may aliases: ");
410       dump_may_aliases_for (file, var);
411     }
412
413   if (!is_gimple_reg (var))
414     {
415       if (memory_partition (var))
416         {
417           fprintf (file, ", belongs to partition: ");
418           print_generic_expr (file, memory_partition (var), dump_flags);
419         }
420
421       if (TREE_CODE (var) == MEMORY_PARTITION_TAG)
422         {
423           fprintf (file, ", partition symbols: ");
424           dump_decl_set (file, MPT_SYMBOLS (var));
425         }
426     }
427
428   fprintf (file, "\n");
429 }
430
431
432 /* Dump variable VAR and its may-aliases to stderr.  */
433
434 void
435 debug_variable (tree var)
436 {
437   dump_variable (stderr, var);
438 }
439
440
441 /* Dump various DFA statistics to FILE.  */
442
443 void
444 dump_dfa_stats (FILE *file)
445 {
446   struct dfa_stats_d dfa_stats;
447
448   unsigned long size, total = 0;
449   const char * const fmt_str   = "%-30s%-13s%12s\n";
450   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
451   const char * const fmt_str_3 = "%-43s%11lu%c\n";
452   const char *funcname
453     = lang_hooks.decl_printable_name (current_function_decl, 2);
454
455   collect_dfa_stats (&dfa_stats);
456
457   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
458
459   fprintf (file, "---------------------------------------------------------\n");
460   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
461   fprintf (file, fmt_str, "", "  instances  ", "used ");
462   fprintf (file, "---------------------------------------------------------\n");
463
464   size = num_referenced_vars * sizeof (tree);
465   total += size;
466   fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
467            SCALE (size), LABEL (size));
468
469   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
470   total += size;
471   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
472            SCALE (size), LABEL (size));
473
474   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
475   total += size;
476   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
477            SCALE (size), LABEL (size));
478
479   size = dfa_stats.num_uses * sizeof (tree *);
480   total += size;
481   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
482            SCALE (size), LABEL (size));
483
484   size = dfa_stats.num_defs * sizeof (tree *);
485   total += size;
486   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
487            SCALE (size), LABEL (size));
488
489   size = dfa_stats.num_vuses * sizeof (tree *);
490   total += size;
491   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
492            SCALE (size), LABEL (size));
493
494   size = dfa_stats.num_vdefs * sizeof (tree *);
495   total += size;
496   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
497            SCALE (size), LABEL (size));
498
499   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
500   total += size;
501   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
502            SCALE (size), LABEL (size));
503
504   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
505   total += size;
506   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
507            SCALE (size), LABEL (size));
508
509   fprintf (file, "---------------------------------------------------------\n");
510   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
511            LABEL (total));
512   fprintf (file, "---------------------------------------------------------\n");
513   fprintf (file, "\n");
514
515   if (dfa_stats.num_phis)
516     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
517              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
518              dfa_stats.max_num_phi_args);
519
520   fprintf (file, "\n");
521 }
522
523
524 /* Dump DFA statistics on stderr.  */
525
526 void
527 debug_dfa_stats (void)
528 {
529   dump_dfa_stats (stderr);
530 }
531
532
533 /* Collect DFA statistics and store them in the structure pointed to by
534    DFA_STATS_P.  */
535
536 static void
537 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
538 {
539   struct pointer_set_t *pset;
540   basic_block bb;
541   block_stmt_iterator i;
542
543   gcc_assert (dfa_stats_p);
544
545   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
546
547   /* Walk all the trees in the function counting references.  Start at
548      basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
549   pset = pointer_set_create ();
550
551   for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
552        !bsi_end_p (i); bsi_next (&i))
553     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
554                pset);
555
556   pointer_set_destroy (pset);
557
558   FOR_EACH_BB (bb)
559     {
560       tree phi;
561       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
562         {
563           dfa_stats_p->num_phis++;
564           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
565           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
566             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
567         }
568     }
569 }
570
571
572 /* Callback for walk_tree to collect DFA statistics for a tree and its
573    children.  */
574
575 static tree
576 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
577                      void *data)
578 {
579   tree t = *tp;
580   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
581
582   if (t->base.ann)
583     {
584       switch (ann_type (t->base.ann))
585         {
586         case STMT_ANN:
587           {
588             dfa_stats_p->num_stmt_anns++;
589             dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
590             dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
591             dfa_stats_p->num_vdefs += NUM_SSA_OPERANDS (t, SSA_OP_VDEF);
592             dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
593             break;
594           }
595
596         case VAR_ANN:
597           dfa_stats_p->num_var_anns++;
598           break;
599
600         default:
601           break;
602         }
603     }
604
605   return NULL;
606 }
607
608
609 /*---------------------------------------------------------------------------
610                              Miscellaneous helpers
611 ---------------------------------------------------------------------------*/
612 /* Callback for walk_tree.  Used to collect variables referenced in
613    the function.  */
614
615 static tree
616 find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
617 {
618   /* If we are reading the lto info back in, we need to rescan the
619      referenced vars.  */
620   if (TREE_CODE (*tp) == SSA_NAME)
621     add_referenced_var (SSA_NAME_VAR (*tp));
622
623   /* If T is a regular variable that the optimizers are interested
624      in, add it to the list of variables.  */
625   else if (SSA_VAR_P (*tp))
626     add_referenced_var (*tp);
627
628   /* Type, _DECL and constant nodes have no interesting children.
629      Ignore them.  */
630   else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
631     *walk_subtrees = 0;
632
633   return NULL_TREE;
634 }
635
636 /* Lookup UID in the referenced_vars hashtable and return the associated
637    variable.  */
638
639 tree 
640 referenced_var_lookup (unsigned int uid)
641 {
642   tree h;
643   struct tree_decl_minimal in;
644   in.uid = uid;
645   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
646   gcc_assert (h || uid == 0);
647   return h;
648 }
649
650 /* Check if TO is in the referenced_vars hash table and insert it if not.  
651    Return true if it required insertion.  */
652
653 bool
654 referenced_var_check_and_insert (tree to)
655
656   tree h, *loc;
657   struct tree_decl_minimal in;
658   unsigned int uid = DECL_UID (to);
659
660   in.uid = uid;
661   h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
662   if (h)
663     {
664       /* DECL_UID has already been entered in the table.  Verify that it is
665          the same entry as TO.  See PR 27793.  */
666       gcc_assert (h == to);
667       return false;
668     }
669
670   loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
671                                            &in, uid, INSERT);
672   *loc = to;
673   return true;
674 }
675
676 /* Lookup VAR UID in the default_defs hashtable and return the associated
677    variable.  */
678
679 tree 
680 gimple_default_def (struct function *fn, tree var)
681 {
682   struct tree_decl_minimal ind;
683   struct tree_ssa_name in;
684   gcc_assert (SSA_VAR_P (var));
685   in.var = (tree)&ind;
686   ind.uid = DECL_UID (var);
687   return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
688 }
689
690 /* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
691
692 void
693 set_default_def (tree var, tree def)
694
695   struct tree_decl_minimal ind;
696   struct tree_ssa_name in;
697   void **loc;
698
699   gcc_assert (SSA_VAR_P (var));
700   in.var = (tree)&ind;
701   ind.uid = DECL_UID (var);
702   if (!def)
703     {
704       loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
705             DECL_UID (var), INSERT);
706       gcc_assert (*loc);
707       htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
708       return;
709     }
710   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
711   loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
712                                   DECL_UID (var), INSERT);
713
714   /* Default definition might be changed by tail call optimization.  */
715   if (*loc)
716     SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
717   *(tree *) loc = def;
718
719    /* Mark DEF as the default definition for VAR.  */
720    SSA_NAME_IS_DEFAULT_DEF (def) = true;
721 }
722
723 /* Add VAR to the list of referenced variables if it isn't already there.  */
724
725 void
726 add_referenced_var (tree var)
727 {
728   var_ann_t v_ann;
729
730   v_ann = get_var_ann (var);
731   gcc_assert (DECL_P (var));
732   
733   /* Insert VAR into the referenced_vars has table if it isn't present.  */
734   if (referenced_var_check_and_insert (var))
735     {
736       /* This is the first time we found this variable, annotate it with
737          attributes that are intrinsic to the variable.  */
738       
739       /* Tag's don't have DECL_INITIAL.  */
740       if (MTAG_P (var))
741         return;
742
743       /* Scan DECL_INITIAL for pointer variables as they may contain
744          address arithmetic referencing the address of other
745          variables.  
746          Even non-constant intializers need to be walked, because
747          IPA passes might prove that their are invariant later on.  */
748       if (DECL_INITIAL (var)
749           /* Initializers of external variables are not useful to the
750              optimizers.  */
751           && !DECL_EXTERNAL (var))
752         walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
753     }
754 }
755
756 /* Remove VAR from the list.  */
757
758 void
759 remove_referenced_var (tree var)
760 {
761   var_ann_t v_ann;
762   struct tree_decl_minimal in;
763   void **loc;
764   unsigned int uid = DECL_UID (var);
765
766   clear_call_clobbered (var);
767   if ((v_ann = var_ann (var)))
768     ggc_free (v_ann);
769   var->base.ann = NULL;
770   gcc_assert (DECL_P (var));
771   in.uid = uid;
772   loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
773                                   NO_INSERT);
774   htab_clear_slot (gimple_referenced_vars (cfun), loc);
775 }
776
777
778 /* Return the virtual variable associated to the non-scalar variable VAR.  */
779
780 tree
781 get_virtual_var (tree var)
782 {
783   STRIP_NOPS (var);
784
785   if (TREE_CODE (var) == SSA_NAME)
786     var = SSA_NAME_VAR (var);
787
788   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
789          || handled_component_p (var))
790     var = TREE_OPERAND (var, 0);
791
792   /* Treating GIMPLE registers as virtual variables makes no sense.
793      Also complain if we couldn't extract a _DECL out of the original
794      expression.  */
795   gcc_assert (SSA_VAR_P (var));
796   gcc_assert (!is_gimple_reg (var));
797
798   return var;
799 }
800
801 /* Mark all the naked symbols in STMT for SSA renaming.
802    
803    NOTE: This function should only be used for brand new statements.
804    If the caller is modifying an existing statement, it should use the
805    combination push_stmt_changes/pop_stmt_changes.  */
806
807 void
808 mark_symbols_for_renaming (tree stmt)
809 {
810   tree op;
811   ssa_op_iter iter;
812
813   update_stmt (stmt);
814
815   /* Mark all the operands for renaming.  */
816   FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
817     if (DECL_P (op))
818       mark_sym_for_renaming (op);
819 }
820
821
822 /* Find all variables within the gimplified statement that were not previously
823    visible to the function and add them to the referenced variables list.  */
824
825 static tree
826 find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
827                             void *data ATTRIBUTE_UNUSED)
828 {
829   tree t = *tp;
830
831   if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
832     {
833       add_referenced_var (t);
834       mark_sym_for_renaming (t);
835     }
836
837   if (IS_TYPE_OR_DECL_P (t))
838     *walk_subtrees = 0;
839
840   return NULL;
841 }
842
843 void
844 find_new_referenced_vars (tree *stmt_p)
845 {
846   walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
847 }
848
849
850 /* If EXP is a handled component reference for a structure, return the
851    base variable.  The access range is delimited by bit positions *POFFSET and
852    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
853    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
854    and *PMAX_SIZE are equal, the access is non-variable.  */
855
856 tree
857 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
858                          HOST_WIDE_INT *psize,
859                          HOST_WIDE_INT *pmax_size)
860 {
861   HOST_WIDE_INT bitsize = -1;
862   HOST_WIDE_INT maxsize = -1;
863   tree size_tree = NULL_TREE;
864   HOST_WIDE_INT bit_offset = 0;
865   bool seen_variable_array_ref = false;
866
867   gcc_assert (!SSA_VAR_P (exp));
868
869   /* First get the final access size from just the outermost expression.  */
870   if (TREE_CODE (exp) == COMPONENT_REF)
871     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
872   else if (TREE_CODE (exp) == BIT_FIELD_REF)
873     size_tree = TREE_OPERAND (exp, 1);
874   else
875     {
876       enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
877       if (mode == BLKmode)
878         size_tree = TYPE_SIZE (TREE_TYPE (exp));
879       else
880         bitsize = GET_MODE_BITSIZE (mode);
881     }
882   if (size_tree != NULL_TREE)
883     {
884       if (! host_integerp (size_tree, 1))
885         bitsize = -1;
886       else
887         bitsize = TREE_INT_CST_LOW (size_tree);
888     }
889
890   /* Initially, maxsize is the same as the accessed element size.
891      In the following it will only grow (or become -1).  */
892   maxsize = bitsize;
893
894   /* Compute cumulative bit-offset for nested component-refs and array-refs,
895      and find the ultimate containing object.  */
896   while (1)
897     {
898       switch (TREE_CODE (exp))
899         {
900         case BIT_FIELD_REF:
901           bit_offset += tree_low_cst (TREE_OPERAND (exp, 2), 0);
902           break;
903
904         case COMPONENT_REF:
905           {
906             tree field = TREE_OPERAND (exp, 1);
907             tree this_offset = component_ref_field_offset (exp);
908
909             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
910               {
911                 HOST_WIDE_INT hthis_offset = tree_low_cst (this_offset, 0);
912
913                 hthis_offset *= BITS_PER_UNIT;
914                 bit_offset += hthis_offset;
915                 bit_offset += tree_low_cst (DECL_FIELD_BIT_OFFSET (field), 0);
916               }
917             else
918               {
919                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
920                 /* We need to adjust maxsize to the whole structure bitsize.
921                    But we can subtract any constant offset seen sofar,
922                    because that would get us out of the structure otherwise.  */
923                 if (maxsize != -1 && csize && host_integerp (csize, 1))
924                   maxsize = TREE_INT_CST_LOW (csize) - bit_offset;
925                 else
926                   maxsize = -1;
927               }
928           }
929           break;
930
931         case ARRAY_REF:
932         case ARRAY_RANGE_REF:
933           {
934             tree index = TREE_OPERAND (exp, 1);
935             tree low_bound = array_ref_low_bound (exp);
936             tree unit_size = array_ref_element_size (exp);
937
938             /* If the resulting bit-offset is constant, track it.  */
939             if (host_integerp (index, 0)
940                 && host_integerp (low_bound, 0)
941                 && host_integerp (unit_size, 1))
942               {
943                 HOST_WIDE_INT hindex = tree_low_cst (index, 0);
944
945                 hindex -= tree_low_cst (low_bound, 0);
946                 hindex *= tree_low_cst (unit_size, 1);
947                 hindex *= BITS_PER_UNIT;
948                 bit_offset += hindex;
949
950                 /* An array ref with a constant index up in the structure
951                    hierarchy will constrain the size of any variable array ref
952                    lower in the access hierarchy.  */
953                 seen_variable_array_ref = false;
954               }
955             else
956               {
957                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
958                 /* We need to adjust maxsize to the whole array bitsize.
959                    But we can subtract any constant offset seen sofar,
960                    because that would get us outside of the array otherwise.  */
961                 if (maxsize != -1 && asize && host_integerp (asize, 1))
962                   maxsize = TREE_INT_CST_LOW (asize) - bit_offset;
963                 else
964                   maxsize = -1;
965
966                 /* Remember that we have seen an array ref with a variable
967                    index.  */
968                 seen_variable_array_ref = true;
969               }
970           }
971           break;
972
973         case REALPART_EXPR:
974           break;
975
976         case IMAGPART_EXPR:
977           bit_offset += bitsize;
978           break;
979
980         case VIEW_CONVERT_EXPR:
981           /* ???  We probably should give up here and bail out.  */
982           break;
983
984         default:
985           goto done;
986         }
987
988       exp = TREE_OPERAND (exp, 0);
989     }
990  done:
991
992   /* We need to deal with variable arrays ending structures such as
993        struct { int length; int a[1]; } x;           x.a[d]
994        struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
995        struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
996      where we do not know maxsize for variable index accesses to
997      the array.  The simplest way to conservatively deal with this
998      is to punt in the case that offset + maxsize reaches the
999      base type boundary.  */
1000   if (seen_variable_array_ref
1001       && maxsize != -1
1002       && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
1003       && bit_offset + maxsize
1004            == (signed)TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
1005     maxsize = -1;
1006
1007   /* ???  Due to negative offsets in ARRAY_REF we can end up with
1008      negative bit_offset here.  We might want to store a zero offset
1009      in this case.  */
1010   *poffset = bit_offset;
1011   *psize = bitsize;
1012   *pmax_size = maxsize;
1013
1014   return exp;
1015 }
1016
1017 /* Returns true if STMT references an SSA_NAME that has
1018    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
1019
1020 bool
1021 stmt_references_abnormal_ssa_name (tree stmt)
1022 {
1023   ssa_op_iter oi;
1024   use_operand_p use_p;
1025
1026   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
1027     {
1028       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
1029         return true;
1030     }
1031
1032   return false;
1033 }
1034
1035 /* Return true, if the two memory references REF1 and REF2 may alias.  */
1036
1037 bool
1038 refs_may_alias_p (tree ref1, tree ref2)
1039 {
1040   tree base1, base2;
1041   HOST_WIDE_INT offset1 = 0, offset2 = 0;
1042   HOST_WIDE_INT size1 = -1, size2 = -1;
1043   HOST_WIDE_INT max_size1 = -1, max_size2 = -1;
1044
1045   gcc_assert ((SSA_VAR_P (ref1)
1046                || handled_component_p (ref1)
1047                || INDIRECT_REF_P (ref1)
1048                || TREE_CODE (ref1) == TARGET_MEM_REF)
1049               && (SSA_VAR_P (ref2)
1050                   || handled_component_p (ref2)
1051                   || INDIRECT_REF_P (ref2)
1052                   || TREE_CODE (ref2) == TARGET_MEM_REF));
1053
1054   /* Defer to TBAA if possible.  */
1055   if (flag_strict_aliasing
1056       && !alias_sets_conflict_p (get_alias_set (ref1), get_alias_set (ref2)))
1057     return false;
1058
1059   /* Decompose the references into their base objects and the access.  */
1060   base1 = ref1;
1061   if (handled_component_p (ref1))
1062     base1 = get_ref_base_and_extent (ref1, &offset1, &size1, &max_size1);
1063   base2 = ref2;
1064   if (handled_component_p (ref2))
1065     base2 = get_ref_base_and_extent (ref2, &offset2, &size2, &max_size2);
1066
1067   /* If both references are based on different variables, they cannot alias.
1068      If both references are based on the same variable, they cannot alias if
1069      if the accesses do not overlap.  */
1070   if (SSA_VAR_P (base1)
1071       && SSA_VAR_P (base2)
1072       && (!operand_equal_p (base1, base2, 0)
1073           || !ranges_overlap_p (offset1, max_size1, offset2, max_size2)))
1074     return false;
1075
1076   /* If both references are through pointers and both pointers are equal
1077      then they do not alias if the accesses do not overlap.  */
1078   if (TREE_CODE (base1) == INDIRECT_REF
1079       && TREE_CODE (base2) == INDIRECT_REF
1080       && operand_equal_p (TREE_OPERAND (base1, 0),
1081                           TREE_OPERAND (base2, 0), 0)
1082       && !ranges_overlap_p (offset1, max_size1, offset2, max_size2))
1083     return false;
1084
1085   return true;
1086 }
1087
1088 /* Given a stmt STMT that references memory, return the single stmt
1089    that is reached by following the VUSE -> VDEF link.  Returns
1090    NULL_TREE, if there is no single stmt that defines all VUSEs of
1091    STMT.
1092    Note that for a stmt with a single virtual operand this may return
1093    a PHI node as well.  Note that if all VUSEs are default definitions
1094    this function will return an empty statement.  */
1095
1096 tree
1097 get_single_def_stmt (tree stmt)
1098 {
1099   tree def_stmt = NULL_TREE;
1100   tree use;
1101   ssa_op_iter iter;
1102
1103   FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
1104     {
1105       tree tmp = SSA_NAME_DEF_STMT (use);
1106
1107       /* ???  This is too simplistic for multiple virtual operands
1108          reaching different PHI nodes of the same basic blocks or for
1109          reaching all default definitions.  */
1110       if (def_stmt
1111           && def_stmt != tmp
1112           && !(IS_EMPTY_STMT (def_stmt)
1113                && IS_EMPTY_STMT (tmp)))
1114         return NULL_TREE;
1115
1116       def_stmt = tmp;
1117     }
1118
1119   return def_stmt;
1120 }
1121
1122 /* Given a PHI node of virtual operands, tries to eliminate cyclic
1123    reached definitions if they do not alias REF and returns the
1124    defining statement of the single virtual operand that flows in
1125    from a non-backedge.  Returns NULL_TREE if such statement within
1126    the above conditions cannot be found.  */
1127
1128 tree
1129 get_single_def_stmt_from_phi (tree ref, tree phi)
1130 {
1131   tree def_arg = NULL_TREE;
1132   int i;
1133
1134   /* Find the single PHI argument that is not flowing in from a
1135      back edge and verify that the loop-carried definitions do
1136      not alias the reference we look for.  */
1137   for (i = 0; i < PHI_NUM_ARGS (phi); ++i)
1138     {
1139       tree arg = PHI_ARG_DEF (phi, i);
1140       tree def_stmt;
1141
1142       if (!(PHI_ARG_EDGE (phi, i)->flags & EDGE_DFS_BACK))
1143         {
1144           /* Multiple non-back edges?  Do not try to handle this.  */
1145           if (def_arg)
1146             return NULL_TREE;
1147           def_arg = arg;
1148           continue;
1149         }
1150
1151       /* Follow the definitions back to the original PHI node.  Bail
1152          out once a definition is found that may alias REF.  */
1153       def_stmt = SSA_NAME_DEF_STMT (arg);
1154       do
1155         {
1156           if (TREE_CODE (def_stmt) != GIMPLE_MODIFY_STMT
1157               || refs_may_alias_p (ref, GIMPLE_STMT_OPERAND (def_stmt, 0)))
1158             return NULL_TREE;
1159           /* ???  This will only work, reaching the PHI node again if
1160              there is a single virtual operand on def_stmt.  */
1161           def_stmt = get_single_def_stmt (def_stmt);
1162           if (!def_stmt)
1163             return NULL_TREE;
1164         }
1165       while (def_stmt != phi);
1166     }
1167
1168   return SSA_NAME_DEF_STMT (def_arg);
1169 }
1170
1171 /* Return the single reference statement defining all virtual uses
1172    on STMT or NULL_TREE, if there are multiple defining statements.
1173    Take into account only definitions that alias REF if following
1174    back-edges when looking through a loop PHI node.  */
1175
1176 tree
1177 get_single_def_stmt_with_phi (tree ref, tree stmt)
1178 {
1179   switch (NUM_SSA_OPERANDS (stmt, SSA_OP_VIRTUAL_USES))
1180     {
1181     case 0:
1182       gcc_unreachable ();
1183
1184     case 1:
1185       {
1186         tree def_stmt = SSA_NAME_DEF_STMT (SINGLE_SSA_TREE_OPERAND
1187                                              (stmt, SSA_OP_VIRTUAL_USES));
1188         /* We can handle lookups over PHI nodes only for a single
1189            virtual operand.  */
1190         if (TREE_CODE (def_stmt) == PHI_NODE)
1191           return get_single_def_stmt_from_phi (ref, def_stmt);
1192         return def_stmt;
1193       }
1194
1195     default:
1196       return get_single_def_stmt (stmt);
1197     }
1198 }