gcc/tree-sra.c

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