[RFC] Marking C++ new operator as malloc?

[RFC] Marking C++ new operator as malloc?

[Martin Jambor]

Hi,

when trying  to analyse dynamically  allocated objects in C++,  I came
across the need to identify results  of the new operator (at least the
non-overridden  standard  one)   as  malloc-allocated.   The  cleanest
approach would probably be to  mark the new operator function with the
malloc attribute.   So I did  that (see the extra-short  patch below),
bootstrapped c  and c++ on  i686-linux (with "all,fold"  checking) and
ran the test suite. To my surprise, there were no new regressions.

I  am  now  wondering  why  the  function  is  not  marked  as  malloc
already. In fact, its implementation  always returns what it gets from
the built-in malloc. Are there  any known issues or concerns with this
that the test suite cannot reveal? Can anyone comment on this?

Moreover, just before sending this  email, I have found out that there
is  already PR23383  (builtin array  operator new  is not  marked with
malloc attribute) about  the array variant of the  new operator. Given
its implementation, it is probably the same thing...

Thank you very much in advance,

Martin



Index: libstdc++-v3/libsupc++/new
===================================================================
--- libstdc++-v3/libsupc++/new	(revision 128207)
+++ libstdc++-v3/libsupc++/new	(working copy)
@@ -92,7 +92,8 @@
  *  Placement new and delete signatures (take a memory address argument,
  *  does nothing) may not be replaced by a user's program.
 */
-void* operator new(std::size_t) throw (std::bad_alloc);
+void* operator new(std::size_t) throw (std::bad_alloc) 
+    __attribute__ ((malloc));
 void* operator new[](std::size_t) throw (std::bad_alloc);
 void operator delete(void*) throw();
 void operator delete[](void*) throw();

Re: [RFC] Marking C++ new operator as malloc?

[Kaveh R. GHAZI]

On Fri, 7 Sep 2007, Martin Jambor wrote:

> Index: libstdc++-v3/libsupc++/new
> ===================================================================
> --- libstdc++-v3/libsupc++/new	(revision 128207)
> +++ libstdc++-v3/libsupc++/new	(working copy)
> @@ -92,7 +92,8 @@
>   *  Placement new and delete signatures (take a memory address argument,
>   *  does nothing) may not be replaced by a user's program.
>  */
> -void* operator new(std::size_t) throw (std::bad_alloc);
> +void* operator new(std::size_t) throw (std::bad_alloc)
> +    __attribute__ ((malloc));
>  void* operator new[](std::size_t) throw (std::bad_alloc);
>  void operator delete(void*) throw();
>  void operator delete[](void*) throw();

If this is accepted, IMHO you should use __attribute__((__malloc__)) not
__attribute__ ((malloc)).

		Thanks,
		--Kaveh
--
Kaveh R. Ghazi			ghazi@caip.rutgers.edu

Re: [RFC] Marking C++ new operator as malloc?

[Chris Lattner]

On Sep 7, 2007, at 1:53 PM, Martin Jambor wrote:

> Hi,
>
> when trying  to analyse dynamically  allocated objects in C++,  I came
> across the need to identify results  of the new operator (at least the
> non-overridden  standard  one)   as  malloc-allocated.   The  cleanest
> approach would probably be to  mark the new operator function with the
> malloc attribute.   So I did  that (see the extra-short  patch below),
> bootstrapped c  and c++ on  i686-linux (with "all,fold"  checking) and
> ran the test suite. To my surprise, there were no new regressions.
>
> I  am  now  wondering  why  the  function  is  not  marked  as  malloc
> already. In fact, its implementation  always returns what it gets from
> the built-in malloc. Are there  any known issues or concerns with this
> that the test suite cannot reveal? Can anyone comment on this?

It is unclear whether this is safe.  Nothing in the standard AFAIK  
requires the operator new be implemented in terms of malloc, and  
users are allowed to override it.

-Chris

Re: [RFC] Marking C++ new operator as malloc?

[Joe Buck]

On Sep 7, 2007, at 1:53 PM, Martin Jambor wrote:
> [ giving operator new the malloc property ]

On Fri, Sep 07, 2007 at 06:30:33PM -0700, Chris Lattner wrote:
> It is unclear whether this is safe.  Nothing in the standard AFAIK  
> requires the operator new be implemented in terms of malloc, and  
> users are allowed to override it.

The malloc property doesn't mean that operator new is defined in terms
of malloc.  It refers to the aliasing properties of the returned
values; specifically, the compiler can assume that two separate calls
return values that don't alias each other.

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

Joe Buck <Joe.Buck@synopsys.COM> writes:

| On Sep 7, 2007, at 1:53 PM, Martin Jambor wrote:
| > [ giving operator new the malloc property ]
| 
| On Fri, Sep 07, 2007 at 06:30:33PM -0700, Chris Lattner wrote:
| > It is unclear whether this is safe.  Nothing in the standard AFAIK  
| > requires the operator new be implemented in terms of malloc, and  
| > users are allowed to override it.
| 
| The malloc property doesn't mean that operator new is defined in terms
| of malloc.  It refers to the aliasing properties of the returned
| values; specifically, the compiler can assume that two separate calls
| return values that don't alias each other.

I seem to remember we had had this discussion before -- in connection
with optimizations related to 'malloc' attribute -- and decided not to
apply the attribute because it was not clear whether it was permitted
by the standard.  I don't seem to get my hands on reference to the
thread right now.

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[H.J. Lu]

On Sat, Sep 08, 2007 at 12:57:13AM -0500, Gabriel Dos Reis wrote:
> Joe Buck <Joe.Buck@synopsys.COM> writes:
> 
> | On Sep 7, 2007, at 1:53 PM, Martin Jambor wrote:
> | > [ giving operator new the malloc property ]
> | 
> | On Fri, Sep 07, 2007 at 06:30:33PM -0700, Chris Lattner wrote:
> | > It is unclear whether this is safe.  Nothing in the standard AFAIK  
> | > requires the operator new be implemented in terms of malloc, and  
> | > users are allowed to override it.
> | 
> | The malloc property doesn't mean that operator new is defined in terms
> | of malloc.  It refers to the aliasing properties of the returned
> | values; specifically, the compiler can assume that two separate calls
> | return values that don't alias each other.
> 
> I seem to remember we had had this discussion before -- in connection
> with optimizations related to 'malloc' attribute -- and decided not to
> apply the attribute because it was not clear whether it was permitted
> by the standard.  I don't seem to get my hands on reference to the
> thread right now.
> 

There is a related bug:

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


H.J.

Re: [RFC] Marking C++ new operator as malloc?

[Chris Lattner]

I understand, but allowing users to override new means that the actual  
implementation may not honor the aliasing guarantees of attribute  
malloc.

-Chris

http://nondot.org/sabre
http://llvm.org

On Sep 7, 2007, at 10:12 PM, Joe Buck <Joe.Buck@synopsys.COM> wrote:

>
> On Sep 7, 2007, at 1:53 PM, Martin Jambor wrote:
>> [ giving operator new the malloc property ]
>
> On Fri, Sep 07, 2007 at 06:30:33PM -0700, Chris Lattner wrote:
>> It is unclear whether this is safe.  Nothing in the standard AFAIK
>> requires the operator new be implemented in terms of malloc, and
>> users are allowed to override it.
>
> The malloc property doesn't mean that operator new is defined in terms
> of malloc.  It refers to the aliasing properties of the returned
> values; specifically, the compiler can assume that two separate calls
> return values that don't alias each other.

Re: [RFC] Marking C++ new operator as malloc?

[Basile STARYNKEVITCH]

Chris Lattner wrote:
> I understand, but allowing users to override new means that the actual 
> implementation may not honor the aliasing guarantees of attribute malloc.
> 
> -Chris
> 
> On Sep 7, 2007, at 10:12 PM, Joe Buck <Joe.Buck@synopsys.COM> wrote:
> 
>>
>> On Sep 7, 2007, at 1:53 PM, Martin Jambor wrote:
>>> [ giving operator new the malloc property ]
>>
>> On Fri, Sep 07, 2007 at 06:30:33PM -0700, Chris Lattner wrote:
>>> It is unclear whether this is safe.  Nothing in the standard AFAIK
>>> requires the operator new be implemented in terms of malloc, and
>>> users are allowed to override it.

Maybe it could make sense to give the malloc attribute only to 
::operator new but not to other new-s, in particular not to the 
placement new?

But I am not a C++ expert!

Regards.


-- 
Basile STARYNKEVITCH         http://starynkevitch.net/Basile/
email: basile<at>starynkevitch<dot>net mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/8/07, Chris Lattner <clattner@apple.com> wrote:
> I understand, but allowing users to override new means that the actual
> implementation may not honor the aliasing guarantees of attribute
> malloc.

Well, you can argue that all hell breaks lose if you do so.  A sane ::new
is required for almost everything :)

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

"Richard Guenther" <richard.guenther@gmail.com> writes:

| On 9/8/07, Chris Lattner <clattner@apple.com> wrote:
| > I understand, but allowing users to override new means that the actual
| > implementation may not honor the aliasing guarantees of attribute
| > malloc.
| 
| Well, you can argue that all hell breaks lose if you do so.  A sane ::new
| is required for almost everything :)

I suspect the question is how to you distinguish a sane new from an an
insane one.

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Joe Buck]

On Sat, Sep 08, 2007 at 04:33:50PM -0500, Gabriel Dos Reis wrote:
> "Richard Guenther" <richard.guenther@gmail.com> writes:
> 
> | On 9/8/07, Chris Lattner <clattner@apple.com> wrote:
> | > I understand, but allowing users to override new means that the actual
> | > implementation may not honor the aliasing guarantees of attribute
> | > malloc.
> | 
> | Well, you can argue that all hell breaks lose if you do so.  A sane ::new
> | is required for almost everything :)
> 
> I suspect the question is how to you distinguish a sane new from an an
> insane one.

Does it matter?  If an insane new hands multiple callers the same memory
without an intervening delete, whether or not the compiler optimizes on
the assumption that new is sane doesn't matter; the program is still going
to break.

Re: [RFC] Marking C++ new operator as malloc?

[Joe Buck]

On Sat, Sep 08, 2007 at 10:16:41PM +0200, Basile STARYNKEVITCH wrote:
> Maybe it could make sense to give the malloc attribute only to 
> ::operator new but not to other new-s, in particular not to the 
> placement new?

It would be completely wrong to give the attribute to placement new,
as the return value *always* aliases the memory you passed it to
supply the place.

Re: [RFC] Marking C++ new operator as malloc?

[Martin Jambor]

