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