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) 2003, 2004 Free Software Foundation, Inc.
   5    Contributed by Diego Novillo <dnovillo@redhat.com>
   6
   7 This file is part of GCC.
   8
   9 GCC is free software; you can redistribute it and/or modify it
  10 under the terms of the GNU General Public License as published by the
  11 Free Software Foundation; either version 2, or (at your option) any
  12 later version.
  13
  14 GCC is distributed in the hope that it will be useful, but WITHOUT
  15 ANY 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 COPYING.  If not, write to the Free
  21 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  22 02111-1307, USA.  */
  23
  24 #include "config.h"
  25 #include "system.h"
  26 #include "coretypes.h"
  27 #include "tm.h"
  28 #include "errors.h"
  29 #include "ggc.h"
  30 #include "tree.h"
  31
  32 /* These RTL headers are needed for basic-block.h.  */
  33 #include "rtl.h"
  34 #include "tm_p.h"
  35 #include "hard-reg-set.h"
  36 #include "basic-block.h"
  37 #include "diagnostic.h"
  38 #include "langhooks.h"
  39 #include "tree-inline.h"
  40 #include "tree-flow.h"
  41 #include "tree-gimple.h"
  42 #include "tree-dump.h"
  43 #include "tree-pass.h"
  44 #include "timevar.h"
  45 #include "flags.h"
  46 #include "bitmap.h"
  47
  48
  49 /* Maximum number of fields that a structure should have to be scalarized.
  50    FIXME  This limit has been arbitrarily set to 5.  Experiment to find a
  51           sensible setting.  */
  52 #define MAX_NFIELDS_FOR_SRA     5
  53
  54 /* Codes indicating how to copy one structure into another.  */
  55 enum sra_copy_mode { SCALAR_SCALAR, FIELD_SCALAR, SCALAR_FIELD };
  56
  57 /* Local functions.  */
  58 static inline bool can_be_scalarized_p (tree);
  59 static inline void insert_edge_copies (tree stmt, basic_block bb);
  60 static tree create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode);
  61 static inline void scalarize_component_ref (tree, tree *tp);
  62 static void scalarize_structures (void);
  63 static void scalarize_stmt (block_stmt_iterator *);
  64 static void scalarize_modify_expr (block_stmt_iterator *);
  65 static void scalarize_call_expr (block_stmt_iterator *);
  66 static void scalarize_asm_expr (block_stmt_iterator *);
  67 static void scalarize_return_expr (block_stmt_iterator *);
  68
  69 /* The set of aggregate variables that are candidates for scalarization.  */
  70 static bitmap sra_candidates;
  71
  72 /* Set of scalarizable PARM_DECLs that need copy-in operations at the
  73    beginning of the function.  */
  74 static bitmap needs_copy_in;
  75
  76 /* This structure holds the mapping between and element of an aggregate
  77    and the scalar replacement variable.  */
  78 struct sra_elt
  79 {
  80   enum tree_code kind;
  81   tree base;
  82   tree field;
  83   tree replace;
  84 };
  85
  86 static htab_t sra_map;
  87
  88 static hashval_t
  89 sra_elt_hash (const void *x)
  90 {
  91   const struct sra_elt *e = x;
  92   hashval_t h = (size_t) e->base * e->kind;
  93   if (e->kind == COMPONENT_REF)
  94     h ^= (size_t) e->field;
  95   return h;
  96 }
  97
  98 static int
  99 sra_elt_eq (const void *x, const void *y)
 100 {
 101   const struct sra_elt *a = x;
 102   const struct sra_elt *b = y;
 103
 104   if (a->kind != b->kind)
 105     return false;
 106   if (a->base != b->base)
 107     return false;
 108   if (a->kind == COMPONENT_REF)
 109     if (a->field != b->field)
 110       return false;
 111
 112   return true;
 113 }
 114
 115 /* Mark all the variables in V_MAY_DEF operands for STMT for renaming.
 116    This becomes necessary when we modify all of a non-scalar.  */
 117
 118 static void
 119 mark_all_v_may_defs (tree stmt)
 120 {
 121   v_may_def_optype v_may_defs;
 122   size_t i, n;
 123
 124   get_stmt_operands (stmt);
 125   v_may_defs = V_MAY_DEF_OPS (stmt_ann (stmt));
 126   n = NUM_V_MAY_DEFS (v_may_defs);
 127
 128   for (i = 0; i < n; i++)
 129     {
 130       tree sym = V_MAY_DEF_RESULT (v_may_defs, i);
 131       bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
 132     }
 133 }
 134
 135 /* Mark all the variables in V_MUST_DEF operands for STMT for renaming.
 136    This becomes necessary when we modify all of a non-scalar.  */
 137
 138 static void
 139 mark_all_v_must_defs (tree stmt)
 140 {
 141   v_must_def_optype v_must_defs;
 142   size_t i, n;
 143
 144   get_stmt_operands (stmt);
 145   v_must_defs = V_MUST_DEF_OPS (stmt_ann (stmt));
 146   n = NUM_V_MUST_DEFS (v_must_defs);
 147
 148   for (i = 0; i < n; i++)
 149     {
 150       tree sym = V_MUST_DEF_OP (v_must_defs, i);
 151       bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
 152     }
 153 }
 154
 155 /* Return true if DECL is an SRA candidate.  */
 156
 157 static bool
 158 is_sra_candidate_decl (tree decl)
 159 {
 160   return DECL_P (decl) && bitmap_bit_p (sra_candidates, var_ann (decl)->uid);
 161 }
 162
 163 /* Return true if EXP is of the form <ref decl>, where REF is one of the
 164    field access references we handle and DECL is an SRA candidate.
 165
 166    Set ALLOW_BIT_FIELD_REF to accept BIT_FIELD_REF as well.  This is
 167    normally false, except when we're trying to work around it.  */
 168
 169 static bool
 170 is_sra_candidate_ref (tree exp, bool allow_bit_field_ref)
 171 {
 172   switch (TREE_CODE (exp))
 173     {
 174     case BIT_FIELD_REF:
 175       if (!allow_bit_field_ref)
 176         break;
 177       /* FALLTHRU */
 178
 179     case COMPONENT_REF:
 180     case REALPART_EXPR:
 181     case IMAGPART_EXPR:
 182       return is_sra_candidate_decl (TREE_OPERAND (exp, 0));
 183
 184     default:
 185       break;
 186     }
 187
 188   return false;
 189 }
 190
 191 /* Return the scalar in SRA_MAP[VAR_IX][FIELD_IX].  If none exists, create
 192    a new scalar with type TYPE.  */
 193
 194 static tree
 195 lookup_scalar (struct sra_elt *key, tree type)
 196 {
 197   struct sra_elt **slot, *res;
 198
 199   slot = (struct sra_elt **) htab_find_slot (sra_map, key, INSERT);
 200   res = *slot;
 201   if (!res)
 202     {
 203       res = xmalloc (sizeof (*res));
 204       *slot = res;
 205       *res = *key;
 206       res->replace = make_rename_temp (type, "SR");
 207
 208       if (DECL_NAME (key->base) && !DECL_IGNORED_P (key->base))
 209         {
 210           char *name = NULL;
 211           switch (key->kind)
 212             {
 213             case COMPONENT_REF:
 214               if (!DECL_NAME (key->field))
 215                 break;
 216               name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
 217                              "$",
 218                              IDENTIFIER_POINTER (DECL_NAME (key->field)),
 219                              NULL);
 220               break;
 221             case REALPART_EXPR:
 222               name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
 223                              "$real", NULL);
 224               break;
 225             case IMAGPART_EXPR:
 226               name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
 227                              "$imag", NULL);
 228               break;
 229             default:
 230               abort ();
 231             }
 232           if (name)
 233             {
 234               DECL_NAME (res->replace) = get_identifier (name);
 235               free (name);
 236             }
 237         }
 238
 239       DECL_SOURCE_LOCATION (res->replace) = DECL_SOURCE_LOCATION (key->base);
 240       TREE_NO_WARNING (res->replace) = TREE_NO_WARNING (key->base);
 241       DECL_ARTIFICIAL (res->replace) = DECL_ARTIFICIAL (key->base);
 242     }
 243
 244   return res->replace;
 245 }
 246
 247
 248 /* Given a structure reference VAR.FIELD, return a scalar representing it.
 249    If no scalar is found, a new one is created and added to the SRA_MAP
 250    matrix.  */
 251
 252 static tree
 253 get_scalar_for_field (tree var, tree field)
 254 {
 255   struct sra_elt key;
 256
 257 #ifdef ENABLE_CHECKING
 258   /* Validate that FIELD actually exists in VAR's type.  */
 259   {
 260     tree f;
 261     for (f = TYPE_FIELDS (TREE_TYPE (var)); f ; f = TREE_CHAIN (f))
 262       if (f == field)
 263         goto found;
 264     abort ();
 265    found:;
 266   }
 267 #endif
 268
 269   key.kind = COMPONENT_REF;
 270   key.base = var;
 271   key.field = field;
 272
 273   return lookup_scalar (&key, TREE_TYPE (field));
 274 }
 275
 276
 277 /* Similarly for the parts of a complex type.  */
 278
 279 static tree
 280 get_scalar_for_complex_part (tree var, enum tree_code part)
 281 {
 282   struct sra_elt key;
 283
 284   key.kind = part;
 285   key.base = var;
 286
 287   return lookup_scalar (&key, TREE_TYPE (TREE_TYPE (var)));
 288 }
 289
 290 /* Return true if the fields of VAR can be replaced by scalar temporaries.
 291    This only happens if VAR is not call-clobbered and it contains less
 292    than MAX_NFIELDS_FOR_SRA scalar fields.  */
 293
 294 static inline bool
 295 can_be_scalarized_p (tree var)
 296 {
 297   tree field, type;
 298   int nfields;
 299
 300   if (!is_gimple_non_addressable (var))
 301     {
 302       if (dump_file && (dump_flags & TDF_DETAILS))
 303         {
 304           fprintf (dump_file, "Cannot scalarize variable ");
 305           print_generic_expr (dump_file, var, dump_flags);
 306           fprintf (dump_file, " because it must live in memory\n");
 307         }
 308       return false;
 309     }
 310
 311   if (TREE_THIS_VOLATILE (var))
 312     {
 313       if (dump_file && (dump_flags & TDF_DETAILS))
 314         {
 315           fprintf (dump_file, "Cannot scalarize variable ");
 316           print_generic_expr (dump_file, var, dump_flags);
 317           fprintf (dump_file, " because it is declared volatile\n");
 318         }
 319       return false;
 320     }
 321
 322   /* Any COMPLEX_TYPE that has reached this point can be scalarized.  */
 323   if (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
 324     return true;
 325
 326   type = TREE_TYPE (var);
 327   nfields = 0;
 328   for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
 329     {
 330       if (TREE_CODE (field) != FIELD_DECL)
 331         continue;
 332
 333       /* FIXME: We really should recurse down the type hierarchy and
 334          scalarize the fields at the leaves.  */
 335       if (AGGREGATE_TYPE_P (TREE_TYPE (field)))
 336         {
 337           if (dump_file && (dump_flags & TDF_DETAILS))
 338             {
 339               fprintf (dump_file, "Cannot scalarize variable ");
 340               print_generic_expr (dump_file, var, dump_flags);
 341               fprintf (dump_file,
 342                        " because it contains an aggregate type field, ");
 343               print_generic_expr (dump_file, field, dump_flags);
 344               fprintf (dump_file, "\n");
 345             }
 346           return false;
 347         }
 348
 349       /* FIXME: Similarly.  Indeed, considering that we treat complex
 350          as an aggregate, this is exactly the same problem.
 351          Structures with __complex__ fields are tested in the libstdc++
 352          testsuite: 26_numerics/complex_inserters_extractors.cc.  */
 353       if (TREE_CODE (TREE_TYPE (field)) == COMPLEX_TYPE)
 354         {
 355           if (dump_file && (dump_flags & TDF_DETAILS))
 356             {
 357               fprintf (dump_file, "Cannot scalarize variable ");
 358               print_generic_expr (dump_file, var, dump_flags);
 359               fprintf (dump_file,
 360                        " because it contains a __complex__ field, ");
 361               print_generic_expr (dump_file, field, dump_flags);
 362               fprintf (dump_file, "\n");
 363             }
 364           return false;
 365         }
 366
 367       /* FIXME.  We don't scalarize structures with bit fields yet.  To
 368          support this, we should make sure that all the fields fit in one
 369          word and modify every operation done on the scalarized bit fields
 370          to mask them properly.  */
 371       if (DECL_BIT_FIELD (field))
 372         {
 373           if (dump_file && (dump_flags & TDF_DETAILS))
 374             {
 375               fprintf (dump_file, "Cannot scalarize variable ");
 376               print_generic_expr (dump_file, var, dump_flags);
 377               fprintf (dump_file,
 378                        " because it contains a bit-field, ");
 379               print_generic_expr (dump_file, field, dump_flags);
 380               fprintf (dump_file, "\n");
 381             }
 382           return false;
 383         }
 384
 385       nfields++;
 386       if (nfields > MAX_NFIELDS_FOR_SRA)
 387         {
 388           if (dump_file && (dump_flags & TDF_DETAILS))
 389             {
 390               fprintf (dump_file, "Cannot scalarize variable ");
 391               print_generic_expr (dump_file, var, dump_flags);
 392               fprintf (dump_file,
 393                        " because it contains more than %d fields\n",
 394                        MAX_NFIELDS_FOR_SRA);
 395             }
 396           return false;
 397         }
 398     }
 399
 400   /* If the structure had no FIELD_DECLs, then don't bother
 401      scalarizing it.  */
 402   return nfields > 0;
 403 }
 404
 405
 406 /* Replace the COMPONENT_REF, REALPART_EXPR or IMAGPART_EXPR pointed-to by
 407    TP inside STMT with the corresponding scalar replacement from SRA_MAP.  */
 408
 409 static inline void
 410 scalarize_component_ref (tree stmt, tree *tp)
 411 {
 412   tree t = *tp, obj = TREE_OPERAND (t, 0);
 413
 414   /* When scalarizing a function argument, we will need to insert copy-in
 415      operations from the original PARM_DECLs. Note that these copy-in
 416      operations may end up being dead, but we won't know until we rename
 417      the new variables into SSA.  */
 418   if (TREE_CODE (obj) == PARM_DECL)
 419     bitmap_set_bit (needs_copy_in, var_ann (obj)->uid);
 420
 421   switch (TREE_CODE (t))
 422     {
 423     case COMPONENT_REF:
 424       t = get_scalar_for_field (obj, TREE_OPERAND (t, 1));
 425       break;
 426     case REALPART_EXPR:
 427     case IMAGPART_EXPR:
 428       t = get_scalar_for_complex_part (obj, TREE_CODE (t));
 429       break;
 430     default:
 431       abort ();
 432     }
 433
 434   *tp = t;
 435   modify_stmt (stmt);
 436 }
 437
 438
 439 /* Scalarize the structure assignment for the statement pointed by SI_P.  */
 440
 441 static void
 442 scalarize_structure_assignment (block_stmt_iterator *si_p)
 443 {
 444   var_ann_t lhs_ann, rhs_ann;
 445   tree lhs, rhs, list, orig_stmt;
 446   bool lhs_can, rhs_can;
 447
 448   orig_stmt = bsi_stmt (*si_p);
 449   lhs = TREE_OPERAND (orig_stmt, 0);
 450   rhs = TREE_OPERAND (orig_stmt, 1);
 451   list = NULL_TREE;
 452
 453 #if defined ENABLE_CHECKING
 454   if (TREE_CODE (orig_stmt) != MODIFY_EXPR)
 455     abort ();
 456 #endif
 457
 458   /* Remove all type casts from RHS.  This may seem heavy handed but
 459      it's actually safe and it is necessary in the presence of C++
 460      reinterpret_cast<> where structure assignments of different
 461      structures will be present in the IL.  This was the case of PR
 462      13347 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13347) which
 463      had something like this:
 464
 465         struct A f;
 466         struct B g;
 467         f = (struct A)g;
 468
 469      Both 'f' and 'g' were scalarizable, but the presence of the type
 470      cast was causing SRA to not replace the RHS of the assignment
 471      with g's scalar replacements.  Furthermore, the fact that this
 472      assignment reached this point without causing syntax errors means
 473      that the type cast is safe and that a field-by-field assignment
 474      from 'g' into 'f' is the right thing to do.  */
 475   STRIP_NOPS (rhs);
 476
 477   lhs_ann = DECL_P (lhs) ? var_ann (lhs) : NULL;
 478   rhs_ann = DECL_P (rhs) ? var_ann (rhs) : NULL;
 479
 480 #if defined ENABLE_CHECKING
 481   /* Two different variables should not have the same UID.  */
 482   if (lhs_ann
 483       && rhs_ann
 484       && lhs != rhs
 485       && lhs_ann->uid == rhs_ann->uid)
 486     abort ();
 487 #endif
 488
 489   lhs_can = lhs_ann && bitmap_bit_p (sra_candidates, lhs_ann->uid);
 490   rhs_can = rhs_ann && bitmap_bit_p (sra_candidates, rhs_ann->uid);
 491
 492   /* Both LHS and RHS are scalarizable.  */
 493   if (lhs_can && rhs_can)
 494     list = create_scalar_copies (lhs, rhs, SCALAR_SCALAR);
 495
 496   /* Only RHS is scalarizable.  */
 497   else if (rhs_can)
 498     list = create_scalar_copies (lhs, rhs, FIELD_SCALAR);
 499
 500   /* Only LHS is scalarizable.  */
 501   else if (lhs_can)
 502     list = create_scalar_copies (lhs, rhs, SCALAR_FIELD);
 503
 504   /* If neither side is scalarizable, do nothing else.  */
 505   else
 506     return;
 507
 508   /* Set line number information for our replacements.  */
 509   if (EXPR_HAS_LOCATION (orig_stmt))
 510     annotate_all_with_locus (&list, EXPR_LOCATION (orig_stmt));
 511
 512   /* Replace the existing statement with the newly created list of
 513      scalarized copies.  When replacing the original statement, the first
 514      copy replaces it and the remaining copies are inserted either after
 515      the first copy or on the outgoing edges of the original statement's
 516      block.  */
 517   {
 518     tree_stmt_iterator tsi = tsi_start (list);
 519     bsi_replace (si_p, tsi_stmt (tsi), true);
 520     tsi_delink (&tsi);
 521     if (stmt_ends_bb_p (orig_stmt))
 522       insert_edge_copies (list, bb_for_stmt (orig_stmt));
 523     else
 524       bsi_insert_after (si_p, list, BSI_CONTINUE_LINKING);
 525   }
 526 }
 527
 528
 529 /* Traverse all the referenced variables in the program looking for
 530    structures that could be replaced with scalars.  */
 531
 532 static bool
 533 find_candidates_for_sra (void)
 534 {
 535   size_t i;
 536   bool any_set = false;
 537
 538   for (i = 0; i < num_referenced_vars; i++)
 539     {
 540       tree var = referenced_var (i);
 541
 542       if ((TREE_CODE (TREE_TYPE (var)) == RECORD_TYPE
 543            || TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
 544           && can_be_scalarized_p (var))
 545         {
 546           bitmap_set_bit (sra_candidates, var_ann (var)->uid);
 547           any_set = true;
 548         }
 549     }
 550
 551   return any_set;
 552 }
 553
 554
 555 /* Insert STMT on all the outgoing edges out of BB.  Note that if BB
 556    has more than one edge, STMT will be replicated for each edge.  Also,
 557    abnormal edges will be ignored.  */
 558
 559 static inline void
 560 insert_edge_copies (tree stmt, basic_block bb)
 561 {
 562   edge e;
 563   bool first_copy;
 564
 565   first_copy = true;
 566   for (e = bb->succ; e; e = e->succ_next)
 567     {
 568       /* We don't need to insert copies on abnormal edges.  The
 569          value of the scalar replacement is not guaranteed to
 570          be valid through an abnormal edge.  */
 571       if (!(e->flags & EDGE_ABNORMAL))
 572         {
 573           if (first_copy)
 574             {
 575               bsi_insert_on_edge (e, stmt);
 576               first_copy = false;
 577             }
 578           else
 579             bsi_insert_on_edge (e, lhd_unsave_expr_now (stmt));
 580         }
 581     }
 582 }
 583
 584
 585 /* Append a new assignment statement to TSI.  */
 586
 587 static tree
 588 csc_assign (tree_stmt_iterator *tsi, tree lhs, tree rhs)
 589 {
 590   tree stmt = build (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
 591   modify_stmt (stmt);
 592   tsi_link_after (tsi, stmt, TSI_NEW_STMT);
 593   return stmt;
 594 }
 595
 596 /* A subroutine of create_scalar_copies.  Construct a COMPONENT_REF
 597    expression for BASE referencing FIELD.  INDEX is the field index.  */
 598
 599 static tree
 600 csc_build_component_ref (tree base, tree field)
 601 {
 602   switch (TREE_CODE (base))
 603     {
 604     case CONSTRUCTOR:
 605       /* Only appears on RHS.  The only remaining CONSTRUCTORS for
 606          record types that should remain are empty, and imply that
 607          the entire structure should be zeroed.  */
 608       if (CONSTRUCTOR_ELTS (base))
 609         abort ();
 610       return fold_convert (TREE_TYPE (field), integer_zero_node);
 611
 612     default:
 613       /* Avoid sharing BASE when building the different COMPONENT_REFs.
 614          We let the first field have the original version.  */
 615       if (field != TYPE_FIELDS (TREE_TYPE (base)))
 616         base = unshare_expr (base);
 617       break;
 618
 619     case VAR_DECL:
 620     case PARM_DECL:
 621       /* Special case for the above -- decls are always shared.  */
 622       break;
 623     }
 624
 625   return build (COMPONENT_REF, TREE_TYPE (field), base, field);
 626 }
 627
 628 /* Similarly for REALPART_EXPR and IMAGPART_EXPR for complex types.  */
 629
 630 static tree
 631 csc_build_complex_part (tree base, enum tree_code part)
 632 {
 633   switch (TREE_CODE (base))
 634     {
 635     case COMPLEX_CST:
 636       if (part == REALPART_EXPR)
 637         return TREE_REALPART (base);
 638       else
 639         return TREE_IMAGPART (base);
 640
 641     case COMPLEX_EXPR:
 642       if (part == REALPART_EXPR)
 643         return TREE_OPERAND (base, 0);
 644       else
 645         return TREE_OPERAND (base, 1);
 646
 647     default:
 648       /* Avoid sharing BASE when building the different references.
 649          We let the real part have the original version.  */
 650       if (part != REALPART_EXPR)
 651         base = unshare_expr (base);
 652       break;
 653
 654     case VAR_DECL:
 655     case PARM_DECL:
 656       /* Special case for the above -- decls are always shared.  */
 657       break;
 658     }
 659
 660   return build1 (part, TREE_TYPE (TREE_TYPE (base)), base);
 661 }
 662
 663 /* Create and return a list of assignments to perform a scalarized
 664    structure assignment 'LHS = RHS'.  Both LHS and RHS are assumed to be
 665    of an aggregate or complex type.  Three types of copies may be specified:
 666
 667    SCALAR_SCALAR will emit assignments for all the scalar temporaries
 668       corresponding to the fields of LHS and RHS.
 669
 670    FIELD_SCALAR will emit assignments from the scalar replacements of
 671       RHS into each of the fields of the LHS.
 672
 673    SCALAR_FIELD will emit assignments from each field of the RHS into
 674       the scalar replacements of the LHS.  */
 675
 676 static tree
 677 create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode)
 678 {
 679   tree type, list;
 680   tree_stmt_iterator tsi;
 681
 682 #if defined ENABLE_CHECKING
 683   /* Sanity checking.  Check that we are not trying to scalarize a
 684      non-decl.  */
 685   if (!DECL_P (lhs) && (mode == SCALAR_FIELD || mode == SCALAR_SCALAR))
 686     abort ();
 687   if (!DECL_P (rhs) && (mode == FIELD_SCALAR || mode == SCALAR_SCALAR))
 688     abort ();
 689 #endif
 690
 691   type = TREE_TYPE (lhs);
 692   list = alloc_stmt_list ();
 693   tsi = tsi_start (list);
 694
 695   /* VA_ARG_EXPRs have side effects, so we need to copy it first to a
 696      temporary before scalarizing.  FIXME: This should disappear once
 697      VA_ARG_EXPRs are properly lowered.  */
 698   if (TREE_CODE (rhs) == VA_ARG_EXPR)
 699     {
 700       tree stmt, tmp;
 701
 702       /* Add TMP = VA_ARG_EXPR <>  */
 703       tmp = make_rename_temp (TREE_TYPE (rhs), NULL);
 704       stmt = csc_assign (&tsi, tmp, rhs);
 705
 706       /* Mark all the variables in VDEF operands for renaming, because
 707          the VA_ARG_EXPR will now be in a different statement.  */
 708       mark_all_v_may_defs (stmt);
 709       mark_all_v_must_defs (stmt);
 710
 711       /* Set RHS to be the new temporary TMP.  */
 712       rhs = tmp;
 713     }
 714
 715   /* When making *_SCALAR copies from PARM_DECLs, we will need to insert
 716      copy-in operations from the original PARM_DECLs.  Note that these
 717      copy-in operations may end up being dead, but we won't know until
 718      we rename the new variables into SSA.  */
 719   if ((mode == SCALAR_SCALAR || mode == FIELD_SCALAR)
 720       && TREE_CODE (rhs) == PARM_DECL)
 721     bitmap_set_bit (needs_copy_in, var_ann (rhs)->uid);
 722
 723   /* Now create scalar copies for each individual field according to MODE.  */
 724   if (TREE_CODE (type) == COMPLEX_TYPE)
 725     {
 726       /* Create scalar copies of both the real and imaginary parts.  */
 727       tree real_lhs, real_rhs, imag_lhs, imag_rhs;
 728
 729       if (mode == SCALAR_FIELD)
 730         {
 731           real_rhs = csc_build_complex_part (rhs, REALPART_EXPR);
 732           imag_rhs = csc_build_complex_part (rhs, IMAGPART_EXPR);
 733         }
 734       else
 735         {
 736           real_rhs = get_scalar_for_complex_part (rhs, REALPART_EXPR);
 737           imag_rhs = get_scalar_for_complex_part (rhs, IMAGPART_EXPR);
 738         }
 739
 740       if (mode == FIELD_SCALAR)
 741         {
 742           /* In this case we do not need to create but one statement,
 743              since we can create a new complex value whole.  */
 744
 745           if (TREE_CONSTANT (real_rhs) && TREE_CONSTANT (imag_rhs))
 746             rhs = build_complex (type, real_rhs, imag_rhs);
 747           else
 748             rhs = build (COMPLEX_EXPR, type, real_rhs, imag_rhs);
 749           csc_assign (&tsi, lhs, rhs);
 750         }
 751       else
 752         {
 753           real_lhs = get_scalar_for_complex_part (lhs, REALPART_EXPR);
 754           imag_lhs = get_scalar_for_complex_part (lhs, IMAGPART_EXPR);
 755
 756           csc_assign (&tsi, real_lhs, real_rhs);
 757           csc_assign (&tsi, imag_lhs, imag_rhs);
 758         }
 759     }
 760   else
 761     {
 762       tree lf, rf;
 763
 764       /* ??? C++ generates copies between different pointer-to-member
 765          structures of different types.  To combat this, we must track
 766          the field of both the left and right structures, so that we
 767          index the variables with fields of their own type.  */
 768
 769       for (lf = TYPE_FIELDS (type), rf = TYPE_FIELDS (TREE_TYPE (rhs));
 770            lf;
 771            lf = TREE_CHAIN (lf), rf = TREE_CHAIN (rf))
 772         {
 773           tree lhs_var, rhs_var;
 774
 775           /* Only copy FIELD_DECLs.  */
 776           if (TREE_CODE (lf) != FIELD_DECL)
 777             continue;
 778
 779           if (mode == FIELD_SCALAR)
 780             lhs_var = csc_build_component_ref (lhs, lf);
 781           else
 782             lhs_var = get_scalar_for_field (lhs, lf);
 783
 784           if (mode == SCALAR_FIELD)
 785             rhs_var = csc_build_component_ref (rhs, rf);
 786           else
 787             rhs_var = get_scalar_for_field (rhs, rf);
 788
 789           csc_assign (&tsi, lhs_var, rhs_var);
 790         }
 791     }
 792
 793   /* All the scalar copies just created will either create new definitions
 794      or remove existing definitions of LHS, so we need to mark it for
 795      renaming.  */
 796   if (TREE_SIDE_EFFECTS (list))
 797     {
 798       if (mode == SCALAR_FIELD || mode == SCALAR_SCALAR)
 799         {
 800           /* If the LHS has been scalarized, mark it for renaming.  */
 801           bitmap_set_bit (vars_to_rename, var_ann (lhs)->uid);
 802         }
 803       else if (mode == FIELD_SCALAR)
 804         {
 805           /* Otherwise, mark all the symbols in the VDEFs for the last
 806              scalarized statement just created.  Since all the statements
 807              introduce the same VDEFs, we only need to check the last one.  */
 808           mark_all_v_may_defs (tsi_stmt (tsi));
 809           mark_all_v_must_defs (tsi_stmt (tsi));
 810         }
 811       else
 812         abort ();
 813     }
 814
 815   return list;
 816 }
 817
 818 /* A helper function that creates the copies, updates line info,
 819    and emits the code either before or after BSI.  */
 820
 821 static void
 822 emit_scalar_copies (block_stmt_iterator *bsi, tree lhs, tree rhs,
 823                     enum sra_copy_mode mode)
 824 {
 825   tree list = create_scalar_copies (lhs, rhs, mode);
 826   tree stmt = bsi_stmt (*bsi);
 827
 828   if (EXPR_HAS_LOCATION (stmt))
 829     annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
 830
 831   bsi_insert_before (bsi, list, BSI_SAME_STMT);
 832 }
 833
 834 /* Traverse all the statements in the function replacing references to
 835    scalarizable structures with their corresponding scalar temporaries.  */
 836
 837 static void
 838 scalarize_structures (void)
 839 {
 840   basic_block bb;
 841   block_stmt_iterator si;
 842   size_t i;
 843
 844   FOR_EACH_BB (bb)
 845     for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
 846       {
 847         tree stmt;
 848         stmt_ann_t ann;
 849
 850         stmt = bsi_stmt (si);
 851         ann = stmt_ann (stmt);
 852
 853         /* If the statement has no virtual operands, then it doesn't make
 854            structure references that we care about.  */
 855         if (NUM_V_MAY_DEFS (V_MAY_DEF_OPS (ann)) == 0
 856             && NUM_VUSES (VUSE_OPS (ann)) == 0
 857             && NUM_V_MUST_DEFS (V_MUST_DEF_OPS (ann)) == 0)
 858           continue;
 859
 860         /* Structure references may only appear in certain statements.  */
 861         if (TREE_CODE (stmt) != MODIFY_EXPR
 862             && TREE_CODE (stmt) != CALL_EXPR
 863             && TREE_CODE (stmt) != RETURN_EXPR
 864             && TREE_CODE (stmt) != ASM_EXPR)
 865           continue;
 866
 867         scalarize_stmt (&si);
 868       }
 869
 870   /* Initialize the scalar replacements for every structure that is a
 871      function argument.  */
 872   EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i,
 873     {
 874       tree var = referenced_var (i);
 875       tree list = create_scalar_copies (var, var, SCALAR_FIELD);
 876       bsi_insert_on_edge (ENTRY_BLOCK_PTR->succ, list);
 877     });
 878
 879   /* Commit edge insertions.  */
 880   bsi_commit_edge_inserts (NULL);
 881 }
 882
 883
 884 /* Scalarize structure references in the statement pointed by SI_P.  */
 885
 886 static void
 887 scalarize_stmt (block_stmt_iterator *si_p)
 888 {
 889   tree stmt = bsi_stmt (*si_p);
 890
 891   /* Handle assignments.  */
 892   if (TREE_CODE (stmt) == MODIFY_EXPR
 893       && TREE_CODE (TREE_OPERAND (stmt, 1)) != CALL_EXPR)
 894     scalarize_modify_expr (si_p);
 895
 896   /* Handle RETURN_EXPR.  */
 897   else if (TREE_CODE (stmt) == RETURN_EXPR)
 898     scalarize_return_expr (si_p);
 899
 900   /* Handle function calls (note that this must be handled after
 901      MODIFY_EXPR and RETURN_EXPR because a function call can appear in
 902      both).  */
 903   else if (get_call_expr_in (stmt) != NULL_TREE)
 904     scalarize_call_expr (si_p);
 905
 906   /* Handle ASM_EXPRs.  */
 907   else if (TREE_CODE (stmt) == ASM_EXPR)
 908     scalarize_asm_expr (si_p);
 909 }
 910
 911
 912 /* Helper for scalarize_stmt to handle assignments.  */
 913
 914 static void
 915 scalarize_modify_expr (block_stmt_iterator *si_p)
 916 {
 917   tree stmt = bsi_stmt (*si_p);
 918   tree lhs = TREE_OPERAND (stmt, 0);
 919   tree rhs = TREE_OPERAND (stmt, 1);
 920
 921   /* Found AGGREGATE.FIELD = ...  */
 922   if (is_sra_candidate_ref (lhs, false))
 923     {
 924       tree sym;
 925       v_may_def_optype v_may_defs;
 926
 927       scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 0));
 928
 929       /* Mark the LHS to be renamed, as we have just removed the previous
 930          V_MAY_DEF for AGGREGATE.  The statement should have exactly one
 931          V_MAY_DEF for variable AGGREGATE.  */
 932       v_may_defs = STMT_V_MAY_DEF_OPS (stmt);
 933       if (NUM_V_MAY_DEFS (v_may_defs) != 1)
 934         abort ();
 935       sym = SSA_NAME_VAR (V_MAY_DEF_RESULT (v_may_defs, 0));
 936       bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
 937     }
 938
 939   /* Found ... = AGGREGATE.FIELD  */
 940   else if (is_sra_candidate_ref (rhs, false))
 941     scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 1));
 942
 943   /* Found ... = BIT_FIELD_REF <>.  This is similar to a CALL_EXPR, if the
 944      operand of the BIT_FIELD_REF is a scalarizable structure, we need to
 945      copy from its scalar replacements before doing the bitfield operation.
 946
 947      FIXME: BIT_FIELD_REFs are often generated by fold-const.c.  This is
 948      not always desirable because they obfuscate the original predicates,
 949      limiting what the tree optimizers may do.  For instance, in
 950      testsuite/g++.dg/opt/nrv4.C the use of SRA allows the optimizers to
 951      optimize function main() to 'return 0;'.  However, the folder
 952      generates a BIT_FIELD_REF operation for one of the comparisons,
 953      preventing the optimizers from removing all the redundant
 954      operations.  */
 955   else if (is_sra_candidate_ref (rhs, true))
 956     {
 957       tree var = TREE_OPERAND (rhs, 0);
 958       emit_scalar_copies (si_p, var, var, FIELD_SCALAR);
 959     }
 960
 961   /* Found AGGREGATE = ... or ... = AGGREGATE  */
 962   else if (DECL_P (lhs) || DECL_P (rhs))
 963     scalarize_structure_assignment (si_p);
 964 }
 965
 966
 967 /* Scalarize structure references in LIST.  Use DONE to avoid duplicates.  */
 968
 969 static inline void
 970 scalarize_tree_list (tree list, block_stmt_iterator *si_p, bitmap done)
 971 {
 972   tree op;
 973
 974   for (op = list; op; op = TREE_CHAIN (op))
 975     {
 976       tree arg = TREE_VALUE (op);
 977
 978       if (is_sra_candidate_decl (arg))
 979         {
 980           int index = var_ann (arg)->uid;
 981           if (!bitmap_bit_p (done, index))
 982             {
 983               emit_scalar_copies (si_p, arg, arg, FIELD_SCALAR);
 984               bitmap_set_bit (done, index);
 985             }
 986         }
 987       else if (is_sra_candidate_ref (arg, false))
 988         {
 989           tree stmt = bsi_stmt (*si_p);
 990           scalarize_component_ref (stmt, &TREE_VALUE (op));
 991         }
 992     }
 993 }
 994
 995
 996 /* Helper for scalarize_stmt to handle function calls.  */
 997
 998 static void
 999 scalarize_call_expr (block_stmt_iterator *si_p)
