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 = gimple_build_debug_bind (get_access_replacement (access),
2843                                             NULL_TREE,
2844                                             gsi_stmt (*gsi));
2845       gsi_insert_after (gsi, ds, GSI_NEW_STMT);
2846     }
2847
2848   if (access->first_child)
2849     {
2850       HOST_WIDE_INT start_offset, chunk_size;
2851       if (bfr
2852           && tree_fits_uhwi_p (TREE_OPERAND (bfr, 1))
2853           && tree_fits_uhwi_p (TREE_OPERAND (bfr, 2)))
2854         {
2855           chunk_size = tree_to_uhwi (TREE_OPERAND (bfr, 1));
2856           start_offset = access->offset
2857             + tree_to_uhwi (TREE_OPERAND (bfr, 2));
2858         }
2859       else
2860         start_offset = chunk_size = 0;
2861
2862       generate_subtree_copies (access->first_child, orig_expr, access->offset,
2863                                start_offset, chunk_size, gsi, write, write,
2864                                loc);
2865     }
2866   return true;
2867 }
2868
2869 /* Where scalar replacements of the RHS have been written to when a replacement
2870    of a LHS of an assigments cannot be direclty loaded from a replacement of
2871    the RHS. */
2872 enum unscalarized_data_handling { SRA_UDH_NONE,  /* Nothing done so far. */
2873                                   SRA_UDH_RIGHT, /* Data flushed to the RHS. */
2874                                   SRA_UDH_LEFT }; /* Data flushed to the LHS. */
2875
2876 struct subreplacement_assignment_data
2877 {
2878   /* Offset of the access representing the lhs of the assignment.  */
2879   HOST_WIDE_INT left_offset;
2880
2881   /* LHS and RHS of the original assignment.  */
2882   tree assignment_lhs, assignment_rhs;
2883
2884   /* Access representing the rhs of the whole assignment.  */
2885   struct access *top_racc;
2886
2887   /* Stmt iterator used for statement insertions after the original assignment.
2888    It points to the main GSI used to traverse a BB during function body
2889    modification.  */
2890   gimple_stmt_iterator *new_gsi;
2891
2892   /* Stmt iterator used for statement insertions before the original
2893    assignment.  Keeps on pointing to the original statement.  */
2894   gimple_stmt_iterator old_gsi;
2895
2896   /* Location of the assignment.   */
2897   location_t loc;
2898
2899   /* Keeps the information whether we have needed to refresh replacements of
2900    the LHS and from which side of the assignments this takes place.  */
2901   enum unscalarized_data_handling refreshed;
2902 };
2903
2904 /* Store all replacements in the access tree rooted in TOP_RACC either to their
2905    base aggregate if there are unscalarized data or directly to LHS of the
2906    statement that is pointed to by GSI otherwise.  */
2907
2908 static void
2909 handle_unscalarized_data_in_subtree (struct subreplacement_assignment_data *sad)
2910 {
2911   tree src;
2912   if (sad->top_racc->grp_unscalarized_data)
2913     {
2914       src = sad->assignment_rhs;
2915       sad->refreshed = SRA_UDH_RIGHT;
2916     }
2917   else
2918     {
2919       src = sad->assignment_lhs;
2920       sad->refreshed = SRA_UDH_LEFT;
2921     }
2922   generate_subtree_copies (sad->top_racc->first_child, src,
2923                            sad->top_racc->offset, 0, 0,
2924                            &sad->old_gsi, false, false, sad->loc);
2925 }
2926
2927 /* Try to generate statements to load all sub-replacements in an access subtree
2928    formed by children of LACC from scalar replacements in the SAD->top_racc
2929    subtree.  If that is not possible, refresh the SAD->top_racc base aggregate
2930    and load the accesses from it.  */
2931
2932 static void
2933 load_assign_lhs_subreplacements (struct access *lacc,
2934                                  struct subreplacement_assignment_data *sad)
2935 {
2936   for (lacc = lacc->first_child; lacc; lacc = lacc->next_sibling)
2937     {
2938       HOST_WIDE_INT offset;
2939       offset = lacc->offset - sad->left_offset + sad->top_racc->offset;
2940
2941       if (lacc->grp_to_be_replaced)
2942         {
2943           struct access *racc;
2944           gassign *stmt;
2945           tree rhs;
2946
2947           racc = find_access_in_subtree (sad->top_racc, offset, lacc->size);
2948           if (racc && racc->grp_to_be_replaced)
2949             {
2950               rhs = get_access_replacement (racc);
2951               if (!useless_type_conversion_p (lacc->type, racc->type))
2952                 rhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
2953                                        lacc->type, rhs);
2954
2955               if (racc->grp_partial_lhs && lacc->grp_partial_lhs)
2956                 rhs = force_gimple_operand_gsi (&sad->old_gsi, rhs, true,
2957                                                 NULL_TREE, true, GSI_SAME_STMT);
2958             }
2959           else
2960             {
2961               /* No suitable access on the right hand side, need to load from
2962                  the aggregate.  See if we have to update it first... */
2963               if (sad->refreshed == SRA_UDH_NONE)
2964                 handle_unscalarized_data_in_subtree (sad);
2965
2966               if (sad->refreshed == SRA_UDH_LEFT)
2967                 rhs = build_ref_for_model (sad->loc, sad->assignment_lhs,
2968                                            lacc->offset - sad->left_offset,
2969                                            lacc, sad->new_gsi, true);
2970               else
2971                 rhs = build_ref_for_model (sad->loc, sad->assignment_rhs,
2972                                            lacc->offset - sad->left_offset,
2973                                            lacc, sad->new_gsi, true);
2974               if (lacc->grp_partial_lhs)
2975                 rhs = force_gimple_operand_gsi (sad->new_gsi,
2976                                                 rhs, true, NULL_TREE,
2977                                                 false, GSI_NEW_STMT);
2978             }
2979
2980           stmt = gimple_build_assign (get_access_replacement (lacc), rhs);
2981           gsi_insert_after (sad->new_gsi, stmt, GSI_NEW_STMT);
2982           gimple_set_location (stmt, sad->loc);
2983           update_stmt (stmt);
2984           sra_stats.subreplacements++;
2985         }
2986       else
2987         {
2988           if (sad->refreshed == SRA_UDH_NONE
2989               && lacc->grp_read && !lacc->grp_covered)
2990             handle_unscalarized_data_in_subtree (sad);
2991
2992           if (lacc && lacc->grp_to_be_debug_replaced)
2993             {
2994               gdebug *ds;
2995               tree drhs;
2996               struct access *racc = find_access_in_subtree (sad->top_racc,
2997                                                             offset,
2998                                                             lacc->size);
2999
3000               if (racc && racc->grp_to_be_replaced)
3001                 {
3002                   if (racc->grp_write)
3003                     drhs = get_access_replacement (racc);
3004                   else
3005                     drhs = NULL;
3006                 }
3007               else if (sad->refreshed == SRA_UDH_LEFT)
3008                 drhs = build_debug_ref_for_model (sad->loc, lacc->base,
3009                                                   lacc->offset, lacc);
3010               else if (sad->refreshed == SRA_UDH_RIGHT)
3011                 drhs = build_debug_ref_for_model (sad->loc, sad->top_racc->base,
3012                                                   offset, lacc);
3013               else
3014                 drhs = NULL_TREE;
3015               if (drhs
3016                   && !useless_type_conversion_p (lacc->type, TREE_TYPE (drhs)))
3017                 drhs = fold_build1_loc (sad->loc, VIEW_CONVERT_EXPR,
3018                                         lacc->type, drhs);
3019               ds = gimple_build_debug_bind (get_access_replacement (lacc),
3020                                             drhs, gsi_stmt (sad->old_gsi));
3021               gsi_insert_after (sad->new_gsi, ds, GSI_NEW_STMT);
3022             }
3023         }
3024
3025       if (lacc->first_child)
3026         load_assign_lhs_subreplacements (lacc, sad);
3027     }
3028 }
3029
3030 /* Result code for SRA assignment modification.  */
3031 enum assignment_mod_result { SRA_AM_NONE,       /* nothing done for the stmt */
3032                              SRA_AM_MODIFIED,  /* stmt changed but not
3033                                                   removed */
3034                              SRA_AM_REMOVED };  /* stmt eliminated */
3035
3036 /* Modify assignments with a CONSTRUCTOR on their RHS.  STMT contains a pointer
3037    to the assignment and GSI is the statement iterator pointing at it.  Returns
3038    the same values as sra_modify_assign.  */
3039
3040 static enum assignment_mod_result
3041 sra_modify_constructor_assign (gimple stmt, gimple_stmt_iterator *gsi)
3042 {
3043   tree lhs = gimple_assign_lhs (stmt);
3044   struct access *acc;
3045   location_t loc;
3046
3047   acc = get_access_for_expr (lhs);
3048   if (!acc)
3049     return SRA_AM_NONE;
3050
3051   if (gimple_clobber_p (stmt))
3052     {
3053       /* Remove clobbers of fully scalarized variables, otherwise
3054          do nothing.  */
3055       if (acc->grp_covered)
3056         {
3057           unlink_stmt_vdef (stmt);
3058           gsi_remove (gsi, true);
3059           release_defs (stmt);
3060           return SRA_AM_REMOVED;
3061         }
3062       else
3063         return SRA_AM_NONE;
3064     }
3065
3066   loc = gimple_location (stmt);
3067   if (vec_safe_length (CONSTRUCTOR_ELTS (gimple_assign_rhs1 (stmt))) > 0)
3068     {
3069       /* I have never seen this code path trigger but if it can happen the
3070          following should handle it gracefully.  */
3071       if (access_has_children_p (acc))
3072         generate_subtree_copies (acc->first_child, lhs, acc->offset, 0, 0, gsi,
3073                                  true, true, loc);
3074       return SRA_AM_MODIFIED;
3075     }
3076
3077   if (acc->grp_covered)
3078     {
3079       init_subtree_with_zero (acc, gsi, false, loc);
3080       unlink_stmt_vdef (stmt);
3081       gsi_remove (gsi, true);
3082       release_defs (stmt);
3083       return SRA_AM_REMOVED;
3084     }
3085   else
3086     {
3087       init_subtree_with_zero (acc, gsi, true, loc);
3088       return SRA_AM_MODIFIED;
3089     }
3090 }
3091
3092 /* Create and return a new suitable default definition SSA_NAME for RACC which
3093    is an access describing an uninitialized part of an aggregate that is being
3094    loaded.  */
3095
3096 static tree
3097 get_repl_default_def_ssa_name (struct access *racc)
3098 {
3099   gcc_checking_assert (!racc->grp_to_be_replaced
3100                        && !racc->grp_to_be_debug_replaced);
3101   if (!racc->replacement_decl)
3102     racc->replacement_decl = create_access_replacement (racc);
3103   return get_or_create_ssa_default_def (cfun, racc->replacement_decl);
3104 }
3105
3106 /* Return true if REF has an VIEW_CONVERT_EXPR or a COMPONENT_REF with a
3107    bit-field field declaration somewhere in it.  */
3108
3109 static inline bool
3110 contains_vce_or_bfcref_p (const_tree ref)
3111 {
3112   while (handled_component_p (ref))
3113     {
3114       if (TREE_CODE (ref) == VIEW_CONVERT_EXPR
3115           || (TREE_CODE (ref) == COMPONENT_REF
3116               && DECL_BIT_FIELD (TREE_OPERAND (ref, 1))))
3117         return true;
3118       ref = TREE_OPERAND (ref, 0);
3119     }
3120
3121   return false;
3122 }
3123
3124 /* Examine both sides of the assignment statement pointed to by STMT, replace
3125    them with a scalare replacement if there is one and generate copying of
3126    replacements if scalarized aggregates have been used in the assignment.  GSI
3127    is used to hold generated statements for type conversions and subtree
3128    copying.  */
3129
3130 static enum assignment_mod_result
3131 sra_modify_assign (gimple stmt, gimple_stmt_iterator *gsi)
3132 {
3133   struct access *lacc, *racc;
3134   tree lhs, rhs;
3135   bool modify_this_stmt = false;
3136   bool force_gimple_rhs = false;
3137   location_t loc;
3138   gimple_stmt_iterator orig_gsi = *gsi;
3139
3140   if (!gimple_assign_single_p (stmt))
3141     return SRA_AM_NONE;
3142   lhs = gimple_assign_lhs (stmt);
3143   rhs = gimple_assign_rhs1 (stmt);
3144
3145   if (TREE_CODE (rhs) == CONSTRUCTOR)
3146     return sra_modify_constructor_assign (stmt, gsi);
3147
3148   if (TREE_CODE (rhs) == REALPART_EXPR || TREE_CODE (lhs) == REALPART_EXPR
3149       || TREE_CODE (rhs) == IMAGPART_EXPR || TREE_CODE (lhs) == IMAGPART_EXPR
3150       || TREE_CODE (rhs) == BIT_FIELD_REF || TREE_CODE (lhs) == BIT_FIELD_REF)
3151     {
3152       modify_this_stmt = sra_modify_expr (gimple_assign_rhs1_ptr (stmt),
3153                                           gsi, false);
3154       modify_this_stmt |= sra_modify_expr (gimple_assign_lhs_ptr (stmt),
3155                                            gsi, true);
3156       return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
3157     }
3158
3159   lacc = get_access_for_expr (lhs);
3160   racc = get_access_for_expr (rhs);
3161   if (!lacc && !racc)
3162     return SRA_AM_NONE;
3163
3164   loc = gimple_location (stmt);
3165   if (lacc && lacc->grp_to_be_replaced)
3166     {
3167       lhs = get_access_replacement (lacc);
3168       gimple_assign_set_lhs (stmt, lhs);
3169       modify_this_stmt = true;
3170       if (lacc->grp_partial_lhs)
3171         force_gimple_rhs = true;
3172       sra_stats.exprs++;
3173     }
3174
3175   if (racc && racc->grp_to_be_replaced)
3176     {
3177       rhs = get_access_replacement (racc);
3178       modify_this_stmt = true;
3179       if (racc->grp_partial_lhs)
3180         force_gimple_rhs = true;
3181       sra_stats.exprs++;
3182     }
3183   else if (racc
3184            && !racc->grp_unscalarized_data
3185            && TREE_CODE (lhs) == SSA_NAME
3186            && !access_has_replacements_p (racc))
3187     {
3188       rhs = get_repl_default_def_ssa_name (racc);
3189       modify_this_stmt = true;
3190       sra_stats.exprs++;
3191     }
3192
3193   if (modify_this_stmt)
3194     {
3195       if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3196         {
3197           /* If we can avoid creating a VIEW_CONVERT_EXPR do so.
3198              ???  This should move to fold_stmt which we simply should
3199              call after building a VIEW_CONVERT_EXPR here.  */
3200           if (AGGREGATE_TYPE_P (TREE_TYPE (lhs))
3201               && !contains_bitfld_component_ref_p (lhs))
3202             {
3203               lhs = build_ref_for_model (loc, lhs, 0, racc, gsi, false);
3204               gimple_assign_set_lhs (stmt, lhs);
3205             }
3206           else if (AGGREGATE_TYPE_P (TREE_TYPE (rhs))
3207                    && !contains_vce_or_bfcref_p (rhs))
3208             rhs = build_ref_for_model (loc, rhs, 0, lacc, gsi, false);
3209
3210           if (!useless_type_conversion_p (TREE_TYPE (lhs), TREE_TYPE (rhs)))
3211             {
3212               rhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR, TREE_TYPE (lhs),
3213                                      rhs);
3214               if (is_gimple_reg_type (TREE_TYPE (lhs))
3215                   && TREE_CODE (lhs) != SSA_NAME)
3216                 force_gimple_rhs = true;
3217             }
3218         }
3219     }
3220
3221   if (lacc && lacc->grp_to_be_debug_replaced)
3222     {
3223       tree dlhs = get_access_replacement (lacc);
3224       tree drhs = unshare_expr (rhs);
3225       if (!useless_type_conversion_p (TREE_TYPE (dlhs), TREE_TYPE (drhs)))
3226         {
3227           if (AGGREGATE_TYPE_P (TREE_TYPE (drhs))
3228               && !contains_vce_or_bfcref_p (drhs))
3229             drhs = build_debug_ref_for_model (loc, drhs, 0, lacc);
3230           if (drhs
3231               && !useless_type_conversion_p (TREE_TYPE (dlhs),
3232                                              TREE_TYPE (drhs)))
3233             drhs = fold_build1_loc (loc, VIEW_CONVERT_EXPR,
3234                                     TREE_TYPE (dlhs), drhs);
3235         }
3236       gdebug *ds = gimple_build_debug_bind (dlhs, drhs, stmt);
3237       gsi_insert_before (gsi, ds, GSI_SAME_STMT);
3238     }
3239
3240   /* From this point on, the function deals with assignments in between
3241      aggregates when at least one has scalar reductions of some of its
3242      components.  There are three possible scenarios: Both the LHS and RHS have
3243      to-be-scalarized components, 2) only the RHS has or 3) only the LHS has.
3244
3245      In the first case, we would like to load the LHS components from RHS
3246      components whenever possible.  If that is not possible, we would like to
3247      read it directly from the RHS (after updating it by storing in it its own
3248      components).  If there are some necessary unscalarized data in the LHS,
3249      those will be loaded by the original assignment too.  If neither of these
3250      cases happen, the original statement can be removed.  Most of this is done
3251      by load_assign_lhs_subreplacements.
3252
3253      In the second case, we would like to store all RHS scalarized components
3254      directly into LHS and if they cover the aggregate completely, remove the
3255      statement too.  In the third case, we want the LHS components to be loaded
3256      directly from the RHS (DSE will remove the original statement if it
3257      becomes redundant).
3258
3259      This is a bit complex but manageable when types match and when unions do
3260      not cause confusion in a way that we cannot really load a component of LHS
3261      from the RHS or vice versa (the access representing this level can have
3262      subaccesses that are accessible only through a different union field at a
3263      higher level - different from the one used in the examined expression).
3264      Unions are fun.
3265
3266      Therefore, I specially handle a fourth case, happening when there is a
3267      specific type cast or it is impossible to locate a scalarized subaccess on
3268      the other side of the expression.  If that happens, I simply "refresh" the
3269      RHS by storing in it is scalarized components leave the original statement
3270      there to do the copying and then load the scalar replacements of the LHS.
3271      This is what the first branch does.  */
3272
3273   if (modify_this_stmt
3274       || gimple_has_volatile_ops (stmt)
3275       || contains_vce_or_bfcref_p (rhs)
3276       || contains_vce_or_bfcref_p (lhs)
3277       || stmt_ends_bb_p (stmt))
3278     {
3279       if (access_has_children_p (racc))
3280         generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
3281                                  gsi, false, false, loc);
3282       if (access_has_children_p (lacc))
3283         {
3284           gimple_stmt_iterator alt_gsi = gsi_none ();
3285           if (stmt_ends_bb_p (stmt))
3286             {
3287               alt_gsi = gsi_start_edge (single_non_eh_succ (gsi_bb (*gsi)));
3288               gsi = &alt_gsi;
3289             }
3290           generate_subtree_copies (lacc->first_child, lhs, lacc->offset, 0, 0,
3291                                    gsi, true, true, loc);
3292         }
3293       sra_stats.separate_lhs_rhs_handling++;
3294
3295       /* This gimplification must be done after generate_subtree_copies,
3296          lest we insert the subtree copies in the middle of the gimplified
3297          sequence.  */
3298       if (force_gimple_rhs)
3299         rhs = force_gimple_operand_gsi (&orig_gsi, rhs, true, NULL_TREE,
3300                                         true, GSI_SAME_STMT);
3301       if (gimple_assign_rhs1 (stmt) != rhs)
3302         {
3303           modify_this_stmt = true;
3304           gimple_assign_set_rhs_from_tree (&orig_gsi, rhs);
3305           gcc_assert (stmt == gsi_stmt (orig_gsi));
3306         }
3307
3308       return modify_this_stmt ? SRA_AM_MODIFIED : SRA_AM_NONE;
3309     }
3310   else
3311     {
3312       if (access_has_children_p (lacc)
3313           && access_has_children_p (racc)
3314           /* When an access represents an unscalarizable region, it usually
3315              represents accesses with variable offset and thus must not be used
3316              to generate new memory accesses.  */
3317           && !lacc->grp_unscalarizable_region
3318           && !racc->grp_unscalarizable_region)
3319         {
3320           struct subreplacement_assignment_data sad;
3321
3322           sad.left_offset = lacc->offset;
3323           sad.assignment_lhs = lhs;
3324           sad.assignment_rhs = rhs;
3325           sad.top_racc = racc;
3326           sad.old_gsi = *gsi;
3327           sad.new_gsi = gsi;
3328           sad.loc = gimple_location (stmt);
3329           sad.refreshed = SRA_UDH_NONE;
3330
3331           if (lacc->grp_read && !lacc->grp_covered)
3332             handle_unscalarized_data_in_subtree (&sad);
3333
3334           load_assign_lhs_subreplacements (lacc, &sad);
3335           if (sad.refreshed != SRA_UDH_RIGHT)
3336             {
3337               gsi_next (gsi);
3338               unlink_stmt_vdef (stmt);
3339               gsi_remove (&sad.old_gsi, true);
3340               release_defs (stmt);
3341               sra_stats.deleted++;
3342               return SRA_AM_REMOVED;
3343             }
3344         }
3345       else
3346         {
3347           if (access_has_children_p (racc)
3348               && !racc->grp_unscalarized_data)
3349             {
3350               if (dump_file)
3351                 {
3352                   fprintf (dump_file, "Removing load: ");
3353                   print_gimple_stmt (dump_file, stmt, 0, 0);
3354                 }
3355               generate_subtree_copies (racc->first_child, lhs,
3356                                        racc->offset, 0, 0, gsi,
3357                                        false, false, loc);
3358               gcc_assert (stmt == gsi_stmt (*gsi));
3359               unlink_stmt_vdef (stmt);
3360               gsi_remove (gsi, true);
3361               release_defs (stmt);
3362               sra_stats.deleted++;
3363               return SRA_AM_REMOVED;
3364             }
3365           /* Restore the aggregate RHS from its components so the
3366              prevailing aggregate copy does the right thing.  */
3367           if (access_has_children_p (racc))
3368             generate_subtree_copies (racc->first_child, rhs, racc->offset, 0, 0,
3369                                      gsi, false, false, loc);
3370           /* Re-load the components of the aggregate copy destination.
3371              But use the RHS aggregate to load from to expose more
3372              optimization opportunities.  */
3373           if (access_has_children_p (lacc))
3374             generate_subtree_copies (lacc->first_child, rhs, lacc->offset,
3375                                      0, 0, gsi, true, true, loc);
3376         }
3377
3378       return SRA_AM_NONE;
3379     }
3380 }
3381
3382 /* Traverse the function body and all modifications as decided in
3383    analyze_all_variable_accesses.  Return true iff the CFG has been
3384    changed.  */
3385
3386 static bool
3387 sra_modify_function_body (void)
3388 {
3389   bool cfg_changed = false;
3390   basic_block bb;
3391
3392   FOR_EACH_BB_FN (bb, cfun)
3393     {
3394       gimple_stmt_iterator gsi = gsi_start_bb (bb);
3395       while (!gsi_end_p (gsi))
3396         {
3397           gimple stmt = gsi_stmt (gsi);
3398           enum assignment_mod_result assign_result;
3399           bool modified = false, deleted = false;
3400           tree *t;
3401           unsigned i;
3402
3403           switch (gimple_code (stmt))
3404             {
3405             case GIMPLE_RETURN:
3406               t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
3407               if (*t != NULL_TREE)
3408                 modified |= sra_modify_expr (t, &gsi, false);
3409               break;
3410
3411             case GIMPLE_ASSIGN:
3412               assign_result = sra_modify_assign (stmt, &gsi);
3413               modified |= assign_result == SRA_AM_MODIFIED;
3414               deleted = assign_result == SRA_AM_REMOVED;
3415               break;
3416
3417             case GIMPLE_CALL:
3418               /* Operands must be processed before the lhs.  */
3419               for (i = 0; i < gimple_call_num_args (stmt); i++)
3420                 {
3421                   t = gimple_call_arg_ptr (stmt, i);
3422                   modified |= sra_modify_expr (t, &gsi, false);
3423                 }
3424
3425               if (gimple_call_lhs (stmt))
3426                 {
3427                   t = gimple_call_lhs_ptr (stmt);
3428                   modified |= sra_modify_expr (t, &gsi, true);
3429                 }
3430               break;
3431
3432             case GIMPLE_ASM:
3433               {
3434                 gasm *asm_stmt = as_a <gasm *> (stmt);
3435                 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
3436                   {
3437                     t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
3438                     modified |= sra_modify_expr (t, &gsi, false);
3439                   }
3440                 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
3441                   {
3442                     t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
3443                     modified |= sra_modify_expr (t, &gsi, true);
3444                   }
3445               }
3446               break;
3447
3448             default:
3449               break;
3450             }
3451
3452           if (modified)
3453             {
3454               update_stmt (stmt);
3455               if (maybe_clean_eh_stmt (stmt)
3456                   && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
3457                 cfg_changed = true;
3458             }
3459           if (!deleted)
3460             gsi_next (&gsi);
3461         }
3462     }
3463
3464   gsi_commit_edge_inserts ();
3465   return cfg_changed;
3466 }
3467
3468 /* Generate statements initializing scalar replacements of parts of function
3469    parameters.  */
3470
3471 static void
3472 initialize_parameter_reductions (void)
3473 {
3474   gimple_stmt_iterator gsi;
3475   gimple_seq seq = NULL;
3476   tree parm;
3477
3478   gsi = gsi_start (seq);
3479   for (parm = DECL_ARGUMENTS (current_function_decl);
3480        parm;
3481        parm = DECL_CHAIN (parm))
3482     {
3483       vec<access_p> *access_vec;
3484       struct access *access;
3485
3486       if (!bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
3487         continue;
3488       access_vec = get_base_access_vector (parm);
3489       if (!access_vec)
3490         continue;
3491
3492       for (access = (*access_vec)[0];
3493            access;
3494            access = access->next_grp)
3495         generate_subtree_copies (access, parm, 0, 0, 0, &gsi, true, true,
3496                                  EXPR_LOCATION (parm));
3497     }
3498
3499   seq = gsi_seq (gsi);
3500   if (seq)
3501     gsi_insert_seq_on_edge_immediate (single_succ_edge (ENTRY_BLOCK_PTR_FOR_FN (cfun)), seq);
3502 }
3503
3504 /* The "main" function of intraprocedural SRA passes.  Runs the analysis and if
3505    it reveals there are components of some aggregates to be scalarized, it runs
3506    the required transformations.  */
3507 static unsigned int
3508 perform_intra_sra (void)
3509 {
3510   int ret = 0;
3511   sra_initialize ();
3512
3513   if (!find_var_candidates ())
3514     goto out;
3515
3516   if (!scan_function ())
3517     goto out;
3518
3519   if (!analyze_all_variable_accesses ())
3520     goto out;
3521
3522   if (sra_modify_function_body ())
3523     ret = TODO_update_ssa | TODO_cleanup_cfg;
3524   else
3525     ret = TODO_update_ssa;
3526   initialize_parameter_reductions ();
3527
3528   statistics_counter_event (cfun, "Scalar replacements created",
3529                             sra_stats.replacements);
3530   statistics_counter_event (cfun, "Modified expressions", sra_stats.exprs);
3531   statistics_counter_event (cfun, "Subtree copy stmts",
3532                             sra_stats.subtree_copies);
3533   statistics_counter_event (cfun, "Subreplacement stmts",
3534                             sra_stats.subreplacements);
3535   statistics_counter_event (cfun, "Deleted stmts", sra_stats.deleted);
3536   statistics_counter_event (cfun, "Separate LHS and RHS handling",
3537                             sra_stats.separate_lhs_rhs_handling);
3538
3539  out:
3540   sra_deinitialize ();
3541   return ret;
3542 }
3543
3544 /* Perform early intraprocedural SRA.  */
3545 static unsigned int
3546 early_intra_sra (void)
3547 {
3548   sra_mode = SRA_MODE_EARLY_INTRA;
3549   return perform_intra_sra ();
3550 }
3551
3552 /* Perform "late" intraprocedural SRA.  */
3553 static unsigned int
3554 late_intra_sra (void)
3555 {
3556   sra_mode = SRA_MODE_INTRA;
3557   return perform_intra_sra ();
3558 }
3559
3560
3561 static bool
3562 gate_intra_sra (void)
3563 {
3564   return flag_tree_sra != 0 && dbg_cnt (tree_sra);
3565 }
3566
3567
3568 namespace {
3569
3570 const pass_data pass_data_sra_early =
3571 {
3572   GIMPLE_PASS, /* type */
3573   "esra", /* name */
3574   OPTGROUP_NONE, /* optinfo_flags */
3575   TV_TREE_SRA, /* tv_id */
3576   ( PROP_cfg | PROP_ssa ), /* properties_required */
3577   0, /* properties_provided */
3578   0, /* properties_destroyed */
3579   0, /* todo_flags_start */
3580   TODO_update_ssa, /* todo_flags_finish */
3581 };
3582
3583 class pass_sra_early : public gimple_opt_pass
3584 {
3585 public:
3586   pass_sra_early (gcc::context *ctxt)
3587     : gimple_opt_pass (pass_data_sra_early, ctxt)
3588   {}
3589
3590   /* opt_pass methods: */
3591   virtual bool gate (function *) { return gate_intra_sra (); }
3592   virtual unsigned int execute (function *) { return early_intra_sra (); }
3593
3594 }; // class pass_sra_early
3595
3596 } // anon namespace
3597
3598 gimple_opt_pass *
3599 make_pass_sra_early (gcc::context *ctxt)
3600 {
3601   return new pass_sra_early (ctxt);
3602 }
3603
3604 namespace {
3605
3606 const pass_data pass_data_sra =
3607 {
3608   GIMPLE_PASS, /* type */
3609   "sra", /* name */
3610   OPTGROUP_NONE, /* optinfo_flags */
3611   TV_TREE_SRA, /* tv_id */
3612   ( PROP_cfg | PROP_ssa ), /* properties_required */
3613   0, /* properties_provided */
3614   0, /* properties_destroyed */
3615   TODO_update_address_taken, /* todo_flags_start */
3616   TODO_update_ssa, /* todo_flags_finish */
3617 };
3618
3619 class pass_sra : public gimple_opt_pass
3620 {
3621 public:
3622   pass_sra (gcc::context *ctxt)
3623     : gimple_opt_pass (pass_data_sra, ctxt)
3624   {}
3625
3626   /* opt_pass methods: */
3627   virtual bool gate (function *) { return gate_intra_sra (); }
3628   virtual unsigned int execute (function *) { return late_intra_sra (); }
3629
3630 }; // class pass_sra
3631
3632 } // anon namespace
3633
3634 gimple_opt_pass *
3635 make_pass_sra (gcc::context *ctxt)
3636 {
3637   return new pass_sra (ctxt);
3638 }
3639
3640
3641 /* Return true iff PARM (which must be a parm_decl) is an unused scalar
3642    parameter.  */
3643
3644 static bool
3645 is_unused_scalar_param (tree parm)
3646 {
3647   tree name;
3648   return (is_gimple_reg (parm)
3649           && (!(name = ssa_default_def (cfun, parm))
3650               || has_zero_uses (name)));
3651 }
3652
3653 /* Scan immediate uses of a default definition SSA name of a parameter PARM and
3654    examine whether there are any direct or otherwise infeasible ones.  If so,
3655    return true, otherwise return false.  PARM must be a gimple register with a
3656    non-NULL default definition.  */
3657
3658 static bool
3659 ptr_parm_has_direct_uses (tree parm)
3660 {
3661   imm_use_iterator ui;
3662   gimple stmt;
3663   tree name = ssa_default_def (cfun, parm);
3664   bool ret = false;
3665
3666   FOR_EACH_IMM_USE_STMT (stmt, ui, name)
3667     {
3668       int uses_ok = 0;
3669       use_operand_p use_p;
3670
3671       if (is_gimple_debug (stmt))
3672         continue;
3673
3674       /* Valid uses include dereferences on the lhs and the rhs.  */
3675       if (gimple_has_lhs (stmt))
3676         {
3677           tree lhs = gimple_get_lhs (stmt);
3678           while (handled_component_p (lhs))
3679             lhs = TREE_OPERAND (lhs, 0);
3680           if (TREE_CODE (lhs) == MEM_REF
3681               && TREE_OPERAND (lhs, 0) == name
3682               && integer_zerop (TREE_OPERAND (lhs, 1))
3683               && types_compatible_p (TREE_TYPE (lhs),
3684                                      TREE_TYPE (TREE_TYPE (name)))
3685               && !TREE_THIS_VOLATILE (lhs))
3686             uses_ok++;
3687         }
3688       if (gimple_assign_single_p (stmt))
3689         {
3690           tree rhs = gimple_assign_rhs1 (stmt);
3691           while (handled_component_p (rhs))
3692             rhs = TREE_OPERAND (rhs, 0);
3693           if (TREE_CODE (rhs) == MEM_REF
3694               && TREE_OPERAND (rhs, 0) == name
3695               && integer_zerop (TREE_OPERAND (rhs, 1))
3696               && types_compatible_p (TREE_TYPE (rhs),
3697                                      TREE_TYPE (TREE_TYPE (name)))
3698               && !TREE_THIS_VOLATILE (rhs))
3699             uses_ok++;
3700         }
3701       else if (is_gimple_call (stmt))
3702         {
3703           unsigned i;
3704           for (i = 0; i < gimple_call_num_args (stmt); ++i)
3705             {
3706               tree arg = gimple_call_arg (stmt, i);
3707               while (handled_component_p (arg))
3708                 arg = TREE_OPERAND (arg, 0);
3709               if (TREE_CODE (arg) == MEM_REF
3710                   && TREE_OPERAND (arg, 0) == name
3711                   && integer_zerop (TREE_OPERAND (arg, 1))
3712                   && types_compatible_p (TREE_TYPE (arg),
3713                                          TREE_TYPE (TREE_TYPE (name)))
3714                   && !TREE_THIS_VOLATILE (arg))
3715                 uses_ok++;
3716             }
3717         }
3718
3719       /* If the number of valid uses does not match the number of
3720          uses in this stmt there is an unhandled use.  */
3721       FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
3722         --uses_ok;
3723
3724       if (uses_ok != 0)
3725         ret = true;
3726
3727       if (ret)
3728         BREAK_FROM_IMM_USE_STMT (ui);
3729     }
3730
3731   return ret;
3732 }
3733
3734 /* Identify candidates for reduction for IPA-SRA based on their type and mark
3735    them in candidate_bitmap.  Note that these do not necessarily include
3736    parameter which are unused and thus can be removed.  Return true iff any
3737    such candidate has been found.  */
3738
3739 static bool
3740 find_param_candidates (void)
3741 {
3742   tree parm;
3743   int count = 0;
3744   bool ret = false;
3745   const char *msg;
3746
3747   for (parm = DECL_ARGUMENTS (current_function_decl);
3748        parm;
3749        parm = DECL_CHAIN (parm))
3750     {
3751       tree type = TREE_TYPE (parm);
3752       tree_node **slot;
3753
3754       count++;
3755
3756       if (TREE_THIS_VOLATILE (parm)
3757           || TREE_ADDRESSABLE (parm)
3758           || (!is_gimple_reg_type (type) && is_va_list_type (type)))
3759         continue;
3760
3761       if (is_unused_scalar_param (parm))
3762         {
3763           ret = true;
3764           continue;
3765         }
3766
3767       if (POINTER_TYPE_P (type))
3768         {
3769           type = TREE_TYPE (type);
3770
3771           if (TREE_CODE (type) == FUNCTION_TYPE
3772               || TYPE_VOLATILE (type)
3773               || (TREE_CODE (type) == ARRAY_TYPE
3774                   && TYPE_NONALIASED_COMPONENT (type))
3775               || !is_gimple_reg (parm)
3776               || is_va_list_type (type)
3777               || ptr_parm_has_direct_uses (parm))
3778             continue;
3779         }
3780       else if (!AGGREGATE_TYPE_P (type))
3781         continue;
3782
3783       if (!COMPLETE_TYPE_P (type)
3784           || !tree_fits_uhwi_p (TYPE_SIZE (type))
3785           || tree_to_uhwi (TYPE_SIZE (type)) == 0
3786           || (AGGREGATE_TYPE_P (type)
3787               && type_internals_preclude_sra_p (type, &msg)))
3788         continue;
3789
3790       bitmap_set_bit (candidate_bitmap, DECL_UID (parm));
3791       slot = candidates->find_slot_with_hash (parm, DECL_UID (parm), INSERT);
3792       *slot = parm;
3793
3794       ret = true;
3795       if (dump_file && (dump_flags & TDF_DETAILS))
3796         {
3797           fprintf (dump_file, "Candidate (%d): ", DECL_UID (parm));
3798           print_generic_expr (dump_file, parm, 0);
3799           fprintf (dump_file, "\n");
3800         }
3801     }
3802
3803   func_param_count = count;
3804   return ret;
3805 }
3806
3807 /* Callback of walk_aliased_vdefs, marks the access passed as DATA as
3808    maybe_modified. */
3809
3810 static bool
3811 mark_maybe_modified (ao_ref *ao ATTRIBUTE_UNUSED, tree vdef ATTRIBUTE_UNUSED,
3812                      void *data)
3813 {
3814   struct access *repr = (struct access *) data;
3815
3816   repr->grp_maybe_modified = 1;
3817   return true;
3818 }
3819
3820 /* Analyze what representatives (in linked lists accessible from
3821    REPRESENTATIVES) can be modified by side effects of statements in the
3822    current function.  */
3823
3824 static void
3825 analyze_modified_params (vec<access_p> representatives)
3826 {
3827   int i;
3828
3829   for (i = 0; i < func_param_count; i++)
3830     {
3831       struct access *repr;
3832
3833       for (repr = representatives[i];
3834            repr;
3835            repr = repr->next_grp)
3836         {
3837           struct access *access;
3838           bitmap visited;
3839           ao_ref ar;
3840
3841           if (no_accesses_p (repr))
3842             continue;
3843           if (!POINTER_TYPE_P (TREE_TYPE (repr->base))
3844               || repr->grp_maybe_modified)
3845             continue;
3846
3847           ao_ref_init (&ar, repr->expr);
3848           visited = BITMAP_ALLOC (NULL);
3849           for (access = repr; access; access = access->next_sibling)
3850             {
3851               /* All accesses are read ones, otherwise grp_maybe_modified would
3852                  be trivially set.  */
3853               walk_aliased_vdefs (&ar, gimple_vuse (access->stmt),
3854                                   mark_maybe_modified, repr, &visited);
3855               if (repr->grp_maybe_modified)
3856                 break;
3857             }
3858           BITMAP_FREE (visited);
3859         }
3860     }
3861 }
3862
3863 /* Propagate distances in bb_dereferences in the opposite direction than the
3864    control flow edges, in each step storing the maximum of the current value
3865    and the minimum of all successors.  These steps are repeated until the table
3866    stabilizes.  Note that BBs which might terminate the functions (according to
3867    final_bbs bitmap) never updated in this way.  */
3868
3869 static void
3870 propagate_dereference_distances (void)
3871 {
3872   basic_block bb;
3873
3874   auto_vec<basic_block> queue (last_basic_block_for_fn (cfun));
3875   queue.quick_push (ENTRY_BLOCK_PTR_FOR_FN (cfun));
3876   FOR_EACH_BB_FN (bb, cfun)
3877     {
3878       queue.quick_push (bb);
3879       bb->aux = bb;
3880     }
3881
3882   while (!queue.is_empty ())
3883     {
3884       edge_iterator ei;
3885       edge e;
3886       bool change = false;
3887       int i;
3888
3889       bb = queue.pop ();
3890       bb->aux = NULL;
3891
3892       if (bitmap_bit_p (final_bbs, bb->index))
3893         continue;
3894
3895       for (i = 0; i < func_param_count; i++)
3896         {
3897           int idx = bb->index * func_param_count + i;
3898           bool first = true;
3899           HOST_WIDE_INT inh = 0;
3900
3901           FOR_EACH_EDGE (e, ei, bb->succs)
3902           {
3903             int succ_idx = e->dest->index * func_param_count + i;
3904
3905             if (e->src == EXIT_BLOCK_PTR_FOR_FN (cfun))
3906               continue;
3907
3908             if (first)
3909               {
3910                 first = false;
3911                 inh = bb_dereferences [succ_idx];
3912               }
3913             else if (bb_dereferences [succ_idx] < inh)
3914               inh = bb_dereferences [succ_idx];
3915           }
3916
3917           if (!first && bb_dereferences[idx] < inh)
3918             {
3919               bb_dereferences[idx] = inh;
3920               change = true;
3921             }
3922         }
3923
3924       if (change && !bitmap_bit_p (final_bbs, bb->index))
3925         FOR_EACH_EDGE (e, ei, bb->preds)
3926           {
3927             if (e->src->aux)
3928               continue;
3929
3930             e->src->aux = e->src;
3931             queue.quick_push (e->src);
3932           }
3933     }
3934 }
3935
3936 /* Dump a dereferences TABLE with heading STR to file F.  */
3937
3938 static void
3939 dump_dereferences_table (FILE *f, const char *str, HOST_WIDE_INT *table)
3940 {
3941   basic_block bb;
3942
3943   fprintf (dump_file, str);
3944   FOR_BB_BETWEEN (bb, ENTRY_BLOCK_PTR_FOR_FN (cfun),
3945                   EXIT_BLOCK_PTR_FOR_FN (cfun), next_bb)
3946     {
3947       fprintf (f, "%4i  %i   ", bb->index, bitmap_bit_p (final_bbs, bb->index));
3948       if (bb != EXIT_BLOCK_PTR_FOR_FN (cfun))
3949         {
3950           int i;
3951           for (i = 0; i < func_param_count; i++)
3952             {
3953               int idx = bb->index * func_param_count + i;
3954               fprintf (f, " %4" HOST_WIDE_INT_PRINT "d", table[idx]);
3955             }
3956         }
3957       fprintf (f, "\n");
3958     }
3959   fprintf (dump_file, "\n");
3960 }
3961
3962 /* Determine what (parts of) parameters passed by reference that are not
3963    assigned to are not certainly dereferenced in this function and thus the
3964    dereferencing cannot be safely moved to the caller without potentially
3965    introducing a segfault.  Mark such REPRESENTATIVES as
3966    grp_not_necessarilly_dereferenced.
3967
3968    The dereferenced maximum "distance," i.e. the offset + size of the accessed
3969    part is calculated rather than simple booleans are calculated for each
3970    pointer parameter to handle cases when only a fraction of the whole
3971    aggregate is allocated (see testsuite/gcc.c-torture/execute/ipa-sra-2.c for
3972    an example).
3973
3974    The maximum dereference distances for each pointer parameter and BB are
3975    already stored in bb_dereference.  This routine simply propagates these
3976    values upwards by propagate_dereference_distances and then compares the
3977    distances of individual parameters in the ENTRY BB to the equivalent
3978    distances of each representative of a (fraction of a) parameter.  */
3979
3980 static void
3981 analyze_caller_dereference_legality (vec<access_p> representatives)
3982 {
3983   int i;
3984
3985   if (dump_file && (dump_flags & TDF_DETAILS))
3986     dump_dereferences_table (dump_file,
3987                              "Dereference table before propagation:\n",
3988                              bb_dereferences);
3989
3990   propagate_dereference_distances ();
3991
3992   if (dump_file && (dump_flags & TDF_DETAILS))
3993     dump_dereferences_table (dump_file,
3994                              "Dereference table after propagation:\n",
3995                              bb_dereferences);
3996
3997   for (i = 0; i < func_param_count; i++)
3998     {
3999       struct access *repr = representatives[i];
4000       int idx = ENTRY_BLOCK_PTR_FOR_FN (cfun)->index * func_param_count + i;
4001
4002       if (!repr || no_accesses_p (repr))
4003         continue;
4004
4005       do
4006         {
4007           if ((repr->offset + repr->size) > bb_dereferences[idx])
4008             repr->grp_not_necessarilly_dereferenced = 1;
4009           repr = repr->next_grp;
4010         }
4011       while (repr);
4012     }
4013 }
4014
4015 /* Return the representative access for the parameter declaration PARM if it is
4016    a scalar passed by reference which is not written to and the pointer value
4017    is not used directly.  Thus, if it is legal to dereference it in the caller
4018    and we can rule out modifications through aliases, such parameter should be
4019    turned into one passed by value.  Return NULL otherwise.  */
4020
4021 static struct access *
4022 unmodified_by_ref_scalar_representative (tree parm)
4023 {
4024   int i, access_count;
4025   struct access *repr;
4026   vec<access_p> *access_vec;
4027
4028   access_vec = get_base_access_vector (parm);
4029   gcc_assert (access_vec);
4030   repr = (*access_vec)[0];
4031   if (repr->write)
4032     return NULL;
4033   repr->group_representative = repr;
4034
4035   access_count = access_vec->length ();
4036   for (i = 1; i < access_count; i++)
4037     {
4038       struct access *access = (*access_vec)[i];
4039       if (access->write)
4040         return NULL;
4041       access->group_representative = repr;
4042       access->next_sibling = repr->next_sibling;
4043       repr->next_sibling = access;
4044     }
4045
4046   repr->grp_read = 1;
4047   repr->grp_scalar_ptr = 1;
4048   return repr;
4049 }
4050
4051 /* Return true iff this ACCESS precludes IPA-SRA of the parameter it is
4052    associated with.  REQ_ALIGN is the minimum required alignment.  */
4053
4054 static bool
4055 access_precludes_ipa_sra_p (struct access *access, unsigned int req_align)
4056 {
4057   unsigned int exp_align;
4058   /* Avoid issues such as the second simple testcase in PR 42025.  The problem
4059      is incompatible assign in a call statement (and possibly even in asm
4060      statements).  This can be relaxed by using a new temporary but only for
4061      non-TREE_ADDRESSABLE types and is probably not worth the complexity. (In
4062      intraprocedural SRA we deal with this by keeping the old aggregate around,
4063      something we cannot do in IPA-SRA.)  */
4064   if (access->write
4065       && (is_gimple_call (access->stmt)
4066           || gimple_code (access->stmt) == GIMPLE_ASM))
4067     return true;
4068
4069   exp_align = get_object_alignment (access->expr);
4070   if (exp_align < req_align)
4071     return true;
4072
4073   return false;
4074 }
4075
4076
4077 /* Sort collected accesses for parameter PARM, identify representatives for
4078    each accessed region and link them together.  Return NULL if there are
4079    different but overlapping accesses, return the special ptr value meaning
4080    there are no accesses for this parameter if that is the case and return the
4081    first representative otherwise.  Set *RO_GRP if there is a group of accesses
4082    with only read (i.e. no write) accesses.  */
4083
4084 static struct access *
4085 splice_param_accesses (tree parm, bool *ro_grp)
4086 {
4087   int i, j, access_count, group_count;
4088   int agg_size, total_size = 0;
4089   struct access *access, *res, **prev_acc_ptr = &res;
4090   vec<access_p> *access_vec;
4091
4092   access_vec = get_base_access_vector (parm);
4093   if (!access_vec)
4094     return &no_accesses_representant;
4095   access_count = access_vec->length ();
4096
4097   access_vec->qsort (compare_access_positions);
4098
4099   i = 0;
4100   total_size = 0;
4101   group_count = 0;
4102   while (i < access_count)
4103     {
4104       bool modification;
4105       tree a1_alias_type;
4106       access = (*access_vec)[i];
4107       modification = access->write;
4108       if (access_precludes_ipa_sra_p (access, TYPE_ALIGN (access->type)))
4109         return NULL;
4110       a1_alias_type = reference_alias_ptr_type (access->expr);
4111
4112       /* Access is about to become group representative unless we find some
4113          nasty overlap which would preclude us from breaking this parameter
4114          apart. */
4115
4116       j = i + 1;
4117       while (j < access_count)
4118         {
4119           struct access *ac2 = (*access_vec)[j];
4120           if (ac2->offset != access->offset)
4121             {
4122               /* All or nothing law for parameters. */
4123               if (access->offset + access->size > ac2->offset)
4124                 return NULL;
4125               else
4126                 break;
4127             }
4128           else if (ac2->size != access->size)
4129             return NULL;
4130
4131           if (access_precludes_ipa_sra_p (ac2, TYPE_ALIGN (access->type))
4132               || (ac2->type != access->type
4133                   && (TREE_ADDRESSABLE (ac2->type)
4134                       || TREE_ADDRESSABLE (access->type)))
4135               || (reference_alias_ptr_type (ac2->expr) != a1_alias_type))
4136             return NULL;
4137
4138           modification |= ac2->write;
4139           ac2->group_representative = access;
4140           ac2->next_sibling = access->next_sibling;
4141           access->next_sibling = ac2;
4142           j++;
4143         }
4144
4145       group_count++;
4146       access->grp_maybe_modified = modification;
4147       if (!modification)
4148         *ro_grp = true;
4149       *prev_acc_ptr = access;
4150       prev_acc_ptr = &access->next_grp;
4151       total_size += access->size;
4152       i = j;
4153     }
4154
4155   if (POINTER_TYPE_P (TREE_TYPE (parm)))
4156     agg_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))));
4157   else
4158     agg_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm)));
4159   if (total_size >= agg_size)
4160     return NULL;
4161
4162   gcc_assert (group_count > 0);
4163   return res;
4164 }
4165
4166 /* Decide whether parameters with representative accesses given by REPR should
4167    be reduced into components.  */
4168
4169 static int
4170 decide_one_param_reduction (struct access *repr)
4171 {
4172   int total_size, cur_parm_size, agg_size, new_param_count, parm_size_limit;
4173   bool by_ref;
4174   tree parm;
4175
4176   parm = repr->base;
4177   cur_parm_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (parm)));
4178   gcc_assert (cur_parm_size > 0);
4179
4180   if (POINTER_TYPE_P (TREE_TYPE (parm)))
4181     {
4182       by_ref = true;
4183       agg_size = tree_to_uhwi (TYPE_SIZE (TREE_TYPE (TREE_TYPE (parm))));
4184     }
4185   else
4186     {
4187       by_ref = false;
4188       agg_size = cur_parm_size;
4189     }
4190
4191   if (dump_file)
4192     {
4193       struct access *acc;
4194       fprintf (dump_file, "Evaluating PARAM group sizes for ");
4195       print_generic_expr (dump_file, parm, 0);
4196       fprintf (dump_file, " (UID: %u): \n", DECL_UID (parm));
4197       for (acc = repr; acc; acc = acc->next_grp)
4198         dump_access (dump_file, acc, true);
4199     }
4200
4201   total_size = 0;
4202   new_param_count = 0;
4203
4204   for (; repr; repr = repr->next_grp)
4205     {
4206       gcc_assert (parm == repr->base);
4207
4208       /* Taking the address of a non-addressable field is verboten.  */
4209       if (by_ref && repr->non_addressable)
4210         return 0;
4211
4212       /* Do not decompose a non-BLKmode param in a way that would
4213          create BLKmode params.  Especially for by-reference passing
4214          (thus, pointer-type param) this is hardly worthwhile.  */
4215       if (DECL_MODE (parm) != BLKmode
4216           && TYPE_MODE (repr->type) == BLKmode)
4217         return 0;
4218
4219       if (!by_ref || (!repr->grp_maybe_modified
4220                       && !repr->grp_not_necessarilly_dereferenced))
4221         total_size += repr->size;
4222       else
4223         total_size += cur_parm_size;
4224
4225       new_param_count++;
4226     }
4227
4228   gcc_assert (new_param_count > 0);
4229
4230   if (optimize_function_for_size_p (cfun))
4231     parm_size_limit = cur_parm_size;
4232   else
4233     parm_size_limit = (PARAM_VALUE (PARAM_IPA_SRA_PTR_GROWTH_FACTOR)
4234                        * cur_parm_size);
4235
4236   if (total_size < agg_size
4237       && total_size <= parm_size_limit)
4238     {
4239       if (dump_file)
4240         fprintf (dump_file, "    ....will be split into %i components\n",
4241                  new_param_count);
4242       return new_param_count;
4243     }
4244   else
4245     return 0;
4246 }
4247
4248 /* The order of the following enums is important, we need to do extra work for
4249    UNUSED_PARAMS, BY_VAL_ACCESSES and UNMODIF_BY_REF_ACCESSES.  */
4250 enum ipa_splicing_result { NO_GOOD_ACCESS, UNUSED_PARAMS, BY_VAL_ACCESSES,
4251                           MODIF_BY_REF_ACCESSES, UNMODIF_BY_REF_ACCESSES };
4252
4253 /* Identify representatives of all accesses to all candidate parameters for
4254    IPA-SRA.  Return result based on what representatives have been found. */
4255
4256 static enum ipa_splicing_result
4257 splice_all_param_accesses (vec<access_p> &representatives)
4258 {
4259   enum ipa_splicing_result result = NO_GOOD_ACCESS;
4260   tree parm;
4261   struct access *repr;
4262
4263   representatives.create (func_param_count);
4264
4265   for (parm = DECL_ARGUMENTS (current_function_decl);
4266        parm;
4267        parm = DECL_CHAIN (parm))
4268     {
4269       if (is_unused_scalar_param (parm))
4270         {
4271           representatives.quick_push (&no_accesses_representant);
4272           if (result == NO_GOOD_ACCESS)
4273             result = UNUSED_PARAMS;
4274         }
4275       else if (POINTER_TYPE_P (TREE_TYPE (parm))
4276                && is_gimple_reg_type (TREE_TYPE (TREE_TYPE (parm)))
4277                && bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
4278         {
4279           repr = unmodified_by_ref_scalar_representative (parm);
4280           representatives.quick_push (repr);
4281           if (repr)
4282             result = UNMODIF_BY_REF_ACCESSES;
4283         }
4284       else if (bitmap_bit_p (candidate_bitmap, DECL_UID (parm)))
4285         {
4286           bool ro_grp = false;
4287           repr = splice_param_accesses (parm, &ro_grp);
4288           representatives.quick_push (repr);
4289
4290           if (repr && !no_accesses_p (repr))
4291             {
4292               if (POINTER_TYPE_P (TREE_TYPE (parm)))
4293                 {
4294                   if (ro_grp)
4295                     result = UNMODIF_BY_REF_ACCESSES;
4296                   else if (result < MODIF_BY_REF_ACCESSES)
4297                     result = MODIF_BY_REF_ACCESSES;
4298                 }
4299               else if (result < BY_VAL_ACCESSES)
4300                 result = BY_VAL_ACCESSES;
4301             }
4302           else if (no_accesses_p (repr) && (result == NO_GOOD_ACCESS))
4303             result = UNUSED_PARAMS;
4304         }
4305       else
4306         representatives.quick_push (NULL);
4307     }
4308
4309   if (result == NO_GOOD_ACCESS)
4310     {
4311       representatives.release ();
4312       return NO_GOOD_ACCESS;
4313     }
4314
4315   return result;
4316 }
4317
4318 /* Return the index of BASE in PARMS.  Abort if it is not found.  */
4319
4320 static inline int
4321 get_param_index (tree base, vec<tree> parms)
4322 {
4323   int i, len;
4324
4325   len = parms.length ();
4326   for (i = 0; i < len; i++)
4327     if (parms[i] == base)
4328       return i;
4329   gcc_unreachable ();
4330 }
4331
4332 /* Convert the decisions made at the representative level into compact
4333    parameter adjustments.  REPRESENTATIVES are pointers to first
4334    representatives of each param accesses, ADJUSTMENTS_COUNT is the expected
4335    final number of adjustments.  */
4336
4337 static ipa_parm_adjustment_vec
4338 turn_representatives_into_adjustments (vec<access_p> representatives,
4339                                        int adjustments_count)
4340 {
4341   vec<tree> parms;
4342   ipa_parm_adjustment_vec adjustments;
4343   tree parm;
4344   int i;
4345
4346   gcc_assert (adjustments_count > 0);
4347   parms = ipa_get_vector_of_formal_parms (current_function_decl);
4348   adjustments.create (adjustments_count);
4349   parm = DECL_ARGUMENTS (current_function_decl);
4350   for (i = 0; i < func_param_count; i++, parm = DECL_CHAIN (parm))
4351     {
4352       struct access *repr = representatives[i];
4353
4354       if (!repr || no_accesses_p (repr))
4355         {
4356           struct ipa_parm_adjustment adj;
4357
4358           memset (&adj, 0, sizeof (adj));
4359           adj.base_index = get_param_index (parm, parms);
4360           adj.base = parm;
4361           if (!repr)
4362             adj.op = IPA_PARM_OP_COPY;
4363           else
4364             adj.op = IPA_PARM_OP_REMOVE;
4365           adj.arg_prefix = "ISRA";
4366           adjustments.quick_push (adj);
4367         }
4368       else
4369         {
4370           struct ipa_parm_adjustment adj;
4371           int index = get_param_index (parm, parms);
4372
4373           for (; repr; repr = repr->next_grp)
4374             {
4375               memset (&adj, 0, sizeof (adj));
4376               gcc_assert (repr->base == parm);
4377               adj.base_index = index;
4378               adj.base = repr->base;
4379               adj.type = repr->type;
4380               adj.alias_ptr_type = reference_alias_ptr_type (repr->expr);
4381               adj.offset = repr->offset;
4382               adj.by_ref = (POINTER_TYPE_P (TREE_TYPE (repr->base))
4383                             && (repr->grp_maybe_modified
4384                                 || repr->grp_not_necessarilly_dereferenced));
4385               adj.arg_prefix = "ISRA";
4386               adjustments.quick_push (adj);
4387             }
4388         }
4389     }
4390   parms.release ();
4391   return adjustments;
4392 }
4393
4394 /* Analyze the collected accesses and produce a plan what to do with the
4395    parameters in the form of adjustments, NULL meaning nothing.  */
4396
4397 static ipa_parm_adjustment_vec
4398 analyze_all_param_acesses (void)
4399 {
4400   enum ipa_splicing_result repr_state;
4401   bool proceed = false;
4402   int i, adjustments_count = 0;
4403   vec<access_p> representatives;
4404   ipa_parm_adjustment_vec adjustments;
4405
4406   repr_state = splice_all_param_accesses (representatives);
4407   if (repr_state == NO_GOOD_ACCESS)
4408     return ipa_parm_adjustment_vec ();
4409
4410   /* If there are any parameters passed by reference which are not modified
4411      directly, we need to check whether they can be modified indirectly.  */
4412   if (repr_state == UNMODIF_BY_REF_ACCESSES)
4413     {
4414       analyze_caller_dereference_legality (representatives);
4415       analyze_modified_params (representatives);
4416     }
4417
4418   for (i = 0; i < func_param_count; i++)
4419     {
4420       struct access *repr = representatives[i];
4421
4422       if (repr && !no_accesses_p (repr))
4423         {
4424           if (repr->grp_scalar_ptr)
4425             {
4426               adjustments_count++;
4427               if (repr->grp_not_necessarilly_dereferenced
4428                   || repr->grp_maybe_modified)
4429                 representatives[i] = NULL;
4430               else
4431                 {
4432                   proceed = true;
4433                   sra_stats.scalar_by_ref_to_by_val++;
4434                 }
4435             }
4436           else
4437             {
4438               int new_components = decide_one_param_reduction (repr);
4439
4440               if (new_components == 0)
4441                 {
4442                   representatives[i] = NULL;
4443                   adjustments_count++;
4444                 }
4445               else
4446                 {
4447                   adjustments_count += new_components;
4448                   sra_stats.aggregate_params_reduced++;
4449                   sra_stats.param_reductions_created += new_components;
4450                   proceed = true;
4451                 }
4452             }
4453         }
4454       else
4455         {
4456           if (no_accesses_p (repr))
4457             {
4458               proceed = true;
4459               sra_stats.deleted_unused_parameters++;
4460             }
4461           adjustments_count++;
4462         }
4463     }
4464
4465   if (!proceed && dump_file)
4466     fprintf (dump_file, "NOT proceeding to change params.\n");
4467
4468   if (proceed)
4469     adjustments = turn_representatives_into_adjustments (representatives,
4470                                                          adjustments_count);
4471   else
4472     adjustments = ipa_parm_adjustment_vec ();
4473
4474   representatives.release ();
4475   return adjustments;
4476 }
4477
4478 /* If a parameter replacement identified by ADJ does not yet exist in the form
4479    of declaration, create it and record it, otherwise return the previously
4480    created one.  */
4481
4482 static tree
4483 get_replaced_param_substitute (struct ipa_parm_adjustment *adj)
4484 {
4485   tree repl;
4486   if (!adj->new_ssa_base)
4487     {
4488       char *pretty_name = make_fancy_name (adj->base);
4489
4490       repl = create_tmp_reg (TREE_TYPE (adj->base), "ISR");
4491       DECL_NAME (repl) = get_identifier (pretty_name);
4492       obstack_free (&name_obstack, pretty_name);
4493
4494       adj->new_ssa_base = repl;
4495     }
4496   else
4497     repl = adj->new_ssa_base;
4498   return repl;
4499 }
4500
4501 /* Find the first adjustment for a particular parameter BASE in a vector of
4502    ADJUSTMENTS which is not a copy_param.  Return NULL if there is no such
4503    adjustment. */
4504
4505 static struct ipa_parm_adjustment *
4506 get_adjustment_for_base (ipa_parm_adjustment_vec adjustments, tree base)
4507 {
4508   int i, len;
4509
4510   len = adjustments.length ();
4511   for (i = 0; i < len; i++)
4512     {
4513       struct ipa_parm_adjustment *adj;
4514
4515       adj = &adjustments[i];
4516       if (adj->op != IPA_PARM_OP_COPY && adj->base == base)
4517         return adj;
4518     }
4519
4520   return NULL;
4521 }
4522
4523 /* If the statement STMT defines an SSA_NAME of a parameter which is to be
4524    removed because its value is not used, replace the SSA_NAME with a one
4525    relating to a created VAR_DECL together all of its uses and return true.
4526    ADJUSTMENTS is a pointer to an adjustments vector.  */
4527
4528 static bool
4529 replace_removed_params_ssa_names (gimple stmt,
4530                                   ipa_parm_adjustment_vec adjustments)
4531 {
4532   struct ipa_parm_adjustment *adj;
4533   tree lhs, decl, repl, name;
4534
4535   if (gimple_code (stmt) == GIMPLE_PHI)
4536     lhs = gimple_phi_result (stmt);
4537   else if (is_gimple_assign (stmt))
4538     lhs = gimple_assign_lhs (stmt);
4539   else if (is_gimple_call (stmt))
4540     lhs = gimple_call_lhs (stmt);
4541   else
4542     gcc_unreachable ();
4543
4544   if (TREE_CODE (lhs) != SSA_NAME)
4545     return false;
4546
4547   decl = SSA_NAME_VAR (lhs);
4548   if (decl == NULL_TREE
4549       || TREE_CODE (decl) != PARM_DECL)
4550     return false;
4551
4552   adj = get_adjustment_for_base (adjustments, decl);
4553   if (!adj)
4554     return false;
4555
4556   repl = get_replaced_param_substitute (adj);
4557   name = make_ssa_name (repl, stmt);
4558
4559   if (dump_file)
4560     {
4561       fprintf (dump_file, "replacing an SSA name of a removed param ");
4562       print_generic_expr (dump_file, lhs, 0);
4563       fprintf (dump_file, " with ");
4564       print_generic_expr (dump_file, name, 0);
4565       fprintf (dump_file, "\n");
4566     }
4567
4568   if (is_gimple_assign (stmt))
4569     gimple_assign_set_lhs (stmt, name);
4570   else if (is_gimple_call (stmt))
4571     gimple_call_set_lhs (stmt, name);
4572   else
4573     gimple_phi_set_result (as_a <gphi *> (stmt), name);
4574
4575   replace_uses_by (lhs, name);
4576   release_ssa_name (lhs);
4577   return true;
4578 }
4579
4580 /* If the statement STMT contains any expressions that need to replaced with a
4581    different one as noted by ADJUSTMENTS, do so.  Handle any potential type
4582    incompatibilities (GSI is used to accommodate conversion statements and must
4583    point to the statement).  Return true iff the statement was modified.  */
4584
4585 static bool
4586 sra_ipa_modify_assign (gimple stmt, gimple_stmt_iterator *gsi,
4587                        ipa_parm_adjustment_vec adjustments)
4588 {
4589   tree *lhs_p, *rhs_p;
4590   bool any;
4591
4592   if (!gimple_assign_single_p (stmt))
4593     return false;
4594
4595   rhs_p = gimple_assign_rhs1_ptr (stmt);
4596   lhs_p = gimple_assign_lhs_ptr (stmt);
4597
4598   any = ipa_modify_expr (rhs_p, false, adjustments);
4599   any |= ipa_modify_expr (lhs_p, false, adjustments);
4600   if (any)
4601     {
4602       tree new_rhs = NULL_TREE;
4603
4604       if (!useless_type_conversion_p (TREE_TYPE (*lhs_p), TREE_TYPE (*rhs_p)))
4605         {
4606           if (TREE_CODE (*rhs_p) == CONSTRUCTOR)
4607             {
4608               /* V_C_Es of constructors can cause trouble (PR 42714).  */
4609               if (is_gimple_reg_type (TREE_TYPE (*lhs_p)))
4610                 *rhs_p = build_zero_cst (TREE_TYPE (*lhs_p));
4611               else
4612                 *rhs_p = build_constructor (TREE_TYPE (*lhs_p),
4613                                             NULL);
4614             }
4615           else
4616             new_rhs = fold_build1_loc (gimple_location (stmt),
4617                                        VIEW_CONVERT_EXPR, TREE_TYPE (*lhs_p),
4618                                        *rhs_p);
4619         }
4620       else if (REFERENCE_CLASS_P (*rhs_p)
4621                && is_gimple_reg_type (TREE_TYPE (*lhs_p))
4622                && !is_gimple_reg (*lhs_p))
4623         /* This can happen when an assignment in between two single field
4624            structures is turned into an assignment in between two pointers to
4625            scalars (PR 42237).  */
4626         new_rhs = *rhs_p;
4627
4628       if (new_rhs)
4629         {
4630           tree tmp = force_gimple_operand_gsi (gsi, new_rhs, true, NULL_TREE,
4631                                                true, GSI_SAME_STMT);
4632
4633           gimple_assign_set_rhs_from_tree (gsi, tmp);
4634         }
4635
4636       return true;
4637     }
4638
4639   return false;
4640 }
4641
4642 /* Traverse the function body and all modifications as described in
4643    ADJUSTMENTS.  Return true iff the CFG has been changed.  */
4644
4645 bool
4646 ipa_sra_modify_function_body (ipa_parm_adjustment_vec adjustments)
4647 {
4648   bool cfg_changed = false;
4649   basic_block bb;
4650
4651   FOR_EACH_BB_FN (bb, cfun)
4652     {
4653       gimple_stmt_iterator gsi;
4654
4655       for (gsi = gsi_start_phis (bb); !gsi_end_p (gsi); gsi_next (&gsi))
4656         replace_removed_params_ssa_names (gsi_stmt (gsi), adjustments);
4657
4658       gsi = gsi_start_bb (bb);
4659       while (!gsi_end_p (gsi))
4660         {
4661           gimple stmt = gsi_stmt (gsi);
4662           bool modified = false;
4663           tree *t;
4664           unsigned i;
4665
4666           switch (gimple_code (stmt))
4667             {
4668             case GIMPLE_RETURN:
4669               t = gimple_return_retval_ptr (as_a <greturn *> (stmt));
4670               if (*t != NULL_TREE)
4671                 modified |= ipa_modify_expr (t, true, adjustments);
4672               break;
4673
4674             case GIMPLE_ASSIGN:
4675               modified |= sra_ipa_modify_assign (stmt, &gsi, adjustments);
4676               modified |= replace_removed_params_ssa_names (stmt, adjustments);
4677               break;
4678
4679             case GIMPLE_CALL:
4680               /* Operands must be processed before the lhs.  */
4681               for (i = 0; i < gimple_call_num_args (stmt); i++)
4682                 {
4683                   t = gimple_call_arg_ptr (stmt, i);
4684                   modified |= ipa_modify_expr (t, true, adjustments);
4685                 }
4686
4687               if (gimple_call_lhs (stmt))
4688                 {
4689                   t = gimple_call_lhs_ptr (stmt);
4690                   modified |= ipa_modify_expr (t, false, adjustments);
4691                   modified |= replace_removed_params_ssa_names (stmt,
4692                                                                 adjustments);
4693                 }
4694               break;
4695
4696             case GIMPLE_ASM:
4697               {
4698                 gasm *asm_stmt = as_a <gasm *> (stmt);
4699                 for (i = 0; i < gimple_asm_ninputs (asm_stmt); i++)
4700                   {
4701                     t = &TREE_VALUE (gimple_asm_input_op (asm_stmt, i));
4702                     modified |= ipa_modify_expr (t, true, adjustments);
4703                   }
4704                 for (i = 0; i < gimple_asm_noutputs (asm_stmt); i++)
4705                   {
4706                     t = &TREE_VALUE (gimple_asm_output_op (asm_stmt, i));
4707                     modified |= ipa_modify_expr (t, false, adjustments);
4708                   }
4709               }
4710               break;
4711
4712             default:
4713               break;
4714             }
4715
4716           if (modified)
4717             {
4718               update_stmt (stmt);
4719               if (maybe_clean_eh_stmt (stmt)
4720                   && gimple_purge_dead_eh_edges (gimple_bb (stmt)))
4721                 cfg_changed = true;
4722             }
4723           gsi_next (&gsi);
4724         }
4725     }
4726
4727   return cfg_changed;
4728 }
4729
4730 /* Call gimple_debug_bind_reset_value on all debug statements describing
4731    gimple register parameters that are being removed or replaced.  */
4732
4733 static void
4734 sra_ipa_reset_debug_stmts (ipa_parm_adjustment_vec adjustments)
4735 {
4736   int i, len;
4737   gimple_stmt_iterator *gsip = NULL, gsi;
4738
4739   if (MAY_HAVE_DEBUG_STMTS && single_succ_p (ENTRY_BLOCK_PTR_FOR_FN (cfun)))
4740     {
4741       gsi = gsi_after_labels (single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)));
4742       gsip = &gsi;
4743     }
4744   len = adjustments.length ();
4745   for (i = 0; i < len; i++)
4746     {
4747       struct ipa_parm_adjustment *adj;
4748       imm_use_iterator ui;
4749       gimple stmt;
4750       gdebug *def_temp;
4751       tree name, vexpr, copy = NULL_TREE;
4752       use_operand_p use_p;
4753
4754       adj = &adjustments[i];
4755       if (adj->op == IPA_PARM_OP_COPY || !is_gimple_reg (adj->base))
4756         continue;
4757       name = ssa_default_def (cfun, adj->base);
4758       vexpr = NULL;
4759       if (name)
4760         FOR_EACH_IMM_USE_STMT (stmt, ui, name)
4761           {
4762             if (gimple_clobber_p (stmt))
4763               {
4764                 gimple_stmt_iterator cgsi = gsi_for_stmt (stmt);
4765                 unlink_stmt_vdef (stmt);
4766                 gsi_remove (&cgsi, true);
4767                 release_defs (stmt);
4768                 continue;
4769               }
4770             /* All other users must have been removed by
4771                ipa_sra_modify_function_body.  */
4772             gcc_assert (is_gimple_debug (stmt));
4773             if (vexpr == NULL && gsip != NULL)
4774               {
4775                 gcc_assert (TREE_CODE (adj->base) == PARM_DECL);
4776                 vexpr = make_node (DEBUG_EXPR_DECL);
4777                 def_temp = gimple_build_debug_source_bind (vexpr, adj->base,
4778                                                            NULL);
4779                 DECL_ARTIFICIAL (vexpr) = 1;
4780                 TREE_TYPE (vexpr) = TREE_TYPE (name);
4781                 DECL_MODE (vexpr) = DECL_MODE (adj->base);
4782                 gsi_insert_before (gsip, def_temp, GSI_SAME_STMT);
4783               }
4784             if (vexpr)
4785               {
4786                 FOR_EACH_IMM_USE_ON_STMT (use_p, ui)
4787                   SET_USE (use_p, vexpr);
4788               }
4789             else
4790               gimple_debug_bind_reset_value (stmt);
4791             update_stmt (stmt);
4792           }
4793       /* Create a VAR_DECL for debug info purposes.  */
4794       if (!DECL_IGNORED_P (adj->base))
4795         {
4796           copy = build_decl (DECL_SOURCE_LOCATION (current_function_decl),
4797                              VAR_DECL, DECL_NAME (adj->base),
4798                              TREE_TYPE (adj->base));
4799           if (DECL_PT_UID_SET_P (adj->base))
4800             SET_DECL_PT_UID (copy, DECL_PT_UID (adj->base));
4801           TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (adj->base);
4802           TREE_READONLY (copy) = TREE_READONLY (adj->base);
4803           TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (adj->base);
4804           DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (adj->base);
4805           DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (adj->base);
4806           DECL_IGNORED_P (copy) = DECL_IGNORED_P (adj->base);
4807           DECL_ABSTRACT_ORIGIN (copy) = DECL_ORIGIN (adj->base);
4808           DECL_SEEN_IN_BIND_EXPR_P (copy) = 1;
4809           SET_DECL_RTL (copy, 0);
4810           TREE_USED (copy) = 1;
4811           DECL_CONTEXT (copy) = current_function_decl;
4812           add_local_decl (cfun, copy);
4813           DECL_CHAIN (copy) =
4814             BLOCK_VARS (DECL_INITIAL (current_function_decl));
4815           BLOCK_VARS (DECL_INITIAL (current_function_decl)) = copy;
4816         }
4817       if (gsip != NULL && copy && target_for_debug_bind (adj->base))
4818         {
4819           gcc_assert (TREE_CODE (adj->base) == PARM_DECL);
4820           if (vexpr)
4821             def_temp = gimple_build_debug_bind (copy, vexpr, NULL);
4822           else
4823             def_temp = gimple_build_debug_source_bind (copy, adj->base,
4824                                                        NULL);
4825           gsi_insert_before (gsip, def_temp, GSI_SAME_STMT);
4826         }
4827     }
4828 }
4829
4830 /* Return false if all callers have at least as many actual arguments as there
4831    are formal parameters in the current function and that their types
4832    match.  */
4833
4834 static bool
4835 some_callers_have_mismatched_arguments_p (struct cgraph_node *node,
4836                                           void *data ATTRIBUTE_UNUSED)
4837 {
4838   struct cgraph_edge *cs;
4839   for (cs = node->callers; cs; cs = cs->next_caller)
4840     if (!callsite_arguments_match_p (cs->call_stmt))
4841       return true;
4842
4843   return false;
4844 }
4845
4846 /* Convert all callers of NODE.  */
4847
4848 static bool
4849 convert_callers_for_node (struct cgraph_node *node,
4850                           void *data)
4851 {
4852   ipa_parm_adjustment_vec *adjustments = (ipa_parm_adjustment_vec *) data;
4853   bitmap recomputed_callers = BITMAP_ALLOC (NULL);
4854   struct cgraph_edge *cs;
4855
4856   for (cs = node->callers; cs; cs = cs->next_caller)
4857     {
4858       push_cfun (DECL_STRUCT_FUNCTION (cs->caller->decl));
4859
4860       if (dump_file)
4861         fprintf (dump_file, "Adjusting call %s/%i -> %s/%i\n",
4862                  xstrdup (cs->caller->name ()),
4863                  cs->caller->order,
4864                  xstrdup (cs->callee->name ()),
4865                  cs->callee->order);
4866
4867       ipa_modify_call_arguments (cs, cs->call_stmt, *adjustments);
4868
4869       pop_cfun ();
4870     }
4871
4872   for (cs = node->callers; cs; cs = cs->next_caller)
4873     if (bitmap_set_bit (recomputed_callers, cs->caller->uid)
4874         && gimple_in_ssa_p (DECL_STRUCT_FUNCTION (cs->caller->decl)))
4875       compute_inline_parameters (cs->caller, true);
4876   BITMAP_FREE (recomputed_callers);
4877
4878   return true;
4879 }
4880
4881 /* Convert all callers of NODE to pass parameters as given in ADJUSTMENTS.  */
4882
4883 static void
4884 convert_callers (struct cgraph_node *node, tree old_decl,
4885                  ipa_parm_adjustment_vec adjustments)
4886 {
4887   basic_block this_block;
4888
4889   node->call_for_symbol_thunks_and_aliases (convert_callers_for_node,
4890                                           &adjustments, false);
4891
4892   if (!encountered_recursive_call)
4893     return;
4894
4895   FOR_EACH_BB_FN (this_block, cfun)
4896     {
4897       gimple_stmt_iterator gsi;
4898
4899       for (gsi = gsi_start_bb (this_block); !gsi_end_p (gsi); gsi_next (&gsi))
4900         {
4901           gcall *stmt;
4902           tree call_fndecl;
4903           stmt = dyn_cast <gcall *> (gsi_stmt (gsi));
4904           if (!stmt)
4905             continue;
4906           call_fndecl = gimple_call_fndecl (stmt);
4907           if (call_fndecl == old_decl)
4908             {
4909               if (dump_file)
4910                 fprintf (dump_file, "Adjusting recursive call");
4911               gimple_call_set_fndecl (stmt, node->decl);
4912               ipa_modify_call_arguments (NULL, stmt, adjustments);
4913             }
4914         }
4915     }
4916
4917   return;
4918 }
4919
4920 /* Perform all the modification required in IPA-SRA for NODE to have parameters
4921    as given in ADJUSTMENTS.  Return true iff the CFG has been changed.  */
4922
4923 static bool
4924 modify_function (struct cgraph_node *node, ipa_parm_adjustment_vec adjustments)
4925 {
4926   struct cgraph_node *new_node;
4927   bool cfg_changed;
4928
4929   cgraph_edge::rebuild_edges ();
4930   free_dominance_info (CDI_DOMINATORS);
4931   pop_cfun ();
4932
4933   /* This must be done after rebuilding cgraph edges for node above.
4934      Otherwise any recursive calls to node that are recorded in
4935      redirect_callers will be corrupted.  */
4936   vec<cgraph_edge *> redirect_callers = node->collect_callers ();
4937   new_node = node->create_version_clone_with_body (redirect_callers, NULL,
4938                                                    NULL, false, NULL, NULL,
4939                                                    "isra");
4940   redirect_callers.release ();
4941
4942   push_cfun (DECL_STRUCT_FUNCTION (new_node->decl));
4943   ipa_modify_formal_parameters (current_function_decl, adjustments);
4944   cfg_changed = ipa_sra_modify_function_body (adjustments);
4945   sra_ipa_reset_debug_stmts (adjustments);
4946   convert_callers (new_node, node->decl, adjustments);
4947   new_node->make_local ();
4948   return cfg_changed;
4949 }
4950
4951 /* If NODE has a caller, return true.  */
4952
4953 static bool
4954 has_caller_p (struct cgraph_node *node, void *data ATTRIBUTE_UNUSED)
4955 {
4956   if (node->callers)
4957     return true;
4958   return false;
4959 }
4960
4961 /* Return false the function is apparently unsuitable for IPA-SRA based on it's
4962    attributes, return true otherwise.  NODE is the cgraph node of the current
4963    function.  */
4964
4965 static bool
4966 ipa_sra_preliminary_function_checks (struct cgraph_node *node)
4967 {
4968   if (!node->can_be_local_p ())
4969     {
4970       if (dump_file)
4971         fprintf (dump_file, "Function not local to this compilation unit.\n");
4972       return false;
4973     }
4974
4975   if (!node->local.can_change_signature)
4976     {
4977       if (dump_file)
4978         fprintf (dump_file, "Function can not change signature.\n");
4979       return false;
4980     }
4981
4982   if (!tree_versionable_function_p (node->decl))
4983     {
4984       if (dump_file)
4985         fprintf (dump_file, "Function is not versionable.\n");
4986       return false;
4987     }
4988
4989   if (!opt_for_fn (node->decl, optimize)
4990       || !opt_for_fn (node->decl, flag_ipa_sra))
4991     {
4992       if (dump_file)
4993         fprintf (dump_file, "Function not optimized.\n");
4994       return false;
4995     }
4996
4997   if (DECL_VIRTUAL_P (current_function_decl))
4998     {
4999       if (dump_file)
5000         fprintf (dump_file, "Function is a virtual method.\n");
5001       return false;
5002     }
5003
5004   if ((DECL_COMDAT (node->decl) || DECL_EXTERNAL (node->decl))
5005       && inline_summary (node)->size >= MAX_INLINE_INSNS_AUTO)
5006     {
5007       if (dump_file)
5008         fprintf (dump_file, "Function too big to be made truly local.\n");
5009       return false;
5010     }
5011
5012   if (!node->call_for_symbol_thunks_and_aliases (has_caller_p, NULL, true))
5013     {
5014       if (dump_file)
5015         fprintf (dump_file,
5016                  "Function has no callers in this compilation unit.\n");
5017       return false;
5018     }
5019
5020   if (cfun->stdarg)
5021     {
5022       if (dump_file)
5023         fprintf (dump_file, "Function uses stdarg. \n");
5024       return false;
5025     }
5026
5027   if (TYPE_ATTRIBUTES (TREE_TYPE (node->decl)))
5028     return false;
5029
5030   if (DECL_DISREGARD_INLINE_LIMITS (node->decl))
5031     {
5032       if (dump_file)
5033         fprintf (dump_file, "Always inline function will be inlined "
5034                  "anyway. \n");
5035       return false;
5036     }
5037
5038   return true;
5039 }
5040
5041 /* Perform early interprocedural SRA.  */
5042
5043 static unsigned int
5044 ipa_early_sra (void)
5045 {
5046   struct cgraph_node *node = cgraph_node::get (current_function_decl);
5047   ipa_parm_adjustment_vec adjustments;
5048   int ret = 0;
5049
5050   if (!ipa_sra_preliminary_function_checks (node))
5051     return 0;
5052
5053   sra_initialize ();
5054   sra_mode = SRA_MODE_EARLY_IPA;
5055
5056   if (!find_param_candidates ())
5057     {
5058       if (dump_file)
5059         fprintf (dump_file, "Function has no IPA-SRA candidates.\n");
5060       goto simple_out;
5061     }
5062
5063   if (node->call_for_symbol_thunks_and_aliases
5064        (some_callers_have_mismatched_arguments_p, NULL, true))
5065     {
5066       if (dump_file)
5067         fprintf (dump_file, "There are callers with insufficient number of "
5068                  "arguments or arguments with type mismatches.\n");
5069       goto simple_out;
5070     }
5071
5072   bb_dereferences = XCNEWVEC (HOST_WIDE_INT,
5073                                  func_param_count
5074                                  * last_basic_block_for_fn (cfun));
5075   final_bbs = BITMAP_ALLOC (NULL);
5076
5077   scan_function ();
5078   if (encountered_apply_args)
5079     {
5080       if (dump_file)
5081         fprintf (dump_file, "Function calls  __builtin_apply_args().\n");
5082       goto out;
5083     }
5084
5085   if (encountered_unchangable_recursive_call)
5086     {
5087       if (dump_file)
5088         fprintf (dump_file, "Function calls itself with insufficient "
5089                  "number of arguments.\n");
5090       goto out;
5091     }
5092
5093   adjustments = analyze_all_param_acesses ();
5094   if (!adjustments.exists ())
5095     goto out;
5096   if (dump_file)
5097     ipa_dump_param_adjustments (dump_file, adjustments, current_function_decl);
5098
5099   if (modify_function (node, adjustments))
5100     ret = TODO_update_ssa | TODO_cleanup_cfg;
5101   else
5102     ret = TODO_update_ssa;
5103   adjustments.release ();
5104
5105   statistics_counter_event (cfun, "Unused parameters deleted",
5106                             sra_stats.deleted_unused_parameters);
5107   statistics_counter_event (cfun, "Scalar parameters converted to by-value",
5108                             sra_stats.scalar_by_ref_to_by_val);
5109   statistics_counter_event (cfun, "Aggregate parameters broken up",
5110                             sra_stats.aggregate_params_reduced);
5111   statistics_counter_event (cfun, "Aggregate parameter components created",
5112                             sra_stats.param_reductions_created);
5113
5114  out:
5115   BITMAP_FREE (final_bbs);
5116   free (bb_dereferences);
5117  simple_out:
5118   sra_deinitialize ();
5119   return ret;
5120 }
5121
5122 namespace {
5123
5124 const pass_data pass_data_early_ipa_sra =
5125 {
5126   GIMPLE_PASS, /* type */
5127   "eipa_sra", /* name */
5128   OPTGROUP_NONE, /* optinfo_flags */
5129   TV_IPA_SRA, /* tv_id */
5130   0, /* properties_required */
5131   0, /* properties_provided */
5132   0, /* properties_destroyed */
5133   0, /* todo_flags_start */
5134   TODO_dump_symtab, /* todo_flags_finish */
5135 };
5136
5137 class pass_early_ipa_sra : public gimple_opt_pass
5138 {
5139 public:
5140   pass_early_ipa_sra (gcc::context *ctxt)
5141     : gimple_opt_pass (pass_data_early_ipa_sra, ctxt)
5142   {}
5143
5144   /* opt_pass methods: */
5145   virtual bool gate (function *) { return flag_ipa_sra && dbg_cnt (eipa_sra); }
5146   virtual unsigned int execute (function *) { return ipa_early_sra (); }
5147
5148 }; // class pass_early_ipa_sra
5149
5150 } // anon namespace
5151
5152 gimple_opt_pass *
5153 make_pass_early_ipa_sra (gcc::context *ctxt)
5154 {
5155   return new pass_early_ipa_sra (ctxt);
5156 }