[-- Attachment #1: Type: text/plain, Size: 2650 bytes --]

Hi,

On Sat, Sep 08, 2007 at 10:16:41PM +0200, Basile STARYNKEVITCH wrote:
> Chris Lattner wrote:
>> I understand, but allowing users to override new means that the actual 
>> implementation may not honor the aliasing guarantees of attribute malloc.
>> -Chris
>
> Maybe it could make sense to give the malloc attribute only to ::operator 
> new but not to other new-s, in particular not to the placement new?
>
> But I am not a C++ expert!

Neither am I. However, I have  done a small series of experiments that
showed  this is  exactly what  happens with  the patch  I sent  in the
original mail.

Obviously,  this thread  is not  about placement  new which  I believe
definitely cannot have the flag set.

I compiled four small tests  with both patched and untampered compiler
(revision 128277) and compared dumps. The exact dumps and some further
details are  attached, here  I'll just list  three of the  sources and
briefly summarize the effect of the patch.

1. Allocating a simple int (in fact the same example as in PR23383):

    int f(void)
    {
      int t;
      int *a = new int;
      int *b = new int;
      *a = 1;
      *b = 2;
      t = *a;
      delete a;
      delete b;
      return t;
    }

  The patched compiler turnes return into "return 1" and removes the
  load to t. The unpatched does neither.

2. Allocating a simple class:

    class A 
    {
    public:
      int d;
    };
    
    int f(void)
    {
      int t;
      A *a = new A;
      A *b = new A;
      a->d = 1;
      b->d = 2;
      t = a->d;
      delete a;
      delete b;
      return t;
    }
    
  The same thing. Patched version returns 1, original performs load.

3. Allocating a simple class with a redefined new operator.

    class A 
    {
    public:
      int d;
      static void* operator new (size_t size); 
      static void operator delete (void *p);
    };
    
    static A pool[2];
    static int n = 0;
    
    __attribute__ ((noinline)) void* A::operator new (size_t size)
    {
      // the following should be dangerous enough:
      void *p = &pool[n];
      n++;
      return p; 
    }
    
    __attribute__ ((noinline)) void A::operator delete (void *p)
    {	
      // no-op
    } 
    
    int f(void)
    {
      int t;
      A *a = new A;
      A *b = new A;
      a->d = 1;
      b->d = 2;
      t = a->d;
      delete a;
      delete b;
      return t;
    }
     
  Both patched  and original compiler produced exactly  the same dump,
  the patched version did not perform any (unsafe) transformations.

So my conclusion is that redefined new operators are not an issue and
the attribute does not affect them. 

Martin

[-- Attachment #2: new.txt --]
[-- Type: text/plain, Size: 10520 bytes --]

All dumps below are from *.121t.optimized files.
The only optimization related switch used was -O3.
======================================================================

			      test.int.cpp
                              ------------ 
Source:
-------

#include <new> 

int f(void)
{
  int t;
  int *a = new int;
  int *b = new int;
  *a = 1;
  *b = 2;
  t = *a;
  delete a;
  delete b;
  return t;
}
----------------------------------------------------------------------

Unpatched compiler:
-------------------

int f() ()
{
  intD.2 * bD.1771;
  intD.2 * aD.1770;
  intD.2 tD.1769;
  voidD.35 * D.1773;
  voidD.35 * D.1772;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # SMT.6D.1783_9 = VDEF <SMT.6D.1783_8(D)> { SMT.6D.1783 }
  D.1772 = operator new (4);
  aD.1770 = (intD.2 *) D.1772;
  # SMT.6D.1783_10 = VDEF <SMT.6D.1783_9> { SMT.6D.1783 }
  D.1773 = operator new (4);
  bD.1771 = (intD.2 *) D.1773;
  # SMT.6D.1783_11 = VDEF <SMT.6D.1783_10> { SMT.6D.1783 }
  *aD.1770 = 1;
  # SMT.6D.1783_12 = VDEF <SMT.6D.1783_11> { SMT.6D.1783 }
  *bD.1771 = 2;
  # VUSE <SMT.6D.1783_12> { SMT.6D.1783 }
  tD.1769 = *aD.1770;
  # SMT.6D.1783_13 = VDEF <SMT.6D.1783_12> { SMT.6D.1783 }
  operator delete (aD.1770);
  # SMT.6D.1783_14 = VDEF <SMT.6D.1783_13> { SMT.6D.1783 }
  operator delete (bD.1771);
  return tD.1769;
  # SUCC: EXIT [100.0%] 
}
----------------------------------------------------------------------

Patched compiler:
-----------------

int f() ()
{
  intD.2 * bD.1771;
  intD.2 * aD.1770;
  voidD.35 * D.1773;
  voidD.35 * D.1772;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # HEAP.4D.1781_11 = VDEF <HEAP.4D.1781_8(D)>
  # HEAP.5D.1782_12 = VDEF <HEAP.5D.1782_9(D)>
  # SMT.8D.1785_13 = VDEF <SMT.8D.1785_10(D)> { HEAP.4D.1781 HEAP.5D.1782 SMT.8D
.1785 }
  D.1772 = operator new (4);
  aD.1770 = (intD.2 *) D.1772;
  # HEAP.4D.1781_14 = VDEF <HEAP.4D.1781_11>
  # HEAP.5D.1782_15 = VDEF <HEAP.5D.1782_12>
  # SMT.8D.1785_16 = VDEF <SMT.8D.1785_13> { HEAP.4D.1781 HEAP.5D.1782 SMT.8D.17
85 }
  D.1773 = operator new (4);
  bD.1771 = (intD.2 *) D.1773;
  # HEAP.4D.1781_17 = VDEF <HEAP.4D.1781_14> { HEAP.4D.1781 }
  *aD.1770 = 1;
  # HEAP.5D.1782_18 = VDEF <HEAP.5D.1782_15> { HEAP.5D.1782 }
  *bD.1771 = 2;
  # HEAP.4D.1781_19 = VDEF <HEAP.4D.1781_17>
  # HEAP.5D.1782_20 = VDEF <HEAP.5D.1782_18>
  # SMT.8D.1785_21 = VDEF <SMT.8D.1785_16> { HEAP.4D.1781 HEAP.5D.1782 SMT.8D.17
85 }
  operator delete (aD.1770);
  # HEAP.4D.1781_22 = VDEF <HEAP.4D.1781_19>
  # HEAP.5D.1782_23 = VDEF <HEAP.5D.1782_20>
  # SMT.8D.1785_24 = VDEF <SMT.8D.1785_21> { HEAP.4D.1781 HEAP.5D.1782 SMT.8D.17
85 }
  operator delete (bD.1771);
  return 1;
  # SUCC: EXIT [100.0%] 
}
======================================================================

                         test_class_stdnew.cpp
                         ---------------------

Source:
-------

#include <new> 

class A 
{
public:
  int d;
};

int f(void)
{
  int t;
  A *a = new A;
  A *b = new A;
  a->d = 1;
  b->d = 2;
  t = a->d;
  delete a;
  delete b;
  return t;
}
----------------------------------------------------------------------

Unpatched compiler:
-------------------

int f() ()
{
  struct AD.1767 * bD.1774;
  struct AD.1767 * aD.1773;
  intD.2 tD.1772;
  voidD.35 * D.1776;
  voidD.35 * D.1775;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # SMT.6D.1786_9 = VDEF <SMT.6D.1786_8(D)> { SMT.6D.1786 }
  D.1775 = operator new (4);
  aD.1773 = (struct AD.1767 *) D.1775;
  # SMT.6D.1786_10 = VDEF <SMT.6D.1786_9> { SMT.6D.1786 }
  D.1776 = operator new (4);
  bD.1774 = (struct AD.1767 *) D.1776;
  # SMT.6D.1786_11 = VDEF <SMT.6D.1786_10> { SMT.6D.1786 }
  aD.1773->dD.1769 = 1;
  # SMT.6D.1786_12 = VDEF <SMT.6D.1786_11> { SMT.6D.1786 }
  bD.1774->dD.1769 = 2;
  # VUSE <SMT.6D.1786_12> { SMT.6D.1786 }
  tD.1772 = aD.1773->dD.1769;
  # SMT.6D.1786_13 = VDEF <SMT.6D.1786_12> { SMT.6D.1786 }
  operator delete (aD.1773);
  # SMT.6D.1786_14 = VDEF <SMT.6D.1786_13> { SMT.6D.1786 }
  operator delete (bD.1774);
  return tD.1772;
  # SUCC: EXIT [100.0%] 
}
----------------------------------------------------------------------

Patched compiler:
-----------------

int f() ()
{
  struct AD.1767 * bD.1774;
  struct AD.1767 * aD.1773;
  voidD.35 * D.1776;
  voidD.35 * D.1775;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # HEAP.4D.1784_11 = VDEF <HEAP.4D.1784_8(D)>
  # HEAP.5D.1785_12 = VDEF <HEAP.5D.1785_9(D)>
  # SMT.8D.1788_13 = VDEF <SMT.8D.1788_10(D)> { HEAP.4D.1784 HEAP.5D.1785 SMT.8D
.1788 }
  D.1775 = operator new (4);
  aD.1773 = (struct AD.1767 *) D.1775;
  # HEAP.4D.1784_14 = VDEF <HEAP.4D.1784_11>
  # HEAP.5D.1785_15 = VDEF <HEAP.5D.1785_12>
  # SMT.8D.1788_16 = VDEF <SMT.8D.1788_13> { HEAP.4D.1784 HEAP.5D.1785 SMT.8D.17
88 }
  D.1776 = operator new (4);
  bD.1774 = (struct AD.1767 *) D.1776;
  # HEAP.4D.1784_17 = VDEF <HEAP.4D.1784_14> { HEAP.4D.1784 }
  aD.1773->dD.1769 = 1;
  # HEAP.5D.1785_18 = VDEF <HEAP.5D.1785_15> { HEAP.5D.1785 }
  bD.1774->dD.1769 = 2;
  # HEAP.4D.1784_19 = VDEF <HEAP.4D.1784_17>
  # HEAP.5D.1785_20 = VDEF <HEAP.5D.1785_18>
  # SMT.8D.1788_21 = VDEF <SMT.8D.1788_16> { HEAP.4D.1784 HEAP.5D.1785 SMT.8D.17
88 }
  operator delete (aD.1773);
  # HEAP.4D.1784_22 = VDEF <HEAP.4D.1784_19>
  # HEAP.5D.1785_23 = VDEF <HEAP.5D.1785_20>
  # SMT.8D.1788_24 = VDEF <SMT.8D.1788_21> { HEAP.4D.1784 HEAP.5D.1785 SMT.8D.17
