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