re PR libstdc++/29286 (placement new does not change the dynamic type as it should)

./:	PR libstdc++/29286
	* tree.def: Add CHANGE_DYNAMIC_TYPE_EXPR.
	* tree.h (CHANGE_DYNAMIC_TYPE_NEW_TYPE): Define.
	(CHANGE_DYNAMIC_TYPE_LOCATION): Define.
	(DECL_NO_TBAA_P): Define.
	(struct tree_decl_common): Add no_tbaa_flag field.
	* tree-ssa-structalias.c (struct variable_info): Add
	no_tbaa_pruning field.
	(new_var_info): Initialize no_tbaa_pruning field.
	(unify_nodes): Copy no_tbaa_pruning field.
	(find_func_aliases): Handle CHANGE_DYNAMIC_TYPE_EXPR.
	(dump_solution_for_var): Print no_tbaa_pruning flag.
	(set_uids_in_ptset): Add no_tbaa_pruning parameter.  Change all
	callers.
	(compute_tbaa_pruning): New static function.
	(compute_points_to_sets): Remove CHANGE_DYNAMIC_TYPE_EXPR nodes.
	Call compute_tbaa_pruning.
	* tree-ssa-alias.c (may_alias_p): Test no_tbaa_flag for pointers.
	* gimplify.c (gimplify_expr): Handle CHANGE_DYNAMIC_TYPE_EXPR.
	* gimple-low.c (lower_stmt): Likewise.
	* tree-gimple.c (is_gimple_stmt): Likewise.
	* tree-ssa-operands.c (get_expr_operands): Likewise.
	* tree-ssa-dce.c (mark_stmt_if_obviously_necessary): Likewise.
	* tree-inline.c (estimate_num_insns_1): Likewise.
	(copy_result_decl_to_var): Likewise.
	* expr.c (expand_expr_real_1): Likewise.
	* tree-pretty-print.c (dump_generic_node): Likewise.
	* tree-inline.c (copy_decl_to_var): Copy DECL_NO_TBAA_P flag.
	* omp-low.c (omp_copy_decl_2): Likewise.
	* print-tree.c (print_node): Print DECL_NO_TBAA_P flag.
	* doc/c-tree.texi (Expression trees): Document
	CHANGE_DYNAMIC_TYPE_EXPR.
cp/:
	PR libstdc++/29286
	* init.c (avoid_placement_new_aliasing): New static function.
	(build_new_1): Call it.
testsuite/:
	PR libstdc++/29286
	* g++.dg/init/new16.C: New test.
	* g++.dg/init/new17.C: New test.
	* g++.dg/init/new18.C: New test.
	* g++.dg/init/new19.C: New test.

Co-Authored-By: Daniel Berlin <dberlin@dberlin.org>

From-SVN: r125653

23 files changed, 633 insertions, 66 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 616bc5097e9..d531d976f36 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,39 @@
+2007-06-12  Ian Lance Taylor  <iant@google.com>
+	    Daniel Berlin  <dberlin@dberlin.org>
+
+	PR libstdc++/29286
+	* tree.def: Add CHANGE_DYNAMIC_TYPE_EXPR.
+	* tree.h (CHANGE_DYNAMIC_TYPE_NEW_TYPE): Define.
+	(CHANGE_DYNAMIC_TYPE_LOCATION): Define.
+	(DECL_NO_TBAA_P): Define.
+	(struct tree_decl_common): Add no_tbaa_flag field.
+	* tree-ssa-structalias.c (struct variable_info): Add
+	no_tbaa_pruning field.
+	(new_var_info): Initialize no_tbaa_pruning field.
+	(unify_nodes): Copy no_tbaa_pruning field.
+	(find_func_aliases): Handle CHANGE_DYNAMIC_TYPE_EXPR.
+	(dump_solution_for_var): Print no_tbaa_pruning flag.
+	(set_uids_in_ptset): Add no_tbaa_pruning parameter.  Change all
+	callers.
+	(compute_tbaa_pruning): New static function.
+	(compute_points_to_sets): Remove CHANGE_DYNAMIC_TYPE_EXPR nodes.
+	Call compute_tbaa_pruning.
+	* tree-ssa-alias.c (may_alias_p): Test no_tbaa_flag for pointers.
+	* gimplify.c (gimplify_expr): Handle CHANGE_DYNAMIC_TYPE_EXPR.
+	* gimple-low.c (lower_stmt): Likewise.
+	* tree-gimple.c (is_gimple_stmt): Likewise.
+	* tree-ssa-operands.c (get_expr_operands): Likewise.
+	* tree-ssa-dce.c (mark_stmt_if_obviously_necessary): Likewise.
+	* tree-inline.c (estimate_num_insns_1): Likewise.
+	(copy_result_decl_to_var): Likewise.
+	* expr.c (expand_expr_real_1): Likewise.
+	* tree-pretty-print.c (dump_generic_node): Likewise.
+	* tree-inline.c (copy_decl_to_var): Copy DECL_NO_TBAA_P flag.
+	* omp-low.c (omp_copy_decl_2): Likewise.
+	* print-tree.c (print_node): Print DECL_NO_TBAA_P flag.
+	* doc/c-tree.texi (Expression trees): Document
+	CHANGE_DYNAMIC_TYPE_EXPR.
+
 2007-06-12  Kaveh R. Ghazi  <ghazi@caip.rutgers.edu>
 
 	* fold-const.c (fold_binary): Guard (X-X) -> 0 transformation
diff --git a/gcc/cp/ChangeLog b/gcc/cp/ChangeLog
index 3f010ae7723..f9ca0508ddc 100644
--- a/gcc/cp/ChangeLog
+++ b/gcc/cp/ChangeLog
@@ -1,3 +1,9 @@
+2007-06-12  Ian Lance Taylor  <iant@google.com>
+
+	PR libstdc++/29286
+	* init.c (avoid_placement_new_aliasing): New static function.
+	(build_new_1): Call it.
+
 2007-06-11  Rafael Avila de Espindola  <espindola@google.com>
 
 	* cp-objcp-common.h (LANG_HOOKS_SIGNED_TYPE): Remove.