88 }
  operator delete (bD.1774);
  return 1;
  # SUCC: EXIT [100.0%] 
}
======================================================================

                         test_class_rednew.cpp
			 ---------------------

Note: Inlining had to be switchde off, otherwise it and SRA did too
      good a job.

Source:
-------

#include <new> 

class A 
{
public:
  int d;
  static void* operator new (size_t size); 
  static void operator delete (void *p);
};

static A pool[2];
static int n = 0;

__attribute__ ((noinline)) void* A::operator new (size_t size)
{
  // the following should be dangerous enough:
  void *p = &pool[n];
  n++;
  return p; 
}

__attribute__ ((noinline)) void A::operator delete (void *p)
{	
  // no-op
} 

int f(void)
{
  int t;
  A *a = new A;
  A *b = new A;
  a->d = 1;
  b->d = 2;
  t = a->d;
  delete a;
  delete b;
  return t;
}
----------------------------------------------------------------------

Unpatched compiler:
-------------------

int f() ()
{
  struct AD.1767 * aD.1789;
  voidD.35 * D.1792;
  voidD.35 * D.1791;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # SMT.30D.1825_9 = VDEF <SMT.30D.1825_8(D)> { SMT.30D.1825 }
  D.1791 = operator new (4);
  aD.1789 = (struct AD.1767 *) D.1791;
  # SMT.30D.1825_10 = VDEF <SMT.30D.1825_9> { SMT.30D.1825 }
  D.1792 = operator new (4);
  # SMT.30D.1825_11 = VDEF <SMT.30D.1825_10> { SMT.30D.1825 }
  aD.1789->dD.1769 = 1;
  # SMT.30D.1825_12 = VDEF <SMT.30D.1825_11> { SMT.30D.1825 }
  ((struct AD.1767 *) D.1792)->dD.1769 = 2;
  return aD.1789->dD.1769;
  # SUCC: EXIT [100.0%] 
}
----------------------------------------------------------------------

Patched compiler:    (NO CHANGE)
-----------------

int f() ()
{
  struct AD.1767 * aD.1789;
  voidD.35 * D.1792;
  voidD.35 * D.1791;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # SMT.30D.1825_9 = VDEF <SMT.30D.1825_8(D)> { SMT.30D.1825 }
  D.1791 = operator new (4);
  aD.1789 = (struct AD.1767 *) D.1791;
  # SMT.30D.1825_10 = VDEF <SMT.30D.1825_9> { SMT.30D.1825 }
  D.1792 = operator new (4);
  # SMT.30D.1825_11 = VDEF <SMT.30D.1825_10> { SMT.30D.1825 }
  aD.1789->dD.1769 = 1;
  # SMT.30D.1825_12 = VDEF <SMT.30D.1825_11> { SMT.30D.1825 }
  ((struct AD.1767 *) D.1792)->dD.1769 = 2;
  return aD.1789->dD.1769;
  # SUCC: EXIT [100.0%] 
}
======================================================================

                         test_class_rednew2.cpp
			 ----------------------


Source:
-------

#include <new> 
#include <stdlib.h>

class A 
{
public:
  int d;
  static void* operator new (size_t size); 
  static void operator delete (void *p);
};

static A pool[2];
static int n = 0;

__attribute__ ((noinline)) void* A::operator new (size_t size)
{
  return malloc (size);
}

__attribute__ ((noinline)) void A::operator delete (void *p)
{	
  free (p);
} 

int f(void)
{
  int t;
  A *a = new A;
  A *b = new A;
  a->d = 1;
  b->d = 2;
  t = a->d;
  delete a;
  delete b;
  return t;
}
----------------------------------------------------------------------

Unpatched compiler:
-------------------

int f() ()
{
  struct AD.2539 * bD.2560;
  struct AD.2539 * aD.2559;
  intD.2 tD.2558;
  voidD.35 * D.2562;
  voidD.35 * D.2561;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # SMT.31D.2598_9 = VDEF <SMT.31D.2598_8(D)> { SMT.31D.2598 }
  D.2561 = operator new (4);
  aD.2559 = (struct AD.2539 *) D.2561;
  # SMT.31D.2598_10 = VDEF <SMT.31D.2598_9> { SMT.31D.2598 }
  D.2562 = operator new (4);
  bD.2560 = (struct AD.2539 *) D.2562;
  # SMT.31D.2598_11 = VDEF <SMT.31D.2598_10> { SMT.31D.2598 }
  aD.2559->dD.2541 = 1;
  # SMT.31D.2598_12 = VDEF <SMT.31D.2598_11> { SMT.31D.2598 }
  bD.2560->dD.2541 = 2;
  # VUSE <SMT.31D.2598_12> { SMT.31D.2598 }
  tD.2558 = aD.2559->dD.2541;
  # SMT.31D.2598_13 = VDEF <SMT.31D.2598_12> { SMT.31D.2598 }
  operator delete (aD.2559);
  # SMT.31D.2598_14 = VDEF <SMT.31D.2598_13> { SMT.31D.2598 }
  operator delete (bD.2560);
  return tD.2558;
  # SUCC: EXIT [100.0%] 
}
----------------------------------------------------------------------

Patched compiler:           (NO CHANGE)
-----------------

int f() ()
{
  struct AD.2539 * bD.2560;
  struct AD.2539 * aD.2559;
  intD.2 tD.2558;
  voidD.35 * D.2562;
  voidD.35 * D.2561;

  # BLOCK 2 freq:10000
  # PRED: ENTRY [100.0%]  (fallthru,exec)
  # SMT.31D.2598_9 = VDEF <SMT.31D.2598_8(D)> { SMT.31D.2598 }
  D.2561 = operator new (4);
  aD.2559 = (struct AD.2539 *) D.2561;
  # SMT.31D.2598_10 = VDEF <SMT.31D.2598_9> { SMT.31D.2598 }
  D.2562 = operator new (4);
  bD.2560 = (struct AD.2539 *) D.2562;
  # SMT.31D.2598_11 = VDEF <SMT.31D.2598_10> { SMT.31D.2598 }
  aD.2559->dD.2541 = 1;
  # SMT.31D.2598_12 = VDEF <SMT.31D.2598_11> { SMT.31D.2598 }
  bD.2560->dD.2541 = 2;
  # VUSE <SMT.31D.2598_12> { SMT.31D.2598 }
  tD.2558 = aD.2559->dD.2541;
  # SMT.31D.2598_13 = VDEF <SMT.31D.2598_12> { SMT.31D.2598 }
  operator delete (aD.2559);
  # SMT.31D.2598_14 = VDEF <SMT.31D.2598_13> { SMT.31D.2598 }
  operator delete (bD.2560);
  return tD.2558;
  # SUCC: EXIT [100.0%] 
}

Re: [RFC] Marking C++ new operator as malloc?

[Martin Jambor]

Hi,

On Fri, Sep 07, 2007 at 06:30:33PM -0700, Chris Lattner wrote:
> On Sep 7, 2007, at 1:53 PM, Martin Jambor wrote:
>> when trying  to analyse dynamically  allocated objects in C++,  I came
>> across the need to identify results  of the new operator (at least the
>> non-overridden  standard  one)   as  malloc-allocated.   The  cleanest
>> approach would probably be to  mark the new operator function with the
>> malloc attribute.   So I did  that (see the extra-short  patch below),
>> bootstrapped c  and c++ on  i686-linux (with "all,fold"  checking) and
>> ran the test suite. To my surprise, there were no new regressions.
>>
>> I  am  now  wondering  why  the  function  is  not  marked  as  malloc
>> already. In fact, its implementation  always returns what it gets from
>> the built-in malloc. Are there  any known issues or concerns with this
>> that the test suite cannot reveal? Can anyone comment on this?
>
> It is unclear whether this is safe.  Nothing in the standard AFAIK requires 
> the operator new be implemented in terms of malloc, and users are allowed 
> to override it.

I have just  explained in another email that  user-overridden new's do
not  seem to  be  a problem  as the  attribute  is given  only to  the
libstdc++ one.

The reason  why I believe the patch  is safe not only  in practice but
also  in principle is  that the  libstc++ operator  new implementation
(see  below) returns  what  it  gets from  malloc  which is  hopefully
mallocish enough  (and the  operator does not  do any  dangerous stuff
with the pointer either).


Martin


--- cut here ---
_GLIBCXX_WEAK_DEFINITION void *
operator new (std::size_t sz) throw (std::bad_alloc)
{
  void *p;

  /* malloc (0) is unpredictable; avoid it.  */
  if (sz == 0)
    sz = 1;
  p = (void *) malloc (sz);
  while (p == 0)
    {
      new_handler handler = __new_handler;
      if (! handler)
#ifdef __EXCEPTIONS
        throw bad_alloc();
#else
        std::abort();
#endif
      handler ();
      p = (void *) malloc (sz);
    }

  return p;
}
--- cuthere ---

Re: [RFC] Marking C++ new operator as malloc?

[Martin Jambor]

Hi,

On Sat, Sep 08, 2007 at 07:45:32AM -0700, H.J. Lu wrote:
> On Sat, Sep 08, 2007 at 12:57:13AM -0500, Gabriel Dos Reis wrote:
> > I seem to remember we had had this discussion before -- in connection
> > with optimizations related to 'malloc' attribute -- and decided not to
> > apply the attribute because it was not clear whether it was permitted
> > by the standard.  I don't seem to get my hands on reference to the
> > thread right now.
> 
> There is a related bug:
> 
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=32748

I followed  that discussion  in July  and read it  over again  now (it
starts      with     http://gcc.gnu.org/ml/gcc/2007-07/msg00513.html).
However, I do not believe that it is relevant, because unlike realloc,
new does not half-destroy half-retain an object.

Martin

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

Joe Buck <Joe.Buck@synopsys.COM> writes:

| On Sat, Sep 08, 2007 at 04:33:50PM -0500, Gabriel Dos Reis wrote:
| > "Richard Guenther" <richard.guenther@gmail.com> writes:
| > 
| > | On 9/8/07, Chris Lattner <clattner@apple.com> wrote:
| > | > I understand, but allowing users to override new means that the actual
| > | > implementation may not honor the aliasing guarantees of attribute
| > | > malloc.
| > | 
| > | Well, you can argue that all hell breaks lose if you do so.  A sane ::new
| > | is required for almost everything :)
| > 
| > I suspect the question is how to you distinguish a sane new from an an
| > insane one.
| 
| Does it matter?

No, it does not.

The reason is 3.7.3.1/2

  [...] If the request succeeds, the value returned shall be a nonnull
  pointer value (4.10) p0 different from any previously returned value
  p1, unless that value p1 was subsequently passed to an operator delete.

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

