Merge tree-ssa-20020619-branch into mainline.

git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@81764 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 1193 insertions, 0 deletions

diff --git a/gcc/tree-sra.c b/gcc/tree-sra.c
new file mode 100644
index 00000000000..2131d0047f2
--- /dev/null
+++ b/gcc/tree-sra.c
@@ -0,0 +1,1193 @@
+/* Scalar Replacement of Aggregates (SRA) converts some structure
+   references into scalar references, exposing them to the scalar
+   optimizers.
+   Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+   Contributed by Diego Novillo <dnovillo@redhat.com>
+
+This file is part of GCC.
+   
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+   
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+   
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "ggc.h"
+#include "tree.h"
+
+/* These RTL headers are needed for basic-block.h.  */
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "langhooks.h"
+#include "tree-inline.h"
+#include "tree-flow.h"
+#include "tree-simple.h"
+#include "tree-dump.h"
+#include "tree-pass.h"
+#include "timevar.h"
+#include "flags.h"
+#include "bitmap.h"
+
+
+/* Maximum number of fields that a structure should have to be scalarized.
+   FIXME  This limit has been arbitrarily set to 5.  Experiment to find a
+	  sensible setting.  */
+#define MAX_NFIELDS_FOR_SRA	5
+
+/* Codes indicating how to copy one structure into another.  */
+enum sra_copy_mode { SCALAR_SCALAR, FIELD_SCALAR, SCALAR_FIELD };
+
+/* Local functions.  */
+static inline bool can_be_scalarized_p (tree);
+static inline void insert_edge_copies (tree stmt, basic_block bb);
+static tree create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode);
+static inline void scalarize_component_ref (tree, tree *tp);
+static void scalarize_structures (void);
+static void scalarize_stmt (block_stmt_iterator *);
+static void scalarize_modify_expr (block_stmt_iterator *);
+static void scalarize_call_expr (block_stmt_iterator *);
+static void scalarize_asm_expr (block_stmt_iterator *);
+static void scalarize_return_expr (block_stmt_iterator *);
+
+/* The set of aggregate variables that are candidates for scalarization.  */
+static bitmap sra_candidates;
+
+/* Set of scalarizable PARM_DECLs that need copy-in operations at the
+   beginning of the function.  */
+static bitmap needs_copy_in;
+
+/* This structure holds the mapping between and element of an aggregate
+   and the scalar replacement variable.  */
+struct sra_elt
+{
+  enum tree_code kind;
+  tree base;
+  tree field;
+  tree replace;
+};
+    
+static htab_t sra_map;
+
+static hashval_t
+sra_elt_hash (const void *x)
+{
+  const struct sra_elt *e = x;
+  hashval_t h = (size_t) e->base * e->kind;
+  if (e->kind == COMPONENT_REF)
+    h ^= (size_t) e->field;
+  return h;
+}
+
+static int
+sra_elt_eq (const void *x, const void *y)
+{
+  const struct sra_elt *a = x;
+  const struct sra_elt *b = y;
+
+  if (a->kind != b->kind)
+    return false;
+  if (a->base != b->base)
+    return false;
+  if (a->kind == COMPONENT_REF)
+    if (a->field != b->field)
+      return false;
+
+  return true;
+}
+
+/* Build a temporary.  Make sure and register it to be renamed.  */
+
+static tree
+make_temp (tree type, const char *prefix)
+{
+  tree t = create_tmp_var (type, prefix);
+  add_referenced_tmp_var (t);
+  bitmap_set_bit (vars_to_rename, var_ann (t)->uid);
+  return t;
+}
+
+/* Mark all the variables in VDEF operands for STMT for renaming.
+   This becomes necessary when we modify all of a non-scalar.  */
+
+static void
+mark_all_vdefs (tree stmt)
+{
+  vdef_optype vdefs;
+  size_t i, n;
+
+  get_stmt_operands (stmt);
+  vdefs = VDEF_OPS (stmt_ann (stmt));
+  n = NUM_VDEFS (vdefs);
+
+  for (i = 0; i < n; i++)
+    {
+      tree sym = VDEF_RESULT (vdefs, i);
+      bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
+    }
+}
+
+/* Return true if DECL is an SRA candidate.  */
+
+static bool
+is_sra_candidate_decl (tree decl)
+{
+  return DECL_P (decl) && bitmap_bit_p (sra_candidates, var_ann (decl)->uid);
+}
+
+/* Return true if EXP is of the form <ref decl>, where REF is one of the
+   field access references we handle and DECL is an SRA candidate. 
+
+   Set ALLOW_BIT_FIELD_REF to accept BIT_FIELD_REF as well.  This is
+   normally false, except when we're trying to work around it.  */
+
+static bool
+is_sra_candidate_ref (tree exp, bool allow_bit_field_ref)
+{
+  switch (TREE_CODE (exp))
+    {
+    case BIT_FIELD_REF:
+      if (!allow_bit_field_ref)
+	break;
+      /* FALLTHRU */
+
+    case COMPONENT_REF:
+    case REALPART_EXPR:
+    case IMAGPART_EXPR:
+      return is_sra_candidate_decl (TREE_OPERAND (exp, 0));
+
+    default:
+      break;
+    }
+
+  return false;
+}
+
+/* Return the scalar in SRA_MAP[VAR_IX][FIELD_IX].  If none exists, create
+   a new scalar with type TYPE.  */
+
+static tree
+lookup_scalar (struct sra_elt *key, tree type)
+{
+  struct sra_elt **slot, *res;
+
+  slot = (struct sra_elt **) htab_find_slot (sra_map, key, INSERT);
+  res = *slot;
+  if (!res)
+    {
+      res = xmalloc (sizeof (*res));
+      *slot = res;
+      *res = *key;
+      res->replace = make_temp (type, "SR");
+
+      if (DECL_NAME (key->base) && !DECL_IGNORED_P (key->base))
+	{
+	  char *name = NULL;
+	  switch (key->kind)
+	    {
+	    case COMPONENT_REF:
+	      if (!DECL_NAME (key->field))
+		break;
+	      name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
+			     "$",
+			     IDENTIFIER_POINTER (DECL_NAME (key->field)),
+			     NULL);
+	      break;
+	    case REALPART_EXPR:
+	      name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
+			     "$real", NULL);
+	      break;
+	    case IMAGPART_EXPR:
+	      name = concat (IDENTIFIER_POINTER (DECL_NAME (key->base)),
+			     "$imag", NULL);
+	      break;
+	    default:
+	      abort ();
+	    }
+	  if (name)
+	    {
+	      DECL_NAME (res->replace) = get_identifier (name);
+	      free (name);
+	    }
+	}
+
+      DECL_SOURCE_LOCATION (res->replace) = DECL_SOURCE_LOCATION (key->base);
+      TREE_NO_WARNING (res->replace) = TREE_NO_WARNING (key->base);
+      DECL_ARTIFICIAL (res->replace) = DECL_ARTIFICIAL (key->base);
+    }
+
+  return res->replace;
+}
+
+
+/* Given a structure reference VAR.FIELD, return a scalar representing it.
+   If no scalar is found, a new one is created and added to the SRA_MAP
+   matrix.  */
+
+static tree
+get_scalar_for_field (tree var, tree field)
+{
+  struct sra_elt key;
+
+#ifdef ENABLE_CHECKING
+  /* Validate that FIELD actually exists in VAR's type.  */
+  {
+    tree f;
+    for (f = TYPE_FIELDS (TREE_TYPE (var)); f ; f = TREE_CHAIN (f))
+      if (f == field)
+	goto found;
+    abort ();
+   found:;
+  }
+#endif
+
+  key.kind = COMPONENT_REF;
+  key.base = var;
+  key.field = field;
+
+  return lookup_scalar (&key, TREE_TYPE (field));
+}
+
+
+/* Similarly for the parts of a complex type.  */
+
+static tree
+get_scalar_for_complex_part (tree var, enum tree_code part)
+{
+  struct sra_elt key;
+
+  key.kind = part;
+  key.base = var;
+
+  return lookup_scalar (&key, TREE_TYPE (TREE_TYPE (var)));
+}
+
+/* Return true if the fields of VAR can be replaced by scalar temporaries.
+   This only happens if VAR is not call-clobbered and it contains less
+   than MAX_NFIELDS_FOR_SRA scalar fields.  */
+
+static inline bool
+can_be_scalarized_p (tree var)
+{
+  tree field, type;
+  int nfields;
+
+  if (!is_gimple_non_addressable (var))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Cannot scalarize variable ");
+	  print_generic_expr (dump_file, var, dump_flags);
+	  fprintf (dump_file, " because it must live in memory\n");
+	}
+      return false;
+    }
+
+  if (TREE_THIS_VOLATILE (var))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	{
+	  fprintf (dump_file, "Cannot scalarize variable ");
+	  print_generic_expr (dump_file, var, dump_flags);
+	  fprintf (dump_file, " because it is declared volatile\n");
+	}
+      return false;
+    }
+
+  /* Any COMPLEX_TYPE that has reached this point can be scalarized.  */
+  if (TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
+    return true;
+
+  type = TREE_TYPE (var);
+  nfields = 0;
+  for (field = TYPE_FIELDS (type); field; field = TREE_CHAIN (field))
+    {
+      if (TREE_CODE (field) != FIELD_DECL)
+	continue;
+
+      /* FIXME: We really should recurse down the type hierarchy and
+	 scalarize the fields at the leaves.  */
+      if (AGGREGATE_TYPE_P (TREE_TYPE (field)))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Cannot scalarize variable ");
+	      print_generic_expr (dump_file, var, dump_flags);
+	      fprintf (dump_file,
+		       " because it contains an aggregate type field, ");
+	      print_generic_expr (dump_file, field, dump_flags);
+	      fprintf (dump_file, "\n");
+	    }
+	  return false;
+	}
+
+      /* FIXME: Similarly.  Indeed, considering that we treat complex
+	 as an aggregate, this is exactly the same problem.
+	 Structures with __complex__ fields are tested in the libstdc++
+	 testsuite: 26_numerics/complex_inserters_extractors.cc.  */
+      if (TREE_CODE (TREE_TYPE (field)) == COMPLEX_TYPE)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Cannot scalarize variable ");
+	      print_generic_expr (dump_file, var, dump_flags);
+	      fprintf (dump_file,
+		       " because it contains a __complex__ field, ");
+	      print_generic_expr (dump_file, field, dump_flags);
+	      fprintf (dump_file, "\n");
+	    }
+	  return false;
+	}
+
+      /* FIXME.  We don't scalarize structures with bit fields yet.  To
+	 support this, we should make sure that all the fields fit in one
+	 word and modify every operation done on the scalarized bit fields
+	 to mask them properly.  */
+      if (DECL_BIT_FIELD (field))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Cannot scalarize variable ");
+	      print_generic_expr (dump_file, var, dump_flags);
+	      fprintf (dump_file,
+		       " because it contains a bit-field, ");
+	      print_generic_expr (dump_file, field, dump_flags);
+	      fprintf (dump_file, "\n");
+	    }
+	  return false;
+	}
+
+      nfields++;
+      if (nfields > MAX_NFIELDS_FOR_SRA)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    {
+	      fprintf (dump_file, "Cannot scalarize variable ");
+	      print_generic_expr (dump_file, var, dump_flags);
+	      fprintf (dump_file,
+		       " because it contains more than %d fields\n", 
+		       MAX_NFIELDS_FOR_SRA);
+	    }
+	  return false;
+	}
+    }
+
+  /* If the structure had no FIELD_DECLs, then don't bother
+     scalarizing it.  */
+  return nfields > 0;
+}
+
+
+/* Replace the COMPONENT_REF, REALPART_EXPR or IMAGPART_EXPR pointed-to by
+   TP inside STMT with the corresponding scalar replacement from SRA_MAP.  */
+
+static inline void
+scalarize_component_ref (tree stmt, tree *tp)
+{
+  tree t = *tp, obj = TREE_OPERAND (t, 0);
+
+  /* When scalarizing a function argument, we will need to insert copy-in
+     operations from the original PARM_DECLs. Note that these copy-in
+     operations may end up being dead, but we won't know until we rename
+     the new variables into SSA.  */
+  if (TREE_CODE (obj) == PARM_DECL)
+    bitmap_set_bit (needs_copy_in, var_ann (obj)->uid);
+
+  switch (TREE_CODE (t))
+    {
+    case COMPONENT_REF:
+      t = get_scalar_for_field (obj, TREE_OPERAND (t, 1));
+      break;
+    case REALPART_EXPR:
+    case IMAGPART_EXPR:
+      t = get_scalar_for_complex_part (obj, TREE_CODE (t));
+      break;
+    default:
+      abort ();
+    }
+
+  *tp = t;
+  modify_stmt (stmt);
+}
+
+
+/* Scalarize the structure assignment for the statement pointed by SI_P.  */
+
+static void
+scalarize_structure_assignment (block_stmt_iterator *si_p)
+{
+  var_ann_t lhs_ann, rhs_ann;
+  tree lhs, rhs, list, orig_stmt;
+  bool lhs_can, rhs_can;
+
+  orig_stmt = bsi_stmt (*si_p);
+  lhs = TREE_OPERAND (orig_stmt, 0);
+  rhs = TREE_OPERAND (orig_stmt, 1);
+  list = NULL_TREE;
+
+#if defined ENABLE_CHECKING
+  if (TREE_CODE (orig_stmt) != MODIFY_EXPR)
+    abort ();
+#endif
+
+  /* Remove all type casts from RHS.  This may seem heavy handed but
+     it's actually safe and it is necessary in the presence of C++
+     reinterpret_cast<> where structure assignments of different
+     structures will be present in the IL.  This was the case of PR
+     13347 (http://gcc.gnu.org/bugzilla/show_bug.cgi?id=13347) which
+     had something like this:
+
+	struct A f;
+     	struct B g;
+	f = (struct A)g;
+
+     Both 'f' and 'g' were scalarizable, but the presence of the type
+     cast was causing SRA to not replace the RHS of the assignment
+     with g's scalar replacements.  Furthermore, the fact that this
+     assignment reached this point without causing syntax errors means
+     that the type cast is safe and that a field-by-field assignment
+     from 'g' into 'f' is the right thing to do.  */
+  STRIP_NOPS (rhs);
+
+  lhs_ann = DECL_P (lhs) ? var_ann (lhs) : NULL;
+  rhs_ann = DECL_P (rhs) ? var_ann (rhs) : NULL;
+
+#if defined ENABLE_CHECKING
+  /* Two different variables should not have the same UID.  */
+  if (lhs_ann
+      && rhs_ann
+      && lhs != rhs
+      && lhs_ann->uid == rhs_ann->uid)
+    abort ();
+#endif
+
+  lhs_can = lhs_ann && bitmap_bit_p (sra_candidates, lhs_ann->uid);
+  rhs_can = rhs_ann && bitmap_bit_p (sra_candidates, rhs_ann->uid);
+
+  /* Both LHS and RHS are scalarizable.  */
+  if (lhs_can && rhs_can)
+    list = create_scalar_copies (lhs, rhs, SCALAR_SCALAR);
+
+  /* Only RHS is scalarizable.  */
+  else if (rhs_can)
+    list = create_scalar_copies (lhs, rhs, FIELD_SCALAR);
+
+  /* Only LHS is scalarizable.  */
+  else if (lhs_can)
+    list = create_scalar_copies (lhs, rhs, SCALAR_FIELD);
+
+  /* If neither side is scalarizable, do nothing else.  */
+  else
+    return;
+
+  /* Set line number information for our replacements.  */
+  if (EXPR_HAS_LOCATION (orig_stmt))
+    annotate_all_with_locus (&list, EXPR_LOCATION (orig_stmt));
+
+  /* Replace the existing statement with the newly created list of
+     scalarized copies.  When replacing the original statement, the first
+     copy replaces it and the remaining copies are inserted either after
+     the first copy or on the outgoing edges of the original statement's
+     block.  */
+  {
+    tree_stmt_iterator tsi = tsi_start (list);
+    bsi_replace (si_p, tsi_stmt (tsi), true);
+    tsi_delink (&tsi);
+    if (stmt_ends_bb_p (orig_stmt))
+      insert_edge_copies (list, bb_for_stmt (orig_stmt));
+    else
+      bsi_insert_after (si_p, list, BSI_CONTINUE_LINKING);
+  }
+}
+
+
+/* Traverse all the referenced variables in the program looking for
+   structures that could be replaced with scalars.  */
+
+static bool
+find_candidates_for_sra (void)
+{
+  size_t i;
+  bool any_set = false;
+
+  for (i = 0; i < num_referenced_vars; i++)
+    {
+      tree var = referenced_var (i);
+
+      if ((TREE_CODE (TREE_TYPE (var)) == RECORD_TYPE
+	   || TREE_CODE (TREE_TYPE (var)) == COMPLEX_TYPE)
+	  && can_be_scalarized_p (var))
+	{
+	  bitmap_set_bit (sra_candidates, var_ann (var)->uid);
+	  any_set = true;
+	}
+    }
+
+  return any_set;
+}
+
+
+/* Insert STMT on all the outgoing edges out of BB.  Note that if BB
+   has more than one edge, STMT will be replicated for each edge.  Also,
+   abnormal edges will be ignored.  */
+
+static inline void
+insert_edge_copies (tree stmt, basic_block bb)
+{
+  edge e;
+  bool first_copy;
+
+  first_copy = true;
+  for (e = bb->succ; e; e = e->succ_next)
+    {
+      /* We don't need to insert copies on abnormal edges.  The
+	 value of the scalar replacement is not guaranteed to
+	 be valid through an abnormal edge.  */
+      if (!(e->flags & EDGE_ABNORMAL))
+	{
+	  if (first_copy)
+	    {
+	      bsi_insert_on_edge (e, stmt);
+	      first_copy = false;
+	    }
+	  else
+	    bsi_insert_on_edge (e, lhd_unsave_expr_now (stmt));
+	}
+    }
+}
+
+
+/* Append a new assignment statement to TSI.  */
+
+static tree
+csc_assign (tree_stmt_iterator *tsi, tree lhs, tree rhs)
+{
+  tree stmt = build (MODIFY_EXPR, TREE_TYPE (lhs), lhs, rhs);
+  modify_stmt (stmt);
+  tsi_link_after (tsi, stmt, TSI_NEW_STMT);
+  return stmt;
+}
+
+/* A subroutine of create_scalar_copies.  Construct a COMPONENT_REF
+   expression for BASE referencing FIELD.  INDEX is the field index.  */
+
+static tree
+csc_build_component_ref (tree base, tree field)
+{
+  switch (TREE_CODE (base))
+    {
+    case CONSTRUCTOR:
+      /* Only appears on RHS.  The only remaining CONSTRUCTORS for
+	 record types that should remain are empty, and imply that
+	 the entire structure should be zeroed.  */
+      if (CONSTRUCTOR_ELTS (base))
+	abort ();
+      return convert (TREE_TYPE (field), integer_zero_node);
+
+    default:
+      /* Avoid sharing BASE when building the different COMPONENT_REFs.
+	 We let the first field have the original version.  */
+      if (field != TYPE_FIELDS (TREE_TYPE (base)))
+	base = unshare_expr (base);
+      break;
+
+    case VAR_DECL:
+    case PARM_DECL:
+      /* Special case for the above -- decls are always shared.  */
+      break;
+    }
+
+  return build (COMPONENT_REF, TREE_TYPE (field), base, field);
+}
+
+/* Similarly for REALPART_EXPR and IMAGPART_EXPR for complex types.  */
+
+static tree
+csc_build_complex_part (tree base, enum tree_code part)
+{
+  switch (TREE_CODE (base))
+    {
+    case COMPLEX_CST:
+      if (part == REALPART_EXPR)
+	return TREE_REALPART (base);
+      else
+	return TREE_IMAGPART (base);
+
+    case COMPLEX_EXPR:
+      if (part == REALPART_EXPR)
+        return TREE_OPERAND (base, 0);
+      else
+        return TREE_OPERAND (base, 1);
+
+    default:
+      /* Avoid sharing BASE when building the different references.
+	 We let the real part have the original version.  */
+      if (part != REALPART_EXPR)
+	base = unshare_expr (base);
+      break;
+
+    case VAR_DECL:
+    case PARM_DECL:
+      /* Special case for the above -- decls are always shared.  */
+      break;
+    }
+
+  return build1 (part, TREE_TYPE (TREE_TYPE (base)), base);
+}
+
+/* Create and return a list of assignments to perform a scalarized
+   structure assignment 'LHS = RHS'.  Both LHS and RHS are assumed to be
+   of an aggregate or complex type.  Three types of copies may be specified:
+
+   SCALAR_SCALAR will emit assignments for all the scalar temporaries
+      corresponding to the fields of LHS and RHS.
+
+   FIELD_SCALAR will emit assignments from the scalar replacements of
+      RHS into each of the fields of the LHS.
+
+   SCALAR_FIELD will emit assignments from each field of the RHS into
+      the scalar replacements of the LHS.  */
+
+static tree
+create_scalar_copies (tree lhs, tree rhs, enum sra_copy_mode mode)
+{
+  tree type, list;
+  tree_stmt_iterator tsi;
+
+#if defined ENABLE_CHECKING
+  /* Sanity checking.  Check that we are not trying to scalarize a
+     non-decl.  */
+  if (!DECL_P (lhs) && (mode == SCALAR_FIELD || mode == SCALAR_SCALAR))
+    abort ();
+  if (!DECL_P (rhs) && (mode == FIELD_SCALAR || mode == SCALAR_SCALAR))
+    abort ();
+#endif
+
+  type = TREE_TYPE (lhs);
+  list = alloc_stmt_list ();
+  tsi = tsi_start (list);
+
+  /* VA_ARG_EXPRs have side effects, so we need to copy it first to a
+     temporary before scalarizing.  FIXME: This should disappear once
+     VA_ARG_EXPRs are properly lowered.  */
+  if (TREE_CODE (rhs) == VA_ARG_EXPR)
+    {
+      tree stmt, tmp;
+
+      /* Add TMP = VA_ARG_EXPR <>  */
+      tmp = make_temp (TREE_TYPE (rhs), NULL);
+      stmt = csc_assign (&tsi, tmp, rhs);
+
+      /* Mark all the variables in VDEF operands for renaming, because
+	 the VA_ARG_EXPR will now be in a different statement.  */
+      mark_all_vdefs (stmt);
+
+      /* Set RHS to be the new temporary TMP.  */
+      rhs = tmp;
+    }
+
+  /* When making *_SCALAR copies from PARM_DECLs, we will need to insert
+     copy-in operations from the original PARM_DECLs.  Note that these
+     copy-in operations may end up being dead, but we won't know until
+     we rename the new variables into SSA.  */
+  if ((mode == SCALAR_SCALAR || mode == FIELD_SCALAR)
+      && TREE_CODE (rhs) == PARM_DECL)
+    bitmap_set_bit (needs_copy_in, var_ann (rhs)->uid);
+
+  /* Now create scalar copies for each individual field according to MODE.  */
+  if (TREE_CODE (type) == COMPLEX_TYPE)
+    {
+      /* Create scalar copies of both the real and imaginary parts.  */
+      tree real_lhs, real_rhs, imag_lhs, imag_rhs;
+
+      if (mode == SCALAR_FIELD)
+	{
+	  real_rhs = csc_build_complex_part (rhs, REALPART_EXPR);
+	  imag_rhs = csc_build_complex_part (rhs, IMAGPART_EXPR);
+	}
+      else
+	{
+	  real_rhs = get_scalar_for_complex_part (rhs, REALPART_EXPR);
+	  imag_rhs = get_scalar_for_complex_part (rhs, IMAGPART_EXPR);
+	}
+
+      if (mode == FIELD_SCALAR)
+	{
+	  /* In this case we do not need to create but one statement,
+	     since we can create a new complex value whole.  */
+
+	  if (TREE_CONSTANT (real_rhs) && TREE_CONSTANT (imag_rhs))
+	    rhs = build_complex (type, real_rhs, imag_rhs);
+	  else
+	    rhs = build (COMPLEX_EXPR, type, real_rhs, imag_rhs);
+	  csc_assign (&tsi, lhs, rhs);
+	}
+      else
+	{
+	  real_lhs = get_scalar_for_complex_part (lhs, REALPART_EXPR);
+	  imag_lhs = get_scalar_for_complex_part (lhs, IMAGPART_EXPR);
+
+	  csc_assign (&tsi, real_lhs, real_rhs);
+	  csc_assign (&tsi, imag_lhs, imag_rhs);
+	}
+    }
+  else
+    {
+      tree lf, rf;
+
+      /* ??? C++ generates copies between different pointer-to-member
+	 structures of different types.  To combat this, we must track
+	 the field of both the left and right structures, so that we
+	 index the variables with fields of their own type.  */
+
+      for (lf = TYPE_FIELDS (type), rf = TYPE_FIELDS (TREE_TYPE (rhs));
+	   lf;
+	   lf = TREE_CHAIN (lf), rf = TREE_CHAIN (rf))
+	{
+	  tree lhs_var, rhs_var;
+
+	  /* Only copy FIELD_DECLs.  */
+	  if (TREE_CODE (lf) != FIELD_DECL)
+	    continue;
+
+	  if (mode == FIELD_SCALAR)
+	    lhs_var = csc_build_component_ref (lhs, lf);
+	  else
+	    lhs_var = get_scalar_for_field (lhs, lf);
+
+	  if (mode == SCALAR_FIELD)
+	    rhs_var = csc_build_component_ref (rhs, rf);
+	  else
+	    rhs_var = get_scalar_for_field (rhs, rf);
+
+	  csc_assign (&tsi, lhs_var, rhs_var);
+	}
+    }
+
+  /* All the scalar copies just created will either create new definitions
+     or remove existing definitions of LHS, so we need to mark it for
+     renaming.  */
+  if (TREE_SIDE_EFFECTS (list))
+    {
+      if (mode == SCALAR_FIELD || mode == SCALAR_SCALAR)
+	{
+	  /* If the LHS has been scalarized, mark it for renaming.  */
+	  bitmap_set_bit (vars_to_rename, var_ann (lhs)->uid);
+	}
+      else if (mode == FIELD_SCALAR)
+	{
+	  /* Otherwise, mark all the symbols in the VDEFs for the last
+	     scalarized statement just created.  Since all the statements
+	     introduce the same VDEFs, we only need to check the last one.  */
+	  mark_all_vdefs (tsi_stmt (tsi));
+	}
+      else
+	abort ();
+    }
+
+  return list;
+}
+
+/* A helper function that creates the copies, updates line info,
+   and emits the code either before or after BSI.  */
+
+static void
+emit_scalar_copies (block_stmt_iterator *bsi, tree lhs, tree rhs,
+		    enum sra_copy_mode mode)
+{
+  tree list = create_scalar_copies (lhs, rhs, mode);
+  tree stmt = bsi_stmt (*bsi);
+
+  if (EXPR_HAS_LOCATION (stmt))
+    annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
+
+  bsi_insert_before (bsi, list, BSI_SAME_STMT);
+}
+
+/* Traverse all the statements in the function replacing references to
+   scalarizable structures with their corresponding scalar temporaries.  */
+
+static void
+scalarize_structures (void)
+{
+  basic_block bb;
+  block_stmt_iterator si;
+  size_t i;
+
+  FOR_EACH_BB (bb)
+    for (si = bsi_start (bb); !bsi_end_p (si); bsi_next (&si))
+      {
+	tree stmt;
+	stmt_ann_t ann;
+
+	stmt = bsi_stmt (si);
+	ann = stmt_ann (stmt);
+
+	/* If the statement has no virtual operands, then it doesn't make
+	   structure references that we care about.  */
+	if (NUM_VDEFS (VDEF_OPS (ann)) == 0
+	    && NUM_VUSES (VUSE_OPS (ann)) == 0)
+	  continue;
+
+	/* Structure references may only appear in certain statements.  */
+	if (TREE_CODE (stmt) != MODIFY_EXPR
+	    && TREE_CODE (stmt) != CALL_EXPR
+	    && TREE_CODE (stmt) != RETURN_EXPR
+	    && TREE_CODE (stmt) != ASM_EXPR)
+	  continue;
+
+	scalarize_stmt (&si);
+      }
+
+  /* Initialize the scalar replacements for every structure that is a
+     function argument.  */
+  EXECUTE_IF_SET_IN_BITMAP (needs_copy_in, 0, i,
+    {
+      tree var = referenced_var (i);
+      tree list = create_scalar_copies (var, var, SCALAR_FIELD);
+      bsi_insert_on_edge (ENTRY_BLOCK_PTR->succ, list);
+    });
+
+  /* Commit edge insertions.  */
+  bsi_commit_edge_inserts (NULL);
+}
+
+
+/* Scalarize structure references in the statement pointed by SI_P.  */
+
+static void
+scalarize_stmt (block_stmt_iterator *si_p)
+{
+  tree stmt = bsi_stmt (*si_p);
+
+  /* Handle assignments.  */
+  if (TREE_CODE (stmt) == MODIFY_EXPR
+      && TREE_CODE (TREE_OPERAND (stmt, 1)) != CALL_EXPR)
+    scalarize_modify_expr (si_p);
+
+  /* Handle RETURN_EXPR.  */
+  else if (TREE_CODE (stmt) == RETURN_EXPR)
+    scalarize_return_expr (si_p);
+
+  /* Handle function calls (note that this must be handled after
+     MODIFY_EXPR and RETURN_EXPR because a function call can appear in
+     both).  */
+  else if (get_call_expr_in (stmt) != NULL_TREE)
+    scalarize_call_expr (si_p);
+
+  /* Handle ASM_EXPRs.  */
+  else if (TREE_CODE (stmt) == ASM_EXPR)
+    scalarize_asm_expr (si_p);
+}
+
+
+/* Helper for scalarize_stmt to handle assignments.  */
+
+static void
+scalarize_modify_expr (block_stmt_iterator *si_p)
+{
+  tree stmt = bsi_stmt (*si_p);
+  tree lhs = TREE_OPERAND (stmt, 0);
+  tree rhs = TREE_OPERAND (stmt, 1);
+
+  /* Found AGGREGATE.FIELD = ...  */
+  if (is_sra_candidate_ref (lhs, false))
+    {
+      tree sym;
+      vdef_optype vdefs;
+
+      scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 0));
+
+      /* Mark the LHS to be renamed, as we have just removed the previous
+	 VDEF for AGGREGATE.  The statement should have exactly one VDEF
+	 for variable AGGREGATE.  */
+      vdefs = STMT_VDEF_OPS (stmt);
+      if (NUM_VDEFS (vdefs) != 1)
+	abort ();
+      sym = SSA_NAME_VAR (VDEF_RESULT (vdefs, 0));
+      bitmap_set_bit (vars_to_rename, var_ann (sym)->uid);
+    }
+
+  /* Found ... = AGGREGATE.FIELD  */
+  else if (is_sra_candidate_ref (rhs, false))
+    scalarize_component_ref (stmt, &TREE_OPERAND (stmt, 1));
+
+  /* Found ... = BIT_FIELD_REF <>.  This is similar to a CALL_EXPR, if the
+     operand of the BIT_FIELD_REF is a scalarizable structure, we need to
+     copy from its scalar replacements before doing the bitfield operation.
+
+     FIXME: BIT_FIELD_REFs are often generated by fold-const.c.  This is
+     not always desirable because they obfuscate the original predicates,
+     limiting what the tree optimizers may do.  For instance, in
+     testsuite/g++.dg/opt/nrv4.C the use of SRA allows the optimizers to
+     optimize function main() to 'return 0;'.  However, the folder
+     generates a BIT_FIELD_REF operation for one of the comparisons,
+     preventing the optimizers from removing all the redundant
+     operations.  */
+  else if (is_sra_candidate_ref (rhs, true))
+    {
+      tree var = TREE_OPERAND (rhs, 0);
+      emit_scalar_copies (si_p, var, var, FIELD_SCALAR);
+    }
+
+  /* Found AGGREGATE = ... or ... = AGGREGATE  */
+  else if (DECL_P (lhs) || DECL_P (rhs))
+    scalarize_structure_assignment (si_p);
+}
+
+
+/* Scalarize structure references in LIST.  Use DONE to avoid duplicates.  */
+
+static inline void
+scalarize_tree_list (tree list, block_stmt_iterator *si_p, bitmap done)
+{
+  tree op;
+
+  for (op = list; op; op = TREE_CHAIN (op))
+    {
+      tree arg = TREE_VALUE (op);
+
+      if (is_sra_candidate_decl (arg))
+	{
+	  int index = var_ann (arg)->uid;
+	  if (!bitmap_bit_p (done, index))
+	    {
+	      emit_scalar_copies (si_p, arg, arg, FIELD_SCALAR);
+	      bitmap_set_bit (done, index);
+	    }
+	}
+      else if (is_sra_candidate_ref (arg, false))
+	{
+	  tree stmt = bsi_stmt (*si_p);
+	  scalarize_component_ref (stmt, &TREE_VALUE (op));
+	}
+    }
+}
+
+
+/* Helper for scalarize_stmt to handle function calls.  */
+
+static void
+scalarize_call_expr (block_stmt_iterator *si_p)
+{
+  tree stmt = bsi_stmt (*si_p);
+  tree call = (TREE_CODE (stmt) == MODIFY_EXPR) ? TREE_OPERAND (stmt, 1) : stmt;
+  struct bitmap_head_def done_head;
+
+  /* First scalarize the arguments.  Order is important, because the copy
+     operations for the arguments need to go before the call.
+     Scalarization of the return value needs to go after the call.  */
+  bitmap_initialize (&done_head, 1);
+  scalarize_tree_list (TREE_OPERAND (call, 1), si_p, &done_head);
+  bitmap_clear (&done_head);
+
+  /* Scalarize the return value, if any.  */
+  if (TREE_CODE (stmt) == MODIFY_EXPR)
+    {
+      tree var = TREE_OPERAND (stmt, 0);
+
+      /* If the LHS of the assignment is a scalarizable structure, insert
+	 copies into the scalar replacements after the call.  */
+      if (is_sra_candidate_decl (var))
+	{
+	  tree list = create_scalar_copies (var, var, SCALAR_FIELD);
+	  if (EXPR_HAS_LOCATION (stmt))
+	    annotate_all_with_locus (&list, EXPR_LOCATION (stmt));
+	  if (stmt_ends_bb_p (stmt))
+	    insert_edge_copies (list, bb_for_stmt (stmt));
+	  else
+	    bsi_insert_after (si_p, list, BSI_NEW_STMT);
+	}
+    }
+}
+
+
+/* Helper for scalarize_stmt to handle ASM_EXPRs.  */
+
+static void
+scalarize_asm_expr (block_stmt_iterator *si_p)
+{
+  tree stmt = bsi_stmt (*si_p);
+  struct bitmap_head_def done_head;
+
+  bitmap_initialize (&done_head, 1);
+  scalarize_tree_list (ASM_INPUTS (stmt), si_p, &done_head);
+  scalarize_tree_list (ASM_OUTPUTS (stmt), si_p, &done_head);
+  bitmap_clear (&done_head);
+
+  /* ??? Process outputs after the asm.  */
+}
+
+
+/* Helper for scalarize_stmt to handle return expressions.  */
+
+static void
+scalarize_return_expr (block_stmt_iterator *si_p)
+{
+  tree stmt = bsi_stmt (*si_p);
+  tree op = TREE_OPERAND (stmt, 0);
+
+  if (op == NULL_TREE)
+    return;
+
+  /* Handle a bare RESULT_DECL.  This will handle for types needed
+     constructors, or possibly after NRV type optimizations.  */
+  if (is_sra_candidate_decl (op))
+    emit_scalar_copies (si_p, op, op, FIELD_SCALAR);
+  else if (TREE_CODE (op) == MODIFY_EXPR)
+    {
+      tree *rhs_p = &TREE_OPERAND (op, 1);
+      tree rhs = *rhs_p;
+
+      /* Handle 'return STRUCTURE;'  */
+      if (is_sra_candidate_decl (rhs))
+	emit_scalar_copies (si_p, rhs, rhs, FIELD_SCALAR);
+
+      /* Handle 'return STRUCTURE.FIELD;'  */
+      else if (is_sra_candidate_ref (rhs, false))
+	scalarize_component_ref (stmt, rhs_p);
+
+      /* Handle 'return CALL_EXPR;'  */
+      else if (TREE_CODE (rhs) == CALL_EXPR)
+	{
+	  struct bitmap_head_def done_head;
+	  bitmap_initialize (&done_head, 1);
+	  scalarize_tree_list (TREE_OPERAND (rhs, 1), si_p, &done_head);
+	  bitmap_clear (&done_head);
+	}
+    }
+}
+
+
+/* Debugging dump for the scalar replacement map.  */
+
+static int
+dump_sra_map_trav (void **slot, void *data)
+{
+  struct sra_elt *e = *slot;
+  FILE *f = data;
+
+  switch (e->kind)
+    {
+    case REALPART_EXPR:
+      fputs ("__real__ ", f);
+      print_generic_expr (dump_file, e->base, dump_flags);
+      fprintf (f, " -> %s\n", get_name (e->replace));
+      break;
+    case IMAGPART_EXPR:
+      fputs ("__imag__ ", f);
+      print_generic_expr (dump_file, e->base, dump_flags);
+      fprintf (f, " -> %s\n", get_name (e->replace));
+      break;
+    case COMPONENT_REF:
+      print_generic_expr (dump_file, e->base, dump_flags);
+      fprintf (f, ".%s -> %s\n", get_name (e->field), get_name (e->replace));
+      break;
+    default:
+      abort ();
+    }
+
+  return 1;
+}
+
+static void
+dump_sra_map (FILE *f)
+{
+  fputs ("Scalar replacements:\n", f);
+  htab_traverse_noresize (sra_map, dump_sra_map_trav, f);
+  fputs ("\n\n", f);
+}
+
+/* Main entry point to Scalar Replacement of Aggregates (SRA).  This pass
+   re-writes non-aliased structure references into scalar temporaries.  The
+   goal is to expose some/all structures to the scalar optimizers.
+
+   FNDECL is the function to process.
+   
+   VARS_TO_RENAME_P is a pointer to the set of variables that need to be
+   renamed into SSA after this pass is done.  These are going to be all the
+   new scalars created by the SRA process.  Notice that since this pass
+   creates new variables, the bitmap representing all the variables in the
+   program will be re-sized here.
+
+   PHASE indicates which dump file from the DUMP_FILES array to use when
+   dumping debugging information.
+
+   TODO
+
+   1- Scalarize COMPLEX_TYPEs
+   2- Scalarize ARRAY_REFs that are always referenced with a
+      constant index.
+   3- Timings to determine when scalarization is not profitable.
+   4- Determine what's a good value for MAX_NFIELDS_FOR_SRA.  */
+
+static void
+tree_sra (void)
+{
+  /* Initialize local variables.  */
+  sra_candidates = BITMAP_XMALLOC ();
+  sra_map = NULL;
+  needs_copy_in = NULL;
+
+  /* Find structures to be scalarized.  */
+  if (!find_candidates_for_sra ())
+    {
+      BITMAP_XFREE (sra_candidates);
+      return;
+    }
+
+  /* If we found any, re-write structure references with their
+     corresponding scalar replacement.  */
+  sra_map = htab_create (101, sra_elt_hash, sra_elt_eq, free);
+  needs_copy_in = BITMAP_XMALLOC ();
+
+  scalarize_structures ();
+
+  if (dump_file)
+    dump_sra_map (dump_file);
+
+  /* Free allocated memory.  */
+  htab_delete (sra_map);
+  sra_map = NULL;
+  BITMAP_XFREE (needs_copy_in);
+  BITMAP_XFREE (sra_candidates);
+}
+
+static bool
+gate_sra (void)
+{
+  return flag_tree_sra != 0;
+}
+
+struct tree_opt_pass pass_sra = 
+{
+  "sra",				/* name */
+  gate_sra,				/* gate */
+  tree_sra,				/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_TREE_SRA,				/* tv_id */
+  PROP_cfg | PROP_ssa,			/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func | TODO_rename_vars
+    | TODO_ggc_collect | TODO_verify_ssa  /* todo_flags_finish */
+};