1/* Data flow functions for trees.
2   Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3   Contributed by Diego Novillo <dnovillo@redhat.com>
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify
8it under the terms of the GNU General Public License as published by
9the Free Software Foundation; either version 2, or (at your option)
10any later version.
11
12GCC is distributed in the hope that it will be useful,
13but WITHOUT ANY WARRANTY; without even the implied warranty of
14MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15GNU General Public License for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING.  If not, write to
19the Free Software Foundation, 51 Franklin Street, Fifth Floor,
20Boston, MA 02110-1301, USA.  */
21
22#include "config.h"
23#include "system.h"
24#include "coretypes.h"
25#include "tm.h"
26#include "hashtab.h"
27#include "pointer-set.h"
28#include "tree.h"
29#include "rtl.h"
30#include "tm_p.h"
31#include "hard-reg-set.h"
32#include "basic-block.h"
33#include "output.h"
34#include "timevar.h"
35#include "expr.h"
36#include "ggc.h"
37#include "langhooks.h"
38#include "flags.h"
39#include "function.h"
40#include "diagnostic.h"
41#include "tree-dump.h"
42#include "tree-gimple.h"
43#include "tree-flow.h"
44#include "tree-inline.h"
45#include "tree-pass.h"
46#include "convert.h"
47#include "params.h"
48#include "cgraph.h"
49
50/* Build and maintain data flow information for trees.  */
51
52/* Counters used to display DFA and SSA statistics.  */
53struct 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/* Local functions.  */
69static void collect_dfa_stats (struct dfa_stats_d *);
70static tree collect_dfa_stats_r (tree *, int *, void *);
71static tree find_vars_r (tree *, int *, void *);
72
73
74/* Global declarations.  */
75
76/* Array of all variables referenced in the function.  */
77htab_t referenced_vars;
78
79/* Default definition for this symbols.  If set for symbol, it
80   means that the first reference to this variable in the function is a
81   USE or a VUSE.  In those cases, the SSA renamer creates an SSA name
82   for this variable with an empty defining statement.  */
83htab_t default_defs;
84
85
86/*---------------------------------------------------------------------------
87			Dataflow analysis (DFA) routines
88---------------------------------------------------------------------------*/
89/* Find all the variables referenced in the function.  This function
90   builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
91
92   Note that this function does not look for statement operands, it simply
93   determines what variables are referenced in the program and detects
94   various attributes for each variable used by alias analysis and the
95   optimizer.  */
96
97static unsigned int
98find_referenced_vars (void)
99{
100  basic_block bb;
101  block_stmt_iterator si;
102
103  FOR_EACH_BB (bb)
104    for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
105      {
106	tree *stmt_p = bsi_stmt_ptr (si);
107	walk_tree (stmt_p, find_vars_r, NULL, NULL);
108      }
109
110  return 0;
111}
112
113struct tree_opt_pass pass_referenced_vars =
114{
115  NULL,					/* name */
116  NULL,					/* gate */
117  find_referenced_vars,			/* execute */
118  NULL,					/* sub */
119  NULL,					/* next */
120  0,					/* static_pass_number */
121  TV_FIND_REFERENCED_VARS,		/* tv_id */
122  PROP_gimple_leh | PROP_cfg,		/* properties_required */
123  PROP_referenced_vars,			/* properties_provided */
124  0,					/* properties_destroyed */
125  0,					/* todo_flags_start */
126  0,                                    /* todo_flags_finish */
127  0				        /* letter */
128};
129
130
131/*---------------------------------------------------------------------------
132			    Manage annotations
133---------------------------------------------------------------------------*/
134/* Create a new annotation for a _DECL node T.  */
135
136var_ann_t
137create_var_ann (tree t)
138{
139  var_ann_t ann;
140
141  gcc_assert (t);
142  gcc_assert (DECL_P (t));
143  gcc_assert (!t->common.ann || t->common.ann->common.type == VAR_ANN);
144
145  ann = GGC_CNEW (struct var_ann_d);
146
147  ann->common.type = VAR_ANN;
148
149  t->common.ann = (tree_ann_t) ann;
150
151  return ann;
152}
153
154/* Create a new annotation for a FUNCTION_DECL node T.  */
155
156function_ann_t
157create_function_ann (tree t)
158{
159  function_ann_t ann;
160
161  gcc_assert (t);
162  gcc_assert (TREE_CODE (t) == FUNCTION_DECL);
163  gcc_assert (!t->common.ann || t->common.ann->common.type == FUNCTION_ANN);
164
165  ann = ggc_alloc (sizeof (*ann));
166  memset ((void *) ann, 0, sizeof (*ann));
167
168  ann->common.type = FUNCTION_ANN;
169
170  t->common.ann = (tree_ann_t) ann;
171
172  return ann;
173}
174
175/* Create a new annotation for a statement node T.  */
176
177stmt_ann_t
178create_stmt_ann (tree t)
179{
180  stmt_ann_t ann;
181
182  gcc_assert (is_gimple_stmt (t));
183  gcc_assert (!t->common.ann || t->common.ann->common.type == STMT_ANN);
184
185  ann = GGC_CNEW (struct stmt_ann_d);
186
187  ann->common.type = STMT_ANN;
188
189  /* Since we just created the annotation, mark the statement modified.  */
190  ann->modified = true;
191
192  t->common.ann = (tree_ann_t) ann;
193
194  return ann;
195}
196
197/* Create a new annotation for a tree T.  */
198
199tree_ann_common_t
200create_tree_common_ann (tree t)
201{
202  tree_ann_common_t ann;
203
204  gcc_assert (t);
205  gcc_assert (!t->common.ann || t->common.ann->common.type == TREE_ANN_COMMON);
206
207  ann = GGC_CNEW (struct tree_ann_common_d);
208
209  ann->type = TREE_ANN_COMMON;
210  t->common.ann = (tree_ann_t) ann;
211
212  return ann;
213}
214
215/* Build a temporary.  Make sure and register it to be renamed.  */
216
217tree
218make_rename_temp (tree type, const char *prefix)
219{
220  tree t = create_tmp_var (type, prefix);
221
222  if (TREE_CODE (type) == COMPLEX_TYPE)
223    DECL_COMPLEX_GIMPLE_REG_P (t) = 1;
224
225  if (referenced_vars)
226    {
227      add_referenced_var (t);
228      mark_sym_for_renaming (t);
229    }
230
231  return t;
232}
233
234
235
236/*---------------------------------------------------------------------------
237			      Debugging functions
238---------------------------------------------------------------------------*/
239/* Dump the list of all the referenced variables in the current function to
240   FILE.  */
241
242void
243dump_referenced_vars (FILE *file)
244{
245  tree var;
246  referenced_var_iterator rvi;
247
248  fprintf (file, "\nReferenced variables in %s: %u\n\n",
249	   get_name (current_function_decl), (unsigned) num_referenced_vars);
250
251  FOR_EACH_REFERENCED_VAR (var, rvi)
252    {
253      fprintf (file, "Variable: ");
254      dump_variable (file, var);
255      fprintf (file, "\n");
256    }
257}
258
259
260/* Dump the list of all the referenced variables to stderr.  */
261
262void
263debug_referenced_vars (void)
264{
265  dump_referenced_vars (stderr);
266}
267
268
269/* Dump sub-variables for VAR to FILE.  */
270
271void
272dump_subvars_for (FILE *file, tree var)
273{
274  subvar_t sv = get_subvars_for_var (var);
275
276  if (!sv)
277    return;
278
279  fprintf (file, "{ ");
280
281  for (; sv; sv = sv->next)
282    {
283      print_generic_expr (file, sv->var, dump_flags);
284      fprintf (file, " ");
285    }
286
287  fprintf (file, "}");
288}
289
290
291/* Dumb sub-variables for VAR to stderr.  */
292
293void
294debug_subvars_for (tree var)
295{
296  dump_subvars_for (stderr, var);
297}
298
299
300/* Dump variable VAR and its may-aliases to FILE.  */
301
302void
303dump_variable (FILE *file, tree var)
304{
305  var_ann_t ann;
306
307  if (TREE_CODE (var) == SSA_NAME)
308    {
309      if (POINTER_TYPE_P (TREE_TYPE (var)))
310	dump_points_to_info_for (file, var);
311      var = SSA_NAME_VAR (var);
312    }
313
314  if (var == NULL_TREE)
315    {
316      fprintf (file, "<nil>");
317      return;
318    }
319
320  print_generic_expr (file, var, dump_flags);
321
322  ann = var_ann (var);
323
324  fprintf (file, ", UID %u", (unsigned) DECL_UID (var));
325
326  fprintf (file, ", ");
327  print_generic_expr (file, TREE_TYPE (var), dump_flags);
328
329  if (ann && ann->symbol_mem_tag)
330    {
331      fprintf (file, ", symbol memory tag: ");
332      print_generic_expr (file, ann->symbol_mem_tag, dump_flags);
333    }
334
335  if (ann && ann->is_aliased)
336    fprintf (file, ", is aliased");
337
338  if (TREE_ADDRESSABLE (var))
339    fprintf (file, ", is addressable");
340
341  if (is_global_var (var))
342    fprintf (file, ", is global");
343
344  if (TREE_THIS_VOLATILE (var))
345    fprintf (file, ", is volatile");
346
347  if (is_call_clobbered (var))
348    {
349      fprintf (file, ", call clobbered");
350      if (dump_flags & TDF_DETAILS)
351	{
352	  var_ann_t va = var_ann (var);
353	  unsigned int escape_mask = va->escape_mask;
354
355	  fprintf (file, " (");
356	  if (escape_mask & ESCAPE_STORED_IN_GLOBAL)
357	    fprintf (file, ", stored in global");
358	  if (escape_mask & ESCAPE_TO_ASM)
359	    fprintf (file, ", goes through ASM");
360	  if (escape_mask & ESCAPE_TO_CALL)
361	    fprintf (file, ", passed to call");
362	  if (escape_mask & ESCAPE_BAD_CAST)
363	    fprintf (file, ", bad cast");
364	  if (escape_mask & ESCAPE_TO_RETURN)
365	    fprintf (file, ", returned from func");
366	  if (escape_mask & ESCAPE_TO_PURE_CONST)
367	    fprintf (file, ", passed to pure/const");
368	  if (escape_mask & ESCAPE_IS_GLOBAL)
369	    fprintf (file, ", is global var");
370	  if (escape_mask & ESCAPE_IS_PARM)
371	    fprintf (file, ", is incoming pointer");
372	  if (escape_mask & ESCAPE_UNKNOWN)
373	    fprintf (file, ", unknown escape");
374	  fprintf (file, " )");
375	}
376    }
377
378  if (default_def (var))
379    {
380      fprintf (file, ", default def: ");
381      print_generic_expr (file, default_def (var), dump_flags);
382    }
383
384  if (may_aliases (var))
385    {
386      fprintf (file, ", may aliases: ");
387      dump_may_aliases_for (file, var);
388    }
389
390  if (get_subvars_for_var (var))
391    {
392      fprintf (file, ", sub-vars: ");
393      dump_subvars_for (file, var);
394    }
395
396  fprintf (file, "\n");
397}
398
399
400/* Dump variable VAR and its may-aliases to stderr.  */
401
402void
403debug_variable (tree var)
404{
405  dump_variable (stderr, var);
406}
407
408
409/* Dump various DFA statistics to FILE.  */
410
411void
412dump_dfa_stats (FILE *file)
413{
414  struct dfa_stats_d dfa_stats;
415
416  unsigned long size, total = 0;
417  const char * const fmt_str   = "%-30s%-13s%12s\n";
418  const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
419  const char * const fmt_str_3 = "%-43s%11lu%c\n";
420  const char *funcname
421    = lang_hooks.decl_printable_name (current_function_decl, 2);
422
423  collect_dfa_stats (&dfa_stats);
424
425  fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
426
427  fprintf (file, "---------------------------------------------------------\n");
428  fprintf (file, fmt_str, "", "  Number of  ", "Memory");
429  fprintf (file, fmt_str, "", "  instances  ", "used ");
430  fprintf (file, "---------------------------------------------------------\n");
431
432  size = num_referenced_vars * sizeof (tree);
433  total += size;
434  fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
435	   SCALE (size), LABEL (size));
436
437  size = dfa_stats.num_stmt_anns * sizeof (struct stmt_ann_d);
438  total += size;
439  fprintf (file, fmt_str_1, "Statements annotated", dfa_stats.num_stmt_anns,
440	   SCALE (size), LABEL (size));
441
442  size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
443  total += size;
444  fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
445	   SCALE (size), LABEL (size));
446
447  size = dfa_stats.num_uses * sizeof (tree *);
448  total += size;
449  fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
450	   SCALE (size), LABEL (size));
451
452  size = dfa_stats.num_defs * sizeof (tree *);
453  total += size;
454  fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
455	   SCALE (size), LABEL (size));
456
457  size = dfa_stats.num_vuses * sizeof (tree *);
458  total += size;
459  fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
460	   SCALE (size), LABEL (size));
461
462  size = dfa_stats.num_v_may_defs * sizeof (tree *);
463  total += size;
464  fprintf (file, fmt_str_1, "V_MAY_DEF operands", dfa_stats.num_v_may_defs,
465	   SCALE (size), LABEL (size));
466
467  size = dfa_stats.num_v_must_defs * sizeof (tree *);
468  total += size;
469  fprintf (file, fmt_str_1, "V_MUST_DEF operands", dfa_stats.num_v_must_defs,
470	   SCALE (size), LABEL (size));
471
472  size = dfa_stats.num_phis * sizeof (struct tree_phi_node);
473  total += size;
474  fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
475	   SCALE (size), LABEL (size));
476
477  size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
478  total += size;
479  fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
480 	   SCALE (size), LABEL (size));
481
482  fprintf (file, "---------------------------------------------------------\n");
483  fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
484	   LABEL (total));
485  fprintf (file, "---------------------------------------------------------\n");
486  fprintf (file, "\n");
487
488  if (dfa_stats.num_phis)
489    fprintf (file, "Average number of arguments per PHI node: %.1f (max: %d)\n",
490	     (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
491	     dfa_stats.max_num_phi_args);
492
493  fprintf (file, "\n");
494}
495
496
497/* Dump DFA statistics on stderr.  */
498
499void
500debug_dfa_stats (void)
501{
502  dump_dfa_stats (stderr);
503}
504
505
506/* Collect DFA statistics and store them in the structure pointed to by
507   DFA_STATS_P.  */
508
509static void
510collect_dfa_stats (struct dfa_stats_d *dfa_stats_p)
511{
512  struct pointer_set_t *pset;
513  basic_block bb;
514  block_stmt_iterator i;
515
516  gcc_assert (dfa_stats_p);
517
518  memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
519
520  /* Walk all the trees in the function counting references.  Start at
521     basic block NUM_FIXED_BLOCKS, but don't stop at block boundaries.  */
522  pset = pointer_set_create ();
523
524  for (i = bsi_start (BASIC_BLOCK (NUM_FIXED_BLOCKS));
525       !bsi_end_p (i); bsi_next (&i))
526    walk_tree (bsi_stmt_ptr (i), collect_dfa_stats_r, (void *) dfa_stats_p,
527	       pset);
528
529  pointer_set_destroy (pset);
530
531  FOR_EACH_BB (bb)
532    {
533      tree phi;
534      for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
535	{
536	  dfa_stats_p->num_phis++;
537	  dfa_stats_p->num_phi_args += PHI_NUM_ARGS (phi);
538	  if (PHI_NUM_ARGS (phi) > dfa_stats_p->max_num_phi_args)
539	    dfa_stats_p->max_num_phi_args = PHI_NUM_ARGS (phi);
540	}
541    }
542}
543
544
545/* Callback for walk_tree to collect DFA statistics for a tree and its
546   children.  */
547
548static tree
549collect_dfa_stats_r (tree *tp, int *walk_subtrees ATTRIBUTE_UNUSED,
550		     void *data)
551{
552  tree t = *tp;
553  struct dfa_stats_d *dfa_stats_p = (struct dfa_stats_d *)data;
554
555  if (t->common.ann)
556    {
557      switch (ann_type (t->common.ann))
558	{
559	case STMT_ANN:
560	  {
561	    dfa_stats_p->num_stmt_anns++;
562	    dfa_stats_p->num_defs += NUM_SSA_OPERANDS (t, SSA_OP_DEF);
563	    dfa_stats_p->num_uses += NUM_SSA_OPERANDS (t, SSA_OP_USE);
564	    dfa_stats_p->num_v_may_defs += NUM_SSA_OPERANDS (t, SSA_OP_VMAYDEF);
565	    dfa_stats_p->num_vuses += NUM_SSA_OPERANDS (t, SSA_OP_VUSE);
566	    dfa_stats_p->num_v_must_defs +=
567				  NUM_SSA_OPERANDS (t, SSA_OP_VMUSTDEF);
568	    break;
569	  }
570
571	case VAR_ANN:
572	  dfa_stats_p->num_var_anns++;
573	  break;
574
575	default:
576	  break;
577	}
578    }
579
580  return NULL;
581}
582
583
584/*---------------------------------------------------------------------------
585			     Miscellaneous helpers
586---------------------------------------------------------------------------*/
587/* Callback for walk_tree.  Used to collect variables referenced in
588   the function.  */
589
590static tree
591find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
592{
593  /* If T is a regular variable that the optimizers are interested
594     in, add it to the list of variables.  */
595  if (SSA_VAR_P (*tp))
596    add_referenced_var (*tp);
597
598  /* Type, _DECL and constant nodes have no interesting children.
599     Ignore them.  */
600  else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
601    *walk_subtrees = 0;
602
603  return NULL_TREE;
604}
605
606/* Lookup UID in the referenced_vars hashtable and return the associated
607   variable.  */
608
609tree
610referenced_var_lookup (unsigned int uid)
611{
612  struct int_tree_map *h, in;
613  in.uid = uid;
614  h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
615  gcc_assert (h || uid == 0);
616  if (h)
617    return h->to;
618  return NULL_TREE;
619}
620
621/* Check if TO is in the referenced_vars hash table and insert it if not.
622   Return true if it required insertion.  */
623
624bool
625referenced_var_check_and_insert (tree to)
626{
627  struct int_tree_map *h, in;
628  void **loc;
629  unsigned int uid = DECL_UID (to);
630
631  in.uid = uid;
632  in.to = to;
633  h = (struct int_tree_map *) htab_find_with_hash (referenced_vars, &in, uid);
634
635  if (h)
636    {
637      /* DECL_UID has already been entered in the table.  Verify that it is
638	 the same entry as TO.  See PR 27793.  */
639      gcc_assert (h->to == to);
640      return false;
641    }
642
643  h = GGC_NEW (struct int_tree_map);
644  h->uid = uid;
645  h->to = to;
646  loc = htab_find_slot_with_hash (referenced_vars, h, uid, INSERT);
647  *(struct int_tree_map **)  loc = h;
648  return true;
649}
650
651/* Lookup VAR UID in the default_defs hashtable and return the associated
652   variable.  */
653
654tree
655default_def (tree var)
656{
657  struct int_tree_map *h, in;
658  gcc_assert (SSA_VAR_P (var));
659  in.uid = DECL_UID (var);
660  h = (struct int_tree_map *) htab_find_with_hash (default_defs, &in,
661                                                   DECL_UID (var));
662  if (h)
663    return h->to;
664  return NULL_TREE;
665}
666
667/* Insert the pair VAR's UID, DEF into the default_defs hashtable.  */
668
669void
670set_default_def (tree var, tree def)
671{
672  struct int_tree_map in;
673  struct int_tree_map *h;
674  void **loc;
675
676  gcc_assert (SSA_VAR_P (var));
677  in.uid = DECL_UID (var);
678  if (!def && default_def (var))
679    {
680      loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
681      htab_remove_elt (default_defs, *loc);
682      return;
683    }
684  gcc_assert (TREE_CODE (def) == SSA_NAME);
685  loc = htab_find_slot_with_hash (default_defs, &in, DECL_UID (var), INSERT);
686  /* Default definition might be changed by tail call optimization.  */
687  if (!*loc)
688    {
689      h = GGC_NEW (struct int_tree_map);
690      h->uid = DECL_UID (var);
691      h->to = def;
692      *(struct int_tree_map **)  loc = h;
693    }
694   else
695    {
696      h = (struct int_tree_map *) *loc;
697      h->to = def;
698    }
699}
700
701/* Add VAR to the list of referenced variables if it isn't already there.  */
702
703void
704add_referenced_var (tree var)
705{
706  var_ann_t v_ann;
707
708  v_ann = get_var_ann (var);
709  gcc_assert (DECL_P (var));
710
711  /* Insert VAR into the referenced_vars has table if it isn't present.  */
712  if (referenced_var_check_and_insert (var))
713    {
714      /* This is the first time we found this variable, annotate it with
715	 attributes that are intrinsic to the variable.  */
716
717      /* Tag's don't have DECL_INITIAL.  */
718      if (MTAG_P (var))
719	return;
720
721      /* Scan DECL_INITIAL for pointer variables as they may contain
722	 address arithmetic referencing the address of other
723	 variables.  */
724      if (DECL_INITIAL (var)
725	  /* Initializers of external variables are not useful to the
726	     optimizers.  */
727          && !DECL_EXTERNAL (var)
728	  /* It's not necessary to walk the initial value of non-constant
729	     variables because it cannot be propagated by the
730	     optimizers.  */
731	  && (TREE_CONSTANT (var) || TREE_READONLY (var)))
732      	walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
733    }
734}
735
736
737/* Return the virtual variable associated to the non-scalar variable VAR.  */
738
739tree
740get_virtual_var (tree var)
741{
742  STRIP_NOPS (var);
743
744  if (TREE_CODE (var) == SSA_NAME)
745    var = SSA_NAME_VAR (var);
746
747  while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
748	 || handled_component_p (var))
749    var = TREE_OPERAND (var, 0);
750
751  /* Treating GIMPLE registers as virtual variables makes no sense.
752     Also complain if we couldn't extract a _DECL out of the original
753     expression.  */
754  gcc_assert (SSA_VAR_P (var));
755  gcc_assert (!is_gimple_reg (var));
756
757  return var;
758}
759
760/* Mark all the non-SSA variables found in STMT's operands to be
761   processed by update_ssa.  */
762
763void
764mark_new_vars_to_rename (tree stmt)
765{
766  ssa_op_iter iter;
767  tree val;
768  bitmap vars_in_vops_to_rename;
769  bool found_exposed_symbol = false;
770  int v_may_defs_before, v_may_defs_after;
771  int v_must_defs_before, v_must_defs_after;
772
773  if (TREE_CODE (stmt) == PHI_NODE)
774    return;
775
776  get_stmt_ann (stmt);
777  vars_in_vops_to_rename = BITMAP_ALLOC (NULL);
778
779  /* Before re-scanning the statement for operands, mark the existing
780     virtual operands to be renamed again.  We do this because when new
781     symbols are exposed, the virtual operands that were here before due to
782     aliasing will probably be removed by the call to get_stmt_operand.
783     Therefore, we need to flag them to be renamed beforehand.
784
785     We flag them in a separate bitmap because we don't really want to
786     rename them if there are not any newly exposed symbols in the
787     statement operands.  */
788  v_may_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
789  v_must_defs_before = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
790
791  FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter,
792			     SSA_OP_VMAYDEF | SSA_OP_VUSE | SSA_OP_VMUSTDEF)
793    {
794      if (!DECL_P (val))
795	val = SSA_NAME_VAR (val);
796      bitmap_set_bit (vars_in_vops_to_rename, DECL_UID (val));
797    }
798
799  /* Now force an operand re-scan on the statement and mark any newly
800     exposed variables.  */
801  update_stmt (stmt);
802
803  v_may_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMAYDEF);
804  v_must_defs_after = NUM_SSA_OPERANDS (stmt, SSA_OP_VMUSTDEF);
805
806  FOR_EACH_SSA_TREE_OPERAND (val, stmt, iter, SSA_OP_ALL_OPERANDS)
807    if (DECL_P (val))
808      {
809	found_exposed_symbol = true;
810	mark_sym_for_renaming (val);
811      }
812
813  /* If we found any newly exposed symbols, or if there are fewer VDEF
814     operands in the statement, add the variables we had set in
815     VARS_IN_VOPS_TO_RENAME to VARS_TO_RENAME.  We need to check for
816     vanishing VDEFs because in those cases, the names that were formerly
817     generated by this statement are not going to be available anymore.  */
818  if (found_exposed_symbol
819      || v_may_defs_before > v_may_defs_after
820      || v_must_defs_before > v_must_defs_after)
821    mark_set_for_renaming (vars_in_vops_to_rename);
822
823  BITMAP_FREE (vars_in_vops_to_rename);
824}
825
826/* Find all variables within the gimplified statement that were not previously
827   visible to the function and add them to the referenced variables list.  */
828
829static tree
830find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
831			    void *data ATTRIBUTE_UNUSED)
832{
833  tree t = *tp;
834
835  if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
836    {
837      add_referenced_var (t);
838      mark_sym_for_renaming (t);
839    }
840
841  if (IS_TYPE_OR_DECL_P (t))
842    *walk_subtrees = 0;
843
844  return NULL;
845}
846
847void
848find_new_referenced_vars (tree *stmt_p)
849{
850  walk_tree (stmt_p, find_new_referenced_vars_1, NULL, NULL);
851}
852
853
854/* If REF is a handled component reference for a structure, return the
855   base variable.  The access range is delimited by bit positions *POFFSET and
856   *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
857   *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
858   and *PMAX_SIZE are equal, the access is non-variable.  */
859
860tree
861get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
862			 HOST_WIDE_INT *psize,
863			 HOST_WIDE_INT *pmax_size)
864{
865  HOST_WIDE_INT bitsize = -1;
866  HOST_WIDE_INT maxsize = -1;
867  tree size_tree = NULL_TREE;
868  tree bit_offset = bitsize_zero_node;
869  bool seen_variable_array_ref = false;
870
871  gcc_assert (!SSA_VAR_P (exp));
872
873  /* First get the final access size from just the outermost expression.  */
874  if (TREE_CODE (exp) == COMPONENT_REF)
875    size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
876  else if (TREE_CODE (exp) == BIT_FIELD_REF)
877    size_tree = TREE_OPERAND (exp, 1);
878  else
879    {
880      enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
881      if (mode == BLKmode)
882	size_tree = TYPE_SIZE (TREE_TYPE (exp));
883      else
884	bitsize = GET_MODE_BITSIZE (mode);
885    }
886  if (size_tree != NULL_TREE)
887    {
888      if (! host_integerp (size_tree, 1))
889	bitsize = -1;
890      else
891	bitsize = TREE_INT_CST_LOW (size_tree);
892    }
893
894  /* Initially, maxsize is the same as the accessed element size.
895     In the following it will only grow (or become -1).  */
896  maxsize = bitsize;
897
898  /* Compute cumulative bit-offset for nested component-refs and array-refs,
899     and find the ultimate containing object.  */
900  while (1)
901    {
902      switch (TREE_CODE (exp))
903	{
904	case BIT_FIELD_REF:
905	  bit_offset = size_binop (PLUS_EXPR, bit_offset,
906				   TREE_OPERAND (exp, 2));
907	  break;
908
909	case COMPONENT_REF:
910	  {
911	    tree field = TREE_OPERAND (exp, 1);
912	    tree this_offset = component_ref_field_offset (exp);
913
914	    if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
915	      {
916		this_offset = size_binop (MULT_EXPR,
917					  fold_convert (bitsizetype,
918							this_offset),
919					  bitsize_unit_node);
920		bit_offset = size_binop (PLUS_EXPR,
921				         bit_offset, this_offset);
922		bit_offset = size_binop (PLUS_EXPR, bit_offset,
923					 DECL_FIELD_BIT_OFFSET (field));
924	      }
925	    else
926	      {
927		tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
928		/* We need to adjust maxsize to the whole structure bitsize.
929		   But we can subtract any constant offset seen sofar,
930		   because that would get us out of the structure otherwise.  */
931		if (maxsize != -1
932		    && csize && host_integerp (csize, 1))
933		  {
934		    maxsize = (TREE_INT_CST_LOW (csize)
935			       - TREE_INT_CST_LOW (bit_offset));
936		  }
937		else
938		  maxsize = -1;
939	      }
940	  }
941	  break;
942
943	case ARRAY_REF:
944	case ARRAY_RANGE_REF:
945	  {
946	    tree index = TREE_OPERAND (exp, 1);
947	    tree low_bound = array_ref_low_bound (exp);
948	    tree unit_size = array_ref_element_size (exp);
949
950	    if (! integer_zerop (low_bound))
951	      index = fold_build2 (MINUS_EXPR, TREE_TYPE (index),
952				   index, low_bound);
953	    index = size_binop (MULT_EXPR,
954				fold_convert (sizetype, index), unit_size);
955	    if (TREE_CODE (index) == INTEGER_CST)
956	      {
957		index = size_binop (MULT_EXPR,
958				    fold_convert (bitsizetype, index),
959				    bitsize_unit_node);
960		bit_offset = size_binop (PLUS_EXPR, bit_offset, index);
961
962		/* An array ref with a constant index up in the structure
963		   hierarchy will constrain the size of any variable array ref
964		   lower in the access hierarchy.  */
965		seen_variable_array_ref = false;
966	      }
967	    else
968	      {
969		tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
970		/* We need to adjust maxsize to the whole array bitsize.
971		   But we can subtract any constant offset seen sofar,
972		   because that would get us outside of the array otherwise.  */
973		if (maxsize != -1
974		    && asize && host_integerp (asize, 1))
975		  {
976		    maxsize = (TREE_INT_CST_LOW (asize)
977			       - TREE_INT_CST_LOW (bit_offset));
978		  }
979		else
980		  maxsize = -1;
981
982		/* Remember that we have seen an array ref with a variable
983		   index.  */
984		seen_variable_array_ref = true;
985	      }
986	  }
987	  break;
988
989	case REALPART_EXPR:
990	  break;
991
992	case IMAGPART_EXPR:
993	  bit_offset = size_binop (PLUS_EXPR, bit_offset,
994				   bitsize_int (bitsize));
995	  break;
996
997	case VIEW_CONVERT_EXPR:
998	  /* ???  We probably should give up here and bail out.  */
999	  break;
1000
1001	default:
1002	  goto done;
1003	}
1004
1005      exp = TREE_OPERAND (exp, 0);
1006    }
1007 done:
1008
1009  /* We need to deal with variable arrays ending structures such as
1010       struct { int length; int a[1]; } x;           x.a[d]
1011       struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
1012       struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
1013     where we do not know maxsize for variable index accesses to
1014     the array.  The simplest way to conservatively deal with this
1015     is to punt in the case that offset + maxsize reaches the
1016     base type boundary.  */
1017  if (seen_variable_array_ref
1018      && maxsize != -1
1019      && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
1020      && TREE_INT_CST_LOW (bit_offset) + maxsize
1021	 == TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))
1022    maxsize = -1;
1023
1024  /* ???  Due to negative offsets in ARRAY_REF we can end up with
1025     negative bit_offset here.  We might want to store a zero offset
1026     in this case.  */
1027  *poffset = TREE_INT_CST_LOW (bit_offset);
1028  *psize = bitsize;
1029  *pmax_size = maxsize;
1030
1031  return exp;
1032}
1033