Martin Jambor <jamborm@matfyz.cz> writes:

[...]

| The reason  why I believe the patch  is safe not only  in practice but
| also  in principle 

However, I do not believe it is sufficient.  The reason being that
if the user does not include a header that pulls in that declaration,
then that 'malloc' attribute will be in effect.  
The abstract semantics is that replaceable `operator new' functions
are implicitly declared in *every* translation unit -- and that is
what GCC does --, and you should have those implicit declarations
carry the attributes, not just the one defined in libstdc++.

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Ross Smith]

Gabriel Dos Reis wrote:
> Joe Buck <Joe.Buck@synopsys.COM> writes:
> 
> | On Sat, Sep 08, 2007 at 04:33:50PM -0500, Gabriel Dos Reis wrote:
> | > "Richard Guenther" <richard.guenther@gmail.com> writes:
> | > 
> | > | On 9/8/07, Chris Lattner <clattner@apple.com> wrote:
> | > | > I understand, but allowing users to override new means that the actual
> | > | > implementation may not honor the aliasing guarantees of attribute
> | > | > malloc.
> | > | 
> | > | Well, you can argue that all hell breaks lose if you do so.  A sane ::new
> | > | is required for almost everything :)
> | > 
> | > I suspect the question is how to you distinguish a sane new from an an
> | > insane one.
> | 
> | Does it matter?
> 
> No, it does not.
> 
> The reason is 3.7.3.1/2
> 
>   [...] If the request succeeds, the value returned shall be a nonnull
>   pointer value (4.10) p0 different from any previously returned value
>   p1, unless that value p1 was subsequently passed to an operator delete.

That's not sufficient. First, merely requiring pointers to be different 
isn't the same as requiring them not to alias, which requires the blocks 
of memory they point to not to overlap. Second, the standard only 
requires the pointers returned by new to be different from each other, 
not from any other pointer in the program.

Probably the most common use of a custom new is to allocate memory from 
a user-controlled pool instead of the standard free store. Somewhere in 
the program there will be a pointer to the complete pool, which aliases 
every pointer returned by that version of new. Any such pool-based new 
doesn't meet the requirements of the malloc attribute.

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Ross Smith <r-smith@ihug.co.nz> wrote:
> Gabriel Dos Reis wrote:
> > Joe Buck <Joe.Buck@synopsys.COM> writes:
> >
> > | On Sat, Sep 08, 2007 at 04:33:50PM -0500, Gabriel Dos Reis wrote:
> > | > "Richard Guenther" <richard.guenther@gmail.com> writes:
> > | >
> > | > | On 9/8/07, Chris Lattner <clattner@apple.com> wrote:
> > | > | > I understand, but allowing users to override new means that the actual
> > | > | > implementation may not honor the aliasing guarantees of attribute
> > | > | > malloc.
> > | > |
> > | > | Well, you can argue that all hell breaks lose if you do so.  A sane ::new
> > | > | is required for almost everything :)
> > | >
> > | > I suspect the question is how to you distinguish a sane new from an an
> > | > insane one.
> > |
> > | Does it matter?
> >
> > No, it does not.
> >
> > The reason is 3.7.3.1/2
> >
> >   [...] If the request succeeds, the value returned shall be a nonnull
> >   pointer value (4.10) p0 different from any previously returned value
> >   p1, unless that value p1 was subsequently passed to an operator delete.
>
> That's not sufficient. First, merely requiring pointers to be different
> isn't the same as requiring them not to alias, which requires the blocks
> of memory they point to not to overlap. Second, the standard only
> requires the pointers returned by new to be different from each other,
> not from any other pointer in the program.
>
> Probably the most common use of a custom new is to allocate memory from
> a user-controlled pool instead of the standard free store. Somewhere in
> the program there will be a pointer to the complete pool, which aliases
> every pointer returned by that version of new. Any such pool-based new
> doesn't meet the requirements of the malloc attribute.

That doesn't matter.  What matters is object lifetime, which is properly
preserved by a conforming pool allocator.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Joe Buck]

On Mon, Sep 10, 2007 at 05:33:24AM +1200, Ross Smith wrote:
> >  [...] If the request succeeds, the value returned shall be a nonnull
> >  pointer value (4.10) p0 different from any previously returned value
> >  p1, unless that value p1 was subsequently passed to an operator delete.
> 
> That's not sufficient. First, merely requiring pointers to be different 
> isn't the same as requiring them not to alias, which requires the blocks 
> of memory they point to not to overlap.

That might be grounds for a defect report; clearly the blocks handed out
must not overlap, or conforming programs will fail.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

>> Probably the most common use of a custom new is to allocate memory from
>> a user-controlled pool instead of the standard free store. Somewhere in
>> the program there will be a pointer to the complete pool, which aliases
>> every pointer returned by that version of new. Any such pool-based new
>> doesn't meet the requirements of the malloc attribute.
> 
> That doesn't matter.  What matters is object lifetime, which is properly
> preserved by a conforming pool allocator.

We have some terminology issues here.  The definition of the malloc
attribute is:

> The `malloc' attribute is used to tell the compiler that a function
>      may be treated as if any non-`NULL' pointer it returns cannot
>      alias any other pointer valid when the function returns.  This
>      will often improve optimization.

The term "cannot alias" is not fully defined.  It could mean "cannot
have the same value as any other pointer of the same type".  It could
mean "cannot have the same value as any other pointer, when both
pointers are cast to `void *'".  It could mean, a la "restrict", that
"no store through an expression based on this pointer can modify the
value read from via any expression based on any other pointer".

In the case of "malloc", and assuming that all of the machinery for
malloc is hidden away in some piece of the program we're not talking
about, all three definitions apply.  Each pointer returned by malloc is
an island unto itself; there's no conforming way to get there except by
using the pointer just returned.

For, operator new, the same is true -- but we're more often able to see
the machinery for the allocator.  For example:

char pool[N];
size_t next;

/* Never mind that the return memory isn't properly aligned here;
   fixing the implementation is left to the reader.  */
void *operator new(size_t s) {
   void *p = pool + next;
   next += s;
   return p;
}

bool f() {
  char *c = new char;
  return (c == pool);
}

Now, I don't think we should allow the compiler to optimize the return
statement in "f" to "return false"?  If operator new has attribute
malloc, then it may in fact do so -- even though the value returned
might be "pool" itself.

The same issue occurs if you call malloc from within the file that
defines malloc; the malloc attribute is saying something about what you
can do *if you cannot see the pool out of which the allocation is
occurring*.  For malloc, which is fully squirreled away in libc
somewhere, this is probably safe in practice -- until LTO.  For operator
new, it's a little dicier, since people do tend more often to replace it
in their own programs, and to put those replacements in inline functions
in header files where the compiler is liable to see more about what's
going on.

This seems like a useful optimization to me, and I understand that it
will work 99.99% of the time, and it's in the spirit of the standard --
but how do we actually make it safe?  If the attribute only applied to
other values returned from the same function, then it would be safe --
but less useful.  Can we do better?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Joe Buck]

On Sun, Sep 09, 2007 at 12:24:13PM -0700, Mark Mitchell wrote:
> The term "cannot alias" is not fully defined.  It could mean "cannot
> have the same value as any other pointer of the same type".  It could
> mean "cannot have the same value as any other pointer, when both
> pointers are cast to `void *'".  It could mean, a la "restrict", that
> "no store through an expression based on this pointer can modify the
> value read from via any expression based on any other pointer".
> 
> In the case of "malloc", and assuming that all of the machinery for
> malloc is hidden away in some piece of the program we're not talking
> about, all three definitions apply.  Each pointer returned by malloc is
> an island unto itself; there's no conforming way to get there except by
> using the pointer just returned.

The key point is that the mechanism is hidden away.  This might become
more of an issue with LTO, so the question is how to make such guarantees
make sense to an optimizer that can see the full program.

> For, operator new, the same is true -- but we're more often able to see
> the machinery for the allocator.  For example:
> 
> char pool[N];
> size_t next;
> 
> /* Never mind that the return memory isn't properly aligned here;
>    fixing the implementation is left to the reader.  */
> void *operator new(size_t s) {
>    void *p = pool + next;
>    next += s;
>    return p;
> }
> 
> bool f() {
>   char *c = new char;
>   return (c == pool);
> }
> 
> Now, I don't think we should allow the compiler to optimize the return
> statement in "f" to "return false"?  If operator new has attribute
> malloc, then it may in fact do so -- even though the value returned
> might be "pool" itself.

The issue seems to be that the mechanism is exposed.  The operator new
pointers don't alias each other (when used to store objects that fit
within the size argument), but they do have a relationship with "pool".
It seems that there needs to be some sort of protection boundary.
If there's no LTO, then it would suffice to treat the file implementing
operator new as a black-box module, perhaps exporting a "first_allocation"
function to do the c == pool check.

> This seems like a useful optimization to me, and I understand that it
> will work 99.99% of the time, and it's in the spirit of the standard --
> but how do we actually make it safe?  If the attribute only applied to
> other values returned from the same function, then it would be safe --
> but less useful.  Can we do better?

Maybe "pool", if exported, would have to be marked as aliasing the "new"
calls, possibly with some new attribute "malloc_implementation" or
something like that.  Working out the details would be tricky: calling
a malloc-attributed function might change storage marked
"malloc_implementation", and a return value might alias an implementation
value, but two calls would not alias each other.

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
>
> >> Probably the most common use of a custom new is to allocate memory from
> >> a user-controlled pool instead of the standard free store. Somewhere in
> >> the program there will be a pointer to the complete pool, which aliases
> >> every pointer returned by that version of new. Any such pool-based new
> >> doesn't meet the requirements of the malloc attribute.
> >
> > That doesn't matter.  What matters is object lifetime, which is properly
> > preserved by a conforming pool allocator.
>
> We have some terminology issues here.  The definition of the malloc
> attribute is:
>
> > The `malloc' attribute is used to tell the compiler that a function
> >      may be treated as if any non-`NULL' pointer it returns cannot
> >      alias any other pointer valid when the function returns.  This
> >      will often improve optimization.
>
> The term "cannot alias" is not fully defined.  It could mean "cannot
> have the same value as any other pointer of the same type".  It could
> mean "cannot have the same value as any other pointer, when both
> pointers are cast to `void *'".  It could mean, a la "restrict", that
> "no store through an expression based on this pointer can modify the
> value read from via any expression based on any other pointer".

It actually means that all accesses based on the returned pointer do
not alias accesses based on other pointers that are not derived.  In
particular,

  int *p;
  int * __attribute__((malloc)) my_malloc() { return p; }

  void foo(void)
  {
    int *q = my_malloc();
    *p = 1;
    *q = 0;
    return *p;
  }