diff --git a/gcc/cp/init.c b/gcc/cp/init.c
index 3023cf09d4b..aecbed96795 100644
--- a/gcc/cp/init.c
+++ b/gcc/cp/init.c
@@ -1,6 +1,7 @@
 /* Handle initialization things in C++.
    Copyright (C) 1987, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
-   1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+   1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007
+   Free Software Foundation, Inc.
    Contributed by Michael Tiemann (tiemann@cygnus.com)
 
 This file is part of GCC.
@@ -1564,6 +1565,55 @@ build_raw_new_expr (tree placement, tree type, tree nelts, tree init,
   return new_expr;
 }
 
+/* Make sure that there are no aliasing issues with T, a placement new
+   expression applied to PLACEMENT, by recording the change in dynamic
+   type.  If placement new is inlined, as it is with libstdc++, and if
+   the type of the placement new differs from the type of the
+   placement location itself, then alias analysis may think it is OK
+   to interchange writes to the location from before the placement new
+   and from after the placement new.  We have to prevent type-based
+   alias analysis from applying.  PLACEMENT may be NULL, which means
+   that we couldn't capture it in a temporary variable, in which case
+   we use a memory clobber.  */
+
+static tree
+avoid_placement_new_aliasing (tree t, tree placement)
+{
+  tree type_change;
+
+  if (processing_template_decl)
+    return t;
+
+  /* If we are not using type based aliasing, we don't have to do
+     anything.  */
+  if (!flag_strict_aliasing)
+    return t;
+
+  /* If we have a pointer and a location, record the change in dynamic
+     type.  Otherwise we need a general memory clobber.  */
+  if (TREE_CODE (TREE_TYPE (t)) == POINTER_TYPE
+      && placement != NULL_TREE
+      && TREE_CODE (TREE_TYPE (placement)) == POINTER_TYPE)
+    type_change = build_stmt (CHANGE_DYNAMIC_TYPE_EXPR,
+			      TREE_TYPE (t),
+			      placement);
+  else
+    {
+      /* Build a memory clobber.  */
+      type_change = build_stmt (ASM_EXPR,
+				build_string (0, ""),
+				NULL_TREE,
+				NULL_TREE,
+				tree_cons (NULL_TREE,
+					   build_string (6, "memory"),
+					   NULL_TREE));
+
+      ASM_VOLATILE_P (type_change) = 1;
+    }
+
+  return build2 (COMPOUND_EXPR, TREE_TYPE (t), type_change, t);
+}
+
 /* Generate code for a new-expression, including calling the "operator
    new" function, initializing the object, and, if an exception occurs
    during construction, cleaning up.  The arguments are as for
@@ -1607,6 +1657,7 @@ build_new_1 (tree placement, tree type, tree nelts, tree init,
      beginning of the storage allocated for an array-new expression in
      order to store the number of elements.  */
   tree cookie_size = NULL_TREE;
+  tree placement_var;
   /* True if the function we are calling is a placement allocation
      function.  */
   bool placement_allocation_fn_p;
