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