1/* Generic routines for manipulating SSA_NAME expressions 2 Copyright (C) 2003-2015 Free Software Foundation, Inc. 3 4This file is part of GCC. 5 6GCC is free software; you can redistribute it and/or modify 7it under the terms of the GNU General Public License as published by 8the Free Software Foundation; either version 3, or (at your option) 9any later version. 10 11GCC is distributed in the hope that it will be useful, 12but WITHOUT ANY WARRANTY; without even the implied warranty of 13MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14GNU General Public License for more details. 15 16You should have received a copy of the GNU General Public License 17along with GCC; see the file COPYING3. If not see 18<http://www.gnu.org/licenses/>. */ 19 20#include "config.h" 21#include "system.h" 22#include "coretypes.h" 23#include "tm.h" 24#include "hash-set.h" 25#include "machmode.h" 26#include "vec.h" 27#include "double-int.h" 28#include "input.h" 29#include "alias.h" 30#include "symtab.h" 31#include "wide-int.h" 32#include "inchash.h" 33#include "tree.h" 34#include "fold-const.h" 35#include "stor-layout.h" 36#include "predict.h" 37#include "hard-reg-set.h" 38#include "input.h" 39#include "function.h" 40#include "basic-block.h" 41#include "tree-ssa-alias.h" 42#include "internal-fn.h" 43#include "gimple-expr.h" 44#include "is-a.h" 45#include "gimple.h" 46#include "gimple-ssa.h" 47#include "gimple-iterator.h" 48#include "tree-phinodes.h" 49#include "ssa-iterators.h" 50#include "stringpool.h" 51#include "tree-ssanames.h" 52#include "tree-into-ssa.h" 53#include "tree-ssa.h" 54#include "tree-pass.h" 55 56/* Rewriting a function into SSA form can create a huge number of SSA_NAMEs, 57 many of which may be thrown away shortly after their creation if jumps 58 were threaded through PHI nodes. 59 60 While our garbage collection mechanisms will handle this situation, it 61 is extremely wasteful to create nodes and throw them away, especially 62 when the nodes can be reused. 63 64 For PR 8361, we can significantly reduce the number of nodes allocated 65 and thus the total amount of memory allocated by managing SSA_NAMEs a 66 little. This additionally helps reduce the amount of work done by the 67 garbage collector. Similar results have been seen on a wider variety 68 of tests (such as the compiler itself). 69 70 Right now we maintain our free list on a per-function basis. It may 71 or may not make sense to maintain the free list for the duration of 72 a compilation unit. 73 74 External code should rely solely upon HIGHEST_SSA_VERSION and the 75 externally defined functions. External code should not know about 76 the details of the free list management. 77 78 External code should also not assume the version number on nodes is 79 monotonically increasing. We reuse the version number when we 80 reuse an SSA_NAME expression. This helps keep arrays and bitmaps 81 more compact. */ 82 83 84/* Version numbers with special meanings. We start allocating new version 85 numbers after the special ones. */ 86#define UNUSED_NAME_VERSION 0 87 88unsigned int ssa_name_nodes_reused; 89unsigned int ssa_name_nodes_created; 90 91#define FREE_SSANAMES(fun) (fun)->gimple_df->free_ssanames 92 93 94/* Initialize management of SSA_NAMEs to default SIZE. If SIZE is 95 zero use default. */ 96 97void 98init_ssanames (struct function *fn, int size) 99{ 100 if (size < 50) 101 size = 50; 102 103 vec_alloc (SSANAMES (fn), size); 104 105 /* Version 0 is special, so reserve the first slot in the table. Though 106 currently unused, we may use version 0 in alias analysis as part of 107 the heuristics used to group aliases when the alias sets are too 108 large. 109 110 We use vec::quick_push here because we know that SSA_NAMES has at 111 least 50 elements reserved in it. */ 112 SSANAMES (fn)->quick_push (NULL_TREE); 113 FREE_SSANAMES (fn) = NULL; 114 115 fn->gimple_df->ssa_renaming_needed = 0; 116 fn->gimple_df->rename_vops = 0; 117} 118 119/* Finalize management of SSA_NAMEs. */ 120 121void 122fini_ssanames (void) 123{ 124 vec_free (SSANAMES (cfun)); 125 vec_free (FREE_SSANAMES (cfun)); 126} 127 128/* Dump some simple statistics regarding the re-use of SSA_NAME nodes. */ 129 130void 131ssanames_print_statistics (void) 132{ 133 fprintf (stderr, "SSA_NAME nodes allocated: %u\n", ssa_name_nodes_created); 134 fprintf (stderr, "SSA_NAME nodes reused: %u\n", ssa_name_nodes_reused); 135} 136 137/* Return an SSA_NAME node for variable VAR defined in statement STMT 138 in function FN. STMT may be an empty statement for artificial 139 references (e.g., default definitions created when a variable is 140 used without a preceding definition). */ 141 142tree 143make_ssa_name_fn (struct function *fn, tree var, gimple stmt) 144{ 145 tree t; 146 use_operand_p imm; 147 148 gcc_assert (TREE_CODE (var) == VAR_DECL 149 || TREE_CODE (var) == PARM_DECL 150 || TREE_CODE (var) == RESULT_DECL 151 || (TYPE_P (var) && is_gimple_reg_type (var))); 152 153 /* If our free list has an element, then use it. */ 154 if (!vec_safe_is_empty (FREE_SSANAMES (fn))) 155 { 156 t = FREE_SSANAMES (fn)->pop (); 157 if (GATHER_STATISTICS) 158 ssa_name_nodes_reused++; 159 160 /* The node was cleared out when we put it on the free list, so 161 there is no need to do so again here. */ 162 gcc_assert ((*SSANAMES (fn))[SSA_NAME_VERSION (t)] == NULL); 163 (*SSANAMES (fn))[SSA_NAME_VERSION (t)] = t; 164 } 165 else 166 { 167 t = make_node (SSA_NAME); 168 SSA_NAME_VERSION (t) = SSANAMES (fn)->length (); 169 vec_safe_push (SSANAMES (fn), t); 170 if (GATHER_STATISTICS) 171 ssa_name_nodes_created++; 172 } 173 174 if (TYPE_P (var)) 175 { 176 TREE_TYPE (t) = var; 177 SET_SSA_NAME_VAR_OR_IDENTIFIER (t, NULL_TREE); 178 } 179 else 180 { 181 TREE_TYPE (t) = TREE_TYPE (var); 182 SET_SSA_NAME_VAR_OR_IDENTIFIER (t, var); 183 } 184 SSA_NAME_DEF_STMT (t) = stmt; 185 if (POINTER_TYPE_P (TREE_TYPE (t))) 186 SSA_NAME_PTR_INFO (t) = NULL; 187 else 188 SSA_NAME_RANGE_INFO (t) = NULL; 189 190 SSA_NAME_IN_FREE_LIST (t) = 0; 191 SSA_NAME_IS_DEFAULT_DEF (t) = 0; 192 imm = &(SSA_NAME_IMM_USE_NODE (t)); 193 imm->use = NULL; 194 imm->prev = imm; 195 imm->next = imm; 196 imm->loc.ssa_name = t; 197 198 return t; 199} 200 201/* Store range information RANGE_TYPE, MIN, and MAX to tree ssa_name NAME. */ 202 203void 204set_range_info (tree name, enum value_range_type range_type, 205 const wide_int_ref &min, const wide_int_ref &max) 206{ 207 gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); 208 gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); 209 range_info_def *ri = SSA_NAME_RANGE_INFO (name); 210 unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); 211 212 /* Allocate if not available. */ 213 if (ri == NULL) 214 { 215 size_t size = (sizeof (range_info_def) 216 + trailing_wide_ints <3>::extra_size (precision)); 217 ri = static_cast<range_info_def *> (ggc_internal_alloc (size)); 218 ri->ints.set_precision (precision); 219 SSA_NAME_RANGE_INFO (name) = ri; 220 ri->set_nonzero_bits (wi::shwi (-1, precision)); 221 } 222 223 /* Record the range type. */ 224 if (SSA_NAME_RANGE_TYPE (name) != range_type) 225 SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); 226 227 /* Set the values. */ 228 ri->set_min (min); 229 ri->set_max (max); 230 231 /* If it is a range, try to improve nonzero_bits from the min/max. */ 232 if (range_type == VR_RANGE) 233 { 234 wide_int xorv = ri->get_min () ^ ri->get_max (); 235 if (xorv != 0) 236 xorv = wi::mask (precision - wi::clz (xorv), false, precision); 237 ri->set_nonzero_bits (ri->get_nonzero_bits () & (ri->get_min () | xorv)); 238 } 239} 240 241 242/* Gets range information MIN, MAX and returns enum value_range_type 243 corresponding to tree ssa_name NAME. enum value_range_type returned 244 is used to determine if MIN and MAX are valid values. */ 245 246enum value_range_type 247get_range_info (const_tree name, wide_int *min, wide_int *max) 248{ 249 gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); 250 gcc_assert (min && max); 251 range_info_def *ri = SSA_NAME_RANGE_INFO (name); 252 253 /* Return VR_VARYING for SSA_NAMEs with NULL RANGE_INFO or SSA_NAMEs 254 with integral types width > 2 * HOST_BITS_PER_WIDE_INT precision. */ 255 if (!ri || (GET_MODE_PRECISION (TYPE_MODE (TREE_TYPE (name))) 256 > 2 * HOST_BITS_PER_WIDE_INT)) 257 return VR_VARYING; 258 259 *min = ri->get_min (); 260 *max = ri->get_max (); 261 return SSA_NAME_RANGE_TYPE (name); 262} 263 264/* Change non-zero bits bitmask of NAME. */ 265 266void 267set_nonzero_bits (tree name, const wide_int_ref &mask) 268{ 269 gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); 270 if (SSA_NAME_RANGE_INFO (name) == NULL) 271 set_range_info (name, VR_RANGE, 272 TYPE_MIN_VALUE (TREE_TYPE (name)), 273 TYPE_MAX_VALUE (TREE_TYPE (name))); 274 range_info_def *ri = SSA_NAME_RANGE_INFO (name); 275 ri->set_nonzero_bits (mask); 276} 277 278/* Return a widest_int with potentially non-zero bits in SSA_NAME 279 NAME, or -1 if unknown. */ 280 281wide_int 282get_nonzero_bits (const_tree name) 283{ 284 unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); 285 if (POINTER_TYPE_P (TREE_TYPE (name))) 286 { 287 struct ptr_info_def *pi = SSA_NAME_PTR_INFO (name); 288 if (pi && pi->align) 289 return wi::shwi (-(HOST_WIDE_INT) pi->align 290 | (HOST_WIDE_INT) pi->misalign, precision); 291 return wi::shwi (-1, precision); 292 } 293 294 range_info_def *ri = SSA_NAME_RANGE_INFO (name); 295 if (!ri) 296 return wi::shwi (-1, precision); 297 298 return ri->get_nonzero_bits (); 299} 300 301/* We no longer need the SSA_NAME expression VAR, release it so that 302 it may be reused. 303 304 Note it is assumed that no calls to make_ssa_name will be made 305 until all uses of the ssa name are released and that the only 306 use of the SSA_NAME expression is to check its SSA_NAME_VAR. All 307 other fields must be assumed clobbered. */ 308 309void 310release_ssa_name_fn (struct function *fn, tree var) 311{ 312 if (!var) 313 return; 314 315 /* Never release the default definition for a symbol. It's a 316 special SSA name that should always exist once it's created. */ 317 if (SSA_NAME_IS_DEFAULT_DEF (var)) 318 return; 319 320 /* If VAR has been registered for SSA updating, don't remove it. 321 After update_ssa has run, the name will be released. */ 322 if (name_registered_for_update_p (var)) 323 { 324 release_ssa_name_after_update_ssa (var); 325 return; 326 } 327 328 /* release_ssa_name can be called multiple times on a single SSA_NAME. 329 However, it should only end up on our free list one time. We 330 keep a status bit in the SSA_NAME node itself to indicate it has 331 been put on the free list. 332 333 Note that once on the freelist you can not reference the SSA_NAME's 334 defining statement. */ 335 if (! SSA_NAME_IN_FREE_LIST (var)) 336 { 337 tree saved_ssa_name_var = SSA_NAME_VAR (var); 338 int saved_ssa_name_version = SSA_NAME_VERSION (var); 339 use_operand_p imm = &(SSA_NAME_IMM_USE_NODE (var)); 340 341 if (MAY_HAVE_DEBUG_STMTS) 342 insert_debug_temp_for_var_def (NULL, var); 343 344#ifdef ENABLE_CHECKING 345 verify_imm_links (stderr, var); 346#endif 347 while (imm->next != imm) 348 delink_imm_use (imm->next); 349 350 (*SSANAMES (fn))[SSA_NAME_VERSION (var)] = NULL_TREE; 351 memset (var, 0, tree_size (var)); 352 353 imm->prev = imm; 354 imm->next = imm; 355 imm->loc.ssa_name = var; 356 357 /* First put back the right tree node so that the tree checking 358 macros do not complain. */ 359 TREE_SET_CODE (var, SSA_NAME); 360 361 /* Restore the version number. */ 362 SSA_NAME_VERSION (var) = saved_ssa_name_version; 363 364 /* Hopefully this can go away once we have the new incremental 365 SSA updating code installed. */ 366 SET_SSA_NAME_VAR_OR_IDENTIFIER (var, saved_ssa_name_var); 367 368 /* Note this SSA_NAME is now in the first list. */ 369 SSA_NAME_IN_FREE_LIST (var) = 1; 370 371 /* And finally put it on the free list. */ 372 vec_safe_push (FREE_SSANAMES (fn), var); 373 } 374} 375 376/* If the alignment of the pointer described by PI is known, return true and 377 store the alignment and the deviation from it into *ALIGNP and *MISALIGNP 378 respectively. Otherwise return false. */ 379 380bool 381get_ptr_info_alignment (struct ptr_info_def *pi, unsigned int *alignp, 382 unsigned int *misalignp) 383{ 384 if (pi->align) 385 { 386 *alignp = pi->align; 387 *misalignp = pi->misalign; 388 return true; 389 } 390 else 391 return false; 392} 393 394/* State that the pointer described by PI has unknown alignment. */ 395 396void 397mark_ptr_info_alignment_unknown (struct ptr_info_def *pi) 398{ 399 pi->align = 0; 400 pi->misalign = 0; 401} 402 403/* Store the the power-of-two byte alignment and the deviation from that 404 alignment of pointer described by PI to ALIOGN and MISALIGN 405 respectively. */ 406 407void 408set_ptr_info_alignment (struct ptr_info_def *pi, unsigned int align, 409 unsigned int misalign) 410{ 411 gcc_checking_assert (align != 0); 412 gcc_assert ((align & (align - 1)) == 0); 413 gcc_assert ((misalign & ~(align - 1)) == 0); 414 415 pi->align = align; 416 pi->misalign = misalign; 417} 418 419/* If pointer described by PI has known alignment, increase its known 420 misalignment by INCREMENT modulo its current alignment. */ 421 422void 423adjust_ptr_info_misalignment (struct ptr_info_def *pi, 424 unsigned int increment) 425{ 426 if (pi->align != 0) 427 { 428 pi->misalign += increment; 429 pi->misalign &= (pi->align - 1); 430 } 431} 432 433/* Return the alias information associated with pointer T. It creates a 434 new instance if none existed. */ 435 436struct ptr_info_def * 437get_ptr_info (tree t) 438{ 439 struct ptr_info_def *pi; 440 441 gcc_assert (POINTER_TYPE_P (TREE_TYPE (t))); 442 443 pi = SSA_NAME_PTR_INFO (t); 444 if (pi == NULL) 445 { 446 pi = ggc_cleared_alloc<ptr_info_def> (); 447 pt_solution_reset (&pi->pt); 448 mark_ptr_info_alignment_unknown (pi); 449 SSA_NAME_PTR_INFO (t) = pi; 450 } 451 452 return pi; 453} 454 455 456/* Creates a new SSA name using the template NAME tobe defined by 457 statement STMT in function FN. */ 458 459tree 460copy_ssa_name_fn (struct function *fn, tree name, gimple stmt) 461{ 462 tree new_name; 463 464 if (SSA_NAME_VAR (name)) 465 new_name = make_ssa_name_fn (fn, SSA_NAME_VAR (name), stmt); 466 else 467 { 468 new_name = make_ssa_name_fn (fn, TREE_TYPE (name), stmt); 469 SET_SSA_NAME_VAR_OR_IDENTIFIER (new_name, SSA_NAME_IDENTIFIER (name)); 470 } 471 472 return new_name; 473} 474 475 476/* Creates a duplicate of the ptr_info_def at PTR_INFO for use by 477 the SSA name NAME. */ 478 479void 480duplicate_ssa_name_ptr_info (tree name, struct ptr_info_def *ptr_info) 481{ 482 struct ptr_info_def *new_ptr_info; 483 484 gcc_assert (POINTER_TYPE_P (TREE_TYPE (name))); 485 gcc_assert (!SSA_NAME_PTR_INFO (name)); 486 487 if (!ptr_info) 488 return; 489 490 new_ptr_info = ggc_alloc<ptr_info_def> (); 491 *new_ptr_info = *ptr_info; 492 493 SSA_NAME_PTR_INFO (name) = new_ptr_info; 494} 495 496/* Creates a duplicate of the range_info_def at RANGE_INFO of type 497 RANGE_TYPE for use by the SSA name NAME. */ 498void 499duplicate_ssa_name_range_info (tree name, enum value_range_type range_type, 500 struct range_info_def *range_info) 501{ 502 struct range_info_def *new_range_info; 503 504 gcc_assert (!POINTER_TYPE_P (TREE_TYPE (name))); 505 gcc_assert (!SSA_NAME_RANGE_INFO (name)); 506 507 if (!range_info) 508 return; 509 510 unsigned int precision = TYPE_PRECISION (TREE_TYPE (name)); 511 size_t size = (sizeof (range_info_def) 512 + trailing_wide_ints <3>::extra_size (precision)); 513 new_range_info = static_cast<range_info_def *> (ggc_internal_alloc (size)); 514 memcpy (new_range_info, range_info, size); 515 516 gcc_assert (range_type == VR_RANGE || range_type == VR_ANTI_RANGE); 517 SSA_NAME_ANTI_RANGE_P (name) = (range_type == VR_ANTI_RANGE); 518 SSA_NAME_RANGE_INFO (name) = new_range_info; 519} 520 521 522 523/* Creates a duplicate of a ssa name NAME tobe defined by statement STMT 524 in function FN. */ 525 526tree 527duplicate_ssa_name_fn (struct function *fn, tree name, gimple stmt) 528{ 529 tree new_name = copy_ssa_name_fn (fn, name, stmt); 530 if (POINTER_TYPE_P (TREE_TYPE (name))) 531 { 532 struct ptr_info_def *old_ptr_info = SSA_NAME_PTR_INFO (name); 533 534 if (old_ptr_info) 535 duplicate_ssa_name_ptr_info (new_name, old_ptr_info); 536 } 537 else 538 { 539 struct range_info_def *old_range_info = SSA_NAME_RANGE_INFO (name); 540 541 if (old_range_info) 542 duplicate_ssa_name_range_info (new_name, SSA_NAME_RANGE_TYPE (name), 543 old_range_info); 544 } 545 546 return new_name; 547} 548 549 550/* Reset all flow sensitive data on NAME such as range-info, nonzero 551 bits and alignment. */ 552 553void 554reset_flow_sensitive_info (tree name) 555{ 556 if (POINTER_TYPE_P (TREE_TYPE (name))) 557 { 558 /* points-to info is not flow-sensitive. */ 559 if (SSA_NAME_PTR_INFO (name)) 560 mark_ptr_info_alignment_unknown (SSA_NAME_PTR_INFO (name)); 561 } 562 else 563 SSA_NAME_RANGE_INFO (name) = NULL; 564} 565 566/* Clear all flow sensitive data from all statements and PHI definitions 567 in BB. */ 568 569void 570reset_flow_sensitive_info_in_bb (basic_block bb) 571{ 572 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); 573 gsi_next (&gsi)) 574 { 575 gimple stmt = gsi_stmt (gsi); 576 ssa_op_iter i; 577 tree op; 578 FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF) 579 reset_flow_sensitive_info (op); 580 } 581 582 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); 583 gsi_next (&gsi)) 584 { 585 tree phi_def = gimple_phi_result (gsi.phi ()); 586 reset_flow_sensitive_info (phi_def); 587 } 588} 589 590/* Release all the SSA_NAMEs created by STMT. */ 591 592void 593release_defs (gimple stmt) 594{ 595 tree def; 596 ssa_op_iter iter; 597 598 /* Make sure that we are in SSA. Otherwise, operand cache may point 599 to garbage. */ 600 gcc_assert (gimple_in_ssa_p (cfun)); 601 602 FOR_EACH_SSA_TREE_OPERAND (def, stmt, iter, SSA_OP_ALL_DEFS) 603 if (TREE_CODE (def) == SSA_NAME) 604 release_ssa_name (def); 605} 606 607 608/* Replace the symbol associated with SSA_NAME with SYM. */ 609 610void 611replace_ssa_name_symbol (tree ssa_name, tree sym) 612{ 613 SET_SSA_NAME_VAR_OR_IDENTIFIER (ssa_name, sym); 614 TREE_TYPE (ssa_name) = TREE_TYPE (sym); 615} 616 617/* Return SSA names that are unused to GGC memory and compact the SSA 618 version namespace. This is used to keep footprint of compiler during 619 interprocedural optimization. */ 620 621namespace { 622 623const pass_data pass_data_release_ssa_names = 624{ 625 GIMPLE_PASS, /* type */ 626 "release_ssa", /* name */ 627 OPTGROUP_NONE, /* optinfo_flags */ 628 TV_TREE_SSA_OTHER, /* tv_id */ 629 PROP_ssa, /* properties_required */ 630 0, /* properties_provided */ 631 0, /* properties_destroyed */ 632 TODO_remove_unused_locals, /* todo_flags_start */ 633 0, /* todo_flags_finish */ 634}; 635 636class pass_release_ssa_names : public gimple_opt_pass 637{ 638public: 639 pass_release_ssa_names (gcc::context *ctxt) 640 : gimple_opt_pass (pass_data_release_ssa_names, ctxt) 641 {} 642 643 /* opt_pass methods: */ 644 virtual unsigned int execute (function *); 645 646}; // class pass_release_ssa_names 647 648unsigned int 649pass_release_ssa_names::execute (function *fun) 650{ 651 unsigned i, j; 652 int n = vec_safe_length (FREE_SSANAMES (fun)); 653 654 /* Now release the freelist. */ 655 vec_free (FREE_SSANAMES (fun)); 656 657 /* And compact the SSA number space. We make sure to not change the 658 relative order of SSA versions. */ 659 for (i = 1, j = 1; i < fun->gimple_df->ssa_names->length (); ++i) 660 { 661 tree name = ssa_name (i); 662 if (name) 663 { 664 if (i != j) 665 { 666 SSA_NAME_VERSION (name) = j; 667 (*fun->gimple_df->ssa_names)[j] = name; 668 } 669 j++; 670 } 671 } 672 fun->gimple_df->ssa_names->truncate (j); 673 674 statistics_counter_event (fun, "SSA names released", n); 675 statistics_counter_event (fun, "SSA name holes removed", i - j); 676 if (dump_file) 677 fprintf (dump_file, "Released %i names, %.2f%%, removed %i holes\n", 678 n, n * 100.0 / num_ssa_names, i - j); 679 return 0; 680} 681 682} // anon namespace 683 684gimple_opt_pass * 685make_pass_release_ssa_names (gcc::context *ctxt) 686{ 687 return new pass_release_ssa_names (ctxt); 688} 689