[V2] malloc cannot alias preexisting pointers

Message ID alpine.DEB.2.21.1905140124050.22636@stedding.saclay.inria.fr
State New
Headers show
Series
  • [V2] malloc cannot alias preexisting pointers
Related show

Commit Message

Marc Glisse May 13, 2019, 11:40 p.m.
Here is a version of the patch with a cheaper test, and an extra testcase 
for Martin.

(I kept the tree-ssa-loop-niter.c part although I am not using it anymore)

2019-05-15  Marc Glisse  <marc.glisse@inria.fr>

gcc/
         * tree-ssa-loop-niter.c (stmt_dominates_stmt_p): Handle NULL
         basic block.
         * tree-ssa-alias.c (quick_stmt_dominates_stmt_p): New function.
         (ptr_derefs_may_alias_p): Detect malloc and an older pointer.

gcc/testsuite/
         * g++.dg/tree-ssa/ldist-2.C: New file.
         * gcc.dg/alias-17.c: New file.

-- 
Marc Glisse

Patch

Index: gcc/testsuite/g++.dg/tree-ssa/ldist-2.C
===================================================================
--- gcc/testsuite/g++.dg/tree-ssa/ldist-2.C	(nonexistent)
+++ gcc/testsuite/g++.dg/tree-ssa/ldist-2.C	(working copy)
@@ -0,0 +1,14 @@ 
+// { dg-do compile { target c++11 } }
+// { dg-options "-O3 -fdump-tree-optimized" }
+
+#include <vector>
+#include <memory>
+#include <new>
+// Remove those 2 inlines once gcc knows that new/delete are special
+inline void* operator new(std::size_t n){return malloc(n);}
+inline void operator delete(void*p){free(p);}
+typedef std::unique_ptr<int> T;
+typedef std::vector<T> V;
+void f(V&v){v.reserve(1024);}
+
+/* { dg-final { scan-tree-dump "memcpy" "optimized" } } */
Index: gcc/testsuite/gcc.dg/alias-17.c
===================================================================
--- gcc/testsuite/gcc.dg/alias-17.c	(nonexistent)
+++ gcc/testsuite/gcc.dg/alias-17.c	(working copy)
@@ -0,0 +1,16 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+__attribute__((malloc)) void*mymalloc(void);
+int g;
+int*f(int**p){
+  int*q=*p;
+  if(!q)return 0; // new basic block, because the optimization is weak
+  int*r=mymalloc();
+  *q=1;
+  *r=2;
+  g=*q;
+  return r;
+}
+
+/* { dg-final { scan-tree-dump "g = 1;" "optimized"} } */
Index: gcc/tree-ssa-alias.c
===================================================================
--- gcc/tree-ssa-alias.c	(revision 271135)
+++ gcc/tree-ssa-alias.c	(working copy)
@@ -118,20 +118,42 @@  dump_alias_stats (FILE *s)
 	   + alias_stats.ref_maybe_used_by_call_p_may_alias);
   fprintf (s, "  call_may_clobber_ref_p: "
 	   HOST_WIDE_INT_PRINT_DEC" disambiguations, "
 	   HOST_WIDE_INT_PRINT_DEC" queries\n",
 	   alias_stats.call_may_clobber_ref_p_no_alias,
 	   alias_stats.call_may_clobber_ref_p_no_alias
 	   + alias_stats.call_may_clobber_ref_p_may_alias);
   dump_alias_stats_in_alias_c (s);
 }
 
+/* A faster, weaker version of stmt_dominates_stmt_p.  */
+
+static bool
+quick_stmt_dominates_stmt_p (gimple *s1, gimple *s2)
+{
+  basic_block bb1 = gimple_bb (s1), bb2 = gimple_bb (s2);
+
+  if (!bb1
+      || s1 == s2)
+    return true;
+
+  if (!bb2)
+    return false;
+
+  if (bb1 == bb2)
+    /* Punt. Except in a few passes that maintain UIDs, the only way to answer
+       is to walk through statements, which is too expensive.  */
+    return false;
+
+  return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
+}
+
 
 /* Return true, if dereferencing PTR may alias with a global variable.  */
 
 bool
 ptr_deref_may_alias_global_p (tree ptr)
 {
   struct ptr_info_def *pi;
 
   /* If we end up with a pointer constant here that may point
      to global memory.  */
@@ -284,20 +306,39 @@  ptr_derefs_may_alias_p (tree ptr1, tree
       || !POINTER_TYPE_P (TREE_TYPE (ptr1))
       || !POINTER_TYPE_P (TREE_TYPE (ptr2)))
     return true;
 
   /* We may end up with two empty points-to solutions for two same pointers.
      In this case we still want to say both pointers alias, so shortcut
      that here.  */
   if (ptr1 == ptr2)
     return true;
 
+  /* Memory returned by malloc cannot alias with a pre-existing pointer.
+     This is extremely crude, the order between the statements may be quite
+     arbitrary.  */
+  if (in_gimple_form && dom_info_available_p (cfun, CDI_DOMINATORS))
+    {
+      gimple *def1 = SSA_NAME_DEF_STMT (ptr1);
+      gimple *def2 = SSA_NAME_DEF_STMT (ptr2);
+      tree decl;
+      if ((is_gimple_call (def2)
+	   && (decl = gimple_call_fndecl (def2))
+	   && DECL_IS_MALLOC (decl)
+	   && quick_stmt_dominates_stmt_p (def1, def2))
+	  || (is_gimple_call (def1)
+	      && (decl = gimple_call_fndecl (def1))
+	      && DECL_IS_MALLOC (decl)
+	      && quick_stmt_dominates_stmt_p (def2, def1)))
+	return false;
+    }
+
   /* If we do not have useful points-to information for either pointer
      we cannot disambiguate anything else.  */
   pi1 = SSA_NAME_PTR_INFO (ptr1);
   pi2 = SSA_NAME_PTR_INFO (ptr2);
   if (!pi1 || !pi2)
     return true;
 
   /* ???  This does not use TBAA to prune decls from the intersection
      that not both pointers may access.  */
   return pt_solutions_intersect (&pi1->pt, &pi2->pt);
Index: gcc/tree-ssa-loop-niter.c
===================================================================
--- gcc/tree-ssa-loop-niter.c	(revision 271135)
+++ gcc/tree-ssa-loop-niter.c	(working copy)
@@ -4433,20 +4433,23 @@  stmt_dominates_stmt_p (gimple *s1, gimpl
       if (gimple_code (s1) == GIMPLE_PHI)
 	return true;
 
       for (bsi = gsi_start_bb (bb1); gsi_stmt (bsi) != s2; gsi_next (&bsi))
 	if (gsi_stmt (bsi) == s1)
 	  return true;
 
       return false;
     }
 
+  if (!bb2)
+    return false;
+
   return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
 }
 
 /* Returns true when we can prove that the number of executions of
    STMT in the loop is at most NITER, according to the bound on
    the number of executions of the statement NITER_BOUND->stmt recorded in
    NITER_BOUND and fact that NITER_BOUND->stmt dominate STMT.
 
    ??? This code can become quite a CPU hog - we can have many bounds,
    and large basic block forcing stmt_dominates_stmt_p to be queried