gcc/tree-sra.c

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