diff mbox

[RFC] replace malloc with a decl on the stack

Message ID alpine.DEB.2.02.1311102246280.7470@stedding.saclay.inria.fr
State New
Headers show

Commit Message

Marc Glisse Nov. 10, 2013, 10:06 p.m. UTC
On Sun, 10 Nov 2013, Marc Glisse wrote:

> I am posting this patch to get some feedback on the approach. The goal is to 
> replace malloc+free with a stack allocation (a decl actually) when the size 
> is a small constant.

A slightly updated version that handles abort and if(VAR==0) where VAR is 
the return value of malloc. I was confused because gimple.def doesn't warn 
that the labels in a GIMPLE_COND are unused most of the time.

Joost, if you replace #if 0 with #if 1 in the patch, it handles your 
testcase from PR 38318, though obviously I can't do that for C.

(warning: I didn't rerun the testsuite)
diff mbox

Patch

Index: testsuite/g++.dg/tree-ssa/heapstack-1.C
===================================================================
--- testsuite/g++.dg/tree-ssa/heapstack-1.C	(revision 0)
+++ testsuite/g++.dg/tree-ssa/heapstack-1.C	(working copy)
@@ -0,0 +1,24 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+struct A {
+  void*p;
+  A(void*q) : p(q) {}
+  ~A(){ __builtin_free(p); }
+};
+void f(void*)__attribute__((__leaf__));
+void h(void*)__attribute__((__leaf__,__nothrow__));
+void g(){
+  void*p=__builtin_malloc(12);
+  A a(p);
+  f(p);
+}
+
+void i(){
+  void*p=__builtin_malloc(12);
+  h(p);
+  __builtin_free(p);
+}
+
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */

Property changes on: testsuite/g++.dg/tree-ssa/heapstack-1.C
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: testsuite/g++.dg/tree-ssa/heapstack-2.C
===================================================================
--- testsuite/g++.dg/tree-ssa/heapstack-2.C	(revision 0)
+++ testsuite/g++.dg/tree-ssa/heapstack-2.C	(working copy)
@@ -0,0 +1,12 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void f(void*)__attribute__((__leaf__));
+void g(){
+  void*p=__builtin_malloc(12);
+  f(p);
+  __builtin_free(p);
+}
+
+/* { dg-final { scan-tree-dump-times "malloc" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */

Property changes on: testsuite/g++.dg/tree-ssa/heapstack-2.C
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: testsuite/gcc.dg/tree-ssa/heapstack-1.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/heapstack-1.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/heapstack-1.c	(working copy)
@@ -0,0 +1,23 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void* f(void*)__attribute__((__pure__));
+void *q;
+void g(int m,int n){
+  int i;
+  void*p=__builtin_malloc(12);
+  switch(n){
+    case 1:
+      for (i=0; i<m; ++i)
+	q=f(p);
+      break;
+    case 2:
+      __builtin_free(p);
+      __builtin_exit(42);
+    default:;
+  }
+  __builtin_free(p);
+}
+
+/* { dg-final { scan-tree-dump-not "malloc" "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */

Property changes on: testsuite/gcc.dg/tree-ssa/heapstack-1.c
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: testsuite/gcc.dg/tree-ssa/heapstack-2.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/heapstack-2.c	(revision 0)
+++ testsuite/gcc.dg/tree-ssa/heapstack-2.c	(working copy)
@@ -0,0 +1,12 @@ 
+/* { dg-do compile } */
+/* { dg-options "-O2 -fdump-tree-optimized" } */
+
+void f(void*);
+void g(){
+  void*p=__builtin_malloc(12);
+  f(p);
+  __builtin_free(p);
+}
+
+/* { dg-final { scan-tree-dump-times "malloc" 1 "optimized" } } */
+/* { dg-final { cleanup-tree-dump "optimized" } } */

Property changes on: testsuite/gcc.dg/tree-ssa/heapstack-2.c
___________________________________________________________________
Added: svn:keywords
## -0,0 +1 ##
+Author Date Id Revision URL
\ No newline at end of property
Added: svn:eol-style
## -0,0 +1 ##
+native
\ No newline at end of property
Index: testsuite/gcc.dg/tree-ssa/pr19831-3.c
===================================================================
--- testsuite/gcc.dg/tree-ssa/pr19831-3.c	(revision 204620)
+++ testsuite/gcc.dg/tree-ssa/pr19831-3.c	(working copy)
@@ -1,31 +1,31 @@ 
 /* { dg-do compile } */
 /* { dg-options "-O2 -fdump-tree-optimized" } */
 
-void test2(void)
+void test2(int n)
 {
-  int *p = __builtin_malloc (sizeof (int) * 4);
+  int *p = __builtin_malloc (sizeof (int) * n);
   if (p == (void *)0)
     __builtin_abort ();
   __builtin_free (p);
 }
 
-void test5(int b)
+void test5(int n)
 {
-  int *p = __builtin_malloc (sizeof (int) * 4);
+  int *p = __builtin_malloc (sizeof (int) * n);
   if (p)
     __builtin_free (p);
 }
 
-void test6(void)
+void test6(int n)
 {
-  int *p = __builtin_malloc (sizeof (int) * 4);
+  int *p = __builtin_malloc (sizeof (int) * n);
   if (p == (void *)0)
     __builtin_abort ();
   if (p)
     __builtin_free (p);
 }
 
 /* We should be able to remove all malloc/free pairs with CDDCE.
    Assume p was non-NULL for test2.
    For test5, it doesn't matter if p is NULL or non-NULL.  */
 
Index: tree-ssa-forwprop.c
===================================================================
--- tree-ssa-forwprop.c	(revision 204620)
+++ tree-ssa-forwprop.c	(working copy)
@@ -33,20 +33,21 @@  along with GCC; see the file COPYING3.
 #include "tree-ssanames.h"
 #include "tree-dfa.h"
 #include "tree-pass.h"
 #include "langhooks.h"
 #include "flags.h"
 #include "expr.h"
 #include "cfgloop.h"
 #include "optabs.h"
 #include "tree-ssa-propagate.h"
 #include "tree-ssa-dom.h"
+#include "params.h"
 
 /* This pass propagates the RHS of assignment statements into use
    sites of the LHS of the assignment.  It's basically a specialized
    form of tree combination.   It is hoped all of this can disappear
    when we have a generalized tree combiner.
 
    One class of common cases we handle is forward propagating a single use
    variable into a COND_EXPR.
 
      bb0:
@@ -1478,20 +1479,145 @@  constant_pointer_difference (tree p1, tr
     }
 
   for (i = 0; i < cnt[0]; i++)
     for (j = 0; j < cnt[1]; j++)
       if (exps[0][i] == exps[1][j])
 	return size_binop (MINUS_EXPR, offs[0][i], offs[1][j]);
 
   return NULL_TREE;
 }
 
+/* We want to be sure that free (VAR) can't be called in another function, and
+   the easiest way to ensure that is to prove that it is called in this
+   function.  The hardest part is avoiding some call to a function that may not
+   return because of exit, an infinite loop, setjmp, etc, where it might call
+   free on VAR.  */
+static bool
+malloc_safe_on_stack (gimple stmt, vec<gimple, va_heap> *list_of_frees)
+{
+  tree var = gimple_call_lhs (stmt);
+  basic_block bb = gimple_bb (stmt);
+  stack_vec<basic_block, 20> bb_to_visit;
+  bitmap bb_visited = BITMAP_ALLOC (NULL);
+  bitmap_set_bit (bb_visited, bb->index);
+  gimple_stmt_iterator gsi = gsi_for_stmt (stmt);
+  enum tree_code code;
+
+next_stmt:
+  gsi_next_nondebug (&gsi);
+
+handle_stmt:
+  if (gsi_end_p (gsi))
+    {
+      edge e;
+      edge_iterator ei;
+      FOR_EACH_EDGE (e, ei, bb->succs)
+	bb_to_visit.safe_push (e->dest);
+      goto next_bb;
+    }
+  stmt = gsi_stmt (gsi);
+  if (stmt_can_throw_external (stmt))
+    /* We could give up only if VAR has escaped (same for return), but that
+       means there is a memory leak, so don't bother.  */
+    goto unsafe;
+
+  switch (gimple_code (stmt))
+  // TODO: GIMPLE_ASM, EH related gimples?
+    {
+	/* We leave the function without calling free.  */
+      case GIMPLE_RETURN:
+	goto unsafe;
+
+      case GIMPLE_COND:
+	code = gimple_cond_code (stmt);
+	/* If we replace malloc by an array on the stack, it can't be NULL.  */
+	if ((code == EQ_EXPR || code == NE_EXPR)
+	    && var == gimple_cond_lhs (stmt)
+	    && integer_zerop (gimple_cond_rhs (stmt)))
+	  {
+	    edge e;
+	    edge_iterator ei;
+	    FOR_EACH_EDGE (e, ei, bb->succs)
+	      if (e->flags
+		  & ((code == NE_EXPR) ? EDGE_TRUE_VALUE : EDGE_FALSE_VALUE))
+		bb_to_visit.safe_push (e->dest);
+	    goto next_bb;
+	  }
+	/* Fallthrough.  */
+
+	/* Last stmt of the bb, handled by looking at the outgoing edges.  */
+      case GIMPLE_GOTO:
+      case GIMPLE_SWITCH:
+	/* Statements that are irrelevant.  */
+      case GIMPLE_ASSIGN:
+      case GIMPLE_LABEL:
+      case GIMPLE_NOP:
+	goto next_stmt;
+
+      case GIMPLE_CALL:
+	{
+	  tree callee = gimple_call_fndecl (stmt);
+	  if (callee != NULL_TREE
+	      && DECL_BUILT_IN_CLASS (callee) == BUILT_IN_NORMAL)
+	    switch (DECL_FUNCTION_CODE (callee))
+	      {
+		case BUILT_IN_FREE:
+		  if (gimple_call_arg (stmt, 0) != var)
+		    goto next_stmt;
+		  list_of_frees->safe_push (stmt);
+		  /* Fallthrough.  */
+
+		case BUILT_IN_ABORT:
+		case BUILT_IN_EXIT:
+		case BUILT_IN__EXIT:
+		case BUILT_IN__EXIT2:
+		case BUILT_IN_TRAP:
+		case BUILT_IN_UNREACHABLE:
+		  /* Nothing could throw an exception earlier in the block,
+		     so we don't need to check the EH edges.  */
+		  goto next_bb;
+		default:;
+	      }
+
+#if 0
+	  // Fortran testcase
+	  goto next_stmt;
+#endif
+	  int flags = gimple_call_flags (stmt);
+	  // FIXME: leaf is actually not safe, we need some new ECF_* flags.
+	  // ??? In fortran any call is safe?
+	  if (flags & (ECF_CONST|ECF_PURE|ECF_LEAF|ECF_NOVOPS))
+	    goto next_stmt;
+	  goto unsafe;
+	}
+      default:
+	goto unsafe;
+    }
+
+next_bb:
+  if (bb_to_visit.is_empty ())
+    goto safe;
+  bb = bb_to_visit.last ();
+  bb_to_visit.pop ();
+  if (!bitmap_set_bit (bb_visited, bb->index))
+    goto next_bb;
+  gsi = gsi_start_bb (bb);
+  goto handle_stmt;
+
+unsafe:
+  BITMAP_FREE (bb_visited);
+  return false;
+safe:
+  BITMAP_FREE (bb_visited);
+  return true;
+}
+
 /* *GSI_P is a GIMPLE_CALL to a builtin function.
    Optimize
    memcpy (p, "abcd", 4);
    memset (p + 4, ' ', 3);
    into
    memcpy (p, "abcd   ", 7);
    call if the latter can be stored by pieces during expansion.  */
 
 static bool
 simplify_builtin_call (gimple_stmt_iterator *gsi_p, tree callee2)
@@ -1681,20 +1807,64 @@  simplify_builtin_call (gimple_stmt_itera
 	      gimple_call_set_arg (stmt2, 2,
 				   build_int_cst (TREE_TYPE (len2), src_len));
 	      unlink_stmt_vdef (stmt1);
 	      gsi_remove (&gsi, true);
 	      release_defs (stmt1);
 	      update_stmt (stmt2);
 	      return false;
 	    }
 	}
       break;
