Merge branch 'vendor/GCC47'
[dragonfly.git] / contrib / gcc-4.7 / gcc / tree-dfa.c
CommitLineData
e4b17023
JM
1/* Data flow functions for trees.
2 Copyright (C) 2001, 2002, 2003, 2004, 2005, 2007, 2008, 2009, 2010
3 Free Software Foundation, Inc.
4 Contributed by Diego Novillo <dnovillo@redhat.com>
5
6This file is part of GCC.
7
8GCC is free software; you can redistribute it and/or modify
9it under the terms of the GNU General Public License as published by
10the Free Software Foundation; either version 3, or (at your option)
11any later version.
12
13GCC is distributed in the hope that it will be useful,
14but WITHOUT ANY WARRANTY; without even the implied warranty of
15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16GNU General Public License for more details.
17
18You should have received a copy of the GNU General Public License
19along with GCC; see the file COPYING3. If not see
20<http://www.gnu.org/licenses/>. */
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 "tm_p.h"
30#include "basic-block.h"
31#include "output.h"
32#include "timevar.h"
33#include "ggc.h"
34#include "langhooks.h"
35#include "flags.h"
36#include "function.h"
37#include "tree-pretty-print.h"
38#include "tree-dump.h"
39#include "gimple.h"
40#include "tree-flow.h"
41#include "tree-inline.h"
42#include "tree-pass.h"
43#include "convert.h"
44#include "params.h"
45#include "cgraph.h"
46
47/* Build and maintain data flow information for trees. */
48
49/* Counters used to display DFA and SSA statistics. */
50struct dfa_stats_d
51{
52 long num_var_anns;
53 long num_defs;
54 long num_uses;
55 long num_phis;
56 long num_phi_args;
57 size_t max_num_phi_args;
58 long num_vdefs;
59 long num_vuses;
60};
61
62
63/* Local functions. */
64static void collect_dfa_stats (struct dfa_stats_d *);
65static tree find_vars_r (tree *, int *, void *);
66
67
68/*---------------------------------------------------------------------------
69 Dataflow analysis (DFA) routines
70---------------------------------------------------------------------------*/
71/* Find all the variables referenced in the function. This function
72 builds the global arrays REFERENCED_VARS and CALL_CLOBBERED_VARS.
73
74 Note that this function does not look for statement operands, it simply
75 determines what variables are referenced in the program and detects
76 various attributes for each variable used by alias analysis and the
77 optimizer. */
78
79static unsigned int
80find_referenced_vars (void)
81{
82 basic_block bb;
83 gimple_stmt_iterator si;
84
85 FOR_EACH_BB (bb)
86 {
87 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
88 {
89 gimple stmt = gsi_stmt (si);
90 if (is_gimple_debug (stmt))
91 continue;
92 find_referenced_vars_in (gsi_stmt (si));
93 }
94
95 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
96 find_referenced_vars_in (gsi_stmt (si));
97 }
98
99 return 0;
100}
101
102struct gimple_opt_pass pass_referenced_vars =
103{
104 {
105 GIMPLE_PASS,
106 "*referenced_vars", /* name */
107 NULL, /* gate */
108 find_referenced_vars, /* execute */
109 NULL, /* sub */
110 NULL, /* next */
111 0, /* static_pass_number */
112 TV_FIND_REFERENCED_VARS, /* tv_id */
113 PROP_gimple_leh | PROP_cfg, /* properties_required */
114 PROP_referenced_vars, /* properties_provided */
115 0, /* properties_destroyed */
116 0, /* todo_flags_start */
117 0 /* todo_flags_finish */
118 }
119};
120
121
122/*---------------------------------------------------------------------------
123 Manage annotations
124---------------------------------------------------------------------------*/
125/* Create a new annotation for a _DECL node T. */
126
127var_ann_t
128create_var_ann (tree t)
129{
130 var_ann_t ann;
131
132 gcc_assert (t);
133 gcc_assert (TREE_CODE (t) == VAR_DECL
134 || TREE_CODE (t) == PARM_DECL
135 || TREE_CODE (t) == RESULT_DECL);
136
137 ann = ggc_alloc_cleared_var_ann_d ();
138 *DECL_VAR_ANN_PTR (t) = ann;
139
140 return ann;
141}
142
143/* Renumber all of the gimple stmt uids. */
144
145void
146renumber_gimple_stmt_uids (void)
147{
148 basic_block bb;
149
150 set_gimple_stmt_max_uid (cfun, 0);
151 FOR_ALL_BB (bb)
152 {
153 gimple_stmt_iterator bsi;
154 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
155 {
156 gimple stmt = gsi_stmt (bsi);
157 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
158 }
159 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
160 {
161 gimple stmt = gsi_stmt (bsi);
162 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
163 }
164 }
165}
166
167/* Like renumber_gimple_stmt_uids, but only do work on the basic blocks
168 in BLOCKS, of which there are N_BLOCKS. Also renumbers PHIs. */
169
170void
171renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks)
172{
173 int i;
174
175 set_gimple_stmt_max_uid (cfun, 0);
176 for (i = 0; i < n_blocks; i++)
177 {
178 basic_block bb = blocks[i];
179 gimple_stmt_iterator bsi;
180 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
181 {
182 gimple stmt = gsi_stmt (bsi);
183 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
184 }
185 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
186 {
187 gimple stmt = gsi_stmt (bsi);
188 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun));
189 }
190 }
191}
192
193/* Build a temporary. Make sure and register it to be renamed. */
194
195tree
196make_rename_temp (tree type, const char *prefix)
197{
198 tree t = create_tmp_reg (type, prefix);
199
200 if (gimple_referenced_vars (cfun))
201 {
202 add_referenced_var (t);
203 mark_sym_for_renaming (t);
204 }
205
206 return t;
207}
208
209
210
211/*---------------------------------------------------------------------------
212 Debugging functions
213---------------------------------------------------------------------------*/
214/* Dump the list of all the referenced variables in the current function to
215 FILE. */
216
217void
218dump_referenced_vars (FILE *file)
219{
220 tree var;
221 referenced_var_iterator rvi;
222
223 fprintf (file, "\nReferenced variables in %s: %u\n\n",
224 get_name (current_function_decl), (unsigned) num_referenced_vars);
225
226 FOR_EACH_REFERENCED_VAR (cfun, var, rvi)
227 {
228 fprintf (file, "Variable: ");
229 dump_variable (file, var);
230 }
231
232 fprintf (file, "\n");
233}
234
235
236/* Dump the list of all the referenced variables to stderr. */
237
238DEBUG_FUNCTION void
239debug_referenced_vars (void)
240{
241 dump_referenced_vars (stderr);
242}
243
244
245/* Dump variable VAR and its may-aliases to FILE. */
246
247void
248dump_variable (FILE *file, tree var)
249{
250 if (TREE_CODE (var) == SSA_NAME)
251 {
252 if (POINTER_TYPE_P (TREE_TYPE (var)))
253 dump_points_to_info_for (file, var);
254 var = SSA_NAME_VAR (var);
255 }
256
257 if (var == NULL_TREE)
258 {
259 fprintf (file, "<nil>");
260 return;
261 }
262
263 print_generic_expr (file, var, dump_flags);
264
265 fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var));
266 if (DECL_PT_UID (var) != DECL_UID (var))
267 fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var));
268
269 fprintf (file, ", ");
270 print_generic_expr (file, TREE_TYPE (var), dump_flags);
271
272 if (TREE_ADDRESSABLE (var))
273 fprintf (file, ", is addressable");
274
275 if (is_global_var (var))
276 fprintf (file, ", is global");
277
278 if (TREE_THIS_VOLATILE (var))
279 fprintf (file, ", is volatile");
280
281 if (cfun && gimple_default_def (cfun, var))
282 {
283 fprintf (file, ", default def: ");
284 print_generic_expr (file, gimple_default_def (cfun, var), dump_flags);
285 }
286
287 if (DECL_INITIAL (var))
288 {
289 fprintf (file, ", initial: ");
290 print_generic_expr (file, DECL_INITIAL (var), dump_flags);
291 }
292
293 fprintf (file, "\n");
294}
295
296
297/* Dump variable VAR and its may-aliases to stderr. */
298
299DEBUG_FUNCTION void
300debug_variable (tree var)
301{
302 dump_variable (stderr, var);
303}
304
305
306/* Dump various DFA statistics to FILE. */
307
308void
309dump_dfa_stats (FILE *file)
310{
311 struct dfa_stats_d dfa_stats;
312
313 unsigned long size, total = 0;
314 const char * const fmt_str = "%-30s%-13s%12s\n";
315 const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n";
316 const char * const fmt_str_3 = "%-43s%11lu%c\n";
317 const char *funcname
318 = lang_hooks.decl_printable_name (current_function_decl, 2);
319
320 collect_dfa_stats (&dfa_stats);
321
322 fprintf (file, "\nDFA Statistics for %s\n\n", funcname);
323
324 fprintf (file, "---------------------------------------------------------\n");
325 fprintf (file, fmt_str, "", " Number of ", "Memory");
326 fprintf (file, fmt_str, "", " instances ", "used ");
327 fprintf (file, "---------------------------------------------------------\n");
328
329 size = num_referenced_vars * sizeof (tree);
330 total += size;
331 fprintf (file, fmt_str_1, "Referenced variables", (unsigned long)num_referenced_vars,
332 SCALE (size), LABEL (size));
333
334 size = dfa_stats.num_var_anns * sizeof (struct var_ann_d);
335 total += size;
336 fprintf (file, fmt_str_1, "Variables annotated", dfa_stats.num_var_anns,
337 SCALE (size), LABEL (size));
338
339 size = dfa_stats.num_uses * sizeof (tree *);
340 total += size;
341 fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses,
342 SCALE (size), LABEL (size));
343
344 size = dfa_stats.num_defs * sizeof (tree *);
345 total += size;
346 fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs,
347 SCALE (size), LABEL (size));
348
349 size = dfa_stats.num_vuses * sizeof (tree *);
350 total += size;
351 fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses,
352 SCALE (size), LABEL (size));
353
354 size = dfa_stats.num_vdefs * sizeof (tree *);
355 total += size;
356 fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs,
357 SCALE (size), LABEL (size));
358
359 size = dfa_stats.num_phis * sizeof (struct gimple_statement_phi);
360 total += size;
361 fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis,
362 SCALE (size), LABEL (size));
363
364 size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d);
365 total += size;
366 fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args,
367 SCALE (size), LABEL (size));
368
369 fprintf (file, "---------------------------------------------------------\n");
370 fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total),
371 LABEL (total));
372 fprintf (file, "---------------------------------------------------------\n");
373 fprintf (file, "\n");
374
375 if (dfa_stats.num_phis)
376 fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n",
377 (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis,
378 (long) dfa_stats.max_num_phi_args);
379
380 fprintf (file, "\n");
381}
382
383
384/* Dump DFA statistics on stderr. */
385
386DEBUG_FUNCTION void
387debug_dfa_stats (void)
388{
389 dump_dfa_stats (stderr);
390}
391
392
393/* Collect DFA statistics and store them in the structure pointed to by
394 DFA_STATS_P. */
395
396static void
397collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED)
398{
399 basic_block bb;
400 referenced_var_iterator vi;
401 tree var;
402
403 gcc_assert (dfa_stats_p);
404
405 memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d));
406
407 /* Count all the variable annotations. */
408 FOR_EACH_REFERENCED_VAR (cfun, var, vi)
409 if (var_ann (var))
410 dfa_stats_p->num_var_anns++;
411
412 /* Walk all the statements in the function counting references. */
413 FOR_EACH_BB (bb)
414 {
415 gimple_stmt_iterator si;
416
417 for (si = gsi_start_phis (bb); !gsi_end_p (si); gsi_next (&si))
418 {
419 gimple phi = gsi_stmt (si);
420 dfa_stats_p->num_phis++;
421 dfa_stats_p->num_phi_args += gimple_phi_num_args (phi);
422 if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args)
423 dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi);
424 }
425
426 for (si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
427 {
428 gimple stmt = gsi_stmt (si);
429 dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF);
430 dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE);
431 dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0;
432 dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0;
433 }
434 }
435}
436
437
438/*---------------------------------------------------------------------------
439 Miscellaneous helpers
440---------------------------------------------------------------------------*/
441/* Callback for walk_tree. Used to collect variables referenced in
442 the function. */
443
444static tree
445find_vars_r (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED)
446{
447 /* If we are reading the lto info back in, we need to rescan the
448 referenced vars. */
449 if (TREE_CODE (*tp) == SSA_NAME)
450 add_referenced_var (SSA_NAME_VAR (*tp));
451
452 /* If T is a regular variable that the optimizers are interested
453 in, add it to the list of variables. */
454 else if (SSA_VAR_P (*tp))
455 add_referenced_var (*tp);
456
457 /* Type, _DECL and constant nodes have no interesting children.
458 Ignore them. */
459 else if (IS_TYPE_OR_DECL_P (*tp) || CONSTANT_CLASS_P (*tp))
460 *walk_subtrees = 0;
461
462 return NULL_TREE;
463}
464
465/* Find referenced variables in STMT. In contrast with
466 find_new_referenced_vars, this function will not mark newly found
467 variables for renaming. */
468
469void
470find_referenced_vars_in (gimple stmt)
471{
472 size_t i;
473
474 if (gimple_code (stmt) != GIMPLE_PHI)
475 {
476 for (i = 0; i < gimple_num_ops (stmt); i++)
477 walk_tree (gimple_op_ptr (stmt, i), find_vars_r, NULL, NULL);
478 }
479 else
480 {
481 walk_tree (gimple_phi_result_ptr (stmt), find_vars_r, NULL, NULL);
482
483 for (i = 0; i < gimple_phi_num_args (stmt); i++)
484 {
485 tree arg = gimple_phi_arg_def (stmt, i);
486 walk_tree (&arg, find_vars_r, NULL, NULL);
487 }
488 }
489}
490
491
492/* Lookup UID in the referenced_vars hashtable and return the associated
493 variable. */
494
495tree
496referenced_var_lookup (struct function *fn, unsigned int uid)
497{
498 tree h;
499 struct tree_decl_minimal in;
500 in.uid = uid;
501 h = (tree) htab_find_with_hash (gimple_referenced_vars (fn), &in, uid);
502 return h;
503}
504
505/* Check if TO is in the referenced_vars hash table and insert it if not.
506 Return true if it required insertion. */
507
508bool
509referenced_var_check_and_insert (tree to)
510{
511 tree h, *loc;
512 struct tree_decl_minimal in;
513 unsigned int uid = DECL_UID (to);
514
515 in.uid = uid;
516 h = (tree) htab_find_with_hash (gimple_referenced_vars (cfun), &in, uid);
517 if (h)
518 {
519 /* DECL_UID has already been entered in the table. Verify that it is
520 the same entry as TO. See PR 27793. */
521 gcc_assert (h == to);
522 return false;
523 }
524
525 loc = (tree *) htab_find_slot_with_hash (gimple_referenced_vars (cfun),
526 &in, uid, INSERT);
527 *loc = to;
528 return true;
529}
530
531/* Lookup VAR UID in the default_defs hashtable and return the associated
532 variable. */
533
534tree
535gimple_default_def (struct function *fn, tree var)
536{
537 struct tree_decl_minimal ind;
538 struct tree_ssa_name in;
539 gcc_assert (SSA_VAR_P (var));
540 in.var = (tree)&ind;
541 ind.uid = DECL_UID (var);
542 return (tree) htab_find_with_hash (DEFAULT_DEFS (fn), &in, DECL_UID (var));
543}
544
545/* Insert the pair VAR's UID, DEF into the default_defs hashtable. */
546
547void
548set_default_def (tree var, tree def)
549{
550 struct tree_decl_minimal ind;
551 struct tree_ssa_name in;
552 void **loc;
553
554 gcc_assert (SSA_VAR_P (var));
555 in.var = (tree)&ind;
556 ind.uid = DECL_UID (var);
557 if (!def)
558 {
559 loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
560 DECL_UID (var), INSERT);
561 gcc_assert (*loc);
562 htab_remove_elt (DEFAULT_DEFS (cfun), *loc);
563 return;
564 }
565 gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var);
566 loc = htab_find_slot_with_hash (DEFAULT_DEFS (cfun), &in,
567 DECL_UID (var), INSERT);
568
569 /* Default definition might be changed by tail call optimization. */
570 if (*loc)
571 SSA_NAME_IS_DEFAULT_DEF (*(tree *) loc) = false;
572 *(tree *) loc = def;
573
574 /* Mark DEF as the default definition for VAR. */
575 SSA_NAME_IS_DEFAULT_DEF (def) = true;
576}
577
578/* Add VAR to the list of referenced variables if it isn't already there. */
579
580bool
581add_referenced_var (tree var)
582{
583 gcc_assert (DECL_P (var));
584 if (!*DECL_VAR_ANN_PTR (var))
585 create_var_ann (var);
586
587 /* Insert VAR into the referenced_vars hash table if it isn't present. */
588 if (referenced_var_check_and_insert (var))
589 {
590 /* Scan DECL_INITIAL for pointer variables as they may contain
591 address arithmetic referencing the address of other
592 variables. As we are only interested in directly referenced
593 globals or referenced locals restrict this to initializers
594 than can refer to local variables. */
595 if (DECL_INITIAL (var)
596 && DECL_CONTEXT (var) == current_function_decl)
597 walk_tree (&DECL_INITIAL (var), find_vars_r, NULL, 0);
598
599 return true;
600 }
601
602 return false;
603}
604
605/* Remove VAR from the list. */
606
607void
608remove_referenced_var (tree var)
609{
610 var_ann_t v_ann;
611 struct tree_decl_minimal in;
612 void **loc;
613 unsigned int uid = DECL_UID (var);
614
615 /* Preserve var_anns of globals. */
616 if (!is_global_var (var)
617 && (v_ann = var_ann (var)))
618 {
619 ggc_free (v_ann);
620 *DECL_VAR_ANN_PTR (var) = NULL;
621 }
622 gcc_assert (DECL_P (var));
623 in.uid = uid;
624 loc = htab_find_slot_with_hash (gimple_referenced_vars (cfun), &in, uid,
625 NO_INSERT);
626 htab_clear_slot (gimple_referenced_vars (cfun), loc);
627}
628
629
630/* Return the virtual variable associated to the non-scalar variable VAR. */
631
632tree
633get_virtual_var (tree var)
634{
635 STRIP_NOPS (var);
636
637 if (TREE_CODE (var) == SSA_NAME)
638 var = SSA_NAME_VAR (var);
639
640 while (TREE_CODE (var) == REALPART_EXPR || TREE_CODE (var) == IMAGPART_EXPR
641 || handled_component_p (var))
642 var = TREE_OPERAND (var, 0);
643
644 /* Treating GIMPLE registers as virtual variables makes no sense.
645 Also complain if we couldn't extract a _DECL out of the original
646 expression. */
647 gcc_assert (SSA_VAR_P (var));
648 gcc_assert (!is_gimple_reg (var));
649
650 return var;
651}
652
653/* Mark all the naked symbols in STMT for SSA renaming. */
654
655void
656mark_symbols_for_renaming (gimple stmt)
657{
658 tree op;
659 ssa_op_iter iter;
660
661 update_stmt (stmt);
662
663 /* Mark all the operands for renaming. */
664 FOR_EACH_SSA_TREE_OPERAND (op, stmt, iter, SSA_OP_ALL_OPERANDS)
665 if (DECL_P (op))
666 mark_sym_for_renaming (op);
667}
668
669
670/* Find all variables within the gimplified statement that were not
671 previously visible to the function and add them to the referenced
672 variables list. */
673
674static tree
675find_new_referenced_vars_1 (tree *tp, int *walk_subtrees,
676 void *data ATTRIBUTE_UNUSED)
677{
678 tree t = *tp;
679
680 if (TREE_CODE (t) == VAR_DECL && !var_ann (t))
681 {
682 add_referenced_var (t);
683 mark_sym_for_renaming (t);
684 }
685
686 if (IS_TYPE_OR_DECL_P (t))
687 *walk_subtrees = 0;
688
689 return NULL;
690}
691
692
693/* Find any new referenced variables in STMT. */
694
695void
696find_new_referenced_vars (gimple stmt)
697{
698 walk_gimple_op (stmt, find_new_referenced_vars_1, NULL);
699}
700
701
702/* If EXP is a handled component reference for a structure, return the
703 base variable. The access range is delimited by bit positions *POFFSET and
704 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either
705 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE
706 and *PMAX_SIZE are equal, the access is non-variable. */
707
708tree
709get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset,
710 HOST_WIDE_INT *psize,
711 HOST_WIDE_INT *pmax_size)
712{
713 HOST_WIDE_INT bitsize = -1;
714 HOST_WIDE_INT maxsize = -1;
715 tree size_tree = NULL_TREE;
95d28233
JM
716 double_int bit_offset = double_int_zero;
717 HOST_WIDE_INT hbit_offset;
e4b17023 718 bool seen_variable_array_ref = false;
e4b17023
JM
719
720 /* First get the final access size from just the outermost expression. */
721 if (TREE_CODE (exp) == COMPONENT_REF)
722 size_tree = DECL_SIZE (TREE_OPERAND (exp, 1));
723 else if (TREE_CODE (exp) == BIT_FIELD_REF)
724 size_tree = TREE_OPERAND (exp, 1);
725 else if (!VOID_TYPE_P (TREE_TYPE (exp)))
726 {
727 enum machine_mode mode = TYPE_MODE (TREE_TYPE (exp));
728 if (mode == BLKmode)
729 size_tree = TYPE_SIZE (TREE_TYPE (exp));
730 else
731 bitsize = GET_MODE_BITSIZE (mode);
732 }
733 if (size_tree != NULL_TREE)
734 {
735 if (! host_integerp (size_tree, 1))
736 bitsize = -1;
737 else
738 bitsize = TREE_INT_CST_LOW (size_tree);
739 }
740
741 /* Initially, maxsize is the same as the accessed element size.
742 In the following it will only grow (or become -1). */
743 maxsize = bitsize;
744
745 /* Compute cumulative bit-offset for nested component-refs and array-refs,
746 and find the ultimate containing object. */
747 while (1)
748 {
e4b17023
JM
749 switch (TREE_CODE (exp))
750 {
751 case BIT_FIELD_REF:
95d28233
JM
752 bit_offset
753 = double_int_add (bit_offset,
754 tree_to_double_int (TREE_OPERAND (exp, 2)));
e4b17023
JM
755 break;
756
757 case COMPONENT_REF:
758 {
759 tree field = TREE_OPERAND (exp, 1);
760 tree this_offset = component_ref_field_offset (exp);
761
95d28233 762 if (this_offset && TREE_CODE (this_offset) == INTEGER_CST)
e4b17023 763 {
95d28233
JM
764 double_int doffset = tree_to_double_int (this_offset);
765 doffset = double_int_lshift (doffset,
766 BITS_PER_UNIT == 8
767 ? 3 : exact_log2 (BITS_PER_UNIT),
768 HOST_BITS_PER_DOUBLE_INT, true);
769 doffset = double_int_add (doffset,
770 tree_to_double_int
771 (DECL_FIELD_BIT_OFFSET (field)));
772 bit_offset = double_int_add (bit_offset, doffset);
e4b17023
JM
773
774 /* If we had seen a variable array ref already and we just
775 referenced the last field of a struct or a union member
776 then we have to adjust maxsize by the padding at the end
777 of our field. */
95d28233 778 if (seen_variable_array_ref && maxsize != -1)
e4b17023
JM
779 {
780 tree stype = TREE_TYPE (TREE_OPERAND (exp, 0));
781 tree next = DECL_CHAIN (field);
782 while (next && TREE_CODE (next) != FIELD_DECL)
783 next = DECL_CHAIN (next);
784 if (!next
785 || TREE_CODE (stype) != RECORD_TYPE)
786 {
787 tree fsize = DECL_SIZE_UNIT (field);
788 tree ssize = TYPE_SIZE_UNIT (stype);
789 if (host_integerp (fsize, 0)
95d28233
JM
790 && host_integerp (ssize, 0)
791 && double_int_fits_in_shwi_p (doffset))
e4b17023
JM
792 maxsize += ((TREE_INT_CST_LOW (ssize)
793 - TREE_INT_CST_LOW (fsize))
95d28233
JM
794 * BITS_PER_UNIT
795 - double_int_to_shwi (doffset));
e4b17023
JM
796 else
797 maxsize = -1;
798 }
799 }
800 }
801 else
802 {
803 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
804 /* We need to adjust maxsize to the whole structure bitsize.
805 But we can subtract any constant offset seen so far,
806 because that would get us out of the structure otherwise. */
95d28233
JM
807 if (maxsize != -1
808 && csize
809 && host_integerp (csize, 1)
810 && double_int_fits_in_shwi_p (bit_offset))
811 maxsize = TREE_INT_CST_LOW (csize)
812 - double_int_to_shwi (bit_offset);
e4b17023
JM
813 else
814 maxsize = -1;
815 }
816 }
817 break;
818
819 case ARRAY_REF:
820 case ARRAY_RANGE_REF:
821 {
822 tree index = TREE_OPERAND (exp, 1);
823 tree low_bound, unit_size;
824
825 /* If the resulting bit-offset is constant, track it. */
826 if (TREE_CODE (index) == INTEGER_CST
e4b17023 827 && (low_bound = array_ref_low_bound (exp),
95d28233 828 TREE_CODE (low_bound) == INTEGER_CST)
e4b17023 829 && (unit_size = array_ref_element_size (exp),
95d28233 830 TREE_CODE (unit_size) == INTEGER_CST))
e4b17023 831 {
95d28233
JM
832 double_int doffset
833 = double_int_sext
834 (double_int_sub (TREE_INT_CST (index),
835 TREE_INT_CST (low_bound)),
836 TYPE_PRECISION (TREE_TYPE (index)));
837 doffset = double_int_mul (doffset,
838 tree_to_double_int (unit_size));
839 doffset = double_int_lshift (doffset,
840 BITS_PER_UNIT == 8
841 ? 3 : exact_log2 (BITS_PER_UNIT),
842 HOST_BITS_PER_DOUBLE_INT, true);
843 bit_offset = double_int_add (bit_offset, doffset);
e4b17023
JM
844
845 /* An array ref with a constant index up in the structure
846 hierarchy will constrain the size of any variable array ref
847 lower in the access hierarchy. */
848 seen_variable_array_ref = false;
849 }
850 else
851 {
852 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0)));
853 /* We need to adjust maxsize to the whole array bitsize.
854 But we can subtract any constant offset seen so far,
855 because that would get us outside of the array otherwise. */
95d28233
JM
856 if (maxsize != -1
857 && asize
858 && host_integerp (asize, 1)
859 && double_int_fits_in_shwi_p (bit_offset))
860 maxsize = TREE_INT_CST_LOW (asize)
861 - double_int_to_shwi (bit_offset);
e4b17023
JM
862 else
863 maxsize = -1;
864
865 /* Remember that we have seen an array ref with a variable
866 index. */
867 seen_variable_array_ref = true;
868 }
869 }
870 break;
871
872 case REALPART_EXPR:
873 break;
874
875 case IMAGPART_EXPR:
95d28233
JM
876 bit_offset
877 = double_int_add (bit_offset, uhwi_to_double_int (bitsize));
e4b17023
JM
878 break;
879
880 case VIEW_CONVERT_EXPR:
881 break;
882
95d28233
JM
883 case TARGET_MEM_REF:
884 /* Via the variable index or index2 we can reach the
885 whole object. Still hand back the decl here. */
886 if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR
887 && (TMR_INDEX (exp) || TMR_INDEX2 (exp)))
888 {
889 exp = TREE_OPERAND (TMR_BASE (exp), 0);
890 bit_offset = double_int_zero;
891 maxsize = -1;
892 goto done;
893 }
894 /* Fallthru. */
e4b17023 895 case MEM_REF:
95d28233
JM
896 /* We need to deal with variable arrays ending structures such as
897 struct { int length; int a[1]; } x; x.a[d]
898 struct { struct { int a; int b; } a[1]; } x; x.a[d].a
899 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0]
900 struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d]
901 where we do not know maxsize for variable index accesses to
902 the array. The simplest way to conservatively deal with this
903 is to punt in the case that offset + maxsize reaches the
904 base type boundary. This needs to include possible trailing
905 padding that is there for alignment purposes. */
906 if (seen_variable_array_ref
907 && maxsize != -1
908 && (!double_int_fits_in_shwi_p (bit_offset)
909 || !host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
910 || (double_int_to_shwi (bit_offset) + maxsize
911 == (HOST_WIDE_INT) TREE_INT_CST_LOW
912 (TYPE_SIZE (TREE_TYPE (exp))))))
913 maxsize = -1;
914
e4b17023
JM
915 /* Hand back the decl for MEM[&decl, off]. */
916 if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR)
917 {
918 if (integer_zerop (TREE_OPERAND (exp, 1)))
919 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
920 else
921 {
922 double_int off = mem_ref_offset (exp);
923 off = double_int_lshift (off,
924 BITS_PER_UNIT == 8
925 ? 3 : exact_log2 (BITS_PER_UNIT),
926 HOST_BITS_PER_DOUBLE_INT, true);
95d28233 927 off = double_int_add (off, bit_offset);
e4b17023
JM
928 if (double_int_fits_in_shwi_p (off))
929 {
95d28233 930 bit_offset = off;
e4b17023
JM
931 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0);
932 }
933 }
934 }
935 goto done;
936
e4b17023
JM
937 default:
938 goto done;
939 }
940
941 exp = TREE_OPERAND (exp, 0);
942 }
e4b17023 943
95d28233 944 /* We need to deal with variable arrays ending structures. */
e4b17023
JM
945 if (seen_variable_array_ref
946 && maxsize != -1
95d28233
JM
947 && (!double_int_fits_in_shwi_p (bit_offset)
948 || !host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)
949 || (double_int_to_shwi (bit_offset) + maxsize
950 == (HOST_WIDE_INT)
951 TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))))))
e4b17023
JM
952 maxsize = -1;
953
95d28233
JM
954 done:
955 if (!double_int_fits_in_shwi_p (bit_offset))
956 {
957 *poffset = 0;
958 *psize = bitsize;
959 *pmax_size = -1;
960
961 return exp;
962 }
963
964 hbit_offset = double_int_to_shwi (bit_offset);
965
e4b17023
JM
966 /* In case of a decl or constant base object we can do better. */
967
968 if (DECL_P (exp))
969 {
970 /* If maxsize is unknown adjust it according to the size of the
971 base decl. */
972 if (maxsize == -1
973 && host_integerp (DECL_SIZE (exp), 1))
95d28233 974 maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - hbit_offset;
e4b17023
JM
975 }
976 else if (CONSTANT_CLASS_P (exp))
977 {
978 /* If maxsize is unknown adjust it according to the size of the
979 base type constant. */
980 if (maxsize == -1
981 && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1))
95d28233 982 maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - hbit_offset;
e4b17023
JM
983 }
984
985 /* ??? Due to negative offsets in ARRAY_REF we can end up with
986 negative bit_offset here. We might want to store a zero offset
987 in this case. */
95d28233 988 *poffset = hbit_offset;
e4b17023
JM
989 *psize = bitsize;
990 *pmax_size = maxsize;
991
992 return exp;
993}
994
995/* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that
996 denotes the starting address of the memory access EXP.
997 Returns NULL_TREE if the offset is not constant or any component
998 is not BITS_PER_UNIT-aligned. */
999
1000tree
1001get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset)
1002{
1003 return get_addr_base_and_unit_offset_1 (exp, poffset, NULL);
1004}
1005
1006/* Returns true if STMT references an SSA_NAME that has
1007 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */
1008
1009bool
1010stmt_references_abnormal_ssa_name (gimple stmt)
1011{
1012 ssa_op_iter oi;
1013 use_operand_p use_p;
1014
1015 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE)
1016 {
1017 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p)))
1018 return true;
1019 }
1020
1021 return false;
1022}