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