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