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