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