OSDN Git Service

87e0ac865f61c62b4ee9590dd57090f6e5e5d026
[pf3gnuchains/gcc-fork.git] / gcc / tree-dfa.c
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>
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 2, 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 COPYING.  If not, write to
19 the Free Software Foundation, 59 Temple Place - Suite 330,
20 Boston, MA 02111-1307, USA.  */
21
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "hashtab.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 "errors.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-alias-common.h"
46 #include "tree-pass.h"
47 #include "convert.h"
48 #include "params.h"
49
50 /* Build and maintain data flow information for trees.  */
51
52 /* Counters used to display DFA and SSA statistics.  */
53 struct dfa_stats_d
54 {
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_v_may_defs;
63   long num_vuses;
64   long num_v_must_defs;
65 };
66
67
68 /* State information for find_vars_r.  */
69 struct walk_state
70 {
71   /* Hash table used to avoid adding the same variable more than once.  */
72   htab_t vars_found;
73 };
74
75
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
85
86 /* Global declarations.  */
87
88 /* Array of all variables referenced in the function.  */
89 varray_type referenced_vars;
90
91
92 /*---------------------------------------------------------------------------
93                         Dataflow analysis (DFA) routines
94 ---------------------------------------------------------------------------*/
95 /* Find all the variables referenced in the function.  This function
96    builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
97
98    Note that this function does not look for statement operands, it simply
99    determines what variables are referenced in the program and detects
100    various attributes for each variable used by alias analysis and the
101    optimizer.  */
102
103 static void
104 find_referenced_vars (void)
105 {
106   htab_t vars_found;
107   basic_block bb;
108   block_stmt_iterator si;
109   struct walk_state walk_state;
110
111   vars_found = htab_create (50, htab_hash_pointer, htab_eq_pointer, NULL);
112   memset (&walk_state, 0, sizeof (walk_state));
113   walk_state.vars_found = vars_found;
114
115   FOR_EACH_BB (bb)
116     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
117       {
118         tree *stmt_p = bsi_stmt_ptr (si);
119         walk_tree (stmt_p, find_vars_r, &walk_state, NULL);
120       }
121
122   htab_delete (vars_found);
123 }
124
125 struct tree_opt_pass pass_referenced_vars =
126 {
127   NULL,                                 /* name */
128   NULL,                                 /* gate */
129   find_referenced_vars,                 /* execute */
130   NULL,                                 /* sub */
131   NULL,                                 /* next */
132   0,                                    /* static_pass_number */
133   0,                                    /* tv_id */
134   PROP_gimple_leh | PROP_cfg,           /* properties_required */
135   PROP_referenced_vars,                 /* properties_provided */
136   0,                                    /* properties_destroyed */
137   0,                                    /* todo_flags_start */
138   0,                                    /* todo_flags_finish */
139   0                                     /* letter */
140 };
141
142
143 /* Compute immediate uses.
144
145    CALC_FOR is an optional function pointer which indicates whether
146       immediate uses information should be calculated for a given SSA
147       variable.  If NULL, then information is computed for all
148       variables.
149
150    FLAGS is one of {TDFA_USE_OPS, TDFA_USE_VOPS}.  It is used by
151       compute_immediate_uses_for_stmt to determine whether to look at
152       virtual and/or real operands while computing def-use chains.  */
153
154 void
155 compute_immediate_uses (int flags, bool (*calc_for)(tree))
156 {
157   basic_block bb;
158   block_stmt_iterator si;
159
160   FOR_EACH_BB (bb)
161     {
162       tree phi;
163
164       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
165         {
166           if (is_gimple_reg (PHI_RESULT (phi)))
167             {
168               if (!(flags & TDFA_USE_OPS))
169                 continue;
170             }
171           else
172             {
173               if (!(flags & TDFA_USE_VOPS))
174                 continue;
175             }
176
177           compute_immediate_uses_for_phi (phi, calc_for);
178         }
179
180       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
181         {
182           tree stmt = bsi_stmt (si);
183           get_stmt_operands (stmt);
184           compute_immediate_uses_for_stmt (stmt, flags, calc_for);
185         }
186     }
187 }
188
189
190 /* Invalidates dataflow information for a statement STMT.  */
191
192 static void
193 free_df_for_stmt (tree stmt)
194 {
195   stmt_ann_t ann = stmt_ann (stmt);
196
197   if (ann && ann->df)
198     {
199       /* If we have a varray of immediate uses, then go ahead and release
200          it for re-use.  */
201       if (ann->df->immediate_uses)
202         ggc_free (ann->df->immediate_uses);
203
204       /* Similarly for the main dataflow structure.  */
205       ggc_free (ann->df);
206       ann->df = NULL;
207     }
208 }
209
210
211 /* Invalidate dataflow information for the whole function.  */
212
213 void
214 free_df (void)
215 {
216   basic_block bb;
217   block_stmt_iterator si;
218
219   FOR_EACH_BB (bb)
220     {
221       tree phi;
222
223       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
224         free_df_for_stmt (phi);
225
226       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
227         {
228           tree stmt = bsi_stmt (si);
229           free_df_for_stmt (stmt);
230         }
231     }
232 }
233
234
235 /* Helper for compute_immediate_uses.  Check all the USE and/or VUSE
236    operands in phi node PHI and add a def-use edge between their
237    defining statement and PHI.  CALC_FOR is as in
238    compute_immediate_uses.
239
240    PHI nodes are easy, we only need to look at their arguments.  */
241
242 static void
243 compute_immediate_uses_for_phi (tree phi, bool (*calc_for)(tree))
244 {
245   int i;
246
247 #ifdef ENABLE_CHECKING
248   if (TREE_CODE (phi) != PHI_NODE)
249     abort ();
250 #endif
251
252   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
253     {
254       tree arg = PHI_ARG_DEF (phi, i);
255
256       if (TREE_CODE (arg) == SSA_NAME && (!calc_for || calc_for (arg)))
257         {
258           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF (phi, i));
259           if (!IS_EMPTY_STMT (imm_rdef_stmt))
260             add_immediate_use (imm_rdef_stmt, phi);
261         }
262     }
263 }
264
265
266 /* Another helper for compute_immediate_uses.  Depending on the value
267    of FLAGS, check all the USE and/or VUSE operands in STMT and add a
268    def-use edge between their defining statement and STMT.  CALC_FOR
269    is as in compute_immediate_uses.  */
270
271 static void
272 compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
273 {
274   tree use;
275   ssa_op_iter iter;
276
277 #ifdef ENABLE_CHECKING
278   /* PHI nodes are handled elsewhere.  */
279   if (TREE_CODE (stmt) == PHI_NODE)
280     abort ();
281 #endif
282
283   /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
284   if (flags & TDFA_USE_OPS)
285     {
286       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
287         {
288           tree imm_stmt = SSA_NAME_DEF_STMT (use);
289           if (!IS_EMPTY_STMT (imm_stmt) && (!calc_for || calc_for (use)))
290             add_immediate_use (imm_stmt, stmt);
291         }
292     }
293
294   if (flags & TDFA_USE_VOPS)
295     {
296       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
297         {
298           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (use);
299           if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (use)))
300             add_immediate_use (imm_rdef_stmt, stmt);
301         }
302     }
303 }
304
305
306 /* Add statement USE_STMT to the list of statements that use definitions
307     made by STMT.  */
308
309 static void
310 add_immediate_use (tree stmt, tree use_stmt)
311 {
312   stmt_ann_t ann = get_stmt_ann (stmt);
313   struct dataflow_d *df;
314
315   df = ann->df;
316   if (df == NULL)
317     {
318       df = ann->df = ggc_alloc (sizeof (struct dataflow_d));
319       memset ((void *) df, 0, sizeof (struct dataflow_d));
320       df->uses[0] = use_stmt;
321       return;
322     }
323
324   if (!df->uses[1])
325     {
326       df->uses[1] = use_stmt;
327       return;
328     }
329
330   if (ann->df->immediate_uses == NULL)
331     VARRAY_TREE_INIT (ann->df->immediate_uses, 4, "immediate_uses");
332
333   VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
334 }
335
336
337 /* If the immediate use of USE points to OLD, then redirect it to NEW.  */
338
339 static void
340 redirect_immediate_use (tree use, tree old, tree new)
341 {
342   tree imm_stmt = SSA_NAME_DEF_STMT (use);
343   struct dataflow_d *df = get_stmt_ann (imm_stmt)->df;
344   unsigned int num_uses = num_immediate_uses (df);
345   unsigned int i;
346
347   for (i = 0; i < num_uses; i++)
348     {
349       if (immediate_use (df, i) == old)
350         {
351           if (i == 0 || i == 1)
352             df->uses[i] = new;
353           else
354             VARRAY_TREE (df->immediate_uses, i - 2) = new;
355         }
356     }
357 }
358
359
360 /* Redirect all immediate uses for operands in OLD so that they point
361    to NEW.  This routine should have no knowledge of how immediate
362    uses are stored.  */
363
364 void
365 redirect_immediate_uses (tree old, tree new)
366 {
367   ssa_op_iter iter;
368   tree val;
369
370   FOR_EACH_SSA_TREE_OPERAND (val, old, iter, SSA_OP_ALL_USES)
371     redirect_immediate_use (val, old, new);
372 }
373
374
375 /*---------------------------------------------------------------------------
376                             Manage annotations
377 ---------------------------------------------------------------------------*/
378 /* Create a new annotation for a _DECL node T.  */
379
380 var_ann_t
381 create_var_ann (tree t)
382 {
383   var_ann_t ann;
384
385 #if defined ENABLE_CHECKING
386   if (t == NULL_TREE
387       || !DECL_P (t)
388       || (t->common.ann
389           && t->common.ann->common.type != VAR_ANN))
390     abort ();
391 #endif
392
393   ann = ggc_alloc (sizeof (*ann));
394   memset ((void *) ann, 0, sizeof (*ann));
395
396   ann->common.type = VAR_ANN;
397
398   t->common.ann = (tree_ann_t) ann;
399
400   return ann;
401 }
402
403
404 /* Create a new annotation for a statement node T.  */
405
406 stmt_ann_t
407 create_stmt_ann (tree t)
408 {
409   stmt_ann_t ann;
410
411 #if defined ENABLE_CHECKING
412   if ((!is_gimple_stmt (t))
413       || (t->common.ann
414           && t->common.ann->common.type != STMT_ANN))
415     abort ();
416 #endif
417
418   ann = ggc_alloc (sizeof (*ann));
419   memset ((void *) ann, 0, sizeof (*ann));
420
421   ann->common.type = STMT_ANN;
422
423   /* Since we just created the annotation, mark the statement modified.  */
424   ann->modified = true;
425
426   t->common.ann = (tree_ann_t) ann;
427
428   return ann;
429 }
430
431
432 /* Create a new annotation for a tree T.  */
433
434 tree_ann_t
435 create_tree_ann (tree t)
436 {
437   tree_ann_t ann;
438
439 #if defined ENABLE_CHECKING
440   if (t == NULL_TREE
441       || (t->common.ann
442           && t->common.ann->common.type != TREE_ANN_COMMON))
443     abort ();
444 #endif
445
446   ann = ggc_alloc (sizeof (*ann));
447   memset ((void *) ann, 0, sizeof (*ann));
448
449   ann->common.type = TREE_ANN_COMMON;
450   t->common.ann = ann;
451
452   return ann;
453 }
454
455 /* Build a temporary.  Make sure and register it to be renamed.  */
456
457 tree
458 make_rename_temp (tree type, const char *prefix)
459 {
460   tree t = create_tmp_var (type, prefix);
461   if (referenced_vars)
462     {
463       add_referenced_tmp_var (t);
464       bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
465     }
466   return t;
467 }
468
469
470
471 /*---------------------------------------------------------------------------
472                               Debugging functions
473 ---------------------------------------------------------------------------*/
474 /* Dump the list of all the referenced variables in the current function to
475    FILE.  */
476
477 void
478 dump_referenced_vars (FILE *file)
479 {
480   size_t i;
481
482   fprintf (file, "\nReferenced variables in %s: %u\n\n",
483            get_name (current_function_decl), (unsigned) num_referenced_vars);
484
485   for (i = 0; i < num_referenced_vars; i++)
486     {
487       tree var = referenced_var (i);
488       fprintf (file, "Variable: ");
489       dump_variable (file, var);
490       fprintf (file, "\n");
491     }
492 }
493
494
495 /* Dump the list of all the referenced variables to stderr.  */
496
497 void
498 debug_referenced_vars (void)
499 {
500   dump_referenced_vars (stderr);
501 }
502
503
504 /* Dump variable VAR and its may-aliases to FILE.  */
505
506 void
507 dump_variable (FILE *file, tree var)
508 {
509   var_ann_t ann;
510
511   if (TREE_CODE (var) == SSA_NAME)
512     {
513       if (POINTER_TYPE_P (TREE_TYPE (var)))
514         dump_points_to_info_for (file, var);
515       var = SSA_NAME_VAR (var);
516     }
517
518   if (var == NULL_TREE)
519     {
520       fprintf (file, "<nil>");
521       return;
522     }
523
524   print_generic_expr (file, var, dump_flags);
525
526   ann = var_ann (var);
527
528   fprintf (file, ", UID %u", (unsigned) ann->uid);
529
530   if (ann->type_mem_tag)
531     {
532       fprintf (file, ", type memory tag: ");
533       print_generic_expr (file, ann->type_mem_tag, dump_flags);
534     }
535
536   if (ann->is_alias_tag)
537     fprintf (file, ", is an alias tag");
538
539   if (TREE_ADDRESSABLE (var))
540     fprintf (file, ", is addressable");
541   
542   if (is_global_var (var))
543     fprintf (file, ", is global");
544
545   if (is_call_clobbered (var))
546     fprintf (file, ", call clobbered");
547
548   if (ann->default_def)
549     {
550       fprintf (file, ", default def: ");
551       print_generic_expr (file, ann->default_def, dump_flags);
552     }
553
554   if (ann->may_aliases)
555     {
556       fprintf (file, ", may aliases: ");
557       dump_may_aliases_for (file, var);
558     }
559
560   fprintf (file, "\n");
561 }
562
563
564 /* Dump variable VAR and its may-aliases to stderr.  */
565
566 void
567 debug_variable (tree var)
568 {
569   dump_variable (stderr, var);
570 }
571
572
573 /* Dump def-use edges on FILE.  */
574
575 void
576 dump_immediate_uses (FILE *file)
577 {
578   basic_block bb;
579   block_stmt_iterator si;
580   const char *funcname
581     = lang_hooks.decl_printable_name (current_function_decl, 2);
582
583   fprintf (file, "\nDef-use edges for function %s\n", funcname);
584
585   FOR_EACH_BB (bb)
586     {
587       tree phi;
588
589       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
590         dump_immediate_uses_for (file, phi);
591
592       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
593         dump_immediate_uses_for (file, bsi_stmt (si));
594     }
595
596   fprintf (file, "\n");
597 }
598
599
600 /* Dump def-use edges on stderr.  */
601
602 void
603 debug_immediate_uses (void)
604 {
605   dump_immediate_uses (stderr);
606 }
607
608
609 /* Dump all immediate uses for STMT on FILE.  */
610
611 void
612 dump_immediate_uses_for (FILE *file, tree stmt)
613 {
614   dataflow_t df = get_immediate_uses (stmt);
615   int num_imm_uses = num_immediate_uses (df);
616
617   if (num_imm_uses > 0)
618     {
619       int i;
620
621       fprintf (file, "-> ");
622       print_generic_stmt (file, stmt, TDF_SLIM);
623       fprintf (file, "\n");
624
625       for (i = 0; i < num_imm_uses; i++)
626         {
627           fprintf (file, "\t");
628           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
629           fprintf (file, "\n");
630         }
631
632       fprintf (file, "\n");
633     }
634 }
635
636
637 /* Dump immediate uses for STMT on stderr.  */
638
639 void
640 debug_immediate_uses_for (tree stmt)
641 {
642   dump_immediate_uses_for (stderr, stmt);
643 }
644
645
646 /* Dump various DFA statistics to FILE.  */
647
648 void
649 dump_dfa_stats (FILE *file)
650 {
651   struct dfa_stats_d dfa_stats;
652
653   unsigned long size, total = 0;
654   const char * const fmt_str   = "%-30s%-13s%12s\n";
655   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
656   const char * const fmt_str_3 = "%-43s%11lu%c\n";
657   const char *funcname
658     = lang_hooks.decl_printable_name (current_function_decl, 2);
659
660   collect_dfa_stats (&dfa_stats);
661
662   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
663
664   fprintf (file, "---------------------------------------------------------\n");
665   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
666   fprintf (file, fmt_str, "", "  instances  ", "used ");
667   fprintf (file, "---------------------------------------------------------\n");
668
669   size = num_referenced_vars * sizeof (tree);
670   total += size;
671   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
672            SCALE (size), LABEL (size));
673
674   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
675   total += size;
676   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
677            SCALE (size), LABEL (size));
678
679   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
680   total += size;
681   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
682            SCALE (size), LABEL (size));
683
684   size = dfa_stats.num_uses * sizeof (tree *);
685   total += size;
686   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
687            SCALE (size), LABEL (size));
688
689   size = dfa_stats.num_defs * sizeof (tree *);
690   total += size;
691   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
692            SCALE (size), LABEL (size));
693
694   size = dfa_stats.num_vuses * sizeof (tree *);
695   total += size;
696   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
697            SCALE (size), LABEL (size));
698
699   size = dfa_stats.num_v_may_defs * sizeof (tree *);
700   total += size;
701   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
702            SCALE (size), LABEL (size));
703
704   size = dfa_stats.num_v_must_defs * sizeof (tree *);
705   total += size;
706   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
707            SCALE (size), LABEL (size));
708
709   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
710   total += size;
711   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
712            SCALE (size), LABEL (size));
713
714   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
715   total += size;
716   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
717            SCALE (size), LABEL (size));
718
719   fprintf (file, "---------------------------------------------------------\n");
720   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
721            LABEL (total));
722   fprintf (file, "---------------------------------------------------------\n");
723   fprintf (file, "\n");
724
725   if (dfa_stats.num_phis)
726     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
727              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
728              dfa_stats.max_num_phi_args);
729
730   fprintf (file, "\n");
731 }
732
733
734 /* Dump DFA statistics on stderr.  */
735
736 void
737 debug_dfa_stats (void)
738 {
739   dump_dfa_stats (stderr);
740 }
741
742
743 /* Collect DFA statistics and store them in the structure pointed by
744    DFA_STATS_P.  */
745
746 static void
747 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
748 {
749   htab_t htab;
750   basic_block bb;
751   block_stmt_iterator i;
752
753   if (dfa_stats_p == NULL)
754     abort ();
755
756   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
757
758   /* Walk all the trees in the function counting references.  Start at
759      basic block 0, but don't stop at block boundaries.  */
760   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
761
762   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
763     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
764                (void *) htab);
765
766   htab_delete (htab);
767
768   FOR_EACH_BB (bb)
769     {
770       tree phi;
771       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
772         {
773           dfa_stats_p->num_phis++;
774           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
775           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
776             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
777         }
778     }
779 }
780
781
782 /* Callback for walk_tree to collect DFA statistics for a tree and its
783    children.  */
784
785 static tree
786 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
787                      void *data)
788 {
789   tree t = *tp;
790   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
791
792   if (t->common.ann)
793     {
794       switch (ann_type (t->common.ann))
795         {
796         case STMT_ANN:
797           {
798             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
799             dfa_stats_p->num_stmt_anns++;
800             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
801             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
802             dfa_stats_p->num_v_may_defs +=
803                          NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann));
804             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
805             dfa_stats_p->num_v_must_defs +=
806                          NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann));
807             break;
808           }
809
810         case VAR_ANN:
811           dfa_stats_p->num_var_anns++;
812           break;
813
814         default:
815           break;
816         }
817     }
818
819   return NULL;
820 }
821
822
823 /*---------------------------------------------------------------------------
824                              Miscellaneous helpers
825 ---------------------------------------------------------------------------*/
826 /* Callback for walk_tree.  Used to collect variables referenced in
827    the function.  */
828
829 static tree
830 find_vars_r (tree *tp, int *walk_subtrees, void *data)
831 {
832   struct walk_state *walk_state = (struct walk_state *) data;
833
834   /* If T is a regular variable that the optimizers are interested
835      in, add it to the list of variables.  */
836   if (SSA_VAR_P (*tp))
837     add_referenced_var (*tp, walk_state);
838
839   /* Type, _DECL and constant nodes have no interesting children.
840      Ignore them.  */
841   else if (DECL_P (*tp)
842            || TYPE_P (*tp)
843            || TREE_CODE_CLASS (TREE_CODE (*tp)) == 'c')
844     *walk_subtrees = 0;
845
846   return NULL_TREE;
847 }
848
849
850 /* Add VAR to the list of dereferenced variables.
851
852    WALK_STATE contains a hash table used to avoid adding the same
853       variable more than once. Note that this function assumes that
854       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
855       duplicate checking is done.  */
856
857 static void
858 add_referenced_var (tree var, struct walk_state *walk_state)
859 {
860   void **slot;
861   var_ann_t v_ann;
862
863   v_ann = get_var_ann (var);
864
865   if (walk_state)
866     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
867   else
868     slot = NULL;
869
870   if (slot == NULL || *slot == NULL)
871     {
872       /* This is the first time we find this variable, add it to the
873          REFERENCED_VARS array and annotate it with attributes that are
874          intrinsic to the variable.  */
875       if (slot)
876         *slot = (void *) var;
877       v_ann->uid = num_referenced_vars;
878       VARRAY_PUSH_TREE (referenced_vars, var);
879
880       /* Global variables are always call-clobbered.  */
881       if (is_global_var (var))
882         mark_call_clobbered (var);
883
884       /* If an initialized global variable then register the initializer
885          as well.  */
886       if (POINTER_TYPE_P (TREE_TYPE (var))
887           && TREE_READONLY (var)
888           && DECL_INITIAL (var)
889           && TREE_CODE (DECL_INITIAL (var)) == ADDR_EXPR)
890         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
891     }
892 }
893
894
895 /* Return the virtual variable associated to the non-scalar variable VAR.  */
896
897 tree
898 get_virtual_var (tree var)
899 {
900   STRIP_NOPS (var);
901
902   if (TREE_CODE (var) == SSA_NAME)
903     var = SSA_NAME_VAR (var);
904
905   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
906          || handled_component_p (var))
907     var = TREE_OPERAND (var, 0);
908
909 #ifdef ENABLE_CHECKING
910   /* Treating GIMPLE registers as virtual variables makes no sense.
911      Also complain if we couldn't extract a _DECL out of the original
912      expression.  */
913   if (!SSA_VAR_P (var)
914       || is_gimple_reg (var))
915     abort ();
916 #endif
917
918   return var;
919 }
920
921 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
922    add_referenced_var, but is used by passes that need to add new temps to
923    the REFERENCED_VARS array after the program has been scanned for
924    variables.  The variable will just receive a new UID and be added
925    to the REFERENCED_VARS array without checking for duplicates.  */
926
927 void
928 add_referenced_tmp_var (tree var)
929 {
930   add_referenced_var (var, NULL);
931 }
932
933
934 /* Add all the non-SSA variables found in STMT's operands to the bitmap
935    VARS_TO_RENAME.  */
936
937 void
938 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
939 {
940   ssa_op_iter iter;
941   tree val;
942   bitmap vars_in_vops_to_rename;
943   bool found_exposed_symbol = false;
944   int v_may_defs_before, v_may_defs_after;
945   int v_must_defs_before, v_must_defs_after;
946
947   vars_in_vops_to_rename = BITMAP_XMALLOC ();
948
949   /* Before re-scanning the statement for operands, mark the existing
950      virtual operands to be renamed again.  We do this because when new
951      symbols are exposed, the virtual operands that were here before due to
952      aliasing will probably be removed by the call to get_stmt_operand.
953      Therefore, we need to flag them to be renamed beforehand.
954
955      We flag them in a separate bitmap because we don't really want to
956      rename them if there are not any newly exposed symbols in the
957      statement operands.  */
958   v_may_defs_before = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
959   v_must_defs_before = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
960
961   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, 
962                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
963     {
964       if (!DECL_P (val))
965         val = SSA_NAME_VAR (val);
966       bitmap_set_bit (vars_in_vops_to_rename, var_ann (val)->uid);
967     }
968
969   /* Now force an operand re-scan on the statement and mark any newly
970      exposed variables.  */
971   modify_stmt (stmt);
972   get_stmt_operands (stmt);
973
974   v_may_defs_after = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
975   v_must_defs_after = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
976
977   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, 
978                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
979
980     {
981       if (DECL_P (val))
982         {
983           found_exposed_symbol = true;
984           bitmap_set_bit (vars_to_rename, var_ann (val)->uid);
985         }
986     }
987
988   /* If we found any newly exposed symbols, or if there are fewer VDEF
989      operands in the statement, add the variables we had set in
990      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
991      vanishing VDEFs because in those cases, the names that were formerly
992      generated by this statement are not going to be available anymore.  */
993   if (found_exposed_symbol
994       || v_may_defs_before > v_may_defs_after
995       || v_must_defs_before > v_must_defs_after)
996     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
997
998   BITMAP_XFREE (vars_in_vops_to_rename);
999 }