will be optimized to return 1 if my_malloc is not inlined and 0 otherwise.

> In the case of "malloc", and assuming that all of the machinery for
> malloc is hidden away in some piece of the program we're not talking
> about, all three definitions apply.  Each pointer returned by malloc is
> an island unto itself; there's no conforming way to get there except by
> using the pointer just returned.
>
> For, operator new, the same is true -- but we're more often able to see
> the machinery for the allocator.  For example:
>
> char pool[N];
> size_t next;
>
> /* Never mind that the return memory isn't properly aligned here;
>    fixing the implementation is left to the reader.  */
> void *operator new(size_t s) {
>    void *p = pool + next;
>    next += s;
>    return p;
> }
>
> bool f() {
>   char *c = new char;
>   return (c == pool);
> }
>
> Now, I don't think we should allow the compiler to optimize the return
> statement in "f" to "return false"?  If operator new has attribute
> malloc, then it may in fact do so -- even though the value returned
> might be "pool" itself.

Yes, at least the first case would give different results based on inlining
decisions.  But only for undefined cases I believe.

> The same issue occurs if you call malloc from within the file that
> defines malloc; the malloc attribute is saying something about what you
> can do *if you cannot see the pool out of which the allocation is
> occurring*.  For malloc, which is fully squirreled away in libc
> somewhere, this is probably safe in practice -- until LTO.

Which brings back the fact that you cannot implement malloc in C
(you certainly remember the discussions about C++ placement new
handling wrt aliasing).  To re-use the machinery we invented there
we would need to place a CHANGE_DYNAMIC_TYPE_EXPR for
the pointer assignment resulting from inlining a function with
attribute malloc set.  As you say, unless we are inlining such functions
we are safe in practice.

> For operator
> new, it's a little dicier, since people do tend more often to replace it
> in their own programs, and to put those replacements in inline functions
> in header files where the compiler is liable to see more about what's
> going on.
>
> This seems like a useful optimization to me, and I understand that it
> will work 99.99% of the time, and it's in the spirit of the standard --
> but how do we actually make it safe?  If the attribute only applied to
> other values returned from the same function, then it would be safe --
> but less useful.  Can we do better?

See above - inlining an allocator function produces the need to change
the dynamic type of the pointed-to memory as we are basically exposing
a "placement new" operation to the optimizers.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Joe Buck wrote:

>> In the case of "malloc", and assuming that all of the machinery for
>> malloc is hidden away in some piece of the program we're not talking
>> about, all three definitions apply.  Each pointer returned by malloc is
>> an island unto itself; there's no conforming way to get there except by
>> using the pointer just returned.
> 
> The key point is that the mechanism is hidden away.  This might become
> more of an issue with LTO, so the question is how to make such guarantees
> make sense to an optimizer that can see the full program.

Correct.  The "malloc" attribute is only applicable to "malloc" because
we can't see how "malloc" is implemented.

>> This seems like a useful optimization to me, and I understand that it
>> will work 99.99% of the time, and it's in the spirit of the standard --
>> but how do we actually make it safe?  If the attribute only applied to
>> other values returned from the same function, then it would be safe --
>> but less useful.  Can we do better?
> 
> Maybe "pool", if exported, would have to be marked as aliasing the "new"
> calls, possibly with some new attribute "malloc_implementation" or
> something like that. 

It's worse than that:

  char *pool;
  void set_pool(char *p) { pool = p; }
  void *operator new(size_t s) { // return stuff from pool. }

  bool f() {
     char *p = new char[1024];
     set_pool (p);
     char *i = new char;
     return (p == i);
  }

In other words, pointers from any part of the program can potentially be
"laundered" through set_pool and return via the new operator.  I don't
see any way to make this fully safe, in general, without the limitation
I imposed: the no-aliasing guarantee only applies to the values returned
from the function called.

For a particular implementation of "operator new" (such as the one in
libstdc++), you can of course make it safe in the same way as "malloc";
hide the implementation somewhere the rest of the program can't see it
(modulo LTO).  But, to declare it with the "malloc" attribute in the
headers seems dangerous, since we have no way of knowing if the user
replaced it, off in some file somewhere we don't know about, but in such
a way that pointers in our source code are being laundered back to us.

Perhaps we could have an <ext/i_promise_i_will_not_define_new> header,
which you can include if you aren't overriding the operator...

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Joe Buck wrote:
>
> >> In the case of "malloc", and assuming that all of the machinery for
> >> malloc is hidden away in some piece of the program we're not talking
> >> about, all three definitions apply.  Each pointer returned by malloc is
> >> an island unto itself; there's no conforming way to get there except by
> >> using the pointer just returned.
> >
> > The key point is that the mechanism is hidden away.  This might become
> > more of an issue with LTO, so the question is how to make such guarantees
> > make sense to an optimizer that can see the full program.
>
> Correct.  The "malloc" attribute is only applicable to "malloc" because
> we can't see how "malloc" is implemented.
>
> >> This seems like a useful optimization to me, and I understand that it
> >> will work 99.99% of the time, and it's in the spirit of the standard --
> >> but how do we actually make it safe?  If the attribute only applied to
> >> other values returned from the same function, then it would be safe --
> >> but less useful.  Can we do better?
> >
> > Maybe "pool", if exported, would have to be marked as aliasing the "new"
> > calls, possibly with some new attribute "malloc_implementation" or
> > something like that.
>
> It's worse than that:
>
>   char *pool;
>   void set_pool(char *p) { pool = p; }
>   void *operator new(size_t s) { // return stuff from pool. }
>
>   bool f() {
>      char *p = new char[1024];
>      set_pool (p);
>      char *i = new char;
>      return (p == i);
>   }
>
> In other words, pointers from any part of the program can potentially be
> "laundered" through set_pool and return via the new operator.  I don't
> see any way to make this fully safe, in general, without the limitation
> I imposed: the no-aliasing guarantee only applies to the values returned
> from the function called.

But in this case an access to *i through *p is invalid.  [I suppose both
new calls are actually different implementations here]  Each new
call starts lifetime of a new object,  the previous object lifetime is
terminated.  Even comparing both pointers here for this reason
would lead to undefined behavior.

I know it's easy to play games to trick optimizers into doing something,
but creating a not undefined testcase that goes wrong is hard ;)  At
least iff you remember to transform 'malloc' attributes to a dynamic type
change if you inline a malloc.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Richard Guenther <richard.guenther@gmail.com> wrote:
>
> Which brings back the fact that you cannot implement malloc in C
> (you certainly remember the discussions about C++ placement new
> handling wrt aliasing).  To re-use the machinery we invented there
> we would need to place a CHANGE_DYNAMIC_TYPE_EXPR for
> the pointer assignment resulting from inlining a function with
> attribute malloc set.  As you say, unless we are inlining such functions
> we are safe in practice.

Actually this looks nice in general.  We could implement placement
new in C this way:

  extern inline T * __attribute__((malloc)) placement_new (void *p)
  { return p; }

if we can somehow encode the target type here.  Note that only
type-based aliasing is a problem with this discussion - PTA will
be obviously fine if new is inlined as it will see that both pointers
are related and we loose the 'malloc' attribution on the target pointer
during inlining.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

>>   char *pool;
>>   void set_pool(char *p) { pool = p; }
>>   void *operator new(size_t s) { // return stuff from pool. }
>>
>>   bool f() {
>>      char *p = new char[1024];
>>      set_pool (p);
>>      char *i = new char;
>>      return (p == i);
>>   }
>>
>> In other words, pointers from any part of the program can potentially be
>> "laundered" through set_pool and return via the new operator.  I don't
>> see any way to make this fully safe, in general, without the limitation
>> I imposed: the no-aliasing guarantee only applies to the values returned
>> from the function called.
> 
> But in this case an access to *i through *p is invalid.  [I suppose both
> new calls are actually different implementations here]  Each new
> call starts lifetime of a new object,  the previous object lifetime is
> terminated.  Even comparing both pointers here for this reason
> would lead to undefined behavior.

I don't think there's necessarily agreement about that; you're into
what-is-an-object land here...

In any case, using new to allocate from a pool doesn't invalidate the
pointer to the pool itself.  Even if you think reads/writes through *p
are undefined, do you think that comparing addresses is undefined?  If
so, how can you still talk about "pool" at all, even in the
implementation of "new" and "delete" themselves, after the first
allocation?

If comparing addresses is allowed, it's weird to think that:

  if (p == i)
    *p = '\0';

is invalid, while:

  if (p == i)
    *i = '\0';

is valid, but I suppose it's possible.

Do we have any way to guarantee that aliasing information will not be
used when analyzing pointer comparisons, but only when analyzing stores
through pointers?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
>
> >>   char *pool;
> >>   void set_pool(char *p) { pool = p; }
> >>   void *operator new(size_t s) { // return stuff from pool. }
> >>
> >>   bool f() {
> >>      char *p = new char[1024];
> >>      set_pool (p);
> >>      char *i = new char;
> >>      return (p == i);
> >>   }
> >>
> >> In other words, pointers from any part of the program can potentially be
> >> "laundered" through set_pool and return via the new operator.  I don't
> >> see any way to make this fully safe, in general, without the limitation
> >> I imposed: the no-aliasing guarantee only applies to the values returned
> >> from the function called.
> >
> > But in this case an access to *i through *p is invalid.  [I suppose both
> > new calls are actually different implementations here]  Each new
> > call starts lifetime of a new object,  the previous object lifetime is
> > terminated.  Even comparing both pointers here for this reason
> > would lead to undefined behavior.
>
> I don't think there's necessarily agreement about that; you're into
> what-is-an-object land here...
>
> In any case, using new to allocate from a pool doesn't invalidate the
> pointer to the pool itself.  Even if you think reads/writes through *p
> are undefined, do you think that comparing addresses is undefined?  If
> so, how can you still talk about "pool" at all, even in the
> implementation of "new" and "delete" themselves, after the first
> allocation?
>
> If comparing addresses is allowed, it's weird to think that:
>
>   if (p == i)
>     *p = '\0';
>
> is invalid, while:
>
>   if (p == i)
>     *i = '\0';
>
> is valid, but I suppose it's possible.
>
> Do we have any way to guarantee that aliasing information will not be
> used when analyzing pointer comparisons, but only when analyzing stores
> through pointers?

I don't know of any place we would use such information.  At least

  int *p = new int;
  int *q = new int;
  if (p == q)

cannot be simplified as both pointers may be NULL?

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

> I don't know of any place we would use such information.  At least
> 
>   int *p = new int;
>   int *q = new int;
>   if (p == q)
> 
> cannot be simplified as both pointers may be NULL?

They cannot be NULL; new-expressions throw an exception if the
allocation fails.  (Of course, they could be NULL if you called the
"nothrow" variant, or another "operator new" declared "throw()".)

We should optimize away things like:

  int *p = new int;
  if (!p)
    cerr << "Could not allocate memory\n";

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
>
> > I don't know of any place we would use such information.  At least
> >
> >   int *p = new int;
> >   int *q = new int;
> >   if (p == q)
> >
> > cannot be simplified as both pointers may be NULL?
>
> They cannot be NULL; new-expressions throw an exception if the
> allocation fails.  (Of course, they could be NULL if you called the
> "nothrow" variant, or another "operator new" declared "throw()".)
>
> We should optimize away things like:
>
>   int *p = new int;
>   if (!p)
>     cerr << "Could not allocate memory\n";

We don't I believe.  We'd optimize

  int *p = new int;
  *p;
  if (!p)
    cerr << "Could not allocate memory\n";

though ;)  Well, at least malloc is allowed to return NULL, so unless
we want to force all malloc attributed functions in C++ to throw exceptions
we cannot assume they return non-NULL (just on the basis they have
malloc attribute, that is).

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
> > Richard Guenther wrote:
> >
> > > I don't know of any place we would use such information.  At least
> > >
> > >   int *p = new int;
> > >   int *q = new int;
> > >   if (p == q)
> > >
> > > cannot be simplified as both pointers may be NULL?

A better one:

  int *p = new int;
  foo(p);
  int *q = new int;

if foo deletes p then q may be equal to p.  But alias analysis still
(validly!) says they don't alias.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

>> We should optimize away things like:
>>
>>   int *p = new int;
>>   if (!p)
>>     cerr << "Could not allocate memory\n";
> 
> We don't I believe.

That's a missed-optimization, and independent of any attributes on
"operator new".  It's a property of the new *expression*, not of the
implementation of new.  If the compiler treats:

  int *p = new int;

any differently from:

  int &r = *new int;

then we're missing an optimization opportunity.

> though ;)  Well, at least malloc is allowed to return NULL, so unless
> we want to force all malloc attributed functions in C++ to throw exceptions
> we cannot assume they return non-NULL (just on the basis they have
> malloc attribute, that is).

Sure, we can have the attribute in C++ mean the same thing it does in C,
even if that's not the strongest declaration we can make.  That's OK.

But, I don't think that even the C meaning is safe in C++ for use with
the library declaration of <new>.  I'm also somewhat skeptical of the
idea that we will never do any optimization on pointer comparisons.
What design principle in the compiler is going to keep us from some day
introducing the obvious idea that "if modifying *p cannot affect the
value of *q, and p and q are of the same type, then p != q"?

I think that (a) either we have to weaken the meaning of the attribute
in some way, or (b) we let users use this attribute optionally, for
their implementations of operator new when they "know" it's OK to do so,
but do not actually put it in the standard headers.

I'm not arguing that the attribute is meaningless in C++, or does not
apply to the libstdc++ implementation; I'm just arguing that putting it
into <new> is not safe.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
>
> But, I don't think that even the C meaning is safe in C++ for use with
> the library declaration of <new>.  I'm also somewhat skeptical of the
> idea that we will never do any optimization on pointer comparisons.
> What design principle in the compiler is going to keep us from some day
> introducing the obvious idea that "if modifying *p cannot affect the
> value of *q, and p and q are of the same type, then p != q"?

But that reasoning is not valid.  Consider

 void foo(int *q, double *p)
 {
    if (q != p)
      abort ();
 }
 int main()
 {
   int i;
   foo (&i, &i);
 }

which would abort.  Now, instead

void foo(int *q, double *p)
{
  *q;
  *p;
  if (q != p)
    abort ();
}

we can optimize the comparison to alwas true as in the case
of p == q the program invokes undefined behavior.  The essence
is that we usually cannot tell anything about pointer values and
pointed-to types unless we see accesses through them.

> I think that (a) either we have to weaken the meaning of the attribute
> in some way, or (b) we let users use this attribute optionally, for
> their implementations of operator new when they "know" it's OK to do so,
> but do not actually put it in the standard headers.

> I'm not arguing that the attribute is meaningless in C++, or does not
> apply to the libstdc++ implementation; I'm just arguing that putting it
> into <new> is not safe.

Today we should be safe I believe.  Even if we inline new (we'd lose
knowledge about the call in this case -- which we of course may
fix in future).

It would be nice to have some testcases in the testsuite with the ideas
that pop up around these discussions though :)

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

