Merge branch 'vendor/GCC50' - gcc 5.0 snapshot 1 FEB 2015
[dragonfly.git] / contrib / gcc-5.0 / gcc / tree-dfa.c
1 /* Data flow functions for trees.
2    Copyright (C) 2001-2015 Free Software Foundation, Inc.
3    Contributed by Diego Novillo <dnovillo@redhat.com>
4
5 This file is part of GCC.
6
7 GCC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 3, or (at your option)
10 any later version.
11
12 GCC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 GNU General Public License for more details.
16
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3.  If not see
19 <http://www.gnu.org/licenses/>.  */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "hashtab.h"
26 #include "hash-set.h"
27 #include "machmode.h"
28 #include "vec.h"
29 #include "double-int.h"
30 #include "input.h"
31 #include "alias.h"
32 #include "symtab.h"
33 #include "wide-int.h"
34 #include "inchash.h"
35 #include "tree.h"
36 #include "fold-const.h"
37 #include "stor-layout.h"
38 #include "tm_p.h"
39 #include "predict.h"
40 #include "hard-reg-set.h"
41 #include "function.h"
42 #include "dominance.h"
43 #include "cfg.h"
44 #include "basic-block.h"
45 #include "langhooks.h"
46 #include "flags.h"
47 #include "tree-pretty-print.h"
48 #include "tree-ssa-alias.h"
49 #include "internal-fn.h"
50 #include "gimple-expr.h"
51 #include "is-a.h"
52 #include "gimple.h"
53 #include "gimple-iterator.h"
54 #include "gimple-walk.h"
55 #include "gimple-ssa.h"
56 #include "tree-phinodes.h"
57 #include "ssa-iterators.h"
58 #include "stringpool.h"
59 #include "tree-ssanames.h"
60 #include "rtl.h"
61 #include "statistics.h"
62 #include "real.h"
63 #include "fixed-value.h"
64 #include "insn-config.h"
65 #include "expmed.h"
66 #include "dojump.h"
67 #include "explow.h"
68 #include "calls.h"
69 #include "emit-rtl.h"
70 #include "varasm.h"
71 #include "stmt.h"
72 #include "expr.h"
73 #include "tree-dfa.h"
74 #include "tree-inline.h"
75 #include "tree-pass.h"
76 #include "params.h"
77
78 /* Build and maintain data flow information for trees.  */
79
80 /* Counters used to display DFA and SSA statistics.  */
81 struct dfa_stats_d
82 {
83   long num_defs;
84   long num_uses;
85   long num_phis;
86   long num_phi_args;
87   size_t max_num_phi_args;
88   long num_vdefs;
89   long num_vuses;
90 };
91
92
93 /* Local functions.  */
94 static void collect_dfa_stats (struct dfa_stats_d *);
95
96
97 /*---------------------------------------------------------------------------
98                         Dataflow analysis (DFA) routines
99 ---------------------------------------------------------------------------*/
100
101 /* Renumber all of the gimple stmt uids.  */
102
103 void
104 renumber_gimple_stmt_uids (void)
105 {
106   basic_block bb;
107
108   set_gimple_stmt_max_uid (cfun, 0);
109   FOR_ALL_BB_FN (bb, cfun)
110     {
111       gimple_stmt_iterator bsi;
112       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
113         {
114           gimple stmt = gsi_stmt (bsi);
115           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
116         }
117       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
118         {
119           gimple stmt = gsi_stmt (bsi);
120           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
121         }
122     }
123 }
124
125 /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks
126    in BLOCKS, of which there are N_BLOCKS.  Also renumbers PHIs.  */
127
128 void
129 renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
130 {
131   int i;
132
133   set_gimple_stmt_max_uid (cfun, 0);
134   for (i = 0; i < n_blocks; i++)
135     {
136       basic_block bb = blocks[i];
137       gimple_stmt_iterator bsi;
138       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
139         {
140           gimple stmt = gsi_stmt (bsi);
141           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
142         }
143       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
144         {
145           gimple stmt = gsi_stmt (bsi);
146           gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
147         }
148     }
149 }
150
151
152
153 /*---------------------------------------------------------------------------
154                               Debugging functions
155 ---------------------------------------------------------------------------*/
156
157 /* Dump variable VAR and its may-aliases to FILE.  */
158
159 void
160 dump_variable (FILE *file, tree var)
161 {
162   if (TREE_CODE (var) == SSA_NAME)
163     {
164       if (POINTER_TYPE_P (TREE_TYPE (var)))
165         dump_points_to_info_for (file, var);
166       var = SSA_NAME_VAR (var);
167     }
168
169   if (var == NULL_TREE)
170     {
171       fprintf (file, "<nil>");
172       return;
173     }
174
175   print_generic_expr (file, var, dump_flags);
176
177   fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
178   if (DECL_PT_UID (var) != DECL_UID (var))
179     fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var));
180
181   fprintf (file, ", ");
182   print_generic_expr (file, TREE_TYPE (var), dump_flags);
183
184   if (TREE_ADDRESSABLE (var))
185     fprintf (file, ", is addressable");
186
187   if (is_global_var (var))
188     fprintf (file, ", is global");
189
190   if (TREE_THIS_VOLATILE (var))
191     fprintf (file, ", is volatile");
192
193   if (cfun && ssa_default_def (cfun, var))
194     {
195       fprintf (file, ", default def: ");
196       print_generic_expr (file, ssa_default_def (cfun, var), dump_flags);
197     }
198
199   if (DECL_INITIAL (var))
200     {
201       fprintf (file, ", initial: ");
202       print_generic_expr (file, DECL_INITIAL (var), dump_flags);
203     }
204
205   fprintf (file, "\n");
206 }
207
208
209 /* Dump variable VAR and its may-aliases to stderr.  */
210
211 DEBUG_FUNCTION void
212 debug_variable (tree var)
213 {
214   dump_variable (stderr, var);
215 }
216
217
218 /* Dump various DFA statistics to FILE.  */
219
220 void
221 dump_dfa_stats (FILE *file)
222 {
223   struct dfa_stats_d dfa_stats;
224
225   unsigned long size, total = 0;
226   const char * const fmt_str   = "%-30s%-13s%12s\n";
227   const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
228   const char * const fmt_str_3 = "%-43s%11lu%c\n";
229   const char *funcname
230     = lang_hooks.decl_printable_name (current_function_decl, 2);
231
232   collect_dfa_stats (&dfa_stats);
233
234   fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
235
236   fprintf (file, "---------------------------------------------------------\n");
237   fprintf (file, fmt_str, "", "  Number of  ", "Memory");
238   fprintf (file, fmt_str, "", "  instances  ", "used ");
239   fprintf (file, "---------------------------------------------------------\n");
240
241   size = dfa_stats.num_uses * sizeof (tree *);
242   total += size;
243   fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
244            SCALE (size), LABEL (size));
245
246   size = dfa_stats.num_defs * sizeof (tree *);
247   total += size;
248   fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
249            SCALE (size), LABEL (size));
250
251   size = dfa_stats.num_vuses * sizeof (tree *);
252   total += size;
253   fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
254            SCALE (size), LABEL (size));
255
256   size = dfa_stats.num_vdefs * sizeof (tree *);
257   total += size;
258   fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
259            SCALE (size), LABEL (size));
260
261   size = dfa_stats.num_phis * sizeof (struct gphi);
262   total += size;
263   fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
264            SCALE (size), LABEL (size));
265
266   size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
267   total += size;
268   fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
269            SCALE (size), LABEL (size));
270
271   fprintf (file, "---------------------------------------------------------\n");
272   fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
273            LABEL (total));
274   fprintf (file, "---------------------------------------------------------\n");
275   fprintf (file, "\n");
276
277   if (dfa_stats.num_phis)
278     fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
279              (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
280              (long) dfa_stats.max_num_phi_args);
281
282   fprintf (file, "\n");
283 }
284
285
286 /* Dump DFA statistics on stderr.  */
287
288 DEBUG_FUNCTION void
289 debug_dfa_stats (void)
290 {
291   dump_dfa_stats (stderr);
292 }
293
294
295 /* Collect DFA statistics and store them in the structure pointed to by
296    DFA_STATS_P.  */
297
298 static void
299 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
300 {
301   basic_block bb;
302
303   gcc_assert (dfa_stats_p);
304
305   memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
306
307   /* Walk all the statements in the function counting references.  */
308   FOR_EACH_BB_FN (bb, cfun)
309     {
310       for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si);
311            gsi_next (&si))
312         {
313           gphi *phi = si.phi ();
314           dfa_stats_p->num_phis++;
315           dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
316           if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
317             dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
318         }
319
320       for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si);
321            gsi_next (&si))
322         {
323           gimple stmt = gsi_stmt (si);
324           dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
325           dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
326           dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
327           dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
328         }
329     }
330 }
331
332
333 /*---------------------------------------------------------------------------
334                              Miscellaneous helpers
335 ---------------------------------------------------------------------------*/
336
337 /* Lookup VAR UID in the default_defs hashtable and return the associated
338    variable.  */
339
340 tree
341 ssa_default_def (struct function *fn, tree var)
342 {
343   struct tree_decl_minimal ind;
344   struct tree_ssa_name in;
345   gcc_assert (TREE_CODE (var) == VAR_DECL
346               || TREE_CODE (var) == PARM_DECL
347               || TREE_CODE (var) == RESULT_DECL);
348   in.var = (tree)&ind;
349   ind.uid = DECL_UID (var);
350   return DEFAULT_DEFS (fn)->find_with_hash ((tree)&in, DECL_UID (var));
351 }
352
353 /* Insert the pair VAR's UID, DEF into the default_defs hashtable
354    of function FN.  */
355
356 void
357 set_ssa_default_def (struct function *fn, tree var, tree def)
358 {
359   struct tree_decl_minimal ind;
360   struct tree_ssa_name in;
361
362   gcc_assert (TREE_CODE (var) == VAR_DECL
363               || TREE_CODE (var) == PARM_DECL
364               || TREE_CODE (var) == RESULT_DECL);
365   in.var = (tree)&ind;
366   ind.uid = DECL_UID (var);
367   if (!def)
368     {
369       tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in,
370                                                           DECL_UID (var),
371                                                           NO_INSERT);
372       if (loc)
373         {
374           SSA_NAME_IS_DEFAULT_DEF (*(tree *)loc) = false;
375           DEFAULT_DEFS (fn)->clear_slot (loc);
376         }
377       return;
378     }
379   gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
380   tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in,
381                                                       DECL_UID (var), INSERT);
382
383   /* Default definition might be changed by tail call optimization.  */
384   if (*loc)
385     SSA_NAME_IS_DEFAULT_DEF (*loc) = false;
386
387    /* Mark DEF as the default definition for VAR.  */
388   *loc = def;
389   SSA_NAME_IS_DEFAULT_DEF (def) = true;
390 }
391
392 /* Retrieve or create a default definition for VAR.  */
393
394 tree
395 get_or_create_ssa_default_def (struct function *fn, tree var)
396 {
397   tree ddef = ssa_default_def (fn, var);
398   if (ddef == NULL_TREE)
399     {
400       ddef = make_ssa_name_fn (fn, var, gimple_build_nop ());
401       set_ssa_default_def (fn, var, ddef);
402     }
403   return ddef;
404 }
405
406
407 /* If EXP is a handled component reference for a structure, return the
408    base variable.  The access range is delimited by bit positions *POFFSET and
409    *POFFSET + *PMAX_SIZE.  The access size is *PSIZE bits.  If either
410    *PSIZE or *PMAX_SIZE is -1, they could not be determined.  If *PSIZE
411    and *PMAX_SIZE are equal, the access is non-variable.  */
412
413 tree
414 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
415                          HOST_WIDE_INT *psize,
416                          HOST_WIDE_INT *pmax_size)
417 {
418   offset_int bitsize = -1;
419   offset_int maxsize;
420   tree size_tree = NULL_TREE;
421   offset_int bit_offset = 0;
422   bool seen_variable_array_ref = false;
423
424   /* First get the final access size from just the outermost expression.  */
425   if (TREE_CODE (exp) == COMPONENT_REF)
426     size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
427   else if (TREE_CODE (exp) == BIT_FIELD_REF)
428     size_tree = TREE_OPERAND (exp, 1);
429   else if (!VOID_TYPE_P (TREE_TYPE (exp)))
430     {
431       machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
432       if (mode == BLKmode)
433         size_tree = TYPE_SIZE (TREE_TYPE (exp));
434       else
435         bitsize = int (GET_MODE_PRECISION (mode));
436     }
437   if (size_tree != NULL_TREE
438       && TREE_CODE (size_tree) == INTEGER_CST)
439     bitsize = wi::to_offset (size_tree);
440
441   /* Initially, maxsize is the same as the accessed element size.
442      In the following it will only grow (or become -1).  */
443   maxsize = bitsize;
444
445   /* Compute cumulative bit-offset for nested component-refs and array-refs,
446      and find the ultimate containing object.  */
447   while (1)
448     {
449       switch (TREE_CODE (exp))
450         {
451         case BIT_FIELD_REF:
452           bit_offset += wi::to_offset (TREE_OPERAND (exp, 2));
453           break;
454
455         case COMPONENT_REF:
456           {
457             tree field = TREE_OPERAND (exp, 1);
458             tree this_offset = component_ref_field_offset (exp);
459
460             if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
461               {
462                 offset_int woffset = wi::lshift (wi::to_offset (this_offset),
463                                                  LOG2_BITS_PER_UNIT);
464                 woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field));
465                 bit_offset += woffset;
466
467                 /* If we had seen a variable array ref already and we just
468                    referenced the last field of a struct or a union member
469                    then we have to adjust maxsize by the padding at the end
470                    of our field.  */
471                 if (seen_variable_array_ref && maxsize != -1)
472                   {
473                     tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
474                     tree next = DECL_CHAIN (field);
475                     while (next && TREE_CODE (next) != FIELD_DECL)
476                       next = DECL_CHAIN (next);
477                     if (!next
478                         || TREE_CODE (stype) != RECORD_TYPE)
479                       {
480                         tree fsize = DECL_SIZE_UNIT (field);
481                         tree ssize = TYPE_SIZE_UNIT (stype);
482                         if (fsize == NULL
483                             || TREE_CODE (fsize) != INTEGER_CST
484                             || ssize == NULL
485                             || TREE_CODE (ssize) != INTEGER_CST)
486                           maxsize = -1;
487                         else
488                           {
489                             offset_int tem = (wi::to_offset (ssize)
490                                               - wi::to_offset (fsize));
491                             tem = wi::lshift (tem, LOG2_BITS_PER_UNIT);
492                             tem -= woffset;
493                             maxsize += tem;
494                           }
495                       }
496                   }
497               }
498             else
499               {
500                 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
501                 /* We need to adjust maxsize to the whole structure bitsize.
502                    But we can subtract any constant offset seen so far,
503                    because that would get us out of the structure otherwise.  */
504                 if (maxsize != -1
505                     && csize
506                     && TREE_CODE (csize) == INTEGER_CST)
507                   maxsize = wi::to_offset (csize) - bit_offset;
508                 else
509                   maxsize = -1;
510               }
511           }
512           break;
513
514         case ARRAY_REF:
515         case ARRAY_RANGE_REF:
516           {
517             tree index = TREE_OPERAND (exp, 1);
518             tree low_bound, unit_size;
519
520             /* If the resulting bit-offset is constant, track it.  */
521             if (TREE_CODE (index) == INTEGER_CST
522                 && (low_bound = array_ref_low_bound (exp),
523                     TREE_CODE (low_bound) == INTEGER_CST)
524                 && (unit_size = array_ref_element_size (exp),
525                     TREE_CODE (unit_size) == INTEGER_CST))
526               {
527                 offset_int woffset
528                   = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound),
529                               TYPE_PRECISION (TREE_TYPE (index)));
530                 woffset *= wi::to_offset (unit_size);
531                 woffset = wi::lshift (woffset, LOG2_BITS_PER_UNIT);
532                 bit_offset += woffset;
533
534                 /* An array ref with a constant index up in the structure
535                    hierarchy will constrain the size of any variable array ref
536                    lower in the access hierarchy.  */
537                 seen_variable_array_ref = false;
538               }
539             else
540               {
541                 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
542                 /* We need to adjust maxsize to the whole array bitsize.
543                    But we can subtract any constant offset seen so far,
544                    because that would get us outside of the array otherwise.  */
545                 if (maxsize != -1
546                     && asize
547                     && TREE_CODE (asize) == INTEGER_CST)
548                   maxsize = wi::to_offset (asize) - bit_offset;
549                 else
550                   maxsize = -1;
551
552                 /* Remember that we have seen an array ref with a variable
553                    index.  */
554                 seen_variable_array_ref = true;
555               }
556           }
557           break;
558
559         case REALPART_EXPR:
560           break;
561
562         case IMAGPART_EXPR:
563           bit_offset += bitsize;
564           break;
565
566         case VIEW_CONVERT_EXPR:
567           break;
568
569         case TARGET_MEM_REF:
570           /* Via the variable index or index2 we can reach the
571              whole object.  Still hand back the decl here.  */
572           if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR
573               && (TMR_INDEX (exp) || TMR_INDEX2 (exp)))
574             {
575               exp = TREE_OPERAND (TMR_BASE (exp), 0);
576               bit_offset = 0;
577               maxsize = -1;
578               goto done;
579             }
580           /* Fallthru.  */
581         case MEM_REF:
582           /* We need to deal with variable arrays ending structures such as
583              struct { int length; int a[1]; } x;           x.a[d]
584              struct { struct { int a; int b; } a[1]; } x;  x.a[d].a
585              struct { struct { int a[1]; } a[1]; } x;      x.a[0][d], x.a[d][0]
586              struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
587              where we do not know maxsize for variable index accesses to
588              the array.  The simplest way to conservatively deal with this
589              is to punt in the case that offset + maxsize reaches the
590              base type boundary.  This needs to include possible trailing
591              padding that is there for alignment purposes.  */
592           if (seen_variable_array_ref
593               && maxsize != -1
594               && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
595                   || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST
596                   || (bit_offset + maxsize
597                       == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp))))))
598             maxsize = -1;
599
600           /* Hand back the decl for MEM[&decl, off].  */
601           if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
602             {
603               if (integer_zerop (TREE_OPERAND (exp, 1)))
604                 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
605               else
606                 {
607                   offset_int off = mem_ref_offset (exp);
608                   off = wi::lshift (off, LOG2_BITS_PER_UNIT);
609                   off += bit_offset;
610                   if (wi::fits_shwi_p (off))
611                     {
612                       bit_offset = off;
613                       exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
614                     }
615                 }
616             }
617           goto done;
618
619         default:
620           goto done;
621         }
622
623       exp = TREE_OPERAND (exp, 0);
624     }
625
626   /* We need to deal with variable arrays ending structures.  */
627   if (seen_variable_array_ref
628       && maxsize != -1
629       && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE
630           || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST
631           || (bit_offset + maxsize
632               == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp))))))
633     maxsize = -1;
634
635  done:
636   if (!wi::fits_shwi_p (bitsize) || wi::neg_p (bitsize))
637     {
638       *poffset = 0;
639       *psize = -1;
640       *pmax_size = -1;
641
642       return exp;
643     }
644
645   *psize = bitsize.to_shwi ();
646
647   if (!wi::fits_shwi_p (bit_offset))
648     {
649       *poffset = 0;
650       *pmax_size = -1;
651
652       return exp;
653     }
654
655   /* In case of a decl or constant base object we can do better.  */
656
657   if (DECL_P (exp))
658     {
659       /* If maxsize is unknown adjust it according to the size of the
660          base decl.  */
661       if (maxsize == -1
662           && DECL_SIZE (exp)
663           && TREE_CODE (DECL_SIZE (exp)) == INTEGER_CST)
664         maxsize = wi::to_offset (DECL_SIZE (exp)) - bit_offset;
665     }
666   else if (CONSTANT_CLASS_P (exp))
667     {
668       /* If maxsize is unknown adjust it according to the size of the
669          base type constant.  */
670       if (maxsize == -1
671           && TYPE_SIZE (TREE_TYPE (exp))
672           && TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) == INTEGER_CST)
673         maxsize = (wi::to_offset (TYPE_SIZE (TREE_TYPE (exp)))
674                    - bit_offset);
675     }
676
677   /* ???  Due to negative offsets in ARRAY_REF we can end up with
678      negative bit_offset here.  We might want to store a zero offset
679      in this case.  */
680   *poffset = bit_offset.to_shwi ();
681   if (!wi::fits_shwi_p (maxsize) || wi::neg_p (maxsize))
682     *pmax_size = -1;
683   else
684     *pmax_size = maxsize.to_shwi ();
685
686   return exp;
687 }
688
689 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
690    denotes the starting address of the memory access EXP.
691    Returns NULL_TREE if the offset is not constant or any component
692    is not BITS_PER_UNIT-aligned.
693    VALUEIZE if non-NULL is used to valueize SSA names.  It should return
694    its argument or a constant if the argument is known to be constant.  */
695
696 tree
697 get_addr_base_and_unit_offset_1 (tree exp, HOST_WIDE_INT *poffset,
698                                  tree (*valueize) (tree))
699 {
700   HOST_WIDE_INT byte_offset = 0;
701
702   /* Compute cumulative byte-offset for nested component-refs and array-refs,
703      and find the ultimate containing object.  */
704   while (1)
705     {
706       switch (TREE_CODE (exp))
707         {
708         case BIT_FIELD_REF:
709           {
710             HOST_WIDE_INT this_off = TREE_INT_CST_LOW (TREE_OPERAND (exp, 2));
711             if (this_off % BITS_PER_UNIT)
712               return NULL_TREE;
713             byte_offset += this_off / BITS_PER_UNIT;
714           }
715           break;
716
717         case COMPONENT_REF:
718           {
719             tree field = TREE_OPERAND (exp, 1);
720             tree this_offset = component_ref_field_offset (exp);
721             HOST_WIDE_INT hthis_offset;
722
723             if (!this_offset
724                 || TREE_CODE (this_offset) != INTEGER_CST
725                 || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
726                     % BITS_PER_UNIT))
727               return NULL_TREE;
728
729             hthis_offset = TREE_INT_CST_LOW (this_offset);
730             hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field))
731                              / BITS_PER_UNIT);
732             byte_offset += hthis_offset;
733           }
734           break;
735
736         case ARRAY_REF:
737         case ARRAY_RANGE_REF:
738           {
739             tree index = TREE_OPERAND (exp, 1);
740             tree low_bound, unit_size;
741
742             if (valueize
743                 && TREE_CODE (index) == SSA_NAME)
744               index = (*valueize) (index);
745
746             /* If the resulting bit-offset is constant, track it.  */
747             if (TREE_CODE (index) == INTEGER_CST
748                 && (low_bound = array_ref_low_bound (exp),
749                     TREE_CODE (low_bound) == INTEGER_CST)
750                 && (unit_size = array_ref_element_size (exp),
751                     TREE_CODE (unit_size) == INTEGER_CST))
752               {
753                 offset_int woffset
754                   = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound),
755                               TYPE_PRECISION (TREE_TYPE (index)));
756                 woffset *= wi::to_offset (unit_size);
757                 byte_offset += woffset.to_shwi ();
758               }
759             else
760               return NULL_TREE;
761           }
762           break;
763
764         case REALPART_EXPR:
765           break;
766
767         case IMAGPART_EXPR:
768           byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp)));
769           break;
770
771         case VIEW_CONVERT_EXPR:
772           break;
773
774         case MEM_REF:
775           {
776             tree base = TREE_OPERAND (exp, 0);
777             if (valueize
778                 && TREE_CODE (base) == SSA_NAME)
779               base = (*valueize) (base);
780
781             /* Hand back the decl for MEM[&decl, off].  */
782             if (TREE_CODE (base) == ADDR_EXPR)
783               {
784                 if (!integer_zerop (TREE_OPERAND (exp, 1)))
785                   {
786                     offset_int off = mem_ref_offset (exp);
787                     byte_offset += off.to_short_addr ();
788                   }
789                 exp = TREE_OPERAND (base, 0);
790               }
791             goto done;
792           }
793
794         case TARGET_MEM_REF:
795           {
796             tree base = TREE_OPERAND (exp, 0);
797             if (valueize
798                 && TREE_CODE (base) == SSA_NAME)
799               base = (*valueize) (base);
800
801             /* Hand back the decl for MEM[&decl, off].  */
802             if (TREE_CODE (base) == ADDR_EXPR)
803               {
804                 if (TMR_INDEX (exp) || TMR_INDEX2 (exp))
805                   return NULL_TREE;
806                 if (!integer_zerop (TMR_OFFSET (exp)))
807                   {
808                     offset_int off = mem_ref_offset (exp);
809                     byte_offset += off.to_short_addr ();
810                   }
811                 exp = TREE_OPERAND (base, 0);
812               }
813             goto done;
814           }
815
816         default:
817           goto done;
818         }
819
820       exp = TREE_OPERAND (exp, 0);
821     }
822 done:
823
824   *poffset = byte_offset;
825   return exp;
826 }
827
828 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
829    denotes the starting address of the memory access EXP.
830    Returns NULL_TREE if the offset is not constant or any component
831    is not BITS_PER_UNIT-aligned.  */
832
833 tree
834 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
835 {
836   return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
837 }
838
839 /* Returns true if STMT references an SSA_NAME that has
840    SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false.  */
841
842 bool
843 stmt_references_abnormal_ssa_name (gimple stmt)
844 {
845   ssa_op_iter oi;
846   use_operand_p use_p;
847
848   FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
849     {
850       if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
851         return true;
852     }
853
854   return false;
855 }
856
857 /* Pair of tree and a sorting index, for dump_enumerated_decls.  */
858 struct GTY(()) numbered_tree_d
859 {
860   tree t;
861   int num;
862 };
863 typedef struct numbered_tree_d numbered_tree;
864
865
866 /* Compare two declarations references by their DECL_UID / sequence number.
867    Called via qsort.  */
868
869 static int
870 compare_decls_by_uid (const void *pa, const void *pb)
871 {
872   const numbered_tree *nt_a = ((const numbered_tree *)pa);
873   const numbered_tree *nt_b = ((const numbered_tree *)pb);
874
875   if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t))
876     return  DECL_UID (nt_a->t) - DECL_UID (nt_b->t);
877   return nt_a->num - nt_b->num;
878 }
879
880 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls.  */
881 static tree
882 dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data)
883 {
884   struct walk_stmt_info *wi = (struct walk_stmt_info *) data;
885   vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info;
886   numbered_tree nt;
887
888   if (!DECL_P (*tp))
889     return NULL_TREE;
890   nt.t = *tp;
891   nt.num = list->length ();
892   list->safe_push (nt);
893   *walk_subtrees = 0;
894   return NULL_TREE;
895 }
896
897 /* Find all the declarations used by the current function, sort them by uid,
898    and emit the sorted list.  Each declaration is tagged with a sequence
899    number indicating when it was found during statement / tree walking,
900    so that TDF_NOUID comparisons of anonymous declarations are still
901    meaningful.  Where a declaration was encountered more than once, we
902    emit only the sequence number of the first encounter.
903    FILE is the dump file where to output the list and FLAGS is as in
904    print_generic_expr.  */
905 void
906 dump_enumerated_decls (FILE *file, int flags)
907 {
908   basic_block bb;
909   struct walk_stmt_info wi;
910   auto_vec<numbered_tree, 40> decl_list;
911
912   memset (&wi, '\0', sizeof (wi));
913   wi.info = (void *) &decl_list;
914   FOR_EACH_BB_FN (bb, cfun)
915     {
916       gimple_stmt_iterator gsi;
917
918       for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi))
919         if (!is_gimple_debug (gsi_stmt (gsi)))
920           walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi);
921     }
922   decl_list.qsort (compare_decls_by_uid);
923   if (decl_list.length ())
924     {
925       unsigned ix;
926       numbered_tree *ntp;
927       tree last = NULL_TREE;
928
929       fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n",
930                current_function_name ());
931       FOR_EACH_VEC_ELT (decl_list, ix, ntp)
932         {
933           if (ntp->t == last)
934             continue;
935           fprintf (file, "%d: ", ntp->num);
936           print_generic_decl (file, ntp->t, flags);
937           fprintf (file, "\n");
938           last = ntp->t;
939         }
940     }
941 }