1 /* Data flow functions for trees. 2 Copyright (C) 2001-2015 Free Software Foundation, Inc. 3 Contributed by Diego Novillo <dnovillo@redhat.com> 4 5 This file is part of GCC. 6 7 GCC is free software; you can redistribute it and/or modify 8 it under the terms of the GNU General Public License as published by 9 the Free Software Foundation; either version 3, or (at your option) 10 any later version. 11 12 GCC is distributed in the hope that it will be useful, 13 but WITHOUT ANY WARRANTY; without even the implied warranty of 14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15 GNU General Public License for more details. 16 17 You should have received a copy of the GNU General Public License 18 along with GCC; see the file COPYING3. If not see 19 <http://www.gnu.org/licenses/>. */ 20 21 #include "config.h" 22 #include "system.h" 23 #include "coretypes.h" 24 #include "tm.h" 25 #include "hashtab.h" 26 #include "hash-set.h" 27 #include "machmode.h" 28 #include "vec.h" 29 #include "double-int.h" 30 #include "input.h" 31 #include "alias.h" 32 #include "symtab.h" 33 #include "wide-int.h" 34 #include "inchash.h" 35 #include "tree.h" 36 #include "fold-const.h" 37 #include "stor-layout.h" 38 #include "tm_p.h" 39 #include "predict.h" 40 #include "hard-reg-set.h" 41 #include "function.h" 42 #include "dominance.h" 43 #include "cfg.h" 44 #include "basic-block.h" 45 #include "langhooks.h" 46 #include "flags.h" 47 #include "tree-pretty-print.h" 48 #include "tree-ssa-alias.h" 49 #include "internal-fn.h" 50 #include "gimple-expr.h" 51 #include "is-a.h" 52 #include "gimple.h" 53 #include "gimple-iterator.h" 54 #include "gimple-walk.h" 55 #include "gimple-ssa.h" 56 #include "tree-phinodes.h" 57 #include "ssa-iterators.h" 58 #include "stringpool.h" 59 #include "tree-ssanames.h" 60 #include "rtl.h" 61 #include "statistics.h" 62 #include "real.h" 63 #include "fixed-value.h" 64 #include "insn-config.h" 65 #include "expmed.h" 66 #include "dojump.h" 67 #include "explow.h" 68 #include "calls.h" 69 #include "emit-rtl.h" 70 #include "varasm.h" 71 #include "stmt.h" 72 #include "expr.h" 73 #include "tree-dfa.h" 74 #include "tree-inline.h" 75 #include "tree-pass.h" 76 #include "params.h" 77 78 /* Build and maintain data flow information for trees. */ 79 80 /* Counters used to display DFA and SSA statistics. */ 81 struct dfa_stats_d 82 { 83 long num_defs; 84 long num_uses; 85 long num_phis; 86 long num_phi_args; 87 size_t max_num_phi_args; 88 long num_vdefs; 89 long num_vuses; 90 }; 91 92 93 /* Local functions. */ 94 static void collect_dfa_stats (struct dfa_stats_d *); 95 96 97 /*--------------------------------------------------------------------------- 98 Dataflow analysis (DFA) routines 99 ---------------------------------------------------------------------------*/ 100 101 /* Renumber all of the gimple stmt uids. */ 102 103 void 104 renumber_gimple_stmt_uids (void) 105 { 106 basic_block bb; 107 108 set_gimple_stmt_max_uid (cfun, 0); 109 FOR_ALL_BB_FN (bb, cfun) 110 { 111 gimple_stmt_iterator bsi; 112 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 113 { 114 gimple stmt = gsi_stmt (bsi); 115 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); 116 } 117 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 118 { 119 gimple stmt = gsi_stmt (bsi); 120 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); 121 } 122 } 123 } 124 125 /* Like renumber_gimple_stmt_uids, but only do work on the basic blocks 126 in BLOCKS, of which there are N_BLOCKS. Also renumbers PHIs. */ 127 128 void 129 renumber_gimple_stmt_uids_in_blocks (basic_block *blocks, int n_blocks) 130 { 131 int i; 132 133 set_gimple_stmt_max_uid (cfun, 0); 134 for (i = 0; i < n_blocks; i++) 135 { 136 basic_block bb = blocks[i]; 137 gimple_stmt_iterator bsi; 138 for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 139 { 140 gimple stmt = gsi_stmt (bsi); 141 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); 142 } 143 for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi)) 144 { 145 gimple stmt = gsi_stmt (bsi); 146 gimple_set_uid (stmt, inc_gimple_stmt_max_uid (cfun)); 147 } 148 } 149 } 150 151 152 153 /*--------------------------------------------------------------------------- 154 Debugging functions 155 ---------------------------------------------------------------------------*/ 156 157 /* Dump variable VAR and its may-aliases to FILE. */ 158 159 void 160 dump_variable (FILE *file, tree var) 161 { 162 if (TREE_CODE (var) == SSA_NAME) 163 { 164 if (POINTER_TYPE_P (TREE_TYPE (var))) 165 dump_points_to_info_for (file, var); 166 var = SSA_NAME_VAR (var); 167 } 168 169 if (var == NULL_TREE) 170 { 171 fprintf (file, "<nil>"); 172 return; 173 } 174 175 print_generic_expr (file, var, dump_flags); 176 177 fprintf (file, ", UID D.%u", (unsigned) DECL_UID (var)); 178 if (DECL_PT_UID (var) != DECL_UID (var)) 179 fprintf (file, ", PT-UID D.%u", (unsigned) DECL_PT_UID (var)); 180 181 fprintf (file, ", "); 182 print_generic_expr (file, TREE_TYPE (var), dump_flags); 183 184 if (TREE_ADDRESSABLE (var)) 185 fprintf (file, ", is addressable"); 186 187 if (is_global_var (var)) 188 fprintf (file, ", is global"); 189 190 if (TREE_THIS_VOLATILE (var)) 191 fprintf (file, ", is volatile"); 192 193 if (cfun && ssa_default_def (cfun, var)) 194 { 195 fprintf (file, ", default def: "); 196 print_generic_expr (file, ssa_default_def (cfun, var), dump_flags); 197 } 198 199 if (DECL_INITIAL (var)) 200 { 201 fprintf (file, ", initial: "); 202 print_generic_expr (file, DECL_INITIAL (var), dump_flags); 203 } 204 205 fprintf (file, "\n"); 206 } 207 208 209 /* Dump variable VAR and its may-aliases to stderr. */ 210 211 DEBUG_FUNCTION void 212 debug_variable (tree var) 213 { 214 dump_variable (stderr, var); 215 } 216 217 218 /* Dump various DFA statistics to FILE. */ 219 220 void 221 dump_dfa_stats (FILE *file) 222 { 223 struct dfa_stats_d dfa_stats; 224 225 unsigned long size, total = 0; 226 const char * const fmt_str = "%-30s%-13s%12s\n"; 227 const char * const fmt_str_1 = "%-30s%13lu%11lu%c\n"; 228 const char * const fmt_str_3 = "%-43s%11lu%c\n"; 229 const char *funcname 230 = lang_hooks.decl_printable_name (current_function_decl, 2); 231 232 collect_dfa_stats (&dfa_stats); 233 234 fprintf (file, "\nDFA Statistics for %s\n\n", funcname); 235 236 fprintf (file, "---------------------------------------------------------\n"); 237 fprintf (file, fmt_str, "", " Number of ", "Memory"); 238 fprintf (file, fmt_str, "", " instances ", "used "); 239 fprintf (file, "---------------------------------------------------------\n"); 240 241 size = dfa_stats.num_uses * sizeof (tree *); 242 total += size; 243 fprintf (file, fmt_str_1, "USE operands", dfa_stats.num_uses, 244 SCALE (size), LABEL (size)); 245 246 size = dfa_stats.num_defs * sizeof (tree *); 247 total += size; 248 fprintf (file, fmt_str_1, "DEF operands", dfa_stats.num_defs, 249 SCALE (size), LABEL (size)); 250 251 size = dfa_stats.num_vuses * sizeof (tree *); 252 total += size; 253 fprintf (file, fmt_str_1, "VUSE operands", dfa_stats.num_vuses, 254 SCALE (size), LABEL (size)); 255 256 size = dfa_stats.num_vdefs * sizeof (tree *); 257 total += size; 258 fprintf (file, fmt_str_1, "VDEF operands", dfa_stats.num_vdefs, 259 SCALE (size), LABEL (size)); 260 261 size = dfa_stats.num_phis * sizeof (struct gphi); 262 total += size; 263 fprintf (file, fmt_str_1, "PHI nodes", dfa_stats.num_phis, 264 SCALE (size), LABEL (size)); 265 266 size = dfa_stats.num_phi_args * sizeof (struct phi_arg_d); 267 total += size; 268 fprintf (file, fmt_str_1, "PHI arguments", dfa_stats.num_phi_args, 269 SCALE (size), LABEL (size)); 270 271 fprintf (file, "---------------------------------------------------------\n"); 272 fprintf (file, fmt_str_3, "Total memory used by DFA/SSA data", SCALE (total), 273 LABEL (total)); 274 fprintf (file, "---------------------------------------------------------\n"); 275 fprintf (file, "\n"); 276 277 if (dfa_stats.num_phis) 278 fprintf (file, "Average number of arguments per PHI node: %.1f (max: %ld)\n", 279 (float) dfa_stats.num_phi_args / (float) dfa_stats.num_phis, 280 (long) dfa_stats.max_num_phi_args); 281 282 fprintf (file, "\n"); 283 } 284 285 286 /* Dump DFA statistics on stderr. */ 287 288 DEBUG_FUNCTION void 289 debug_dfa_stats (void) 290 { 291 dump_dfa_stats (stderr); 292 } 293 294 295 /* Collect DFA statistics and store them in the structure pointed to by 296 DFA_STATS_P. */ 297 298 static void 299 collect_dfa_stats (struct dfa_stats_d *dfa_stats_p ATTRIBUTE_UNUSED) 300 { 301 basic_block bb; 302 303 gcc_assert (dfa_stats_p); 304 305 memset ((void *)dfa_stats_p, 0, sizeof (struct dfa_stats_d)); 306 307 /* Walk all the statements in the function counting references. */ 308 FOR_EACH_BB_FN (bb, cfun) 309 { 310 for (gphi_iterator si = gsi_start_phis (bb); !gsi_end_p (si); 311 gsi_next (&si)) 312 { 313 gphi *phi = si.phi (); 314 dfa_stats_p->num_phis++; 315 dfa_stats_p->num_phi_args += gimple_phi_num_args (phi); 316 if (gimple_phi_num_args (phi) > dfa_stats_p->max_num_phi_args) 317 dfa_stats_p->max_num_phi_args = gimple_phi_num_args (phi); 318 } 319 320 for (gimple_stmt_iterator si = gsi_start_bb (bb); !gsi_end_p (si); 321 gsi_next (&si)) 322 { 323 gimple stmt = gsi_stmt (si); 324 dfa_stats_p->num_defs += NUM_SSA_OPERANDS (stmt, SSA_OP_DEF); 325 dfa_stats_p->num_uses += NUM_SSA_OPERANDS (stmt, SSA_OP_USE); 326 dfa_stats_p->num_vdefs += gimple_vdef (stmt) ? 1 : 0; 327 dfa_stats_p->num_vuses += gimple_vuse (stmt) ? 1 : 0; 328 } 329 } 330 } 331 332 333 /*--------------------------------------------------------------------------- 334 Miscellaneous helpers 335 ---------------------------------------------------------------------------*/ 336 337 /* Lookup VAR UID in the default_defs hashtable and return the associated 338 variable. */ 339 340 tree 341 ssa_default_def (struct function *fn, tree var) 342 { 343 struct tree_decl_minimal ind; 344 struct tree_ssa_name in; 345 gcc_assert (TREE_CODE (var) == VAR_DECL 346 || TREE_CODE (var) == PARM_DECL 347 || TREE_CODE (var) == RESULT_DECL); 348 in.var = (tree)&ind; 349 ind.uid = DECL_UID (var); 350 return DEFAULT_DEFS (fn)->find_with_hash ((tree)&in, DECL_UID (var)); 351 } 352 353 /* Insert the pair VAR's UID, DEF into the default_defs hashtable 354 of function FN. */ 355 356 void 357 set_ssa_default_def (struct function *fn, tree var, tree def) 358 { 359 struct tree_decl_minimal ind; 360 struct tree_ssa_name in; 361 362 gcc_assert (TREE_CODE (var) == VAR_DECL 363 || TREE_CODE (var) == PARM_DECL 364 || TREE_CODE (var) == RESULT_DECL); 365 in.var = (tree)&ind; 366 ind.uid = DECL_UID (var); 367 if (!def) 368 { 369 tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in, 370 DECL_UID (var), 371 NO_INSERT); 372 if (loc) 373 { 374 SSA_NAME_IS_DEFAULT_DEF (*(tree *)loc) = false; 375 DEFAULT_DEFS (fn)->clear_slot (loc); 376 } 377 return; 378 } 379 gcc_assert (TREE_CODE (def) == SSA_NAME && SSA_NAME_VAR (def) == var); 380 tree *loc = DEFAULT_DEFS (fn)->find_slot_with_hash ((tree)&in, 381 DECL_UID (var), INSERT); 382 383 /* Default definition might be changed by tail call optimization. */ 384 if (*loc) 385 SSA_NAME_IS_DEFAULT_DEF (*loc) = false; 386 387 /* Mark DEF as the default definition for VAR. */ 388 *loc = def; 389 SSA_NAME_IS_DEFAULT_DEF (def) = true; 390 } 391 392 /* Retrieve or create a default definition for VAR. */ 393 394 tree 395 get_or_create_ssa_default_def (struct function *fn, tree var) 396 { 397 tree ddef = ssa_default_def (fn, var); 398 if (ddef == NULL_TREE) 399 { 400 ddef = make_ssa_name_fn (fn, var, gimple_build_nop ()); 401 set_ssa_default_def (fn, var, ddef); 402 } 403 return ddef; 404 } 405 406 407 /* If EXP is a handled component reference for a structure, return the 408 base variable. The access range is delimited by bit positions *POFFSET and 409 *POFFSET + *PMAX_SIZE. The access size is *PSIZE bits. If either 410 *PSIZE or *PMAX_SIZE is -1, they could not be determined. If *PSIZE 411 and *PMAX_SIZE are equal, the access is non-variable. */ 412 413 tree 414 get_ref_base_and_extent (tree exp, HOST_WIDE_INT *poffset, 415 HOST_WIDE_INT *psize, 416 HOST_WIDE_INT *pmax_size) 417 { 418 offset_int bitsize = -1; 419 offset_int maxsize; 420 tree size_tree = NULL_TREE; 421 offset_int bit_offset = 0; 422 bool seen_variable_array_ref = false; 423 424 /* First get the final access size from just the outermost expression. */ 425 if (TREE_CODE (exp) == COMPONENT_REF) 426 size_tree = DECL_SIZE (TREE_OPERAND (exp, 1)); 427 else if (TREE_CODE (exp) == BIT_FIELD_REF) 428 size_tree = TREE_OPERAND (exp, 1); 429 else if (!VOID_TYPE_P (TREE_TYPE (exp))) 430 { 431 machine_mode mode = TYPE_MODE (TREE_TYPE (exp)); 432 if (mode == BLKmode) 433 size_tree = TYPE_SIZE (TREE_TYPE (exp)); 434 else 435 bitsize = int (GET_MODE_PRECISION (mode)); 436 } 437 if (size_tree != NULL_TREE 438 && TREE_CODE (size_tree) == INTEGER_CST) 439 bitsize = wi::to_offset (size_tree); 440 441 /* Initially, maxsize is the same as the accessed element size. 442 In the following it will only grow (or become -1). */ 443 maxsize = bitsize; 444 445 /* Compute cumulative bit-offset for nested component-refs and array-refs, 446 and find the ultimate containing object. */ 447 while (1) 448 { 449 switch (TREE_CODE (exp)) 450 { 451 case BIT_FIELD_REF: 452 bit_offset += wi::to_offset (TREE_OPERAND (exp, 2)); 453 break; 454 455 case COMPONENT_REF: 456 { 457 tree field = TREE_OPERAND (exp, 1); 458 tree this_offset = component_ref_field_offset (exp); 459 460 if (this_offset && TREE_CODE (this_offset) == INTEGER_CST) 461 { 462 offset_int woffset = wi::lshift (wi::to_offset (this_offset), 463 LOG2_BITS_PER_UNIT); 464 woffset += wi::to_offset (DECL_FIELD_BIT_OFFSET (field)); 465 bit_offset += woffset; 466 467 /* If we had seen a variable array ref already and we just 468 referenced the last field of a struct or a union member 469 then we have to adjust maxsize by the padding at the end 470 of our field. */ 471 if (seen_variable_array_ref && maxsize != -1) 472 { 473 tree stype = TREE_TYPE (TREE_OPERAND (exp, 0)); 474 tree next = DECL_CHAIN (field); 475 while (next && TREE_CODE (next) != FIELD_DECL) 476 next = DECL_CHAIN (next); 477 if (!next 478 || TREE_CODE (stype) != RECORD_TYPE) 479 { 480 tree fsize = DECL_SIZE_UNIT (field); 481 tree ssize = TYPE_SIZE_UNIT (stype); 482 if (fsize == NULL 483 || TREE_CODE (fsize) != INTEGER_CST 484 || ssize == NULL 485 || TREE_CODE (ssize) != INTEGER_CST) 486 maxsize = -1; 487 else 488 { 489 offset_int tem = (wi::to_offset (ssize) 490 - wi::to_offset (fsize)); 491 tem = wi::lshift (tem, LOG2_BITS_PER_UNIT); 492 tem -= woffset; 493 maxsize += tem; 494 } 495 } 496 } 497 } 498 else 499 { 500 tree csize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); 501 /* We need to adjust maxsize to the whole structure bitsize. 502 But we can subtract any constant offset seen so far, 503 because that would get us out of the structure otherwise. */ 504 if (maxsize != -1 505 && csize 506 && TREE_CODE (csize) == INTEGER_CST) 507 maxsize = wi::to_offset (csize) - bit_offset; 508 else 509 maxsize = -1; 510 } 511 } 512 break; 513 514 case ARRAY_REF: 515 case ARRAY_RANGE_REF: 516 { 517 tree index = TREE_OPERAND (exp, 1); 518 tree low_bound, unit_size; 519 520 /* If the resulting bit-offset is constant, track it. */ 521 if (TREE_CODE (index) == INTEGER_CST 522 && (low_bound = array_ref_low_bound (exp), 523 TREE_CODE (low_bound) == INTEGER_CST) 524 && (unit_size = array_ref_element_size (exp), 525 TREE_CODE (unit_size) == INTEGER_CST)) 526 { 527 offset_int woffset 528 = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound), 529 TYPE_PRECISION (TREE_TYPE (index))); 530 woffset *= wi::to_offset (unit_size); 531 woffset = wi::lshift (woffset, LOG2_BITS_PER_UNIT); 532 bit_offset += woffset; 533 534 /* An array ref with a constant index up in the structure 535 hierarchy will constrain the size of any variable array ref 536 lower in the access hierarchy. */ 537 seen_variable_array_ref = false; 538 } 539 else 540 { 541 tree asize = TYPE_SIZE (TREE_TYPE (TREE_OPERAND (exp, 0))); 542 /* We need to adjust maxsize to the whole array bitsize. 543 But we can subtract any constant offset seen so far, 544 because that would get us outside of the array otherwise. */ 545 if (maxsize != -1 546 && asize 547 && TREE_CODE (asize) == INTEGER_CST) 548 maxsize = wi::to_offset (asize) - bit_offset; 549 else 550 maxsize = -1; 551 552 /* Remember that we have seen an array ref with a variable 553 index. */ 554 seen_variable_array_ref = true; 555 } 556 } 557 break; 558 559 case REALPART_EXPR: 560 break; 561 562 case IMAGPART_EXPR: 563 bit_offset += bitsize; 564 break; 565 566 case VIEW_CONVERT_EXPR: 567 break; 568 569 case TARGET_MEM_REF: 570 /* Via the variable index or index2 we can reach the 571 whole object. Still hand back the decl here. */ 572 if (TREE_CODE (TMR_BASE (exp)) == ADDR_EXPR 573 && (TMR_INDEX (exp) || TMR_INDEX2 (exp))) 574 { 575 exp = TREE_OPERAND (TMR_BASE (exp), 0); 576 bit_offset = 0; 577 maxsize = -1; 578 goto done; 579 } 580 /* Fallthru. */ 581 case MEM_REF: 582 /* We need to deal with variable arrays ending structures such as 583 struct { int length; int a[1]; } x; x.a[d] 584 struct { struct { int a; int b; } a[1]; } x; x.a[d].a 585 struct { struct { int a[1]; } a[1]; } x; x.a[0][d], x.a[d][0] 586 struct { int len; union { int a[1]; struct X x; } u; } x; x.u.a[d] 587 where we do not know maxsize for variable index accesses to 588 the array. The simplest way to conservatively deal with this 589 is to punt in the case that offset + maxsize reaches the 590 base type boundary. This needs to include possible trailing 591 padding that is there for alignment purposes. */ 592 if (seen_variable_array_ref 593 && maxsize != -1 594 && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE 595 || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST 596 || (bit_offset + maxsize 597 == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp)))))) 598 maxsize = -1; 599 600 /* Hand back the decl for MEM[&decl, off]. */ 601 if (TREE_CODE (TREE_OPERAND (exp, 0)) == ADDR_EXPR) 602 { 603 if (integer_zerop (TREE_OPERAND (exp, 1))) 604 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0); 605 else 606 { 607 offset_int off = mem_ref_offset (exp); 608 off = wi::lshift (off, LOG2_BITS_PER_UNIT); 609 off += bit_offset; 610 if (wi::fits_shwi_p (off)) 611 { 612 bit_offset = off; 613 exp = TREE_OPERAND (TREE_OPERAND (exp, 0), 0); 614 } 615 } 616 } 617 goto done; 618 619 default: 620 goto done; 621 } 622 623 exp = TREE_OPERAND (exp, 0); 624 } 625 626 /* We need to deal with variable arrays ending structures. */ 627 if (seen_variable_array_ref 628 && maxsize != -1 629 && (TYPE_SIZE (TREE_TYPE (exp)) == NULL_TREE 630 || TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) != INTEGER_CST 631 || (bit_offset + maxsize 632 == wi::to_offset (TYPE_SIZE (TREE_TYPE (exp)))))) 633 maxsize = -1; 634 635 done: 636 if (!wi::fits_shwi_p (bitsize) || wi::neg_p (bitsize)) 637 { 638 *poffset = 0; 639 *psize = -1; 640 *pmax_size = -1; 641 642 return exp; 643 } 644 645 *psize = bitsize.to_shwi (); 646 647 if (!wi::fits_shwi_p (bit_offset)) 648 { 649 *poffset = 0; 650 *pmax_size = -1; 651 652 return exp; 653 } 654 655 /* In case of a decl or constant base object we can do better. */ 656 657 if (DECL_P (exp)) 658 { 659 /* If maxsize is unknown adjust it according to the size of the 660 base decl. */ 661 if (maxsize == -1 662 && DECL_SIZE (exp) 663 && TREE_CODE (DECL_SIZE (exp)) == INTEGER_CST) 664 maxsize = wi::to_offset (DECL_SIZE (exp)) - bit_offset; 665 } 666 else if (CONSTANT_CLASS_P (exp)) 667 { 668 /* If maxsize is unknown adjust it according to the size of the 669 base type constant. */ 670 if (maxsize == -1 671 && TYPE_SIZE (TREE_TYPE (exp)) 672 && TREE_CODE (TYPE_SIZE (TREE_TYPE (exp))) == INTEGER_CST) 673 maxsize = (wi::to_offset (TYPE_SIZE (TREE_TYPE (exp))) 674 - bit_offset); 675 } 676 677 /* ??? Due to negative offsets in ARRAY_REF we can end up with 678 negative bit_offset here. We might want to store a zero offset 679 in this case. */ 680 *poffset = bit_offset.to_shwi (); 681 if (!wi::fits_shwi_p (maxsize) || wi::neg_p (maxsize)) 682 *pmax_size = -1; 683 else 684 *pmax_size = maxsize.to_shwi (); 685 686 return exp; 687 } 688 689 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that 690 denotes the starting address of the memory access EXP. 691 Returns NULL_TREE if the offset is not constant or any component 692 is not BITS_PER_UNIT-aligned. 693 VALUEIZE if non-NULL is used to valueize SSA names. It should return 694 its argument or a constant if the argument is known to be constant. */ 695 696 tree 697 get_addr_base_and_unit_offset_1 (tree exp, HOST_WIDE_INT *poffset, 698 tree (*valueize) (tree)) 699 { 700 HOST_WIDE_INT byte_offset = 0; 701 702 /* Compute cumulative byte-offset for nested component-refs and array-refs, 703 and find the ultimate containing object. */ 704 while (1) 705 { 706 switch (TREE_CODE (exp)) 707 { 708 case BIT_FIELD_REF: 709 { 710 HOST_WIDE_INT this_off = TREE_INT_CST_LOW (TREE_OPERAND (exp, 2)); 711 if (this_off % BITS_PER_UNIT) 712 return NULL_TREE; 713 byte_offset += this_off / BITS_PER_UNIT; 714 } 715 break; 716 717 case COMPONENT_REF: 718 { 719 tree field = TREE_OPERAND (exp, 1); 720 tree this_offset = component_ref_field_offset (exp); 721 HOST_WIDE_INT hthis_offset; 722 723 if (!this_offset 724 || TREE_CODE (this_offset) != INTEGER_CST 725 || (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field)) 726 % BITS_PER_UNIT)) 727 return NULL_TREE; 728 729 hthis_offset = TREE_INT_CST_LOW (this_offset); 730 hthis_offset += (TREE_INT_CST_LOW (DECL_FIELD_BIT_OFFSET (field)) 731 / BITS_PER_UNIT); 732 byte_offset += hthis_offset; 733 } 734 break; 735 736 case ARRAY_REF: 737 case ARRAY_RANGE_REF: 738 { 739 tree index = TREE_OPERAND (exp, 1); 740 tree low_bound, unit_size; 741 742 if (valueize 743 && TREE_CODE (index) == SSA_NAME) 744 index = (*valueize) (index); 745 746 /* If the resulting bit-offset is constant, track it. */ 747 if (TREE_CODE (index) == INTEGER_CST 748 && (low_bound = array_ref_low_bound (exp), 749 TREE_CODE (low_bound) == INTEGER_CST) 750 && (unit_size = array_ref_element_size (exp), 751 TREE_CODE (unit_size) == INTEGER_CST)) 752 { 753 offset_int woffset 754 = wi::sext (wi::to_offset (index) - wi::to_offset (low_bound), 755 TYPE_PRECISION (TREE_TYPE (index))); 756 woffset *= wi::to_offset (unit_size); 757 byte_offset += woffset.to_shwi (); 758 } 759 else 760 return NULL_TREE; 761 } 762 break; 763 764 case REALPART_EXPR: 765 break; 766 767 case IMAGPART_EXPR: 768 byte_offset += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (TREE_TYPE (exp))); 769 break; 770 771 case VIEW_CONVERT_EXPR: 772 break; 773 774 case MEM_REF: 775 { 776 tree base = TREE_OPERAND (exp, 0); 777 if (valueize 778 && TREE_CODE (base) == SSA_NAME) 779 base = (*valueize) (base); 780 781 /* Hand back the decl for MEM[&decl, off]. */ 782 if (TREE_CODE (base) == ADDR_EXPR) 783 { 784 if (!integer_zerop (TREE_OPERAND (exp, 1))) 785 { 786 offset_int off = mem_ref_offset (exp); 787 byte_offset += off.to_short_addr (); 788 } 789 exp = TREE_OPERAND (base, 0); 790 } 791 goto done; 792 } 793 794 case TARGET_MEM_REF: 795 { 796 tree base = TREE_OPERAND (exp, 0); 797 if (valueize 798 && TREE_CODE (base) == SSA_NAME) 799 base = (*valueize) (base); 800 801 /* Hand back the decl for MEM[&decl, off]. */ 802 if (TREE_CODE (base) == ADDR_EXPR) 803 { 804 if (TMR_INDEX (exp) || TMR_INDEX2 (exp)) 805 return NULL_TREE; 806 if (!integer_zerop (TMR_OFFSET (exp))) 807 { 808 offset_int off = mem_ref_offset (exp); 809 byte_offset += off.to_short_addr (); 810 } 811 exp = TREE_OPERAND (base, 0); 812 } 813 goto done; 814 } 815 816 default: 817 goto done; 818 } 819 820 exp = TREE_OPERAND (exp, 0); 821 } 822 done: 823 824 *poffset = byte_offset; 825 return exp; 826 } 827 828 /* Returns the base object and a constant BITS_PER_UNIT offset in *POFFSET that 829 denotes the starting address of the memory access EXP. 830 Returns NULL_TREE if the offset is not constant or any component 831 is not BITS_PER_UNIT-aligned. */ 832 833 tree 834 get_addr_base_and_unit_offset (tree exp, HOST_WIDE_INT *poffset) 835 { 836 return get_addr_base_and_unit_offset_1 (exp, poffset, NULL); 837 } 838 839 /* Returns true if STMT references an SSA_NAME that has 840 SSA_NAME_OCCURS_IN_ABNORMAL_PHI set, otherwise false. */ 841 842 bool 843 stmt_references_abnormal_ssa_name (gimple stmt) 844 { 845 ssa_op_iter oi; 846 use_operand_p use_p; 847 848 FOR_EACH_SSA_USE_OPERAND (use_p, stmt, oi, SSA_OP_USE) 849 { 850 if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (USE_FROM_PTR (use_p))) 851 return true; 852 } 853 854 return false; 855 } 856 857 /* Pair of tree and a sorting index, for dump_enumerated_decls. */ 858 struct GTY(()) numbered_tree_d 859 { 860 tree t; 861 int num; 862 }; 863 typedef struct numbered_tree_d numbered_tree; 864 865 866 /* Compare two declarations references by their DECL_UID / sequence number. 867 Called via qsort. */ 868 869 static int 870 compare_decls_by_uid (const void *pa, const void *pb) 871 { 872 const numbered_tree *nt_a = ((const numbered_tree *)pa); 873 const numbered_tree *nt_b = ((const numbered_tree *)pb); 874 875 if (DECL_UID (nt_a->t) != DECL_UID (nt_b->t)) 876 return DECL_UID (nt_a->t) - DECL_UID (nt_b->t); 877 return nt_a->num - nt_b->num; 878 } 879 880 /* Called via walk_gimple_stmt / walk_gimple_op by dump_enumerated_decls. */ 881 static tree 882 dump_enumerated_decls_push (tree *tp, int *walk_subtrees, void *data) 883 { 884 struct walk_stmt_info *wi = (struct walk_stmt_info *) data; 885 vec<numbered_tree> *list = (vec<numbered_tree> *) wi->info; 886 numbered_tree nt; 887 888 if (!DECL_P (*tp)) 889 return NULL_TREE; 890 nt.t = *tp; 891 nt.num = list->length (); 892 list->safe_push (nt); 893 *walk_subtrees = 0; 894 return NULL_TREE; 895 } 896 897 /* Find all the declarations used by the current function, sort them by uid, 898 and emit the sorted list. Each declaration is tagged with a sequence 899 number indicating when it was found during statement / tree walking, 900 so that TDF_NOUID comparisons of anonymous declarations are still 901 meaningful. Where a declaration was encountered more than once, we 902 emit only the sequence number of the first encounter. 903 FILE is the dump file where to output the list and FLAGS is as in 904 print_generic_expr. */ 905 void 906 dump_enumerated_decls (FILE *file, int flags) 907 { 908 basic_block bb; 909 struct walk_stmt_info wi; 910 auto_vec<numbered_tree, 40> decl_list; 911 912 memset (&wi, '\0', sizeof (wi)); 913 wi.info = (void *) &decl_list; 914 FOR_EACH_BB_FN (bb, cfun) 915 { 916 gimple_stmt_iterator gsi; 917 918 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 919 if (!is_gimple_debug (gsi_stmt (gsi))) 920 walk_gimple_stmt (&gsi, NULL, dump_enumerated_decls_push, &wi); 921 } 922 decl_list.qsort (compare_decls_by_uid); 923 if (decl_list.length ()) 924 { 925 unsigned ix; 926 numbered_tree *ntp; 927 tree last = NULL_TREE; 928 929 fprintf (file, "Declarations used by %s, sorted by DECL_UID:\n", 930 current_function_name ()); 931 FOR_EACH_VEC_ELT (decl_list, ix, ntp) 932 { 933 if (ntp->t == last) 934 continue; 935 fprintf (file, "%d: ", ntp->num); 936 print_generic_decl (file, ntp->t, flags); 937 fprintf (file, "\n"); 938 last = ntp->t; 939 } 940 } 941 } 942