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