> A better one:
> 
>   int *p = new int;
>   foo(p);
>   int *q = new int;
> 
> if foo deletes p then q may be equal to p.  But alias analysis still
> (validly!) says they don't alias.

Yes, I agree that this is safe.  (Either "p" is still valid and
therefore different from "q", or it has been deleted and you may no
longer talk about it.)  That's the case I mentioned of assuming that
distinct calls to "operator new" result in different values.  But,
that's not as strong as assuming that "p" is distinct from all other
pointers in the program, which is what the "malloc" attribute says.

And, even here there's a corner case:

  char *pool;
  void *operator new(size_t) { // return memory from pool }
  bool f() {
    char *p = new char;
    pool = p;
    char *q = new char;
    return p == q;
  }

Here, we have the situation that two subsequent calls to the same
"operator new" returned the same pointer.

Why isn't that valid?  For a more real-world example, use array-new for
the first call.

I don't think the GCC lists are actually the place to fix these kinds of
problems.  These are fundamental problems with the C++ standard.  It
simply is not sufficiently clear about all of these memory model issues
to allow us (as compiler vendors) to reason about them in the ways that
we "know" make sense.

I think the optimization we want to do here (i.e., assume that pointers
returned by operator new are all distinct, and distinct from all other
pointers we can see) is only safe for particular implementations of
operator new.  So, I don't think we can put any attribute to that affect
in our standard headers.  You need a command-line switch, macro, etc.,
for the user to use to say that they are using an implementation that
meets the requirements.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:
> On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
>> But, I don't think that even the C meaning is safe in C++ for use with
>> the library declaration of <new>.  I'm also somewhat skeptical of the
>> idea that we will never do any optimization on pointer comparisons.
>> What design principle in the compiler is going to keep us from some day
>> introducing the obvious idea that "if modifying *p cannot affect the
>> value of *q, and p and q are of the same type, then p != q"?
> 
> But that reasoning is not valid.  Consider
> 
>  void foo(int *q, double *p)
>  {
>     if (q != p)
>       abort ();
>  }
>  int main()
>  {
>    int i;
>    foo (&i, &i);
>  }

That doesn't type-check; did you want to have a cast somewhere?  Note
that my statement above depends on the pointers having the same type.

What is an example program in that meets the requirements I gave above
-- i.e., allows the compiler to prove that two same-typed pointers do
not alias (whether by the compiler's cleverness, use of "restrict", or
whatever), but where the compiler must still assume that the values of
the pointers might be the same?

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

Mark Mitchell <mark@codesourcery.com> writes:

[...]

| This seems like a useful optimization to me, and I understand that it
| will work 99.99% of the time

Except for people writing allocators :-)

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

"Richard Guenther" <richard.guenther@gmail.com> writes:


[...]

