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 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 "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. */ 50 struct 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. */ 64 static void collect_dfa_stats (struct dfa_stats_d *); 65 static 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 79 static unsigned int 80 find_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 102 struct 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 127 var_ann_t 128 create_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 145 void 146 renumber_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 170 void 171 renumber_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 195 tree 196 make_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 217 void 218 dump_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 238 DEBUG_FUNCTION void 239 debug_referenced_vars (void) 240 { 241 dump_referenced_vars (stderr); 242 } 243 244 245 /* Dump variable VAR and its may-aliases to FILE. */ 246 247 void 248 dump_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 299 DEBUG_FUNCTION void 300 debug_variable (tree var) 301 { 302 dump_variable (stderr, var); 303 } 304 305 306 /* Dump various DFA statistics to FILE. */ 307 308 void 309 dump_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 386 DEBUG_FUNCTION void 387 debug_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 396 static void 397 collect_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 444 static tree 445 find_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 469 void 470 find_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 495 tree 496 referenced_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 508 bool 509 referenced_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 534 tree 535 gimple_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 547 void 548 set_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 580 bool 581 add_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 607 void 608 remove_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 632 tree 633 get_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 655 void 656 mark_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 674 static tree 675 find_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 695 void 696 find_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 708 tree 709 get_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; 716 HOST_WIDE_INT bit_offset = 0; 717 bool seen_variable_array_ref = false; 718 tree base_type; 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 { 749 base_type = TREE_TYPE (exp); 750 751 switch (TREE_CODE (exp)) 752 { 753 case BIT_FIELD_REF: 754 bit_offset += TREE_INT_CST_LOW (TREE_OPERAND (exp, 2)); 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 762 if (this_offset 763 && TREE_CODE (this_offset) == INTEGER_CST 764 && host_integerp (this_offset, 0)) 765 { 766 HOST_WIDE_INT hthis_offset = TREE_INT_CST_LOW (this_offset); 767 hthis_offset *= BITS_PER_UNIT; 768 hthis_offset 769 += TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field)); 770 bit_offset += hthis_offset; 771 772 /* If we had seen a variable array ref already and we just 773 referenced the last field of a struct or a union member 774 then we have to adjust maxsize by the padding at the end 775 of our field. */ 776 if (seen_variable_array_ref 777 && maxsize != -1) 778 { 779 tree stype = TREE_TYPE (TREE_OPERAND (exp, 0)); 780 tree next = DECL_CHAIN (field); 781 while (next && TREE_CODE (next) != FIELD_DECL) 782 next = DECL_CHAIN (next); 783 if (!next 784 || TREE_CODE (stype) != RECORD_TYPE) 785 { 786 tree fsize = DECL_SIZE_UNIT (field); 787 tree ssize = TYPE_SIZE_UNIT (stype); 788 if (host_integerp (fsize, 0) 789 && host_integerp (ssize, 0)) 790 maxsize += ((TREE_INT_CST_LOW (ssize) 791 - TREE_INT_CST_LOW (fsize)) 792 * BITS_PER_UNIT - hthis_offset); 793 else 794 maxsize = -1; 795 } 796 } 797 } 798 else 799 { 800 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); 801 /* We need to adjust maxsize to the whole structure bitsize. 802 But we can subtract any constant offset seen so far, 803 because that would get us out of the structure otherwise. */ 804 if (maxsize != -1 && csize && host_integerp (csize, 1)) 805 maxsize = TREE_INT_CST_LOW (csize) - bit_offset; 806 else 807 maxsize = -1; 808 } 809 } 810 break; 811 812 case ARRAY_REF: 813 case ARRAY_RANGE_REF: 814 { 815 tree index = TREE_OPERAND (exp, 1); 816 tree low_bound, unit_size; 817 818 /* If the resulting bit-offset is constant, track it. */ 819 if (TREE_CODE (index) == INTEGER_CST 820 && host_integerp (index, 0) 821 && (low_bound = array_ref_low_bound (exp), 822 host_integerp (low_bound, 0)) 823 && (unit_size = array_ref_element_size (exp), 824 host_integerp (unit_size, 1))) 825 { 826 HOST_WIDE_INT hindex = TREE_INT_CST_LOW (index); 827 828 hindex -= TREE_INT_CST_LOW (low_bound); 829 hindex *= TREE_INT_CST_LOW (unit_size); 830 hindex *= BITS_PER_UNIT; 831 bit_offset += hindex; 832 833 /* An array ref with a constant index up in the structure 834 hierarchy will constrain the size of any variable array ref 835 lower in the access hierarchy. */ 836 seen_variable_array_ref = false; 837 } 838 else 839 { 840 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); 841 /* We need to adjust maxsize to the whole array bitsize. 842 But we can subtract any constant offset seen so far, 843 because that would get us outside of the array otherwise. */ 844 if (maxsize != -1 && asize && host_integerp (asize, 1)) 845 maxsize = TREE_INT_CST_LOW (asize) - bit_offset; 846 else 847 maxsize = -1; 848 849 /* Remember that we have seen an array ref with a variable 850 index. */ 851 seen_variable_array_ref = true; 852 } 853 } 854 break; 855 856 case REALPART_EXPR: 857 break; 858 859 case IMAGPART_EXPR: 860 bit_offset += bitsize; 861 break; 862 863 case VIEW_CONVERT_EXPR: 864 break; 865 866 case MEM_REF: 867 /* Hand back the decl for MEM[&decl, off]. */ 868 if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR) 869 { 870 if (integer_zerop (TREE_OPERAND (exp, 1))) 871 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0); 872 else 873 { 874 double_int off = mem_ref_offset (exp); 875 off = double_int_lshift (off, 876 BITS_PER_UNIT == 8 877 ? 3 : exact_log2 (BITS_PER_UNIT), 878 HOST_BITS_PER_DOUBLE_INT, true); 879 off = double_int_add (off, shwi_to_double_int (bit_offset)); 880 if (double_int_fits_in_shwi_p (off)) 881 { 882 bit_offset = double_int_to_shwi (off); 883 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0); 884 } 885 } 886 } 887 goto done; 888 889 case TARGET_MEM_REF: 890 /* Hand back the decl for MEM[&decl, off]. */ 891 if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR) 892 { 893 /* Via the variable index or index2 we can reach the 894 whole object. */ 895 if (TMR_INDEX (exp) || TMR_INDEX2 (exp)) 896 { 897 exp = TREE_OPERAND (TMR_BASE (exp), 0); 898 bit_offset = 0; 899 maxsize = -1; 900 goto done; 901 } 902 if (integer_zerop (TMR_OFFSET (exp))) 903 exp = TREE_OPERAND (TMR_BASE (exp), 0); 904 else 905 { 906 double_int off = mem_ref_offset (exp); 907 off = double_int_lshift (off, 908 BITS_PER_UNIT == 8 909 ? 3 : exact_log2 (BITS_PER_UNIT), 910 HOST_BITS_PER_DOUBLE_INT, true); 911 off = double_int_add (off, shwi_to_double_int (bit_offset)); 912 if (double_int_fits_in_shwi_p (off)) 913 { 914 bit_offset = double_int_to_shwi (off); 915 exp = TREE_OPERAND (TMR_BASE (exp), 0); 916 } 917 } 918 } 919 goto done; 920 921 default: 922 goto done; 923 } 924 925 exp = TREE_OPERAND (exp, 0); 926 } 927 done: 928 929 /* We need to deal with variable arrays ending structures such as 930 struct { int length; int a[1]; } x; x.a[d] 931 struct { struct { int a; int b; } a[1]; } x; x.a[d].a 932 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0] 933 struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d] 934 where we do not know maxsize for variable index accesses to 935 the array. The simplest way to conservatively deal with this 936 is to punt in the case that offset + maxsize reaches the 937 base type boundary. This needs to include possible trailing padding 938 that is there for alignment purposes. */ 939 940 if (seen_variable_array_ref 941 && maxsize != -1 942 && (!host_integerp (TYPE_SIZE (base_type), 1) 943 || (bit_offset + maxsize 944 == (signed) TREE_INT_CST_LOW (TYPE_SIZE (base_type))))) 945 maxsize = -1; 946 947 /* In case of a decl or constant base object we can do better. */ 948 949 if (DECL_P (exp)) 950 { 951 /* If maxsize is unknown adjust it according to the size of the 952 base decl. */ 953 if (maxsize == -1 954 && host_integerp (DECL_SIZE (exp), 1)) 955 maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - bit_offset; 956 } 957 else if (CONSTANT_CLASS_P (exp)) 958 { 959 /* If maxsize is unknown adjust it according to the size of the 960 base type constant. */ 961 if (maxsize == -1 962 && host_integerp (TYPE_SIZE (TREE_TYPE (exp)), 1)) 963 maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - bit_offset; 964 } 965 966 /* ??? Due to negative offsets in ARRAY_REF we can end up with 967 negative bit_offset here. We might want to store a zero offset 968 in this case. */ 969 *poffset = bit_offset; 970 *psize = bitsize; 971 *pmax_size = maxsize; 972 973 return exp; 974 } 975 976 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that 977 denotes the starting address of the memory access EXP. 978 Returns NULL_TREE if the offset is not constant or any component 979 is not BITS_PER_UNIT-aligned. */ 980 981 tree 982 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset) 983 { 984 return get_addr_base_and_unit_offset_1 (exp, poffset, NULL); 985 } 986 987 /* Returns true if STMT references an SSA_NAME that has 988 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */ 989 990 bool 991 stmt_references_abnormal_ssa_name (gimple stmt) 992 { 993 ssa_op_iter oi; 994 use_operand_p use_p; 995 996 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE) 997 { 998 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p))) 999 return true; 1000 } 1001 1002 return false; 1003 } 1004