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