| > It's worse than that:
| >
| >   char *pool;
| >   void set_pool(char *p) { pool = p; }
| >   void *operator new(size_t s) { // return stuff from pool. }
| >
| >   bool f() {
| >      char *p = new char[1024];
| >      set_pool (p);
| >      char *i = new char;
| >      return (p == i);
| >   }
| >
| > In other words, pointers from any part of the program can potentially be
| > "laundered" through set_pool and return via the new operator.  I don't
| > see any way to make this fully safe, in general, without the limitation
| > I imposed: the no-aliasing guarantee only applies to the values returned
| > from the function called.
| 
| But in this case an access to *i through *p is invalid.  [I suppose both
| new calls are actually different implementations here]  Each new
| call starts lifetime of a new object,  the previous object lifetime is
| terminated.  Even comparing both pointers here for this reason
| would lead to undefined behavior.

I don't follow your reasoning here.  'char*' and 'void*' are special.

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

"Richard Guenther" <richard.guenther@gmail.com> writes:


[...]

| I don't know of any place we would use such information.  At least
| 
|   int *p = new int;
|   int *q = new int;
|   if (p == q)
| 
| cannot be simplified as both pointers may be NULL?

The above does not use the no-throw operator new, so neither can be
null -- except if the user used command-line -fno-exceptions.

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
> > On 9/9/07, Mark Mitchell <mark@codesourcery.com> wrote:
> >> But, I don't think that even the C meaning is safe in C++ for use with
> >> the library declaration of <new>.  I'm also somewhat skeptical of the
> >> idea that we will never do any optimization on pointer comparisons.
> >> What design principle in the compiler is going to keep us from some day
> >> introducing the obvious idea that "if modifying *p cannot affect the
> >> value of *q, and p and q are of the same type, then p != q"?
> >
> > But that reasoning is not valid.  Consider
> >
> >  void foo(int *q, double *p)
> >  {
> >     if (q != p)
> >       abort ();
> >  }
> >  int main()
> >  {
> >    int i;
> >    foo (&i, &i);
> >  }
>
> That doesn't type-check; did you want to have a cast somewhere?  Note
> that my statement above depends on the pointers having the same type.
>
> What is an example program in that meets the requirements I gave above
> -- i.e., allows the compiler to prove that two same-typed pointers do
> not alias (whether by the compiler's cleverness, use of "restrict", or
> whatever), but where the compiler must still assume that the values of
> the pointers might be the same?

I see I misinterpreted your sentence.  I don't think a testcase that
holds all your requirements can be constructed as they
contradict each other.  Can you give one?

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

>> What is an example program in that meets the requirements I gave above
>> -- i.e., allows the compiler to prove that two same-typed pointers do
>> not alias (whether by the compiler's cleverness, use of "restrict", or
>> whatever), but where the compiler must still assume that the values of
>> the pointers might be the same?
> 
> I see I misinterpreted your sentence.  I don't think a testcase that
> holds all your requirements can be constructed as they
> contradict each other.  Can you give one?

No -- I don't think any such test case should exist.  But, IIUC, one of
your proposals could lead to the existence of such a test case.  In
particular, I understood you to be suggesting that we might be able to
make the "malloc" attribute work for any implementation of "operator
new" by saying that while the compiler could assume that "*p" and "*q"
did not alias, the compiler was none-the-less not allowed to assume that
"p != q".

My point was that this seems like a very strange requirement to impose
on the compiler, and that the compiler -- now, or in future -- is very
likely to make exactly that deduction, since it is logically true.  More
broadly, my point was that a universe in which "*p does not alias *q"
fails to imply "p != q", for "p" and "q" pointers of the same type, is a
weird place to be.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/10/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
>
> >> What is an example program in that meets the requirements I gave above
> >> -- i.e., allows the compiler to prove that two same-typed pointers do
> >> not alias (whether by the compiler's cleverness, use of "restrict", or
> >> whatever), but where the compiler must still assume that the values of
> >> the pointers might be the same?
> >
> > I see I misinterpreted your sentence.  I don't think a testcase that
> > holds all your requirements can be constructed as they
> > contradict each other.  Can you give one?
>
> No -- I don't think any such test case should exist.  But, IIUC, one of
> your proposals could lead to the existence of such a test case.  In
> particular, I understood you to be suggesting that we might be able to
> make the "malloc" attribute work for any implementation of "operator
> new" by saying that while the compiler could assume that "*p" and "*q"
> did not alias, the compiler was none-the-less not allowed to assume that
> "p != q".
>
> My point was that this seems like a very strange requirement to impose
> on the compiler, and that the compiler -- now, or in future -- is very
> likely to make exactly that deduction, since it is logically true.  More
> broadly, my point was that a universe in which "*p does not alias *q"
> fails to imply "p != q", for "p" and "q" pointers of the same type, is a
> weird place to be.

Well, we have that now:

  int *q = new int;
  delete q;
  int *p = new int;
  delete p;
  if (q != p)
    cout << "different";

we cannot optimize the test to be always true.  The point is that alias
analysis tells us something about accesses to *q and *p, but neither
on lifetime of *q and *p nor lifetime of q and p (and thus their value).

The only value analysis valid on pointers is non-NULLness which we
can derive from accesses to the pointed-to memory location (ok, assuming
the OS really traps on accesses to address zero, which is not true in
general).

I don't think my proposal opens up more "problems" in this area.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Martin Jambor]

Hi,

On Sun, Sep 09, 2007 at 12:56:25PM -0700, Mark Mitchell wrote:
> For a particular implementation of "operator new" (such as the one in
> libstdc++), you can of course make it safe in the same way as "malloc";
> hide the implementation somewhere the rest of the program can't see it
> (modulo LTO).  But, to declare it with the "malloc" attribute in the
> headers seems dangerous, since we have no way of knowing if the user
> replaced it, off in some file somewhere we don't know about, but in such
> a way that pointers in our source code are being laundered back to us.

All I attempted  to do was to mark  just one particular implementation
of the  new operator  which also happened  to be the  default built-in
one. From my experiments, it appears  that marking it as malloc in the
libstc++ headers  does not affect other  implementations.  However, as
Gabriel Dos Reis  correctly pointed out, the attribute  is not applied
to the new operator if the changed declaration is not somehow included
in  the  compiled source.   Fixing  this  inconsistency requires  some
changes in  the FE.  Nevertheless, so  far I do not  see problems with
declaring standard new implementation as malloc in the header file.

I hope you all agree that  marking the default (and only the default),
implementation as  malloc is worthwhile  and will look into  it(, even
though it is going to take some time).

Martin

Re: [RFC] Marking C++ new operator as malloc?

[Tom Tromey]

>>>>> "Mark" == Mark Mitchell <mark@codesourcery.com> writes:

Mark> If the compiler treats:
Mark>   int *p = new int;
Mark> any differently from:
Mark>   int &r = *new int;
Mark> then we're missing an optimization opportunity.

AFAIK we don't have a way to mark a function as "cannot return NULL".
This is PR 20318.

Tom

Re: [RFC] Marking C++ new operator as malloc?

[Daniel Berlin]

On 9/10/07, Tom Tromey <tromey@redhat.com> wrote:
> >>>>> "Mark" == Mark Mitchell <mark@codesourcery.com> writes:
>
> Mark> If the compiler treats:
> Mark>   int *p = new int;
> Mark> any differently from:
> Mark>   int &r = *new int;
> Mark> then we're missing an optimization opportunity.
>
> AFAIK we don't have a way to mark a function as "cannot return NULL".
> This is PR 20318.

If someone reviewed zdenek's function attribute table patch (That
started adding info about arguments, etc and what happens to them), we
could simply extend it to do this in about 10 lines of code

>
> Tom
>

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

> Well, we have that now:
> 
>   int *q = new int;
>   delete q;
>   int *p = new int;
>   delete p;
>   if (q != p)
>     cout << "different";
> 
> we cannot optimize the test to be always true.  The point is that alias
> analysis tells us something about accesses to *q and *p, but neither
> on lifetime of *q and *p nor lifetime of q and p (and thus their value).

That's an interesting example.  Thanks for showing it to me.  From
looking at the standard, I think I could be a language lawyer and try to
argue that the comparison is not defined -- but that would just be
weaselish; the comparison should be defined.  So, yes, I concede that
you've found a counter-example to my claim that "*p does not alias *q"
=> "p != q".  How odd.  I would have to revise my claim to require that
"p" and "q" are valid pointers.

So, for something like:

  char *pool;
  void *operator new[] (size_t s) { /* return memory from pool */ }
  ...
  pool = new char[1024];
  char *c = new char[16];

IIUC, your claim is that if pool and c now have the same value, then any
indirection through pool is invalid (because the object with newest
lifetime at that location is the 16-byte array), so we can assume *pool
and *c do not alias?  Do you also claim that:

  ((char (*)[16])pool)[0] = '\0';

is invalid because it is a pointer "based on" pool?

If you think it's OK to put the "malloc" attribute on operator new, why
did you say earlier that you can't implement "malloc" in C itself, for
exactly these kinds of reasons?  Isn't the situation exactly analogous?

I think I'm getting confused.  Perhaps you could sum up in a single
email the argument for why putting this attribute in our standard
headers is safe, even in view of possible replacement in user programs?

Sorry,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 9/11/07, Mark Mitchell <mark@codesourcery.com> wrote:
> Richard Guenther wrote:
>
> > Well, we have that now:
> >
> >   int *q = new int;
> >   delete q;
> >   int *p = new int;
> >   delete p;
> >   if (q != p)
> >     cout << "different";
> >
> > we cannot optimize the test to be always true.  The point is that alias
> > analysis tells us something about accesses to *q and *p, but neither
> > on lifetime of *q and *p nor lifetime of q and p (and thus their value).
>
> That's an interesting example.  Thanks for showing it to me.  From
> looking at the standard, I think I could be a language lawyer and try to
> argue that the comparison is not defined -- but that would just be
> weaselish; the comparison should be defined.  So, yes, I concede that
> you've found a counter-example to my claim that "*p does not alias *q"
> => "p != q".  How odd.  I would have to revise my claim to require that
> "p" and "q" are valid pointers.
>
> So, for something like:
>
>   char *pool;
>   void *operator new[] (size_t s) { /* return memory from pool */ }
>   ...
>   pool = new char[1024];
>   char *c = new char[16];
>
> IIUC, your claim is that if pool and c now have the same value, then any
> indirection through pool is invalid (because the object with newest
> lifetime at that location is the 16-byte array), so we can assume *pool
> and *c do not alias?  Do you also claim that:

Yes.

>   ((char (*)[16])pool)[0] = '\0';
>
> is invalid because it is a pointer "based on" pool?

Yes.

> If you think it's OK to put the "malloc" attribute on operator new, why
> did you say earlier that you can't implement "malloc" in C itself, for
> exactly these kinds of reasons?  Isn't the situation exactly analogous?

It looks like, but C doesn't provide us with the notion of dynamic lifetime
of objects at the same memory location.  That is, the "newest object"
argument doesn't work in C.  In fact this is one reason why we should
not (or can't) put the malloc attribute on obstack_alloc -- it would be
valid to access the obstack memory through the pool pointer.

For C++ we can argue that 'new' starts lifetime of a new object at
the place of the old 'new'ed memory and accesses to the old object
invoke undefined behavior.

> I think I'm getting confused.  Perhaps you could sum up in a single
> email the argument for why putting this attribute in our standard
> headers is safe, even in view of possible replacement in user programs?

My argument goes like "We can safely put attribute malloc on all overloads
of new as C++ starts lifetime of  a new object in the target and accesses to
old objects at that location invoke undefined behavior".  I claim that you
cannot construct a testcase with no undefined behavior that has two
pointers returned from a call to 'new' alias.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

"Richard Guenther" <richard.guenther@gmail.com> writes:

[...]

| > I think I'm getting confused.  Perhaps you could sum up in a single
| > email the argument for why putting this attribute in our standard
| > headers is safe, even in view of possible replacement in user programs?
| 
| My argument goes like "We can safely put attribute malloc on all overloads
                                                            ^^^^^^^^^^^^^^^^^
| of new as C++ starts lifetime of  a new object in the target and accesses to
| old objects at that location invoke undefined behavior".  I claim that you
| cannot construct a testcase with no undefined behavior that has two
| pointers returned from a call to 'new' alias.

I don't think I understand the claim.  The C++ does not say anything
about all overloads in terms of aliasing.  IT makes claims about
specific `operator new's.  Could you elaborate on why it is OK to
annotate all overloads?

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 11 Sep 2007 07:24:44 -0500, Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> "Richard Guenther" <richard.guenther@gmail.com> writes:
>
> [...]
>
> | > I think I'm getting confused.  Perhaps you could sum up in a single
> | > email the argument for why putting this attribute in our standard
> | > headers is safe, even in view of possible replacement in user programs?
> |
> | My argument goes like "We can safely put attribute malloc on all overloads
>                                                             ^^^^^^^^^^^^^^^^^
> | of new as C++ starts lifetime of  a new object in the target and accesses to
> | old objects at that location invoke undefined behavior".  I claim that you
> | cannot construct a testcase with no undefined behavior that has two
> | pointers returned from a call to 'new' alias.
>
> I don't think I understand the claim.  The C++ does not say anything
> about all overloads in terms of aliasing.  IT makes claims about
> specific `operator new's.  Could you elaborate on why it is OK to
> annotate all overloads?

Sorry for the wrong terminology, I think I mean all implementations of

void* operator new(std::size_t) throw (std::bad_alloc);
void* operator new[](std::size_t) throw (std::bad_alloc);
void* operator new(std::size_t, const std::nothrow_t&) throw();
void* operator new[](std::size_t, const std::nothrow_t&) throw();

that is, not only annotating libsupc++ implementation but assuring
the attribute is set by changing the C++ frontend.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Mark Mitchell]

Richard Guenther wrote:

