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