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 double_int bit_offset = double_int_zero; 717 HOST_WIDE_INT hbit_offset; 718 bool seen_variable_array_ref = false; 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 switch (TREE_CODE (exp)) 750 { 751 case BIT_FIELD_REF: 752 bit_offset 753 = double_int_add (bit_offset, 754 tree_to_double_int (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 && TREE_CODE (this_offset) == INTEGER_CST) 763 { 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); 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. */ 778 if (seen_variable_array_ref && maxsize != -1) 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) 790 && host_integerp (ssize, 0) 791 && double_int_fits_in_shwi_p (doffset)) 792 maxsize += ((TREE_INT_CST_LOW (ssize) 793 - TREE_INT_CST_LOW (fsize)) 794 * BITS_PER_UNIT 795 - double_int_to_shwi (doffset)); 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. */ 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); 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 827 && (low_bound = array_ref_low_bound (exp), 828 TREE_CODE (low_bound) == INTEGER_CST) 829 && (unit_size = array_ref_element_size (exp), 830 TREE_CODE (unit_size) == INTEGER_CST)) 831 { 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); 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. */ 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); 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: 876 bit_offset 877 = double_int_add (bit_offset, uhwi_to_double_int (bitsize)); 878 break; 879 880 case VIEW_CONVERT_EXPR: 881 break; 882 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. */ 895 case MEM_REF: 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 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); 927 off = double_int_add (off, bit_offset); 928 if (double_int_fits_in_shwi_p (off)) 929 { 930 bit_offset = off; 931 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0); 932 } 933 } 934 } 935 goto done; 936 937 default: 938 goto done; 939 } 940 941 exp = TREE_OPERAND (exp, 0); 942 } 943 944 /* We need to deal with variable arrays ending structures. */ 945 if (seen_variable_array_ref 946 && maxsize != -1 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)))))) 952 maxsize = -1; 953 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 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)) 974 maxsize = TREE_INT_CST_LOW (DECL_SIZE (exp)) - hbit_offset; 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)) 982 maxsize = TREE_INT_CST_LOW (TYPE_SIZE (TREE_TYPE (exp))) - hbit_offset; 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. */ 988 *poffset = hbit_offset; 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 1000 tree 1001 get_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 1009 bool 1010 stmt_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 } 1023