>> So, for something like:
>>
>>   char *pool;
>>   void *operator new[] (size_t s) { /* return memory from pool */ }
>>   ...
>>   pool = new char[1024];
>>   char *c = new char[16];
>>
>> IIUC, your claim is that if pool and c now have the same value, then any
>> indirection through pool is invalid (because the object with newest
>> lifetime at that location is the 16-byte array), so we can assume *pool
>> and *c do not alias?  Do you also claim that:
> 
> Yes.
> 
>>   ((char (*)[16])pool)[0] = '\0';
>>
>> is invalid because it is a pointer "based on" pool?
> 
> Yes.

Thanks for explaining your argument.  It's very well-reasoned.

However, it still leads to weird results.  For example, you're now in a
situation where transforming:

  if (p == q)
    *p = 3;

to:

  if (p == q)
    *q = 3;

is not valid.  I'd imagine most people to be somewhat surprised by that;
it's rather contrary to the idea of equality.  Are we sure we want to go
there?

(This issue does not occur with "restrict", because if the pointers were
known not to alias due to use of "restrict", then the comparison is
always false, by hypothesis -- or else the program behavior is already
undefined.)

>> If you think it's OK to put the "malloc" attribute on operator new, why
>> did you say earlier that you can't implement "malloc" in C itself, for
>> exactly these kinds of reasons?  Isn't the situation exactly analogous?
> 
> It looks like, but C doesn't provide us with the notion of dynamic lifetime
> of objects at the same memory location.

I'm not really confident C++ does either.  Or, rather, that even if it
does, we should take advantage of that.  I'm concerned that we're going
to break a lot of code.

> My argument goes like "We can safely put attribute malloc on all overloads
> of new as C++ starts lifetime of  a new object in the target and accesses to
> old objects at that location invoke undefined behavior".  I claim that you
> cannot construct a testcase with no undefined behavior that has two
> pointers returned from a call to 'new' alias.

Actually, the claim for attribute "malloc" must be even stronger -- the
value returned must not alias *any* other pointer.  I don't think that
affects your argument, but just for the sake of clarity, that must be
your claim.

I think my point of view on this is that, whether or not the standard
can be read to support your claim, I don't think we should put the
attribute in our standard headers.  I'd rather let people who know what
they're doing put that in their own headers if they want to do so.  And,
I'd certainly suggest that we ask the ISO committee before doing this.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: [RFC] Marking C++ new operator as malloc?

[Ian Lance Taylor]

"Richard Guenther" <richard.guenther@gmail.com> writes:

> On 9/9/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> >
> > Which brings back the fact that you cannot implement malloc in C
> > (you certainly remember the discussions about C++ placement new
> > handling wrt aliasing).  To re-use the machinery we invented there
> > we would need to place a CHANGE_DYNAMIC_TYPE_EXPR for
> > the pointer assignment resulting from inlining a function with
> > attribute malloc set.  As you say, unless we are inlining such functions
> > we are safe in practice.
> 
> Actually this looks nice in general.  We could implement placement
> new in C this way:
> 
>   extern inline T * __attribute__((malloc)) placement_new (void *p)
>   { return p; }
> 
> if we can somehow encode the target type here.  Note that only
> type-based aliasing is a problem with this discussion - PTA will
> be obviously fine if new is inlined as it will see that both pointers
> are related and we loose the 'malloc' attribution on the target pointer
> during inlining.

CHANGE_DYNAMIC_TYPE_EXPR has the target type, of course.  So perhaps
we need __attribute__ ((change_dynamic_type))?

Or actually of course __attribute__ ((malloc)) is fine but we could
throw in a CHANGE_DYNAMIC_TYPE_EXPR after any call to such a
function.  That ought to do the right thing for C malloc
implementations as well, I think.

Ian

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 11 Sep 2007 18:14:21 -0700, Ian Lance Taylor <iant@google.com> wrote:
> "Richard Guenther" <richard.guenther@gmail.com> writes:
>
> > On 9/9/07, Richard Guenther <richard.guenther@gmail.com> wrote:
> > >
> > > Which brings back the fact that you cannot implement malloc in C
> > > (you certainly remember the discussions about C++ placement new
> > > handling wrt aliasing).  To re-use the machinery we invented there
> > > we would need to place a CHANGE_DYNAMIC_TYPE_EXPR for
> > > the pointer assignment resulting from inlining a function with
> > > attribute malloc set.  As you say, unless we are inlining such functions
> > > we are safe in practice.
> >
> > Actually this looks nice in general.  We could implement placement
> > new in C this way:
> >
> >   extern inline T * __attribute__((malloc)) placement_new (void *p)
> >   { return p; }
> >
> > if we can somehow encode the target type here.  Note that only
> > type-based aliasing is a problem with this discussion - PTA will
> > be obviously fine if new is inlined as it will see that both pointers
> > are related and we loose the 'malloc' attribution on the target pointer
> > during inlining.
>
> CHANGE_DYNAMIC_TYPE_EXPR has the target type, of course.  So perhaps
> we need __attribute__ ((change_dynamic_type))?
>
> Or actually of course __attribute__ ((malloc)) is fine but we could
> throw in a CHANGE_DYNAMIC_TYPE_EXPR after any call to such a
> function.  That ought to do the right thing for C malloc
> implementations as well, I think.

We should need this only if inlining malloc functions in C.

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Ian Lance Taylor]

"Richard Guenther" <richard.guenther@gmail.com> writes:

> > CHANGE_DYNAMIC_TYPE_EXPR has the target type, of course.  So perhaps
> > we need __attribute__ ((change_dynamic_type))?
> >
> > Or actually of course __attribute__ ((malloc)) is fine but we could
> > throw in a CHANGE_DYNAMIC_TYPE_EXPR after any call to such a
> > function.  That ought to do the right thing for C malloc
> > implementations as well, I think.
> 
> We should need this only if inlining malloc functions in C.

Which we will presumably do at some point.  After all, it's not just
malloc--it's any function with __attribute__ ((malloc)), which can
include user functions.

Ian

Re: [RFC] Marking C++ new operator as malloc?

[Richard Guenther]

On 12 Sep 2007 08:13:31 -0700, Ian Lance Taylor <iant@google.com> wrote:
> "Richard Guenther" <richard.guenther@gmail.com> writes:
>
> > > CHANGE_DYNAMIC_TYPE_EXPR has the target type, of course.  So perhaps
> > > we need __attribute__ ((change_dynamic_type))?
> > >
> > > Or actually of course __attribute__ ((malloc)) is fine but we could
> > > throw in a CHANGE_DYNAMIC_TYPE_EXPR after any call to such a
> > > function.  That ought to do the right thing for C malloc
> > > implementations as well, I think.
> >
> > We should need this only if inlining malloc functions in C.
>
> Which we will presumably do at some point.  After all, it's not just
> malloc--it's any function with __attribute__ ((malloc)), which can
> include user functions.

Btw, I filed PR33407 to hint that we need the CHANGE_DYNAMIC_TYPE_EXPR
trick for the usual operator new
as well.

And yes, we would need to fix all __attribute__((malloc)) functions
in C with the same thing - the problem I see in C is that we don't
know the type we are "converting" to ;)

Richard.

Re: [RFC] Marking C++ new operator as malloc?

[Andrew Pinski]

On 9/7/07, Chris Lattner <clattner@apple.com> wrote:

> It is unclear whether this is safe.  Nothing in the standard AFAIK
> requires the operator new be implemented in terms of malloc, and
> users are allowed to override it.

I was looking for something else in the standard and found this (5.3.4/7):
[Note: If the library allocation function is called, the pointer
returned is distinct from the pointer to any other object. ]

Which means it has to act like malloc.

-- Pinski

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

"Andrew Pinski" <pinskia@gmail.com> writes:

| On 9/7/07, Chris Lattner <clattner@apple.com> wrote:
| 
| > It is unclear whether this is safe.  Nothing in the standard AFAIK
| > requires the operator new be implemented in terms of malloc, and
| > users are allowed to override it.
| 
| I was looking for something else in the standard and found this (5.3.4/7):
| [Note: If the library allocation function is called, the pointer
| returned is distinct from the pointer to any other object. ]
| 
| Which means it has to act like malloc.

As has been pointed out, that is not exactly true -- although I
suspect the intent is to have the default operator new behaves like
malloc.

The difference is that, being distinct from a pointer to any other
object is not the same as not aliasing any other pointer.

Furthermore, the issue is more subtle/non-trivial for C++ because
users can provide their own allocators.


Consider the following:

   struct ChunkAlloc {
     ChunkAlloc();

     void* allocate(size_t n);
     void* deallocate(void*) { } 

   private:
     enum { size = 4096 };
     char chunk[size];          // assume this is suitable aligned
     char* next
   };

   ChunkAlloc::ChunkAlloc() 
      : next(chunk) { }

   void*
   ChunkAlloc::allocate(size_t n)
   {
     if (n == 0) return malloc(1);
     if ((chunk + size - next) >= n) {
        char* mem = next;
        next += n;
        return mem;
     }
     throw bad_alloc;        
   }


Do you believe that allocator is prohibited by the C++ standard?

Notice that the first pointer returned for non-zero memory chunk
request has the same address (as void*) as the allocator object --
under usual GCC ABI.

-- Gaby

Re: [RFC] Marking C++ new operator as malloc?

[Andrew Pinski]

On 13 Sep 2007 19:37:27 -0500, Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
> Do you believe that allocator is prohibited by the C++ standard?

Yes just because it points to another object at that point.

Now people do these tricks, I know but I guess most of them don't
understand C++ that much to know they are invoking undefined behavior.

-- Pinski

Re: [RFC] Marking C++ new operator as malloc?

[Gabriel Dos Reis]

On Thu, 13 Sep 2007, Andrew Pinski wrote:

| On 13 Sep 2007 19:37:27 -0500, Gabriel Dos Reis <gdr@cs.tamu.edu> wrote:
| > Do you believe that allocator is prohibited by the C++ standard?
| 
| Yes just because it points to another object at that point.

I'm afraid that is too dense for me.  Please could you detail that
assertion?


| Now people do these tricks, I know but I guess most of them don't
| understand C++ that much to know they are invoking undefined behavior.

I don't think this is more about doing tricks that implementing than
implementing useful allocators.  Surelly this kind of constructs does
not exist in C, but then C does not provide the appropriate apparatus 
to write conforming alloctors.

Furthermore, ISO C++ is considering the addition of aligned_storage<T,N>.

  http://www.open-std.org/JTC1/SC22/WG21/docs/papers/2007/n2165.pdf

How do you reconcilie the above statement with the fact that an obejct
of type aligned_storage<T,N> will serve as (properly aligned) storage
for objects of type T?

-- Gaby