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