[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

Richard Guenther <rguenth at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |ASSIGNED
         AssignedTo|unassigned at gcc dot       |rguenth at gcc dot gnu.org
                   |gnu.org                     |

--- Comment #7 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-07 14:11:29 UTC ---
I'll give it another try somewhen.  Don't mark the free as necessary, nor
its operand.  If a malloc ends up not being marked as necessary
and all uses of the lhs are free calls remove the pairs, otherwise do nothing
in eliminate_unnecessary_stmts.

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #8 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-07 15:04:17 UTC ---
Hm, and for invalid code like

int main()
{
  int *p = __builtin_malloc (sizeof (int) * 4);
  *p++ = 4;
  *p++ = 8;
  __builtin_free (p);
  return 0;
}

we shouldn't ICE either ... but here the idea wouldn't work (malloc is
not marked necessary but free doesn't match up with it either).

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #9 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-08 09:21:47 UTC ---
Author: rguenth
Date: Thu Sep  8 09:21:39 2011
New Revision: 178683

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=178683
Log:
2011-09-08  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/19831
    * tree-ssa-dce.c (mark_stmt_if_obviously_necessary): Do not mark
    allocation functions as necessary.

    * gcc.dg/tree-ssa/ssa-dce-8.c: New testcase.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-8.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-dce.c

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #10 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-08 13:00:32 UTC ---
Author: rguenth
Date: Thu Sep  8 13:00:23 2011
New Revision: 178687

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=178687
Log:
2011-09-08  Richard Guenther  <rguenther@suse.de>

    PR tree-optimization/19831
    * tree-ssa-dce.c (mark_all_reaching_defs_necessary_1): Also
    skip builtins with vdefs that do not really store something.
    (propagate_necessity): For calls to free that we can associate
    with an allocation function do not mark the freed pointer
    definition necessary.
    (eliminate_unnecessary_stmts): Remove a call to free if
    the associated call to an allocation function is not necessary.

    * gcc.dg/tree-ssa/pr19831-1.c: New testcase.
    * gcc.dg/tree-ssa/pr19831-2.c: Likewise.
    * gcc.dg/tree-ssa/pr19831-3.c: Likewise.
    * gcc.dg/errno-1.c: Adjust.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr19831-1.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr19831-2.c
    trunk/gcc/testsuite/gcc.dg/tree-ssa/pr19831-3.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/errno-1.c
    trunk/gcc/tree-ssa-dce.c

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #11 from Richard Guenther <rguenth at gcc dot gnu.org> 2011-09-08 13:05:26 UTC ---
More cases handled now.  What we still miss is conditional free, see
gcc.dg/tree-ssa/pr19831-3.c for XFAILed testcases.

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[xiaoyuanbo at yeah dot net]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

xiaoyuanbo <xiaoyuanbo at yeah dot net> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xiaoyuanbo at yeah dot net

--- Comment #12 from xiaoyuanbo <xiaoyuanbo at yeah dot net> 2012-02-22 12:41:56 UTC ---
but you need some

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[pinskia at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

Andrew Pinski <pinskia at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |xinliangli at gmail dot com

--- Comment #13 from Andrew Pinski <pinskia at gcc dot gnu.org> 2012-04-23 06:51:34 UTC ---
*** Bug 53082 has been marked as a duplicate of this bug. ***

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

Marc Glisse <glisse at gcc dot gnu.org> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |glisse at gcc dot gnu.org

--- Comment #14 from Marc Glisse <glisse at gcc dot gnu.org> ---
Discussing PR 53082 here since it was closed as a dup. It asks for 2 things:

1) Replacing a=malloc(n);b=malloc(m); ... free(a);free(b); with a single
malloc-free pair: a=malloc(n+m);b=a+n; ... free(a);.

2) Replacing some malloc calls with alloca.

I am wondering about the circumstances where those things are safe to do. The
second one can only be safe if the size is a constant or VRP tells us it is at
most a small constant. And then for both, nothing too weird must happen in
between, but I am not sure what bad things are possible exactly. The "easy"
case would be with the 2 malloc calls consecutive (what can't we put in
between?), the 2 free calls consecutive, everything in a single basic block
(this sounds way too restrictive), the argument of free an SSA_NAME defined
with the malloc call, nothing that may throw (or any other way we can avoid
coming back to execute free) in "...". Then I have a hard time finding bad
cases (except that on error, malloc returns 0, and we put 0+n in b, maybe it
requires a -fmalloc-cannot-fail). Are there other places in the compiler with a
similar set of checks?

And then we would also need to extend everything to new/delete :-(
(unless maybe we install an LTO version of libstdc++ and, with -fwhole-program
(taken as a promise not to LD_PRELOAD another new/delete), gcc accepts to
inline new/delete and sees malloc and free, but that seems a long shot...)

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #15 from Marc Glisse <glisse at gcc dot gnu.org> ---
See the discussion that starts at:
http://lists.cs.uiuc.edu/pipermail/llvm-commits/Week-of-Mon-20130923/188747.html

(it continues in the following weeks) for optimization 2 of comment #14 in
clang. The key idea is that if, in the function where malloc is called, we can
check that on all paths (including EH) to the exit of the function free is
called on the return value of malloc, then we can replace malloc and all the
corresponding free with a stack allocation (whether we want to, depending on
the size, is a different issue). Of course there are some details like: if we
test whether malloc returned 0, that's one branch where we don't need free,
etc.

Also, the optimization can make a crash happen much earlier:
p=malloc(n);fun(p);free(p);
where fun calls free, would normally fail in the second free (double-free) and
will instead fail in fun (free of a pointer to the stack). I think that's fine,
but people may be surprised if there are a lot of side-effects (I/O for
instance) between the 2 free.

The hardest part here is deciding whether we always reach a free (this is how
we prove that there is no hidden call to realloc/free). There could be an
infinite loop in between. Any function we call might itself have an infinite
loop or call exit. And worst of all, there might be a call to longjmp. That
seems to make it impossible to perform the optimization when there is a
function call, in all but the most contrived cases (a call to setjmp between
malloc and the function call, or in C++ if the EH landing pad for the call
contains a non-inlined call to a non-trivial destructor).

So to make this possible, the first thing to do seems to forbid longjmp:
-fno-longjmp.

But even then it is still hard to know if regular functions always return
(infinite loops, exit). There are *LOOPING_CONST_OR_PURE* flags in gcc (and a
hardcoded list of builtins in call_may_noreturn_p), we could generalize them to
a may_not_return / always_returns flag (and associated attribute), that gcc
could recursively infer on many functions (a similar no_longjmp flag could also
be added to avoid the need for -fno-longjmp). I think this is the most
promising direction.

Assuming that we never do the things that would break the optimization (call
realloc or free in a function that won't return) seems too complicated to
explain properly, so I wouldn't even propose a -fI-promise-it-is-ok.

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #16 from Marc Glisse <glisse at gcc dot gnu.org> ---
Some more transformations for the list:

p = malloc (n);
memcpy (p, q, m);
free (q);

==>

p = realloc (q, n);

it isn't equivalent, in particular it could be slower if m is much smaller than
what q points to, but I think it should generally be safe and profitable. Doing
it without the memcpy is more questionable.

---

And in case we could actually see where q was coming from above:

q = malloc (n);
...
p = realloc (q, n); // --> just p = q;

Maybe I shouldn't list more without implementing at least one first...

---

A detail I had forgotten for the heap to stack (malloc+free -> alloca)
transformation is that the stack deallocation (which we clearly want,
especially if the allocation is in a loop) can't be inserted exactly where free
was. Otherwise, for:

p = malloc (m);
q = malloc (n);
free (p);
free (q); // deallocation not in reverse order!

bad things could happen. Besides, there could already be VLAs in the function,
and even without doing stack deallocation on free there are already strange
interactions if we call alloca from inside the scope of a VLA.

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #17 from Marc Glisse <glisse at gcc dot gnu.org> ---
void f (double * __restrict a) {
  int * __restrict p = (int*) __builtin_malloc (sizeof (int));
  *p = 42;
  __builtin_free (p);
  ++*a; // Breaks the optimization!
}

Normally, gcc now manages to remove unused malloc+write+free sequences.
However, it seems that completely unrelated operations, even after free, can
prevent this optimization (it is the detection that *p=42 is dead that fails).
That limits the effect in real-world code...

(funny that if I remove the line with free(p), gcc does manage to optimize)

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenther at suse dot de]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #18 from rguenther at suse dot de <rguenther at suse dot de> ---
On Fri, 25 Oct 2013, glisse at gcc dot gnu.org wrote:

> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831
> 
> --- Comment #17 from Marc Glisse <glisse at gcc dot gnu.org> ---
> void f (double * __restrict a) {
>   int * __restrict p = (int*) __builtin_malloc (sizeof (int));
>   *p = 42;
>   __builtin_free (p);
>   ++*a; // Breaks the optimization!
> }
> 
> Normally, gcc now manages to remove unused malloc+write+free sequences.
> However, it seems that completely unrelated operations, even after free, can
> prevent this optimization (it is the detection that *p=42 is dead that fails).
> That limits the effect in real-world code...
> 
> (funny that if I remove the line with free(p), gcc does manage to optimize)

That's just DCE doing more than it is designed to do in some very
rare corner cases.

Look why DSE doesn't do its job instead.

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[glisse at gcc dot gnu.org]

http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #19 from Marc Glisse <glisse at gcc dot gnu.org> ---
Author: glisse
Date: Tue Oct 29 13:19:08 2013
New Revision: 204160

URL: http://gcc.gnu.org/viewcvs?rev=204160&root=gcc&view=rev
Log:
2013-10-29  Marc Glisse  <marc.glisse@inria.fr>

    PR tree-optimization/19831
gcc/
    * tree-ssa-alias.c (stmt_kills_ref_p_1): Handle BUILT_IN_FREE.

gcc/testsuite/
    * gcc.dg/tree-ssa/alias-25.c: New file.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/alias-25.c   (with props)
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/tree-ssa-alias.c

Propchange: trunk/gcc/testsuite/gcc.dg/tree-ssa/alias-25.c
            ('svn:eol-style' added)

Propchange: trunk/gcc/testsuite/gcc.dg/tree-ssa/alias-25.c
            ('svn:keywords' added)

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu.org]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #20 from Richard Biener <rguenth at gcc dot gnu.org> ---
The original cases are all fixed but what remains is us failing to elide

void f ()
{
  void *p = __builtin_malloc (1);
  if (!p)
    __builtin_abort ();
  __builtin_free (p);
}

if that's even desirable.  Note that we mark the abort() call as necessary
since it has side-effects which is contrary to this expectation.  If you
think of, say,

extern int alloc_fails;
extern int alloc_success;
void f ()
{
  void *p = __builtin_malloc (1);
  if (!p)
    alloc_fails++;
  else
    alloc_success++;
  __builtin_free (p);
}

then the question is really whether we may assume that malloc does not
return NULL.  We can then avoid marking 'p' necessary on NULL checks
on malloc returned pointers and upon DCEing the malloc/free pair
replace the def of 'p' with a non-zero constant.

Related would be to play similar things with realloc - replace

 void *p = realloc (q, n);
 free (p);

with

 free (q);

and

  void *p = realloc (q, n);
  if (p == q)
    not_copied++;
 free (p);

with

  void *p = q;
  if (p == q)
    not_copied++;
  free(q);

so here we'd not only have to deal with != NULL but other pointer equality
checks.

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[koss.dallas at crm dot leadkahuna.com]

https://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

--- Comment #21 from koss.dallas at crm dot leadkahuna.com ---
Hello! 

You can examine a list of the required documents here in one file: 

xpawel.com/miss-edythe-mccullough/gcc-bugzilla-12.zip



-----Original Message-----
On Thursday, 25 March 2021, 15:07, <gcc-bugzilla@gcc.gnu.org> wrote:
> Hello! 
> 
> You can examine a list of the required documents here in one file: 
> 
> xpawel.com/miss-edythe-mccullough/gcc-bugzilla-12.zip

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu dot org]

