1 /* Scalar Replacement of Aggregates (SRA) converts some structure 2 references into scalar references, exposing them to the scalar 3 optimizers. 4 Copyright (C) 2008-2015 Free Software Foundation, Inc. 5 Contributed by Martin Jambor <mjambor@suse.cz> 6 7 This file is part of GCC. 8 9 GCC is free software; you can redistribute it and/or modify it under 10 the terms of the GNU General Public License as published by the Free 11 Software Foundation; either version 3, or (at your option) any later 12 version. 13 14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY 15 WARRANTY; without even the implied warranty of MERCHANTABILITY or 16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17 for more details. 18 19 You should have received a copy of the GNU General Public License 20 along with GCC; see the file COPYING3. If not see 21 <http://www.gnu.org/licenses/>. */ 22 23 /* This file implements Scalar Reduction of Aggregates (SRA). SRA is run 24 twice, once in the early stages of compilation (early SRA) and once in the 25 late stages (late SRA). The aim of both is to turn references to scalar 26 parts of aggregates into uses of independent scalar variables. 27 28 The two passes are nearly identical, the only difference is that early SRA 29 does not scalarize unions which are used as the result in a GIMPLE_RETURN 30 statement because together with inlining this can lead to weird type 31 conversions. 32 33 Both passes operate in four stages: 34 35 1. The declarations that have properties which make them candidates for 36 scalarization are identified in function find_var_candidates(). The 37 candidates are stored in candidate_bitmap. 38 39 2. The function body is scanned. In the process, declarations which are 40 used in a manner that prevent their scalarization are removed from the 41 candidate bitmap. More importantly, for every access into an aggregate, 42 an access structure (struct access) is created by create_access() and 43 stored in a vector associated with the aggregate. Among other 44 information, the aggregate declaration, the offset and size of the access 45 and its type are stored in the structure. 46 47 On a related note, assign_link structures are created for every assign 48 statement between candidate aggregates and attached to the related 49 accesses. 50 51 3. The vectors of accesses are analyzed. They are first sorted according to 52 their offset and size and then scanned for partially overlapping accesses 53 (i.e. those which overlap but one is not entirely within another). Such 54 an access disqualifies the whole aggregate from being scalarized. 55 56 If there is no such inhibiting overlap, a representative access structure 57 is chosen for every unique combination of offset and size. Afterwards, 58 the pass builds a set of trees from these structures, in which children 59 of an access are within their parent (in terms of offset and size). 60 61 Then accesses are propagated whenever possible (i.e. in cases when it 62 does not create a partially overlapping access) across assign_links from 63 the right hand side to the left hand side. 64 65 Then the set of trees for each declaration is traversed again and those 66 accesses which should be replaced by a scalar are identified. 67 68 4. The function is traversed again, and for every reference into an 69 aggregate that has some component which is about to be scalarized, 70 statements are amended and new statements are created as necessary. 71 Finally, if a parameter got scalarized, the scalar replacements are 72 initialized with values from respective parameter aggregates. */ 73 74 #include "config.h" 75 #include "system.h" 76 #include "coretypes.h" 77 #include "hash-map.h" 78 #include "hash-table.h" 79 #include "alloc-pool.h" 80 #include "tm.h" 81 #include "hash-set.h" 82 #include "machmode.h" 83 #include "vec.h" 84 #include "double-int.h" 85 #include "input.h" 86 #include "alias.h" 87 #include "symtab.h" 88 #include "wide-int.h" 89 #include "inchash.h" 90 #include "tree.h" 91 #include "fold-const.h" 92 #include "predict.h" 93 #include "hard-reg-set.h" 94 #include "function.h" 95 #include "dominance.h" 96 #include "cfg.h" 97 #include "basic-block.h" 98 #include "tree-ssa-alias.h" 99 #include "internal-fn.h" 100 #include "tree-eh.h" 101 #include "gimple-expr.h" 102 #include "is-a.h" 103 #include "gimple.h" 104 #include "stor-layout.h" 105 #include "gimplify.h" 106 #include "gimple-iterator.h" 107 #include "gimplify-me.h" 108 #include "gimple-walk.h" 109 #include "bitmap.h" 110 #include "gimple-ssa.h" 111 #include "tree-cfg.h" 112 #include "tree-phinodes.h" 113 #include "ssa-iterators.h" 114 #include "stringpool.h" 115 #include "tree-ssanames.h" 116 #include "hashtab.h" 117 #include "rtl.h" 118 #include "flags.h" 119 #include "statistics.h" 120 #include "real.h" 121 #include "fixed-value.h" 122 #include "insn-config.h" 123 #include "expmed.h" 124 #include "dojump.h" 125 #include "explow.h" 126 #include "calls.h" 127 #include "emit-rtl.h" 128 #include "varasm.h" 129 #include "stmt.h" 130 #include "expr.h" 131 #include "tree-dfa.h" 132 #include "tree-ssa.h" 133 #include "tree-pass.h" 134 #include "plugin-api.h" 135 #include "ipa-ref.h" 136 #include "cgraph.h" 137 #include "symbol-summary.h" 138 #include "ipa-prop.h" 139 #include "params.h" 140 #include "target.h" 141 #include "dbgcnt.h" 142 #include "tree-inline.h" 143 #include "gimple-pretty-print.h" 144 #include "ipa-inline.h" 145 #include "ipa-utils.h" 146 #include "builtins.h" 147 148 /* Enumeration of all aggregate reductions we can do. */ 149 enum sra_mode { SRA_MODE_EARLY_IPA, /* early call regularization */ 150 SRA_MODE_EARLY_INTRA, /* early intraprocedural SRA */ 151 SRA_MODE_INTRA }; /* late intraprocedural SRA */ 152 153 /* Global variable describing which aggregate reduction we are performing at 154 the moment. */ 155 static enum sra_mode sra_mode; 156 157 struct assign_link; 158 159 /* ACCESS represents each access to an aggregate variable (as a whole or a 160 part). It can also represent a group of accesses that refer to exactly the 161 same fragment of an aggregate (i.e. those that have exactly the same offset 162 and size). Such representatives for a single aggregate, once determined, 163 are linked in a linked list and have the group fields set. 164 165 Moreover, when doing intraprocedural SRA, a tree is built from those 166 representatives (by the means of first_child and next_sibling pointers), in 167 which all items in a subtree are "within" the root, i.e. their offset is 168 greater or equal to offset of the root and offset+size is smaller or equal 169 to offset+size of the root. Children of an access are sorted by offset. 170 171 Note that accesses to parts of vector and complex number types always 172 represented by an access to the whole complex number or a vector. It is a 173 duty of the modifying functions to replace them appropriately. */ 174 175 struct access 176 { 177 /* Values returned by `get_ref_base_and_extent' for each component reference 178 If EXPR isn't a component reference just set `BASE = EXPR', `OFFSET = 0', 179 `SIZE = TREE_SIZE (TREE_TYPE (expr))'. */ 180 HOST_WIDE_INT offset; 181 HOST_WIDE_INT size; 182 tree base; 183 184 /* Expression. It is context dependent so do not use it to create new 185 expressions to access the original aggregate. See PR 42154 for a 186 testcase. */ 187 tree expr; 188 /* Type. */ 189 tree type; 190 191 /* The statement this access belongs to. */ 192 gimple stmt; 193 194 /* Next group representative for this aggregate. */ 195 struct access *next_grp; 196 197 /* Pointer to the group representative. Pointer to itself if the struct is 198 the representative. */ 199 struct access *group_representative; 200 201 /* If this access has any children (in terms of the definition above), this 202 points to the first one. */ 203 struct access *first_child; 204 205 /* In intraprocedural SRA, pointer to the next sibling in the access tree as 206 described above. In IPA-SRA this is a pointer to the next access 207 belonging to the same group (having the same representative). */ 208 struct access *next_sibling; 209 210 /* Pointers to the first and last element in the linked list of assign 211 links. */ 212 struct assign_link *first_link, *last_link; 213 214 /* Pointer to the next access in the work queue. */ 215 struct access *next_queued; 216 217 /* Replacement variable for this access "region." Never to be accessed 218 directly, always only by the means of get_access_replacement() and only 219 when grp_to_be_replaced flag is set. */ 220 tree replacement_decl; 221 222 /* Is this particular access write access? */ 223 unsigned write : 1; 224 225 /* Is this access an access to a non-addressable field? */ 226 unsigned non_addressable : 1; 227 228 /* Is this access currently in the work queue? */ 229 unsigned grp_queued : 1; 230 231 /* Does this group contain a write access? This flag is propagated down the 232 access tree. */ 233 unsigned grp_write : 1; 234 235 /* Does this group contain a read access? This flag is propagated down the 236 access tree. */ 237 unsigned grp_read : 1; 238 239 /* Does this group contain a read access that comes from an assignment 240 statement? This flag is propagated down the access tree. */ 241 unsigned grp_assignment_read : 1; 242 243 /* Does this group contain a write access that comes from an assignment 244 statement? This flag is propagated down the access tree. */ 245 unsigned grp_assignment_write : 1; 246 247 /* Does this group contain a read access through a scalar type? This flag is 248 not propagated in the access tree in any direction. */ 249 unsigned grp_scalar_read : 1; 250 251 /* Does this group contain a write access through a scalar type? This flag 252 is not propagated in the access tree in any direction. */ 253 unsigned grp_scalar_write : 1; 254 255 /* Is this access an artificial one created to scalarize some record 256 entirely? */ 257 unsigned grp_total_scalarization : 1; 258 259 /* Other passes of the analysis use this bit to make function 260 analyze_access_subtree create scalar replacements for this group if 261 possible. */ 262 unsigned grp_hint : 1; 263 264 /* Is the subtree rooted in this access fully covered by scalar 265 replacements? */ 266 unsigned grp_covered : 1; 267 268 /* If set to true, this access and all below it in an access tree must not be 269 scalarized. */ 270 unsigned grp_unscalarizable_region : 1; 271 272 /* Whether data have been written to parts of the aggregate covered by this 273 access which is not to be scalarized. This flag is propagated up in the 274 access tree. */ 275 unsigned grp_unscalarized_data : 1; 276 277 /* Does this access and/or group contain a write access through a 278 BIT_FIELD_REF? */ 279 unsigned grp_partial_lhs : 1; 280 281 /* Set when a scalar replacement should be created for this variable. */ 282 unsigned grp_to_be_replaced : 1; 283 284 /* Set when we want a replacement for the sole purpose of having it in 285 generated debug statements. */ 286 unsigned grp_to_be_debug_replaced : 1; 287 288 /* Should TREE_NO_WARNING of a replacement be set? */ 289 unsigned grp_no_warning : 1; 290 291 /* Is it possible that the group refers to data which might be (directly or 292 otherwise) modified? */ 293 unsigned grp_maybe_modified : 1; 294 295 /* Set when this is a representative of a pointer to scalar (i.e. by 296 reference) parameter which we consider for turning into a plain scalar 297 (i.e. a by value parameter). */ 298 unsigned grp_scalar_ptr : 1; 299 300 /* Set when we discover that this pointer is not safe to dereference in the 301 caller. */ 302 unsigned grp_not_necessarilly_dereferenced : 1; 303 }; 304 305 typedef struct access *access_p; 306 307 308 /* Alloc pool for allocating access structures. */ 309 static alloc_pool access_pool; 310 311 /* A structure linking lhs and rhs accesses from an aggregate assignment. They 312 are used to propagate subaccesses from rhs to lhs as long as they don't 313 conflict with what is already there. */ 314 struct assign_link 315 { 316 struct access *lacc, *racc; 317 struct assign_link *next; 318 }; 319 320 /* Alloc pool for allocating assign link structures. */ 321 static alloc_pool link_pool; 322 323 /* Base (tree) -> Vector (vec<access_p> *) map. */ 324 static hash_map<tree, auto_vec<access_p> > *base_access_vec; 325 326 /* Candidate hash table helpers. */ 327 328 struct uid_decl_hasher : typed_noop_remove <tree_node> 329 { 330 typedef tree_node value_type; 331 typedef tree_node compare_type; 332 static inline hashval_t hash (const value_type *); 333 static inline bool equal (const value_type *, const compare_type *); 334 }; 335 336 /* Hash a tree in a uid_decl_map. */ 337 338 inline hashval_t 339 uid_decl_hasher::hash (const value_type *item) 340 { 341 return item->decl_minimal.uid; 342 } 343 344 /* Return true if the DECL_UID in both trees are equal. */ 345 346 inline bool 347 uid_decl_hasher::equal (const value_type *a, const compare_type *b) 348 { 349 return (a->decl_minimal.uid == b->decl_minimal.uid); 350 } 351 352 /* Set of candidates. */ 353 static bitmap candidate_bitmap; 354 static hash_table<uid_decl_hasher> *candidates; 355 356 /* For a candidate UID return the candidates decl. */ 357 358 static inline tree 359 candidate (unsigned uid) 360 { 361 tree_node t; 362 t.decl_minimal.uid = uid; 363 return candidates->find_with_hash (&t, static_cast <hashval_t> (uid)); 364 } 365 366 /* Bitmap of candidates which we should try to entirely scalarize away and 367 those which cannot be (because they are and need be used as a whole). */ 368 static bitmap should_scalarize_away_bitmap, cannot_scalarize_away_bitmap; 369 370 /* Obstack for creation of fancy names. */ 371 static struct obstack name_obstack; 372 373 /* Head of a linked list of accesses that need to have its subaccesses 374 propagated to their assignment counterparts. */ 375 static struct access *work_queue_head; 376 377 /* Number of parameters of the analyzed function when doing early ipa SRA. */ 378 static int func_param_count; 379 380 /* scan_function sets the following to true if it encounters a call to 381 __builtin_apply_args. */ 382 static bool encountered_apply_args; 383 384 /* Set by scan_function when it finds a recursive call. */ 385 static bool encountered_recursive_call; 386 387 /* Set by scan_function when it finds a recursive call with less actual 388 arguments than formal parameters.. */ 389 static bool encountered_unchangable_recursive_call; 390 391 /* This is a table in which for each basic block and parameter there is a 392 distance (offset + size) in that parameter which is dereferenced and 393 accessed in that BB. */ 394 static HOST_WIDE_INT *bb_dereferences; 395 /* Bitmap of BBs that can cause the function to "stop" progressing by 396 returning, throwing externally, looping infinitely or calling a function 397 which might abort etc.. */ 398 static bitmap final_bbs; 399 400 /* Representative of no accesses at all. */ 401 static struct access no_accesses_representant; 402 403 /* Predicate to test the special value. */ 404 405 static inline bool 406 no_accesses_p (struct access *access) 407 { 408 return access == &no_accesses_representant; 409 } 410 411 /* Dump contents of ACCESS to file F in a human friendly way. If GRP is true, 412 representative fields are dumped, otherwise those which only describe the 413 individual access are. */ 414 415 static struct 416 { 417 /* Number of processed aggregates is readily available in 418 analyze_all_variable_accesses and so is not stored here. */ 419 420 /* Number of created scalar replacements. */ 421 int replacements; 422 423 /* Number of times sra_modify_expr or sra_modify_assign themselves changed an 424 expression. */ 425 int exprs; 426 427 /* Number of statements created by generate_subtree_copies. */ 428 int subtree_copies; 429 430 /* Number of statements created by load_assign_lhs_subreplacements. */ 431 int subreplacements; 432 433 /* Number of times sra_modify_assign has deleted a statement. */ 434 int deleted; 435 436 /* Number of times sra_modify_assign has to deal with subaccesses of LHS and 437 RHS reparately due to type conversions or nonexistent matching 438 references. */ 439 int separate_lhs_rhs_handling; 440 441 /* Number of parameters that were removed because they were unused. */ 442 int deleted_unused_parameters; 443 444 /* Number of scalars passed as parameters by reference that have been 445 converted to be passed by value. */ 446 int scalar_by_ref_to_by_val; 447 448 /* Number of aggregate parameters that were replaced by one or more of their 449 components. */ 450 int aggregate_params_reduced; 451 452 /* Numbber of components created when splitting aggregate parameters. */ 453 int param_reductions_created; 454 } sra_stats; 455 456 static void 457 dump_access (FILE *f, struct access *access, bool grp) 458 { 459 fprintf (f, "access { "); 460 fprintf (f, "base = (%d)'", DECL_UID (access->base)); 461 print_generic_expr (f, access->base, 0); 462 fprintf (f, "', offset = " HOST_WIDE_INT_PRINT_DEC, access->offset); 463 fprintf (f, ", size = " HOST_WIDE_INT_PRINT_DEC, access->size); 464 fprintf (f, ", expr = "); 465 print_generic_expr (f, access->expr, 0); 466 fprintf (f, ", type = "); 467 print_generic_expr (f, access->type, 0); 468 if (grp) 469 fprintf (f, ", grp_read = %d, grp_write = %d, grp_assignment_read = %d, " 470 "grp_assignment_write = %d, grp_scalar_read = %d, " 471 "grp_scalar_write = %d, grp_total_scalarization = %d, " 472 "grp_hint = %d, grp_covered = %d, " 473 "grp_unscalarizable_region = %d, grp_unscalarized_data = %d, " 474 "grp_partial_lhs = %d, grp_to_be_replaced = %d, " 475 "grp_to_be_debug_replaced = %d, grp_maybe_modified = %d, " 476 "grp_not_necessarilly_dereferenced = %d\n", 477 access->grp_read, access->grp_write, access->grp_assignment_read, 478 access->grp_assignment_write, access->grp_scalar_read, 479 access->grp_scalar_write, access->grp_total_scalarization, 480 access->grp_hint, access->grp_covered, 481 access->grp_unscalarizable_region, access->grp_unscalarized_data, 482 access->grp_partial_lhs, access->grp_to_be_replaced, 483 access->grp_to_be_debug_replaced, access->grp_maybe_modified, 484 access->grp_not_necessarilly_dereferenced); 485 else 486 fprintf (f, ", write = %d, grp_total_scalarization = %d, " 487 "grp_partial_lhs = %d\n", 488 access->write, access->grp_total_scalarization, 489 access->grp_partial_lhs); 490 } 491 492 /* Dump a subtree rooted in ACCESS to file F, indent by LEVEL. */ 493 494 static void 495 dump_access_tree_1 (FILE *f, struct access *access, int level) 496 { 497 do 498 { 499 int i; 500 501 for (i = 0; i < level; i++) 502 fputs ("* ", dump_file); 503 504 dump_access (f, access, true); 505 506 if (access->first_child) 507 dump_access_tree_1 (f, access->first_child, level + 1); 508 509 access = access->next_sibling; 510 } 511 while (access); 512 } 513 514 /* Dump all access trees for a variable, given the pointer to the first root in 515 ACCESS. */ 516 517 static void 518 dump_access_tree (FILE *f, struct access *access) 519 { 520 for (; access; access = access->next_grp) 521 dump_access_tree_1 (f, access, 0); 522 } 523 524 /* Return true iff ACC is non-NULL and has subaccesses. */ 525 526 static inline bool 527 access_has_children_p (struct access *acc) 528 { 529 return acc && acc->first_child; 530 } 531 532 /* Return true iff ACC is (partly) covered by at least one replacement. */ 533 534 static bool 535 access_has_replacements_p (struct access *acc) 536 { 537 struct access *child; 538 if (acc->grp_to_be_replaced) 539 return true; 540 for (child = acc->first_child; child; child = child->next_sibling) 541 if (access_has_replacements_p (child)) 542 return true; 543 return false; 544 } 545 546 /* Return a vector of pointers to accesses for the variable given in BASE or 547 NULL if there is none. */ 548 549 static vec<access_p> * 550 get_base_access_vector (tree base) 551 { 552 return base_access_vec->get (base); 553 } 554 555 /* Find an access with required OFFSET and SIZE in a subtree of accesses rooted 556 in ACCESS. Return NULL if it cannot be found. */ 557 558 static struct access * 559 find_access_in_subtree (struct access *access, HOST_WIDE_INT offset, 560 HOST_WIDE_INT size) 561 { 562 while (access && (access->offset != offset || access->size != size)) 563 { 564 struct access *child = access->first_child; 565 566 while (child && (child->offset + child->size <= offset)) 567 child = child->next_sibling; 568 access = child; 569 } 570 571 return access; 572 } 573 574 /* Return the first group representative for DECL or NULL if none exists. */ 575 576 static struct access * 577 get_first_repr_for_decl (tree base) 578 { 579 vec<access_p> *access_vec; 580 581 access_vec = get_base_access_vector (base); 582 if (!access_vec) 583 return NULL; 584 585 return (*access_vec)[0]; 586 } 587 588 /* Find an access representative for the variable BASE and given OFFSET and 589 SIZE. Requires that access trees have already been built. Return NULL if 590 it cannot be found. */ 591 592 static struct access * 593 get_var_base_offset_size_access (tree base, HOST_WIDE_INT offset, 594 HOST_WIDE_INT size) 595 { 596 struct access *access; 597 598 access = get_first_repr_for_decl (base); 599 while (access && (access->offset + access->size <= offset)) 600 access = access->next_grp; 601 if (!access) 602 return NULL; 603 604 return find_access_in_subtree (access, offset, size); 605 } 606 607 /* Add LINK to the linked list of assign links of RACC. */ 608 static void 609 add_link_to_rhs (struct access *racc, struct assign_link *link) 610 { 611 gcc_assert (link->racc == racc); 612 613 if (!racc->first_link) 614 { 615 gcc_assert (!racc->last_link); 616 racc->first_link = link; 617 } 618 else 619 racc->last_link->next = link; 620 621 racc->last_link = link; 622 link->next = NULL; 623 } 624 625 /* Move all link structures in their linked list in OLD_RACC to the linked list 626 in NEW_RACC. */ 627 static void 628 relink_to_new_repr (struct access *new_racc, struct access *old_racc) 629 { 630 if (!old_racc->first_link) 631 { 632 gcc_assert (!old_racc->last_link); 633 return; 634 } 635 636 if (new_racc->first_link) 637 { 638 gcc_assert (!new_racc->last_link->next); 639 gcc_assert (!old_racc->last_link || !old_racc->last_link->next); 640 641 new_racc->last_link->next = old_racc->first_link; 642 new_racc->last_link = old_racc->last_link; 643 } 644 else 645 { 646 gcc_assert (!new_racc->last_link); 647 648 new_racc->first_link = old_racc->first_link; 649 new_racc->last_link = old_racc->last_link; 650 } 651 old_racc->first_link = old_racc->last_link = NULL; 652 } 653 654 /* Add ACCESS to the work queue (which is actually a stack). */ 655 656 static void 657 add_access_to_work_queue (struct access *access) 658 { 659 if (!access->grp_queued) 660 { 661 gcc_assert (!access->next_queued); 662 access->next_queued = work_queue_head; 663 access->grp_queued = 1; 664 work_queue_head = access; 665 } 666 } 667 668 /* Pop an access from the work queue, and return it, assuming there is one. */ 669 670 static struct access * 671 pop_access_from_work_queue (void) 672 { 673 struct access *access = work_queue_head; 674 675 work_queue_head = access->next_queued; 676 access->next_queued = NULL; 677 access->grp_queued = 0; 678 return access; 679 } 680 681 682 /* Allocate necessary structures. */ 683 684 static void 685 sra_initialize (void) 686 { 687 candidate_bitmap = BITMAP_ALLOC (NULL); 688 candidates = new hash_table<uid_decl_hasher> 689 (vec_safe_length (cfun->local_decls) / 2); 690 should_scalarize_away_bitmap = BITMAP_ALLOC (NULL); 691 cannot_scalarize_away_bitmap = BITMAP_ALLOC (NULL); 692 gcc_obstack_init (&name_obstack); 693 access_pool = create_alloc_pool ("SRA accesses", sizeof (struct access), 16); 694 link_pool = create_alloc_pool ("SRA links", sizeof (struct assign_link), 16); 695 base_access_vec = new hash_map<tree, auto_vec<access_p> >; 696 memset (&sra_stats, 0, sizeof (sra_stats)); 697 encountered_apply_args = false; 698 encountered_recursive_call = false; 699 encountered_unchangable_recursive_call = false; 700 } 701 702 /* Deallocate all general structures. */ 703 704 static void 705 sra_deinitialize (void) 706 { 707 BITMAP_FREE (candidate_bitmap); 708 delete candidates; 709 candidates = NULL; 710 BITMAP_FREE (should_scalarize_away_bitmap); 711 BITMAP_FREE (cannot_scalarize_away_bitmap); 712 free_alloc_pool (access_pool); 713 free_alloc_pool (link_pool); 714 obstack_free (&name_obstack, NULL); 715 716 delete base_access_vec; 717 } 718 719 /* Remove DECL from candidates for SRA and write REASON to the dump file if 720 there is one. */ 721 static void 722 disqualify_candidate (tree decl, const char *reason) 723 { 724 if (bitmap_clear_bit (candidate_bitmap, DECL_UID (decl))) 725 candidates->remove_elt_with_hash (decl, DECL_UID (decl)); 726 727 if (dump_file && (dump_flags & TDF_DETAILS)) 728 { 729 fprintf (dump_file, "! Disqualifying "); 730 print_generic_expr (dump_file, decl, 0); 731 fprintf (dump_file, " - %s\n", reason); 732 } 733 } 734 735 /* Return true iff the type contains a field or an element which does not allow 736 scalarization. */ 737 738 static bool 739 type_internals_preclude_sra_p (tree type, const char **msg) 740 { 741 tree fld; 742 tree et; 743 744 switch (TREE_CODE (type)) 745 { 746 case RECORD_TYPE: 747 case UNION_TYPE: 748 case QUAL_UNION_TYPE: 749 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) 750 if (TREE_CODE (fld) == FIELD_DECL) 751 { 752 tree ft = TREE_TYPE (fld); 753 754 if (TREE_THIS_VOLATILE (fld)) 755 { 756 *msg = "volatile structure field"; 757 return true; 758 } 759 if (!DECL_FIELD_OFFSET (fld)) 760 { 761 *msg = "no structure field offset"; 762 return true; 763 } 764 if (!DECL_SIZE (fld)) 765 { 766 *msg = "zero structure field size"; 767 return true; 768 } 769 if (!tree_fits_uhwi_p (DECL_FIELD_OFFSET (fld))) 770 { 771 *msg = "structure field offset not fixed"; 772 return true; 773 } 774 if (!tree_fits_uhwi_p (DECL_SIZE (fld))) 775 { 776 *msg = "structure field size not fixed"; 777 return true; 778 } 779 if (!tree_fits_shwi_p (bit_position (fld))) 780 { 781 *msg = "structure field size too big"; 782 return true; 783 } 784 if (AGGREGATE_TYPE_P (ft) 785 && int_bit_position (fld) % BITS_PER_UNIT != 0) 786 { 787 *msg = "structure field is bit field"; 788 return true; 789 } 790 791 if (AGGREGATE_TYPE_P (ft) && type_internals_preclude_sra_p (ft, msg)) 792 return true; 793 } 794 795 return false; 796 797 case ARRAY_TYPE: 798 et = TREE_TYPE (type); 799 800 if (TYPE_VOLATILE (et)) 801 { 802 *msg = "element type is volatile"; 803 return true; 804 } 805 806 if (AGGREGATE_TYPE_P (et) && type_internals_preclude_sra_p (et, msg)) 807 return true; 808 809 return false; 810 811 default: 812 return false; 813 } 814 } 815 816 /* If T is an SSA_NAME, return NULL if it is not a default def or return its 817 base variable if it is. Return T if it is not an SSA_NAME. */ 818 819 static tree 820 get_ssa_base_param (tree t) 821 { 822 if (TREE_CODE (t) == SSA_NAME) 823 { 824 if (SSA_NAME_IS_DEFAULT_DEF (t)) 825 return SSA_NAME_VAR (t); 826 else 827 return NULL_TREE; 828 } 829 return t; 830 } 831 832 /* Mark a dereference of BASE of distance DIST in a basic block tht STMT 833 belongs to, unless the BB has already been marked as a potentially 834 final. */ 835 836 static void 837 mark_parm_dereference (tree base, HOST_WIDE_INT dist, gimple stmt) 838 { 839 basic_block bb = gimple_bb (stmt); 840 int idx, parm_index = 0; 841 tree parm; 842 843 if (bitmap_bit_p (final_bbs, bb->index)) 844 return; 845 846 for (parm = DECL_ARGUMENTS (current_function_decl); 847 parm && parm != base; 848 parm = DECL_CHAIN (parm)) 849 parm_index++; 850 851 gcc_assert (parm_index < func_param_count); 852 853 idx = bb->index * func_param_count + parm_index; 854 if (bb_dereferences[idx] < dist) 855 bb_dereferences[idx] = dist; 856 } 857 858 /* Allocate an access structure for BASE, OFFSET and SIZE, clear it, fill in 859 the three fields. Also add it to the vector of accesses corresponding to 860 the base. Finally, return the new access. */ 861 862 static struct access * 863 create_access_1 (tree base, HOST_WIDE_INT offset, HOST_WIDE_INT size) 864 { 865 struct access *access; 866 867 access = (struct access *) pool_alloc (access_pool); 868 memset (access, 0, sizeof (struct access)); 869 access->base = base; 870 access->offset = offset; 871 access->size = size; 872 873 base_access_vec->get_or_insert (base).safe_push (access); 874 875 return access; 876 } 877 878 /* Create and insert access for EXPR. Return created access, or NULL if it is 879 not possible. */ 880 881 static struct access * 882 create_access (tree expr, gimple stmt, bool write) 883 { 884 struct access *access; 885 HOST_WIDE_INT offset, size, max_size; 886 tree base = expr; 887 bool ptr, unscalarizable_region = false; 888 889 base = get_ref_base_and_extent (expr, &offset, &size, &max_size); 890 891 if (sra_mode == SRA_MODE_EARLY_IPA 892 && TREE_CODE (base) == MEM_REF) 893 { 894 base = get_ssa_base_param (TREE_OPERAND (base, 0)); 895 if (!base) 896 return NULL; 897 ptr = true; 898 } 899 else 900 ptr = false; 901 902 if (!DECL_P (base) || !bitmap_bit_p (candidate_bitmap, DECL_UID (base))) 903 return NULL; 904 905 if (sra_mode == SRA_MODE_EARLY_IPA) 906 { 907 if (size < 0 || size != max_size) 908 { 909 disqualify_candidate (base, "Encountered a variable sized access."); 910 return NULL; 911 } 912 if (TREE_CODE (expr) == COMPONENT_REF 913 && DECL_BIT_FIELD (TREE_OPERAND (expr, 1))) 914 { 915 disqualify_candidate (base, "Encountered a bit-field access."); 916 return NULL; 917 } 918 gcc_checking_assert ((offset % BITS_PER_UNIT) == 0); 919 920 if (ptr) 921 mark_parm_dereference (base, offset + size, stmt); 922 } 923 else 924 { 925 if (size != max_size) 926 { 927 size = max_size; 928 unscalarizable_region = true; 929 } 930 if (size < 0) 931 { 932 disqualify_candidate (base, "Encountered an unconstrained access."); 933 return NULL; 934 } 935 } 936 937 access = create_access_1 (base, offset, size); 938 access->expr = expr; 939 access->type = TREE_TYPE (expr); 940 access->write = write; 941 access->grp_unscalarizable_region = unscalarizable_region; 942 access->stmt = stmt; 943 944 if (TREE_CODE (expr) == COMPONENT_REF 945 && DECL_NONADDRESSABLE_P (TREE_OPERAND (expr, 1))) 946 access->non_addressable = 1; 947 948 return access; 949 } 950 951 952 /* Return true iff TYPE is a RECORD_TYPE with fields that are either of gimple 953 register types or (recursively) records with only these two kinds of fields. 954 It also returns false if any of these records contains a bit-field. */ 955 956 static bool 957 type_consists_of_records_p (tree type) 958 { 959 tree fld; 960 961 if (TREE_CODE (type) != RECORD_TYPE) 962 return false; 963 964 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) 965 if (TREE_CODE (fld) == FIELD_DECL) 966 { 967 tree ft = TREE_TYPE (fld); 968 969 if (DECL_BIT_FIELD (fld)) 970 return false; 971 972 if (!is_gimple_reg_type (ft) 973 && !type_consists_of_records_p (ft)) 974 return false; 975 } 976 977 return true; 978 } 979 980 /* Create total_scalarization accesses for all scalar type fields in DECL that 981 must be of a RECORD_TYPE conforming to type_consists_of_records_p. BASE 982 must be the top-most VAR_DECL representing the variable, OFFSET must be the 983 offset of DECL within BASE. REF must be the memory reference expression for 984 the given decl. */ 985 986 static void 987 completely_scalarize_record (tree base, tree decl, HOST_WIDE_INT offset, 988 tree ref) 989 { 990 tree fld, decl_type = TREE_TYPE (decl); 991 992 for (fld = TYPE_FIELDS (decl_type); fld; fld = DECL_CHAIN (fld)) 993 if (TREE_CODE (fld) == FIELD_DECL) 994 { 995 HOST_WIDE_INT pos = offset + int_bit_position (fld); 996 tree ft = TREE_TYPE (fld); 997 tree nref = build3 (COMPONENT_REF, TREE_TYPE (fld), ref, fld, 998 NULL_TREE); 999 1000 if (is_gimple_reg_type (ft)) 1001 { 1002 struct access *access; 1003 HOST_WIDE_INT size; 1004 1005 size = tree_to_uhwi (DECL_SIZE (fld)); 1006 access = create_access_1 (base, pos, size); 1007 access->expr = nref; 1008 access->type = ft; 1009 access->grp_total_scalarization = 1; 1010 /* Accesses for intraprocedural SRA can have their stmt NULL. */ 1011 } 1012 else 1013 completely_scalarize_record (base, fld, pos, nref); 1014 } 1015 } 1016 1017 /* Create total_scalarization accesses for all scalar type fields in VAR and 1018 for VAR a a whole. VAR must be of a RECORD_TYPE conforming to 1019 type_consists_of_records_p. */ 1020 1021 static void 1022 completely_scalarize_var (tree var) 1023 { 1024 HOST_WIDE_INT size = tree_to_uhwi (DECL_SIZE (var)); 1025 struct access *access; 1026 1027 access = create_access_1 (var, 0, size); 1028 access->expr = var; 1029 access->type = TREE_TYPE (var); 1030 access->grp_total_scalarization = 1; 1031 1032 completely_scalarize_record (var, var, 0, var); 1033 } 1034 1035 /* Return true if REF has an VIEW_CONVERT_EXPR somewhere in it. */ 1036 1037 static inline bool 1038 contains_view_convert_expr_p (const_tree ref) 1039 { 1040 while (handled_component_p (ref)) 1041 { 1042 if (TREE_CODE (ref) == VIEW_CONVERT_EXPR) 1043 return true; 1044 ref = TREE_OPERAND (ref, 0); 1045 } 1046 1047 return false; 1048 } 1049 1050 /* Search the given tree for a declaration by skipping handled components and 1051 exclude it from the candidates. */ 1052 1053 static void 1054 disqualify_base_of_expr (tree t, const char *reason) 1055 { 1056 t = get_base_address (t); 1057 if (sra_mode == SRA_MODE_EARLY_IPA 1058 && TREE_CODE (t) == MEM_REF) 1059 t = get_ssa_base_param (TREE_OPERAND (t, 0)); 1060 1061 if (t && DECL_P (t)) 1062 disqualify_candidate (t, reason); 1063 } 1064 1065 /* Scan expression EXPR and create access structures for all accesses to 1066 candidates for scalarization. Return the created access or NULL if none is 1067 created. */ 1068 1069 static struct access * 1070 build_access_from_expr_1 (tree expr, gimple stmt, bool write) 1071 { 1072 struct access *ret = NULL; 1073 bool partial_ref; 1074 1075 if (TREE_CODE (expr) == BIT_FIELD_REF 1076 || TREE_CODE (expr) == IMAGPART_EXPR 1077 || TREE_CODE (expr) == REALPART_EXPR) 1078 { 1079 expr = TREE_OPERAND (expr, 0); 1080 partial_ref = true; 1081 } 1082 else 1083 partial_ref = false; 1084 1085 /* We need to dive through V_C_Es in order to get the size of its parameter 1086 and not the result type. Ada produces such statements. We are also 1087 capable of handling the topmost V_C_E but not any of those buried in other 1088 handled components. */ 1089 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR) 1090 expr = TREE_OPERAND (expr, 0); 1091 1092 if (contains_view_convert_expr_p (expr)) 1093 { 1094 disqualify_base_of_expr (expr, "V_C_E under a different handled " 1095 "component."); 1096 return NULL; 1097 } 1098 if (TREE_THIS_VOLATILE (expr)) 1099 { 1100 disqualify_base_of_expr (expr, "part of a volatile reference."); 1101 return NULL; 1102 } 1103 1104 switch (TREE_CODE (expr)) 1105 { 1106 case MEM_REF: 1107 if (TREE_CODE (TREE_OPERAND (expr, 0)) != ADDR_EXPR 1108 && sra_mode != SRA_MODE_EARLY_IPA) 1109 return NULL; 1110 /* fall through */ 1111 case VAR_DECL: 1112 case PARM_DECL: 1113 case RESULT_DECL: 1114 case COMPONENT_REF: 1115 case ARRAY_REF: 1116 case ARRAY_RANGE_REF: 1117 ret = create_access (expr, stmt, write); 1118 break; 1119 1120 default: 1121 break; 1122 } 1123 1124 if (write && partial_ref && ret) 1125 ret->grp_partial_lhs = 1; 1126 1127 return ret; 1128 } 1129 1130 /* Scan expression EXPR and create access structures for all accesses to 1131 candidates for scalarization. Return true if any access has been inserted. 1132 STMT must be the statement from which the expression is taken, WRITE must be 1133 true if the expression is a store and false otherwise. */ 1134 1135 static bool 1136 build_access_from_expr (tree expr, gimple stmt, bool write) 1137 { 1138 struct access *access; 1139 1140 access = build_access_from_expr_1 (expr, stmt, write); 1141 if (access) 1142 { 1143 /* This means the aggregate is accesses as a whole in a way other than an 1144 assign statement and thus cannot be removed even if we had a scalar 1145 replacement for everything. */ 1146 if (cannot_scalarize_away_bitmap) 1147 bitmap_set_bit (cannot_scalarize_away_bitmap, DECL_UID (access->base)); 1148 return true; 1149 } 1150 return false; 1151 } 1152 1153 /* Return the single non-EH successor edge of BB or NULL if there is none or 1154 more than one. */ 1155 1156 static edge 1157 single_non_eh_succ (basic_block bb) 1158 { 1159 edge e, res = NULL; 1160 edge_iterator ei; 1161 1162 FOR_EACH_EDGE (e, ei, bb->succs) 1163 if (!(e->flags & EDGE_EH)) 1164 { 1165 if (res) 1166 return NULL; 1167 res = e; 1168 } 1169 1170 return res; 1171 } 1172 1173 /* Disqualify LHS and RHS for scalarization if STMT has to terminate its BB and 1174 there is no alternative spot where to put statements SRA might need to 1175 generate after it. The spot we are looking for is an edge leading to a 1176 single non-EH successor, if it exists and is indeed single. RHS may be 1177 NULL, in that case ignore it. */ 1178 1179 static bool 1180 disqualify_if_bad_bb_terminating_stmt (gimple stmt, tree lhs, tree rhs) 1181 { 1182 if ((sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA) 1183 && stmt_ends_bb_p (stmt)) 1184 { 1185 if (single_non_eh_succ (gimple_bb (stmt))) 1186 return false; 1187 1188 disqualify_base_of_expr (lhs, "LHS of a throwing stmt."); 1189 if (rhs) 1190 disqualify_base_of_expr (rhs, "RHS of a throwing stmt."); 1191 return true; 1192 } 1193 return false; 1194 } 1195 1196 /* Scan expressions occurring in STMT, create access structures for all accesses 1197 to candidates for scalarization and remove those candidates which occur in 1198 statements or expressions that prevent them from being split apart. Return 1199 true if any access has been inserted. */ 1200 1201 static bool 1202 build_accesses_from_assign (gimple stmt) 1203 { 1204 tree lhs, rhs; 1205 struct access *lacc, *racc; 1206 1207 if (!gimple_assign_single_p (stmt) 1208 /* Scope clobbers don't influence scalarization. */ 1209 || gimple_clobber_p (stmt)) 1210 return false; 1211 1212 lhs = gimple_assign_lhs (stmt); 1213 rhs = gimple_assign_rhs1 (stmt); 1214 1215 if (disqualify_if_bad_bb_terminating_stmt (stmt, lhs, rhs)) 1216 return false; 1217 1218 racc = build_access_from_expr_1 (rhs, stmt, false); 1219 lacc = build_access_from_expr_1 (lhs, stmt, true); 1220 1221 if (lacc) 1222 lacc->grp_assignment_write = 1; 1223 1224 if (racc) 1225 { 1226 racc->grp_assignment_read = 1; 1227 if (should_scalarize_away_bitmap && !gimple_has_volatile_ops (stmt) 1228 && !is_gimple_reg_type (racc->type)) 1229 bitmap_set_bit (should_scalarize_away_bitmap, DECL_UID (racc->base)); 1230 } 1231 1232 if (lacc && racc 1233 && (sra_mode == SRA_MODE_EARLY_INTRA || sra_mode == SRA_MODE_INTRA) 1234 && !lacc->grp_unscalarizable_region 1235 && !racc->grp_unscalarizable_region 1236 && AGGREGATE_TYPE_P (TREE_TYPE (lhs)) 1237 && lacc->size == racc->size 1238 && useless_type_conversion_p (lacc->type, racc->type)) 1239 { 1240 struct assign_link *link; 1241 1242 link = (struct assign_link *) pool_alloc (link_pool); 1243 memset (link, 0, sizeof (struct assign_link)); 1244 1245 link->lacc = lacc; 1246 link->racc = racc; 1247 1248 add_link_to_rhs (racc, link); 1249 } 1250 1251 return lacc || racc; 1252 } 1253 1254 /* Callback of walk_stmt_load_store_addr_ops visit_addr used to determine 1255 GIMPLE_ASM operands with memory constrains which cannot be scalarized. */ 1256 1257 static bool 1258 asm_visit_addr (gimple, tree op, tree, void *) 1259 { 1260 op = get_base_address (op); 1261 if (op 1262 && DECL_P (op)) 1263 disqualify_candidate (op, "Non-scalarizable GIMPLE_ASM operand."); 1264 1265 return false; 1266 } 1267 1268 /* Return true iff callsite CALL has at least as many actual arguments as there 1269 are formal parameters of the function currently processed by IPA-SRA and 1270 that their types match. */ 1271 1272 static inline bool 1273 callsite_arguments_match_p (gimple call) 1274 { 1275 if (gimple_call_num_args (call) < (unsigned) func_param_count) 1276 return false; 1277 1278 tree parm; 1279 int i; 1280 for (parm = DECL_ARGUMENTS (current_function_decl), i = 0; 1281 parm; 1282 parm = DECL_CHAIN (parm), i++) 1283 { 1284 tree arg = gimple_call_arg (call, i); 1285 if (!useless_type_conversion_p (TREE_TYPE (parm), TREE_TYPE (arg))) 1286 return false; 1287 } 1288 return true; 1289 } 1290 1291 /* Scan function and look for interesting expressions and create access 1292 structures for them. Return true iff any access is created. */ 1293 1294 static bool 1295 scan_function (void) 1296 { 1297 basic_block bb; 1298 bool ret = false; 1299 1300 FOR_EACH_BB_FN (bb, cfun) 1301 { 1302 gimple_stmt_iterator gsi; 1303 for (gsi = gsi_start_bb (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 1304 { 1305 gimple stmt = gsi_stmt (gsi); 1306 tree t; 1307 unsigned i; 1308 1309 if (final_bbs && stmt_can_throw_external (stmt)) 1310 bitmap_set_bit (final_bbs, bb->index); 1311 switch (gimple_code (stmt)) 1312 { 1313 case GIMPLE_RETURN: 1314 t = gimple_return_retval (as_a <greturn *> (stmt)); 1315 if (t != NULL_TREE) 1316 ret |= build_access_from_expr (t, stmt, false); 1317 if (final_bbs) 1318 bitmap_set_bit (final_bbs, bb->index); 1319 break; 1320 1321 case GIMPLE_ASSIGN: 1322 ret |= build_accesses_from_assign (stmt); 1323 break; 1324 1325 case GIMPLE_CALL: 1326 for (i = 0; i < gimple_call_num_args (stmt); i++) 1327 ret |= build_access_from_expr (gimple_call_arg (stmt, i), 1328 stmt, false); 1329 1330 if (sra_mode == SRA_MODE_EARLY_IPA) 1331 { 1332 tree dest = gimple_call_fndecl (stmt); 1333 int flags = gimple_call_flags (stmt); 1334 1335 if (dest) 1336 { 1337 if (DECL_BUILT_IN_CLASS (dest) == BUILT_IN_NORMAL 1338 && DECL_FUNCTION_CODE (dest) == BUILT_IN_APPLY_ARGS) 1339 encountered_apply_args = true; 1340 if (recursive_call_p (current_function_decl, dest)) 1341 { 1342 encountered_recursive_call = true; 1343 if (!callsite_arguments_match_p (stmt)) 1344 encountered_unchangable_recursive_call = true; 1345 } 1346 } 1347 1348 if (final_bbs 1349 && (flags & (ECF_CONST | ECF_PURE)) == 0) 1350 bitmap_set_bit (final_bbs, bb->index); 1351 } 1352 1353 t = gimple_call_lhs (stmt); 1354 if (t && !disqualify_if_bad_bb_terminating_stmt (stmt, t, NULL)) 1355 ret |= build_access_from_expr (t, stmt, true); 1356 break; 1357 1358 case GIMPLE_ASM: 1359 { 1360 gasm *asm_stmt = as_a <gasm *> (stmt); 1361 walk_stmt_load_store_addr_ops (asm_stmt, NULL, NULL, NULL, 1362 asm_visit_addr); 1363 if (final_bbs) 1364 bitmap_set_bit (final_bbs, bb->index); 1365 1366 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++) 1367 { 1368 t = TREE_VALUE (gimple_asm_input_op (asm_stmt, i)); 1369 ret |= build_access_from_expr (t, asm_stmt, false); 1370 } 1371 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++) 1372 { 1373 t = TREE_VALUE (gimple_asm_output_op (asm_stmt, i)); 1374 ret |= build_access_from_expr (t, asm_stmt, true); 1375 } 1376 } 1377 break; 1378 1379 default: 1380 break; 1381 } 1382 } 1383 } 1384 1385 return ret; 1386 } 1387 1388 /* Helper of QSORT function. There are pointers to accesses in the array. An 1389 access is considered smaller than another if it has smaller offset or if the 1390 offsets are the same but is size is bigger. */ 1391 1392 static int 1393 compare_access_positions (const void *a, const void *b) 1394 { 1395 const access_p *fp1 = (const access_p *) a; 1396 const access_p *fp2 = (const access_p *) b; 1397 const access_p f1 = *fp1; 1398 const access_p f2 = *fp2; 1399 1400 if (f1->offset != f2->offset) 1401 return f1->offset < f2->offset ? -1 : 1; 1402 1403 if (f1->size == f2->size) 1404 { 1405 if (f1->type == f2->type) 1406 return 0; 1407 /* Put any non-aggregate type before any aggregate type. */ 1408 else if (!is_gimple_reg_type (f1->type) 1409 && is_gimple_reg_type (f2->type)) 1410 return 1; 1411 else if (is_gimple_reg_type (f1->type) 1412 && !is_gimple_reg_type (f2->type)) 1413 return -1; 1414 /* Put any complex or vector type before any other scalar type. */ 1415 else if (TREE_CODE (f1->type) != COMPLEX_TYPE 1416 && TREE_CODE (f1->type) != VECTOR_TYPE 1417 && (TREE_CODE (f2->type) == COMPLEX_TYPE 1418 || TREE_CODE (f2->type) == VECTOR_TYPE)) 1419 return 1; 1420 else if ((TREE_CODE (f1->type) == COMPLEX_TYPE 1421 || TREE_CODE (f1->type) == VECTOR_TYPE) 1422 && TREE_CODE (f2->type) != COMPLEX_TYPE 1423 && TREE_CODE (f2->type) != VECTOR_TYPE) 1424 return -1; 1425 /* Put the integral type with the bigger precision first. */ 1426 else if (INTEGRAL_TYPE_P (f1->type) 1427 && INTEGRAL_TYPE_P (f2->type)) 1428 return TYPE_PRECISION (f2->type) - TYPE_PRECISION (f1->type); 1429 /* Put any integral type with non-full precision last. */ 1430 else if (INTEGRAL_TYPE_P (f1->type) 1431 && (TREE_INT_CST_LOW (TYPE_SIZE (f1->type)) 1432 != TYPE_PRECISION (f1->type))) 1433 return 1; 1434 else if (INTEGRAL_TYPE_P (f2->type) 1435 && (TREE_INT_CST_LOW (TYPE_SIZE (f2->type)) 1436 != TYPE_PRECISION (f2->type))) 1437 return -1; 1438 /* Stabilize the sort. */ 1439 return TYPE_UID (f1->type) - TYPE_UID (f2->type); 1440 } 1441 1442 /* We want the bigger accesses first, thus the opposite operator in the next 1443 line: */ 1444 return f1->size > f2->size ? -1 : 1; 1445 } 1446 1447 1448 /* Append a name of the declaration to the name obstack. A helper function for 1449 make_fancy_name. */ 1450 1451 static void 1452 make_fancy_decl_name (tree decl) 1453 { 1454 char buffer[32]; 1455 1456 tree name = DECL_NAME (decl); 1457 if (name) 1458 obstack_grow (&name_obstack, IDENTIFIER_POINTER (name), 1459 IDENTIFIER_LENGTH (name)); 1460 else 1461 { 1462 sprintf (buffer, "D%u", DECL_UID (decl)); 1463 obstack_grow (&name_obstack, buffer, strlen (buffer)); 1464 } 1465 } 1466 1467 /* Helper for make_fancy_name. */ 1468 1469 static void 1470 make_fancy_name_1 (tree expr) 1471 { 1472 char buffer[32]; 1473 tree index; 1474 1475 if (DECL_P (expr)) 1476 { 1477 make_fancy_decl_name (expr); 1478 return; 1479 } 1480 1481 switch (TREE_CODE (expr)) 1482 { 1483 case COMPONENT_REF: 1484 make_fancy_name_1 (TREE_OPERAND (expr, 0)); 1485 obstack_1grow (&name_obstack, '$'); 1486 make_fancy_decl_name (TREE_OPERAND (expr, 1)); 1487 break; 1488 1489 case ARRAY_REF: 1490 make_fancy_name_1 (TREE_OPERAND (expr, 0)); 1491 obstack_1grow (&name_obstack, '$'); 1492 /* Arrays with only one element may not have a constant as their 1493 index. */ 1494 index = TREE_OPERAND (expr, 1); 1495 if (TREE_CODE (index) != INTEGER_CST) 1496 break; 1497 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (index)); 1498 obstack_grow (&name_obstack, buffer, strlen (buffer)); 1499 break; 1500 1501 case ADDR_EXPR: 1502 make_fancy_name_1 (TREE_OPERAND (expr, 0)); 1503 break; 1504 1505 case MEM_REF: 1506 make_fancy_name_1 (TREE_OPERAND (expr, 0)); 1507 if (!integer_zerop (TREE_OPERAND (expr, 1))) 1508 { 1509 obstack_1grow (&name_obstack, '$'); 1510 sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, 1511 TREE_INT_CST_LOW (TREE_OPERAND (expr, 1))); 1512 obstack_grow (&name_obstack, buffer, strlen (buffer)); 1513 } 1514 break; 1515 1516 case BIT_FIELD_REF: 1517 case REALPART_EXPR: 1518 case IMAGPART_EXPR: 1519 gcc_unreachable (); /* we treat these as scalars. */ 1520 break; 1521 default: 1522 break; 1523 } 1524 } 1525 1526 /* Create a human readable name for replacement variable of ACCESS. */ 1527 1528 static char * 1529 make_fancy_name (tree expr) 1530 { 1531 make_fancy_name_1 (expr); 1532 obstack_1grow (&name_obstack, '\0'); 1533 return XOBFINISH (&name_obstack, char *); 1534 } 1535 1536 /* Construct a MEM_REF that would reference a part of aggregate BASE of type 1537 EXP_TYPE at the given OFFSET. If BASE is something for which 1538 get_addr_base_and_unit_offset returns NULL, gsi must be non-NULL and is used 1539 to insert new statements either before or below the current one as specified 1540 by INSERT_AFTER. This function is not capable of handling bitfields. 1541 1542 BASE must be either a declaration or a memory reference that has correct 1543 alignment ifformation embeded in it (e.g. a pre-existing one in SRA). */ 1544 1545 tree 1546 build_ref_for_offset (location_t loc, tree base, HOST_WIDE_INT offset, 1547 tree exp_type, gimple_stmt_iterator *gsi, 1548 bool insert_after) 1549 { 1550 tree prev_base = base; 1551 tree off; 1552 tree mem_ref; 1553 HOST_WIDE_INT base_offset; 1554 unsigned HOST_WIDE_INT misalign; 1555 unsigned int align; 1556 1557 gcc_checking_assert (offset % BITS_PER_UNIT == 0); 1558 get_object_alignment_1 (base, &align, &misalign); 1559 base = get_addr_base_and_unit_offset (base, &base_offset); 1560 1561 /* get_addr_base_and_unit_offset returns NULL for references with a variable 1562 offset such as array[var_index]. */ 1563 if (!base) 1564 { 1565 gassign *stmt; 1566 tree tmp, addr; 1567 1568 gcc_checking_assert (gsi); 1569 tmp = make_ssa_name (build_pointer_type (TREE_TYPE (prev_base))); 1570 addr = build_fold_addr_expr (unshare_expr (prev_base)); 1571 STRIP_USELESS_TYPE_CONVERSION (addr); 1572 stmt = gimple_build_assign (tmp, addr); 1573 gimple_set_location (stmt, loc); 1574 if (insert_after) 1575 gsi_insert_after (gsi, stmt, GSI_NEW_STMT); 1576 else 1577 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 1578 1579 off = build_int_cst (reference_alias_ptr_type (prev_base), 1580 offset / BITS_PER_UNIT); 1581 base = tmp; 1582 } 1583 else if (TREE_CODE (base) == MEM_REF) 1584 { 1585 off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)), 1586 base_offset + offset / BITS_PER_UNIT); 1587 off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off); 1588 base = unshare_expr (TREE_OPERAND (base, 0)); 1589 } 1590 else 1591 { 1592 off = build_int_cst (reference_alias_ptr_type (prev_base), 1593 base_offset + offset / BITS_PER_UNIT); 1594 base = build_fold_addr_expr (unshare_expr (base)); 1595 } 1596 1597 misalign = (misalign + offset) & (align - 1); 1598 if (misalign != 0) 1599 align = (misalign & -misalign); 1600 if (align != TYPE_ALIGN (exp_type)) 1601 exp_type = build_aligned_type (exp_type, align); 1602 1603 mem_ref = fold_build2_loc (loc, MEM_REF, exp_type, base, off); 1604 if (TREE_THIS_VOLATILE (prev_base)) 1605 TREE_THIS_VOLATILE (mem_ref) = 1; 1606 if (TREE_SIDE_EFFECTS (prev_base)) 1607 TREE_SIDE_EFFECTS (mem_ref) = 1; 1608 return mem_ref; 1609 } 1610 1611 /* Construct a memory reference to a part of an aggregate BASE at the given 1612 OFFSET and of the same type as MODEL. In case this is a reference to a 1613 bit-field, the function will replicate the last component_ref of model's 1614 expr to access it. GSI and INSERT_AFTER have the same meaning as in 1615 build_ref_for_offset. */ 1616 1617 static tree 1618 build_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset, 1619 struct access *model, gimple_stmt_iterator *gsi, 1620 bool insert_after) 1621 { 1622 if (TREE_CODE (model->expr) == COMPONENT_REF 1623 && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1))) 1624 { 1625 /* This access represents a bit-field. */ 1626 tree t, exp_type, fld = TREE_OPERAND (model->expr, 1); 1627 1628 offset -= int_bit_position (fld); 1629 exp_type = TREE_TYPE (TREE_OPERAND (model->expr, 0)); 1630 t = build_ref_for_offset (loc, base, offset, exp_type, gsi, insert_after); 1631 return fold_build3_loc (loc, COMPONENT_REF, TREE_TYPE (fld), t, fld, 1632 NULL_TREE); 1633 } 1634 else 1635 return build_ref_for_offset (loc, base, offset, model->type, 1636 gsi, insert_after); 1637 } 1638 1639 /* Attempt to build a memory reference that we could but into a gimple 1640 debug_bind statement. Similar to build_ref_for_model but punts if it has to 1641 create statements and return s NULL instead. This function also ignores 1642 alignment issues and so its results should never end up in non-debug 1643 statements. */ 1644 1645 static tree 1646 build_debug_ref_for_model (location_t loc, tree base, HOST_WIDE_INT offset, 1647 struct access *model) 1648 { 1649 HOST_WIDE_INT base_offset; 1650 tree off; 1651 1652 if (TREE_CODE (model->expr) == COMPONENT_REF 1653 && DECL_BIT_FIELD (TREE_OPERAND (model->expr, 1))) 1654 return NULL_TREE; 1655 1656 base = get_addr_base_and_unit_offset (base, &base_offset); 1657 if (!base) 1658 return NULL_TREE; 1659 if (TREE_CODE (base) == MEM_REF) 1660 { 1661 off = build_int_cst (TREE_TYPE (TREE_OPERAND (base, 1)), 1662 base_offset + offset / BITS_PER_UNIT); 1663 off = int_const_binop (PLUS_EXPR, TREE_OPERAND (base, 1), off); 1664 base = unshare_expr (TREE_OPERAND (base, 0)); 1665 } 1666 else 1667 { 1668 off = build_int_cst (reference_alias_ptr_type (base), 1669 base_offset + offset / BITS_PER_UNIT); 1670 base = build_fold_addr_expr (unshare_expr (base)); 1671 } 1672 1673 return fold_build2_loc (loc, MEM_REF, model->type, base, off); 1674 } 1675 1676 /* Construct a memory reference consisting of component_refs and array_refs to 1677 a part of an aggregate *RES (which is of type TYPE). The requested part 1678 should have type EXP_TYPE at be the given OFFSET. This function might not 1679 succeed, it returns true when it does and only then *RES points to something 1680 meaningful. This function should be used only to build expressions that we 1681 might need to present to user (e.g. in warnings). In all other situations, 1682 build_ref_for_model or build_ref_for_offset should be used instead. */ 1683 1684 static bool 1685 build_user_friendly_ref_for_offset (tree *res, tree type, HOST_WIDE_INT offset, 1686 tree exp_type) 1687 { 1688 while (1) 1689 { 1690 tree fld; 1691 tree tr_size, index, minidx; 1692 HOST_WIDE_INT el_size; 1693 1694 if (offset == 0 && exp_type 1695 && types_compatible_p (exp_type, type)) 1696 return true; 1697 1698 switch (TREE_CODE (type)) 1699 { 1700 case UNION_TYPE: 1701 case QUAL_UNION_TYPE: 1702 case RECORD_TYPE: 1703 for (fld = TYPE_FIELDS (type); fld; fld = DECL_CHAIN (fld)) 1704 { 1705 HOST_WIDE_INT pos, size; 1706 tree tr_pos, expr, *expr_ptr; 1707 1708 if (TREE_CODE (fld) != FIELD_DECL) 1709 continue; 1710 1711 tr_pos = bit_position (fld); 1712 if (!tr_pos || !tree_fits_uhwi_p (tr_pos)) 1713 continue; 1714 pos = tree_to_uhwi (tr_pos); 1715 gcc_assert (TREE_CODE (type) == RECORD_TYPE || pos == 0); 1716 tr_size = DECL_SIZE (fld); 1717 if (!tr_size || !tree_fits_uhwi_p (tr_size)) 1718 continue; 1719 size = tree_to_uhwi (tr_size); 1720 if (size == 0) 1721 { 1722 if (pos != offset) 1723 continue; 1724 } 1725 else if (pos > offset || (pos + size) <= offset) 1726 continue; 1727 1728 expr = build3 (COMPONENT_REF, TREE_TYPE (fld), *res, fld, 1729 NULL_TREE); 1730 expr_ptr = &expr; 1731 if (build_user_friendly_ref_for_offset (expr_ptr, TREE_TYPE (fld), 1732 offset - pos, exp_type)) 1733 { 1734 *res = expr; 1735 return true; 1736 } 1737 } 1738 return false; 1739 1740 case ARRAY_TYPE: 1741 tr_size = TYPE_SIZE (TREE_TYPE (type)); 1742 if (!tr_size || !tree_fits_uhwi_p (tr_size)) 1743 return false; 1744 el_size = tree_to_uhwi (tr_size); 1745 1746 minidx = TYPE_MIN_VALUE (TYPE_DOMAIN (type)); 1747 if (TREE_CODE (minidx) != INTEGER_CST || el_size == 0) 1748 return false; 1749 index = build_int_cst (TYPE_DOMAIN (type), offset / el_size); 1750 if (!integer_zerop (minidx)) 1751 index = int_const_binop (PLUS_EXPR, index, minidx); 1752 *res = build4 (ARRAY_REF, TREE_TYPE (type), *res, index, 1753 NULL_TREE, NULL_TREE); 1754 offset = offset % el_size; 1755 type = TREE_TYPE (type); 1756 break; 1757 1758 default: 1759 if (offset != 0) 1760 return false; 1761 1762 if (exp_type) 1763 return false; 1764 else 1765 return true; 1766 } 1767 } 1768 } 1769 1770 /* Return true iff TYPE is stdarg va_list type. */ 1771 1772 static inline bool 1773 is_va_list_type (tree type) 1774 { 1775 return TYPE_MAIN_VARIANT (type) == TYPE_MAIN_VARIANT (va_list_type_node); 1776 } 1777 1778 /* Print message to dump file why a variable was rejected. */ 1779 1780 static void 1781 reject (tree var, const char *msg) 1782 { 1783 if (dump_file && (dump_flags & TDF_DETAILS)) 1784 { 1785 fprintf (dump_file, "Rejected (%d): %s: ", DECL_UID (var), msg); 1786 print_generic_expr (dump_file, var, 0); 1787 fprintf (dump_file, "\n"); 1788 } 1789 } 1790 1791 /* Return true if VAR is a candidate for SRA. */ 1792 1793 static bool 1794 maybe_add_sra_candidate (tree var) 1795 { 1796 tree type = TREE_TYPE (var); 1797 const char *msg; 1798 tree_node **slot; 1799 1800 if (!AGGREGATE_TYPE_P (type)) 1801 { 1802 reject (var, "not aggregate"); 1803 return false; 1804 } 1805 if (needs_to_live_in_memory (var)) 1806 { 1807 reject (var, "needs to live in memory"); 1808 return false; 1809 } 1810 if (TREE_THIS_VOLATILE (var)) 1811 { 1812 reject (var, "is volatile"); 1813 return false; 1814 } 1815 if (!COMPLETE_TYPE_P (type)) 1816 { 1817 reject (var, "has incomplete type"); 1818 return false; 1819 } 1820 if (!tree_fits_uhwi_p (TYPE_SIZE (type))) 1821 { 1822 reject (var, "type size not fixed"); 1823 return false; 1824 } 1825 if (tree_to_uhwi (TYPE_SIZE (type)) == 0) 1826 { 1827 reject (var, "type size is zero"); 1828 return false; 1829 } 1830 if (type_internals_preclude_sra_p (type, &msg)) 1831 { 1832 reject (var, msg); 1833 return false; 1834 } 1835 if (/* Fix for PR 41089. tree-stdarg.c needs to have va_lists intact but 1836 we also want to schedule it rather late. Thus we ignore it in 1837 the early pass. */ 1838 (sra_mode == SRA_MODE_EARLY_INTRA 1839 && is_va_list_type (type))) 1840 { 1841 reject (var, "is va_list"); 1842 return false; 1843 } 1844 1845 bitmap_set_bit (candidate_bitmap, DECL_UID (var)); 1846 slot = candidates->find_slot_with_hash (var, DECL_UID (var), INSERT); 1847 *slot = var; 1848 1849 if (dump_file && (dump_flags & TDF_DETAILS)) 1850 { 1851 fprintf (dump_file, "Candidate (%d): ", DECL_UID (var)); 1852 print_generic_expr (dump_file, var, 0); 1853 fprintf (dump_file, "\n"); 1854 } 1855 1856 return true; 1857 } 1858 1859 /* The very first phase of intraprocedural SRA. It marks in candidate_bitmap 1860 those with type which is suitable for scalarization. */ 1861 1862 static bool 1863 find_var_candidates (void) 1864 { 1865 tree var, parm; 1866 unsigned int i; 1867 bool ret = false; 1868 1869 for (parm = DECL_ARGUMENTS (current_function_decl); 1870 parm; 1871 parm = DECL_CHAIN (parm)) 1872 ret |= maybe_add_sra_candidate (parm); 1873 1874 FOR_EACH_LOCAL_DECL (cfun, i, var) 1875 { 1876 if (TREE_CODE (var) != VAR_DECL) 1877 continue; 1878 1879 ret |= maybe_add_sra_candidate (var); 1880 } 1881 1882 return ret; 1883 } 1884 1885 /* Sort all accesses for the given variable, check for partial overlaps and 1886 return NULL if there are any. If there are none, pick a representative for 1887 each combination of offset and size and create a linked list out of them. 1888 Return the pointer to the first representative and make sure it is the first 1889 one in the vector of accesses. */ 1890 1891 static struct access * 1892 sort_and_splice_var_accesses (tree var) 1893 { 1894 int i, j, access_count; 1895 struct access *res, **prev_acc_ptr = &res; 1896 vec<access_p> *access_vec; 1897 bool first = true; 1898 HOST_WIDE_INT low = -1, high = 0; 1899 1900 access_vec = get_base_access_vector (var); 1901 if (!access_vec) 1902 return NULL; 1903 access_count = access_vec->length (); 1904 1905 /* Sort by <OFFSET, SIZE>. */ 1906 access_vec->qsort (compare_access_positions); 1907 1908 i = 0; 1909 while (i < access_count) 1910 { 1911 struct access *access = (*access_vec)[i]; 1912 bool grp_write = access->write; 1913 bool grp_read = !access->write; 1914 bool grp_scalar_write = access->write 1915 && is_gimple_reg_type (access->type); 1916 bool grp_scalar_read = !access->write 1917 && is_gimple_reg_type (access->type); 1918 bool grp_assignment_read = access->grp_assignment_read; 1919 bool grp_assignment_write = access->grp_assignment_write; 1920 bool multiple_scalar_reads = false; 1921 bool total_scalarization = access->grp_total_scalarization; 1922 bool grp_partial_lhs = access->grp_partial_lhs; 1923 bool first_scalar = is_gimple_reg_type (access->type); 1924 bool unscalarizable_region = access->grp_unscalarizable_region; 1925 1926 if (first || access->offset >= high) 1927 { 1928 first = false; 1929 low = access->offset; 1930 high = access->offset + access->size; 1931 } 1932 else if (access->offset > low && access->offset + access->size > high) 1933 return NULL; 1934 else 1935 gcc_assert (access->offset >= low 1936 && access->offset + access->size <= high); 1937 1938 j = i + 1; 1939 while (j < access_count) 1940 { 1941 struct access *ac2 = (*access_vec)[j]; 1942 if (ac2->offset != access->offset || ac2->size != access->size) 1943 break; 1944 if (ac2->write) 1945 { 1946 grp_write = true; 1947 grp_scalar_write = (grp_scalar_write 1948 || is_gimple_reg_type (ac2->type)); 1949 } 1950 else 1951 { 1952 grp_read = true; 1953 if (is_gimple_reg_type (ac2->type)) 1954 { 1955 if (grp_scalar_read) 1956 multiple_scalar_reads = true; 1957 else 1958 grp_scalar_read = true; 1959 } 1960 } 1961 grp_assignment_read |= ac2->grp_assignment_read; 1962 grp_assignment_write |= ac2->grp_assignment_write; 1963 grp_partial_lhs |= ac2->grp_partial_lhs; 1964 unscalarizable_region |= ac2->grp_unscalarizable_region; 1965 total_scalarization |= ac2->grp_total_scalarization; 1966 relink_to_new_repr (access, ac2); 1967 1968 /* If there are both aggregate-type and scalar-type accesses with 1969 this combination of size and offset, the comparison function 1970 should have put the scalars first. */ 1971 gcc_assert (first_scalar || !is_gimple_reg_type (ac2->type)); 1972 ac2->group_representative = access; 1973 j++; 1974 } 1975 1976 i = j; 1977 1978 access->group_representative = access; 1979 access->grp_write = grp_write; 1980 access->grp_read = grp_read; 1981 access->grp_scalar_read = grp_scalar_read; 1982 access->grp_scalar_write = grp_scalar_write; 1983 access->grp_assignment_read = grp_assignment_read; 1984 access->grp_assignment_write = grp_assignment_write; 1985 access->grp_hint = multiple_scalar_reads || total_scalarization; 1986 access->grp_total_scalarization = total_scalarization; 1987 access->grp_partial_lhs = grp_partial_lhs; 1988 access->grp_unscalarizable_region = unscalarizable_region; 1989 if (access->first_link) 1990 add_access_to_work_queue (access); 1991 1992 *prev_acc_ptr = access; 1993 prev_acc_ptr = &access->next_grp; 1994 } 1995 1996 gcc_assert (res == (*access_vec)[0]); 1997 return res; 1998 } 1999 2000 /* Create a variable for the given ACCESS which determines the type, name and a 2001 few other properties. Return the variable declaration and store it also to 2002 ACCESS->replacement. */ 2003 2004 static tree 2005 create_access_replacement (struct access *access) 2006 { 2007 tree repl; 2008 2009 if (access->grp_to_be_debug_replaced) 2010 { 2011 repl = create_tmp_var_raw (access->type); 2012 DECL_CONTEXT (repl) = current_function_decl; 2013 } 2014 else 2015 /* Drop any special alignment on the type if it's not on the main 2016 variant. This avoids issues with weirdo ABIs like AAPCS. */ 2017 repl = create_tmp_var (build_qualified_type 2018 (TYPE_MAIN_VARIANT (access->type), 2019 TYPE_QUALS (access->type)), "SR"); 2020 if (TREE_CODE (access->type) == COMPLEX_TYPE 2021 || TREE_CODE (access->type) == VECTOR_TYPE) 2022 { 2023 if (!access->grp_partial_lhs) 2024 DECL_GIMPLE_REG_P (repl) = 1; 2025 } 2026 else if (access->grp_partial_lhs 2027 && is_gimple_reg_type (access->type)) 2028 TREE_ADDRESSABLE (repl) = 1; 2029 2030 DECL_SOURCE_LOCATION (repl) = DECL_SOURCE_LOCATION (access->base); 2031 DECL_ARTIFICIAL (repl) = 1; 2032 DECL_IGNORED_P (repl) = DECL_IGNORED_P (access->base); 2033 2034 if (DECL_NAME (access->base) 2035 && !DECL_IGNORED_P (access->base) 2036 && !DECL_ARTIFICIAL (access->base)) 2037 { 2038 char *pretty_name = make_fancy_name (access->expr); 2039 tree debug_expr = unshare_expr_without_location (access->expr), d; 2040 bool fail = false; 2041 2042 DECL_NAME (repl) = get_identifier (pretty_name); 2043 obstack_free (&name_obstack, pretty_name); 2044 2045 /* Get rid of any SSA_NAMEs embedded in debug_expr, 2046 as DECL_DEBUG_EXPR isn't considered when looking for still 2047 used SSA_NAMEs and thus they could be freed. All debug info 2048 generation cares is whether something is constant or variable 2049 and that get_ref_base_and_extent works properly on the 2050 expression. It cannot handle accesses at a non-constant offset 2051 though, so just give up in those cases. */ 2052 for (d = debug_expr; 2053 !fail && (handled_component_p (d) || TREE_CODE (d) == MEM_REF); 2054 d = TREE_OPERAND (d, 0)) 2055 switch (TREE_CODE (d)) 2056 { 2057 case ARRAY_REF: 2058 case ARRAY_RANGE_REF: 2059 if (TREE_OPERAND (d, 1) 2060 && TREE_CODE (TREE_OPERAND (d, 1)) != INTEGER_CST) 2061 fail = true; 2062 if (TREE_OPERAND (d, 3) 2063 && TREE_CODE (TREE_OPERAND (d, 3)) != INTEGER_CST) 2064 fail = true; 2065 /* FALLTHRU */ 2066 case COMPONENT_REF: 2067 if (TREE_OPERAND (d, 2) 2068 && TREE_CODE (TREE_OPERAND (d, 2)) != INTEGER_CST) 2069 fail = true; 2070 break; 2071 case MEM_REF: 2072 if (TREE_CODE (TREE_OPERAND (d, 0)) != ADDR_EXPR) 2073 fail = true; 2074 else 2075 d = TREE_OPERAND (d, 0); 2076 break; 2077 default: 2078 break; 2079 } 2080 if (!fail) 2081 { 2082 SET_DECL_DEBUG_EXPR (repl, debug_expr); 2083 DECL_HAS_DEBUG_EXPR_P (repl) = 1; 2084 } 2085 if (access->grp_no_warning) 2086 TREE_NO_WARNING (repl) = 1; 2087 else 2088 TREE_NO_WARNING (repl) = TREE_NO_WARNING (access->base); 2089 } 2090 else 2091 TREE_NO_WARNING (repl) = 1; 2092 2093 if (dump_file) 2094 { 2095 if (access->grp_to_be_debug_replaced) 2096 { 2097 fprintf (dump_file, "Created a debug-only replacement for "); 2098 print_generic_expr (dump_file, access->base, 0); 2099 fprintf (dump_file, " offset: %u, size: %u\n", 2100 (unsigned) access->offset, (unsigned) access->size); 2101 } 2102 else 2103 { 2104 fprintf (dump_file, "Created a replacement for "); 2105 print_generic_expr (dump_file, access->base, 0); 2106 fprintf (dump_file, " offset: %u, size: %u: ", 2107 (unsigned) access->offset, (unsigned) access->size); 2108 print_generic_expr (dump_file, repl, 0); 2109 fprintf (dump_file, "\n"); 2110 } 2111 } 2112 sra_stats.replacements++; 2113 2114 return repl; 2115 } 2116 2117 /* Return ACCESS scalar replacement, create it if it does not exist yet. */ 2118 2119 static inline tree 2120 get_access_replacement (struct access *access) 2121 { 2122 gcc_checking_assert (access->replacement_decl); 2123 return access->replacement_decl; 2124 } 2125 2126 2127 /* Build a subtree of accesses rooted in *ACCESS, and move the pointer in the 2128 linked list along the way. Stop when *ACCESS is NULL or the access pointed 2129 to it is not "within" the root. Return false iff some accesses partially 2130 overlap. */ 2131 2132 static bool 2133 build_access_subtree (struct access **access) 2134 { 2135 struct access *root = *access, *last_child = NULL; 2136 HOST_WIDE_INT limit = root->offset + root->size; 2137 2138 *access = (*access)->next_grp; 2139 while (*access && (*access)->offset + (*access)->size <= limit) 2140 { 2141 if (!last_child) 2142 root->first_child = *access; 2143 else 2144 last_child->next_sibling = *access; 2145 last_child = *access; 2146 2147 if (!build_access_subtree (access)) 2148 return false; 2149 } 2150 2151 if (*access && (*access)->offset < limit) 2152 return false; 2153 2154 return true; 2155 } 2156 2157 /* Build a tree of access representatives, ACCESS is the pointer to the first 2158 one, others are linked in a list by the next_grp field. Return false iff 2159 some accesses partially overlap. */ 2160 2161 static bool 2162 build_access_trees (struct access *access) 2163 { 2164 while (access) 2165 { 2166 struct access *root = access; 2167 2168 if (!build_access_subtree (&access)) 2169 return false; 2170 root->next_grp = access; 2171 } 2172 return true; 2173 } 2174 2175 /* Return true if expr contains some ARRAY_REFs into a variable bounded 2176 array. */ 2177 2178 static bool 2179 expr_with_var_bounded_array_refs_p (tree expr) 2180 { 2181 while (handled_component_p (expr)) 2182 { 2183 if (TREE_CODE (expr) == ARRAY_REF 2184 && !tree_fits_shwi_p (array_ref_low_bound (expr))) 2185 return true; 2186 expr = TREE_OPERAND (expr, 0); 2187 } 2188 return false; 2189 } 2190 2191 /* Analyze the subtree of accesses rooted in ROOT, scheduling replacements when 2192 both seeming beneficial and when ALLOW_REPLACEMENTS allows it. Also set all 2193 sorts of access flags appropriately along the way, notably always set 2194 grp_read and grp_assign_read according to MARK_READ and grp_write when 2195 MARK_WRITE is true. 2196 2197 Creating a replacement for a scalar access is considered beneficial if its 2198 grp_hint is set (this means we are either attempting total scalarization or 2199 there is more than one direct read access) or according to the following 2200 table: 2201 2202 Access written to through a scalar type (once or more times) 2203 | 2204 | Written to in an assignment statement 2205 | | 2206 | | Access read as scalar _once_ 2207 | | | 2208 | | | Read in an assignment statement 2209 | | | | 2210 | | | | Scalarize Comment 2211 ----------------------------------------------------------------------------- 2212 0 0 0 0 No access for the scalar 2213 0 0 0 1 No access for the scalar 2214 0 0 1 0 No Single read - won't help 2215 0 0 1 1 No The same case 2216 0 1 0 0 No access for the scalar 2217 0 1 0 1 No access for the scalar 2218 0 1 1 0 Yes s = *g; return s.i; 2219 0 1 1 1 Yes The same case as above 2220 1 0 0 0 No Won't help 2221 1 0 0 1 Yes s.i = 1; *g = s; 2222 1 0 1 0 Yes s.i = 5; g = s.i; 2223 1 0 1 1 Yes The same case as above 2224 1 1 0 0 No Won't help. 2225 1 1 0 1 Yes s.i = 1; *g = s; 2226 1 1 1 0 Yes s = *g; return s.i; 2227 1 1 1 1 Yes Any of the above yeses */ 2228 2229 static bool 2230 analyze_access_subtree (struct access *root, struct access *parent, 2231 bool allow_replacements) 2232 { 2233 struct access *child; 2234 HOST_WIDE_INT limit = root->offset + root->size; 2235 HOST_WIDE_INT covered_to = root->offset; 2236 bool scalar = is_gimple_reg_type (root->type); 2237 bool hole = false, sth_created = false; 2238 2239 if (parent) 2240 { 2241 if (parent->grp_read) 2242 root->grp_read = 1; 2243 if (parent->grp_assignment_read) 2244 root->grp_assignment_read = 1; 2245 if (parent->grp_write) 2246 root->grp_write = 1; 2247 if (parent->grp_assignment_write) 2248 root->grp_assignment_write = 1; 2249 if (parent->grp_total_scalarization) 2250 root->grp_total_scalarization = 1; 2251 } 2252 2253 if (root->grp_unscalarizable_region) 2254 allow_replacements = false; 2255 2256 if (allow_replacements && expr_with_var_bounded_array_refs_p (root->expr)) 2257 allow_replacements = false; 2258 2259 for (child = root->first_child; child; child = child->next_sibling) 2260 { 2261 hole |= covered_to < child->offset; 2262 sth_created |= analyze_access_subtree (child, root, 2263 allow_replacements && !scalar); 2264 2265 root->grp_unscalarized_data |= child->grp_unscalarized_data; 2266 root->grp_total_scalarization &= child->grp_total_scalarization; 2267 if (child->grp_covered) 2268 covered_to += child->size; 2269 else 2270 hole = true; 2271 } 2272 2273 if (allow_replacements && scalar && !root->first_child 2274 && (root->grp_hint 2275 || ((root->grp_scalar_read || root->grp_assignment_read) 2276 && (root->grp_scalar_write || root->grp_assignment_write)))) 2277 { 2278 /* Always create access replacements that cover the whole access. 2279 For integral types this means the precision has to match. 2280 Avoid assumptions based on the integral type kind, too. */ 2281 if (INTEGRAL_TYPE_P (root->type) 2282 && (TREE_CODE (root->type) != INTEGER_TYPE 2283 || TYPE_PRECISION (root->type) != root->size) 2284 /* But leave bitfield accesses alone. */ 2285 && (TREE_CODE (root->expr) != COMPONENT_REF 2286 || !DECL_BIT_FIELD (TREE_OPERAND (root->expr, 1)))) 2287 { 2288 tree rt = root->type; 2289 gcc_assert ((root->offset % BITS_PER_UNIT) == 0 2290 && (root->size % BITS_PER_UNIT) == 0); 2291 root->type = build_nonstandard_integer_type (root->size, 2292 TYPE_UNSIGNED (rt)); 2293 root->expr = build_ref_for_offset (UNKNOWN_LOCATION, 2294 root->base, root->offset, 2295 root->type, NULL, false); 2296 2297 if (dump_file && (dump_flags & TDF_DETAILS)) 2298 { 2299 fprintf (dump_file, "Changing the type of a replacement for "); 2300 print_generic_expr (dump_file, root->base, 0); 2301 fprintf (dump_file, " offset: %u, size: %u ", 2302 (unsigned) root->offset, (unsigned) root->size); 2303 fprintf (dump_file, " to an integer.\n"); 2304 } 2305 } 2306 2307 root->grp_to_be_replaced = 1; 2308 root->replacement_decl = create_access_replacement (root); 2309 sth_created = true; 2310 hole = false; 2311 } 2312 else 2313 { 2314 if (allow_replacements 2315 && scalar && !root->first_child 2316 && (root->grp_scalar_write || root->grp_assignment_write) 2317 && !bitmap_bit_p (cannot_scalarize_away_bitmap, 2318 DECL_UID (root->base))) 2319 { 2320 gcc_checking_assert (!root->grp_scalar_read 2321 && !root->grp_assignment_read); 2322 sth_created = true; 2323 if (MAY_HAVE_DEBUG_STMTS) 2324 { 2325 root->grp_to_be_debug_replaced = 1; 2326 root->replacement_decl = create_access_replacement (root); 2327 } 2328 } 2329 2330 if (covered_to < limit) 2331 hole = true; 2332 if (scalar || !allow_replacements) 2333 root->grp_total_scalarization = 0; 2334 } 2335 2336 if (!hole || root->grp_total_scalarization) 2337 root->grp_covered = 1; 2338 else if (root->grp_write || TREE_CODE (root->base) == PARM_DECL) 2339 root->grp_unscalarized_data = 1; /* not covered and written to */ 2340 return sth_created; 2341 } 2342 2343 /* Analyze all access trees linked by next_grp by the means of 2344 analyze_access_subtree. */ 2345 static bool 2346 analyze_access_trees (struct access *access) 2347 { 2348 bool ret = false; 2349 2350 while (access) 2351 { 2352 if (analyze_access_subtree (access, NULL, true)) 2353 ret = true; 2354 access = access->next_grp; 2355 } 2356 2357 return ret; 2358 } 2359 2360 /* Return true iff a potential new child of LACC at offset OFFSET and with size 2361 SIZE would conflict with an already existing one. If exactly such a child 2362 already exists in LACC, store a pointer to it in EXACT_MATCH. */ 2363 2364 static bool 2365 child_would_conflict_in_lacc (struct access *lacc, HOST_WIDE_INT norm_offset, 2366 HOST_WIDE_INT size, struct access **exact_match) 2367 { 2368 struct access *child; 2369 2370 for (child = lacc->first_child; child; child = child->next_sibling) 2371 { 2372 if (child->offset == norm_offset && child->size == size) 2373 { 2374 *exact_match = child; 2375 return true; 2376 } 2377 2378 if (child->offset < norm_offset + size 2379 && child->offset + child->size > norm_offset) 2380 return true; 2381 } 2382 2383 return false; 2384 } 2385 2386 /* Create a new child access of PARENT, with all properties just like MODEL 2387 except for its offset and with its grp_write false and grp_read true. 2388 Return the new access or NULL if it cannot be created. Note that this access 2389 is created long after all splicing and sorting, it's not located in any 2390 access vector and is automatically a representative of its group. */ 2391 2392 static struct access * 2393 create_artificial_child_access (struct access *parent, struct access *model, 2394 HOST_WIDE_INT new_offset) 2395 { 2396 struct access *access; 2397 struct access **child; 2398 tree expr = parent->base; 2399 2400 gcc_assert (!model->grp_unscalarizable_region); 2401 2402 access = (struct access *) pool_alloc (access_pool); 2403 memset (access, 0, sizeof (struct access)); 2404 if (!build_user_friendly_ref_for_offset (&expr, TREE_TYPE (expr), new_offset, 2405 model->type)) 2406 { 2407 access->grp_no_warning = true; 2408 expr = build_ref_for_model (EXPR_LOCATION (parent->base), parent->base, 2409 new_offset, model, NULL, false); 2410 } 2411 2412 access->base = parent->base; 2413 access->expr = expr; 2414 access->offset = new_offset; 2415 access->size = model->size; 2416 access->type = model->type; 2417 access->grp_write = true; 2418 access->grp_read = false; 2419 2420 child = &parent->first_child; 2421 while (*child && (*child)->offset < new_offset) 2422 child = &(*child)->next_sibling; 2423 2424 access->next_sibling = *child; 2425 *child = access; 2426 2427 return access; 2428 } 2429 2430 2431 /* Propagate all subaccesses of RACC across an assignment link to LACC. Return 2432 true if any new subaccess was created. Additionally, if RACC is a scalar 2433 access but LACC is not, change the type of the latter, if possible. */ 2434 2435 static bool 2436 propagate_subaccesses_across_link (struct access *lacc, struct access *racc) 2437 { 2438 struct access *rchild; 2439 HOST_WIDE_INT norm_delta = lacc->offset - racc->offset; 2440 bool ret = false; 2441 2442 if (is_gimple_reg_type (lacc->type) 2443 || lacc->grp_unscalarizable_region 2444 || racc->grp_unscalarizable_region) 2445 return false; 2446 2447 if (is_gimple_reg_type (racc->type)) 2448 { 2449 if (!lacc->first_child && !racc->first_child) 2450 { 2451 tree t = lacc->base; 2452 2453 lacc->type = racc->type; 2454 if (build_user_friendly_ref_for_offset (&t, TREE_TYPE (t), 2455 lacc->offset, racc->type)) 2456 lacc->expr = t; 2457 else 2458 { 2459 lacc->expr = build_ref_for_model (EXPR_LOCATION (lacc->base), 2460 lacc->base, lacc->offset, 2461 racc, NULL, false); 2462 lacc->grp_no_warning = true; 2463 } 2464 } 2465 return false; 2466 } 2467 2468 for (rchild = racc->first_child; rchild; rchild = rchild->next_sibling) 2469 { 2470 struct access *new_acc = NULL; 2471 HOST_WIDE_INT norm_offset = rchild->offset + norm_delta; 2472 2473 if (rchild->grp_unscalarizable_region) 2474 continue; 2475 2476 if (child_would_conflict_in_lacc (lacc, norm_offset, rchild->size, 2477 &new_acc)) 2478 { 2479 if (new_acc) 2480 { 2481 rchild->grp_hint = 1; 2482 new_acc->grp_hint |= new_acc->grp_read; 2483 if (rchild->first_child) 2484 ret |= propagate_subaccesses_across_link (new_acc, rchild); 2485 } 2486 continue; 2487 } 2488 2489 rchild->grp_hint = 1; 2490 new_acc = create_artificial_child_access (lacc, rchild, norm_offset); 2491 if (new_acc) 2492 { 2493 ret = true; 2494 if (racc->first_child) 2495 propagate_subaccesses_across_link (new_acc, rchild); 2496 } 2497 } 2498 2499 return ret; 2500 } 2501 2502 /* Propagate all subaccesses across assignment links. */ 2503 2504 static void 2505 propagate_all_subaccesses (void) 2506 { 2507 while (work_queue_head) 2508 { 2509 struct access *racc = pop_access_from_work_queue (); 2510 struct assign_link *link; 2511 2512 gcc_assert (racc->first_link); 2513 2514 for (link = racc->first_link; link; link = link->next) 2515 { 2516 struct access *lacc = link->lacc; 2517 2518 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (lacc->base))) 2519 continue; 2520 lacc = lacc->group_representative; 2521 if (propagate_subaccesses_across_link (lacc, racc) 2522 && lacc->first_link) 2523 add_access_to_work_queue (lacc); 2524 } 2525 } 2526 } 2527 2528 /* Go through all accesses collected throughout the (intraprocedural) analysis 2529 stage, exclude overlapping ones, identify representatives and build trees 2530 out of them, making decisions about scalarization on the way. Return true 2531 iff there are any to-be-scalarized variables after this stage. */ 2532 2533 static bool 2534 analyze_all_variable_accesses (void) 2535 { 2536 int res = 0; 2537 bitmap tmp = BITMAP_ALLOC (NULL); 2538 bitmap_iterator bi; 2539 unsigned i; 2540 bool optimize_speed_p = !optimize_function_for_size_p (cfun); 2541 2542 enum compiler_param param = optimize_speed_p 2543 ? PARAM_SRA_MAX_SCALARIZATION_SIZE_SPEED 2544 : PARAM_SRA_MAX_SCALARIZATION_SIZE_SIZE; 2545 2546 /* If the user didn't set PARAM_SRA_MAX_SCALARIZATION_SIZE_<...>, 2547 fall back to a target default. */ 2548 unsigned HOST_WIDE_INT max_scalarization_size 2549 = global_options_set.x_param_values[param] 2550 ? PARAM_VALUE (param) 2551 : get_move_ratio (optimize_speed_p) * UNITS_PER_WORD; 2552 2553 max_scalarization_size *= BITS_PER_UNIT; 2554 2555 EXECUTE_IF_SET_IN_BITMAP (candidate_bitmap, 0, i, bi) 2556 if (bitmap_bit_p (should_scalarize_away_bitmap, i) 2557 && !bitmap_bit_p (cannot_scalarize_away_bitmap, i)) 2558 { 2559 tree var = candidate (i); 2560 2561 if (TREE_CODE (var) == VAR_DECL 2562 && type_consists_of_records_p (TREE_TYPE (var))) 2563 { 2564 if (tree_to_uhwi (TYPE_SIZE (TREE_TYPE (var))) 2565 <= max_scalarization_size) 2566 { 2567 completely_scalarize_var (var); 2568 if (dump_file && (dump_flags & TDF_DETAILS)) 2569 { 2570 fprintf (dump_file, "Will attempt to totally scalarize "); 2571 print_generic_expr (dump_file, var, 0); 2572 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var)); 2573 } 2574 } 2575 else if (dump_file && (dump_flags & TDF_DETAILS)) 2576 { 2577 fprintf (dump_file, "Too big to totally scalarize: "); 2578 print_generic_expr (dump_file, var, 0); 2579 fprintf (dump_file, " (UID: %u)\n", DECL_UID (var)); 2580 } 2581 } 2582 } 2583 2584 bitmap_copy (tmp, candidate_bitmap); 2585 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi) 2586 { 2587 tree var = candidate (i); 2588 struct access *access; 2589 2590 access = sort_and_splice_var_accesses (var); 2591 if (!access || !build_access_trees (access)) 2592 disqualify_candidate (var, 2593 "No or inhibitingly overlapping accesses."); 2594 } 2595 2596 propagate_all_subaccesses (); 2597 2598 bitmap_copy (tmp, candidate_bitmap); 2599 EXECUTE_IF_SET_IN_BITMAP (tmp, 0, i, bi) 2600 { 2601 tree var = candidate (i); 2602 struct access *access = get_first_repr_for_decl (var); 2603 2604 if (analyze_access_trees (access)) 2605 { 2606 res++; 2607 if (dump_file && (dump_flags & TDF_DETAILS)) 2608 { 2609 fprintf (dump_file, "\nAccess trees for "); 2610 print_generic_expr (dump_file, var, 0); 2611 fprintf (dump_file, " (UID: %u): \n", DECL_UID (var)); 2612 dump_access_tree (dump_file, access); 2613 fprintf (dump_file, "\n"); 2614 } 2615 } 2616 else 2617 disqualify_candidate (var, "No scalar replacements to be created."); 2618 } 2619 2620 BITMAP_FREE (tmp); 2621 2622 if (res) 2623 { 2624 statistics_counter_event (cfun, "Scalarized aggregates", res); 2625 return true; 2626 } 2627 else 2628 return false; 2629 } 2630 2631 /* Generate statements copying scalar replacements of accesses within a subtree 2632 into or out of AGG. ACCESS, all its children, siblings and their children 2633 are to be processed. AGG is an aggregate type expression (can be a 2634 declaration but does not have to be, it can for example also be a mem_ref or 2635 a series of handled components). TOP_OFFSET is the offset of the processed 2636 subtree which has to be subtracted from offsets of individual accesses to 2637 get corresponding offsets for AGG. If CHUNK_SIZE is non-null, copy only 2638 replacements in the interval <start_offset, start_offset + chunk_size>, 2639 otherwise copy all. GSI is a statement iterator used to place the new 2640 statements. WRITE should be true when the statements should write from AGG 2641 to the replacement and false if vice versa. if INSERT_AFTER is true, new 2642 statements will be added after the current statement in GSI, they will be 2643 added before the statement otherwise. */ 2644 2645 static void 2646 generate_subtree_copies (struct access *access, tree agg, 2647 HOST_WIDE_INT top_offset, 2648 HOST_WIDE_INT start_offset, HOST_WIDE_INT chunk_size, 2649 gimple_stmt_iterator *gsi, bool write, 2650 bool insert_after, location_t loc) 2651 { 2652 do 2653 { 2654 if (chunk_size && access->offset >= start_offset + chunk_size) 2655 return; 2656 2657 if (access->grp_to_be_replaced 2658 && (chunk_size == 0 2659 || access->offset + access->size > start_offset)) 2660 { 2661 tree expr, repl = get_access_replacement (access); 2662 gassign *stmt; 2663 2664 expr = build_ref_for_model (loc, agg, access->offset - top_offset, 2665 access, gsi, insert_after); 2666 2667 if (write) 2668 { 2669 if (access->grp_partial_lhs) 2670 expr = force_gimple_operand_gsi (gsi, expr, true, NULL_TREE, 2671 !insert_after, 2672 insert_after ? GSI_NEW_STMT 2673 : GSI_SAME_STMT); 2674 stmt = gimple_build_assign (repl, expr); 2675 } 2676 else 2677 { 2678 TREE_NO_WARNING (repl) = 1; 2679 if (access->grp_partial_lhs) 2680 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE, 2681 !insert_after, 2682 insert_after ? GSI_NEW_STMT 2683 : GSI_SAME_STMT); 2684 stmt = gimple_build_assign (expr, repl); 2685 } 2686 gimple_set_location (stmt, loc); 2687 2688 if (insert_after) 2689 gsi_insert_after (gsi, stmt, GSI_NEW_STMT); 2690 else 2691 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 2692 update_stmt (stmt); 2693 sra_stats.subtree_copies++; 2694 } 2695 else if (write 2696 && access->grp_to_be_debug_replaced 2697 && (chunk_size == 0 2698 || access->offset + access->size > start_offset)) 2699 { 2700 gdebug *ds; 2701 tree drhs = build_debug_ref_for_model (loc, agg, 2702 access->offset - top_offset, 2703 access); 2704 ds = gimple_build_debug_bind (get_access_replacement (access), 2705 drhs, gsi_stmt (*gsi)); 2706 if (insert_after) 2707 gsi_insert_after (gsi, ds, GSI_NEW_STMT); 2708 else 2709 gsi_insert_before (gsi, ds, GSI_SAME_STMT); 2710 } 2711 2712 if (access->first_child) 2713 generate_subtree_copies (access->first_child, agg, top_offset, 2714 start_offset, chunk_size, gsi, 2715 write, insert_after, loc); 2716 2717 access = access->next_sibling; 2718 } 2719 while (access); 2720 } 2721 2722 /* Assign zero to all scalar replacements in an access subtree. ACCESS is the 2723 the root of the subtree to be processed. GSI is the statement iterator used 2724 for inserting statements which are added after the current statement if 2725 INSERT_AFTER is true or before it otherwise. */ 2726 2727 static void 2728 init_subtree_with_zero (struct access *access, gimple_stmt_iterator *gsi, 2729 bool insert_after, location_t loc) 2730 2731 { 2732 struct access *child; 2733 2734 if (access->grp_to_be_replaced) 2735 { 2736 gassign *stmt; 2737 2738 stmt = gimple_build_assign (get_access_replacement (access), 2739 build_zero_cst (access->type)); 2740 if (insert_after) 2741 gsi_insert_after (gsi, stmt, GSI_NEW_STMT); 2742 else 2743 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 2744 update_stmt (stmt); 2745 gimple_set_location (stmt, loc); 2746 } 2747 else if (access->grp_to_be_debug_replaced) 2748 { 2749 gdebug *ds 2750 = gimple_build_debug_bind (get_access_replacement (access), 2751 build_zero_cst (access->type), 2752 gsi_stmt (*gsi)); 2753 if (insert_after) 2754 gsi_insert_after (gsi, ds, GSI_NEW_STMT); 2755 else 2756 gsi_insert_before (gsi, ds, GSI_SAME_STMT); 2757 } 2758 2759 for (child = access->first_child; child; child = child->next_sibling) 2760 init_subtree_with_zero (child, gsi, insert_after, loc); 2761 } 2762 2763 /* Clobber all scalar replacements in an access subtree. ACCESS is the the 2764 root of the subtree to be processed. GSI is the statement iterator used 2765 for inserting statements which are added after the current statement if 2766 INSERT_AFTER is true or before it otherwise. */ 2767 2768 static void 2769 clobber_subtree (struct access *access, gimple_stmt_iterator *gsi, 2770 bool insert_after, location_t loc) 2771 2772 { 2773 struct access *child; 2774 2775 if (access->grp_to_be_replaced) 2776 { 2777 tree rep = get_access_replacement (access); 2778 tree clobber = build_constructor (access->type, NULL); 2779 TREE_THIS_VOLATILE (clobber) = 1; 2780 gimple stmt = gimple_build_assign (rep, clobber); 2781 2782 if (insert_after) 2783 gsi_insert_after (gsi, stmt, GSI_NEW_STMT); 2784 else 2785 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 2786 update_stmt (stmt); 2787 gimple_set_location (stmt, loc); 2788 } 2789 2790 for (child = access->first_child; child; child = child->next_sibling) 2791 clobber_subtree (child, gsi, insert_after, loc); 2792 } 2793 2794 /* Search for an access representative for the given expression EXPR and 2795 return it or NULL if it cannot be found. */ 2796 2797 static struct access * 2798 get_access_for_expr (tree expr) 2799 { 2800 HOST_WIDE_INT offset, size, max_size; 2801 tree base; 2802 2803 /* FIXME: This should not be necessary but Ada produces V_C_Es with a type of 2804 a different size than the size of its argument and we need the latter 2805 one. */ 2806 if (TREE_CODE (expr) == VIEW_CONVERT_EXPR) 2807 expr = TREE_OPERAND (expr, 0); 2808 2809 base = get_ref_base_and_extent (expr, &offset, &size, &max_size); 2810 if (max_size == -1 || !DECL_P (base)) 2811 return NULL; 2812 2813 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (base))) 2814 return NULL; 2815 2816 return get_var_base_offset_size_access (base, offset, max_size); 2817 } 2818 2819 /* Replace the expression EXPR with a scalar replacement if there is one and 2820 generate other statements to do type conversion or subtree copying if 2821 necessary. GSI is used to place newly created statements, WRITE is true if 2822 the expression is being written to (it is on a LHS of a statement or output 2823 in an assembly statement). */ 2824 2825 static bool 2826 sra_modify_expr (tree *expr, gimple_stmt_iterator *gsi, bool write) 2827 { 2828 location_t loc; 2829 struct access *access; 2830 tree type, bfr, orig_expr; 2831 2832 if (TREE_CODE (*expr) == BIT_FIELD_REF) 2833 { 2834 bfr = *expr; 2835 expr = &TREE_OPERAND (*expr, 0); 2836 } 2837 else 2838 bfr = NULL_TREE; 2839 2840 if (TREE_CODE (*expr) == REALPART_EXPR || TREE_CODE (*expr) == IMAGPART_EXPR) 2841 expr = &TREE_OPERAND (*expr, 0); 2842 access = get_access_for_expr (*expr); 2843 if (!access) 2844 return false; 2845 type = TREE_TYPE (*expr); 2846 orig_expr = *expr; 2847 2848 loc = gimple_location (gsi_stmt (*gsi)); 2849 gimple_stmt_iterator alt_gsi = gsi_none (); 2850 if (write && stmt_ends_bb_p (gsi_stmt (*gsi))) 2851 { 2852 alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi))); 2853 gsi = &alt_gsi; 2854 } 2855 2856 if (access->grp_to_be_replaced) 2857 { 2858 tree repl = get_access_replacement (access); 2859 /* If we replace a non-register typed access simply use the original 2860 access expression to extract the scalar component afterwards. 2861 This happens if scalarizing a function return value or parameter 2862 like in gcc.c-torture/execute/20041124-1.c, 20050316-1.c and 2863 gcc.c-torture/compile/20011217-1.c. 2864 2865 We also want to use this when accessing a complex or vector which can 2866 be accessed as a different type too, potentially creating a need for 2867 type conversion (see PR42196) and when scalarized unions are involved 2868 in assembler statements (see PR42398). */ 2869 if (!useless_type_conversion_p (type, access->type)) 2870 { 2871 tree ref; 2872 2873 ref = build_ref_for_model (loc, orig_expr, 0, access, gsi, false); 2874 2875 if (write) 2876 { 2877 gassign *stmt; 2878 2879 if (access->grp_partial_lhs) 2880 ref = force_gimple_operand_gsi (gsi, ref, true, NULL_TREE, 2881 false, GSI_NEW_STMT); 2882 stmt = gimple_build_assign (repl, ref); 2883 gimple_set_location (stmt, loc); 2884 gsi_insert_after (gsi, stmt, GSI_NEW_STMT); 2885 } 2886 else 2887 { 2888 gassign *stmt; 2889 2890 if (access->grp_partial_lhs) 2891 repl = force_gimple_operand_gsi (gsi, repl, true, NULL_TREE, 2892 true, GSI_SAME_STMT); 2893 stmt = gimple_build_assign (ref, repl); 2894 gimple_set_location (stmt, loc); 2895 gsi_insert_before (gsi, stmt, GSI_SAME_STMT); 2896 } 2897 } 2898 else 2899 *expr = repl; 2900 sra_stats.exprs++; 2901 } 2902 else if (write && access->grp_to_be_debug_replaced) 2903 { 2904 gdebug *ds = gimple_build_debug_bind (get_access_replacement (access), 2905 NULL_TREE, 2906 gsi_stmt (*gsi)); 2907 gsi_insert_after (gsi, ds, GSI_NEW_STMT); 2908 } 2909 2910 if (access->first_child) 2911 { 2912 HOST_WIDE_INT start_offset, chunk_size; 2913 if (bfr 2914 && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1)) 2915 && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2))) 2916 { 2917 chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1)); 2918 start_offset = access->offset 2919 + tree_to_uhwi (TREE_OPERAND (bfr, 2)); 2920 } 2921 else 2922 start_offset = chunk_size = 0; 2923 2924 generate_subtree_copies (access->first_child, orig_expr, access->offset, 2925 start_offset, chunk_size, gsi, write, write, 2926 loc); 2927 } 2928 return true; 2929 } 2930 2931 /* Where scalar replacements of the RHS have been written to when a replacement 2932 of a LHS of an assigments cannot be direclty loaded from a replacement of 2933 the RHS. */ 2934 enum unscalarized_data_handling { SRA_UDH_NONE, /* Nothing done so far. */ 2935 SRA_UDH_RIGHT, /* Data flushed to the RHS. */ 2936 SRA_UDH_LEFT }; /* Data flushed to the LHS. */ 2937 2938 struct subreplacement_assignment_data 2939 { 2940 /* Offset of the access representing the lhs of the assignment. */ 2941 HOST_WIDE_INT left_offset; 2942 2943 /* LHS and RHS of the original assignment. */ 2944 tree assignment_lhs, assignment_rhs; 2945 2946 /* Access representing the rhs of the whole assignment. */ 2947 struct access *top_racc; 2948 2949 /* Stmt iterator used for statement insertions after the original assignment. 2950 It points to the main GSI used to traverse a BB during function body 2951 modification. */ 2952 gimple_stmt_iterator *new_gsi; 2953 2954 /* Stmt iterator used for statement insertions before the original 2955 assignment. Keeps on pointing to the original statement. */ 2956 gimple_stmt_iterator old_gsi; 2957 2958 /* Location of the assignment. */ 2959 location_t loc; 2960 2961 /* Keeps the information whether we have needed to refresh replacements of 2962 the LHS and from which side of the assignments this takes place. */ 2963 enum unscalarized_data_handling refreshed; 2964 }; 2965 2966 /* Store all replacements in the access tree rooted in TOP_RACC either to their 2967 base aggregate if there are unscalarized data or directly to LHS of the 2968 statement that is pointed to by GSI otherwise. */ 2969 2970 static void 2971 handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad) 2972 { 2973 tree src; 2974 if (sad->top_racc->grp_unscalarized_data) 2975 { 2976 src = sad->assignment_rhs; 2977 sad->refreshed = SRA_UDH_RIGHT; 2978 } 2979 else 2980 { 2981 src = sad->assignment_lhs; 2982 sad->refreshed = SRA_UDH_LEFT; 2983 } 2984 generate_subtree_copies (sad->top_racc->first_child, src, 2985 sad->top_racc->offset, 0, 0, 2986 &sad->old_gsi, false, false, sad->loc); 2987 } 2988 2989 /* Try to generate statements to load all sub-replacements in an access subtree 2990 formed by children of LACC from scalar replacements in the SAD->top_racc 2991 subtree. If that is not possible, refresh the SAD->top_racc base aggregate 2992 and load the accesses from it. */ 2993 2994 static void 2995 load_assign_lhs_subreplacements (struct access *lacc, 2996 struct subreplacement_assignment_data *sad) 2997 { 2998 for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling) 2999 { 3000 HOST_WIDE_INT offset; 3001 offset = lacc->offset - sad->left_offset + sad->top_racc->offset; 3002 3003 if (lacc->grp_to_be_replaced) 3004 { 3005 struct access *racc; 3006 gassign *stmt; 3007 tree rhs; 3008 3009 racc = find_access_in_subtree (sad->top_racc, offset, lacc->size); 3010 if (racc && racc->grp_to_be_replaced) 3011 { 3012 rhs = get_access_replacement (racc); 3013 if (!useless_type_conversion_p (lacc->type, racc->type)) 3014 rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR, 3015 lacc->type, rhs); 3016 3017 if (racc->grp_partial_lhs && lacc->grp_partial_lhs) 3018 rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true, 3019 NULL_TREE, true, GSI_SAME_STMT); 3020 } 3021 else 3022 { 3023 /* No suitable access on the right hand side, need to load from 3024 the aggregate. See if we have to update it first... */ 3025 if (sad->refreshed == SRA_UDH_NONE) 3026 handle_unscalarized_data_in_subtree (sad); 3027 3028 if (sad->refreshed == SRA_UDH_LEFT) 3029 rhs = build_ref_for_model (sad->loc, sad->assignment_lhs, 3030 lacc->offset - sad->left_offset, 3031 lacc, sad->new_gsi, true); 3032 else 3033 rhs = build_ref_for_model (sad->loc, sad->assignment_rhs, 3034 lacc->offset - sad->left_offset, 3035 lacc, sad->new_gsi, true); 3036 if (lacc->grp_partial_lhs) 3037 rhs = force_gimple_operand_gsi (sad->new_gsi, 3038 rhs, true, NULL_TREE, 3039 false, GSI_NEW_STMT); 3040 } 3041 3042 stmt = gimple_build_assign (get_access_replacement (lacc), rhs); 3043 gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT); 3044 gimple_set_location (stmt, sad->loc); 3045 update_stmt (stmt); 3046 sra_stats.subreplacements++; 3047 } 3048 else 3049 { 3050 if (sad->refreshed == SRA_UDH_NONE 3051 && lacc->grp_read && !lacc->grp_covered) 3052 handle_unscalarized_data_in_subtree (sad); 3053 3054 if (lacc && lacc->grp_to_be_debug_replaced) 3055 { 3056 gdebug *ds; 3057 tree drhs; 3058 struct access *racc = find_access_in_subtree (sad->top_racc, 3059 offset, 3060 lacc->size); 3061 3062 if (racc && racc->grp_to_be_replaced) 3063 { 3064 if (racc->grp_write) 3065 drhs = get_access_replacement (racc); 3066 else 3067 drhs = NULL; 3068 } 3069 else if (sad->refreshed == SRA_UDH_LEFT) 3070 drhs = build_debug_ref_for_model (sad->loc, lacc->base, 3071 lacc->offset, lacc); 3072 else if (sad->refreshed == SRA_UDH_RIGHT) 3073 drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base, 3074 offset, lacc); 3075 else 3076 drhs = NULL_TREE; 3077 if (drhs 3078 && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs))) 3079 drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR, 3080 lacc->type, drhs); 3081 ds = gimple_build_debug_bind (get_access_replacement (lacc), 3082 drhs, gsi_stmt (sad->old_gsi)); 3083 gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT); 3084 } 3085 } 3086 3087 if (lacc->first_child) 3088 load_assign_lhs_subreplacements (lacc, sad); 3089 } 3090 } 3091 3092 /* Result code for SRA assignment modification. */ 3093 enum assignment_mod_result { SRA_AM_NONE, /* nothing done for the stmt */ 3094 SRA_AM_MODIFIED, /* stmt changed but not 3095 removed */ 3096 SRA_AM_REMOVED }; /* stmt eliminated */ 3097 3098 /* Modify assignments with a CONSTRUCTOR on their RHS. STMT contains a pointer 3099 to the assignment and GSI is the statement iterator pointing at it. Returns 3100 the same values as sra_modify_assign. */ 3101 3102 static enum assignment_mod_result 3103 sra_modify_constructor_assign (gimple stmt, gimple_stmt_iterator *gsi) 3104 { 3105 tree lhs = gimple_assign_lhs (stmt); 3106 struct access *acc = get_access_for_expr (lhs); 3107 if (!acc) 3108 return SRA_AM_NONE; 3109 location_t loc = gimple_location (stmt); 3110 3111 if (gimple_clobber_p (stmt)) 3112 { 3113 /* Clobber the replacement variable. */ 3114 clobber_subtree (acc, gsi, !acc->grp_covered, loc); 3115 /* Remove clobbers of fully scalarized variables, they are dead. */ 3116 if (acc->grp_covered) 3117 { 3118 unlink_stmt_vdef (stmt); 3119 gsi_remove (gsi, true); 3120 release_defs (stmt); 3121 return SRA_AM_REMOVED; 3122 } 3123 else 3124 return SRA_AM_MODIFIED; 3125 } 3126 3127 if (vec_safe_length (CONSTRUCTOR_ELTS (gimple_assign_rhs1 (stmt))) > 0) 3128 { 3129 /* I have never seen this code path trigger but if it can happen the 3130 following should handle it gracefully. */ 3131 if (access_has_children_p (acc)) 3132 generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi, 3133 true, true, loc); 3134 return SRA_AM_MODIFIED; 3135 } 3136 3137 if (acc->grp_covered) 3138 { 3139 init_subtree_with_zero (acc, gsi, false, loc); 3140 unlink_stmt_vdef (stmt); 3141 gsi_remove (gsi, true); 3142 release_defs (stmt); 3143 return SRA_AM_REMOVED; 3144 } 3145 else 3146 { 3147 init_subtree_with_zero (acc, gsi, true, loc); 3148 return SRA_AM_MODIFIED; 3149 } 3150 } 3151 3152 /* Create and return a new suitable default definition SSA_NAME for RACC which 3153 is an access describing an uninitialized part of an aggregate that is being 3154 loaded. */ 3155 3156 static tree 3157 get_repl_default_def_ssa_name (struct access *racc) 3158 { 3159 gcc_checking_assert (!racc->grp_to_be_replaced 3160 && !racc->grp_to_be_debug_replaced); 3161 if (!racc->replacement_decl) 3162 racc->replacement_decl = create_access_replacement (racc); 3163 return get_or_create_ssa_default_def (cfun, racc->replacement_decl); 3164 } 3165 3166 /* Return true if REF has an VIEW_CONVERT_EXPR or a COMPONENT_REF with a 3167 bit-field field declaration somewhere in it. */ 3168 3169 static inline bool 3170 contains_vce_or_bfcref_p (const_tree ref) 3171 { 3172 while (handled_component_p (ref)) 3173 { 3174 if (TREE_CODE (ref) == VIEW_CONVERT_EXPR 3175 || (TREE_CODE (ref) == COMPONENT_REF 3176 && DECL_BIT_FIELD (TREE_OPERAND (ref, 1)))) 3177 return true; 3178 ref = TREE_OPERAND (ref, 0); 3179 } 3180 3181 return false; 3182 } 3183 3184 /* Examine both sides of the assignment statement pointed to by STMT, replace 3185 them with a scalare replacement if there is one and generate copying of 3186 replacements if scalarized aggregates have been used in the assignment. GSI 3187 is used to hold generated statements for type conversions and subtree 3188 copying. */ 3189 3190 static enum assignment_mod_result 3191 sra_modify_assign (gimple stmt, gimple_stmt_iterator *gsi) 3192 { 3193 struct access *lacc, *racc; 3194 tree lhs, rhs; 3195 bool modify_this_stmt = false; 3196 bool force_gimple_rhs = false; 3197 location_t loc; 3198 gimple_stmt_iterator orig_gsi = *gsi; 3199 3200 if (!gimple_assign_single_p (stmt)) 3201 return SRA_AM_NONE; 3202 lhs = gimple_assign_lhs (stmt); 3203 rhs = gimple_assign_rhs1 (stmt); 3204 3205 if (TREE_CODE (rhs) == CONSTRUCTOR) 3206 return sra_modify_constructor_assign (stmt, gsi); 3207 3208 if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR 3209 || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR 3210 || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF) 3211 { 3212 modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt), 3213 gsi, false); 3214 modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt), 3215 gsi, true); 3216 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE; 3217 } 3218 3219 lacc = get_access_for_expr (lhs); 3220 racc = get_access_for_expr (rhs); 3221 if (!lacc && !racc) 3222 return SRA_AM_NONE; 3223 3224 loc = gimple_location (stmt); 3225 if (lacc && lacc->grp_to_be_replaced) 3226 { 3227 lhs = get_access_replacement (lacc); 3228 gimple_assign_set_lhs (stmt, lhs); 3229 modify_this_stmt = true; 3230 if (lacc->grp_partial_lhs) 3231 force_gimple_rhs = true; 3232 sra_stats.exprs++; 3233 } 3234 3235 if (racc && racc->grp_to_be_replaced) 3236 { 3237 rhs = get_access_replacement (racc); 3238 modify_this_stmt = true; 3239 if (racc->grp_partial_lhs) 3240 force_gimple_rhs = true; 3241 sra_stats.exprs++; 3242 } 3243 else if (racc 3244 && !racc->grp_unscalarized_data 3245 && !racc->grp_unscalarizable_region 3246 && TREE_CODE (lhs) == SSA_NAME 3247 && !access_has_replacements_p (racc)) 3248 { 3249 rhs = get_repl_default_def_ssa_name (racc); 3250 modify_this_stmt = true; 3251 sra_stats.exprs++; 3252 } 3253 3254 if (modify_this_stmt) 3255 { 3256 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 3257 { 3258 /* If we can avoid creating a VIEW_CONVERT_EXPR do so. 3259 ??? This should move to fold_stmt which we simply should 3260 call after building a VIEW_CONVERT_EXPR here. */ 3261 if (AGGREGATE_TYPE_P (TREE_TYPE (lhs)) 3262 && !contains_bitfld_component_ref_p (lhs)) 3263 { 3264 lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false); 3265 gimple_assign_set_lhs (stmt, lhs); 3266 } 3267 else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs)) 3268 && !contains_vce_or_bfcref_p (rhs)) 3269 rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false); 3270 3271 if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs))) 3272 { 3273 rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs), 3274 rhs); 3275 if (is_gimple_reg_type (TREE_TYPE (lhs)) 3276 && TREE_CODE (lhs) != SSA_NAME) 3277 force_gimple_rhs = true; 3278 } 3279 } 3280 } 3281 3282 if (lacc && lacc->grp_to_be_debug_replaced) 3283 { 3284 tree dlhs = get_access_replacement (lacc); 3285 tree drhs = unshare_expr (rhs); 3286 if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs))) 3287 { 3288 if (AGGREGATE_TYPE_P (TREE_TYPE (drhs)) 3289 && !contains_vce_or_bfcref_p (drhs)) 3290 drhs = build_debug_ref_for_model (loc, drhs, 0, lacc); 3291 if (drhs 3292 && !useless_type_conversion_p (TREE_TYPE (dlhs), 3293 TREE_TYPE (drhs))) 3294 drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, 3295 TREE_TYPE (dlhs), drhs); 3296 } 3297 gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt); 3298 gsi_insert_before (gsi, ds, GSI_SAME_STMT); 3299 } 3300 3301 /* From this point on, the function deals with assignments in between 3302 aggregates when at least one has scalar reductions of some of its 3303 components. There are three possible scenarios: Both the LHS and RHS have 3304 to-be-scalarized components, 2) only the RHS has or 3) only the LHS has. 3305 3306 In the first case, we would like to load the LHS components from RHS 3307 components whenever possible. If that is not possible, we would like to 3308 read it directly from the RHS (after updating it by storing in it its own 3309 components). If there are some necessary unscalarized data in the LHS, 3310 those will be loaded by the original assignment too. If neither of these 3311 cases happen, the original statement can be removed. Most of this is done 3312 by load_assign_lhs_subreplacements. 3313 3314 In the second case, we would like to store all RHS scalarized components 3315 directly into LHS and if they cover the aggregate completely, remove the 3316 statement too. In the third case, we want the LHS components to be loaded 3317 directly from the RHS (DSE will remove the original statement if it 3318 becomes redundant). 3319 3320 This is a bit complex but manageable when types match and when unions do 3321 not cause confusion in a way that we cannot really load a component of LHS 3322 from the RHS or vice versa (the access representing this level can have 3323 subaccesses that are accessible only through a different union field at a 3324 higher level - different from the one used in the examined expression). 3325 Unions are fun. 3326 3327 Therefore, I specially handle a fourth case, happening when there is a 3328 specific type cast or it is impossible to locate a scalarized subaccess on 3329 the other side of the expression. If that happens, I simply "refresh" the 3330 RHS by storing in it is scalarized components leave the original statement 3331 there to do the copying and then load the scalar replacements of the LHS. 3332 This is what the first branch does. */ 3333 3334 if (modify_this_stmt 3335 || gimple_has_volatile_ops (stmt) 3336 || contains_vce_or_bfcref_p (rhs) 3337 || contains_vce_or_bfcref_p (lhs) 3338 || stmt_ends_bb_p (stmt)) 3339 { 3340 if (access_has_children_p (racc)) 3341 generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0, 3342 gsi, false, false, loc); 3343 if (access_has_children_p (lacc)) 3344 { 3345 gimple_stmt_iterator alt_gsi = gsi_none (); 3346 if (stmt_ends_bb_p (stmt)) 3347 { 3348 alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi))); 3349 gsi = &alt_gsi; 3350 } 3351 generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0, 3352 gsi, true, true, loc); 3353 } 3354 sra_stats.separate_lhs_rhs_handling++; 3355 3356 /* This gimplification must be done after generate_subtree_copies, 3357 lest we insert the subtree copies in the middle of the gimplified 3358 sequence. */ 3359 if (force_gimple_rhs) 3360 rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE, 3361 true, GSI_SAME_STMT); 3362 if (gimple_assign_rhs1 (stmt) != rhs) 3363 { 3364 modify_this_stmt = true; 3365 gimple_assign_set_rhs_from_tree (&orig_gsi, rhs); 3366 gcc_assert (stmt == gsi_stmt (orig_gsi)); 3367 } 3368 3369 return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE; 3370 } 3371 else 3372 { 3373 if (access_has_children_p (lacc) 3374 && access_has_children_p (racc) 3375 /* When an access represents an unscalarizable region, it usually 3376 represents accesses with variable offset and thus must not be used 3377 to generate new memory accesses. */ 3378 && !lacc->grp_unscalarizable_region 3379 && !racc->grp_unscalarizable_region) 3380 { 3381 struct subreplacement_assignment_data sad; 3382 3383 sad.left_offset = lacc->offset; 3384 sad.assignment_lhs = lhs; 3385 sad.assignment_rhs = rhs; 3386 sad.top_racc = racc; 3387 sad.old_gsi = *gsi; 3388 sad.new_gsi = gsi; 3389 sad.loc = gimple_location (stmt); 3390 sad.refreshed = SRA_UDH_NONE; 3391 3392 if (lacc->grp_read && !lacc->grp_covered) 3393 handle_unscalarized_data_in_subtree (&sad); 3394 3395 load_assign_lhs_subreplacements (lacc, &sad); 3396 if (sad.refreshed != SRA_UDH_RIGHT) 3397 { 3398 gsi_next (gsi); 3399 unlink_stmt_vdef (stmt); 3400 gsi_remove (&sad.old_gsi, true); 3401 release_defs (stmt); 3402 sra_stats.deleted++; 3403 return SRA_AM_REMOVED; 3404 } 3405 } 3406 else 3407 { 3408 if (access_has_children_p (racc) 3409 && !racc->grp_unscalarized_data 3410 && TREE_CODE (lhs) != SSA_NAME) 3411 { 3412 if (dump_file) 3413 { 3414 fprintf (dump_file, "Removing load: "); 3415 print_gimple_stmt (dump_file, stmt, 0, 0); 3416 } 3417 generate_subtree_copies (racc->first_child, lhs, 3418 racc->offset, 0, 0, gsi, 3419 false, false, loc); 3420 gcc_assert (stmt == gsi_stmt (*gsi)); 3421 unlink_stmt_vdef (stmt); 3422 gsi_remove (gsi, true); 3423 release_defs (stmt); 3424 sra_stats.deleted++; 3425 return SRA_AM_REMOVED; 3426 } 3427 /* Restore the aggregate RHS from its components so the 3428 prevailing aggregate copy does the right thing. */ 3429 if (access_has_children_p (racc)) 3430 generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0, 3431 gsi, false, false, loc); 3432 /* Re-load the components of the aggregate copy destination. 3433 But use the RHS aggregate to load from to expose more 3434 optimization opportunities. */ 3435 if (access_has_children_p (lacc)) 3436 generate_subtree_copies (lacc->first_child, rhs, lacc->offset, 3437 0, 0, gsi, true, true, loc); 3438 } 3439 3440 return SRA_AM_NONE; 3441 } 3442 } 3443 3444 /* Traverse the function body and all modifications as decided in 3445 analyze_all_variable_accesses. Return true iff the CFG has been 3446 changed. */ 3447 3448 static bool 3449 sra_modify_function_body (void) 3450 { 3451 bool cfg_changed = false; 3452 basic_block bb; 3453 3454 FOR_EACH_BB_FN (bb, cfun) 3455 { 3456 gimple_stmt_iterator gsi = gsi_start_bb (bb); 3457 while (!gsi_end_p (gsi)) 3458 { 3459 gimple stmt = gsi_stmt (gsi); 3460 enum assignment_mod_result assign_result; 3461 bool modified = false, deleted = false; 3462 tree *t; 3463 unsigned i; 3464 3465 switch (gimple_code (stmt)) 3466 { 3467 case GIMPLE_RETURN: 3468 t = gimple_return_retval_ptr (as_a <greturn *> (stmt)); 3469 if (*t != NULL_TREE) 3470 modified |= sra_modify_expr (t, &gsi, false); 3471 break; 3472 3473 case GIMPLE_ASSIGN: 3474 assign_result = sra_modify_assign (stmt, &gsi); 3475 modified |= assign_result == SRA_AM_MODIFIED; 3476 deleted = assign_result == SRA_AM_REMOVED; 3477 break; 3478 3479 case GIMPLE_CALL: 3480 /* Operands must be processed before the lhs. */ 3481 for (i = 0; i < gimple_call_num_args (stmt); i++) 3482 { 3483 t = gimple_call_arg_ptr (stmt, i); 3484 modified |= sra_modify_expr (t, &gsi, false); 3485 } 3486 3487 if (gimple_call_lhs (stmt)) 3488 { 3489 t = gimple_call_lhs_ptr (stmt); 3490 modified |= sra_modify_expr (t, &gsi, true); 3491 } 3492 break; 3493 3494 case GIMPLE_ASM: 3495 { 3496 gasm *asm_stmt = as_a <gasm *> (stmt); 3497 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++) 3498 { 3499 t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i)); 3500 modified |= sra_modify_expr (t, &gsi, false); 3501 } 3502 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++) 3503 { 3504 t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i)); 3505 modified |= sra_modify_expr (t, &gsi, true); 3506 } 3507 } 3508 break; 3509 3510 default: 3511 break; 3512 } 3513 3514 if (modified) 3515 { 3516 update_stmt (stmt); 3517 if (maybe_clean_eh_stmt (stmt) 3518 && gimple_purge_dead_eh_edges (gimple_bb (stmt))) 3519 cfg_changed = true; 3520 } 3521 if (!deleted) 3522 gsi_next (&gsi); 3523 } 3524 } 3525 3526 gsi_commit_edge_inserts (); 3527 return cfg_changed; 3528 } 3529 3530 /* Generate statements initializing scalar replacements of parts of function 3531 parameters. */ 3532 3533 static void 3534 initialize_parameter_reductions (void) 3535 { 3536 gimple_stmt_iterator gsi; 3537 gimple_seq seq = NULL; 3538 tree parm; 3539 3540 gsi = gsi_start (seq); 3541 for (parm = DECL_ARGUMENTS (current_function_decl); 3542 parm; 3543 parm = DECL_CHAIN (parm)) 3544 { 3545 vec<access_p> *access_vec; 3546 struct access *access; 3547 3548 if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm))) 3549 continue; 3550 access_vec = get_base_access_vector (parm); 3551 if (!access_vec) 3552 continue; 3553 3554 for (access = (*access_vec)[0]; 3555 access; 3556 access = access->next_grp) 3557 generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true, 3558 EXPR_LOCATION (parm)); 3559 } 3560 3561 seq = gsi_seq (gsi); 3562 if (seq) 3563 gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq); 3564 } 3565 3566 /* The "main" function of intraprocedural SRA passes. Runs the analysis and if 3567 it reveals there are components of some aggregates to be scalarized, it runs 3568 the required transformations. */ 3569 static unsigned int 3570 perform_intra_sra (void) 3571 { 3572 int ret = 0; 3573 sra_initialize (); 3574 3575 if (!find_var_candidates ()) 3576 goto out; 3577 3578 if (!scan_function ()) 3579 goto out; 3580 3581 if (!analyze_all_variable_accesses ()) 3582 goto out; 3583 3584 if (sra_modify_function_body ()) 3585 ret = TODO_update_ssa | TODO_cleanup_cfg; 3586 else 3587 ret = TODO_update_ssa; 3588 initialize_parameter_reductions (); 3589 3590 statistics_counter_event (cfun, "Scalar replacements created", 3591 sra_stats.replacements); 3592 statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs); 3593 statistics_counter_event (cfun, "Subtree copy stmts", 3594 sra_stats.subtree_copies); 3595 statistics_counter_event (cfun, "Subreplacement stmts", 3596 sra_stats.subreplacements); 3597 statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted); 3598 statistics_counter_event (cfun, "Separate LHS and RHS handling", 3599 sra_stats.separate_lhs_rhs_handling); 3600 3601 out: 3602 sra_deinitialize (); 3603 return ret; 3604 } 3605 3606 /* Perform early intraprocedural SRA. */ 3607 static unsigned int 3608 early_intra_sra (void) 3609 { 3610 sra_mode = SRA_MODE_EARLY_INTRA; 3611 return perform_intra_sra (); 3612 } 3613 3614 /* Perform "late" intraprocedural SRA. */ 3615 static unsigned int 3616 late_intra_sra (void) 3617 { 3618 sra_mode = SRA_MODE_INTRA; 3619 return perform_intra_sra (); 3620 } 3621 3622 3623 static bool 3624 gate_intra_sra (void) 3625 { 3626 return flag_tree_sra != 0 && dbg_cnt (tree_sra); 3627 } 3628 3629 3630 namespace { 3631 3632 const pass_data pass_data_sra_early = 3633 { 3634 GIMPLE_PASS, /* type */ 3635 "esra", /* name */ 3636 OPTGROUP_NONE, /* optinfo_flags */ 3637 TV_TREE_SRA, /* tv_id */ 3638 ( PROP_cfg | PROP_ssa ), /* properties_required */ 3639 0, /* properties_provided */ 3640 0, /* properties_destroyed */ 3641 0, /* todo_flags_start */ 3642 TODO_update_ssa, /* todo_flags_finish */ 3643 }; 3644 3645 class pass_sra_early : public gimple_opt_pass 3646 { 3647 public: 3648 pass_sra_early (gcc::context *ctxt) 3649 : gimple_opt_pass (pass_data_sra_early, ctxt) 3650 {} 3651 3652 /* opt_pass methods: */ 3653 virtual bool gate (function *) { return gate_intra_sra (); } 3654 virtual unsigned int execute (function *) { return early_intra_sra (); } 3655 3656 }; // class pass_sra_early 3657 3658 } // anon namespace 3659 3660 gimple_opt_pass * 3661 make_pass_sra_early (gcc::context *ctxt) 3662 { 3663 return new pass_sra_early (ctxt); 3664 } 3665 3666 namespace { 3667 3668 const pass_data pass_data_sra = 3669 { 3670 GIMPLE_PASS, /* type */ 3671 "sra", /* name */ 3672 OPTGROUP_NONE, /* optinfo_flags */ 3673 TV_TREE_SRA, /* tv_id */ 3674 ( PROP_cfg | PROP_ssa ), /* properties_required */ 3675 0, /* properties_provided */ 3676 0, /* properties_destroyed */ 3677 TODO_update_address_taken, /* todo_flags_start */ 3678 TODO_update_ssa, /* todo_flags_finish */ 3679 }; 3680 3681 class pass_sra : public gimple_opt_pass 3682 { 3683 public: 3684 pass_sra (gcc::context *ctxt) 3685 : gimple_opt_pass (pass_data_sra, ctxt) 3686 {} 3687 3688 /* opt_pass methods: */ 3689 virtual bool gate (function *) { return gate_intra_sra (); } 3690 virtual unsigned int execute (function *) { return late_intra_sra (); } 3691 3692 }; // class pass_sra 3693 3694 } // anon namespace 3695 3696 gimple_opt_pass * 3697 make_pass_sra (gcc::context *ctxt) 3698 { 3699 return new pass_sra (ctxt); 3700 } 3701 3702 3703 /* Return true iff PARM (which must be a parm_decl) is an unused scalar 3704 parameter. */ 3705 3706 static bool 3707 is_unused_scalar_param (tree parm) 3708 { 3709 tree name; 3710 return (is_gimple_reg (parm) 3711 && (!(name = ssa_default_def (cfun, parm)) 3712 || has_zero_uses (name))); 3713 } 3714 3715 /* Scan immediate uses of a default definition SSA name of a parameter PARM and 3716 examine whether there are any direct or otherwise infeasible ones. If so, 3717 return true, otherwise return false. PARM must be a gimple register with a 3718 non-NULL default definition. */ 3719 3720 static bool 3721 ptr_parm_has_direct_uses (tree parm) 3722 { 3723 imm_use_iterator ui; 3724 gimple stmt; 3725 tree name = ssa_default_def (cfun, parm); 3726 bool ret = false; 3727 3728 FOR_EACH_IMM_USE_STMT (stmt, ui, name) 3729 { 3730 int uses_ok = 0; 3731 use_operand_p use_p; 3732 3733 if (is_gimple_debug (stmt)) 3734 continue; 3735 3736 /* Valid uses include dereferences on the lhs and the rhs. */ 3737 if (gimple_has_lhs (stmt)) 3738 { 3739 tree lhs = gimple_get_lhs (stmt); 3740 while (handled_component_p (lhs)) 3741 lhs = TREE_OPERAND (lhs, 0); 3742 if (TREE_CODE (lhs) == MEM_REF 3743 && TREE_OPERAND (lhs, 0) == name 3744 && integer_zerop (TREE_OPERAND (lhs, 1)) 3745 && types_compatible_p (TREE_TYPE (lhs), 3746 TREE_TYPE (TREE_TYPE (name))) 3747 && !TREE_THIS_VOLATILE (lhs)) 3748 uses_ok++; 3749 } 3750 if (gimple_assign_single_p (stmt)) 3751 { 3752 tree rhs = gimple_assign_rhs1 (stmt); 3753 while (handled_component_p (rhs)) 3754 rhs = TREE_OPERAND (rhs, 0); 3755 if (TREE_CODE (rhs) == MEM_REF 3756 && TREE_OPERAND (rhs, 0) == name 3757 && integer_zerop (TREE_OPERAND (rhs, 1)) 3758 && types_compatible_p (TREE_TYPE (rhs), 3759 TREE_TYPE (TREE_TYPE (name))) 3760 && !TREE_THIS_VOLATILE (rhs)) 3761 uses_ok++; 3762 } 3763 else if (is_gimple_call (stmt)) 3764 { 3765 unsigned i; 3766 for (i = 0; i < gimple_call_num_args (stmt); ++i) 3767 { 3768 tree arg = gimple_call_arg (stmt, i); 3769 while (handled_component_p (arg)) 3770 arg = TREE_OPERAND (arg, 0); 3771 if (TREE_CODE (arg) == MEM_REF 3772 && TREE_OPERAND (arg, 0) == name 3773 && integer_zerop (TREE_OPERAND (arg, 1)) 3774 && types_compatible_p (TREE_TYPE (arg), 3775 TREE_TYPE (TREE_TYPE (name))) 3776 && !TREE_THIS_VOLATILE (arg)) 3777 uses_ok++; 3778 } 3779 } 3780 3781 /* If the number of valid uses does not match the number of 3782 uses in this stmt there is an unhandled use. */ 3783 FOR_EACH_IMM_USE_ON_STMT (use_p, ui) 3784 --uses_ok; 3785 3786 if (uses_ok != 0) 3787 ret = true; 3788 3789 if (ret) 3790 BREAK_FROM_IMM_USE_STMT (ui); 3791 } 3792 3793 return ret; 3794 } 3795 3796 /* Identify candidates for reduction for IPA-SRA based on their type and mark 3797 them in candidate_bitmap. Note that these do not necessarily include 3798 parameter which are unused and thus can be removed. Return true iff any 3799 such candidate has been found. */ 3800 3801 static bool 3802 find_param_candidates (void) 3803 { 3804 tree parm; 3805 int count = 0; 3806 bool ret = false; 3807 const char *msg; 3808 3809 for (parm = DECL_ARGUMENTS (current_function_decl); 3810 parm; 3811 parm = DECL_CHAIN (parm)) 3812 { 3813 tree type = TREE_TYPE (parm); 3814 tree_node **slot; 3815 3816 count++; 3817 3818 if (TREE_THIS_VOLATILE (parm) 3819 || TREE_ADDRESSABLE (parm) 3820 || (!is_gimple_reg_type (type) && is_va_list_type (type))) 3821 continue; 3822 3823 if (is_unused_scalar_param (parm)) 3824 { 3825 ret = true; 3826 continue; 3827 } 3828 3829 if (POINTER_TYPE_P (type)) 3830 { 3831 type = TREE_TYPE (type); 3832 3833 if (TREE_CODE (type) == FUNCTION_TYPE 3834 || TYPE_VOLATILE (type) 3835 || (TREE_CODE (type) == ARRAY_TYPE 3836 && TYPE_NONALIASED_COMPONENT (type)) 3837 || !is_gimple_reg (parm) 3838 || is_va_list_type (type) 3839 || ptr_parm_has_direct_uses (parm)) 3840 continue; 3841 } 3842 else if (!AGGREGATE_TYPE_P (type)) 3843 continue; 3844 3845 if (!COMPLETE_TYPE_P (type) 3846 || !tree_fits_uhwi_p (TYPE_SIZE (type)) 3847 || tree_to_uhwi (TYPE_SIZE (type)) == 0 3848 || (AGGREGATE_TYPE_P (type) 3849 && type_internals_preclude_sra_p (type, &msg))) 3850 continue; 3851 3852 bitmap_set_bit (candidate_bitmap, DECL_UID (parm)); 3853 slot = candidates->find_slot_with_hash (parm, DECL_UID (parm), INSERT); 3854 *slot = parm; 3855 3856 ret = true; 3857 if (dump_file && (dump_flags & TDF_DETAILS)) 3858 { 3859 fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm)); 3860 print_generic_expr (dump_file, parm, 0); 3861 fprintf (dump_file, "\n"); 3862 } 3863 } 3864 3865 func_param_count = count; 3866 return ret; 3867 } 3868 3869 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as 3870 maybe_modified. */ 3871 3872 static bool 3873 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED, 3874 void *data) 3875 { 3876 struct access *repr = (struct access *) data; 3877 3878 repr->grp_maybe_modified = 1; 3879 return true; 3880 } 3881 3882 /* Analyze what representatives (in linked lists accessible from 3883 REPRESENTATIVES) can be modified by side effects of statements in the 3884 current function. */ 3885 3886 static void 3887 analyze_modified_params (vec<access_p> representatives) 3888 { 3889 int i; 3890 3891 for (i = 0; i < func_param_count; i++) 3892 { 3893 struct access *repr; 3894 3895 for (repr = representatives[i]; 3896 repr; 3897 repr = repr->next_grp) 3898 { 3899 struct access *access; 3900 bitmap visited; 3901 ao_ref ar; 3902 3903 if (no_accesses_p (repr)) 3904 continue; 3905 if (!POINTER_TYPE_P (TREE_TYPE (repr->base)) 3906 || repr->grp_maybe_modified) 3907 continue; 3908 3909 ao_ref_init (&ar, repr->expr); 3910 visited = BITMAP_ALLOC (NULL); 3911 for (access = repr; access; access = access->next_sibling) 3912 { 3913 /* All accesses are read ones, otherwise grp_maybe_modified would 3914 be trivially set. */ 3915 walk_aliased_vdefs (&ar, gimple_vuse (access->stmt), 3916 mark_maybe_modified, repr, &visited); 3917 if (repr->grp_maybe_modified) 3918 break; 3919 } 3920 BITMAP_FREE (visited); 3921 } 3922 } 3923 } 3924 3925 /* Propagate distances in bb_dereferences in the opposite direction than the 3926 control flow edges, in each step storing the maximum of the current value 3927 and the minimum of all successors. These steps are repeated until the table 3928 stabilizes. Note that BBs which might terminate the functions (according to 3929 final_bbs bitmap) never updated in this way. */ 3930 3931 static void 3932 propagate_dereference_distances (void) 3933 { 3934 basic_block bb; 3935 3936 auto_vec<basic_block> queue (last_basic_block_for_fn (cfun)); 3937 queue.quick_push (ENTRY_BLOCK_PTR_FOR_FN (cfun)); 3938 FOR_EACH_BB_FN (bb, cfun) 3939 { 3940 queue.quick_push (bb); 3941 bb->aux = bb; 3942 } 3943 3944 while (!queue.is_empty ()) 3945 { 3946 edge_iterator ei; 3947 edge e; 3948 bool change = false; 3949 int i; 3950 3951 bb = queue.pop (); 3952 bb->aux = NULL; 3953 3954 if (bitmap_bit_p (final_bbs, bb->index)) 3955 continue; 3956 3957 for (i = 0; i < func_param_count; i++) 3958 { 3959 int idx = bb->index * func_param_count + i; 3960 bool first = true; 3961 HOST_WIDE_INT inh = 0; 3962 3963 FOR_EACH_EDGE (e, ei, bb->succs) 3964 { 3965 int succ_idx = e->dest->index * func_param_count + i; 3966 3967 if (e->src == EXIT_BLOCK_PTR_FOR_FN (cfun)) 3968 continue; 3969 3970 if (first) 3971 { 3972 first = false; 3973 inh = bb_dereferences [succ_idx]; 3974 } 3975 else if (bb_dereferences [succ_idx] < inh) 3976 inh = bb_dereferences [succ_idx]; 3977 } 3978 3979 if (!first && bb_dereferences[idx] < inh) 3980 { 3981 bb_dereferences[idx] = inh; 3982 change = true; 3983 } 3984 } 3985 3986 if (change && !bitmap_bit_p (final_bbs, bb->index)) 3987 FOR_EACH_EDGE (e, ei, bb->preds) 3988 { 3989 if (e->src->aux) 3990 continue; 3991 3992 e->src->aux = e->src; 3993 queue.quick_push (e->src); 3994 } 3995 } 3996 } 3997 3998 /* Dump a dereferences TABLE with heading STR to file F. */ 3999 4000 static void 4001 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table) 4002 { 4003 basic_block bb; 4004 4005 fprintf (dump_file, "%s", str); 4006 FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun), 4007 EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb) 4008 { 4009 fprintf (f, "%4i %i ", bb->index, bitmap_bit_p (final_bbs, bb->index)); 4010 if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun)) 4011 { 4012 int i; 4013 for (i = 0; i < func_param_count; i++) 4014 { 4015 int idx = bb->index * func_param_count + i; 4016 fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]); 4017 } 4018 } 4019 fprintf (f, "\n"); 4020 } 4021 fprintf (dump_file, "\n"); 4022 } 4023 4024 /* Determine what (parts of) parameters passed by reference that are not 4025 assigned to are not certainly dereferenced in this function and thus the 4026 dereferencing cannot be safely moved to the caller without potentially 4027 introducing a segfault. Mark such REPRESENTATIVES as 4028 grp_not_necessarilly_dereferenced. 4029 4030 The dereferenced maximum "distance," i.e. the offset + size of the accessed 4031 part is calculated rather than simple booleans are calculated for each 4032 pointer parameter to handle cases when only a fraction of the whole 4033 aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for 4034 an example). 4035 4036 The maximum dereference distances for each pointer parameter and BB are 4037 already stored in bb_dereference. This routine simply propagates these 4038 values upwards by propagate_dereference_distances and then compares the 4039 distances of individual parameters in the ENTRY BB to the equivalent 4040 distances of each representative of a (fraction of a) parameter. */ 4041 4042 static void 4043 analyze_caller_dereference_legality (vec<access_p> representatives) 4044 { 4045 int i; 4046 4047 if (dump_file && (dump_flags & TDF_DETAILS)) 4048 dump_dereferences_table (dump_file, 4049 "Dereference table before propagation:\n", 4050 bb_dereferences); 4051 4052 propagate_dereference_distances (); 4053 4054 if (dump_file && (dump_flags & TDF_DETAILS)) 4055 dump_dereferences_table (dump_file, 4056 "Dereference table after propagation:\n", 4057 bb_dereferences); 4058 4059 for (i = 0; i < func_param_count; i++) 4060 { 4061 struct access *repr = representatives[i]; 4062 int idx = ENTRY_BLOCK_PTR_FOR_FN (cfun)->index * func_param_count + i; 4063 4064 if (!repr || no_accesses_p (repr)) 4065 continue; 4066 4067 do 4068 { 4069 if ((repr->offset + repr->size) > bb_dereferences[idx]) 4070 repr->grp_not_necessarilly_dereferenced = 1; 4071 repr = repr->next_grp; 4072 } 4073 while (repr); 4074 } 4075 } 4076 4077 /* Return the representative access for the parameter declaration PARM if it is 4078 a scalar passed by reference which is not written to and the pointer value 4079 is not used directly. Thus, if it is legal to dereference it in the caller 4080 and we can rule out modifications through aliases, such parameter should be 4081 turned into one passed by value. Return NULL otherwise. */ 4082 4083 static struct access * 4084 unmodified_by_ref_scalar_representative (tree parm) 4085 { 4086 int i, access_count; 4087 struct access *repr; 4088 vec<access_p> *access_vec; 4089 4090 access_vec = get_base_access_vector (parm); 4091 gcc_assert (access_vec); 4092 repr = (*access_vec)[0]; 4093 if (repr->write) 4094 return NULL; 4095 repr->group_representative = repr; 4096 4097 access_count = access_vec->length (); 4098 for (i = 1; i < access_count; i++) 4099 { 4100 struct access *access = (*access_vec)[i]; 4101 if (access->write) 4102 return NULL; 4103 access->group_representative = repr; 4104 access->next_sibling = repr->next_sibling; 4105 repr->next_sibling = access; 4106 } 4107 4108 repr->grp_read = 1; 4109 repr->grp_scalar_ptr = 1; 4110 return repr; 4111 } 4112 4113 /* Return true iff this ACCESS precludes IPA-SRA of the parameter it is 4114 associated with. REQ_ALIGN is the minimum required alignment. */ 4115 4116 static bool 4117 access_precludes_ipa_sra_p (struct access *access, unsigned int req_align) 4118 { 4119 unsigned int exp_align; 4120 /* Avoid issues such as the second simple testcase in PR 42025. The problem 4121 is incompatible assign in a call statement (and possibly even in asm 4122 statements). This can be relaxed by using a new temporary but only for 4123 non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In 4124 intraprocedural SRA we deal with this by keeping the old aggregate around, 4125 something we cannot do in IPA-SRA.) */ 4126 if (access->write 4127 && (is_gimple_call (access->stmt) 4128 || gimple_code (access->stmt) == GIMPLE_ASM)) 4129 return true; 4130 4131 exp_align = get_object_alignment (access->expr); 4132 if (exp_align < req_align) 4133 return true; 4134 4135 return false; 4136 } 4137 4138 4139 /* Sort collected accesses for parameter PARM, identify representatives for 4140 each accessed region and link them together. Return NULL if there are 4141 different but overlapping accesses, return the special ptr value meaning 4142 there are no accesses for this parameter if that is the case and return the 4143 first representative otherwise. Set *RO_GRP if there is a group of accesses 4144 with only read (i.e. no write) accesses. */ 4145 4146 static struct access * 4147 splice_param_accesses (tree parm, bool *ro_grp) 4148 { 4149 int i, j, access_count, group_count; 4150 int agg_size, total_size = 0; 4151 struct access *access, *res, **prev_acc_ptr = &res; 4152 vec<access_p> *access_vec; 4153 4154 access_vec = get_base_access_vector (parm); 4155 if (!access_vec) 4156 return &no_accesses_representant; 4157 access_count = access_vec->length (); 4158 4159 access_vec->qsort (compare_access_positions); 4160 4161 i = 0; 4162 total_size = 0; 4163 group_count = 0; 4164 while (i < access_count) 4165 { 4166 bool modification; 4167 tree a1_alias_type; 4168 access = (*access_vec)[i]; 4169 modification = access->write; 4170 if (access_precludes_ipa_sra_p (access, TYPE_ALIGN (access->type))) 4171 return NULL; 4172 a1_alias_type = reference_alias_ptr_type (access->expr); 4173 4174 /* Access is about to become group representative unless we find some 4175 nasty overlap which would preclude us from breaking this parameter 4176 apart. */ 4177 4178 j = i + 1; 4179 while (j < access_count) 4180 { 4181 struct access *ac2 = (*access_vec)[j]; 4182 if (ac2->offset != access->offset) 4183 { 4184 /* All or nothing law for parameters. */ 4185 if (access->offset + access->size > ac2->offset) 4186 return NULL; 4187 else 4188 break; 4189 } 4190 else if (ac2->size != access->size) 4191 return NULL; 4192 4193 if (access_precludes_ipa_sra_p (ac2, TYPE_ALIGN (access->type)) 4194 || (ac2->type != access->type 4195 && (TREE_ADDRESSABLE (ac2->type) 4196 || TREE_ADDRESSABLE (access->type))) 4197 || (reference_alias_ptr_type (ac2->expr) != a1_alias_type)) 4198 return NULL; 4199 4200 modification |= ac2->write; 4201 ac2->group_representative = access; 4202 ac2->next_sibling = access->next_sibling; 4203 access->next_sibling = ac2; 4204 j++; 4205 } 4206 4207 group_count++; 4208 access->grp_maybe_modified = modification; 4209 if (!modification) 4210 *ro_grp = true; 4211 *prev_acc_ptr = access; 4212 prev_acc_ptr = &access->next_grp; 4213 total_size += access->size; 4214 i = j; 4215 } 4216 4217 if (POINTER_TYPE_P (TREE_TYPE (parm))) 4218 agg_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm)))); 4219 else 4220 agg_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm))); 4221 if (total_size >= agg_size) 4222 return NULL; 4223 4224 gcc_assert (group_count > 0); 4225 return res; 4226 } 4227 4228 /* Decide whether parameters with representative accesses given by REPR should 4229 be reduced into components. */ 4230 4231 static int 4232 decide_one_param_reduction (struct access *repr) 4233 { 4234 int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit; 4235 bool by_ref; 4236 tree parm; 4237 4238 parm = repr->base; 4239 cur_parm_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm))); 4240 gcc_assert (cur_parm_size > 0); 4241 4242 if (POINTER_TYPE_P (TREE_TYPE (parm))) 4243 { 4244 by_ref = true; 4245 agg_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm)))); 4246 } 4247 else 4248 { 4249 by_ref = false; 4250 agg_size = cur_parm_size; 4251 } 4252 4253 if (dump_file) 4254 { 4255 struct access *acc; 4256 fprintf (dump_file, "Evaluating PARAM group sizes for "); 4257 print_generic_expr (dump_file, parm, 0); 4258 fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm)); 4259 for (acc = repr; acc; acc = acc->next_grp) 4260 dump_access (dump_file, acc, true); 4261 } 4262 4263 total_size = 0; 4264 new_param_count = 0; 4265 4266 for (; repr; repr = repr->next_grp) 4267 { 4268 gcc_assert (parm == repr->base); 4269 4270 /* Taking the address of a non-addressable field is verboten. */ 4271 if (by_ref && repr->non_addressable) 4272 return 0; 4273 4274 /* Do not decompose a non-BLKmode param in a way that would 4275 create BLKmode params. Especially for by-reference passing 4276 (thus, pointer-type param) this is hardly worthwhile. */ 4277 if (DECL_MODE (parm) != BLKmode 4278 && TYPE_MODE (repr->type) == BLKmode) 4279 return 0; 4280 4281 if (!by_ref || (!repr->grp_maybe_modified 4282 && !repr->grp_not_necessarilly_dereferenced)) 4283 total_size += repr->size; 4284 else 4285 total_size += cur_parm_size; 4286 4287 new_param_count++; 4288 } 4289 4290 gcc_assert (new_param_count > 0); 4291 4292 if (optimize_function_for_size_p (cfun)) 4293 parm_size_limit = cur_parm_size; 4294 else 4295 parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR) 4296 * cur_parm_size); 4297 4298 if (total_size < agg_size 4299 && total_size <= parm_size_limit) 4300 { 4301 if (dump_file) 4302 fprintf (dump_file, " ....will be split into %i components\n", 4303 new_param_count); 4304 return new_param_count; 4305 } 4306 else 4307 return 0; 4308 } 4309 4310 /* The order of the following enums is important, we need to do extra work for 4311 UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES. */ 4312 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES, 4313 MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES }; 4314 4315 /* Identify representatives of all accesses to all candidate parameters for 4316 IPA-SRA. Return result based on what representatives have been found. */ 4317 4318 static enum ipa_splicing_result 4319 splice_all_param_accesses (vec<access_p> &representatives) 4320 { 4321 enum ipa_splicing_result result = NO_GOOD_ACCESS; 4322 tree parm; 4323 struct access *repr; 4324 4325 representatives.create (func_param_count); 4326 4327 for (parm = DECL_ARGUMENTS (current_function_decl); 4328 parm; 4329 parm = DECL_CHAIN (parm)) 4330 { 4331 if (is_unused_scalar_param (parm)) 4332 { 4333 representatives.quick_push (&no_accesses_representant); 4334 if (result == NO_GOOD_ACCESS) 4335 result = UNUSED_PARAMS; 4336 } 4337 else if (POINTER_TYPE_P (TREE_TYPE (parm)) 4338 && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm))) 4339 && bitmap_bit_p (candidate_bitmap, DECL_UID (parm))) 4340 { 4341 repr = unmodified_by_ref_scalar_representative (parm); 4342 representatives.quick_push (repr); 4343 if (repr) 4344 result = UNMODIF_BY_REF_ACCESSES; 4345 } 4346 else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm))) 4347 { 4348 bool ro_grp = false; 4349 repr = splice_param_accesses (parm, &ro_grp); 4350 representatives.quick_push (repr); 4351 4352 if (repr && !no_accesses_p (repr)) 4353 { 4354 if (POINTER_TYPE_P (TREE_TYPE (parm))) 4355 { 4356 if (ro_grp) 4357 result = UNMODIF_BY_REF_ACCESSES; 4358 else if (result < MODIF_BY_REF_ACCESSES) 4359 result = MODIF_BY_REF_ACCESSES; 4360 } 4361 else if (result < BY_VAL_ACCESSES) 4362 result = BY_VAL_ACCESSES; 4363 } 4364 else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS)) 4365 result = UNUSED_PARAMS; 4366 } 4367 else 4368 representatives.quick_push (NULL); 4369 } 4370 4371 if (result == NO_GOOD_ACCESS) 4372 { 4373 representatives.release (); 4374 return NO_GOOD_ACCESS; 4375 } 4376 4377 return result; 4378 } 4379 4380 /* Return the index of BASE in PARMS. Abort if it is not found. */ 4381 4382 static inline int 4383 get_param_index (tree base, vec<tree> parms) 4384 { 4385 int i, len; 4386 4387 len = parms.length (); 4388 for (i = 0; i < len; i++) 4389 if (parms[i] == base) 4390 return i; 4391 gcc_unreachable (); 4392 } 4393 4394 /* Convert the decisions made at the representative level into compact 4395 parameter adjustments. REPRESENTATIVES are pointers to first 4396 representatives of each param accesses, ADJUSTMENTS_COUNT is the expected 4397 final number of adjustments. */ 4398 4399 static ipa_parm_adjustment_vec 4400 turn_representatives_into_adjustments (vec<access_p> representatives, 4401 int adjustments_count) 4402 { 4403 vec<tree> parms; 4404 ipa_parm_adjustment_vec adjustments; 4405 tree parm; 4406 int i; 4407 4408 gcc_assert (adjustments_count > 0); 4409 parms = ipa_get_vector_of_formal_parms (current_function_decl); 4410 adjustments.create (adjustments_count); 4411 parm = DECL_ARGUMENTS (current_function_decl); 4412 for (i = 0; i < func_param_count; i++, parm = DECL_CHAIN (parm)) 4413 { 4414 struct access *repr = representatives[i]; 4415 4416 if (!repr || no_accesses_p (repr)) 4417 { 4418 struct ipa_parm_adjustment adj; 4419 4420 memset (&adj, 0, sizeof (adj)); 4421 adj.base_index = get_param_index (parm, parms); 4422 adj.base = parm; 4423 if (!repr) 4424 adj.op = IPA_PARM_OP_COPY; 4425 else 4426 adj.op = IPA_PARM_OP_REMOVE; 4427 adj.arg_prefix = "ISRA"; 4428 adjustments.quick_push (adj); 4429 } 4430 else 4431 { 4432 struct ipa_parm_adjustment adj; 4433 int index = get_param_index (parm, parms); 4434 4435 for (; repr; repr = repr->next_grp) 4436 { 4437 memset (&adj, 0, sizeof (adj)); 4438 gcc_assert (repr->base == parm); 4439 adj.base_index = index; 4440 adj.base = repr->base; 4441 adj.type = repr->type; 4442 adj.alias_ptr_type = reference_alias_ptr_type (repr->expr); 4443 adj.offset = repr->offset; 4444 adj.by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base)) 4445 && (repr->grp_maybe_modified 4446 || repr->grp_not_necessarilly_dereferenced)); 4447 adj.arg_prefix = "ISRA"; 4448 adjustments.quick_push (adj); 4449 } 4450 } 4451 } 4452 parms.release (); 4453 return adjustments; 4454 } 4455 4456 /* Analyze the collected accesses and produce a plan what to do with the 4457 parameters in the form of adjustments, NULL meaning nothing. */ 4458 4459 static ipa_parm_adjustment_vec 4460 analyze_all_param_acesses (void) 4461 { 4462 enum ipa_splicing_result repr_state; 4463 bool proceed = false; 4464 int i, adjustments_count = 0; 4465 vec<access_p> representatives; 4466 ipa_parm_adjustment_vec adjustments; 4467 4468 repr_state = splice_all_param_accesses (representatives); 4469 if (repr_state == NO_GOOD_ACCESS) 4470 return ipa_parm_adjustment_vec (); 4471 4472 /* If there are any parameters passed by reference which are not modified 4473 directly, we need to check whether they can be modified indirectly. */ 4474 if (repr_state == UNMODIF_BY_REF_ACCESSES) 4475 { 4476 analyze_caller_dereference_legality (representatives); 4477 analyze_modified_params (representatives); 4478 } 4479 4480 for (i = 0; i < func_param_count; i++) 4481 { 4482 struct access *repr = representatives[i]; 4483 4484 if (repr && !no_accesses_p (repr)) 4485 { 4486 if (repr->grp_scalar_ptr) 4487 { 4488 adjustments_count++; 4489 if (repr->grp_not_necessarilly_dereferenced 4490 || repr->grp_maybe_modified) 4491 representatives[i] = NULL; 4492 else 4493 { 4494 proceed = true; 4495 sra_stats.scalar_by_ref_to_by_val++; 4496 } 4497 } 4498 else 4499 { 4500 int new_components = decide_one_param_reduction (repr); 4501 4502 if (new_components == 0) 4503 { 4504 representatives[i] = NULL; 4505 adjustments_count++; 4506 } 4507 else 4508 { 4509 adjustments_count += new_components; 4510 sra_stats.aggregate_params_reduced++; 4511 sra_stats.param_reductions_created += new_components; 4512 proceed = true; 4513 } 4514 } 4515 } 4516 else 4517 { 4518 if (no_accesses_p (repr)) 4519 { 4520 proceed = true; 4521 sra_stats.deleted_unused_parameters++; 4522 } 4523 adjustments_count++; 4524 } 4525 } 4526 4527 if (!proceed && dump_file) 4528 fprintf (dump_file, "NOT proceeding to change params.\n"); 4529 4530 if (proceed) 4531 adjustments = turn_representatives_into_adjustments (representatives, 4532 adjustments_count); 4533 else 4534 adjustments = ipa_parm_adjustment_vec (); 4535 4536 representatives.release (); 4537 return adjustments; 4538 } 4539 4540 /* If a parameter replacement identified by ADJ does not yet exist in the form 4541 of declaration, create it and record it, otherwise return the previously 4542 created one. */ 4543 4544 static tree 4545 get_replaced_param_substitute (struct ipa_parm_adjustment *adj) 4546 { 4547 tree repl; 4548 if (!adj->new_ssa_base) 4549 { 4550 char *pretty_name = make_fancy_name (adj->base); 4551 4552 repl = create_tmp_reg (TREE_TYPE (adj->base), "ISR"); 4553 DECL_NAME (repl) = get_identifier (pretty_name); 4554 obstack_free (&name_obstack, pretty_name); 4555 4556 adj->new_ssa_base = repl; 4557 } 4558 else 4559 repl = adj->new_ssa_base; 4560 return repl; 4561 } 4562 4563 /* Find the first adjustment for a particular parameter BASE in a vector of 4564 ADJUSTMENTS which is not a copy_param. Return NULL if there is no such 4565 adjustment. */ 4566 4567 static struct ipa_parm_adjustment * 4568 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base) 4569 { 4570 int i, len; 4571 4572 len = adjustments.length (); 4573 for (i = 0; i < len; i++) 4574 { 4575 struct ipa_parm_adjustment *adj; 4576 4577 adj = &adjustments[i]; 4578 if (adj->op != IPA_PARM_OP_COPY && adj->base == base) 4579 return adj; 4580 } 4581 4582 return NULL; 4583 } 4584 4585 /* If OLD_NAME, which is being defined by statement STMT, is an SSA_NAME of a 4586 parameter which is to be removed because its value is not used, create a new 4587 SSA_NAME relating to a replacement VAR_DECL, replace all uses of the 4588 original with it and return it. If there is no need to re-map, return NULL. 4589 ADJUSTMENTS is a pointer to a vector of IPA-SRA adjustments. */ 4590 4591 static tree 4592 replace_removed_params_ssa_names (tree old_name, gimple stmt, 4593 ipa_parm_adjustment_vec adjustments) 4594 { 4595 struct ipa_parm_adjustment *adj; 4596 tree decl, repl, new_name; 4597 4598 if (TREE_CODE (old_name) != SSA_NAME) 4599 return NULL; 4600 4601 decl = SSA_NAME_VAR (old_name); 4602 if (decl == NULL_TREE 4603 || TREE_CODE (decl) != PARM_DECL) 4604 return NULL; 4605 4606 adj = get_adjustment_for_base (adjustments, decl); 4607 if (!adj) 4608 return NULL; 4609 4610 repl = get_replaced_param_substitute (adj); 4611 new_name = make_ssa_name (repl, stmt); 4612 SSA_NAME_OCCURS_IN_ABNORMAL_PHI (new_name) 4613 = SSA_NAME_OCCURS_IN_ABNORMAL_PHI (old_name); 4614 4615 if (dump_file) 4616 { 4617 fprintf (dump_file, "replacing an SSA name of a removed param "); 4618 print_generic_expr (dump_file, old_name, 0); 4619 fprintf (dump_file, " with "); 4620 print_generic_expr (dump_file, new_name, 0); 4621 fprintf (dump_file, "\n"); 4622 } 4623 4624 replace_uses_by (old_name, new_name); 4625 return new_name; 4626 } 4627 4628 /* If the statement STMT contains any expressions that need to replaced with a 4629 different one as noted by ADJUSTMENTS, do so. Handle any potential type 4630 incompatibilities (GSI is used to accommodate conversion statements and must 4631 point to the statement). Return true iff the statement was modified. */ 4632 4633 static bool 4634 sra_ipa_modify_assign (gimple stmt, gimple_stmt_iterator *gsi, 4635 ipa_parm_adjustment_vec adjustments) 4636 { 4637 tree *lhs_p, *rhs_p; 4638 bool any; 4639 4640 if (!gimple_assign_single_p (stmt)) 4641 return false; 4642 4643 rhs_p = gimple_assign_rhs1_ptr (stmt); 4644 lhs_p = gimple_assign_lhs_ptr (stmt); 4645 4646 any = ipa_modify_expr (rhs_p, false, adjustments); 4647 any |= ipa_modify_expr (lhs_p, false, adjustments); 4648 if (any) 4649 { 4650 tree new_rhs = NULL_TREE; 4651 4652 if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p))) 4653 { 4654 if (TREE_CODE (*rhs_p) == CONSTRUCTOR) 4655 { 4656 /* V_C_Es of constructors can cause trouble (PR 42714). */ 4657 if (is_gimple_reg_type (TREE_TYPE (*lhs_p))) 4658 *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p)); 4659 else 4660 *rhs_p = build_constructor (TREE_TYPE (*lhs_p), 4661 NULL); 4662 } 4663 else 4664 new_rhs = fold_build1_loc (gimple_location (stmt), 4665 VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p), 4666 *rhs_p); 4667 } 4668 else if (REFERENCE_CLASS_P (*rhs_p) 4669 && is_gimple_reg_type (TREE_TYPE (*lhs_p)) 4670 && !is_gimple_reg (*lhs_p)) 4671 /* This can happen when an assignment in between two single field 4672 structures is turned into an assignment in between two pointers to 4673 scalars (PR 42237). */ 4674 new_rhs = *rhs_p; 4675 4676 if (new_rhs) 4677 { 4678 tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE, 4679 true, GSI_SAME_STMT); 4680 4681 gimple_assign_set_rhs_from_tree (gsi, tmp); 4682 } 4683 4684 return true; 4685 } 4686 4687 return false; 4688 } 4689 4690 /* Traverse the function body and all modifications as described in 4691 ADJUSTMENTS. Return true iff the CFG has been changed. */ 4692 4693 bool 4694 ipa_sra_modify_function_body (ipa_parm_adjustment_vec adjustments) 4695 { 4696 bool cfg_changed = false; 4697 basic_block bb; 4698 4699 FOR_EACH_BB_FN (bb, cfun) 4700 { 4701 gimple_stmt_iterator gsi; 4702 4703 for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi)) 4704 { 4705 gphi *phi = as_a <gphi *> (gsi_stmt (gsi)); 4706 tree new_lhs, old_lhs = gimple_phi_result (phi); 4707 new_lhs = replace_removed_params_ssa_names (old_lhs, phi, adjustments); 4708 if (new_lhs) 4709 { 4710 gimple_phi_set_result (phi, new_lhs); 4711 release_ssa_name (old_lhs); 4712 } 4713 } 4714 4715 gsi = gsi_start_bb (bb); 4716 while (!gsi_end_p (gsi)) 4717 { 4718 gimple stmt = gsi_stmt (gsi); 4719 bool modified = false; 4720 tree *t; 4721 unsigned i; 4722 4723 switch (gimple_code (stmt)) 4724 { 4725 case GIMPLE_RETURN: 4726 t = gimple_return_retval_ptr (as_a <greturn *> (stmt)); 4727 if (*t != NULL_TREE) 4728 modified |= ipa_modify_expr (t, true, adjustments); 4729 break; 4730 4731 case GIMPLE_ASSIGN: 4732 modified |= sra_ipa_modify_assign (stmt, &gsi, adjustments); 4733 break; 4734 4735 case GIMPLE_CALL: 4736 /* Operands must be processed before the lhs. */ 4737 for (i = 0; i < gimple_call_num_args (stmt); i++) 4738 { 4739 t = gimple_call_arg_ptr (stmt, i); 4740 modified |= ipa_modify_expr (t, true, adjustments); 4741 } 4742 4743 if (gimple_call_lhs (stmt)) 4744 { 4745 t = gimple_call_lhs_ptr (stmt); 4746 modified |= ipa_modify_expr (t, false, adjustments); 4747 } 4748 break; 4749 4750 case GIMPLE_ASM: 4751 { 4752 gasm *asm_stmt = as_a <gasm *> (stmt); 4753 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++) 4754 { 4755 t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i)); 4756 modified |= ipa_modify_expr (t, true, adjustments); 4757 } 4758 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++) 4759 { 4760 t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i)); 4761 modified |= ipa_modify_expr (t, false, adjustments); 4762 } 4763 } 4764 break; 4765 4766 default: 4767 break; 4768 } 4769 4770 def_operand_p defp; 4771 ssa_op_iter iter; 4772 FOR_EACH_SSA_DEF_OPERAND (defp, stmt, iter, SSA_OP_DEF) 4773 { 4774 tree old_def = DEF_FROM_PTR (defp); 4775 if (tree new_def = replace_removed_params_ssa_names (old_def, stmt, 4776 adjustments)) 4777 { 4778 SET_DEF (defp, new_def); 4779 release_ssa_name (old_def); 4780 modified = true; 4781 } 4782 } 4783 4784 if (modified) 4785 { 4786 update_stmt (stmt); 4787 if (maybe_clean_eh_stmt (stmt) 4788 && gimple_purge_dead_eh_edges (gimple_bb (stmt))) 4789 cfg_changed = true; 4790 } 4791 gsi_next (&gsi); 4792 } 4793 } 4794 4795 return cfg_changed; 4796 } 4797 4798 /* Call gimple_debug_bind_reset_value on all debug statements describing 4799 gimple register parameters that are being removed or replaced. */ 4800 4801 static void 4802 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments) 4803 { 4804 int i, len; 4805 gimple_stmt_iterator *gsip = NULL, gsi; 4806 4807 if (MAY_HAVE_DEBUG_STMTS && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun))) 4808 { 4809 gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun))); 4810 gsip = &gsi; 4811 } 4812 len = adjustments.length (); 4813 for (i = 0; i < len; i++) 4814 { 4815 struct ipa_parm_adjustment *adj; 4816 imm_use_iterator ui; 4817 gimple stmt; 4818 gdebug *def_temp; 4819 tree name, vexpr, copy = NULL_TREE; 4820 use_operand_p use_p; 4821 4822 adj = &adjustments[i]; 4823 if (adj->op == IPA_PARM_OP_COPY || !is_gimple_reg (adj->base)) 4824 continue; 4825 name = ssa_default_def (cfun, adj->base); 4826 vexpr = NULL; 4827 if (name) 4828 FOR_EACH_IMM_USE_STMT (stmt, ui, name) 4829 { 4830 if (gimple_clobber_p (stmt)) 4831 { 4832 gimple_stmt_iterator cgsi = gsi_for_stmt (stmt); 4833 unlink_stmt_vdef (stmt); 4834 gsi_remove (&cgsi, true); 4835 release_defs (stmt); 4836 continue; 4837 } 4838 /* All other users must have been removed by 4839 ipa_sra_modify_function_body. */ 4840 gcc_assert (is_gimple_debug (stmt)); 4841 if (vexpr == NULL && gsip != NULL) 4842 { 4843 gcc_assert (TREE_CODE (adj->base) == PARM_DECL); 4844 vexpr = make_node (DEBUG_EXPR_DECL); 4845 def_temp = gimple_build_debug_source_bind (vexpr, adj->base, 4846 NULL); 4847 DECL_ARTIFICIAL (vexpr) = 1; 4848 TREE_TYPE (vexpr) = TREE_TYPE (name); 4849 DECL_MODE (vexpr) = DECL_MODE (adj->base); 4850 gsi_insert_before (gsip, def_temp, GSI_SAME_STMT); 4851 } 4852 if (vexpr) 4853 { 4854 FOR_EACH_IMM_USE_ON_STMT (use_p, ui) 4855 SET_USE (use_p, vexpr); 4856 } 4857 else 4858 gimple_debug_bind_reset_value (stmt); 4859 update_stmt (stmt); 4860 } 4861 /* Create a VAR_DECL for debug info purposes. */ 4862 if (!DECL_IGNORED_P (adj->base)) 4863 { 4864 copy = build_decl (DECL_SOURCE_LOCATION (current_function_decl), 4865 VAR_DECL, DECL_NAME (adj->base), 4866 TREE_TYPE (adj->base)); 4867 if (DECL_PT_UID_SET_P (adj->base)) 4868 SET_DECL_PT_UID (copy, DECL_PT_UID (adj->base)); 4869 TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (adj->base); 4870 TREE_READONLY (copy) = TREE_READONLY (adj->base); 4871 TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (adj->base); 4872 DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (adj->base); 4873 DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (adj->base); 4874 DECL_IGNORED_P (copy) = DECL_IGNORED_P (adj->base); 4875 DECL_ABSTRACT_ORIGIN (copy) = DECL_ORIGIN (adj->base); 4876 DECL_SEEN_IN_BIND_EXPR_P (copy) = 1; 4877 SET_DECL_RTL (copy, 0); 4878 TREE_USED (copy) = 1; 4879 DECL_CONTEXT (copy) = current_function_decl; 4880 add_local_decl (cfun, copy); 4881 DECL_CHAIN (copy) = 4882 BLOCK_VARS (DECL_INITIAL (current_function_decl)); 4883 BLOCK_VARS (DECL_INITIAL (current_function_decl)) = copy; 4884 } 4885 if (gsip != NULL && copy && target_for_debug_bind (adj->base)) 4886 { 4887 gcc_assert (TREE_CODE (adj->base) == PARM_DECL); 4888 if (vexpr) 4889 def_temp = gimple_build_debug_bind (copy, vexpr, NULL); 4890 else 4891 def_temp = gimple_build_debug_source_bind (copy, adj->base, 4892 NULL); 4893 gsi_insert_before (gsip, def_temp, GSI_SAME_STMT); 4894 } 4895 } 4896 } 4897 4898 /* Return false if all callers have at least as many actual arguments as there 4899 are formal parameters in the current function and that their types 4900 match. */ 4901 4902 static bool 4903 some_callers_have_mismatched_arguments_p (struct cgraph_node *node, 4904 void *data ATTRIBUTE_UNUSED) 4905 { 4906 struct cgraph_edge *cs; 4907 for (cs = node->callers; cs; cs = cs->next_caller) 4908 if (!cs->call_stmt || !callsite_arguments_match_p (cs->call_stmt)) 4909 return true; 4910 4911 return false; 4912 } 4913 4914 /* Return false if all callers have vuse attached to a call statement. */ 4915 4916 static bool 4917 some_callers_have_no_vuse_p (struct cgraph_node *node, 4918 void *data ATTRIBUTE_UNUSED) 4919 { 4920 struct cgraph_edge *cs; 4921 for (cs = node->callers; cs; cs = cs->next_caller) 4922 if (!cs->call_stmt || !gimple_vuse (cs->call_stmt)) 4923 return true; 4924 4925 return false; 4926 } 4927 4928 /* Convert all callers of NODE. */ 4929 4930 static bool 4931 convert_callers_for_node (struct cgraph_node *node, 4932 void *data) 4933 { 4934 ipa_parm_adjustment_vec *adjustments = (ipa_parm_adjustment_vec *) data; 4935 bitmap recomputed_callers = BITMAP_ALLOC (NULL); 4936 struct cgraph_edge *cs; 4937 4938 for (cs = node->callers; cs; cs = cs->next_caller) 4939 { 4940 push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl)); 4941 4942 if (dump_file) 4943 fprintf (dump_file, "Adjusting call %s/%i -> %s/%i\n", 4944 xstrdup (cs->caller->name ()), 4945 cs->caller->order, 4946 xstrdup (cs->callee->name ()), 4947 cs->callee->order); 4948 4949 ipa_modify_call_arguments (cs, cs->call_stmt, *adjustments); 4950 4951 pop_cfun (); 4952 } 4953 4954 for (cs = node->callers; cs; cs = cs->next_caller) 4955 if (bitmap_set_bit (recomputed_callers, cs->caller->uid) 4956 && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (cs->caller->decl))) 4957 compute_inline_parameters (cs->caller, true); 4958 BITMAP_FREE (recomputed_callers); 4959 4960 return true; 4961 } 4962 4963 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS. */ 4964 4965 static void 4966 convert_callers (struct cgraph_node *node, tree old_decl, 4967 ipa_parm_adjustment_vec adjustments) 4968 { 4969 basic_block this_block; 4970 4971 node->call_for_symbol_and_aliases (convert_callers_for_node, 4972 &adjustments, false); 4973 4974 if (!encountered_recursive_call) 4975 return; 4976 4977 FOR_EACH_BB_FN (this_block, cfun) 4978 { 4979 gimple_stmt_iterator gsi; 4980 4981 for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi)) 4982 { 4983 gcall *stmt; 4984 tree call_fndecl; 4985 stmt = dyn_cast <gcall *> (gsi_stmt (gsi)); 4986 if (!stmt) 4987 continue; 4988 call_fndecl = gimple_call_fndecl (stmt); 4989 if (call_fndecl == old_decl) 4990 { 4991 if (dump_file) 4992 fprintf (dump_file, "Adjusting recursive call"); 4993 gimple_call_set_fndecl (stmt, node->decl); 4994 ipa_modify_call_arguments (NULL, stmt, adjustments); 4995 } 4996 } 4997 } 4998 4999 return; 5000 } 5001 5002 /* Perform all the modification required in IPA-SRA for NODE to have parameters 5003 as given in ADJUSTMENTS. Return true iff the CFG has been changed. */ 5004 5005 static bool 5006 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments) 5007 { 5008 struct cgraph_node *new_node; 5009 bool cfg_changed; 5010 5011 cgraph_edge::rebuild_edges (); 5012 free_dominance_info (CDI_DOMINATORS); 5013 pop_cfun (); 5014 5015 /* This must be done after rebuilding cgraph edges for node above. 5016 Otherwise any recursive calls to node that are recorded in 5017 redirect_callers will be corrupted. */ 5018 vec<cgraph_edge *> redirect_callers = node->collect_callers (); 5019 new_node = node->create_version_clone_with_body (redirect_callers, NULL, 5020 NULL, false, NULL, NULL, 5021 "isra"); 5022 redirect_callers.release (); 5023 5024 push_cfun (DECL_STRUCT_FUNCTION (new_node->decl)); 5025 ipa_modify_formal_parameters (current_function_decl, adjustments); 5026 cfg_changed = ipa_sra_modify_function_body (adjustments); 5027 sra_ipa_reset_debug_stmts (adjustments); 5028 convert_callers (new_node, node->decl, adjustments); 5029 new_node->make_local (); 5030 return cfg_changed; 5031 } 5032 5033 /* Means of communication between ipa_sra_check_caller and 5034 ipa_sra_preliminary_function_checks. */ 5035 5036 struct ipa_sra_check_caller_data 5037 { 5038 bool has_callers; 5039 bool bad_arg_alignment; 5040 bool has_thunk; 5041 }; 5042 5043 /* If NODE has a caller, mark that fact in DATA which is pointer to 5044 ipa_sra_check_caller_data. Also check all aggregate arguments in all known 5045 calls if they are unit aligned and if not, set the appropriate flag in DATA 5046 too. */ 5047 5048 static bool 5049 ipa_sra_check_caller (struct cgraph_node *node, void *data) 5050 { 5051 if (!node->callers) 5052 return false; 5053 5054 struct ipa_sra_check_caller_data *iscc; 5055 iscc = (struct ipa_sra_check_caller_data *) data; 5056 iscc->has_callers = true; 5057 5058 for (cgraph_edge *cs = node->callers; cs; cs = cs->next_caller) 5059 { 5060 if (cs->caller->thunk.thunk_p) 5061 { 5062 iscc->has_thunk = true; 5063 return true; 5064 } 5065 gimple call_stmt = cs->call_stmt; 5066 unsigned count = gimple_call_num_args (call_stmt); 5067 for (unsigned i = 0; i < count; i++) 5068 { 5069 tree arg = gimple_call_arg (call_stmt, i); 5070 if (is_gimple_reg (arg)) 5071 continue; 5072 5073 tree offset; 5074 HOST_WIDE_INT bitsize, bitpos; 5075 machine_mode mode; 5076 int unsignedp, volatilep = 0; 5077 get_inner_reference (arg, &bitsize, &bitpos, &offset, &mode, 5078 &unsignedp, &volatilep, false); 5079 if (bitpos % BITS_PER_UNIT) 5080 { 5081 iscc->bad_arg_alignment = true; 5082 return true; 5083 } 5084 } 5085 } 5086 5087 return false; 5088 } 5089 5090 /* Return false the function is apparently unsuitable for IPA-SRA based on it's 5091 attributes, return true otherwise. NODE is the cgraph node of the current 5092 function. */ 5093 5094 static bool 5095 ipa_sra_preliminary_function_checks (struct cgraph_node *node) 5096 { 5097 if (!node->can_be_local_p ()) 5098 { 5099 if (dump_file) 5100 fprintf (dump_file, "Function not local to this compilation unit.\n"); 5101 return false; 5102 } 5103 5104 if (!node->local.can_change_signature) 5105 { 5106 if (dump_file) 5107 fprintf (dump_file, "Function can not change signature.\n"); 5108 return false; 5109 } 5110 5111 if (!tree_versionable_function_p (node->decl)) 5112 { 5113 if (dump_file) 5114 fprintf (dump_file, "Function is not versionable.\n"); 5115 return false; 5116 } 5117 5118 if (!opt_for_fn (node->decl, optimize) 5119 || !opt_for_fn (node->decl, flag_ipa_sra)) 5120 { 5121 if (dump_file) 5122 fprintf (dump_file, "Function not optimized.\n"); 5123 return false; 5124 } 5125 5126 if (DECL_VIRTUAL_P (current_function_decl)) 5127 { 5128 if (dump_file) 5129 fprintf (dump_file, "Function is a virtual method.\n"); 5130 return false; 5131 } 5132 5133 if ((DECL_ONE_ONLY (node->decl) || DECL_EXTERNAL (node->decl)) 5134 && inline_summaries->get (node)->size >= MAX_INLINE_INSNS_AUTO) 5135 { 5136 if (dump_file) 5137 fprintf (dump_file, "Function too big to be made truly local.\n"); 5138 return false; 5139 } 5140 5141 if (cfun->stdarg) 5142 { 5143 if (dump_file) 5144 fprintf (dump_file, "Function uses stdarg. \n"); 5145 return false; 5146 } 5147 5148 if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl))) 5149 return false; 5150 5151 if (DECL_DISREGARD_INLINE_LIMITS (node->decl)) 5152 { 5153 if (dump_file) 5154 fprintf (dump_file, "Always inline function will be inlined " 5155 "anyway. \n"); 5156 return false; 5157 } 5158 5159 struct ipa_sra_check_caller_data iscc; 5160 memset (&iscc, 0, sizeof(iscc)); 5161 node->call_for_symbol_and_aliases (ipa_sra_check_caller, &iscc, true); 5162 if (!iscc.has_callers) 5163 { 5164 if (dump_file) 5165 fprintf (dump_file, 5166 "Function has no callers in this compilation unit.\n"); 5167 return false; 5168 } 5169 5170 if (iscc.bad_arg_alignment) 5171 { 5172 if (dump_file) 5173 fprintf (dump_file, 5174 "A function call has an argument with non-unit alignment.\n"); 5175 return false; 5176 } 5177 5178 if (iscc.has_thunk) 5179 { 5180 if (dump_file) 5181 fprintf (dump_file, 5182 "A has thunk.\n"); 5183 return false; 5184 } 5185 5186 return true; 5187 } 5188 5189 /* Perform early interprocedural SRA. */ 5190 5191 static unsigned int 5192 ipa_early_sra (void) 5193 { 5194 struct cgraph_node *node = cgraph_node::get (current_function_decl); 5195 ipa_parm_adjustment_vec adjustments; 5196 int ret = 0; 5197 5198 if (!ipa_sra_preliminary_function_checks (node)) 5199 return 0; 5200 5201 sra_initialize (); 5202 sra_mode = SRA_MODE_EARLY_IPA; 5203 5204 if (!find_param_candidates ()) 5205 { 5206 if (dump_file) 5207 fprintf (dump_file, "Function has no IPA-SRA candidates.\n"); 5208 goto simple_out; 5209 } 5210 5211 if (node->call_for_symbol_and_aliases 5212 (some_callers_have_mismatched_arguments_p, NULL, true)) 5213 { 5214 if (dump_file) 5215 fprintf (dump_file, "There are callers with insufficient number of " 5216 "arguments or arguments with type mismatches.\n"); 5217 goto simple_out; 5218 } 5219 5220 if (node->call_for_symbol_and_aliases 5221 (some_callers_have_no_vuse_p, NULL, true)) 5222 { 5223 if (dump_file) 5224 fprintf (dump_file, "There are callers with no VUSE attached " 5225 "to a call stmt.\n"); 5226 goto simple_out; 5227 } 5228 5229 bb_dereferences = XCNEWVEC (HOST_WIDE_INT, 5230 func_param_count 5231 * last_basic_block_for_fn (cfun)); 5232 final_bbs = BITMAP_ALLOC (NULL); 5233 5234 scan_function (); 5235 if (encountered_apply_args) 5236 { 5237 if (dump_file) 5238 fprintf (dump_file, "Function calls __builtin_apply_args().\n"); 5239 goto out; 5240 } 5241 5242 if (encountered_unchangable_recursive_call) 5243 { 5244 if (dump_file) 5245 fprintf (dump_file, "Function calls itself with insufficient " 5246 "number of arguments.\n"); 5247 goto out; 5248 } 5249 5250 adjustments = analyze_all_param_acesses (); 5251 if (!adjustments.exists ()) 5252 goto out; 5253 if (dump_file) 5254 ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl); 5255 5256 if (modify_function (node, adjustments)) 5257 ret = TODO_update_ssa | TODO_cleanup_cfg; 5258 else 5259 ret = TODO_update_ssa; 5260 adjustments.release (); 5261 5262 statistics_counter_event (cfun, "Unused parameters deleted", 5263 sra_stats.deleted_unused_parameters); 5264 statistics_counter_event (cfun, "Scalar parameters converted to by-value", 5265 sra_stats.scalar_by_ref_to_by_val); 5266 statistics_counter_event (cfun, "Aggregate parameters broken up", 5267 sra_stats.aggregate_params_reduced); 5268 statistics_counter_event (cfun, "Aggregate parameter components created", 5269 sra_stats.param_reductions_created); 5270 5271 out: 5272 BITMAP_FREE (final_bbs); 5273 free (bb_dereferences); 5274 simple_out: 5275 sra_deinitialize (); 5276 return ret; 5277 } 5278 5279 namespace { 5280 5281 const pass_data pass_data_early_ipa_sra = 5282 { 5283 GIMPLE_PASS, /* type */ 5284 "eipa_sra", /* name */ 5285 OPTGROUP_NONE, /* optinfo_flags */ 5286 TV_IPA_SRA, /* tv_id */ 5287 0, /* properties_required */ 5288 0, /* properties_provided */ 5289 0, /* properties_destroyed */ 5290 0, /* todo_flags_start */ 5291 TODO_dump_symtab, /* todo_flags_finish */ 5292 }; 5293 5294 class pass_early_ipa_sra : public gimple_opt_pass 5295 { 5296 public: 5297 pass_early_ipa_sra (gcc::context *ctxt) 5298 : gimple_opt_pass (pass_data_early_ipa_sra, ctxt) 5299 {} 5300 5301 /* opt_pass methods: */ 5302 virtual bool gate (function *) { return flag_ipa_sra && dbg_cnt (eipa_sra); } 5303 virtual unsigned int execute (function *) { return ipa_early_sra (); } 5304 5305 }; // class pass_early_ipa_sra 5306 5307 } // anon namespace 5308 5309 gimple_opt_pass * 5310 make_pass_early_ipa_sra (gcc::context *ctxt) 5311 { 5312 return new pass_early_ipa_sra (ctxt); 5313 } 5314