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