------- Comment #6 from rguenth at gcc dot gnu dot org  2009-07-01 12:28 -------
I am not working on the other piece.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org
         AssignedTo|rguenth at gcc dot gnu dot  |unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu dot org]

------- Comment #5 from rguenth at gcc dot gnu dot org  2009-07-01 12:27 -------
Subject: Bug 19831

Author: rguenth
Date: Wed Jul  1 12:27:33 2009
New Revision: 149140

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=149140
Log:
2009-07-01  Richard Guenther  <rguenther@suse.de>

        PR tree-optimization/19831
        * tree-ssa-dce.c (propagate_necessity): Calls to functions
        that only act as barriers do not make any previous stores
        necessary.
        * tree-ssa-structalias.c (handle_lhs_call): Delay making
        HEAP variables global, do not add a constraint from nonlocal.
        (find_func_aliases): Handle escapes through return statements.
        (compute_points_to_sets): Make escaped HEAP variables global.

        * gcc.dg/tree-ssa/20041122-1.c: Enable TBAA, scan FRE dump,
        make allocated memory escape.  Un-XFAIL.
        * gcc.dg/vect/pr21591.c: Make allocated memory escape.
        * gcc.dg/vect/pr31699.c: Likewise.
        * gcc.dg/tree-ssa/ssa-dce-7.c: New testcase.

        libmudflap/
        * testsuite/libmudflap.c/fail11-frag.c: Make allocated memory
        escape.
        * testsuite/libmudflap.c/fail12-frag.c: Likewise.
        * testsuite/libmudflap.c/fail16-frag.c: Likewise.
        * testsuite/libmudflap.c/fail31-frag.c: Likewise.

