1169689Skan/* Scalar Replacement of Aggregates (SRA) converts some structure 2169689Skan references into scalar references, exposing them to the scalar 3169689Skan optimizers. 4169689Skan Copyright (C) 2003, 2004, 2005, 2006, 2007 5169689Skan Free Software Foundation, Inc. 6169689Skan Contributed by Diego Novillo <dnovillo@redhat.com> 7169689Skan 8169689SkanThis file is part of GCC. 9169689Skan 10169689SkanGCC is free software; you can redistribute it and/or modify it 11169689Skanunder the terms of the GNU General Public License as published by the 12169689SkanFree Software Foundation; either version 2, or (at your option) any 13169689Skanlater version. 14169689Skan 15169689SkanGCC is distributed in the hope that it will be useful, but WITHOUT 16169689SkanANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 17169689SkanFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18169689Skanfor more details. 19169689Skan 20169689SkanYou should have received a copy of the GNU General Public License 21169689Skanalong with GCC; see the file COPYING. If not, write to the Free 22169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 23169689Skan02110-1301, USA. */ 24169689Skan 25169689Skan#include "config.h" 26169689Skan#include "system.h" 27169689Skan#include "coretypes.h" 28169689Skan#include "tm.h" 29169689Skan#include "ggc.h" 30169689Skan#include "tree.h" 31169689Skan 32169689Skan/* These RTL headers are needed for basic-block.h. */ 33169689Skan#include "rtl.h" 34169689Skan#include "tm_p.h" 35169689Skan#include "hard-reg-set.h" 36169689Skan#include "basic-block.h" 37169689Skan#include "diagnostic.h" 38169689Skan#include "langhooks.h" 39169689Skan#include "tree-inline.h" 40169689Skan#include "tree-flow.h" 41169689Skan#include "tree-gimple.h" 42169689Skan#include "tree-dump.h" 43169689Skan#include "tree-pass.h" 44169689Skan#include "timevar.h" 45169689Skan#include "flags.h" 46169689Skan#include "bitmap.h" 47169689Skan#include "obstack.h" 48169689Skan#include "target.h" 49169689Skan/* expr.h is needed for MOVE_RATIO. */ 50169689Skan#include "expr.h" 51169689Skan#include "params.h" 52169689Skan 53169689Skan 54169689Skan/* This object of this pass is to replace a non-addressable aggregate with a 55169689Skan set of independent variables. Most of the time, all of these variables 56169689Skan will be scalars. But a secondary objective is to break up larger 57169689Skan aggregates into smaller aggregates. In the process we may find that some 58169689Skan bits of the larger aggregate can be deleted as unreferenced. 59169689Skan 60169689Skan This substitution is done globally. More localized substitutions would 61169689Skan be the purvey of a load-store motion pass. 62169689Skan 63169689Skan The optimization proceeds in phases: 64169689Skan 65169689Skan (1) Identify variables that have types that are candidates for 66169689Skan decomposition. 67169689Skan 68169689Skan (2) Scan the function looking for the ways these variables are used. 69169689Skan In particular we're interested in the number of times a variable 70169689Skan (or member) is needed as a complete unit, and the number of times 71169689Skan a variable (or member) is copied. 72169689Skan 73169689Skan (3) Based on the usage profile, instantiate substitution variables. 74169689Skan 75169689Skan (4) Scan the function making replacements. 76169689Skan*/ 77169689Skan 78169689Skan 79169689Skan/* The set of todo flags to return from tree_sra. */ 80169689Skanstatic unsigned int todoflags; 81169689Skan 82169689Skan/* The set of aggregate variables that are candidates for scalarization. */ 83169689Skanstatic bitmap sra_candidates; 84169689Skan 85169689Skan/* Set of scalarizable PARM_DECLs that need copy-in operations at the 86169689Skan beginning of the function. */ 87169689Skanstatic bitmap needs_copy_in; 88169689Skan 89169689Skan/* Sets of bit pairs that cache type decomposition and instantiation. */ 90169689Skanstatic bitmap sra_type_decomp_cache; 91169689Skanstatic bitmap sra_type_inst_cache; 92169689Skan 93169689Skan/* One of these structures is created for each candidate aggregate and 94169689Skan each (accessed) member or group of members of such an aggregate. */ 95169689Skanstruct sra_elt 96169689Skan{ 97169689Skan /* A tree of the elements. Used when we want to traverse everything. */ 98169689Skan struct sra_elt *parent; 99169689Skan struct sra_elt *groups; 100169689Skan struct sra_elt *children; 101169689Skan struct sra_elt *sibling; 102169689Skan 103169689Skan /* If this element is a root, then this is the VAR_DECL. If this is 104169689Skan a sub-element, this is some token used to identify the reference. 105169689Skan In the case of COMPONENT_REF, this is the FIELD_DECL. In the case 106169689Skan of an ARRAY_REF, this is the (constant) index. In the case of an 107169689Skan ARRAY_RANGE_REF, this is the (constant) RANGE_EXPR. In the case 108169689Skan of a complex number, this is a zero or one. */ 109169689Skan tree element; 110169689Skan 111169689Skan /* The type of the element. */ 112169689Skan tree type; 113169689Skan 114169689Skan /* A VAR_DECL, for any sub-element we've decided to replace. */ 115169689Skan tree replacement; 116169689Skan 117169689Skan /* The number of times the element is referenced as a whole. I.e. 118169689Skan given "a.b.c", this would be incremented for C, but not for A or B. */ 119169689Skan unsigned int n_uses; 120169689Skan 121169689Skan /* The number of times the element is copied to or from another 122169689Skan scalarizable element. */ 123169689Skan unsigned int n_copies; 124169689Skan 125169689Skan /* True if TYPE is scalar. */ 126169689Skan bool is_scalar; 127169689Skan 128169689Skan /* True if this element is a group of members of its parent. */ 129169689Skan bool is_group; 130169689Skan 131169689Skan /* True if we saw something about this element that prevents scalarization, 132169689Skan such as non-constant indexing. */ 133169689Skan bool cannot_scalarize; 134169689Skan 135169689Skan /* True if we've decided that structure-to-structure assignment 136169689Skan should happen via memcpy and not per-element. */ 137169689Skan bool use_block_copy; 138169689Skan 139169689Skan /* True if everything under this element has been marked TREE_NO_WARNING. */ 140169689Skan bool all_no_warning; 141169689Skan 142169689Skan /* A flag for use with/after random access traversals. */ 143169689Skan bool visited; 144169689Skan}; 145169689Skan 146169689Skan#define IS_ELEMENT_FOR_GROUP(ELEMENT) (TREE_CODE (ELEMENT) == RANGE_EXPR) 147169689Skan 148169689Skan#define FOR_EACH_ACTUAL_CHILD(CHILD, ELT) \ 149169689Skan for ((CHILD) = (ELT)->is_group \ 150169689Skan ? next_child_for_group (NULL, (ELT)) \ 151169689Skan : (ELT)->children; \ 152169689Skan (CHILD); \ 153169689Skan (CHILD) = (ELT)->is_group \ 154169689Skan ? next_child_for_group ((CHILD), (ELT)) \ 155169689Skan : (CHILD)->sibling) 156169689Skan 157169689Skan/* Helper function for above macro. Return next child in group. */ 158169689Skanstatic struct sra_elt * 159169689Skannext_child_for_group (struct sra_elt *child, struct sra_elt *group) 160169689Skan{ 161169689Skan gcc_assert (group->is_group); 162169689Skan 163169689Skan /* Find the next child in the parent. */ 164169689Skan if (child) 165169689Skan child = child->sibling; 166169689Skan else 167169689Skan child = group->parent->children; 168169689Skan 169169689Skan /* Skip siblings that do not belong to the group. */ 170169689Skan while (child) 171169689Skan { 172169689Skan tree g_elt = group->element; 173169689Skan if (TREE_CODE (g_elt) == RANGE_EXPR) 174169689Skan { 175169689Skan if (!tree_int_cst_lt (child->element, TREE_OPERAND (g_elt, 0)) 176169689Skan && !tree_int_cst_lt (TREE_OPERAND (g_elt, 1), child->element)) 177169689Skan break; 178169689Skan } 179169689Skan else 180169689Skan gcc_unreachable (); 181169689Skan 182169689Skan child = child->sibling; 183169689Skan } 184169689Skan 185169689Skan return child; 186169689Skan} 187169689Skan 188169689Skan/* Random access to the child of a parent is performed by hashing. 189169689Skan This prevents quadratic behavior, and allows SRA to function 190169689Skan reasonably on larger records. */ 191169689Skanstatic htab_t sra_map; 192169689Skan 193169689Skan/* All structures are allocated out of the following obstack. */ 194169689Skanstatic struct obstack sra_obstack; 195169689Skan 196169689Skan/* Debugging functions. */ 197169689Skanstatic void dump_sra_elt_name (FILE *, struct sra_elt *); 198169689Skanextern void debug_sra_elt_name (struct sra_elt *); 199169689Skan 200169689Skan/* Forward declarations. */ 201169689Skanstatic tree generate_element_ref (struct sra_elt *); 202169689Skan 203169689Skan/* Return true if DECL is an SRA candidate. */ 204169689Skan 205169689Skanstatic bool 206169689Skanis_sra_candidate_decl (tree decl) 207169689Skan{ 208169689Skan return DECL_P (decl) && bitmap_bit_p (sra_candidates, DECL_UID (decl)); 209169689Skan} 210169689Skan 211169689Skan/* Return true if TYPE is a scalar type. */ 212169689Skan 213169689Skanstatic bool 214169689Skanis_sra_scalar_type (tree type) 215169689Skan{ 216169689Skan enum tree_code code = TREE_CODE (type); 217169689Skan return (code == INTEGER_TYPE || code == REAL_TYPE || code == VECTOR_TYPE 218169689Skan || code == ENUMERAL_TYPE || code == BOOLEAN_TYPE 219169689Skan || code == POINTER_TYPE || code == OFFSET_TYPE 220169689Skan || code == REFERENCE_TYPE); 221169689Skan} 222169689Skan 223169689Skan/* Return true if TYPE can be decomposed into a set of independent variables. 224169689Skan 225169689Skan Note that this doesn't imply that all elements of TYPE can be 226169689Skan instantiated, just that if we decide to break up the type into 227169689Skan separate pieces that it can be done. */ 228169689Skan 229169689Skanbool 230169689Skansra_type_can_be_decomposed_p (tree type) 231169689Skan{ 232169689Skan unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2; 233169689Skan tree t; 234169689Skan 235169689Skan /* Avoid searching the same type twice. */ 236169689Skan if (bitmap_bit_p (sra_type_decomp_cache, cache+0)) 237169689Skan return true; 238169689Skan if (bitmap_bit_p (sra_type_decomp_cache, cache+1)) 239169689Skan return false; 240169689Skan 241169689Skan /* The type must have a definite nonzero size. */ 242169689Skan if (TYPE_SIZE (type) == NULL || TREE_CODE (TYPE_SIZE (type)) != INTEGER_CST 243169689Skan || integer_zerop (TYPE_SIZE (type))) 244169689Skan goto fail; 245169689Skan 246169689Skan /* The type must be a non-union aggregate. */ 247169689Skan switch (TREE_CODE (type)) 248169689Skan { 249169689Skan case RECORD_TYPE: 250169689Skan { 251169689Skan bool saw_one_field = false; 252169689Skan 253169689Skan for (t = TYPE_FIELDS (type); t ; t = TREE_CHAIN (t)) 254169689Skan if (TREE_CODE (t) == FIELD_DECL) 255169689Skan { 256169689Skan /* Reject incorrectly represented bit fields. */ 257169689Skan if (DECL_BIT_FIELD (t) 258169689Skan && (tree_low_cst (DECL_SIZE (t), 1) 259169689Skan != TYPE_PRECISION (TREE_TYPE (t)))) 260169689Skan goto fail; 261169689Skan 262169689Skan saw_one_field = true; 263169689Skan } 264169689Skan 265169689Skan /* Record types must have at least one field. */ 266169689Skan if (!saw_one_field) 267169689Skan goto fail; 268169689Skan } 269169689Skan break; 270169689Skan 271169689Skan case ARRAY_TYPE: 272169689Skan /* Array types must have a fixed lower and upper bound. */ 273169689Skan t = TYPE_DOMAIN (type); 274169689Skan if (t == NULL) 275169689Skan goto fail; 276169689Skan if (TYPE_MIN_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MIN_VALUE (t))) 277169689Skan goto fail; 278169689Skan if (TYPE_MAX_VALUE (t) == NULL || !TREE_CONSTANT (TYPE_MAX_VALUE (t))) 279169689Skan goto fail; 280169689Skan break; 281169689Skan 282169689Skan case COMPLEX_TYPE: 283169689Skan break; 284169689Skan 285169689Skan default: 286169689Skan goto fail; 287169689Skan } 288169689Skan 289169689Skan bitmap_set_bit (sra_type_decomp_cache, cache+0); 290169689Skan return true; 291169689Skan 292169689Skan fail: 293169689Skan bitmap_set_bit (sra_type_decomp_cache, cache+1); 294169689Skan return false; 295169689Skan} 296169689Skan 297169689Skan/* Return true if DECL can be decomposed into a set of independent 298169689Skan (though not necessarily scalar) variables. */ 299169689Skan 300169689Skanstatic bool 301169689Skandecl_can_be_decomposed_p (tree var) 302169689Skan{ 303169689Skan /* Early out for scalars. */ 304169689Skan if (is_sra_scalar_type (TREE_TYPE (var))) 305169689Skan return false; 306169689Skan 307169689Skan /* The variable must not be aliased. */ 308169689Skan if (!is_gimple_non_addressable (var)) 309169689Skan { 310169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 311169689Skan { 312169689Skan fprintf (dump_file, "Cannot scalarize variable "); 313169689Skan print_generic_expr (dump_file, var, dump_flags); 314169689Skan fprintf (dump_file, " because it must live in memory\n"); 315169689Skan } 316169689Skan return false; 317169689Skan } 318169689Skan 319169689Skan /* The variable must not be volatile. */ 320169689Skan if (TREE_THIS_VOLATILE (var)) 321169689Skan { 322169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 323169689Skan { 324169689Skan fprintf (dump_file, "Cannot scalarize variable "); 325169689Skan print_generic_expr (dump_file, var, dump_flags); 326169689Skan fprintf (dump_file, " because it is declared volatile\n"); 327169689Skan } 328169689Skan return false; 329169689Skan } 330169689Skan 331169689Skan /* We must be able to decompose the variable's type. */ 332169689Skan if (!sra_type_can_be_decomposed_p (TREE_TYPE (var))) 333169689Skan { 334169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 335169689Skan { 336169689Skan fprintf (dump_file, "Cannot scalarize variable "); 337169689Skan print_generic_expr (dump_file, var, dump_flags); 338169689Skan fprintf (dump_file, " because its type cannot be decomposed\n"); 339169689Skan } 340169689Skan return false; 341169689Skan } 342169689Skan 343169689Skan return true; 344169689Skan} 345169689Skan 346169689Skan/* Return true if TYPE can be *completely* decomposed into scalars. */ 347169689Skan 348169689Skanstatic bool 349169689Skantype_can_instantiate_all_elements (tree type) 350169689Skan{ 351169689Skan if (is_sra_scalar_type (type)) 352169689Skan return true; 353169689Skan if (!sra_type_can_be_decomposed_p (type)) 354169689Skan return false; 355169689Skan 356169689Skan switch (TREE_CODE (type)) 357169689Skan { 358169689Skan case RECORD_TYPE: 359169689Skan { 360169689Skan unsigned int cache = TYPE_UID (TYPE_MAIN_VARIANT (type)) * 2; 361169689Skan tree f; 362169689Skan 363169689Skan if (bitmap_bit_p (sra_type_inst_cache, cache+0)) 364169689Skan return true; 365169689Skan if (bitmap_bit_p (sra_type_inst_cache, cache+1)) 366169689Skan return false; 367169689Skan 368169689Skan for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f)) 369169689Skan if (TREE_CODE (f) == FIELD_DECL) 370169689Skan { 371169689Skan if (!type_can_instantiate_all_elements (TREE_TYPE (f))) 372169689Skan { 373169689Skan bitmap_set_bit (sra_type_inst_cache, cache+1); 374169689Skan return false; 375169689Skan } 376169689Skan } 377169689Skan 378169689Skan bitmap_set_bit (sra_type_inst_cache, cache+0); 379169689Skan return true; 380169689Skan } 381169689Skan 382169689Skan case ARRAY_TYPE: 383169689Skan return type_can_instantiate_all_elements (TREE_TYPE (type)); 384169689Skan 385169689Skan case COMPLEX_TYPE: 386169689Skan return true; 387169689Skan 388169689Skan default: 389169689Skan gcc_unreachable (); 390169689Skan } 391169689Skan} 392169689Skan 393169689Skan/* Test whether ELT or some sub-element cannot be scalarized. */ 394169689Skan 395169689Skanstatic bool 396169689Skancan_completely_scalarize_p (struct sra_elt *elt) 397169689Skan{ 398169689Skan struct sra_elt *c; 399169689Skan 400169689Skan if (elt->cannot_scalarize) 401169689Skan return false; 402169689Skan 403169689Skan for (c = elt->children; c; c = c->sibling) 404169689Skan if (!can_completely_scalarize_p (c)) 405169689Skan return false; 406169689Skan 407169689Skan for (c = elt->groups; c; c = c->sibling) 408169689Skan if (!can_completely_scalarize_p (c)) 409169689Skan return false; 410169689Skan 411169689Skan return true; 412169689Skan} 413169689Skan 414169689Skan 415169689Skan/* A simplified tree hashing algorithm that only handles the types of 416169689Skan trees we expect to find in sra_elt->element. */ 417169689Skan 418169689Skanstatic hashval_t 419169689Skansra_hash_tree (tree t) 420169689Skan{ 421169689Skan hashval_t h; 422169689Skan 423169689Skan switch (TREE_CODE (t)) 424169689Skan { 425169689Skan case VAR_DECL: 426169689Skan case PARM_DECL: 427169689Skan case RESULT_DECL: 428169689Skan h = DECL_UID (t); 429169689Skan break; 430169689Skan 431169689Skan case INTEGER_CST: 432169689Skan h = TREE_INT_CST_LOW (t) ^ TREE_INT_CST_HIGH (t); 433169689Skan break; 434169689Skan 435169689Skan case RANGE_EXPR: 436169689Skan h = iterative_hash_expr (TREE_OPERAND (t, 0), 0); 437169689Skan h = iterative_hash_expr (TREE_OPERAND (t, 1), h); 438169689Skan break; 439169689Skan 440169689Skan case FIELD_DECL: 441169689Skan /* We can have types that are compatible, but have different member 442169689Skan lists, so we can't hash fields by ID. Use offsets instead. */ 443169689Skan h = iterative_hash_expr (DECL_FIELD_OFFSET (t), 0); 444169689Skan h = iterative_hash_expr (DECL_FIELD_BIT_OFFSET (t), h); 445169689Skan break; 446169689Skan 447169689Skan default: 448169689Skan gcc_unreachable (); 449169689Skan } 450169689Skan 451169689Skan return h; 452169689Skan} 453169689Skan 454169689Skan/* Hash function for type SRA_PAIR. */ 455169689Skan 456169689Skanstatic hashval_t 457169689Skansra_elt_hash (const void *x) 458169689Skan{ 459169689Skan const struct sra_elt *e = x; 460169689Skan const struct sra_elt *p; 461169689Skan hashval_t h; 462169689Skan 463169689Skan h = sra_hash_tree (e->element); 464169689Skan 465169689Skan /* Take into account everything back up the chain. Given that chain 466169689Skan lengths are rarely very long, this should be acceptable. If we 467169689Skan truly identify this as a performance problem, it should work to 468169689Skan hash the pointer value "e->parent". */ 469169689Skan for (p = e->parent; p ; p = p->parent) 470169689Skan h = (h * 65521) ^ sra_hash_tree (p->element); 471169689Skan 472169689Skan return h; 473169689Skan} 474169689Skan 475169689Skan/* Equality function for type SRA_PAIR. */ 476169689Skan 477169689Skanstatic int 478169689Skansra_elt_eq (const void *x, const void *y) 479169689Skan{ 480169689Skan const struct sra_elt *a = x; 481169689Skan const struct sra_elt *b = y; 482169689Skan tree ae, be; 483169689Skan 484169689Skan if (a->parent != b->parent) 485169689Skan return false; 486169689Skan 487169689Skan ae = a->element; 488169689Skan be = b->element; 489169689Skan 490169689Skan if (ae == be) 491169689Skan return true; 492169689Skan if (TREE_CODE (ae) != TREE_CODE (be)) 493169689Skan return false; 494169689Skan 495169689Skan switch (TREE_CODE (ae)) 496169689Skan { 497169689Skan case VAR_DECL: 498169689Skan case PARM_DECL: 499169689Skan case RESULT_DECL: 500169689Skan /* These are all pointer unique. */ 501169689Skan return false; 502169689Skan 503169689Skan case INTEGER_CST: 504169689Skan /* Integers are not pointer unique, so compare their values. */ 505169689Skan return tree_int_cst_equal (ae, be); 506169689Skan 507169689Skan case RANGE_EXPR: 508169689Skan return 509169689Skan tree_int_cst_equal (TREE_OPERAND (ae, 0), TREE_OPERAND (be, 0)) 510169689Skan && tree_int_cst_equal (TREE_OPERAND (ae, 1), TREE_OPERAND (be, 1)); 511169689Skan 512169689Skan case FIELD_DECL: 513169689Skan /* Fields are unique within a record, but not between 514169689Skan compatible records. */ 515169689Skan if (DECL_FIELD_CONTEXT (ae) == DECL_FIELD_CONTEXT (be)) 516169689Skan return false; 517169689Skan return fields_compatible_p (ae, be); 518169689Skan 519169689Skan default: 520169689Skan gcc_unreachable (); 521169689Skan } 522169689Skan} 523169689Skan 524169689Skan/* Create or return the SRA_ELT structure for CHILD in PARENT. PARENT 525169689Skan may be null, in which case CHILD must be a DECL. */ 526169689Skan 527169689Skanstatic struct sra_elt * 528169689Skanlookup_element (struct sra_elt *parent, tree child, tree type, 529169689Skan enum insert_option insert) 530169689Skan{ 531169689Skan struct sra_elt dummy; 532169689Skan struct sra_elt **slot; 533169689Skan struct sra_elt *elt; 534169689Skan 535169689Skan if (parent) 536169689Skan dummy.parent = parent->is_group ? parent->parent : parent; 537169689Skan else 538169689Skan dummy.parent = NULL; 539169689Skan dummy.element = child; 540169689Skan 541169689Skan slot = (struct sra_elt **) htab_find_slot (sra_map, &dummy, insert); 542169689Skan if (!slot && insert == NO_INSERT) 543169689Skan return NULL; 544169689Skan 545169689Skan elt = *slot; 546169689Skan if (!elt && insert == INSERT) 547169689Skan { 548169689Skan *slot = elt = obstack_alloc (&sra_obstack, sizeof (*elt)); 549169689Skan memset (elt, 0, sizeof (*elt)); 550169689Skan 551169689Skan elt->parent = parent; 552169689Skan elt->element = child; 553169689Skan elt->type = type; 554169689Skan elt->is_scalar = is_sra_scalar_type (type); 555169689Skan 556169689Skan if (parent) 557169689Skan { 558169689Skan if (IS_ELEMENT_FOR_GROUP (elt->element)) 559169689Skan { 560169689Skan elt->is_group = true; 561169689Skan elt->sibling = parent->groups; 562169689Skan parent->groups = elt; 563169689Skan } 564169689Skan else 565169689Skan { 566169689Skan elt->sibling = parent->children; 567169689Skan parent->children = elt; 568169689Skan } 569169689Skan } 570169689Skan 571169689Skan /* If this is a parameter, then if we want to scalarize, we have 572169689Skan one copy from the true function parameter. Count it now. */ 573169689Skan if (TREE_CODE (child) == PARM_DECL) 574169689Skan { 575169689Skan elt->n_copies = 1; 576169689Skan bitmap_set_bit (needs_copy_in, DECL_UID (child)); 577169689Skan } 578169689Skan } 579169689Skan 580169689Skan return elt; 581169689Skan} 582169689Skan 583169689Skan/* Create or return the SRA_ELT structure for EXPR if the expression 584169689Skan refers to a scalarizable variable. */ 585169689Skan 586169689Skanstatic struct sra_elt * 587169689Skanmaybe_lookup_element_for_expr (tree expr) 588169689Skan{ 589169689Skan struct sra_elt *elt; 590169689Skan tree child; 591169689Skan 592169689Skan switch (TREE_CODE (expr)) 593169689Skan { 594169689Skan case VAR_DECL: 595169689Skan case PARM_DECL: 596169689Skan case RESULT_DECL: 597169689Skan if (is_sra_candidate_decl (expr)) 598169689Skan return lookup_element (NULL, expr, TREE_TYPE (expr), INSERT); 599169689Skan return NULL; 600169689Skan 601169689Skan case ARRAY_REF: 602169689Skan /* We can't scalarize variable array indices. */ 603169689Skan if (in_array_bounds_p (expr)) 604169689Skan child = TREE_OPERAND (expr, 1); 605169689Skan else 606169689Skan return NULL; 607169689Skan break; 608169689Skan 609169689Skan case ARRAY_RANGE_REF: 610169689Skan /* We can't scalarize variable array indices. */ 611169689Skan if (range_in_array_bounds_p (expr)) 612169689Skan { 613169689Skan tree domain = TYPE_DOMAIN (TREE_TYPE (expr)); 614169689Skan child = build2 (RANGE_EXPR, integer_type_node, 615169689Skan TYPE_MIN_VALUE (domain), TYPE_MAX_VALUE (domain)); 616169689Skan } 617169689Skan else 618169689Skan return NULL; 619169689Skan break; 620169689Skan 621169689Skan case COMPONENT_REF: 622169689Skan /* Don't look through unions. */ 623169689Skan if (TREE_CODE (TREE_TYPE (TREE_OPERAND (expr, 0))) != RECORD_TYPE) 624169689Skan return NULL; 625169689Skan child = TREE_OPERAND (expr, 1); 626169689Skan break; 627169689Skan 628169689Skan case REALPART_EXPR: 629169689Skan child = integer_zero_node; 630169689Skan break; 631169689Skan case IMAGPART_EXPR: 632169689Skan child = integer_one_node; 633169689Skan break; 634169689Skan 635169689Skan default: 636169689Skan return NULL; 637169689Skan } 638169689Skan 639169689Skan elt = maybe_lookup_element_for_expr (TREE_OPERAND (expr, 0)); 640169689Skan if (elt) 641169689Skan return lookup_element (elt, child, TREE_TYPE (expr), INSERT); 642169689Skan return NULL; 643169689Skan} 644169689Skan 645169689Skan 646169689Skan/* Functions to walk just enough of the tree to see all scalarizable 647169689Skan references, and categorize them. */ 648169689Skan 649169689Skan/* A set of callbacks for phases 2 and 4. They'll be invoked for the 650169689Skan various kinds of references seen. In all cases, *BSI is an iterator 651169689Skan pointing to the statement being processed. */ 652169689Skanstruct sra_walk_fns 653169689Skan{ 654169689Skan /* Invoked when ELT is required as a unit. Note that ELT might refer to 655169689Skan a leaf node, in which case this is a simple scalar reference. *EXPR_P 656169689Skan points to the location of the expression. IS_OUTPUT is true if this 657169689Skan is a left-hand-side reference. USE_ALL is true if we saw something we 658169689Skan couldn't quite identify and had to force the use of the entire object. */ 659169689Skan void (*use) (struct sra_elt *elt, tree *expr_p, 660169689Skan block_stmt_iterator *bsi, bool is_output, bool use_all); 661169689Skan 662169689Skan /* Invoked when we have a copy between two scalarizable references. */ 663169689Skan void (*copy) (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt, 664169689Skan block_stmt_iterator *bsi); 665169689Skan 666169689Skan /* Invoked when ELT is initialized from a constant. VALUE may be NULL, 667169689Skan in which case it should be treated as an empty CONSTRUCTOR. */ 668169689Skan void (*init) (struct sra_elt *elt, tree value, block_stmt_iterator *bsi); 669169689Skan 670169689Skan /* Invoked when we have a copy between one scalarizable reference ELT 671169689Skan and one non-scalarizable reference OTHER without side-effects. 672169689Skan IS_OUTPUT is true if ELT is on the left-hand side. */ 673169689Skan void (*ldst) (struct sra_elt *elt, tree other, 674169689Skan block_stmt_iterator *bsi, bool is_output); 675169689Skan 676169689Skan /* True during phase 2, false during phase 4. */ 677169689Skan /* ??? This is a hack. */ 678169689Skan bool initial_scan; 679169689Skan}; 680169689Skan 681169689Skan#ifdef ENABLE_CHECKING 682169689Skan/* Invoked via walk_tree, if *TP contains a candidate decl, return it. */ 683169689Skan 684169689Skanstatic tree 685169689Skansra_find_candidate_decl (tree *tp, int *walk_subtrees, 686169689Skan void *data ATTRIBUTE_UNUSED) 687169689Skan{ 688169689Skan tree t = *tp; 689169689Skan enum tree_code code = TREE_CODE (t); 690169689Skan 691169689Skan if (code == VAR_DECL || code == PARM_DECL || code == RESULT_DECL) 692169689Skan { 693169689Skan *walk_subtrees = 0; 694169689Skan if (is_sra_candidate_decl (t)) 695169689Skan return t; 696169689Skan } 697169689Skan else if (TYPE_P (t)) 698169689Skan *walk_subtrees = 0; 699169689Skan 700169689Skan return NULL; 701169689Skan} 702169689Skan#endif 703169689Skan 704169689Skan/* Walk most expressions looking for a scalarizable aggregate. 705169689Skan If we find one, invoke FNS->USE. */ 706169689Skan 707169689Skanstatic void 708169689Skansra_walk_expr (tree *expr_p, block_stmt_iterator *bsi, bool is_output, 709169689Skan const struct sra_walk_fns *fns) 710169689Skan{ 711169689Skan tree expr = *expr_p; 712169689Skan tree inner = expr; 713169689Skan bool disable_scalarization = false; 714169689Skan bool use_all_p = false; 715169689Skan 716169689Skan /* We're looking to collect a reference expression between EXPR and INNER, 717169689Skan such that INNER is a scalarizable decl and all other nodes through EXPR 718169689Skan are references that we can scalarize. If we come across something that 719169689Skan we can't scalarize, we reset EXPR. This has the effect of making it 720169689Skan appear that we're referring to the larger expression as a whole. */ 721169689Skan 722169689Skan while (1) 723169689Skan switch (TREE_CODE (inner)) 724169689Skan { 725169689Skan case VAR_DECL: 726169689Skan case PARM_DECL: 727169689Skan case RESULT_DECL: 728169689Skan /* If there is a scalarizable decl at the bottom, then process it. */ 729169689Skan if (is_sra_candidate_decl (inner)) 730169689Skan { 731169689Skan struct sra_elt *elt = maybe_lookup_element_for_expr (expr); 732169689Skan if (disable_scalarization) 733169689Skan elt->cannot_scalarize = true; 734169689Skan else 735169689Skan fns->use (elt, expr_p, bsi, is_output, use_all_p); 736169689Skan } 737169689Skan return; 738169689Skan 739169689Skan case ARRAY_REF: 740169689Skan /* Non-constant index means any member may be accessed. Prevent the 741169689Skan expression from being scalarized. If we were to treat this as a 742169689Skan reference to the whole array, we can wind up with a single dynamic 743169689Skan index reference inside a loop being overridden by several constant 744169689Skan index references during loop setup. It's possible that this could 745169689Skan be avoided by using dynamic usage counts based on BB trip counts 746169689Skan (based on loop analysis or profiling), but that hardly seems worth 747169689Skan the effort. */ 748169689Skan /* ??? Hack. Figure out how to push this into the scan routines 749169689Skan without duplicating too much code. */ 750169689Skan if (!in_array_bounds_p (inner)) 751169689Skan { 752169689Skan disable_scalarization = true; 753169689Skan goto use_all; 754169689Skan } 755169689Skan /* ??? Are we assured that non-constant bounds and stride will have 756169689Skan the same value everywhere? I don't think Fortran will... */ 757169689Skan if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3)) 758169689Skan goto use_all; 759169689Skan inner = TREE_OPERAND (inner, 0); 760169689Skan break; 761169689Skan 762169689Skan case ARRAY_RANGE_REF: 763169689Skan if (!range_in_array_bounds_p (inner)) 764169689Skan { 765169689Skan disable_scalarization = true; 766169689Skan goto use_all; 767169689Skan } 768169689Skan /* ??? See above non-constant bounds and stride . */ 769169689Skan if (TREE_OPERAND (inner, 2) || TREE_OPERAND (inner, 3)) 770169689Skan goto use_all; 771169689Skan inner = TREE_OPERAND (inner, 0); 772169689Skan break; 773169689Skan 774169689Skan case COMPONENT_REF: 775169689Skan /* A reference to a union member constitutes a reference to the 776169689Skan entire union. */ 777169689Skan if (TREE_CODE (TREE_TYPE (TREE_OPERAND (inner, 0))) != RECORD_TYPE) 778169689Skan goto use_all; 779169689Skan /* ??? See above re non-constant stride. */ 780169689Skan if (TREE_OPERAND (inner, 2)) 781169689Skan goto use_all; 782169689Skan inner = TREE_OPERAND (inner, 0); 783169689Skan break; 784169689Skan 785169689Skan case REALPART_EXPR: 786169689Skan case IMAGPART_EXPR: 787169689Skan inner = TREE_OPERAND (inner, 0); 788169689Skan break; 789169689Skan 790169689Skan case BIT_FIELD_REF: 791169689Skan /* A bit field reference (access to *multiple* fields simultaneously) 792169689Skan is not currently scalarized. Consider this an access to the 793169689Skan complete outer element, to which walk_tree will bring us next. */ 794169689Skan goto use_all; 795169689Skan 796169689Skan case VIEW_CONVERT_EXPR: 797169689Skan case NOP_EXPR: 798169689Skan /* Similarly, a view/nop explicitly wants to look at an object in a 799169689Skan type other than the one we've scalarized. */ 800169689Skan goto use_all; 801169689Skan 802169689Skan case WITH_SIZE_EXPR: 803169689Skan /* This is a transparent wrapper. The entire inner expression really 804169689Skan is being used. */ 805169689Skan goto use_all; 806169689Skan 807169689Skan use_all: 808169689Skan expr_p = &TREE_OPERAND (inner, 0); 809169689Skan inner = expr = *expr_p; 810169689Skan use_all_p = true; 811169689Skan break; 812169689Skan 813169689Skan default: 814169689Skan#ifdef ENABLE_CHECKING 815169689Skan /* Validate that we're not missing any references. */ 816169689Skan gcc_assert (!walk_tree (&inner, sra_find_candidate_decl, NULL, NULL)); 817169689Skan#endif 818169689Skan return; 819169689Skan } 820169689Skan} 821169689Skan 822169689Skan/* Walk a TREE_LIST of values looking for scalarizable aggregates. 823169689Skan If we find one, invoke FNS->USE. */ 824169689Skan 825169689Skanstatic void 826169689Skansra_walk_tree_list (tree list, block_stmt_iterator *bsi, bool is_output, 827169689Skan const struct sra_walk_fns *fns) 828169689Skan{ 829169689Skan tree op; 830169689Skan for (op = list; op ; op = TREE_CHAIN (op)) 831169689Skan sra_walk_expr (&TREE_VALUE (op), bsi, is_output, fns); 832169689Skan} 833169689Skan 834169689Skan/* Walk the arguments of a CALL_EXPR looking for scalarizable aggregates. 835169689Skan If we find one, invoke FNS->USE. */ 836169689Skan 837169689Skanstatic void 838169689Skansra_walk_call_expr (tree expr, block_stmt_iterator *bsi, 839169689Skan const struct sra_walk_fns *fns) 840169689Skan{ 841169689Skan sra_walk_tree_list (TREE_OPERAND (expr, 1), bsi, false, fns); 842169689Skan} 843169689Skan 844169689Skan/* Walk the inputs and outputs of an ASM_EXPR looking for scalarizable 845169689Skan aggregates. If we find one, invoke FNS->USE. */ 846169689Skan 847169689Skanstatic void 848169689Skansra_walk_asm_expr (tree expr, block_stmt_iterator *bsi, 849169689Skan const struct sra_walk_fns *fns) 850169689Skan{ 851169689Skan sra_walk_tree_list (ASM_INPUTS (expr), bsi, false, fns); 852169689Skan sra_walk_tree_list (ASM_OUTPUTS (expr), bsi, true, fns); 853169689Skan} 854169689Skan 855169689Skan/* Walk a MODIFY_EXPR and categorize the assignment appropriately. */ 856169689Skan 857169689Skanstatic void 858169689Skansra_walk_modify_expr (tree expr, block_stmt_iterator *bsi, 859169689Skan const struct sra_walk_fns *fns) 860169689Skan{ 861169689Skan struct sra_elt *lhs_elt, *rhs_elt; 862169689Skan tree lhs, rhs; 863169689Skan 864169689Skan lhs = TREE_OPERAND (expr, 0); 865169689Skan rhs = TREE_OPERAND (expr, 1); 866169689Skan lhs_elt = maybe_lookup_element_for_expr (lhs); 867169689Skan rhs_elt = maybe_lookup_element_for_expr (rhs); 868169689Skan 869169689Skan /* If both sides are scalarizable, this is a COPY operation. */ 870169689Skan if (lhs_elt && rhs_elt) 871169689Skan { 872169689Skan fns->copy (lhs_elt, rhs_elt, bsi); 873169689Skan return; 874169689Skan } 875169689Skan 876169689Skan /* If the RHS is scalarizable, handle it. There are only two cases. */ 877169689Skan if (rhs_elt) 878169689Skan { 879169689Skan if (!rhs_elt->is_scalar && !TREE_SIDE_EFFECTS (lhs)) 880169689Skan fns->ldst (rhs_elt, lhs, bsi, false); 881169689Skan else 882169689Skan fns->use (rhs_elt, &TREE_OPERAND (expr, 1), bsi, false, false); 883169689Skan } 884169689Skan 885169689Skan /* If it isn't scalarizable, there may be scalarizable variables within, so 886169689Skan check for a call or else walk the RHS to see if we need to do any 887169689Skan copy-in operations. We need to do it before the LHS is scalarized so 888169689Skan that the statements get inserted in the proper place, before any 889169689Skan copy-out operations. */ 890169689Skan else 891169689Skan { 892169689Skan tree call = get_call_expr_in (rhs); 893169689Skan if (call) 894169689Skan sra_walk_call_expr (call, bsi, fns); 895169689Skan else 896169689Skan sra_walk_expr (&TREE_OPERAND (expr, 1), bsi, false, fns); 897169689Skan } 898169689Skan 899169689Skan /* Likewise, handle the LHS being scalarizable. We have cases similar 900169689Skan to those above, but also want to handle RHS being constant. */ 901169689Skan if (lhs_elt) 902169689Skan { 903169689Skan /* If this is an assignment from a constant, or constructor, then 904169689Skan we have access to all of the elements individually. Invoke INIT. */ 905169689Skan if (TREE_CODE (rhs) == COMPLEX_EXPR 906169689Skan || TREE_CODE (rhs) == COMPLEX_CST 907169689Skan || TREE_CODE (rhs) == CONSTRUCTOR) 908169689Skan fns->init (lhs_elt, rhs, bsi); 909169689Skan 910169689Skan /* If this is an assignment from read-only memory, treat this as if 911169689Skan we'd been passed the constructor directly. Invoke INIT. */ 912169689Skan else if (TREE_CODE (rhs) == VAR_DECL 913169689Skan && TREE_STATIC (rhs) 914169689Skan && TREE_READONLY (rhs) 915169689Skan && targetm.binds_local_p (rhs)) 916169689Skan fns->init (lhs_elt, DECL_INITIAL (rhs), bsi); 917169689Skan 918169689Skan /* If this is a copy from a non-scalarizable lvalue, invoke LDST. 919169689Skan The lvalue requirement prevents us from trying to directly scalarize 920169689Skan the result of a function call. Which would result in trying to call 921169689Skan the function multiple times, and other evil things. */ 922169689Skan else if (!lhs_elt->is_scalar 923169689Skan && !TREE_SIDE_EFFECTS (rhs) && is_gimple_addressable (rhs)) 924169689Skan fns->ldst (lhs_elt, rhs, bsi, true); 925169689Skan 926169689Skan /* Otherwise we're being used in some context that requires the 927169689Skan aggregate to be seen as a whole. Invoke USE. */ 928169689Skan else 929169689Skan fns->use (lhs_elt, &TREE_OPERAND (expr, 0), bsi, true, false); 930169689Skan } 931169689Skan 932169689Skan /* Similarly to above, LHS_ELT being null only means that the LHS as a 933169689Skan whole is not a scalarizable reference. There may be occurrences of 934169689Skan scalarizable variables within, which implies a USE. */ 935169689Skan else 936169689Skan sra_walk_expr (&TREE_OPERAND (expr, 0), bsi, true, fns); 937169689Skan} 938169689Skan 939169689Skan/* Entry point to the walk functions. Search the entire function, 940169689Skan invoking the callbacks in FNS on each of the references to 941169689Skan scalarizable variables. */ 942169689Skan 943169689Skanstatic void 944169689Skansra_walk_function (const struct sra_walk_fns *fns) 945169689Skan{ 946169689Skan basic_block bb; 947169689Skan block_stmt_iterator si, ni; 948169689Skan 949169689Skan /* ??? Phase 4 could derive some benefit to walking the function in 950169689Skan dominator tree order. */ 951169689Skan 952169689Skan FOR_EACH_BB (bb) 953169689Skan for (si = bsi_start (bb); !bsi_end_p (si); si = ni) 954169689Skan { 955169689Skan tree stmt, t; 956169689Skan stmt_ann_t ann; 957169689Skan 958169689Skan stmt = bsi_stmt (si); 959169689Skan ann = stmt_ann (stmt); 960169689Skan 961169689Skan ni = si; 962169689Skan bsi_next (&ni); 963169689Skan 964169689Skan /* If the statement has no virtual operands, then it doesn't 965169689Skan make any structure references that we care about. */ 966169689Skan if (ZERO_SSA_OPERANDS (stmt, (SSA_OP_VIRTUAL_DEFS | SSA_OP_VUSE))) 967169689Skan continue; 968169689Skan 969169689Skan switch (TREE_CODE (stmt)) 970169689Skan { 971169689Skan case RETURN_EXPR: 972169689Skan /* If we have "return <retval>" then the return value is 973169689Skan already exposed for our pleasure. Walk it as a USE to 974169689Skan force all the components back in place for the return. 975169689Skan 976169689Skan If we have an embedded assignment, then <retval> is of 977169689Skan a type that gets returned in registers in this ABI, and 978169689Skan we do not wish to extend their lifetimes. Treat this 979169689Skan as a USE of the variable on the RHS of this assignment. */ 980169689Skan 981169689Skan t = TREE_OPERAND (stmt, 0); 982169689Skan if (TREE_CODE (t) == MODIFY_EXPR) 983169689Skan sra_walk_expr (&TREE_OPERAND (t, 1), &si, false, fns); 984169689Skan else 985169689Skan sra_walk_expr (&TREE_OPERAND (stmt, 0), &si, false, fns); 986169689Skan break; 987169689Skan 988169689Skan case MODIFY_EXPR: 989169689Skan sra_walk_modify_expr (stmt, &si, fns); 990169689Skan break; 991169689Skan case CALL_EXPR: 992169689Skan sra_walk_call_expr (stmt, &si, fns); 993169689Skan break; 994169689Skan case ASM_EXPR: 995169689Skan sra_walk_asm_expr (stmt, &si, fns); 996169689Skan break; 997169689Skan 998169689Skan default: 999169689Skan break; 1000169689Skan } 1001169689Skan } 1002169689Skan} 1003169689Skan 1004169689Skan/* Phase One: Scan all referenced variables in the program looking for 1005169689Skan structures that could be decomposed. */ 1006169689Skan 1007169689Skanstatic bool 1008169689Skanfind_candidates_for_sra (void) 1009169689Skan{ 1010169689Skan bool any_set = false; 1011169689Skan tree var; 1012169689Skan referenced_var_iterator rvi; 1013169689Skan 1014169689Skan FOR_EACH_REFERENCED_VAR (var, rvi) 1015169689Skan { 1016169689Skan if (decl_can_be_decomposed_p (var)) 1017169689Skan { 1018169689Skan bitmap_set_bit (sra_candidates, DECL_UID (var)); 1019169689Skan any_set = true; 1020169689Skan } 1021169689Skan } 1022169689Skan 1023169689Skan return any_set; 1024169689Skan} 1025169689Skan 1026169689Skan 1027169689Skan/* Phase Two: Scan all references to scalarizable variables. Count the 1028169689Skan number of times they are used or copied respectively. */ 1029169689Skan 1030169689Skan/* Callbacks to fill in SRA_WALK_FNS. Everything but USE is 1031169689Skan considered a copy, because we can decompose the reference such that 1032169689Skan the sub-elements needn't be contiguous. */ 1033169689Skan 1034169689Skanstatic void 1035169689Skanscan_use (struct sra_elt *elt, tree *expr_p ATTRIBUTE_UNUSED, 1036169689Skan block_stmt_iterator *bsi ATTRIBUTE_UNUSED, 1037169689Skan bool is_output ATTRIBUTE_UNUSED, bool use_all ATTRIBUTE_UNUSED) 1038169689Skan{ 1039169689Skan elt->n_uses += 1; 1040169689Skan} 1041169689Skan 1042169689Skanstatic void 1043169689Skanscan_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt, 1044169689Skan block_stmt_iterator *bsi ATTRIBUTE_UNUSED) 1045169689Skan{ 1046169689Skan lhs_elt->n_copies += 1; 1047169689Skan rhs_elt->n_copies += 1; 1048169689Skan} 1049169689Skan 1050169689Skanstatic void 1051169689Skanscan_init (struct sra_elt *lhs_elt, tree rhs ATTRIBUTE_UNUSED, 1052169689Skan block_stmt_iterator *bsi ATTRIBUTE_UNUSED) 1053169689Skan{ 1054169689Skan lhs_elt->n_copies += 1; 1055169689Skan} 1056169689Skan 1057169689Skanstatic void 1058169689Skanscan_ldst (struct sra_elt *elt, tree other ATTRIBUTE_UNUSED, 1059169689Skan block_stmt_iterator *bsi ATTRIBUTE_UNUSED, 1060169689Skan bool is_output ATTRIBUTE_UNUSED) 1061169689Skan{ 1062169689Skan elt->n_copies += 1; 1063169689Skan} 1064169689Skan 1065169689Skan/* Dump the values we collected during the scanning phase. */ 1066169689Skan 1067169689Skanstatic void 1068169689Skanscan_dump (struct sra_elt *elt) 1069169689Skan{ 1070169689Skan struct sra_elt *c; 1071169689Skan 1072169689Skan dump_sra_elt_name (dump_file, elt); 1073169689Skan fprintf (dump_file, ": n_uses=%u n_copies=%u\n", elt->n_uses, elt->n_copies); 1074169689Skan 1075169689Skan for (c = elt->children; c ; c = c->sibling) 1076169689Skan scan_dump (c); 1077169689Skan 1078169689Skan for (c = elt->groups; c ; c = c->sibling) 1079169689Skan scan_dump (c); 1080169689Skan} 1081169689Skan 1082169689Skan/* Entry point to phase 2. Scan the entire function, building up 1083169689Skan scalarization data structures, recording copies and uses. */ 1084169689Skan 1085169689Skanstatic void 1086169689Skanscan_function (void) 1087169689Skan{ 1088169689Skan static const struct sra_walk_fns fns = { 1089169689Skan scan_use, scan_copy, scan_init, scan_ldst, true 1090169689Skan }; 1091169689Skan bitmap_iterator bi; 1092169689Skan 1093169689Skan sra_walk_function (&fns); 1094169689Skan 1095169689Skan if (dump_file && (dump_flags & TDF_DETAILS)) 1096169689Skan { 1097169689Skan unsigned i; 1098169689Skan 1099169689Skan fputs ("\nScan results:\n", dump_file); 1100169689Skan EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi) 1101169689Skan { 1102169689Skan tree var = referenced_var (i); 1103169689Skan struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT); 1104169689Skan if (elt) 1105169689Skan scan_dump (elt); 1106169689Skan } 1107169689Skan fputc ('\n', dump_file); 1108169689Skan } 1109169689Skan} 1110169689Skan 1111169689Skan/* Phase Three: Make decisions about which variables to scalarize, if any. 1112169689Skan All elements to be scalarized have replacement variables made for them. */ 1113169689Skan 1114169689Skan/* A subroutine of build_element_name. Recursively build the element 1115169689Skan name on the obstack. */ 1116169689Skan 1117169689Skanstatic void 1118169689Skanbuild_element_name_1 (struct sra_elt *elt) 1119169689Skan{ 1120169689Skan tree t; 1121169689Skan char buffer[32]; 1122169689Skan 1123169689Skan if (elt->parent) 1124169689Skan { 1125169689Skan build_element_name_1 (elt->parent); 1126169689Skan obstack_1grow (&sra_obstack, '$'); 1127169689Skan 1128169689Skan if (TREE_CODE (elt->parent->type) == COMPLEX_TYPE) 1129169689Skan { 1130169689Skan if (elt->element == integer_zero_node) 1131169689Skan obstack_grow (&sra_obstack, "real", 4); 1132169689Skan else 1133169689Skan obstack_grow (&sra_obstack, "imag", 4); 1134169689Skan return; 1135169689Skan } 1136169689Skan } 1137169689Skan 1138169689Skan t = elt->element; 1139169689Skan if (TREE_CODE (t) == INTEGER_CST) 1140169689Skan { 1141169689Skan /* ??? Eh. Don't bother doing double-wide printing. */ 1142169689Skan sprintf (buffer, HOST_WIDE_INT_PRINT_DEC, TREE_INT_CST_LOW (t)); 1143169689Skan obstack_grow (&sra_obstack, buffer, strlen (buffer)); 1144169689Skan } 1145169689Skan else 1146169689Skan { 1147169689Skan tree name = DECL_NAME (t); 1148169689Skan if (name) 1149169689Skan obstack_grow (&sra_obstack, IDENTIFIER_POINTER (name), 1150169689Skan IDENTIFIER_LENGTH (name)); 1151169689Skan else 1152169689Skan { 1153169689Skan sprintf (buffer, "D%u", DECL_UID (t)); 1154169689Skan obstack_grow (&sra_obstack, buffer, strlen (buffer)); 1155169689Skan } 1156169689Skan } 1157169689Skan} 1158169689Skan 1159169689Skan/* Construct a pretty variable name for an element's replacement variable. 1160169689Skan The name is built on the obstack. */ 1161169689Skan 1162169689Skanstatic char * 1163169689Skanbuild_element_name (struct sra_elt *elt) 1164169689Skan{ 1165169689Skan build_element_name_1 (elt); 1166169689Skan obstack_1grow (&sra_obstack, '\0'); 1167169689Skan return XOBFINISH (&sra_obstack, char *); 1168169689Skan} 1169169689Skan 1170169689Skan/* Instantiate an element as an independent variable. */ 1171169689Skan 1172169689Skanstatic void 1173169689Skaninstantiate_element (struct sra_elt *elt) 1174169689Skan{ 1175169689Skan struct sra_elt *base_elt; 1176169689Skan tree var, base; 1177169689Skan 1178169689Skan for (base_elt = elt; base_elt->parent; base_elt = base_elt->parent) 1179169689Skan continue; 1180169689Skan base = base_elt->element; 1181169689Skan 1182169689Skan elt->replacement = var = make_rename_temp (elt->type, "SR"); 1183169689Skan DECL_SOURCE_LOCATION (var) = DECL_SOURCE_LOCATION (base); 1184169689Skan DECL_ARTIFICIAL (var) = 1; 1185169689Skan 1186169689Skan if (TREE_THIS_VOLATILE (elt->type)) 1187169689Skan { 1188169689Skan TREE_THIS_VOLATILE (var) = 1; 1189169689Skan TREE_SIDE_EFFECTS (var) = 1; 1190169689Skan } 1191169689Skan 1192169689Skan if (DECL_NAME (base) && !DECL_IGNORED_P (base)) 1193169689Skan { 1194169689Skan char *pretty_name = build_element_name (elt); 1195169689Skan DECL_NAME (var) = get_identifier (pretty_name); 1196169689Skan obstack_free (&sra_obstack, pretty_name); 1197169689Skan 1198169689Skan SET_DECL_DEBUG_EXPR (var, generate_element_ref (elt)); 1199169689Skan DECL_DEBUG_EXPR_IS_FROM (var) = 1; 1200169689Skan 1201169689Skan DECL_IGNORED_P (var) = 0; 1202169689Skan TREE_NO_WARNING (var) = TREE_NO_WARNING (base); 1203169689Skan } 1204169689Skan else 1205169689Skan { 1206169689Skan DECL_IGNORED_P (var) = 1; 1207169689Skan /* ??? We can't generate any warning that would be meaningful. */ 1208169689Skan TREE_NO_WARNING (var) = 1; 1209169689Skan } 1210169689Skan 1211169689Skan if (dump_file) 1212169689Skan { 1213169689Skan fputs (" ", dump_file); 1214169689Skan dump_sra_elt_name (dump_file, elt); 1215169689Skan fputs (" -> ", dump_file); 1216169689Skan print_generic_expr (dump_file, var, dump_flags); 1217169689Skan fputc ('\n', dump_file); 1218169689Skan } 1219169689Skan} 1220169689Skan 1221169689Skan/* Make one pass across an element tree deciding whether or not it's 1222169689Skan profitable to instantiate individual leaf scalars. 1223169689Skan 1224169689Skan PARENT_USES and PARENT_COPIES are the sum of the N_USES and N_COPIES 1225169689Skan fields all the way up the tree. */ 1226169689Skan 1227169689Skanstatic void 1228169689Skandecide_instantiation_1 (struct sra_elt *elt, unsigned int parent_uses, 1229169689Skan unsigned int parent_copies) 1230169689Skan{ 1231169689Skan if (dump_file && !elt->parent) 1232169689Skan { 1233169689Skan fputs ("Initial instantiation for ", dump_file); 1234169689Skan dump_sra_elt_name (dump_file, elt); 1235169689Skan fputc ('\n', dump_file); 1236169689Skan } 1237169689Skan 1238169689Skan if (elt->cannot_scalarize) 1239169689Skan return; 1240169689Skan 1241169689Skan if (elt->is_scalar) 1242169689Skan { 1243169689Skan /* The decision is simple: instantiate if we're used more frequently 1244169689Skan than the parent needs to be seen as a complete unit. */ 1245169689Skan if (elt->n_uses + elt->n_copies + parent_copies > parent_uses) 1246169689Skan instantiate_element (elt); 1247169689Skan } 1248169689Skan else 1249169689Skan { 1250169689Skan struct sra_elt *c, *group; 1251169689Skan unsigned int this_uses = elt->n_uses + parent_uses; 1252169689Skan unsigned int this_copies = elt->n_copies + parent_copies; 1253169689Skan 1254169689Skan /* Consider groups of sub-elements as weighing in favour of 1255169689Skan instantiation whatever their size. */ 1256169689Skan for (group = elt->groups; group ; group = group->sibling) 1257169689Skan FOR_EACH_ACTUAL_CHILD (c, group) 1258169689Skan { 1259169689Skan c->n_uses += group->n_uses; 1260169689Skan c->n_copies += group->n_copies; 1261169689Skan } 1262169689Skan 1263169689Skan for (c = elt->children; c ; c = c->sibling) 1264169689Skan decide_instantiation_1 (c, this_uses, this_copies); 1265169689Skan } 1266169689Skan} 1267169689Skan 1268169689Skan/* Compute the size and number of all instantiated elements below ELT. 1269169689Skan We will only care about this if the size of the complete structure 1270169689Skan fits in a HOST_WIDE_INT, so we don't have to worry about overflow. */ 1271169689Skan 1272169689Skanstatic unsigned int 1273169689Skansum_instantiated_sizes (struct sra_elt *elt, unsigned HOST_WIDE_INT *sizep) 1274169689Skan{ 1275169689Skan if (elt->replacement) 1276169689Skan { 1277169689Skan *sizep += TREE_INT_CST_LOW (TYPE_SIZE_UNIT (elt->type)); 1278169689Skan return 1; 1279169689Skan } 1280169689Skan else 1281169689Skan { 1282169689Skan struct sra_elt *c; 1283169689Skan unsigned int count = 0; 1284169689Skan 1285169689Skan for (c = elt->children; c ; c = c->sibling) 1286169689Skan count += sum_instantiated_sizes (c, sizep); 1287169689Skan 1288169689Skan return count; 1289169689Skan } 1290169689Skan} 1291169689Skan 1292169689Skan/* Instantiate fields in ELT->TYPE that are not currently present as 1293169689Skan children of ELT. */ 1294169689Skan 1295169689Skanstatic void instantiate_missing_elements (struct sra_elt *elt); 1296169689Skan 1297169689Skanstatic void 1298169689Skaninstantiate_missing_elements_1 (struct sra_elt *elt, tree child, tree type) 1299169689Skan{ 1300169689Skan struct sra_elt *sub = lookup_element (elt, child, type, INSERT); 1301169689Skan if (sub->is_scalar) 1302169689Skan { 1303169689Skan if (sub->replacement == NULL) 1304169689Skan instantiate_element (sub); 1305169689Skan } 1306169689Skan else 1307169689Skan instantiate_missing_elements (sub); 1308169689Skan} 1309169689Skan 1310169689Skanstatic void 1311169689Skaninstantiate_missing_elements (struct sra_elt *elt) 1312169689Skan{ 1313169689Skan tree type = elt->type; 1314169689Skan 1315169689Skan switch (TREE_CODE (type)) 1316169689Skan { 1317169689Skan case RECORD_TYPE: 1318169689Skan { 1319169689Skan tree f; 1320169689Skan for (f = TYPE_FIELDS (type); f ; f = TREE_CHAIN (f)) 1321169689Skan if (TREE_CODE (f) == FIELD_DECL) 1322169689Skan { 1323169689Skan tree field_type = TREE_TYPE (f); 1324169689Skan 1325169689Skan /* canonicalize_component_ref() unwidens some bit-field 1326169689Skan types (not marked as DECL_BIT_FIELD in C++), so we 1327169689Skan must do the same, lest we may introduce type 1328169689Skan mismatches. */ 1329169689Skan if (INTEGRAL_TYPE_P (field_type) 1330169689Skan && DECL_MODE (f) != TYPE_MODE (field_type)) 1331169689Skan field_type = TREE_TYPE (get_unwidened (build3 (COMPONENT_REF, 1332169689Skan field_type, 1333169689Skan elt->element, 1334169689Skan f, NULL_TREE), 1335169689Skan NULL_TREE)); 1336169689Skan 1337169689Skan instantiate_missing_elements_1 (elt, f, field_type); 1338169689Skan } 1339169689Skan break; 1340169689Skan } 1341169689Skan 1342169689Skan case ARRAY_TYPE: 1343169689Skan { 1344169689Skan tree i, max, subtype; 1345169689Skan 1346169689Skan i = TYPE_MIN_VALUE (TYPE_DOMAIN (type)); 1347169689Skan max = TYPE_MAX_VALUE (TYPE_DOMAIN (type)); 1348169689Skan subtype = TREE_TYPE (type); 1349169689Skan 1350169689Skan while (1) 1351169689Skan { 1352169689Skan instantiate_missing_elements_1 (elt, i, subtype); 1353169689Skan if (tree_int_cst_equal (i, max)) 1354169689Skan break; 1355169689Skan i = int_const_binop (PLUS_EXPR, i, integer_one_node, true); 1356169689Skan } 1357169689Skan 1358169689Skan break; 1359169689Skan } 1360169689Skan 1361169689Skan case COMPLEX_TYPE: 1362169689Skan type = TREE_TYPE (type); 1363169689Skan instantiate_missing_elements_1 (elt, integer_zero_node, type); 1364169689Skan instantiate_missing_elements_1 (elt, integer_one_node, type); 1365169689Skan break; 1366169689Skan 1367169689Skan default: 1368169689Skan gcc_unreachable (); 1369169689Skan } 1370169689Skan} 1371169689Skan 1372169689Skan/* Make one pass across an element tree deciding whether to perform block 1373169689Skan or element copies. If we decide on element copies, instantiate all 1374169689Skan elements. Return true if there are any instantiated sub-elements. */ 1375169689Skan 1376169689Skanstatic bool 1377169689Skandecide_block_copy (struct sra_elt *elt) 1378169689Skan{ 1379169689Skan struct sra_elt *c; 1380169689Skan bool any_inst; 1381169689Skan 1382169689Skan /* We shouldn't be invoked on groups of sub-elements as they must 1383169689Skan behave like their parent as far as block copy is concerned. */ 1384169689Skan gcc_assert (!elt->is_group); 1385169689Skan 1386169689Skan /* If scalarization is disabled, respect it. */ 1387169689Skan if (elt->cannot_scalarize) 1388169689Skan { 1389169689Skan elt->use_block_copy = 1; 1390169689Skan 1391169689Skan if (dump_file) 1392169689Skan { 1393169689Skan fputs ("Scalarization disabled for ", dump_file); 1394169689Skan dump_sra_elt_name (dump_file, elt); 1395169689Skan fputc ('\n', dump_file); 1396169689Skan } 1397169689Skan 1398169689Skan /* Disable scalarization of sub-elements */ 1399169689Skan for (c = elt->children; c; c = c->sibling) 1400169689Skan { 1401169689Skan c->cannot_scalarize = 1; 1402169689Skan decide_block_copy (c); 1403169689Skan } 1404169689Skan 1405169689Skan /* Groups behave like their parent. */ 1406169689Skan for (c = elt->groups; c; c = c->sibling) 1407169689Skan { 1408169689Skan c->cannot_scalarize = 1; 1409169689Skan c->use_block_copy = 1; 1410169689Skan } 1411169689Skan 1412169689Skan return false; 1413169689Skan } 1414169689Skan 1415169689Skan /* Don't decide if we've no uses. */ 1416169689Skan if (elt->n_uses == 0 && elt->n_copies == 0) 1417169689Skan ; 1418169689Skan 1419169689Skan else if (!elt->is_scalar) 1420169689Skan { 1421169689Skan tree size_tree = TYPE_SIZE_UNIT (elt->type); 1422169689Skan bool use_block_copy = true; 1423169689Skan 1424169689Skan /* Tradeoffs for COMPLEX types pretty much always make it better 1425169689Skan to go ahead and split the components. */ 1426169689Skan if (TREE_CODE (elt->type) == COMPLEX_TYPE) 1427169689Skan use_block_copy = false; 1428169689Skan 1429169689Skan /* Don't bother trying to figure out the rest if the structure is 1430169689Skan so large we can't do easy arithmetic. This also forces block 1431169689Skan copies for variable sized structures. */ 1432169689Skan else if (host_integerp (size_tree, 1)) 1433169689Skan { 1434169689Skan unsigned HOST_WIDE_INT full_size, inst_size = 0; 1435169689Skan unsigned int max_size, max_count, inst_count, full_count; 1436169689Skan 1437169689Skan /* If the sra-max-structure-size parameter is 0, then the 1438169689Skan user has not overridden the parameter and we can choose a 1439169689Skan sensible default. */ 1440169689Skan max_size = SRA_MAX_STRUCTURE_SIZE 1441169689Skan ? SRA_MAX_STRUCTURE_SIZE 1442169689Skan : MOVE_RATIO * UNITS_PER_WORD; 1443169689Skan max_count = SRA_MAX_STRUCTURE_COUNT 1444169689Skan ? SRA_MAX_STRUCTURE_COUNT 1445169689Skan : MOVE_RATIO; 1446169689Skan 1447169689Skan full_size = tree_low_cst (size_tree, 1); 1448169689Skan full_count = count_type_elements (elt->type, false); 1449169689Skan inst_count = sum_instantiated_sizes (elt, &inst_size); 1450169689Skan 1451169689Skan /* ??? What to do here. If there are two fields, and we've only 1452169689Skan instantiated one, then instantiating the other is clearly a win. 1453169689Skan If there are a large number of fields then the size of the copy 1454169689Skan is much more of a factor. */ 1455169689Skan 1456169689Skan /* If the structure is small, and we've made copies, go ahead 1457169689Skan and instantiate, hoping that the copies will go away. */ 1458169689Skan if (full_size <= max_size 1459169689Skan && (full_count - inst_count) <= max_count 1460169689Skan && elt->n_copies > elt->n_uses) 1461169689Skan use_block_copy = false; 1462169689Skan else if (inst_count * 100 >= full_count * SRA_FIELD_STRUCTURE_RATIO 1463169689Skan && inst_size * 100 >= full_size * SRA_FIELD_STRUCTURE_RATIO) 1464169689Skan use_block_copy = false; 1465169689Skan 1466169689Skan /* In order to avoid block copy, we have to be able to instantiate 1467169689Skan all elements of the type. See if this is possible. */ 1468169689Skan if (!use_block_copy 1469169689Skan && (!can_completely_scalarize_p (elt) 1470169689Skan || !type_can_instantiate_all_elements (elt->type))) 1471169689Skan use_block_copy = true; 1472169689Skan } 1473169689Skan 1474169689Skan elt->use_block_copy = use_block_copy; 1475169689Skan 1476169689Skan /* Groups behave like their parent. */ 1477169689Skan for (c = elt->groups; c; c = c->sibling) 1478169689Skan c->use_block_copy = use_block_copy; 1479169689Skan 1480169689Skan if (dump_file) 1481169689Skan { 1482169689Skan fprintf (dump_file, "Using %s for ", 1483169689Skan use_block_copy ? "block-copy" : "element-copy"); 1484169689Skan dump_sra_elt_name (dump_file, elt); 1485169689Skan fputc ('\n', dump_file); 1486169689Skan } 1487169689Skan 1488169689Skan if (!use_block_copy) 1489169689Skan { 1490169689Skan instantiate_missing_elements (elt); 1491169689Skan return true; 1492169689Skan } 1493169689Skan } 1494169689Skan 1495169689Skan any_inst = elt->replacement != NULL; 1496169689Skan 1497169689Skan for (c = elt->children; c ; c = c->sibling) 1498169689Skan any_inst |= decide_block_copy (c); 1499169689Skan 1500169689Skan return any_inst; 1501169689Skan} 1502169689Skan 1503169689Skan/* Entry point to phase 3. Instantiate scalar replacement variables. */ 1504169689Skan 1505169689Skanstatic void 1506169689Skandecide_instantiations (void) 1507169689Skan{ 1508169689Skan unsigned int i; 1509169689Skan bool cleared_any; 1510169689Skan bitmap_head done_head; 1511169689Skan bitmap_iterator bi; 1512169689Skan 1513169689Skan /* We cannot clear bits from a bitmap we're iterating over, 1514169689Skan so save up all the bits to clear until the end. */ 1515169689Skan bitmap_initialize (&done_head, &bitmap_default_obstack); 1516169689Skan cleared_any = false; 1517169689Skan 1518169689Skan EXECUTE_IF_SET_IN_BITMAP (sra_candidates, 0, i, bi) 1519169689Skan { 1520169689Skan tree var = referenced_var (i); 1521169689Skan struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT); 1522169689Skan if (elt) 1523169689Skan { 1524169689Skan decide_instantiation_1 (elt, 0, 0); 1525169689Skan if (!decide_block_copy (elt)) 1526169689Skan elt = NULL; 1527169689Skan } 1528169689Skan if (!elt) 1529169689Skan { 1530169689Skan bitmap_set_bit (&done_head, i); 1531169689Skan cleared_any = true; 1532169689Skan } 1533169689Skan } 1534169689Skan 1535169689Skan if (cleared_any) 1536169689Skan { 1537169689Skan bitmap_and_compl_into (sra_candidates, &done_head); 1538169689Skan bitmap_and_compl_into (needs_copy_in, &done_head); 1539169689Skan } 1540169689Skan bitmap_clear (&done_head); 1541169689Skan 1542169689Skan if (!bitmap_empty_p (sra_candidates)) 1543169689Skan todoflags |= TODO_update_smt_usage; 1544169689Skan 1545169689Skan mark_set_for_renaming (sra_candidates); 1546169689Skan 1547169689Skan if (dump_file) 1548169689Skan fputc ('\n', dump_file); 1549169689Skan} 1550169689Skan 1551169689Skan 1552169689Skan/* Phase Four: Update the function to match the replacements created. */ 1553169689Skan 1554169689Skan/* Mark all the variables in V_MAY_DEF or V_MUST_DEF operands for STMT for 1555169689Skan renaming. This becomes necessary when we modify all of a non-scalar. */ 1556169689Skan 1557169689Skanstatic void 1558169689Skanmark_all_v_defs_1 (tree stmt) 1559169689Skan{ 1560169689Skan tree sym; 1561169689Skan ssa_op_iter iter; 1562169689Skan 1563169689Skan update_stmt_if_modified (stmt); 1564169689Skan 1565169689Skan FOR_EACH_SSA_TREE_OPERAND (sym, stmt, iter, SSA_OP_ALL_VIRTUALS) 1566169689Skan { 1567169689Skan if (TREE_CODE (sym) == SSA_NAME) 1568169689Skan sym = SSA_NAME_VAR (sym); 1569169689Skan mark_sym_for_renaming (sym); 1570169689Skan } 1571169689Skan} 1572169689Skan 1573169689Skan 1574169689Skan/* Mark all the variables in virtual operands in all the statements in 1575169689Skan LIST for renaming. */ 1576169689Skan 1577169689Skanstatic void 1578169689Skanmark_all_v_defs (tree list) 1579169689Skan{ 1580169689Skan if (TREE_CODE (list) != STATEMENT_LIST) 1581169689Skan mark_all_v_defs_1 (list); 1582169689Skan else 1583169689Skan { 1584169689Skan tree_stmt_iterator i; 1585169689Skan for (i = tsi_start (list); !tsi_end_p (i); tsi_next (&i)) 1586169689Skan mark_all_v_defs_1 (tsi_stmt (i)); 1587169689Skan } 1588169689Skan} 1589169689Skan 1590169689Skan/* Mark every replacement under ELT with TREE_NO_WARNING. */ 1591169689Skan 1592169689Skanstatic void 1593169689Skanmark_no_warning (struct sra_elt *elt) 1594169689Skan{ 1595169689Skan if (!elt->all_no_warning) 1596169689Skan { 1597169689Skan if (elt->replacement) 1598169689Skan TREE_NO_WARNING (elt->replacement) = 1; 1599169689Skan else 1600169689Skan { 1601169689Skan struct sra_elt *c; 1602169689Skan FOR_EACH_ACTUAL_CHILD (c, elt) 1603169689Skan mark_no_warning (c); 1604169689Skan } 1605169689Skan elt->all_no_warning = true; 1606169689Skan } 1607169689Skan} 1608169689Skan 1609169689Skan/* Build a single level component reference to ELT rooted at BASE. */ 1610169689Skan 1611169689Skanstatic tree 1612169689Skangenerate_one_element_ref (struct sra_elt *elt, tree base) 1613169689Skan{ 1614169689Skan switch (TREE_CODE (TREE_TYPE (base))) 1615169689Skan { 1616169689Skan case RECORD_TYPE: 1617169689Skan { 1618169689Skan tree field = elt->element; 1619169689Skan 1620169689Skan /* Watch out for compatible records with differing field lists. */ 1621169689Skan if (DECL_FIELD_CONTEXT (field) != TYPE_MAIN_VARIANT (TREE_TYPE (base))) 1622169689Skan field = find_compatible_field (TREE_TYPE (base), field); 1623169689Skan 1624169689Skan return build3 (COMPONENT_REF, elt->type, base, field, NULL); 1625169689Skan } 1626169689Skan 1627169689Skan case ARRAY_TYPE: 1628169689Skan todoflags |= TODO_update_smt_usage; 1629169689Skan if (TREE_CODE (elt->element) == RANGE_EXPR) 1630169689Skan return build4 (ARRAY_RANGE_REF, elt->type, base, 1631169689Skan TREE_OPERAND (elt->element, 0), NULL, NULL); 1632169689Skan else 1633169689Skan return build4 (ARRAY_REF, elt->type, base, elt->element, NULL, NULL); 1634169689Skan 1635169689Skan case COMPLEX_TYPE: 1636169689Skan if (elt->element == integer_zero_node) 1637169689Skan return build1 (REALPART_EXPR, elt->type, base); 1638169689Skan else 1639169689Skan return build1 (IMAGPART_EXPR, elt->type, base); 1640169689Skan 1641169689Skan default: 1642169689Skan gcc_unreachable (); 1643169689Skan } 1644169689Skan} 1645169689Skan 1646169689Skan/* Build a full component reference to ELT rooted at its native variable. */ 1647169689Skan 1648169689Skanstatic tree 1649169689Skangenerate_element_ref (struct sra_elt *elt) 1650169689Skan{ 1651169689Skan if (elt->parent) 1652169689Skan return generate_one_element_ref (elt, generate_element_ref (elt->parent)); 1653169689Skan else 1654169689Skan return elt->element; 1655169689Skan} 1656169689Skan 1657169689Skanstatic tree 1658169689Skansra_build_assignment (tree dst, tree src) 1659169689Skan{ 1660169689Skan /* We need TYPE_CANONICAL to compare the types of dst and src 1661169689Skan efficiently, but that's only introduced in GCC 4.3. */ 1662169689Skan return build2 (MODIFY_EXPR, void_type_node, dst, src); 1663169689Skan} 1664169689Skan 1665169689Skan/* Generate a set of assignment statements in *LIST_P to copy all 1666169689Skan instantiated elements under ELT to or from the equivalent structure 1667169689Skan rooted at EXPR. COPY_OUT controls the direction of the copy, with 1668169689Skan true meaning to copy out of EXPR into ELT. */ 1669169689Skan 1670169689Skanstatic void 1671169689Skangenerate_copy_inout (struct sra_elt *elt, bool copy_out, tree expr, 1672169689Skan tree *list_p) 1673169689Skan{ 1674169689Skan struct sra_elt *c; 1675169689Skan tree t; 1676169689Skan 1677169689Skan if (!copy_out && TREE_CODE (expr) == SSA_NAME 1678169689Skan && TREE_CODE (TREE_TYPE (expr)) == COMPLEX_TYPE) 1679169689Skan { 1680169689Skan tree r, i; 1681169689Skan 1682169689Skan c = lookup_element (elt, integer_zero_node, NULL, NO_INSERT); 1683169689Skan r = c->replacement; 1684169689Skan c = lookup_element (elt, integer_one_node, NULL, NO_INSERT); 1685169689Skan i = c->replacement; 1686169689Skan 1687169689Skan t = build2 (COMPLEX_EXPR, elt->type, r, i); 1688169689Skan t = sra_build_assignment (expr, t); 1689169689Skan SSA_NAME_DEF_STMT (expr) = t; 1690169689Skan append_to_statement_list (t, list_p); 1691169689Skan } 1692169689Skan else if (elt->replacement) 1693169689Skan { 1694169689Skan if (copy_out) 1695169689Skan t = sra_build_assignment (elt->replacement, expr); 1696169689Skan else 1697169689Skan t = sra_build_assignment (expr, elt->replacement); 1698169689Skan append_to_statement_list (t, list_p); 1699169689Skan } 1700169689Skan else 1701169689Skan { 1702169689Skan FOR_EACH_ACTUAL_CHILD (c, elt) 1703169689Skan { 1704169689Skan t = generate_one_element_ref (c, unshare_expr (expr)); 1705169689Skan generate_copy_inout (c, copy_out, t, list_p); 1706169689Skan } 1707169689Skan } 1708169689Skan} 1709169689Skan 1710169689Skan/* Generate a set of assignment statements in *LIST_P to copy all instantiated 1711169689Skan elements under SRC to their counterparts under DST. There must be a 1-1 1712169689Skan correspondence of instantiated elements. */ 1713169689Skan 1714169689Skanstatic void 1715169689Skangenerate_element_copy (struct sra_elt *dst, struct sra_elt *src, tree *list_p) 1716169689Skan{ 1717169689Skan struct sra_elt *dc, *sc; 1718169689Skan 1719169689Skan FOR_EACH_ACTUAL_CHILD (dc, dst) 1720169689Skan { 1721169689Skan sc = lookup_element (src, dc->element, NULL, NO_INSERT); 1722169689Skan gcc_assert (sc); 1723169689Skan generate_element_copy (dc, sc, list_p); 1724169689Skan } 1725169689Skan 1726169689Skan if (dst->replacement) 1727169689Skan { 1728169689Skan tree t; 1729169689Skan 1730169689Skan gcc_assert (src->replacement); 1731169689Skan 1732169689Skan t = sra_build_assignment (dst->replacement, src->replacement); 1733169689Skan append_to_statement_list (t, list_p); 1734169689Skan } 1735169689Skan} 1736169689Skan 1737169689Skan/* Generate a set of assignment statements in *LIST_P to zero all instantiated 1738169689Skan elements under ELT. In addition, do not assign to elements that have been 1739169689Skan marked VISITED but do reset the visited flag; this allows easy coordination 1740169689Skan with generate_element_init. */ 1741169689Skan 1742169689Skanstatic void 1743169689Skangenerate_element_zero (struct sra_elt *elt, tree *list_p) 1744169689Skan{ 1745169689Skan struct sra_elt *c; 1746169689Skan 1747169689Skan if (elt->visited) 1748169689Skan { 1749169689Skan elt->visited = false; 1750169689Skan return; 1751169689Skan } 1752169689Skan 1753169689Skan FOR_EACH_ACTUAL_CHILD (c, elt) 1754169689Skan generate_element_zero (c, list_p); 1755169689Skan 1756169689Skan if (elt->replacement) 1757169689Skan { 1758169689Skan tree t; 1759169689Skan 1760169689Skan gcc_assert (elt->is_scalar); 1761169689Skan t = fold_convert (elt->type, integer_zero_node); 1762169689Skan 1763169689Skan t = sra_build_assignment (elt->replacement, t); 1764169689Skan append_to_statement_list (t, list_p); 1765169689Skan } 1766169689Skan} 1767169689Skan 1768169689Skan/* Generate an assignment VAR = INIT, where INIT may need gimplification. 1769169689Skan Add the result to *LIST_P. */ 1770169689Skan 1771169689Skanstatic void 1772169689Skangenerate_one_element_init (tree var, tree init, tree *list_p) 1773169689Skan{ 1774169689Skan /* The replacement can be almost arbitrarily complex. Gimplify. */ 1775169689Skan tree stmt = sra_build_assignment (var, init); 1776169689Skan gimplify_and_add (stmt, list_p); 1777169689Skan} 1778169689Skan 1779169689Skan/* Generate a set of assignment statements in *LIST_P to set all instantiated 1780169689Skan elements under ELT with the contents of the initializer INIT. In addition, 1781169689Skan mark all assigned elements VISITED; this allows easy coordination with 1782169689Skan generate_element_zero. Return false if we found a case we couldn't 1783169689Skan handle. */ 1784169689Skan 1785169689Skanstatic bool 1786169689Skangenerate_element_init_1 (struct sra_elt *elt, tree init, tree *list_p) 1787169689Skan{ 1788169689Skan bool result = true; 1789169689Skan enum tree_code init_code; 1790169689Skan struct sra_elt *sub; 1791169689Skan tree t; 1792169689Skan unsigned HOST_WIDE_INT idx; 1793169689Skan tree value, purpose; 1794169689Skan 1795169689Skan /* We can be passed DECL_INITIAL of a static variable. It might have a 1796169689Skan conversion, which we strip off here. */ 1797169689Skan STRIP_USELESS_TYPE_CONVERSION (init); 1798169689Skan init_code = TREE_CODE (init); 1799169689Skan 1800169689Skan if (elt->is_scalar) 1801169689Skan { 1802169689Skan if (elt->replacement) 1803169689Skan { 1804169689Skan generate_one_element_init (elt->replacement, init, list_p); 1805169689Skan elt->visited = true; 1806169689Skan } 1807169689Skan return result; 1808169689Skan } 1809169689Skan 1810169689Skan switch (init_code) 1811169689Skan { 1812169689Skan case COMPLEX_CST: 1813169689Skan case COMPLEX_EXPR: 1814169689Skan FOR_EACH_ACTUAL_CHILD (sub, elt) 1815169689Skan { 1816169689Skan if (sub->element == integer_zero_node) 1817169689Skan t = (init_code == COMPLEX_EXPR 1818169689Skan ? TREE_OPERAND (init, 0) : TREE_REALPART (init)); 1819169689Skan else 1820169689Skan t = (init_code == COMPLEX_EXPR 1821169689Skan ? TREE_OPERAND (init, 1) : TREE_IMAGPART (init)); 1822169689Skan result &= generate_element_init_1 (sub, t, list_p); 1823169689Skan } 1824169689Skan break; 1825169689Skan 1826169689Skan case CONSTRUCTOR: 1827169689Skan FOR_EACH_CONSTRUCTOR_ELT (CONSTRUCTOR_ELTS (init), idx, purpose, value) 1828169689Skan { 1829169689Skan if (TREE_CODE (purpose) == RANGE_EXPR) 1830169689Skan { 1831169689Skan tree lower = TREE_OPERAND (purpose, 0); 1832169689Skan tree upper = TREE_OPERAND (purpose, 1); 1833169689Skan 1834169689Skan while (1) 1835169689Skan { 1836169689Skan sub = lookup_element (elt, lower, NULL, NO_INSERT); 1837169689Skan if (sub != NULL) 1838169689Skan result &= generate_element_init_1 (sub, value, list_p); 1839169689Skan if (tree_int_cst_equal (lower, upper)) 1840169689Skan break; 1841169689Skan lower = int_const_binop (PLUS_EXPR, lower, 1842169689Skan integer_one_node, true); 1843169689Skan } 1844169689Skan } 1845169689Skan else 1846169689Skan { 1847169689Skan sub = lookup_element (elt, purpose, NULL, NO_INSERT); 1848169689Skan if (sub != NULL) 1849169689Skan result &= generate_element_init_1 (sub, value, list_p); 1850169689Skan } 1851169689Skan } 1852169689Skan break; 1853169689Skan 1854169689Skan default: 1855169689Skan elt->visited = true; 1856169689Skan result = false; 1857169689Skan } 1858169689Skan 1859169689Skan return result; 1860169689Skan} 1861169689Skan 1862169689Skan/* A wrapper function for generate_element_init_1 that handles cleanup after 1863169689Skan gimplification. */ 1864169689Skan 1865169689Skanstatic bool 1866169689Skangenerate_element_init (struct sra_elt *elt, tree init, tree *list_p) 1867169689Skan{ 1868169689Skan bool ret; 1869169689Skan 1870169689Skan push_gimplify_context (); 1871169689Skan ret = generate_element_init_1 (elt, init, list_p); 1872169689Skan pop_gimplify_context (NULL); 1873169689Skan 1874169689Skan /* The replacement can expose previously unreferenced variables. */ 1875169689Skan if (ret && *list_p) 1876169689Skan { 1877169689Skan tree_stmt_iterator i; 1878169689Skan 1879169689Skan for (i = tsi_start (*list_p); !tsi_end_p (i); tsi_next (&i)) 1880169689Skan find_new_referenced_vars (tsi_stmt_ptr (i)); 1881169689Skan } 1882169689Skan 1883169689Skan return ret; 1884169689Skan} 1885169689Skan 1886169689Skan/* Insert STMT on all the outgoing edges out of BB. Note that if BB 1887169689Skan has more than one edge, STMT will be replicated for each edge. Also, 1888169689Skan abnormal edges will be ignored. */ 1889169689Skan 1890169689Skanvoid 1891169689Skaninsert_edge_copies (tree stmt, basic_block bb) 1892169689Skan{ 1893169689Skan edge e; 1894169689Skan edge_iterator ei; 1895169689Skan bool first_copy; 1896169689Skan 1897169689Skan first_copy = true; 1898169689Skan FOR_EACH_EDGE (e, ei, bb->succs) 1899169689Skan { 1900169689Skan /* We don't need to insert copies on abnormal edges. The 1901169689Skan value of the scalar replacement is not guaranteed to 1902169689Skan be valid through an abnormal edge. */ 1903169689Skan if (!(e->flags & EDGE_ABNORMAL)) 1904169689Skan { 1905169689Skan if (first_copy) 1906169689Skan { 1907169689Skan bsi_insert_on_edge (e, stmt); 1908169689Skan first_copy = false; 1909169689Skan } 1910169689Skan else 1911169689Skan bsi_insert_on_edge (e, unsave_expr_now (stmt)); 1912169689Skan } 1913169689Skan } 1914169689Skan} 1915169689Skan 1916169689Skan/* Helper function to insert LIST before BSI, and set up line number info. */ 1917169689Skan 1918169689Skanvoid 1919169689Skansra_insert_before (block_stmt_iterator *bsi, tree list) 1920169689Skan{ 1921169689Skan tree stmt = bsi_stmt (*bsi); 1922169689Skan 1923169689Skan if (EXPR_HAS_LOCATION (stmt)) 1924169689Skan annotate_all_with_locus (&list, EXPR_LOCATION (stmt)); 1925169689Skan bsi_insert_before (bsi, list, BSI_SAME_STMT); 1926169689Skan} 1927169689Skan 1928169689Skan/* Similarly, but insert after BSI. Handles insertion onto edges as well. */ 1929169689Skan 1930169689Skanvoid 1931169689Skansra_insert_after (block_stmt_iterator *bsi, tree list) 1932169689Skan{ 1933169689Skan tree stmt = bsi_stmt (*bsi); 1934169689Skan 1935169689Skan if (EXPR_HAS_LOCATION (stmt)) 1936169689Skan annotate_all_with_locus (&list, EXPR_LOCATION (stmt)); 1937169689Skan 1938169689Skan if (stmt_ends_bb_p (stmt)) 1939169689Skan insert_edge_copies (list, bsi->bb); 1940169689Skan else 1941169689Skan bsi_insert_after (bsi, list, BSI_SAME_STMT); 1942169689Skan} 1943169689Skan 1944169689Skan/* Similarly, but replace the statement at BSI. */ 1945169689Skan 1946169689Skanstatic void 1947169689Skansra_replace (block_stmt_iterator *bsi, tree list) 1948169689Skan{ 1949169689Skan sra_insert_before (bsi, list); 1950169689Skan bsi_remove (bsi, false); 1951169689Skan if (bsi_end_p (*bsi)) 1952169689Skan *bsi = bsi_last (bsi->bb); 1953169689Skan else 1954169689Skan bsi_prev (bsi); 1955169689Skan} 1956169689Skan 1957169689Skan/* Scalarize a USE. To recap, this is either a simple reference to ELT, 1958169689Skan if elt is scalar, or some occurrence of ELT that requires a complete 1959169689Skan aggregate. IS_OUTPUT is true if ELT is being modified. */ 1960169689Skan 1961169689Skanstatic void 1962169689Skanscalarize_use (struct sra_elt *elt, tree *expr_p, block_stmt_iterator *bsi, 1963169689Skan bool is_output, bool use_all) 1964169689Skan{ 1965169689Skan tree list = NULL, stmt = bsi_stmt (*bsi); 1966169689Skan 1967169689Skan if (elt->replacement) 1968169689Skan { 1969169689Skan /* If we have a replacement, then updating the reference is as 1970169689Skan simple as modifying the existing statement in place. */ 1971169689Skan if (is_output) 1972169689Skan mark_all_v_defs (stmt); 1973169689Skan *expr_p = elt->replacement; 1974169689Skan update_stmt (stmt); 1975169689Skan } 1976169689Skan else 1977169689Skan { 1978169689Skan /* Otherwise we need some copies. If ELT is being read, then we want 1979169689Skan to store all (modified) sub-elements back into the structure before 1980169689Skan the reference takes place. If ELT is being written, then we want to 1981169689Skan load the changed values back into our shadow variables. */ 1982169689Skan /* ??? We don't check modified for reads, we just always write all of 1983169689Skan the values. We should be able to record the SSA number of the VOP 1984169689Skan for which the values were last read. If that number matches the 1985169689Skan SSA number of the VOP in the current statement, then we needn't 1986169689Skan emit an assignment. This would also eliminate double writes when 1987169689Skan a structure is passed as more than one argument to a function call. 1988169689Skan This optimization would be most effective if sra_walk_function 1989169689Skan processed the blocks in dominator order. */ 1990169689Skan 1991169689Skan generate_copy_inout (elt, is_output, generate_element_ref (elt), &list); 1992169689Skan if (list == NULL) 1993169689Skan return; 1994169689Skan mark_all_v_defs (list); 1995169689Skan if (is_output) 1996169689Skan sra_insert_after (bsi, list); 1997169689Skan else 1998169689Skan { 1999169689Skan sra_insert_before (bsi, list); 2000169689Skan if (use_all) 2001169689Skan mark_no_warning (elt); 2002169689Skan } 2003169689Skan } 2004169689Skan} 2005169689Skan 2006169689Skan/* Scalarize a COPY. To recap, this is an assignment statement between 2007169689Skan two scalarizable references, LHS_ELT and RHS_ELT. */ 2008169689Skan 2009169689Skanstatic void 2010169689Skanscalarize_copy (struct sra_elt *lhs_elt, struct sra_elt *rhs_elt, 2011169689Skan block_stmt_iterator *bsi) 2012169689Skan{ 2013169689Skan tree list, stmt; 2014169689Skan 2015169689Skan if (lhs_elt->replacement && rhs_elt->replacement) 2016169689Skan { 2017169689Skan /* If we have two scalar operands, modify the existing statement. */ 2018169689Skan stmt = bsi_stmt (*bsi); 2019169689Skan 2020169689Skan /* See the commentary in sra_walk_function concerning 2021169689Skan RETURN_EXPR, and why we should never see one here. */ 2022169689Skan gcc_assert (TREE_CODE (stmt) == MODIFY_EXPR); 2023169689Skan 2024169689Skan TREE_OPERAND (stmt, 0) = lhs_elt->replacement; 2025169689Skan TREE_OPERAND (stmt, 1) = rhs_elt->replacement; 2026169689Skan update_stmt (stmt); 2027169689Skan } 2028169689Skan else if (lhs_elt->use_block_copy || rhs_elt->use_block_copy) 2029169689Skan { 2030169689Skan /* If either side requires a block copy, then sync the RHS back 2031169689Skan to the original structure, leave the original assignment 2032169689Skan statement (which will perform the block copy), then load the 2033169689Skan LHS values out of its now-updated original structure. */ 2034169689Skan /* ??? Could perform a modified pair-wise element copy. That 2035169689Skan would at least allow those elements that are instantiated in 2036169689Skan both structures to be optimized well. */ 2037169689Skan 2038169689Skan list = NULL; 2039169689Skan generate_copy_inout (rhs_elt, false, 2040169689Skan generate_element_ref (rhs_elt), &list); 2041169689Skan if (list) 2042169689Skan { 2043169689Skan mark_all_v_defs (list); 2044169689Skan sra_insert_before (bsi, list); 2045169689Skan } 2046169689Skan 2047169689Skan list = NULL; 2048169689Skan generate_copy_inout (lhs_elt, true, 2049169689Skan generate_element_ref (lhs_elt), &list); 2050169689Skan if (list) 2051169689Skan { 2052169689Skan mark_all_v_defs (list); 2053169689Skan sra_insert_after (bsi, list); 2054169689Skan } 2055169689Skan } 2056169689Skan else 2057169689Skan { 2058169689Skan /* Otherwise both sides must be fully instantiated. In which 2059169689Skan case perform pair-wise element assignments and replace the 2060169689Skan original block copy statement. */ 2061169689Skan 2062169689Skan stmt = bsi_stmt (*bsi); 2063169689Skan mark_all_v_defs (stmt); 2064169689Skan 2065169689Skan list = NULL; 2066169689Skan generate_element_copy (lhs_elt, rhs_elt, &list); 2067169689Skan gcc_assert (list); 2068169689Skan mark_all_v_defs (list); 2069169689Skan sra_replace (bsi, list); 2070169689Skan } 2071169689Skan} 2072169689Skan 2073169689Skan/* Scalarize an INIT. To recap, this is an assignment to a scalarizable 2074169689Skan reference from some form of constructor: CONSTRUCTOR, COMPLEX_CST or 2075169689Skan COMPLEX_EXPR. If RHS is NULL, it should be treated as an empty 2076169689Skan CONSTRUCTOR. */ 2077169689Skan 2078169689Skanstatic void 2079169689Skanscalarize_init (struct sra_elt *lhs_elt, tree rhs, block_stmt_iterator *bsi) 2080169689Skan{ 2081169689Skan bool result = true; 2082169689Skan tree list = NULL; 2083169689Skan 2084169689Skan /* Generate initialization statements for all members extant in the RHS. */ 2085169689Skan if (rhs) 2086169689Skan { 2087169689Skan /* Unshare the expression just in case this is from a decl's initial. */ 2088169689Skan rhs = unshare_expr (rhs); 2089169689Skan result = generate_element_init (lhs_elt, rhs, &list); 2090169689Skan } 2091169689Skan 2092169689Skan /* CONSTRUCTOR is defined such that any member not mentioned is assigned 2093169689Skan a zero value. Initialize the rest of the instantiated elements. */ 2094169689Skan generate_element_zero (lhs_elt, &list); 2095169689Skan 2096169689Skan if (!result) 2097169689Skan { 2098169689Skan /* If we failed to convert the entire initializer, then we must 2099169689Skan leave the structure assignment in place and must load values 2100169689Skan from the structure into the slots for which we did not find 2101169689Skan constants. The easiest way to do this is to generate a complete 2102169689Skan copy-out, and then follow that with the constant assignments 2103169689Skan that we were able to build. DCE will clean things up. */ 2104169689Skan tree list0 = NULL; 2105169689Skan generate_copy_inout (lhs_elt, true, generate_element_ref (lhs_elt), 2106169689Skan &list0); 2107169689Skan append_to_statement_list (list, &list0); 2108169689Skan list = list0; 2109169689Skan } 2110169689Skan 2111169689Skan if (lhs_elt->use_block_copy || !result) 2112169689Skan { 2113169689Skan /* Since LHS is not fully instantiated, we must leave the structure 2114169689Skan assignment in place. Treating this case differently from a USE 2115169689Skan exposes constants to later optimizations. */ 2116169689Skan if (list) 2117169689Skan { 2118169689Skan mark_all_v_defs (list); 2119169689Skan sra_insert_after (bsi, list); 2120169689Skan } 2121169689Skan } 2122169689Skan else 2123169689Skan { 2124169689Skan /* The LHS is fully instantiated. The list of initializations 2125169689Skan replaces the original structure assignment. */ 2126169689Skan gcc_assert (list); 2127169689Skan mark_all_v_defs (bsi_stmt (*bsi)); 2128169689Skan mark_all_v_defs (list); 2129169689Skan sra_replace (bsi, list); 2130169689Skan } 2131169689Skan} 2132169689Skan 2133169689Skan/* A subroutine of scalarize_ldst called via walk_tree. Set TREE_NO_TRAP 2134169689Skan on all INDIRECT_REFs. */ 2135169689Skan 2136169689Skanstatic tree 2137169689Skanmark_notrap (tree *tp, int *walk_subtrees, void *data ATTRIBUTE_UNUSED) 2138169689Skan{ 2139169689Skan tree t = *tp; 2140169689Skan 2141169689Skan if (TREE_CODE (t) == INDIRECT_REF) 2142169689Skan { 2143169689Skan TREE_THIS_NOTRAP (t) = 1; 2144169689Skan *walk_subtrees = 0; 2145169689Skan } 2146169689Skan else if (IS_TYPE_OR_DECL_P (t)) 2147169689Skan *walk_subtrees = 0; 2148169689Skan 2149169689Skan return NULL; 2150169689Skan} 2151169689Skan 2152169689Skan/* Scalarize a LDST. To recap, this is an assignment between one scalarizable 2153169689Skan reference ELT and one non-scalarizable reference OTHER. IS_OUTPUT is true 2154169689Skan if ELT is on the left-hand side. */ 2155169689Skan 2156169689Skanstatic void 2157169689Skanscalarize_ldst (struct sra_elt *elt, tree other, 2158169689Skan block_stmt_iterator *bsi, bool is_output) 2159169689Skan{ 2160169689Skan /* Shouldn't have gotten called for a scalar. */ 2161169689Skan gcc_assert (!elt->replacement); 2162169689Skan 2163169689Skan if (elt->use_block_copy) 2164169689Skan { 2165169689Skan /* Since ELT is not fully instantiated, we have to leave the 2166169689Skan block copy in place. Treat this as a USE. */ 2167169689Skan scalarize_use (elt, NULL, bsi, is_output, false); 2168169689Skan } 2169169689Skan else 2170169689Skan { 2171169689Skan /* The interesting case is when ELT is fully instantiated. In this 2172169689Skan case we can have each element stored/loaded directly to/from the 2173169689Skan corresponding slot in OTHER. This avoids a block copy. */ 2174169689Skan 2175169689Skan tree list = NULL, stmt = bsi_stmt (*bsi); 2176169689Skan 2177169689Skan mark_all_v_defs (stmt); 2178169689Skan generate_copy_inout (elt, is_output, other, &list); 2179169689Skan mark_all_v_defs (list); 2180169689Skan gcc_assert (list); 2181169689Skan 2182169689Skan /* Preserve EH semantics. */ 2183169689Skan if (stmt_ends_bb_p (stmt)) 2184169689Skan { 2185169689Skan tree_stmt_iterator tsi; 2186169689Skan tree first; 2187169689Skan 2188169689Skan /* Extract the first statement from LIST. */ 2189169689Skan tsi = tsi_start (list); 2190169689Skan first = tsi_stmt (tsi); 2191169689Skan tsi_delink (&tsi); 2192169689Skan 2193169689Skan /* Replace the old statement with this new representative. */ 2194169689Skan bsi_replace (bsi, first, true); 2195169689Skan 2196169689Skan if (!tsi_end_p (tsi)) 2197169689Skan { 2198169689Skan /* If any reference would trap, then they all would. And more 2199169689Skan to the point, the first would. Therefore none of the rest 2200169689Skan will trap since the first didn't. Indicate this by 2201169689Skan iterating over the remaining statements and set 2202169689Skan TREE_THIS_NOTRAP in all INDIRECT_REFs. */ 2203169689Skan do 2204169689Skan { 2205169689Skan walk_tree (tsi_stmt_ptr (tsi), mark_notrap, NULL, NULL); 2206169689Skan tsi_next (&tsi); 2207169689Skan } 2208169689Skan while (!tsi_end_p (tsi)); 2209169689Skan 2210169689Skan insert_edge_copies (list, bsi->bb); 2211169689Skan } 2212169689Skan } 2213169689Skan else 2214169689Skan sra_replace (bsi, list); 2215169689Skan } 2216169689Skan} 2217169689Skan 2218169689Skan/* Generate initializations for all scalarizable parameters. */ 2219169689Skan 2220169689Skanstatic void 2221169689Skanscalarize_parms (void) 2222169689Skan{ 2223169689Skan tree list = NULL; 2224169689Skan unsigned i; 2225169689Skan bitmap_iterator bi; 2226169689Skan 2227169689Skan EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i, bi) 2228169689Skan { 2229169689Skan tree var = referenced_var (i); 2230169689Skan struct sra_elt *elt = lookup_element (NULL, var, NULL, NO_INSERT); 2231169689Skan generate_copy_inout (elt, true, var, &list); 2232169689Skan } 2233169689Skan 2234169689Skan if (list) 2235169689Skan { 2236169689Skan insert_edge_copies (list, ENTRY_BLOCK_PTR); 2237169689Skan mark_all_v_defs (list); 2238169689Skan } 2239169689Skan} 2240169689Skan 2241169689Skan/* Entry point to phase 4. Update the function to match replacements. */ 2242169689Skan 2243169689Skanstatic void 2244169689Skanscalarize_function (void) 2245169689Skan{ 2246169689Skan static const struct sra_walk_fns fns = { 2247169689Skan scalarize_use, scalarize_copy, scalarize_init, scalarize_ldst, false 2248169689Skan }; 2249169689Skan 2250169689Skan sra_walk_function (&fns); 2251169689Skan scalarize_parms (); 2252169689Skan bsi_commit_edge_inserts (); 2253169689Skan} 2254169689Skan 2255169689Skan 2256169689Skan/* Debug helper function. Print ELT in a nice human-readable format. */ 2257169689Skan 2258169689Skanstatic void 2259169689Skandump_sra_elt_name (FILE *f, struct sra_elt *elt) 2260169689Skan{ 2261169689Skan if (elt->parent && TREE_CODE (elt->parent->type) == COMPLEX_TYPE) 2262169689Skan { 2263169689Skan fputs (elt->element == integer_zero_node ? "__real__ " : "__imag__ ", f); 2264169689Skan dump_sra_elt_name (f, elt->parent); 2265169689Skan } 2266169689Skan else 2267169689Skan { 2268169689Skan if (elt->parent) 2269169689Skan dump_sra_elt_name (f, elt->parent); 2270169689Skan if (DECL_P (elt->element)) 2271169689Skan { 2272169689Skan if (TREE_CODE (elt->element) == FIELD_DECL) 2273169689Skan fputc ('.', f); 2274169689Skan print_generic_expr (f, elt->element, dump_flags); 2275169689Skan } 2276169689Skan else if (TREE_CODE (elt->element) == RANGE_EXPR) 2277169689Skan fprintf (f, "["HOST_WIDE_INT_PRINT_DEC".."HOST_WIDE_INT_PRINT_DEC"]", 2278169689Skan TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 0)), 2279169689Skan TREE_INT_CST_LOW (TREE_OPERAND (elt->element, 1))); 2280169689Skan else 2281169689Skan fprintf (f, "[" HOST_WIDE_INT_PRINT_DEC "]", 2282169689Skan TREE_INT_CST_LOW (elt->element)); 2283169689Skan } 2284169689Skan} 2285169689Skan 2286169689Skan/* Likewise, but callable from the debugger. */ 2287169689Skan 2288169689Skanvoid 2289169689Skandebug_sra_elt_name (struct sra_elt *elt) 2290169689Skan{ 2291169689Skan dump_sra_elt_name (stderr, elt); 2292169689Skan fputc ('\n', stderr); 2293169689Skan} 2294169689Skan 2295169689Skanvoid 2296169689Skansra_init_cache (void) 2297169689Skan{ 2298169689Skan if (sra_type_decomp_cache) 2299169689Skan return; 2300169689Skan 2301169689Skan sra_type_decomp_cache = BITMAP_ALLOC (NULL); 2302169689Skan sra_type_inst_cache = BITMAP_ALLOC (NULL); 2303169689Skan} 2304169689Skan 2305169689Skan/* Main entry point. */ 2306169689Skan 2307169689Skanstatic unsigned int 2308169689Skantree_sra (void) 2309169689Skan{ 2310169689Skan /* Initialize local variables. */ 2311169689Skan todoflags = 0; 2312169689Skan gcc_obstack_init (&sra_obstack); 2313169689Skan sra_candidates = BITMAP_ALLOC (NULL); 2314169689Skan needs_copy_in = BITMAP_ALLOC (NULL); 2315169689Skan sra_init_cache (); 2316169689Skan sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, NULL); 2317169689Skan 2318169689Skan /* Scan. If we find anything, instantiate and scalarize. */ 2319169689Skan if (find_candidates_for_sra ()) 2320169689Skan { 2321169689Skan scan_function (); 2322169689Skan decide_instantiations (); 2323169689Skan scalarize_function (); 2324169689Skan } 2325169689Skan 2326169689Skan /* Free allocated memory. */ 2327169689Skan htab_delete (sra_map); 2328169689Skan sra_map = NULL; 2329169689Skan BITMAP_FREE (sra_candidates); 2330169689Skan BITMAP_FREE (needs_copy_in); 2331169689Skan BITMAP_FREE (sra_type_decomp_cache); 2332169689Skan BITMAP_FREE (sra_type_inst_cache); 2333169689Skan obstack_free (&sra_obstack, NULL); 2334169689Skan return todoflags; 2335169689Skan} 2336169689Skan 2337169689Skanstatic bool 2338169689Skangate_sra (void) 2339169689Skan{ 2340169689Skan return flag_tree_sra != 0; 2341169689Skan} 2342169689Skan 2343169689Skanstruct tree_opt_pass pass_sra = 2344169689Skan{ 2345169689Skan "sra", /* name */ 2346169689Skan gate_sra, /* gate */ 2347169689Skan tree_sra, /* execute */ 2348169689Skan NULL, /* sub */ 2349169689Skan NULL, /* next */ 2350169689Skan 0, /* static_pass_number */ 2351169689Skan TV_TREE_SRA, /* tv_id */ 2352169689Skan PROP_cfg | PROP_ssa | PROP_alias, /* properties_required */ 2353169689Skan 0, /* properties_provided */ 2354169689Skan PROP_smt_usage, /* properties_destroyed */ 2355169689Skan 0, /* todo_flags_start */ 2356169689Skan TODO_dump_func /* todo_flags_finish */ 2357169689Skan | TODO_update_ssa 2358169689Skan | TODO_ggc_collect | TODO_verify_ssa, 2359169689Skan 0 /* letter */ 2360169689Skan}; 2361