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