1/* Liveness for SSA trees. 2 Copyright (C) 2003, 2004, 2005, 2007, 2008, 2009 Free Software Foundation, 3 Inc. 4 Contributed by Andrew MacLeod <amacleod@redhat.com> 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify 9it under the terms of the GNU General Public License as published by 10the Free Software Foundation; either version 3, or (at your option) 11any later version. 12 13GCC is distributed in the hope that it will be useful, 14but WITHOUT ANY WARRANTY; without even the implied warranty of 15MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 16GNU General Public License for more details. 17 18You should have received a copy of the GNU General Public License 19along 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 "tree.h" 27#include "diagnostic.h" 28#include "bitmap.h" 29#include "tree-flow.h" 30#include "tree-dump.h" 31#include "tree-ssa-live.h" 32#include "toplev.h" 33#include "debug.h" 34#include "flags.h" 35 36#ifdef ENABLE_CHECKING 37static void verify_live_on_entry (tree_live_info_p); 38#endif 39 40 41/* VARMAP maintains a mapping from SSA version number to real variables. 42 43 All SSA_NAMES are divided into partitions. Initially each ssa_name is the 44 only member of it's own partition. Coalescing will attempt to group any 45 ssa_names which occur in a copy or in a PHI node into the same partition. 46 47 At the end of out-of-ssa, each partition becomes a "real" variable and is 48 rewritten as a compiler variable. 49 50 The var_map data structure is used to manage these partitions. It allows 51 partitions to be combined, and determines which partition belongs to what 52 ssa_name or variable, and vice versa. */ 53 54 55/* This routine will initialize the basevar fields of MAP. */ 56 57static void 58var_map_base_init (var_map map) 59{ 60 int x, num_part, num; 61 tree var; 62 var_ann_t ann; 63 64 num = 0; 65 num_part = num_var_partitions (map); 66 67 /* If a base table already exists, clear it, otherwise create it. */ 68 if (map->partition_to_base_index != NULL) 69 { 70 free (map->partition_to_base_index); 71 VEC_truncate (tree, map->basevars, 0); 72 } 73 else 74 map->basevars = VEC_alloc (tree, heap, MAX (40, (num_part / 10))); 75 76 map->partition_to_base_index = (int *) xmalloc (sizeof (int) * num_part); 77 78 /* Build the base variable list, and point partitions at their bases. */ 79 for (x = 0; x < num_part; x++) 80 { 81 var = partition_to_var (map, x); 82 if (TREE_CODE (var) == SSA_NAME) 83 var = SSA_NAME_VAR (var); 84 ann = var_ann (var); 85 /* If base variable hasn't been seen, set it up. */ 86 if (!ann->base_var_processed) 87 { 88 ann->base_var_processed = 1; 89 VAR_ANN_BASE_INDEX (ann) = num++; 90 VEC_safe_push (tree, heap, map->basevars, var); 91 } 92 map->partition_to_base_index[x] = VAR_ANN_BASE_INDEX (ann); 93 } 94 95 map->num_basevars = num; 96 97 /* Now clear the processed bit. */ 98 for (x = 0; x < num; x++) 99 { 100 var = VEC_index (tree, map->basevars, x); 101 var_ann (var)->base_var_processed = 0; 102 } 103 104#ifdef ENABLE_CHECKING 105 for (x = 0; x < num_part; x++) 106 { 107 tree var2; 108 var = SSA_NAME_VAR (partition_to_var (map, x)); 109 var2 = VEC_index (tree, map->basevars, basevar_index (map, x)); 110 gcc_assert (var == var2); 111 } 112#endif 113} 114 115 116/* Remove the base table in MAP. */ 117 118static void 119var_map_base_fini (var_map map) 120{ 121 /* Free the basevar info if it is present. */ 122 if (map->partition_to_base_index != NULL) 123 { 124 VEC_free (tree, heap, map->basevars); 125 free (map->partition_to_base_index); 126 map->partition_to_base_index = NULL; 127 map->num_basevars = 0; 128 } 129} 130/* Create a variable partition map of SIZE, initialize and return it. */ 131 132var_map 133init_var_map (int size) 134{ 135 var_map map; 136 137 map = (var_map) xmalloc (sizeof (struct _var_map)); 138 map->var_partition = partition_new (size); 139 140 map->partition_to_view = NULL; 141 map->view_to_partition = NULL; 142 map->num_partitions = size; 143 map->partition_size = size; 144 map->num_basevars = 0; 145 map->partition_to_base_index = NULL; 146 map->basevars = NULL; 147 return map; 148} 149 150 151/* Free memory associated with MAP. */ 152 153void 154delete_var_map (var_map map) 155{ 156 var_map_base_fini (map); 157 partition_delete (map->var_partition); 158 if (map->partition_to_view) 159 free (map->partition_to_view); 160 if (map->view_to_partition) 161 free (map->view_to_partition); 162 free (map); 163} 164 165 166/* This function will combine the partitions in MAP for VAR1 and VAR2. It 167 Returns the partition which represents the new partition. If the two 168 partitions cannot be combined, NO_PARTITION is returned. */ 169 170int 171var_union (var_map map, tree var1, tree var2) 172{ 173 int p1, p2, p3; 174 175 gcc_assert (TREE_CODE (var1) == SSA_NAME); 176 gcc_assert (TREE_CODE (var2) == SSA_NAME); 177 178 /* This is independent of partition_to_view. If partition_to_view is 179 on, then whichever one of these partitions is absorbed will never have a 180 dereference into the partition_to_view array any more. */ 181 182 p1 = partition_find (map->var_partition, SSA_NAME_VERSION (var1)); 183 p2 = partition_find (map->var_partition, SSA_NAME_VERSION (var2)); 184 185 gcc_assert (p1 != NO_PARTITION); 186 gcc_assert (p2 != NO_PARTITION); 187 188 if (p1 == p2) 189 p3 = p1; 190 else 191 p3 = partition_union (map->var_partition, p1, p2); 192 193 if (map->partition_to_view) 194 p3 = map->partition_to_view[p3]; 195 196 return p3; 197} 198 199 200/* Compress the partition numbers in MAP such that they fall in the range 201 0..(num_partitions-1) instead of wherever they turned out during 202 the partitioning exercise. This removes any references to unused 203 partitions, thereby allowing bitmaps and other vectors to be much 204 denser. 205 206 This is implemented such that compaction doesn't affect partitioning. 207 Ie., once partitions are created and possibly merged, running one 208 or more different kind of compaction will not affect the partitions 209 themselves. Their index might change, but all the same variables will 210 still be members of the same partition group. This allows work on reduced 211 sets, and no loss of information when a larger set is later desired. 212 213 In particular, coalescing can work on partitions which have 2 or more 214 definitions, and then 'recompact' later to include all the single 215 definitions for assignment to program variables. */ 216 217 218/* Set MAP back to the initial state of having no partition view. Return a 219 bitmap which has a bit set for each partition number which is in use in the 220 varmap. */ 221 222static bitmap 223partition_view_init (var_map map) 224{ 225 bitmap used; 226 int tmp; 227 unsigned int x; 228 229 used = BITMAP_ALLOC (NULL); 230 231 /* Already in a view? Abandon the old one. */ 232 if (map->partition_to_view) 233 { 234 free (map->partition_to_view); 235 map->partition_to_view = NULL; 236 } 237 if (map->view_to_partition) 238 { 239 free (map->view_to_partition); 240 map->view_to_partition = NULL; 241 } 242 243 /* Find out which partitions are actually referenced. */ 244 for (x = 0; x < map->partition_size; x++) 245 { 246 tmp = partition_find (map->var_partition, x); 247 if (ssa_name (tmp) != NULL_TREE && is_gimple_reg (ssa_name (tmp)) 248 && (!has_zero_uses (ssa_name (tmp)) 249 || !SSA_NAME_IS_DEFAULT_DEF (ssa_name (tmp)))) 250 bitmap_set_bit (used, tmp); 251 } 252 253 map->num_partitions = map->partition_size; 254 return used; 255} 256 257 258/* This routine will finalize the view data for MAP based on the partitions 259 set in SELECTED. This is either the same bitmap returned from 260 partition_view_init, or a trimmed down version if some of those partitions 261 were not desired in this view. SELECTED is freed before returning. */ 262 263static void 264partition_view_fini (var_map map, bitmap selected) 265{ 266 bitmap_iterator bi; 267 unsigned count, i, x, limit; 268 269 gcc_assert (selected); 270 271 count = bitmap_count_bits (selected); 272 limit = map->partition_size; 273 274 /* If its a one-to-one ratio, we don't need any view compaction. */ 275 if (count < limit) 276 { 277 map->partition_to_view = (int *)xmalloc (limit * sizeof (int)); 278 memset (map->partition_to_view, 0xff, (limit * sizeof (int))); 279 map->view_to_partition = (int *)xmalloc (count * sizeof (int)); 280 281 i = 0; 282 /* Give each selected partition an index. */ 283 EXECUTE_IF_SET_IN_BITMAP (selected, 0, x, bi) 284 { 285 map->partition_to_view[x] = i; 286 map->view_to_partition[i] = x; 287 i++; 288 } 289 gcc_assert (i == count); 290 map->num_partitions = i; 291 } 292 293 BITMAP_FREE (selected); 294} 295 296 297/* Create a partition view which includes all the used partitions in MAP. If 298 WANT_BASES is true, create the base variable map as well. */ 299 300extern void 301partition_view_normal (var_map map, bool want_bases) 302{ 303 bitmap used; 304 305 used = partition_view_init (map); 306 partition_view_fini (map, used); 307 308 if (want_bases) 309 var_map_base_init (map); 310 else 311 var_map_base_fini (map); 312} 313 314 315/* Create a partition view in MAP which includes just partitions which occur in 316 the bitmap ONLY. If WANT_BASES is true, create the base variable map 317 as well. */ 318 319extern void 320partition_view_bitmap (var_map map, bitmap only, bool want_bases) 321{ 322 bitmap used; 323 bitmap new_partitions = BITMAP_ALLOC (NULL); 324 unsigned x, p; 325 bitmap_iterator bi; 326 327 used = partition_view_init (map); 328 EXECUTE_IF_SET_IN_BITMAP (only, 0, x, bi) 329 { 330 p = partition_find (map->var_partition, x); 331 gcc_assert (bitmap_bit_p (used, p)); 332 bitmap_set_bit (new_partitions, p); 333 } 334 partition_view_fini (map, new_partitions); 335 336 BITMAP_FREE (used); 337 if (want_bases) 338 var_map_base_init (map); 339 else 340 var_map_base_fini (map); 341} 342 343 344static inline void mark_all_vars_used (tree *, void *data); 345 346/* Helper function for mark_all_vars_used, called via walk_tree. */ 347 348static tree 349mark_all_vars_used_1 (tree *tp, int *walk_subtrees, void *data) 350{ 351 tree t = *tp; 352 enum tree_code_class c = TREE_CODE_CLASS (TREE_CODE (t)); 353 tree b; 354 355 if (TREE_CODE (t) == SSA_NAME) 356 t = SSA_NAME_VAR (t); 357 358 if (IS_EXPR_CODE_CLASS (c) 359 && (b = TREE_BLOCK (t)) != NULL) 360 TREE_USED (b) = true; 361 362 /* Ignore TREE_ORIGINAL for TARGET_MEM_REFS, as well as other 363 fields that do not contain vars. */ 364 if (TREE_CODE (t) == TARGET_MEM_REF) 365 { 366 mark_all_vars_used (&TMR_SYMBOL (t), data); 367 mark_all_vars_used (&TMR_BASE (t), data); 368 mark_all_vars_used (&TMR_INDEX (t), data); 369 *walk_subtrees = 0; 370 return NULL; 371 } 372 373 /* Only need to mark VAR_DECLS; parameters and return results are not 374 eliminated as unused. */ 375 if (TREE_CODE (t) == VAR_DECL) 376 { 377 if (data != NULL && bitmap_bit_p ((bitmap) data, DECL_UID (t))) 378 { 379 bitmap_clear_bit ((bitmap) data, DECL_UID (t)); 380 mark_all_vars_used (&DECL_INITIAL (t), data); 381 } 382 set_is_used (t); 383 } 384 /* remove_unused_scope_block_p requires information about labels 385 which are not DECL_IGNORED_P to tell if they might be used in the IL. */ 386 if (TREE_CODE (t) == LABEL_DECL) 387 /* Although the TREE_USED values that the frontend uses would be 388 acceptable (albeit slightly over-conservative) for our purposes, 389 init_vars_expansion clears TREE_USED for LABEL_DECLs too, so we 390 must re-compute it here. */ 391 TREE_USED (t) = 1; 392 393 if (IS_TYPE_OR_DECL_P (t)) 394 *walk_subtrees = 0; 395 396 return NULL; 397} 398 399/* Mark the scope block SCOPE and its subblocks unused when they can be 400 possibly eliminated if dead. */ 401 402static void 403mark_scope_block_unused (tree scope) 404{ 405 tree t; 406 TREE_USED (scope) = false; 407 if (!(*debug_hooks->ignore_block) (scope)) 408 TREE_USED (scope) = true; 409 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t)) 410 mark_scope_block_unused (t); 411} 412 413/* Look if the block is dead (by possibly eliminating its dead subblocks) 414 and return true if so. 415 Block is declared dead if: 416 1) No statements are associated with it. 417 2) Declares no live variables 418 3) All subblocks are dead 419 or there is precisely one subblocks and the block 420 has same abstract origin as outer block and declares 421 no variables, so it is pure wrapper. 422 When we are not outputting full debug info, we also eliminate dead variables 423 out of scope blocks to let them to be recycled by GGC and to save copying work 424 done by the inliner. */ 425 426static bool 427remove_unused_scope_block_p (tree scope) 428{ 429 tree *t, *next; 430 bool unused = !TREE_USED (scope); 431 var_ann_t ann; 432 int nsubblocks = 0; 433 434 for (t = &BLOCK_VARS (scope); *t; t = next) 435 { 436 next = &TREE_CHAIN (*t); 437 438 /* Debug info of nested function refers to the block of the 439 function. We might stil call it even if all statements 440 of function it was nested into was elliminated. 441 442 TODO: We can actually look into cgraph to see if function 443 will be output to file. */ 444 if (TREE_CODE (*t) == FUNCTION_DECL) 445 unused = false; 446 447 /* If a decl has a value expr, we need to instantiate it 448 regardless of debug info generation, to avoid codegen 449 differences in memory overlap tests. update_equiv_regs() may 450 indirectly call validate_equiv_mem() to test whether a 451 SET_DEST overlaps with others, and if the value expr changes 452 by virtual register instantiation, we may get end up with 453 different results. */ 454 else if (TREE_CODE (*t) == VAR_DECL && DECL_HAS_VALUE_EXPR_P (*t)) 455 unused = false; 456 457 /* Remove everything we don't generate debug info for. */ 458 else if (DECL_IGNORED_P (*t)) 459 { 460 *t = TREE_CHAIN (*t); 461 next = t; 462 } 463 464 /* When we are outputting debug info, we usually want to output 465 info about optimized-out variables in the scope blocks. 466 Exception are the scope blocks not containing any instructions 467 at all so user can't get into the scopes at first place. */ 468 else if ((ann = var_ann (*t)) != NULL 469 && ann->used) 470 unused = false; 471 else if (TREE_CODE (*t) == LABEL_DECL && TREE_USED (*t)) 472 /* For labels that are still used in the IL, the decision to 473 preserve them must not depend DEBUG_INFO_LEVEL, otherwise we 474 risk having different ordering in debug vs. non-debug builds 475 during inlining or versioning. 476 A label appearing here (we have already checked DECL_IGNORED_P) 477 should not be used in the IL unless it has been explicitly used 478 before, so we use TREE_USED as an approximation. */ 479 /* In principle, we should do the same here as for the debug case 480 below, however, when debugging, there might be additional nested 481 levels that keep an upper level with a label live, so we have to 482 force this block to be considered used, too. */ 483 unused = false; 484 485 /* When we are not doing full debug info, we however can keep around 486 only the used variables for cfgexpand's memory packing saving quite 487 a lot of memory. 488 489 For sake of -g3, we keep around those vars but we don't count this as 490 use of block, so innermost block with no used vars and no instructions 491 can be considered dead. We only want to keep around blocks user can 492 breakpoint into and ask about value of optimized out variables. 493 494 Similarly we need to keep around types at least until all variables of 495 all nested blocks are gone. We track no information on whether given 496 type is used or not. */ 497 498 else if (debug_info_level == DINFO_LEVEL_NORMAL 499 || debug_info_level == DINFO_LEVEL_VERBOSE) 500 ; 501 else 502 { 503 *t = TREE_CHAIN (*t); 504 next = t; 505 } 506 } 507 508 for (t = &BLOCK_SUBBLOCKS (scope); *t ;) 509 if (remove_unused_scope_block_p (*t)) 510 { 511 if (BLOCK_SUBBLOCKS (*t)) 512 { 513 tree next = BLOCK_CHAIN (*t); 514 tree supercontext = BLOCK_SUPERCONTEXT (*t); 515 516 *t = BLOCK_SUBBLOCKS (*t); 517 while (BLOCK_CHAIN (*t)) 518 { 519 BLOCK_SUPERCONTEXT (*t) = supercontext; 520 t = &BLOCK_CHAIN (*t); 521 } 522 BLOCK_CHAIN (*t) = next; 523 BLOCK_SUPERCONTEXT (*t) = supercontext; 524 t = &BLOCK_CHAIN (*t); 525 nsubblocks ++; 526 } 527 else 528 *t = BLOCK_CHAIN (*t); 529 } 530 else 531 { 532 t = &BLOCK_CHAIN (*t); 533 nsubblocks ++; 534 } 535 536 537 if (!unused) 538 ; 539 /* Outer scope is always used. */ 540 else if (!BLOCK_SUPERCONTEXT (scope) 541 || TREE_CODE (BLOCK_SUPERCONTEXT (scope)) == FUNCTION_DECL) 542 unused = false; 543 /* Innermost blocks with no live variables nor statements can be always 544 eliminated. */ 545 else if (!nsubblocks) 546 ; 547 /* For terse debug info we can eliminate info on unused variables. */ 548 else if (debug_info_level == DINFO_LEVEL_NONE 549 || debug_info_level == DINFO_LEVEL_TERSE) 550 { 551 /* Even for -g0/-g1 don't prune outer scopes from artificial 552 functions, otherwise diagnostics using tree_nonartificial_location 553 will not be emitted properly. */ 554 if (inlined_function_outer_scope_p (scope)) 555 { 556 tree ao = scope; 557 558 while (ao 559 && TREE_CODE (ao) == BLOCK 560 && BLOCK_ABSTRACT_ORIGIN (ao) != ao) 561 ao = BLOCK_ABSTRACT_ORIGIN (ao); 562 if (ao 563 && TREE_CODE (ao) == FUNCTION_DECL 564 && DECL_DECLARED_INLINE_P (ao) 565 && lookup_attribute ("artificial", DECL_ATTRIBUTES (ao))) 566 unused = false; 567 } 568 } 569 else if (BLOCK_VARS (scope) || BLOCK_NUM_NONLOCALIZED_VARS (scope)) 570 unused = false; 571 /* See if this block is important for representation of inlined function. 572 Inlined functions are always represented by block with 573 block_ultimate_origin being set to FUNCTION_DECL and DECL_SOURCE_LOCATION 574 set... */ 575 else if (inlined_function_outer_scope_p (scope)) 576 unused = false; 577 else 578 /* Verfify that only blocks with source location set 579 are entry points to the inlined functions. */ 580 gcc_assert (BLOCK_SOURCE_LOCATION (scope) == UNKNOWN_LOCATION); 581 582 TREE_USED (scope) = !unused; 583 return unused; 584} 585 586/* Mark all VAR_DECLS under *EXPR_P as used, so that they won't be 587 eliminated during the tree->rtl conversion process. */ 588 589static inline void 590mark_all_vars_used (tree *expr_p, void *data) 591{ 592 walk_tree (expr_p, mark_all_vars_used_1, data, NULL); 593} 594 595 596/* Dump scope blocks starting at SCOPE to FILE. INDENT is the 597 indentation level and FLAGS is as in print_generic_expr. */ 598 599static void 600dump_scope_block (FILE *file, int indent, tree scope, int flags) 601{ 602 tree var, t; 603 unsigned int i; 604 605 fprintf (file, "\n%*s{ Scope block #%i%s%s",indent, "" , BLOCK_NUMBER (scope), 606 TREE_USED (scope) ? "" : " (unused)", 607 BLOCK_ABSTRACT (scope) ? " (abstract)": ""); 608 if (BLOCK_SOURCE_LOCATION (scope) != UNKNOWN_LOCATION) 609 { 610 expanded_location s = expand_location (BLOCK_SOURCE_LOCATION (scope)); 611 fprintf (file, " %s:%i", s.file, s.line); 612 } 613 if (BLOCK_ABSTRACT_ORIGIN (scope)) 614 { 615 tree origin = block_ultimate_origin (scope); 616 if (origin) 617 { 618 fprintf (file, " Originating from :"); 619 if (DECL_P (origin)) 620 print_generic_decl (file, origin, flags); 621 else 622 fprintf (file, "#%i", BLOCK_NUMBER (origin)); 623 } 624 } 625 fprintf (file, " \n"); 626 for (var = BLOCK_VARS (scope); var; var = TREE_CHAIN (var)) 627 { 628 bool used = false; 629 var_ann_t ann; 630 631 if ((ann = var_ann (var)) 632 && ann->used) 633 used = true; 634 635 fprintf (file, "%*s",indent, ""); 636 print_generic_decl (file, var, flags); 637 fprintf (file, "%s\n", used ? "" : " (unused)"); 638 } 639 for (i = 0; i < BLOCK_NUM_NONLOCALIZED_VARS (scope); i++) 640 { 641 fprintf (file, "%*s",indent, ""); 642 print_generic_decl (file, BLOCK_NONLOCALIZED_VAR (scope, i), 643 flags); 644 fprintf (file, " (nonlocalized)\n"); 645 } 646 for (t = BLOCK_SUBBLOCKS (scope); t ; t = BLOCK_CHAIN (t)) 647 dump_scope_block (file, indent + 2, t, flags); 648 fprintf (file, "\n%*s}\n",indent, ""); 649} 650 651/* Dump the tree of lexical scopes starting at SCOPE to stderr. FLAGS 652 is as in print_generic_expr. */ 653 654void 655debug_scope_block (tree scope, int flags) 656{ 657 dump_scope_block (stderr, 0, scope, flags); 658} 659 660 661/* Dump the tree of lexical scopes of current_function_decl to FILE. 662 FLAGS is as in print_generic_expr. */ 663 664void 665dump_scope_blocks (FILE *file, int flags) 666{ 667 dump_scope_block (file, 0, DECL_INITIAL (current_function_decl), flags); 668} 669 670 671/* Dump the tree of lexical scopes of current_function_decl to stderr. 672 FLAGS is as in print_generic_expr. */ 673 674void 675debug_scope_blocks (int flags) 676{ 677 dump_scope_blocks (stderr, flags); 678} 679 680/* Remove local variables that are not referenced in the IL. */ 681 682void 683remove_unused_locals (void) 684{ 685 basic_block bb; 686 tree t, *cell; 687 referenced_var_iterator rvi; 688 var_ann_t ann; 689 bitmap global_unused_vars = NULL; 690 691 /* Removing declarations from lexical blocks when not optimizing is 692 not only a waste of time, it actually causes differences in stack 693 layout. */ 694 if (!optimize) 695 return; 696 697 mark_scope_block_unused (DECL_INITIAL (current_function_decl)); 698 699 /* Assume all locals are unused. */ 700 FOR_EACH_REFERENCED_VAR (t, rvi) 701 var_ann (t)->used = false; 702 703 /* Walk the CFG marking all referenced symbols. */ 704 FOR_EACH_BB (bb) 705 { 706 gimple_stmt_iterator gsi; 707 size_t i; 708 edge_iterator ei; 709 edge e; 710 711 /* Walk the statements. */ 712 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 713 { 714 gimple stmt = gsi_stmt (gsi); 715 tree b = gimple_block (stmt); 716 717 if (is_gimple_debug (stmt)) 718 continue; 719 720 if (b) 721 TREE_USED (b) = true; 722 723 for (i = 0; i < gimple_num_ops (stmt); i++) 724 mark_all_vars_used (gimple_op_ptr (gsi_stmt (gsi), i), NULL); 725 } 726 727 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 728 { 729 use_operand_p arg_p; 730 ssa_op_iter i; 731 tree def; 732 gimple phi = gsi_stmt (gsi); 733 734 /* No point processing globals. */ 735 if (is_global_var (SSA_NAME_VAR (gimple_phi_result (phi)))) 736 continue; 737 738 def = gimple_phi_result (phi); 739 mark_all_vars_used (&def, NULL); 740 741 FOR_EACH_PHI_ARG (arg_p, phi, i, SSA_OP_ALL_USES) 742 { 743 tree arg = USE_FROM_PTR (arg_p); 744 mark_all_vars_used (&arg, NULL); 745 } 746 } 747 748 FOR_EACH_EDGE (e, ei, bb->succs) 749 if (e->goto_locus) 750 TREE_USED (e->goto_block) = true; 751 } 752 753 cfun->has_local_explicit_reg_vars = false; 754 755 /* Remove unmarked local vars from local_decls. */ 756 for (cell = &cfun->local_decls; *cell; ) 757 { 758 tree var = TREE_VALUE (*cell); 759 760 if (TREE_CODE (var) != FUNCTION_DECL 761 && (!(ann = var_ann (var)) 762 || !ann->used)) 763 { 764 if (is_global_var (var)) 765 { 766 if (global_unused_vars == NULL) 767 global_unused_vars = BITMAP_ALLOC (NULL); 768 bitmap_set_bit (global_unused_vars, DECL_UID (var)); 769 } 770 else 771 { 772 *cell = TREE_CHAIN (*cell); 773 continue; 774 } 775 } 776 else if (TREE_CODE (var) == VAR_DECL 777 && DECL_HARD_REGISTER (var) 778 && !is_global_var (var)) 779 cfun->has_local_explicit_reg_vars = true; 780 cell = &TREE_CHAIN (*cell); 781 } 782 783 /* Remove unmarked global vars from local_decls. */ 784 if (global_unused_vars != NULL) 785 { 786 for (t = cfun->local_decls; t; t = TREE_CHAIN (t)) 787 { 788 tree var = TREE_VALUE (t); 789 790 if (TREE_CODE (var) == VAR_DECL 791 && is_global_var (var) 792 && (ann = var_ann (var)) != NULL 793 && ann->used) 794 mark_all_vars_used (&DECL_INITIAL (var), global_unused_vars); 795 } 796 797 for (cell = &cfun->local_decls; *cell; ) 798 { 799 tree var = TREE_VALUE (*cell); 800 801 if (TREE_CODE (var) == VAR_DECL 802 && is_global_var (var) 803 && bitmap_bit_p (global_unused_vars, DECL_UID (var))) 804 *cell = TREE_CHAIN (*cell); 805 else 806 cell = &TREE_CHAIN (*cell); 807 } 808 BITMAP_FREE (global_unused_vars); 809 } 810 811 /* Remove unused variables from REFERENCED_VARs. As a special 812 exception keep the variables that are believed to be aliased. 813 Those can't be easily removed from the alias sets and operand 814 caches. They will be removed shortly after the next may_alias 815 pass is performed. */ 816 FOR_EACH_REFERENCED_VAR (t, rvi) 817 if (!is_global_var (t) 818 && TREE_CODE (t) != PARM_DECL 819 && TREE_CODE (t) != RESULT_DECL 820 && !(ann = var_ann (t))->used 821 && !ann->is_heapvar 822 && !TREE_ADDRESSABLE (t)) 823 remove_referenced_var (t); 824 remove_unused_scope_block_p (DECL_INITIAL (current_function_decl)); 825 if (dump_file && (dump_flags & TDF_DETAILS)) 826 { 827 fprintf (dump_file, "Scope blocks after cleanups:\n"); 828 dump_scope_blocks (dump_file, dump_flags); 829 } 830} 831 832 833/* Allocate and return a new live range information object base on MAP. */ 834 835static tree_live_info_p 836new_tree_live_info (var_map map) 837{ 838 tree_live_info_p live; 839 unsigned x; 840 841 live = (tree_live_info_p) xmalloc (sizeof (struct tree_live_info_d)); 842 live->map = map; 843 live->num_blocks = last_basic_block; 844 845 live->livein = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); 846 for (x = 0; x < (unsigned)last_basic_block; x++) 847 live->livein[x] = BITMAP_ALLOC (NULL); 848 849 live->liveout = (bitmap *)xmalloc (last_basic_block * sizeof (bitmap)); 850 for (x = 0; x < (unsigned)last_basic_block; x++) 851 live->liveout[x] = BITMAP_ALLOC (NULL); 852 853 live->work_stack = XNEWVEC (int, last_basic_block); 854 live->stack_top = live->work_stack; 855 856 live->global = BITMAP_ALLOC (NULL); 857 return live; 858} 859 860 861/* Free storage for live range info object LIVE. */ 862 863void 864delete_tree_live_info (tree_live_info_p live) 865{ 866 int x; 867 868 BITMAP_FREE (live->global); 869 free (live->work_stack); 870 871 for (x = live->num_blocks - 1; x >= 0; x--) 872 BITMAP_FREE (live->liveout[x]); 873 free (live->liveout); 874 875 for (x = live->num_blocks - 1; x >= 0; x--) 876 BITMAP_FREE (live->livein[x]); 877 free (live->livein); 878 879 free (live); 880} 881 882 883/* Visit basic block BB and propagate any required live on entry bits from 884 LIVE into the predecessors. VISITED is the bitmap of visited blocks. 885 TMP is a temporary work bitmap which is passed in to avoid reallocating 886 it each time. */ 887 888static void 889loe_visit_block (tree_live_info_p live, basic_block bb, sbitmap visited, 890 bitmap tmp) 891{ 892 edge e; 893 bool change; 894 edge_iterator ei; 895 basic_block pred_bb; 896 bitmap loe; 897 gcc_assert (!TEST_BIT (visited, bb->index)); 898 899 SET_BIT (visited, bb->index); 900 loe = live_on_entry (live, bb); 901 902 FOR_EACH_EDGE (e, ei, bb->preds) 903 { 904 pred_bb = e->src; 905 if (pred_bb == ENTRY_BLOCK_PTR) 906 continue; 907 /* TMP is variables live-on-entry from BB that aren't defined in the 908 predecessor block. This should be the live on entry vars to pred. 909 Note that liveout is the DEFs in a block while live on entry is 910 being calculated. */ 911 bitmap_and_compl (tmp, loe, live->liveout[pred_bb->index]); 912 913 /* Add these bits to live-on-entry for the pred. if there are any 914 changes, and pred_bb has been visited already, add it to the 915 revisit stack. */ 916 change = bitmap_ior_into (live_on_entry (live, pred_bb), tmp); 917 if (TEST_BIT (visited, pred_bb->index) && change) 918 { 919 RESET_BIT (visited, pred_bb->index); 920 *(live->stack_top)++ = pred_bb->index; 921 } 922 } 923} 924 925 926/* Using LIVE, fill in all the live-on-entry blocks between the defs and uses 927 of all the variables. */ 928 929static void 930live_worklist (tree_live_info_p live) 931{ 932 unsigned b; 933 basic_block bb; 934 sbitmap visited = sbitmap_alloc (last_basic_block + 1); 935 bitmap tmp = BITMAP_ALLOC (NULL); 936 937 sbitmap_zero (visited); 938 939 /* Visit all the blocks in reverse order and propagate live on entry values 940 into the predecessors blocks. */ 941 FOR_EACH_BB_REVERSE (bb) 942 loe_visit_block (live, bb, visited, tmp); 943 944 /* Process any blocks which require further iteration. */ 945 while (live->stack_top != live->work_stack) 946 { 947 b = *--(live->stack_top); 948 loe_visit_block (live, BASIC_BLOCK (b), visited, tmp); 949 } 950 951 BITMAP_FREE (tmp); 952 sbitmap_free (visited); 953} 954 955 956/* Calculate the initial live on entry vector for SSA_NAME using immediate_use 957 links. Set the live on entry fields in LIVE. Def's are marked temporarily 958 in the liveout vector. */ 959 960static void 961set_var_live_on_entry (tree ssa_name, tree_live_info_p live) 962{ 963 int p; 964 gimple stmt; 965 use_operand_p use; 966 basic_block def_bb = NULL; 967 imm_use_iterator imm_iter; 968 bool global = false; 969 970 p = var_to_partition (live->map, ssa_name); 971 if (p == NO_PARTITION) 972 return; 973 974 stmt = SSA_NAME_DEF_STMT (ssa_name); 975 if (stmt) 976 { 977 def_bb = gimple_bb (stmt); 978 /* Mark defs in liveout bitmap temporarily. */ 979 if (def_bb) 980 bitmap_set_bit (live->liveout[def_bb->index], p); 981 } 982 else 983 def_bb = ENTRY_BLOCK_PTR; 984 985 /* Visit each use of SSA_NAME and if it isn't in the same block as the def, 986 add it to the list of live on entry blocks. */ 987 FOR_EACH_IMM_USE_FAST (use, imm_iter, ssa_name) 988 { 989 gimple use_stmt = USE_STMT (use); 990 basic_block add_block = NULL; 991 992 if (gimple_code (use_stmt) == GIMPLE_PHI) 993 { 994 /* Uses in PHI's are considered to be live at exit of the SRC block 995 as this is where a copy would be inserted. Check to see if it is 996 defined in that block, or whether its live on entry. */ 997 int index = PHI_ARG_INDEX_FROM_USE (use); 998 edge e = gimple_phi_arg_edge (use_stmt, index); 999 if (e->src != ENTRY_BLOCK_PTR) 1000 { 1001 if (e->src != def_bb) 1002 add_block = e->src; 1003 } 1004 } 1005 else if (is_gimple_debug (use_stmt)) 1006 continue; 1007 else 1008 { 1009 /* If its not defined in this block, its live on entry. */ 1010 basic_block use_bb = gimple_bb (use_stmt); 1011 if (use_bb != def_bb) 1012 add_block = use_bb; 1013 } 1014 1015 /* If there was a live on entry use, set the bit. */ 1016 if (add_block) 1017 { 1018 global = true; 1019 bitmap_set_bit (live->livein[add_block->index], p); 1020 } 1021 } 1022 1023 /* If SSA_NAME is live on entry to at least one block, fill in all the live 1024 on entry blocks between the def and all the uses. */ 1025 if (global) 1026 bitmap_set_bit (live->global, p); 1027} 1028 1029 1030/* Calculate the live on exit vectors based on the entry info in LIVEINFO. */ 1031 1032void 1033calculate_live_on_exit (tree_live_info_p liveinfo) 1034{ 1035 basic_block bb; 1036 edge e; 1037 edge_iterator ei; 1038 1039 /* live on entry calculations used liveout vectors for defs, clear them. */ 1040 FOR_EACH_BB (bb) 1041 bitmap_clear (liveinfo->liveout[bb->index]); 1042 1043 /* Set all the live-on-exit bits for uses in PHIs. */ 1044 FOR_EACH_BB (bb) 1045 { 1046 gimple_stmt_iterator gsi; 1047 size_t i; 1048 1049 /* Mark the PHI arguments which are live on exit to the pred block. */ 1050 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1051 { 1052 gimple phi = gsi_stmt (gsi); 1053 for (i = 0; i < gimple_phi_num_args (phi); i++) 1054 { 1055 tree t = PHI_ARG_DEF (phi, i); 1056 int p; 1057 1058 if (TREE_CODE (t) != SSA_NAME) 1059 continue; 1060 1061 p = var_to_partition (liveinfo->map, t); 1062 if (p == NO_PARTITION) 1063 continue; 1064 e = gimple_phi_arg_edge (phi, i); 1065 if (e->src != ENTRY_BLOCK_PTR) 1066 bitmap_set_bit (liveinfo->liveout[e->src->index], p); 1067 } 1068 } 1069 1070 /* Add each successors live on entry to this bock live on exit. */ 1071 FOR_EACH_EDGE (e, ei, bb->succs) 1072 if (e->dest != EXIT_BLOCK_PTR) 1073 bitmap_ior_into (liveinfo->liveout[bb->index], 1074 live_on_entry (liveinfo, e->dest)); 1075 } 1076} 1077 1078 1079/* Given partition map MAP, calculate all the live on entry bitmaps for 1080 each partition. Return a new live info object. */ 1081 1082tree_live_info_p 1083calculate_live_ranges (var_map map) 1084{ 1085 tree var; 1086 unsigned i; 1087 tree_live_info_p live; 1088 1089 live = new_tree_live_info (map); 1090 for (i = 0; i < num_var_partitions (map); i++) 1091 { 1092 var = partition_to_var (map, i); 1093 if (var != NULL_TREE) 1094 set_var_live_on_entry (var, live); 1095 } 1096 1097 live_worklist (live); 1098 1099#ifdef ENABLE_CHECKING 1100 verify_live_on_entry (live); 1101#endif 1102 1103 calculate_live_on_exit (live); 1104 return live; 1105} 1106 1107 1108/* Output partition map MAP to file F. */ 1109 1110void 1111dump_var_map (FILE *f, var_map map) 1112{ 1113 int t; 1114 unsigned x, y; 1115 int p; 1116 1117 fprintf (f, "\nPartition map \n\n"); 1118 1119 for (x = 0; x < map->num_partitions; x++) 1120 { 1121 if (map->view_to_partition != NULL) 1122 p = map->view_to_partition[x]; 1123 else 1124 p = x; 1125 1126 if (ssa_name (p) == NULL_TREE) 1127 continue; 1128 1129 t = 0; 1130 for (y = 1; y < num_ssa_names; y++) 1131 { 1132 p = partition_find (map->var_partition, y); 1133 if (map->partition_to_view) 1134 p = map->partition_to_view[p]; 1135 if (p == (int)x) 1136 { 1137 if (t++ == 0) 1138 { 1139 fprintf(f, "Partition %d (", x); 1140 print_generic_expr (f, partition_to_var (map, p), TDF_SLIM); 1141 fprintf (f, " - "); 1142 } 1143 fprintf (f, "%d ", y); 1144 } 1145 } 1146 if (t != 0) 1147 fprintf (f, ")\n"); 1148 } 1149 fprintf (f, "\n"); 1150} 1151 1152 1153/* Output live range info LIVE to file F, controlled by FLAG. */ 1154 1155void 1156dump_live_info (FILE *f, tree_live_info_p live, int flag) 1157{ 1158 basic_block bb; 1159 unsigned i; 1160 var_map map = live->map; 1161 bitmap_iterator bi; 1162 1163 if ((flag & LIVEDUMP_ENTRY) && live->livein) 1164 { 1165 FOR_EACH_BB (bb) 1166 { 1167 fprintf (f, "\nLive on entry to BB%d : ", bb->index); 1168 EXECUTE_IF_SET_IN_BITMAP (live->livein[bb->index], 0, i, bi) 1169 { 1170 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); 1171 fprintf (f, " "); 1172 } 1173 fprintf (f, "\n"); 1174 } 1175 } 1176 1177 if ((flag & LIVEDUMP_EXIT) && live->liveout) 1178 { 1179 FOR_EACH_BB (bb) 1180 { 1181 fprintf (f, "\nLive on exit from BB%d : ", bb->index); 1182 EXECUTE_IF_SET_IN_BITMAP (live->liveout[bb->index], 0, i, bi) 1183 { 1184 print_generic_expr (f, partition_to_var (map, i), TDF_SLIM); 1185 fprintf (f, " "); 1186 } 1187 fprintf (f, "\n"); 1188 } 1189 } 1190} 1191 1192 1193#ifdef ENABLE_CHECKING 1194/* Verify that SSA_VAR is a non-virtual SSA_NAME. */ 1195 1196void 1197register_ssa_partition_check (tree ssa_var) 1198{ 1199 gcc_assert (TREE_CODE (ssa_var) == SSA_NAME); 1200 if (!is_gimple_reg (SSA_NAME_VAR (ssa_var))) 1201 { 1202 fprintf (stderr, "Illegally registering a virtual SSA name :"); 1203 print_generic_expr (stderr, ssa_var, TDF_SLIM); 1204 fprintf (stderr, " in the SSA->Normal phase.\n"); 1205 internal_error ("SSA corruption"); 1206 } 1207} 1208 1209 1210/* Verify that the info in LIVE matches the current cfg. */ 1211 1212static void 1213verify_live_on_entry (tree_live_info_p live) 1214{ 1215 unsigned i; 1216 tree var; 1217 gimple stmt; 1218 basic_block bb; 1219 edge e; 1220 int num; 1221 edge_iterator ei; 1222 var_map map = live->map; 1223 1224 /* Check for live on entry partitions and report those with a DEF in 1225 the program. This will typically mean an optimization has done 1226 something wrong. */ 1227 bb = ENTRY_BLOCK_PTR; 1228 num = 0; 1229 FOR_EACH_EDGE (e, ei, bb->succs) 1230 { 1231 int entry_block = e->dest->index; 1232 if (e->dest == EXIT_BLOCK_PTR) 1233 continue; 1234 for (i = 0; i < (unsigned)num_var_partitions (map); i++) 1235 { 1236 basic_block tmp; 1237 tree d; 1238 bitmap loe; 1239 var = partition_to_var (map, i); 1240 stmt = SSA_NAME_DEF_STMT (var); 1241 tmp = gimple_bb (stmt); 1242 d = gimple_default_def (cfun, SSA_NAME_VAR (var)); 1243 1244 loe = live_on_entry (live, e->dest); 1245 if (loe && bitmap_bit_p (loe, i)) 1246 { 1247 if (!gimple_nop_p (stmt)) 1248 { 1249 num++; 1250 print_generic_expr (stderr, var, TDF_SLIM); 1251 fprintf (stderr, " is defined "); 1252 if (tmp) 1253 fprintf (stderr, " in BB%d, ", tmp->index); 1254 fprintf (stderr, "by:\n"); 1255 print_gimple_stmt (stderr, stmt, 0, TDF_SLIM); 1256 fprintf (stderr, "\nIt is also live-on-entry to entry BB %d", 1257 entry_block); 1258 fprintf (stderr, " So it appears to have multiple defs.\n"); 1259 } 1260 else 1261 { 1262 if (d != var) 1263 { 1264 num++; 1265 print_generic_expr (stderr, var, TDF_SLIM); 1266 fprintf (stderr, " is live-on-entry to BB%d ", 1267 entry_block); 1268 if (d) 1269 { 1270 fprintf (stderr, " but is not the default def of "); 1271 print_generic_expr (stderr, d, TDF_SLIM); 1272 fprintf (stderr, "\n"); 1273 } 1274 else 1275 fprintf (stderr, " and there is no default def.\n"); 1276 } 1277 } 1278 } 1279 else 1280 if (d == var) 1281 { 1282 /* The only way this var shouldn't be marked live on entry is 1283 if it occurs in a PHI argument of the block. */ 1284 size_t z; 1285 bool ok = false; 1286 gimple_stmt_iterator gsi; 1287 for (gsi = gsi_start_phis (e->dest); 1288 !gsi_end_p (gsi) && !ok; 1289 gsi_next (&gsi)) 1290 { 1291 gimple phi = gsi_stmt (gsi); 1292 for (z = 0; z < gimple_phi_num_args (phi); z++) 1293 if (var == gimple_phi_arg_def (phi, z)) 1294 { 1295 ok = true; 1296 break; 1297 } 1298 } 1299 if (ok) 1300 continue; 1301 num++; 1302 print_generic_expr (stderr, var, TDF_SLIM); 1303 fprintf (stderr, " is not marked live-on-entry to entry BB%d ", 1304 entry_block); 1305 fprintf (stderr, "but it is a default def so it should be.\n"); 1306 } 1307 } 1308 } 1309 gcc_assert (num <= 0); 1310} 1311#endif 1312