Added:
    trunk/gcc/testsuite/gcc.dg/tree-ssa/ssa-dce-7.c
Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/testsuite/ChangeLog
    trunk/gcc/testsuite/gcc.dg/tree-ssa/20041122-1.c
    trunk/gcc/testsuite/gcc.dg/vect/pr21591.c
    trunk/gcc/testsuite/gcc.dg/vect/pr31699.c
    trunk/gcc/tree-ssa-dce.c
    trunk/gcc/tree-ssa-structalias.c
    trunk/libmudflap/ChangeLog
    trunk/libmudflap/testsuite/libmudflap.c/fail11-frag.c
    trunk/libmudflap/testsuite/libmudflap.c/fail12-frag.c
    trunk/libmudflap/testsuite/libmudflap.c/fail16-frag.c
    trunk/libmudflap/testsuite/libmudflap.c/fail31-frag.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2009-06-26 15:39 -------
And we want to optimize

void *malloc(__SIZE_TYPE__);
void free(void*);
void abort(void);
int f(void)
{
  char *i = malloc(1);
  if (i == (void *)0)
    abort ();
  *i = 1;
  free (i);
}

the same (removing the check and the abort() call).

Which asks for doing the task all at once.  Somewhere.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2009-06-26 15:23 -------
Hm, it's not _that_ simple.  A fab hack is easier I guess.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[rguenth at gcc dot gnu dot org]