@@ -1700,6 +1751,20 @@ build_new_1 (tree placement, tree type, tree nelts, tree init,
 
   alloc_fn = NULL_TREE;
 
+  /* If PLACEMENT is a simple pointer type, then copy it into
+     PLACEMENT_VAR.  */
+  if (processing_template_decl
+      || placement == NULL_TREE
+      || TREE_CHAIN (placement) != NULL_TREE
+      || TREE_CODE (TREE_TYPE (TREE_VALUE (placement))) != POINTER_TYPE)
+    placement_var = NULL_TREE;
+  else
+    {
+      placement_var = get_temp_regvar (TREE_TYPE (TREE_VALUE (placement)),
+				       TREE_VALUE (placement));
+      placement = tree_cons (NULL_TREE, placement_var, NULL_TREE);
+    }
+
   /* Allocate the object.  */
   if (! placement && TYPE_FOR_JAVA (elt_type))
     {
@@ -1792,7 +1857,12 @@ build_new_1 (tree placement, tree type, tree nelts, tree init,
   /* In the simple case, we can stop now.  */
   pointer_type = build_pointer_type (type);
   if (!cookie_size && !is_initialized)
-    return build_nop (pointer_type, alloc_call);
+    {
+      rval = build_nop (pointer_type, alloc_call);
+      if (placement != NULL)
+	rval = avoid_placement_new_aliasing (rval, placement_var);
+      return rval;
+    }
 
   /* While we're working, use a pointer to the type we've actually
      allocated. Store the result of the call in a variable so that we
@@ -2052,6 +2122,9 @@ build_new_1 (tree placement, tree type, tree nelts, tree init,
   /* A new-expression is never an lvalue.  */
   gcc_assert (!lvalue_p (rval));
 
+  if (placement != NULL)
+    rval = avoid_placement_new_aliasing (rval, placement_var);
+
   return rval;
 }
 
diff --git a/gcc/doc/c-tree.texi b/gcc/doc/c-tree.texi
index bd4c62308ee..c61b871a679 100644
--- a/gcc/doc/c-tree.texi
+++ b/gcc/doc/c-tree.texi
@@ -1965,6 +1965,7 @@ This macro returns the attributes on the type @var{type}.
 @tindex TARGET_EXPR
 @tindex AGGR_INIT_EXPR
 @tindex VA_ARG_EXPR
+@tindex CHANGE_DYNAMIC_TYPE_EXPR
 @tindex OMP_PARALLEL
 @tindex OMP_FOR
 @tindex OMP_SECTIONS
@@ -2655,6 +2656,13 @@ mechanism.  It represents expressions like @code{va_arg (ap, type)}.
 Its @code{TREE_TYPE} yields the tree representation for @code{type} and
 its sole argument yields the representation for @code{ap}.
 
+@item CHANGE_DYNAMIC_TYPE_EXPR
+Indicates the special aliasing required by C++ placement new.  It has
+two operands: a type and a location.  It means that the dynamic type
+of the location is changing to be the specified type.  The alias
+analysis code takes this into account when doing type based alias
+analysis.
+
 @item OMP_PARALLEL
 
 Represents @code{#pragma omp parallel [clause1 ... clauseN]}. It
diff --git a/gcc/expr.c b/gcc/expr.c
index 19b404f00f9..2a4629a71e0 100644
--- a/gcc/expr.c
+++ b/gcc/expr.c
@@ -8947,6 +8947,13 @@ expand_expr_real_1 (tree exp, rtx target, enum machine_mode tmode,
       /* Lowered by gimplify.c.  */
       gcc_unreachable ();
 
+    case CHANGE_DYNAMIC_TYPE_EXPR:
+      /* This is ignored at the RTL level.  The tree level set
+	 DECL_POINTER_ALIAS_SET of any variable to be 0, which is
+	 overkill for the RTL layer but is all that we can
+	 represent.  */
+      return const0_rtx;
+
     case EXC_PTR_EXPR:
       return get_exception_pointer (cfun);
 
diff --git a/gcc/gimple-low.c b/gcc/gimple-low.c
index 642cd4fdd5c..f7888e25482 100644
--- a/gcc/gimple-low.c
+++ b/gcc/gimple-low.c
@@ -242,6 +242,7 @@ lower_stmt (tree_stmt_iterator *tsi, struct lower_data *data)
     case GOTO_EXPR:
     case LABEL_EXPR:
     case SWITCH_EXPR:
+    case CHANGE_DYNAMIC_TYPE_EXPR:
     case OMP_FOR:
     case OMP_SECTIONS:
     case OMP_SECTION:
diff --git a/gcc/gimplify.c b/gcc/gimplify.c
index e73e00ae9ae..268bef184cf 100644
--- a/gcc/gimplify.c
+++ b/gcc/gimplify.c
@@ -5791,6 +5791,11 @@ gimplify_expr (tree *expr_p, tree *pre_p, tree *post_p,
 	  ret = GS_ALL_DONE;
 	  break;
 
+	case CHANGE_DYNAMIC_TYPE_EXPR:
+	  ret = gimplify_expr (&CHANGE_DYNAMIC_TYPE_LOCATION (*expr_p),
+			       pre_p, post_p, is_gimple_reg, fb_lvalue);
+	  break;
+
 	case OBJ_TYPE_REF:
 	  {
 	    enum gimplify_status r0, r1;
diff --git a/gcc/omp-low.c b/gcc/omp-low.c
index 234c860418f..5b1f3c4c3d8 100644
--- a/gcc/omp-low.c
+++ b/gcc/omp-low.c
@@ -516,6 +516,7 @@ omp_copy_decl_2 (tree var, tree name, tree type, omp_context *ctx)
 
   TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (var);
   DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (var);
+  DECL_NO_TBAA_P (copy) = DECL_NO_TBAA_P (var);
   DECL_ARTIFICIAL (copy) = DECL_ARTIFICIAL (var);
   DECL_IGNORED_P (copy) = DECL_IGNORED_P (var);
   TREE_USED (copy) = 1;
diff --git a/gcc/print-tree.c b/gcc/print-tree.c
index 7eef3a386d2..7301f47a879 100644
--- a/gcc/print-tree.c
+++ b/gcc/print-tree.c
@@ -401,7 +401,9 @@ print_node (FILE *file, const char *prefix, tree node, int indent)
 	  if (DECL_VIRTUAL_P (node))
 	    fputs (" virtual", file);
 	  if (DECL_PRESERVE_P (node))
-	    fputs (" preserve", file);	  
+	    fputs (" preserve", file);
+	  if (DECL_NO_TBAA_P (node))
+	    fputs (" no-tbaa", file);
 	  if (DECL_LANG_FLAG_0 (node))
 	    fputs (" decl_0", file);
 	  if (DECL_LANG_FLAG_1 (node))
diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog
index 7aec66339d3..dff238910cd 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,11 @@
+2007-06-12  Ian Lance Taylor  <iant@google.com>
+
+	PR libstdc++/29286
+	* g++.dg/init/new16.C: New test.
+	* g++.dg/init/new17.C: New test.
+	* g++.dg/init/new18.C: New test.
+	* g++.dg/init/new19.C: New test.
+
 2007-06-12  Olivier Hainque  <hainque@adacore.com>
 
 	* gnat.dg/lhs_view_convert.adb: New test.
diff --git a/gcc/testsuite/g++.dg/init/new16.C b/gcc/testsuite/g++.dg/init/new16.C
new file mode 100644
index 00000000000..c49f13f833f
--- /dev/null
+++ b/gcc/testsuite/g++.dg/init/new16.C
@@ -0,0 +1,38 @@
+// { dg-do run }
+// { dg-options "-O2 -fstrict-aliasing" }
+
+// Test that we don't let TBAA reorder an assignment across a
+// placement new.
+// See PR 29286.
+
+typedef __SIZE_TYPE__ size_t;
+
+inline void* operator new(size_t, void* __p) throw() { return __p; }
+
+void __attribute__((noinline)) bar() {}
+
+long __attribute__((noinline)) foo(double *p, int n)
+{
+  long *f;
+  for (int i=0; i<n; ++i)
+  {
+    int *l = (int *)p;
+    *l = 0;
+    f = new (p) long;
+    *f = -1;
+  }
+  bar ();
+  return *f;
+}
+
+extern "C" void abort(void);
+int main()
+{
+  union {
+    int i;
+    long l;
+  } u;
+  if (foo((double *)&u, 1) != -1)
+    abort ();
+  return 0;
+}
diff --git a/gcc/testsuite/g++.dg/init/new17.C b/gcc/testsuite/g++.dg/init/new17.C
new file mode 100644
index 00000000000..58782ff5fba
--- /dev/null
+++ b/gcc/testsuite/g++.dg/init/new17.C
@@ -0,0 +1,37 @@
+// { dg-do compile }
+// { dg-options "-O2 -fstrict-aliasing -fdump-tree-final_cleanup" }
+
+// Test that placement new does not introduce an unnecessary memory
+// barrier.
+// See PR 29286.
+
+typedef __SIZE_TYPE__ size_t;
+
+inline void* operator new(size_t, void* __p) throw() { return __p; }
+
+template <class T, int D>
+class Vector
+{
+public:
+   Vector()
+   {
+     for (int i = 0; i < D; ++i)
+        new (&x_m[i]) T();
+   }
+   T& operator[](int i) { return x_m[i]; }
+
+private:
+   T x_m[D];
+};
+
+void foo(Vector<float, 3> *m)
+{
+  Vector<float, 3> v;
+  v[0] = 1.0;
+  v[1] = 2.0;
+  v[3] = 3.0;
+  *m = v;
+}
+
+// { dg-final { scan-tree-dump-times "= 0\.0" 1 "final_cleanup" } }
+// { dg-final { cleanup-tree-dump "final_cleanup" } }
diff --git a/gcc/testsuite/g++.dg/init/new18.C b/gcc/testsuite/g++.dg/init/new18.C
new file mode 100644
index 00000000000..45f6e7a095d
--- /dev/null
+++ b/gcc/testsuite/g++.dg/init/new18.C
@@ -0,0 +1,45 @@
+// { dg-do compile }
+// { dg-options "-O2 -fstrict-aliasing" }
+
+// This caused an ICE during placement new.
+
+namespace Pooma {
+   typedef int Context_t;
+   namespace Arch {
+   }
+   inline Context_t context() {
+  }
+   inline int contexts() {
+  }
+ }
+template<class DomT, class T, class NewDom1T> struct DomainTraitsScalar {
+  };
+template<class T> struct DomainTraits : public DomainTraitsScalar<T, T, T> {
+  };
+template<int Dim> class Grid;
+template<class DT> class DomainBase {
+  };
+template<int Dim, class DT> class Domain : public DomainBase<DT> {
+  };
+#include <vector>
+template<> class Grid<1> : public Domain<1, DomainTraits<Grid<1> > > {
+  };
+namespace Pooma {
+ class PatchSizeSyncer {
+    typedef Grid<1> Grid_t;
+    PatchSizeSyncer(int contextKey, Grid_t &localGrid);
+    int myContext_m;
+    int numContexts_m;
+    int localKey_m;
+    Grid_t localGrid_m;
+    typedef std::pair<int,Grid_t *> Elem_t;
+    std::vector<Elem_t> gridList_m;
+  };
+ }
+namespace Pooma {
+ PatchSizeSyncer::PatchSizeSyncer(int contextKey, Grid_t &localGrid)   :
+myContext_m(Pooma::context()),     numContexts_m(Pooma::contexts()),    
+localKey_m(contextKey),     localGrid_m(localGrid) {
+    if (myContext_m == 0) gridList_m.reserve(numContexts_m);
+  }
+ }
diff --git a/gcc/testsuite/g++.dg/init/new19.C b/gcc/testsuite/g++.dg/init/new19.C
new file mode 100644
index 00000000000..a139a35aa05
--- /dev/null
+++ b/gcc/testsuite/g++.dg/init/new19.C
@@ -0,0 +1,73 @@
+// { dg-do compile }
+// { dg-options "-O2 -fstrict-aliasing -fdump-tree-lim-details" }
+
+// Make sure we hoist invariants out of the loop even in the presence
+// of placement new.  This is similar to code in tramp3d.
+
+typedef __SIZE_TYPE__ size_t;
+
+inline void* operator new(size_t, void* __p) throw() { return __p; }
+
+template <class T, int D>
+class Vector
+{
+public:
+   Vector()
+   {
+     for (int i = 0; i < D; ++i)
+        new (&x_m[i]) T();
+   }
+   T& operator[](int i) { return x_m[i]; }
+
+private:
+   T x_m[D];
+};
+
+struct sia
+{
+  int ai[3];
+};
+
+struct s
+{
+  struct si
+  {
+    sia* p;
+  } asi[3];
+  float* pd;
+};
+
+class c
+{
+  int foo(int, int, int);
+  s sm;
+};
+
+
+extern void bar(Vector<float, 3>*, int);
+int c::foo(int f1, int f2, int f3)
+{
+  float sum = 0;
+  for (int i = 0; i < 3; ++i)
+    {
+      for (int j = 0; j < 3; ++j)
+	{
+	  Vector<float, 3> v;
+	  v[0] = 1.0;
+	  v[1] = 2.0;
+	  v[2] = 3.0;
+	  for (int k = 0; k < 3; ++k)
+	    {
+	      float f = (f1 * this->sm.asi[0].p->ai[0]
+			 + f2 * this->sm.asi[1].p->ai[0]
+			 + f3 * this->sm.asi[2].p->ai[0]);
+	      sum += f * v[k];
+	    }
+	  *this->sm.pd = sum;
+	}
+    }
+  return sum;
+}
+
+// { dg-final { scan-tree-dump "Moving statement\\n.*->ai\\\[0\\\];\\n.*out of loop" "lim" } }
+// { dg-final { cleanup-tree-dump "lim" } }
diff --git a/gcc/tree-gimple.c b/gcc/tree-gimple.c
index 5530afb231d..16caf0ad573 100644
--- a/gcc/tree-gimple.c
+++ b/gcc/tree-gimple.c
@@ -1,5 +1,6 @@
 /* Functions to analyze and validate GIMPLE trees.
-   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
+   Free Software Foundation, Inc.
    Contributed by Diego Novillo <dnovillo@redhat.com>
    Rewritten by Jason Merrill <jason@redhat.com>
 
@@ -222,6 +223,7 @@ is_gimple_stmt (tree t)
     case TRY_FINALLY_EXPR:
     case EH_FILTER_EXPR:
     case CATCH_EXPR:
+    case CHANGE_DYNAMIC_TYPE_EXPR:
     case ASM_EXPR:
     case RESX_EXPR:
     case PHI_NODE:
diff --git a/gcc/tree-inline.c b/gcc/tree-inline.c
index 799b4f3fb6e..11d400afe61 100644
--- a/gcc/tree-inline.c
+++ b/gcc/tree-inline.c
@@ -2030,6 +2030,11 @@ estimate_num_insns_1 (tree *tp, int *walk_subtrees, void *data)
       *walk_subtrees = 0;
       return NULL;
 
+      /* CHANGE_DYNAMIC_TYPE_EXPR explicitly expands to nothing.  */
+    case CHANGE_DYNAMIC_TYPE_EXPR:
+      *walk_subtrees = 0;
+      return NULL;
+
     /* Try to estimate the cost of assignments.  We have three cases to
        deal with:
 	1) Simple assignments to registers;
@@ -3217,6 +3222,7 @@ copy_decl_to_var (tree decl, copy_body_data *id)
   TREE_READONLY (copy) = TREE_READONLY (decl);
   TREE_THIS_VOLATILE (copy) = TREE_THIS_VOLATILE (decl);
   DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (decl);
+  DECL_NO_TBAA_P (copy) = DECL_NO_TBAA_P (decl);
 
   return copy_decl_for_dup_finish (id, decl, copy);
 }
@@ -3243,6 +3249,7 @@ copy_result_decl_to_var (tree decl, copy_body_data *id)
     {
       TREE_ADDRESSABLE (copy) = TREE_ADDRESSABLE (decl);
       DECL_GIMPLE_REG_P (copy) = DECL_GIMPLE_REG_P (decl);
+      DECL_NO_TBAA_P (copy) = DECL_NO_TBAA_P (decl);
     }
 
   return copy_decl_for_dup_finish (id, decl, copy);
diff --git a/gcc/tree-pretty-print.c b/gcc/tree-pretty-print.c
index 7cfd4b51a14..0c313f20e88 100644
--- a/gcc/tree-pretty-print.c
+++ b/gcc/tree-pretty-print.c
@@ -1496,6 +1496,17 @@ dump_generic_node (pretty_printer *buffer, tree node, int spc, int flags,
       is_expr = false;
       break;
 
+    case CHANGE_DYNAMIC_TYPE_EXPR:
+      pp_string (buffer, "<<<change_dynamic_type (");
+      dump_generic_node (buffer, CHANGE_DYNAMIC_TYPE_NEW_TYPE (node), spc + 2,
+			 flags, false);
+      pp_string (buffer, ") ");
+      dump_generic_node (buffer, CHANGE_DYNAMIC_TYPE_LOCATION (node), spc + 2,
+			 flags, false);
+      pp_string (buffer, ")>>>");
+      is_expr = false;
+      break;
+
     case LABEL_EXPR:
       op0 = TREE_OPERAND (node, 0);
       /* If this is for break or continue, don't bother printing it.  */
diff --git a/gcc/tree-ssa-alias.c b/gcc/tree-ssa-alias.c
index 9fa312919c7..cf5dc2b45e7 100644
--- a/gcc/tree-ssa-alias.c
+++ b/gcc/tree-ssa-alias.c
@@ -1,5 +1,5 @@
 /* Alias analysis for trees.
-   Copyright (C) 2004, 2005 Free Software Foundation, Inc.
+   Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
    Contributed by Diego Novillo <dnovillo@redhat.com>
 
 This file is part of GCC.
@@ -2720,69 +2720,72 @@ may_alias_p (tree ptr, HOST_WIDE_INT mem_alias_set,
 
   gcc_assert (TREE_CODE (mem) == SYMBOL_MEMORY_TAG);
 
-  alias_stats.tbaa_queries++;
-
-  /* If the alias sets don't conflict then MEM cannot alias VAR.  */
-  if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
+  if (!DECL_NO_TBAA_P (ptr))
     {
-      alias_stats.alias_noalias++;
-      alias_stats.tbaa_resolved++;
-      return false;
-    }
+      alias_stats.tbaa_queries++;
 
-  /* If VAR is a record or union type, PTR cannot point into VAR
-     unless there is some explicit address operation in the
-     program that can reference a field of the type pointed-to by PTR.
-     This also assumes that the types of both VAR and PTR are
-     contained within the compilation unit, and that there is no fancy
-     addressing arithmetic associated with any of the types
-     involved.  */
-  if (mem_alias_set != 0 && var_alias_set != 0)
-    {
-      tree ptr_type = TREE_TYPE (ptr);
-      tree var_type = TREE_TYPE (var);
-      
-      /* The star count is -1 if the type at the end of the pointer_to 
-	 chain is not a record or union type. */ 
-      if ((!alias_set_only) && 
-	  ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
+      /* If the alias sets don't conflict then MEM cannot alias VAR.  */
+      if (!alias_sets_conflict_p (mem_alias_set, var_alias_set))
 	{
-	  int ptr_star_count = 0;
-	  
-	  /* ipa_type_escape_star_count_of_interesting_type is a
-	     little too restrictive for the pointer type, need to
-	     allow pointers to primitive types as long as those types
-	     cannot be pointers to everything.  */
-	  while (POINTER_TYPE_P (ptr_type))
+	  alias_stats.alias_noalias++;
+	  alias_stats.tbaa_resolved++;
+	  return false;
+	}
+
+      /* If VAR is a record or union type, PTR cannot point into VAR
+	 unless there is some explicit address operation in the
+	 program that can reference a field of the type pointed-to by
+	 PTR.  This also assumes that the types of both VAR and PTR
+	 are contained within the compilation unit, and that there is
+	 no fancy addressing arithmetic associated with any of the
+	 types involved.  */
+      if (mem_alias_set != 0 && var_alias_set != 0)
+	{
+	  tree ptr_type = TREE_TYPE (ptr);
+	  tree var_type = TREE_TYPE (var);
+      
+	  /* The star count is -1 if the type at the end of the
+	     pointer_to chain is not a record or union type. */ 
+	  if ((!alias_set_only) && 
+	      ipa_type_escape_star_count_of_interesting_type (var_type) >= 0)
 	    {
-	      /* Strip the *s off.  */ 
-	      ptr_type = TREE_TYPE (ptr_type);
-	      ptr_star_count++;
-	    }
+	      int ptr_star_count = 0;
 	  
-	  /* There does not appear to be a better test to see if the 
-	     pointer type was one of the pointer to everything 
-	     types.  */
-	  if (ptr_star_count > 0)
-	    {
-	      alias_stats.structnoaddress_queries++;
-	      if (ipa_type_escape_field_does_not_clobber_p (var_type, 
-							    TREE_TYPE (ptr))) 
+	      /* ipa_type_escape_star_count_of_interesting_type is a
+		 little too restrictive for the pointer type, need to
+		 allow pointers to primitive types as long as those
+		 types cannot be pointers to everything.  */
+	      while (POINTER_TYPE_P (ptr_type))
+		{
+		  /* Strip the *s off.  */ 
+		  ptr_type = TREE_TYPE (ptr_type);
+		  ptr_star_count++;
+		}
+	  
+	      /* There does not appear to be a better test to see if
+		 the pointer type was one of the pointer to everything
+		 types.  */
+	      if (ptr_star_count > 0)
 		{
+		  alias_stats.structnoaddress_queries++;
+		  if (ipa_type_escape_field_does_not_clobber_p (var_type, 
+								TREE_TYPE (ptr)))
+		    {
+		      alias_stats.structnoaddress_resolved++;
+		      alias_stats.alias_noalias++;
+		      return false;
+		    }
+		}
+	      else if (ptr_star_count == 0)
+		{
+		  /* If PTR_TYPE was not really a pointer to type, it cannot 
+		     alias.  */ 
+		  alias_stats.structnoaddress_queries++;
 		  alias_stats.structnoaddress_resolved++;
 		  alias_stats.alias_noalias++;
 		  return false;
 		}
 	    }
-	  else if (ptr_star_count == 0)
-	    {
-	      /* If PTR_TYPE was not really a pointer to type, it cannot 
-		 alias.  */ 
-	      alias_stats.structnoaddress_queries++;
-	      alias_stats.structnoaddress_resolved++;
-	      alias_stats.alias_noalias++;
-	      return false;
-	    }
 	}
     }
 
diff --git a/gcc/tree-ssa-dce.c b/gcc/tree-ssa-dce.c
index a2f80aa308f..d0335a0593f 100644
--- a/gcc/tree-ssa-dce.c
+++ b/gcc/tree-ssa-dce.c
@@ -1,5 +1,6 @@
 /* Dead code elimination pass for the GNU compiler.
-   Copyright (C) 2002, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
+   Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007
+   Free Software Foundation, Inc.
    Contributed by Ben Elliston <bje@redhat.com>
    and Andrew MacLeod <amacleod@redhat.com>
    Adapted to use control dependence by Steven Bosscher, SUSE Labs.
@@ -286,6 +287,7 @@ mark_stmt_if_obviously_necessary (tree stmt, bool aggressive)
     case ASM_EXPR:
     case RESX_EXPR:
     case RETURN_EXPR:
+    case CHANGE_DYNAMIC_TYPE_EXPR:
       mark_stmt_necessary (stmt, true);
       return;
 
diff --git a/gcc/tree-ssa-operands.c b/gcc/tree-ssa-operands.c
index d015a569cd2..edd2b902188 100644
--- a/gcc/tree-ssa-operands.c
+++ b/gcc/tree-ssa-operands.c
@@ -2266,6 +2266,10 @@ get_expr_operands (tree stmt, tree *expr_p, int flags)
         return;
       }
 
+    case CHANGE_DYNAMIC_TYPE_EXPR:
+      get_expr_operands (stmt, &CHANGE_DYNAMIC_TYPE_LOCATION (expr), opf_use);
+      return;
+
     case BLOCK:
     case FUNCTION_DECL:
     case EXC_PTR_EXPR:
diff --git a/gcc/tree-ssa-structalias.c b/gcc/tree-ssa-structalias.c
index d351bf503c2..c5dbf5c5d7f 100644
--- a/gcc/tree-ssa-structalias.c
+++ b/gcc/tree-ssa-structalias.c
@@ -250,6 +250,10 @@ struct variable_info
   /* True if this is a heap variable.  */
   unsigned int is_heap_var:1;
 
+  /* True if we may not use TBAA to prune references to this
+     variable.  This is used for C++ placement new.  */
+  unsigned int no_tbaa_pruning : 1;
+
   /* Points-to set for this variable.  */
   bitmap solution;
 
@@ -359,6 +363,7 @@ static varinfo_t
 new_var_info (tree t, unsigned int id, const char *name)
 {
   varinfo_t ret = (varinfo_t) pool_alloc (variable_info_pool);
+  tree var;
 
   ret->id = id;
   ret->name = name;
@@ -369,6 +374,12 @@ new_var_info (tree t, unsigned int id, const char *name)
   ret->is_special_var = false;
   ret->is_unknown_size_var = false;
   ret->has_union = false;
+  var = t;
+  if (TREE_CODE (var) == SSA_NAME)
+    var = SSA_NAME_VAR (var);
+  ret->no_tbaa_pruning = (DECL_P (var)
+			  && POINTER_TYPE_P (TREE_TYPE (var))
+			  && DECL_NO_TBAA_P (var));
   ret->solution = BITMAP_ALLOC (&pta_obstack);
   ret->oldsolution = BITMAP_ALLOC (&oldpta_obstack);
   ret->next = NULL;
@@ -1195,6 +1206,9 @@ unify_nodes (constraint_graph_t graph, unsigned int to, unsigned int from,
   merge_graph_nodes (graph, to, from);
   merge_node_constraints (graph, to, from);
 
+  if (get_varinfo (from)->no_tbaa_pruning)
+    get_varinfo (to)->no_tbaa_pruning = true;
+
   if (update_changed && TEST_BIT (changed, from))
     {
       RESET_BIT (changed, from);
@@ -3563,6 +3577,14 @@ find_func_aliases (tree origt)
 	    }
 	}
     }
+  else if (TREE_CODE (t) == CHANGE_DYNAMIC_TYPE_EXPR)
+    {
+      unsigned int j;
+
+      get_constraint_for (CHANGE_DYNAMIC_TYPE_LOCATION (t), &lhsc);
+      for (j = 0; VEC_iterate (ce_s, lhsc, j, c); ++j)
+	get_varinfo (c->var)->no_tbaa_pruning = true;
+    }
 
   /* After promoting variables and computing aliasing we will
      need to re-scan most statements.  FIXME: Try to minimize the
@@ -4130,7 +4152,10 @@ dump_solution_for_var (FILE *file, unsigned int var)
 	{
 	  fprintf (file, "%s ", get_varinfo (i)->name);
 	}
-      fprintf (file, "}\n");
+      fprintf (file, "}");
+      if (vi->no_tbaa_pruning)
+	fprintf (file, " no-tbaa-pruning");
+      fprintf (file, "\n");
     }
 }
 
@@ -4292,10 +4317,13 @@ shared_bitmap_add (bitmap pt_vars)
    For variables that are actually dereferenced, we also use type
    based alias analysis to prune the points-to sets.
    IS_DEREFED is true if PTR was directly dereferenced, which we use to
-   help determine whether we are we are allowed to prune using TBAA.  */
+   help determine whether we are we are allowed to prune using TBAA.
+   If NO_TBAA_PRUNING is true, we do not perform any TBAA pruning of
+   the from set.  */
 
 static void
-set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed)
+set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed,
+		   bool no_tbaa_pruning)
 {
   unsigned int i;
   bitmap_iterator bi;
@@ -4331,7 +4359,8 @@ set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed)
 	      if (sft)
 		{
 		  var_alias_set = get_alias_set (sft);
-		  if ((!is_derefed && !vi->directly_dereferenced)
+		  if (no_tbaa_pruning
+		      || (!is_derefed && !vi->directly_dereferenced)
 		      || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
 		    bitmap_set_bit (into, DECL_UID (sft));
 		}
@@ -4345,7 +4374,8 @@ set_uids_in_ptset (tree ptr, bitmap into, bitmap from, bool is_derefed)
 	      else
 		{
 		  var_alias_set = get_alias_set (vi->decl);
-		  if ((!is_derefed && !vi->directly_dereferenced)
+		  if (no_tbaa_pruning
+		      || (!is_derefed && !vi->directly_dereferenced)
 		      || alias_sets_conflict_p (ptr_alias_set, var_alias_set))
 		    bitmap_set_bit (into, DECL_UID (vi->decl));
 		}
@@ -4558,7 +4588,8 @@ find_what_p_points_to (tree p)
 	    }
 	  
 	  set_uids_in_ptset (vi->decl, finished_solution, vi->solution,
-			     vi->directly_dereferenced);
+			     vi->directly_dereferenced,
+			     vi->no_tbaa_pruning);
 	  result = shared_bitmap_lookup (finished_solution);
 
 	  if (!result)
@@ -4784,6 +4815,142 @@ remove_preds_and_fake_succs (constraint_graph_t graph)
   bitmap_obstack_release (&predbitmap_obstack);
 }
 
+/* Compute the set of variables we can't TBAA prune.  */
+
+static void
+compute_tbaa_pruning (void)
+{
+  unsigned int size = VEC_length (varinfo_t, varmap);
+  unsigned int i;
+  bool any;
+
+  changed_count = 0;
+  changed = sbitmap_alloc (size);
+  sbitmap_zero (changed);
+
+  /* Mark all initial no_tbaa_pruning nodes as changed.  */
+  any = false;
+  for (i = 0; i < size; ++i)
+    {
+      varinfo_t ivi = get_varinfo (i);
+
+      if (find (i) == i && ivi->no_tbaa_pruning)
+	{
+	  any = true;
+	  if ((graph->succs[i] && !bitmap_empty_p (graph->succs[i]))
+	      || VEC_length (constraint_t, graph->complex[i]) > 0)
+	    {
+	      SET_BIT (changed, i);
+	      ++changed_count;
+	    }
+	}
+    }
+
+  while (changed_count > 0)
+    {
+      struct topo_info *ti = init_topo_info ();
+      ++stats.iterations;
+
+      bitmap_obstack_initialize (&iteration_obstack);
+
+      compute_topo_order (graph, ti);
+
+      while (VEC_length (unsigned, ti->topo_order) != 0)
+	{
+	  bitmap_iterator bi;
+
+	  i = VEC_pop (unsigned, ti->topo_order);
+
+	  /* If this variable is not a representative, skip it.  */
+	  if (find (i) != i)
+	    continue;
+
+	  /* If the node has changed, we need to process the complex
+	     constraints and outgoing edges again.  */
+	  if (TEST_BIT (changed, i))
+	    {
+	      unsigned int j;
+	      constraint_t c;
+	      VEC(constraint_t,heap) *complex = graph->complex[i];
+
+	      RESET_BIT (changed, i);
+	      --changed_count;
+
+	      /* Process the complex copy constraints.  */
+	      for (j = 0; VEC_iterate (constraint_t, complex, j, c); ++j)
+		{
+		  if (c->lhs.type == SCALAR && c->rhs.type == SCALAR)
+		    {
+		      varinfo_t lhsvi = get_varinfo (find (c->lhs.var));
+
+		      if (!lhsvi->no_tbaa_pruning)
+			{
+			  lhsvi->no_tbaa_pruning = true;
+			  if (!TEST_BIT (changed, lhsvi->id))
+			    {
+			      SET_BIT (changed, lhsvi->id);
+			      ++changed_count;
+			    }
+			}
+		    }
+		}
+
+	      /* Propagate to all successors.  */
+	      EXECUTE_IF_IN_NONNULL_BITMAP (graph->succs[i], 0, j, bi)
+		{
+		  unsigned int to = find (j);
+		  varinfo_t tovi = get_varinfo (to);
+
+		  /* Don't propagate to ourselves.  */
+		  if (to == i)
+		    continue;
+
+		  if (!tovi->no_tbaa_pruning)
+		    {
+		      tovi->no_tbaa_pruning = true;
+		      if (!TEST_BIT (changed, to))
+			{
+			  SET_BIT (changed, to);
+			  ++changed_count;
+			}
+		    }
+		}
+	    }
+	}
+
+      free_topo_info (ti);
+      bitmap_obstack_release (&iteration_obstack);
+    }
+
+  sbitmap_free (changed);
+
+  if (any)
+    {
+      for (i = 0; i < size; ++i)
+	{
+	  varinfo_t ivi = get_varinfo (i);
+	  varinfo_t ivip = get_varinfo (find (i));
+
+	  if (ivip->no_tbaa_pruning)
+	    {
+	      tree var = ivi->decl;
+
+	      if (TREE_CODE (var) == SSA_NAME)
+		var = SSA_NAME_VAR (var);
+
+	      if (POINTER_TYPE_P (TREE_TYPE (var)))
+		{
+		  DECL_NO_TBAA_P (var) = 1;
+
+		  /* Tell the RTL layer that this pointer can alias
+		     anything.  */
+		  DECL_POINTER_ALIAS_SET (var) = 0;
+		}
+	    }
+	}
+    }
+}
+
 /* Create points-to sets for the current function.  See the comments
    at the start of the file for an algorithmic overview.  */
 
@@ -4820,7 +4987,7 @@ compute_points_to_sets (struct alias_info *ai)
 	    }
 	}
 
-      for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
+      for (bsi = bsi_start (bb); !bsi_end_p (bsi); )
 	{
 	  tree stmt = bsi_stmt (bsi);
 
@@ -4831,6 +4998,13 @@ compute_points_to_sets (struct alias_info *ai)
 	     This is used when creating name tags and alias
 	     sets.  */
 	  update_alias_info (stmt, ai);
+
+	  /* The information in CHANGE_DYNAMIC_TYPE_EXPR nodes has now
+	     been captured, and we can remove them.  */
+	  if (TREE_CODE (stmt) == CHANGE_DYNAMIC_TYPE_EXPR)
+	    bsi_remove (&bsi, true);
+	  else
+	    bsi_next (&bsi);
 	}
     }
 
@@ -4862,6 +5036,8 @@ compute_points_to_sets (struct alias_info *ai)
 
   solve_graph (graph);
 
+  compute_tbaa_pruning ();
+
   if (dump_file)
     dump_sa_points_to_info (dump_file);
 
diff --git a/gcc/tree.def b/gcc/tree.def
index e1f5fef063e..d4038322bcd 100644
--- a/gcc/tree.def
+++ b/gcc/tree.def
@@ -1,7 +1,7 @@
 /* This file contains the definitions and documentation for the
    tree codes used in GCC.
    Copyright (C) 1987, 1988, 1993, 1995, 1997, 1998, 2000, 2001, 2004, 2005, 
-   2006 Free Software Foundation, Inc.
+   2006, 2007 Free Software Foundation, Inc.
 
 This file is part of GCC.
 
@@ -876,6 +876,15 @@ DEFTREECODE (CATCH_EXPR, "catch_expr", tcc_statement, 2)
    expanding.  */
 DEFTREECODE (EH_FILTER_EXPR, "eh_filter_expr", tcc_statement, 2)
 
+/* Indicates a change in the dynamic type of a memory location.  This
+   has no value and generates no executable code.  It is only used for
+   type based alias analysis.  This is generated by C++ placement new.
+   CHANGE_DYNAMIC_TYPE_NEW_TYPE, the first operand, is the new type.
+   CHNAGE_DYNAMIC_TYPE_LOCATION, the second operand, is the location
+   whose type is being changed.  */
+DEFTREECODE (CHANGE_DYNAMIC_TYPE_EXPR, "change_dynamic_type_expr",
+	     tcc_statement, 2)
+
 /* Node used for describing a property that is known at compile
    time.  */
 DEFTREECODE (SCEV_KNOWN, "scev_known", tcc_expression, 0)
diff --git a/gcc/tree.h b/gcc/tree.h
index 572a1e7c6f9..aefc00ee33a 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -1637,6 +1637,12 @@ struct tree_constructor GTY(())
 #define EH_FILTER_FAILURE(NODE)	TREE_OPERAND (EH_FILTER_EXPR_CHECK (NODE), 1)
 #define EH_FILTER_MUST_NOT_THROW(NODE) TREE_STATIC (EH_FILTER_EXPR_CHECK (NODE))
 
+/* CHANGE_DYNAMIC_TYPE_EXPR accessors.  */
+#define CHANGE_DYNAMIC_TYPE_NEW_TYPE(NODE) \
+  TREE_OPERAND (CHANGE_DYNAMIC_TYPE_EXPR_CHECK (NODE), 0)
+#define CHANGE_DYNAMIC_TYPE_LOCATION(NODE) \
+  TREE_OPERAND (CHANGE_DYNAMIC_TYPE_EXPR_CHECK (NODE), 1)
+
 /* OBJ_TYPE_REF accessors.  */
 #define OBJ_TYPE_REF_EXPR(NODE)	  TREE_OPERAND (OBJ_TYPE_REF_CHECK (NODE), 0)
 #define OBJ_TYPE_REF_OBJECT(NODE) TREE_OPERAND (OBJ_TYPE_REF_CHECK (NODE), 1)
@@ -2671,6 +2677,11 @@ struct tree_memory_partition_tag GTY(())
 #define DECL_GIMPLE_REG_P(DECL) \
   DECL_COMMON_CHECK (DECL)->decl_common.gimple_reg_flag
 
+/* For a DECL with pointer type, this is set if Type Based Alias
+   Analysis should not be applied to this DECL.  */
+#define DECL_NO_TBAA_P(DECL) \
+  DECL_COMMON_CHECK (DECL)->decl_common.no_tbaa_flag
+
 struct tree_decl_common GTY(())
 {
   struct tree_decl_minimal common;
@@ -2711,6 +2722,8 @@ struct tree_decl_common GTY(())
   /* Logically, these two would go in a theoretical base shared by var and
      parm decl. */
   unsigned gimple_reg_flag : 1;
+  /* In a DECL with pointer type, set if no TBAA should be done.  */
+  unsigned no_tbaa_flag : 1;
 
   union tree_decl_u1 {
     /* In a FUNCTION_DECL for which DECL_BUILT_IN holds, this is