OSDN Git Service

* targhooks.c (default_unwind_emit, default_scalar_mode_supported_p):
[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   gcc_assert (TREE_CODE (phi) == PHI_NODE);
248
249   for (i = 0; i < PHI_NUM_ARGS (phi); i++)
250     {
251       tree arg = PHI_ARG_DEF (phi, i);
252
253       if (TREE_CODE (arg) == SSA_NAME && (!calc_for || calc_for (arg)))
254         {
255           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (PHI_ARG_DEF (phi, i));
256           if (!IS_EMPTY_STMT (imm_rdef_stmt))
257             add_immediate_use (imm_rdef_stmt, phi);
258         }
259     }
260 }
261
262
263 /* Another helper for compute_immediate_uses.  Depending on the value
264    of FLAGS, check all the USE and/or VUSE operands in STMT and add a
265    def-use edge between their defining statement and STMT.  CALC_FOR
266    is as in compute_immediate_uses.  */
267
268 static void
269 compute_immediate_uses_for_stmt (tree stmt, int flags, bool (*calc_for)(tree))
270 {
271   tree use;
272   ssa_op_iter iter;
273
274   /* PHI nodes are handled elsewhere.  */
275   gcc_assert (TREE_CODE (stmt) != PHI_NODE);
276
277   /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
278   if (flags & TDFA_USE_OPS)
279     {
280       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
281         {
282           tree imm_stmt = SSA_NAME_DEF_STMT (use);
283           if (!IS_EMPTY_STMT (imm_stmt) && (!calc_for || calc_for (use)))
284             add_immediate_use (imm_stmt, stmt);
285         }
286     }
287
288   if (flags & TDFA_USE_VOPS)
289     {
290       FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_VIRTUAL_USES)
291         {
292           tree imm_rdef_stmt = SSA_NAME_DEF_STMT (use);
293           if (!IS_EMPTY_STMT (imm_rdef_stmt) && (!calc_for || calc_for (use)))
294             add_immediate_use (imm_rdef_stmt, stmt);
295         }
296     }
297 }
298
299
300 /* Add statement USE_STMT to the list of statements that use definitions
301     made by STMT.  */
302
303 static void
304 add_immediate_use (tree stmt, tree use_stmt)
305 {
306   stmt_ann_t ann = get_stmt_ann (stmt);
307   struct dataflow_d *df;
308
309   df = ann->df;
310   if (df == NULL)
311     {
312       df = ann->df = ggc_alloc (sizeof (struct dataflow_d));
313       memset ((void *) df, 0, sizeof (struct dataflow_d));
314       df->uses[0] = use_stmt;
315       return;
316     }
317
318   if (!df->uses[1])
319     {
320       df->uses[1] = use_stmt;
321       return;
322     }
323
324   if (ann->df->immediate_uses == NULL)
325     VARRAY_TREE_INIT (ann->df->immediate_uses, 4, "immediate_uses");
326
327   VARRAY_PUSH_TREE (ann->df->immediate_uses, use_stmt);
328 }
329
330
331 /* If the immediate use of USE points to OLD, then redirect it to NEW.  */
332
333 static void
334 redirect_immediate_use (tree use, tree old, tree new)
335 {
336   tree imm_stmt = SSA_NAME_DEF_STMT (use);
337   struct dataflow_d *df = get_stmt_ann (imm_stmt)->df;
338   unsigned int num_uses = num_immediate_uses (df);
339   unsigned int i;
340
341   for (i = 0; i < num_uses; i++)
342     {
343       if (immediate_use (df, i) == old)
344         {
345           if (i == 0 || i == 1)
346             df->uses[i] = new;
347           else
348             VARRAY_TREE (df->immediate_uses, i - 2) = new;
349         }
350     }
351 }
352
353
354 /* Redirect all immediate uses for operands in OLD so that they point
355    to NEW.  This routine should have no knowledge of how immediate
356    uses are stored.  */
357
358 void
359 redirect_immediate_uses (tree old, tree new)
360 {
361   ssa_op_iter iter;
362   tree val;
363
364   FOR_EACH_SSA_TREE_OPERAND (val, old, iter, SSA_OP_ALL_USES)
365     redirect_immediate_use (val, old, new);
366 }
367
368
369 /*---------------------------------------------------------------------------
370                             Manage annotations
371 ---------------------------------------------------------------------------*/
372 /* Create a new annotation for a _DECL node T.  */
373
374 var_ann_t
375 create_var_ann (tree t)
376 {
377   var_ann_t ann;
378
379   gcc_assert (t);
380   gcc_assert (DECL_P (t));
381   gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
382
383   ann = ggc_alloc (sizeof (*ann));
384   memset ((void *) ann, 0, sizeof (*ann));
385
386   ann->common.type = VAR_ANN;
387
388   t->common.ann = (tree_ann_t) ann;
389
390   return ann;
391 }
392
393
394 /* Create a new annotation for a statement node T.  */
395
396 stmt_ann_t
397 create_stmt_ann (tree t)
398 {
399   stmt_ann_t ann;
400
401   gcc_assert (is_gimple_stmt (t));
402   gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN);
403
404   ann = ggc_alloc (sizeof (*ann));
405   memset ((void *) ann, 0, sizeof (*ann));
406
407   ann->common.type = STMT_ANN;
408
409   /* Since we just created the annotation, mark the statement modified.  */
410   ann->modified = true;
411
412   t->common.ann = (tree_ann_t) ann;
413
414   return ann;
415 }
416
417
418 /* Create a new annotation for a tree T.  */
419
420 tree_ann_t
421 create_tree_ann (tree t)
422 {
423   tree_ann_t ann;
424
425   gcc_assert (t);
426   gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON);
427
428   ann = ggc_alloc (sizeof (*ann));
429   memset ((void *) ann, 0, sizeof (*ann));
430
431   ann->common.type = TREE_ANN_COMMON;
432   t->common.ann = ann;
433
434   return ann;
435 }
436
437 /* Build a temporary.  Make sure and register it to be renamed.  */
438
439 tree
440 make_rename_temp (tree type, const char *prefix)
441 {
442   tree t = create_tmp_var (type, prefix);
443   if (referenced_vars)
444     {
445       add_referenced_tmp_var (t);
446       bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
447     }
448   return t;
449 }
450
451
452
453 /*---------------------------------------------------------------------------
454                               Debugging functions
455 ---------------------------------------------------------------------------*/
456 /* Dump the list of all the referenced variables in the current function to
457    FILE.  */
458
459 void
460 dump_referenced_vars (FILE *file)
461 {
462   size_t i;
463
464   fprintf (file, "\nReferenced variables in %s: %u\n\n",
465            get_name (current_function_decl), (unsigned) num_referenced_vars);
466
467   for (i = 0; i < num_referenced_vars; i++)
468     {
469       tree var = referenced_var (i);
470       fprintf (file, "Variable: ");
471       dump_variable (file, var);
472       fprintf (file, "\n");
473     }
474 }
475
476
477 /* Dump the list of all the referenced variables to stderr.  */
478
479 void
480 debug_referenced_vars (void)
481 {
482   dump_referenced_vars (stderr);
483 }
484
485
486 /* Dump variable VAR and its may-aliases to FILE.  */
487
488 void
489 dump_variable (FILE *file, tree var)
490 {
491   var_ann_t ann;
492
493   if (TREE_CODE (var) == SSA_NAME)
494     {
495       if (POINTER_TYPE_P (TREE_TYPE (var)))
496         dump_points_to_info_for (file, var);
497       var = SSA_NAME_VAR (var);
498     }
499
500   if (var == NULL_TREE)
501     {
502       fprintf (file, "<nil>");
503       return;
504     }
505
506   print_generic_expr (file, var, dump_flags);
507
508   ann = var_ann (var);
509
510   fprintf (file, ", UID %u", (unsigned) ann->uid);
511
512   if (ann->type_mem_tag)
513     {
514       fprintf (file, ", type memory tag: ");
515       print_generic_expr (file, ann->type_mem_tag, dump_flags);
516     }
517
518   if (ann->is_alias_tag)
519     fprintf (file, ", is an alias tag");
520
521   if (TREE_ADDRESSABLE (var))
522     fprintf (file, ", is addressable");
523   
524   if (is_global_var (var))
525     fprintf (file, ", is global");
526
527   if (is_call_clobbered (var))
528     fprintf (file, ", call clobbered");
529
530   if (ann->default_def)
531     {
532       fprintf (file, ", default def: ");
533       print_generic_expr (file, ann->default_def, dump_flags);
534     }
535
536   if (ann->may_aliases)
537     {
538       fprintf (file, ", may aliases: ");
539       dump_may_aliases_for (file, var);
540     }
541
542   fprintf (file, "\n");
543 }
544
545
546 /* Dump variable VAR and its may-aliases to stderr.  */
547
548 void
549 debug_variable (tree var)
550 {
551   dump_variable (stderr, var);
552 }
553
554
555 /* Dump def-use edges on FILE.  */
556
557 void
558 dump_immediate_uses (FILE *file)
559 {
560   basic_block bb;
561   block_stmt_iterator si;
562   const char *funcname
563     = lang_hooks.decl_printable_name (current_function_decl, 2);
564
565   fprintf (file, "\nDef-use edges for function %s\n", funcname);
566
567   FOR_EACH_BB (bb)
568     {
569       tree phi;
570
571       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
572         dump_immediate_uses_for (file, phi);
573
574       for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
575         dump_immediate_uses_for (file, bsi_stmt (si));
576     }
577
578   fprintf (file, "\n");
579 }
580
581
582 /* Dump def-use edges on stderr.  */
583
584 void
585 debug_immediate_uses (void)
586 {
587   dump_immediate_uses (stderr);
588 }
589
590
591 /* Dump all immediate uses for STMT on FILE.  */
592
593 void
594 dump_immediate_uses_for (FILE *file, tree stmt)
595 {
596   dataflow_t df = get_immediate_uses (stmt);
597   int num_imm_uses = num_immediate_uses (df);
598
599   if (num_imm_uses > 0)
600     {
601       int i;
602
603       fprintf (file, "-> ");
604       print_generic_stmt (file, stmt, TDF_SLIM);
605       fprintf (file, "\n");
606
607       for (i = 0; i < num_imm_uses; i++)
608         {
609           fprintf (file, "\t");
610           print_generic_stmt (file, immediate_use (df, i), TDF_SLIM);
611           fprintf (file, "\n");
612         }
613
614       fprintf (file, "\n");
615     }
616 }
617
618
619 /* Dump immediate uses for STMT on stderr.  */
620
621 void
622 debug_immediate_uses_for (tree stmt)
623 {
624   dump_immediate_uses_for (stderr, stmt);
625 }
626
627
628 /* Dump various DFA statistics to FILE.  */
629
630 void
631 dump_dfa_stats (FILE *file)
632 {
633   struct dfa_stats_d dfa_stats;
634
635   unsigned long size, total = 0;
636   const char * const fmt_str   = "%-30s%-13s%12s\n";
637   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
638   const char * const fmt_str_3 = "%-43s%11lu%c\n";
639   const char *funcname
640     = lang_hooks.decl_printable_name (current_function_decl, 2);
641
642   collect_dfa_stats (&dfa_stats);
643
644   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
645
646   fprintf (file, "---------------------------------------------------------\n");
647   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
648   fprintf (file, fmt_str, "", "  instances  ", "used ");
649   fprintf (file, "---------------------------------------------------------\n");
650
651   size = num_referenced_vars * sizeof (tree);
652   total += size;
653   fprintf (file, fmt_str_1, "Referenced variables", num_referenced_vars,
654            SCALE (size), LABEL (size));
655
656   size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
657   total += size;
658   fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
659            SCALE (size), LABEL (size));
660
661   size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
662   total += size;
663   fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
664            SCALE (size), LABEL (size));
665
666   size = dfa_stats.num_uses * sizeof (tree *);
667   total += size;
668   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
669            SCALE (size), LABEL (size));
670
671   size = dfa_stats.num_defs * sizeof (tree *);
672   total += size;
673   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
674            SCALE (size), LABEL (size));
675
676   size = dfa_stats.num_vuses * sizeof (tree *);
677   total += size;
678   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
679            SCALE (size), LABEL (size));
680
681   size = dfa_stats.num_v_may_defs * sizeof (tree *);
682   total += size;
683   fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
684            SCALE (size), LABEL (size));
685
686   size = dfa_stats.num_v_must_defs * sizeof (tree *);
687   total += size;
688   fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
689            SCALE (size), LABEL (size));
690
691   size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
692   total += size;
693   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
694            SCALE (size), LABEL (size));
695
696   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
697   total += size;
698   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
699            SCALE (size), LABEL (size));
700
701   fprintf (file, "---------------------------------------------------------\n");
702   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
703            LABEL (total));
704   fprintf (file, "---------------------------------------------------------\n");
705   fprintf (file, "\n");
706
707   if (dfa_stats.num_phis)
708     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
709              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
710              dfa_stats.max_num_phi_args);
711
712   fprintf (file, "\n");
713 }
714
715
716 /* Dump DFA statistics on stderr.  */
717
718 void
719 debug_dfa_stats (void)
720 {
721   dump_dfa_stats (stderr);
722 }
723
724
725 /* Collect DFA statistics and store them in the structure pointed by
726    DFA_STATS_P.  */
727
728 static void
729 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
730 {
731   htab_t htab;
732   basic_block bb;
733   block_stmt_iterator i;
734
735   gcc_assert (dfa_stats_p);
736
737   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
738
739   /* Walk all the trees in the function counting references.  Start at
740      basic block 0, but don't stop at block boundaries.  */
741   htab = htab_create (30, htab_hash_pointer, htab_eq_pointer, NULL);
742
743   for (i = bsi_start (BASIC_BLOCK (0)); !bsi_end_p (i); bsi_next (&i))
744     walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
745                (void *) htab);
746
747   htab_delete (htab);
748
749   FOR_EACH_BB (bb)
750     {
751       tree phi;
752       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
753         {
754           dfa_stats_p->num_phis++;
755           dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
756           if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
757             dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
758         }
759     }
760 }
761
762
763 /* Callback for walk_tree to collect DFA statistics for a tree and its
764    children.  */
765
766 static tree
767 collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
768                      void *data)
769 {
770   tree t = *tp;
771   struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
772
773   if (t->common.ann)
774     {
775       switch (ann_type (t->common.ann))
776         {
777         case STMT_ANN:
778           {
779             stmt_ann_t ann = (stmt_ann_t) t->common.ann;
780             dfa_stats_p->num_stmt_anns++;
781             dfa_stats_p->num_defs += NUM_DEFS (DEF_OPS (ann));
782             dfa_stats_p->num_uses += NUM_USES (USE_OPS (ann));
783             dfa_stats_p->num_v_may_defs +=
784                          NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann));
785             dfa_stats_p->num_vuses += NUM_VUSES (VUSE_OPS (ann));
786             dfa_stats_p->num_v_must_defs +=
787                          NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann));
788             break;
789           }
790
791         case VAR_ANN:
792           dfa_stats_p->num_var_anns++;
793           break;
794
795         default:
796           break;
797         }
798     }
799
800   return NULL;
801 }
802
803
804 /*---------------------------------------------------------------------------
805                              Miscellaneous helpers
806 ---------------------------------------------------------------------------*/
807 /* Callback for walk_tree.  Used to collect variables referenced in
808    the function.  */
809
810 static tree
811 find_vars_r (tree *tp, int *walk_subtrees, void *data)
812 {
813   struct walk_state *walk_state = (struct walk_state *) data;
814
815   /* If T is a regular variable that the optimizers are interested
816      in, add it to the list of variables.  */
817   if (SSA_VAR_P (*tp))
818     add_referenced_var (*tp, walk_state);
819
820   /* Type, _DECL and constant nodes have no interesting children.
821      Ignore them.  */
822   else if (DECL_P (*tp)
823            || TYPE_P (*tp)
824            || TREE_CODE_CLASS (TREE_CODE (*tp)) == 'c')
825     *walk_subtrees = 0;
826
827   return NULL_TREE;
828 }
829
830
831 /* Add VAR to the list of dereferenced variables.
832
833    WALK_STATE contains a hash table used to avoid adding the same
834       variable more than once. Note that this function assumes that
835       VAR is a valid SSA variable.  If WALK_STATE is NULL, no
836       duplicate checking is done.  */
837
838 static void
839 add_referenced_var (tree var, struct walk_state *walk_state)
840 {
841   void **slot;
842   var_ann_t v_ann;
843
844   v_ann = get_var_ann (var);
845
846   if (walk_state)
847     slot = htab_find_slot (walk_state->vars_found, (void *) var, INSERT);
848   else
849     slot = NULL;
850
851   if (slot == NULL || *slot == NULL)
852     {
853       /* This is the first time we find this variable, add it to the
854          REFERENCED_VARS array and annotate it with attributes that are
855          intrinsic to the variable.  */
856       if (slot)
857         *slot = (void *) var;
858       v_ann->uid = num_referenced_vars;
859       VARRAY_PUSH_TREE (referenced_vars, var);
860
861       /* Global variables are always call-clobbered.  */
862       if (is_global_var (var))
863         mark_call_clobbered (var);
864
865       /* If an initialized global variable then register the initializer
866          as well.  */
867       if (POINTER_TYPE_P (TREE_TYPE (var))
868           && TREE_READONLY (var)
869           && DECL_INITIAL (var)
870           && TREE_CODE (DECL_INITIAL (var)) == ADDR_EXPR)
871         walk_tree (&DECL_INITIAL (var), find_vars_r, walk_state, 0);
872     }
873 }
874
875
876 /* Return the virtual variable associated to the non-scalar variable VAR.  */
877
878 tree
879 get_virtual_var (tree var)
880 {
881   STRIP_NOPS (var);
882
883   if (TREE_CODE (var) == SSA_NAME)
884     var = SSA_NAME_VAR (var);
885
886   while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
887          || handled_component_p (var))
888     var = TREE_OPERAND (var, 0);
889
890   /* Treating GIMPLE registers as virtual variables makes no sense.
891      Also complain if we couldn't extract a _DECL out of the original
892      expression.  */
893   gcc_assert (SSA_VAR_P (var));
894   gcc_assert (!is_gimple_reg (var));
895
896   return var;
897 }
898
899 /* Add a temporary variable to REFERENCED_VARS.  This is similar to
900    add_referenced_var, but is used by passes that need to add new temps to
901    the REFERENCED_VARS array after the program has been scanned for
902    variables.  The variable will just receive a new UID and be added
903    to the REFERENCED_VARS array without checking for duplicates.  */
904
905 void
906 add_referenced_tmp_var (tree var)
907 {
908   add_referenced_var (var, NULL);
909 }
910
911
912 /* Add all the non-SSA variables found in STMT's operands to the bitmap
913    VARS_TO_RENAME.  */
914
915 void
916 mark_new_vars_to_rename (tree stmt, bitmap vars_to_rename)
917 {
918   ssa_op_iter iter;
919   tree val;
920   bitmap vars_in_vops_to_rename;
921   bool found_exposed_symbol = false;
922   int v_may_defs_before, v_may_defs_after;
923   int v_must_defs_before, v_must_defs_after;
924
925   vars_in_vops_to_rename = BITMAP_XMALLOC ();
926
927   /* Before re-scanning the statement for operands, mark the existing
928      virtual operands to be renamed again.  We do this because when new
929      symbols are exposed, the virtual operands that were here before due to
930      aliasing will probably be removed by the call to get_stmt_operand.
931      Therefore, we need to flag them to be renamed beforehand.
932
933      We flag them in a separate bitmap because we don't really want to
934      rename them if there are not any newly exposed symbols in the
935      statement operands.  */
936   v_may_defs_before = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
937   v_must_defs_before = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
938
939   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, 
940                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
941     {
942       if (!DECL_P (val))
943         val = SSA_NAME_VAR (val);
944       bitmap_set_bit (vars_in_vops_to_rename, var_ann (val)->uid);
945     }
946
947   /* Now force an operand re-scan on the statement and mark any newly
948      exposed variables.  */
949   modify_stmt (stmt);
950   get_stmt_operands (stmt);
951
952   v_may_defs_after = NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt));
953   v_must_defs_after = NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt));
954
955   FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, 
956                              SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
957
958     {
959       if (DECL_P (val))
960         {
961           found_exposed_symbol = true;
962           bitmap_set_bit (vars_to_rename, var_ann (val)->uid);
963         }
964     }
965
966   /* If we found any newly exposed symbols, or if there are fewer VDEF
967      operands in the statement, add the variables we had set in
968      VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
969      vanishing VDEFs because in those cases, the names that were formerly
970      generated by this statement are not going to be available anymore.  */
971   if (found_exposed_symbol
972       || v_may_defs_before > v_may_defs_after
973       || v_must_defs_before > v_must_defs_after)
974     bitmap_a_or_b (vars_to_rename, vars_to_rename, vars_in_vops_to_rename);
975
976   BITMAP_XFREE (vars_in_vops_to_rename);
977 }