------- Comment #2 from rguenth at gcc dot gnu dot org  2009-06-26 15:12 -------
I have a patch for the DSE part.

The malloc part shouldn't be too difficult.

The free part is more interesting.  Basically the pointer use in free (p)
should mark the malloc necessary but really nothing is there to mark the
free necessary if it is (the free is necessary iff the malloc is necessary but
nothing provides this link to provide easy integration with the DCE worklist
implementation).

Maybe a two-stage implementation would work where we replace an unnecessary
malloc () with a NULL assignment (so the free becomes a no-op and is
eventually folded away after CCP).  A little bit hackish - and dependent
on free (NULL) (if it happens to persist) to not fault.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |rguenth at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-07-01 00:25:55         |2009-06-26 15:12:33
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[pinskia at gcc dot gnu dot org]

-- 
           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|                            |1
   Last reconfirmed|0000-00-00 00:00:00         |2005-02-09 06:51:15
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831

[Bug tree-optimization/19831] Missing DSE/malloc/free optimization

[dberlin at dberlin dot org]

------- Additional Comments From dberlin at gcc dot gnu dot org  2005-02-09 03:42 -------
Subject: Re:  New: Missing DSE/malloc/free
	optimization

> void *malloc(__SIZE_TYPE__);
> void free(void*);
> int f(void)
> {
>   char *i = malloc(1);
>   *i = 1;
>   free (i);
> }
> 
> This is something which is useful when we want to much higer level optimizations.

This would require an attribute free, which is on the tree-profiling
branch

Otherwise, you wouldn't know that free is really "free"



-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=19831