+
+    case BUILT_IN_FREE:
+      {
+	tree size;
+	tree ptr = gimple_call_arg (stmt2, 0);
+	if (TREE_CODE (ptr) != SSA_NAME)
+	  return false;
+	stmt1 = SSA_NAME_DEF_STMT (ptr);
+	/* TODO: handle calloc.  */
+	if (gimple_call_builtin_p (stmt1, BUILT_IN_MALLOC)
+	    && host_integerp ((size = gimple_call_arg (stmt1, 0)), 1)
+	    /* param_value(...) / 10? Some new parameter?  */
+	    && TREE_INT_CST_LOW (size)
+	       <= (unsigned HOST_WIDE_INT)PARAM_VALUE (PARAM_LARGE_STACK_FRAME))
+	  {
+	    gcc_checking_assert (gimple_call_lhs (stmt1) == ptr);
+	    stack_vec<gimple, 20> list_of_frees;
+	    if (!malloc_safe_on_stack (stmt1, &list_of_frees))
+	      return false;
+	    /* Declare array.  */
+	    tree elem_type = build_nonstandard_integer_type (BITS_PER_UNIT, 1);
+	    tree array_type = build_array_type_nelts (elem_type,
+						      TREE_INT_CST_LOW (size));
+	    tree var = create_tmp_var (array_type, NULL);
+	    tree p = fold_convert (TREE_TYPE (ptr), build_fold_addr_expr (var));
+	    /* Replace free with a clobber.  */
+	    int i;
+	    gimple free_stmt;
+	    FOR_EACH_VEC_ELT (list_of_frees, i, free_stmt)
+	      {
+		tree clobber = build_constructor (array_type, NULL);
+		TREE_THIS_VOLATILE (clobber) = 1;
+		gimple clobber_stmt = gimple_build_assign (var, clobber);
+		gimple_stmt_iterator gsi_free = gsi_for_stmt (free_stmt);
+		gsi_replace (&gsi_free, clobber_stmt, false);
+	      }
+	    /* Replace malloc with the address of the variable.  */
+	    gimple_stmt_iterator gsi1 = gsi_for_stmt (stmt1);
+	    update_call_from_tree (&gsi1, p);
+	    update_stmt (gsi_stmt (gsi1));
+	    return true;
+	  }
+
+      }
     default:
       break;
     }
   return false;
 }
 
 /* Checks if expression has type of one-bit precision, or is a known
    truth-valued expression.  */
 static bool
 truth_valued_ssa_name (tree name)