1000 {
1001   tree stmt = bsi_stmt (*si_p);
1002   tree call = (TREE_CODE (stmt) == MODIFY_EXPR) ? TREE_OPERAND (stmt, 1) : stmt;
1003   struct bitmap_head_def done_head;
1004
1005   /* First scalarize the arguments.  Order is important, because the copy
1006      operations for the arguments need to go before the call.
1007      Scalarization of the return value needs to go after the call.  */
1008   bitmap_initialize (&done_head, 1);
1009   scalarize_tree_list (TREE_OPERAND (call, 1), si_p, &done_head);
1010   bitmap_clear (&done_head);
1011
1012   /* Scalarize the return value, if any.  */
1013   if (TREE_CODE (stmt) == MODIFY_EXPR)
1014     {
1015       tree var = TREE_OPERAND (stmt, 0);
1016
1017       /* If the LHS of the assignment is a scalarizable structure, insert
1018          copies into the scalar replacements after the call.  */
1019       if (is_sra_candidate_decl (var))
1020         {
1021           tree list = create_scalar_copies (var, var, SCALAR_FIELD);
1022           if (EXPR_HAS_LOCATION (stmt))
1023             annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
1024           if (stmt_ends_bb_p (stmt))
1025             insert_edge_copies (list, bb_for_stmt (stmt));
1026           else
1027             bsi_insert_after (si_p, list, BSI_NEW_STMT);
1028         }
1029     }
1030 }
1031
1032
1033 /* Helper for scalarize_stmt to handle ASM_EXPRs.  */
1034
1035 static void
1036 scalarize_asm_expr (block_stmt_iterator *si_p)
1037 {
1038   tree stmt = bsi_stmt (*si_p);
1039   struct bitmap_head_def done_head;
1040
1041   bitmap_initialize (&done_head, 1);
1042   scalarize_tree_list (ASM_INPUTS (stmt), si_p, &done_head);
1043   scalarize_tree_list (ASM_OUTPUTS (stmt), si_p, &done_head);
1044   bitmap_clear (&done_head);
1045
1046   /* ??? Process outputs after the asm.  */
1047 }
1048
1049
1050 /* Helper for scalarize_stmt to handle return expressions.  */
1051
1052 static void
1053 scalarize_return_expr (block_stmt_iterator *si_p)
1054 {
1055   tree stmt = bsi_stmt (*si_p);
1056   tree op = TREE_OPERAND (stmt, 0);
1057
1058   if (op == NULL_TREE)
1059     return;
1060
1061   /* Handle a bare RESULT_DECL.  This will handle for types needed
1062      constructors, or possibly after NRV type optimizations.  */
1063   if (is_sra_candidate_decl (op))
1064     emit_scalar_copies (si_p, op, op, FIELD_SCALAR);
1065   else if (TREE_CODE (op) == MODIFY_EXPR)
1066     {
1067       tree *rhs_p = &TREE_OPERAND (op, 1);
1068       tree rhs = *rhs_p;
1069
1070       /* Handle 'return STRUCTURE;'  */
1071       if (is_sra_candidate_decl (rhs))
1072         emit_scalar_copies (si_p, rhs, rhs, FIELD_SCALAR);
1073
1074       /* Handle 'return STRUCTURE.FIELD;'  */
1075       else if (is_sra_candidate_ref (rhs, false))
1076         scalarize_component_ref (stmt, rhs_p);
1077
1078       /* Handle 'return CALL_EXPR;'  */
1079       else if (TREE_CODE (rhs) == CALL_EXPR)
1080         {
1081           struct bitmap_head_def done_head;
1082           bitmap_initialize (&done_head, 1);
1083           scalarize_tree_list (TREE_OPERAND (rhs, 1), si_p, &done_head);
1084           bitmap_clear (&done_head);
1085         }
1086     }
1087 }
1088
1089
1090 /* Debugging dump for the scalar replacement map.  */
1091
1092 static int
1093 dump_sra_map_trav (void **slot, void *data)
1094 {
1095   struct sra_elt *e = *slot;
1096   FILE *f = data;
1097
1098   switch (e->kind)
1099     {
1100     case REALPART_EXPR:
1101       fputs ("__real__ ", f);
1102       print_generic_expr (dump_file, e->base, dump_flags);
1103       fprintf (f, " -> %s\n", get_name (e->replace));
1104       break;
1105     case IMAGPART_EXPR:
1106       fputs ("__imag__ ", f);
1107       print_generic_expr (dump_file, e->base, dump_flags);
1108       fprintf (f, " -> %s\n", get_name (e->replace));
1109       break;
1110     case COMPONENT_REF:
1111       print_generic_expr (dump_file, e->base, dump_flags);
1112       fprintf (f, ".%s -> %s\n", get_name (e->field), get_name (e->replace));
1113       break;
1114     default:
1115       abort ();
1116     }
1117
1118   return 1;
1119 }
1120
1121 static void
1122 dump_sra_map (FILE *f)
1123 {
1124   fputs ("Scalar replacements:\n", f);
1125   htab_traverse_noresize (sra_map, dump_sra_map_trav, f);
1126   fputs ("\n\n", f);
1127 }
1128
1129 /* Main entry point to Scalar Replacement of Aggregates (SRA).  This pass
1130    re-writes non-aliased structure references into scalar temporaries.  The
1131    goal is to expose some/all structures to the scalar optimizers.
1132
1133    FNDECL is the function to process.
1134
1135    VARS_TO_RENAME_P is a pointer to the set of variables that need to be
1136    renamed into SSA after this pass is done.  These are going to be all the
1137    new scalars created by the SRA process.  Notice that since this pass
1138    creates new variables, the bitmap representing all the variables in the
1139    program will be re-sized here.
1140
1141    PHASE indicates which dump file from the DUMP_FILES array to use when
1142    dumping debugging information.
1143
1144    TODO
1145
1146    1- Scalarize COMPLEX_TYPEs
1147    2- Scalarize ARRAY_REFs that are always referenced with a
1148       constant index.
1149    3- Timings to determine when scalarization is not profitable.
1150    4- Determine what's a good value for MAX_NFIELDS_FOR_SRA.  */
1151
1152 static void
1153 tree_sra (void)
1154 {
1155   /* Initialize local variables.  */
1156   sra_candidates = BITMAP_XMALLOC ();
1157   sra_map = NULL;
1158   needs_copy_in = NULL;
1159
1160   /* Find structures to be scalarized.  */
1161   if (!find_candidates_for_sra ())
1162     {
1163       BITMAP_XFREE (sra_candidates);
1164       return;
1165     }
1166
1167   /* If we found any, re-write structure references with their
1168      corresponding scalar replacement.  */
1169   sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, free);
1170   needs_copy_in = BITMAP_XMALLOC ();
1171
1172   scalarize_structures ();
1173
1174   if (dump_file)
1175     dump_sra_map (dump_file);
1176
1177   /* Free allocated memory.  */
1178   htab_delete (sra_map);
1179   sra_map = NULL;
1180   BITMAP_XFREE (needs_copy_in);
1181   BITMAP_XFREE (sra_candidates);
1182 }
1183
1184 static bool
1185 gate_sra (void)
1186 {
1187   return flag_tree_sra != 0;
1188 }
1189
1190 struct tree_opt_pass pass_sra =
1191 {
1192   "sra",                                /* name */
1193   gate_sra,                             /* gate */
1194   tree_sra,                             /* execute */
1195   NULL,                                 /* sub */
1196   NULL,                                 /* next */
1197   0,                                    /* static_pass_number */
1198   TV_TREE_SRA,                          /* tv_id */
1199   PROP_cfg | PROP_ssa,                  /* properties_required */
1200   0,                                    /* properties_provided */
1201   0,                                    /* properties_destroyed */
1202   0,                                    /* todo_flags_start */
1203   TODO_dump_func | TODO_rename_vars
1204     | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
1205 };