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