Re: Null pointer check elimination

Re: Null pointer check elimination

[David Daney]

Thanks Anthony.  This has been bothering me for quite some time.

Anthony Green wrote:
> Our compiler inlines many null pointer tests because the language
> requires that we throw NullPointerExeceptions in certain cases that can
> only be detected through explicit tests.
> 
> What's frustrating is that there are many cases where we're testing the
> nullness of a function return value that we know can never be null.  For
> instance, the result of string appends can never be null.  Neither can
> object allocations.

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

> 
> The attached experimental patch detects one special instance of a
> non-null function result (gnu.gcj.runtime.StringBuffer.append()), and
> marks it as being non-null.  GCC's value range propagation code then
> magically eliminates any redundant null pointer checks.

I think all methods returning a reference in 
gnu.gcj.runtime.StringBuffer, java.lang.StringBuffer, 
java.lang.StringBuilder fall into this category.

> 
> Eventually we should manually mark certain function DECLs as
> not-returning-null instead of my kludgy test for this one case.  I don't
> know if/when I can get to that.  Perhaps somebody else can take it from
> here.

Looks like all the bits in struct tree_common are used up.

Q: Would it make sense to add a flag to struct tree_decl_common to 
indicate !zero, set it using an attribute, (and automatically in  the 
java front-end for the cases above), and then test for it in tree-vrp.c 
similar to below?

> 
> In any case, here's a patch Diego and I came up with.  It will eliminate
> null-pointer checks related to the string concatenation operator (foo =
> "blah" + bar).
> 
> (Thanks Diego!)
> 
> AG
> 
> 
> 
> 
> ------------------------------------------------------------------------
> 
> Index: tree-vrp.c
> ===================================================================
> --- tree-vrp.c	(revision 106799)
> +++ tree-vrp.c	(working copy)
> @@ -2216,6 +2216,42 @@ infer_value_range (tree stmt, tree op, e
>    if (SSA_NAME_OCCURS_IN_ABNORMAL_PHI (op))
>      return false;
>  
> +  /* Is this a function call that is guaranteed not to
> +     return null?  */
> +  if (TREE_CODE (stmt) == MODIFY_EXPR
> +      && op == TREE_OPERAND (stmt, 0)
> +      && TREE_CODE (TREE_TYPE (stmt)) == POINTER_TYPE
> +      && TREE_CODE (TREE_OPERAND (stmt, 1)) == CALL_EXPR)
> +    {
> +      /* Ok, we know we have an assignment from a function
> +	 call returning a pointer.  Now - for testing purposes
> +	 - I'm just going to hard-code a test for a specific
> +	 java method known not to return null. */
> +      
> +      tree node = TREE_TYPE (TREE_TYPE (stmt));
> +      if (TREE_CODE (node) == RECORD_TYPE
> +	  && TYPE_NAME (node)
> +	  && TREE_CODE (TYPE_NAME (node)) == TYPE_DECL
> +	  && DECL_NAME (TYPE_NAME (node))
> +	  && strcmp (IDENTIFIER_POINTER (DECL_NAME (TYPE_NAME (node))),
> +		     "gnu.gcj.runtime.StringBuffer") == 0)
> +	{
> +	  tree function = 
> +	    TREE_OPERAND (TREE_OPERAND (TREE_OPERAND (stmt, 1), 0), 0);
> +	  
> +	  if (TREE_CODE (function) == FUNCTION_DECL
> +	      && DECL_NAME (function)
> +	      && strcmp (IDENTIFIER_POINTER (DECL_NAME (function)),
> +			 "append") == 0)
> +	    {
> +	      puts ("WOOHOO!");
> +	      *val_p = build_int_cst (TREE_TYPE (op), 0);
> +	      *comp_code_p = NE_EXPR;
> +	      return true;
> +	    }
> +	}
> +    }
> +  
>    /* Similarly, don't infer anything from statements that may throw
>       exceptions.  */
>    if (tree_could_throw_p (stmt))
> @@ -2734,6 +2770,28 @@ find_assert_locations (basic_block bb)
>  	    }
>  	}
>  
> +      /* Some assignments may compute values that guarantee certain
> +	 known ranges to their LHS.  */
> +      FOR_EACH_SSA_TREE_OPERAND (op, stmt, i, SSA_OP_DEF)
> +	{
> +	  tree value;
> +	  enum tree_code comp_code;
> +
> +	  /* If OP is used only once, namely in this STMT, don't
> +	     bother creating an ASSERT_EXPR for it.  */
> +	  if (has_single_use (op))
> +	    continue;
> +
> +	  /* If OP is used in such a way that we can infer a value
> +	     range for it, and we don't find a previous assertion for
> +	     it, create a new assertion location node for OP.  */
> +	  if (infer_value_range (stmt, op, &comp_code, &value))
> +	    {
> +	      register_new_assert_for (op, comp_code, value, bb, NULL, si);
> +	      need_assert = true;
> +	    }
> +	}
> +
>        /* Remember the last statement of the block.  */
>        last = stmt;
>      }

Re: Null pointer check elimination

[Ian Lance Taylor]

David Daney <ddaney@avtrex.com> writes:

> > Eventually we should manually mark certain function DECLs as
> > not-returning-null instead of my kludgy test for this one case.  I don't
> > know if/when I can get to that.  Perhaps somebody else can take it from
> > here.
> 
> Looks like all the bits in struct tree_common are used up.
> 
> Q: Would it make sense to add a flag to struct tree_decl_common to
> indicate !zero, set it using an attribute, (and automatically in  the
> java front-end for the cases above), and then test for it in
> tree-vrp.c similar to below?

This should be done using an attribute, yes.  If this is going to be
tested frequently enough, it would make sense to add a bit to struct
tree_function_decl (I don't see any reason to put it in struct
tree_decl-common) (there is currently room for one more bit in
tree_function_decl on a machine which requires 16-bit alignment, or 17
more bits on a machine which requires 32-bit alignment).  Note that it
is also possible to simply store the attribute on DECL_ATTRIBUTES and
look it up using lookup_attribute.

Ian

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 01:53, Ian Lance Taylor wrote:

> Note that it is also possible to simply store the attribute on
> DECL_ATTRIBUTES and look it up using lookup_attribute.
>
This is my strong preference.  The original RFE (PR 20318) called for 
attributes to be used in C/C++ function declarations.  It would be 
pointless to have to lookup this attributes in two different ways inside 
tree-vrp.c.

Re: Null pointer check elimination

[Daniel Berlin]

On Fri, 2005-11-11 at 22:53 -0800, Ian Lance Taylor wrote:
> David Daney <ddaney@avtrex.com> writes:
> 
> > > Eventually we should manually mark certain function DECLs as
> > > not-returning-null instead of my kludgy test for this one case.  I don't
> > > know if/when I can get to that.  Perhaps somebody else can take it from
> > > here.
> > 
> > Looks like all the bits in struct tree_common are used up.
> > 
> > Q: Would it make sense to add a flag to struct tree_decl_common to
> > indicate !zero, set it using an attribute, (and automatically in  the
> > java front-end for the cases above), and then test for it in
> > tree-vrp.c similar to below?
> 
> This should be done using an attribute, yes.  If this is going to be
> tested frequently enough, it would make sense to add a bit to struct
> tree_function_decl (I don't see any reason to put it in struct
> tree_decl-common) (there is currently room for one more bit in
> tree_function_decl on a machine which requires 16-bit alignment, or 17
> more bits on a machine which requires 32-bit alignment).


Note you could also put things in decl_non_common, but i'd probably beat
you up :)


>   Note that it
> is also possible to simply store the attribute on DECL_ATTRIBUTES and
> look it up using lookup_attribute.

IMHO, this is the way to go.  The number of times we look at attributes
on function_decls (IE through call_expr_flags, etc) is so small i've
never understood why we use so many bits to represent thing we are
getting from attributes.
Most functions have no attributes, so it's a very simple check for
lookup_attribute to perform.  Even when they have *1* attribute, it's
still simple.




> 
> Ian

Re: Null pointer check elimination

[Per Bothner]

A "function-never-returns-null" attribute doesn't seem like
the right mechanism.  Instead, there should be a "never-null"
attribute on pointer types.  A "function-never-returns-null" is
just a function whose return-type has the "never-null" attribute.

A type attribute is much more useful.  For example it allows:
String x = shared ? "x" : new String("x");
// The type of x [in a single-assignment-world] is non-null.

[If we already have such a mechanism, I apologize.]
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 12:05, Per Bothner wrote:
> A "function-never-returns-null" attribute doesn't seem like
> the right mechanism.  Instead, there should be a "never-null"
> attribute on pointer types.  A "function-never-returns-null" is
> just a function whose return-type has the "never-null" attribute.
>
I disagree.  We would have to prove that every possible instance of this 
type is non-NULL.

> A type attribute is much more useful.  For example it allows:
> String x = shared ? "x" : new String("x");
> // The type of x [in a single-assignment-world] is non-null.
>
No.  We don't put our types in SSA form.  Another variable of type String 
could very well be NULL.

Re: Null pointer check elimination

[Andrew Haley]

Diego Novillo writes:
 > On Saturday 12 November 2005 12:05, Per Bothner wrote:
 > > A "function-never-returns-null" attribute doesn't seem like
 > > the right mechanism.  Instead, there should be a "never-null"
 > > attribute on pointer types.  A "function-never-returns-null" is
 > > just a function whose return-type has the "never-null" attribute.
 > >
 > I disagree.  We would have to prove that every possible instance of this 
 > type is non-NULL.

Couldn't we attach an assertion to the tree?  That way we could just
use the inference logic we already have.

Andrew.

Re: Null pointer check elimination

[Laurent GUERBY]

Note that this correspond to the "not null" feature added to Ada 2006
in various places, including pointer type definitions:

   type Ptr is not null access Integer;

You can also have a regular pointer type and subtype it
with not null, but I guess the Ada front-end introduces
a generated subtype:

   type P is access Integer;
   function F return not null P;

The trunk Ada front-end supports this when the -gnat05
flag is used.

Laurent

On Sat, 2005-11-12 at 09:05 -0800, Per Bothner wrote:
> A "function-never-returns-null" attribute doesn't seem like
> the right mechanism.  Instead, there should be a "never-null"
> attribute on pointer types.  A "function-never-returns-null" is
> just a function whose return-type has the "never-null" attribute.
> 
> A type attribute is much more useful.  For example it allows:
> String x = shared ? "x" : new String("x");
> // The type of x [in a single-assignment-world] is non-null.
> 
> [If we already have such a mechanism, I apologize.]

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 12:19, Andrew Haley wrote:

> Couldn't we attach an assertion to the tree?  That way we could just
> use the inference logic we already have.
>
We already do that.  In Per's test case, 

String x = shared ? "x" : new String("x");

we get into VRP with an SSA form along these lines:

if (shared_1)
   x_4 = "x"
else
  {
    x_5 = new String("x");
    x_6 = ASSERT_EXPR <x_5, x_5 != 0>
  }
x_7 = PHI <x_4, x_6>

VRP already knows that "x" is non-NULL.  The new function attribute will 
cause VRP to insert the ASSERT_EXPR for x_5.  VRP will detetermine that 
x_7 is non-NULL.

Re: Null pointer check elimination

[Per Bothner]

Diego Novillo wrote:
> On Saturday 12 November 2005 12:05, Per Bothner wrote:
> 
>>A "function-never-returns-null" attribute doesn't seem like
>>the right mechanism.  Instead, there should be a "never-null"
>>attribute on pointer types.  A "function-never-returns-null" is
>>just a function whose return-type has the "never-null" attribute.
>>
> 
> I disagree.  We would have to prove that every possible instance of this 
> type is non-NULL.

I think you're missing the point.  The proposal is for a "type variant"
-  not that different from say "constant".

"non-null java.lang.String" is a different POINTER_TYPE object than
"[possibly-null] java.lang.String".  If you dereference an expression
whose type is "non-null java.lang.String" then you know you don't need
an null pointer check.  If you derefernce an expression of type
"[possibly-null] java.lang.String" then you do need the null pointer
check.
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/

Re: Null pointer check elimination

[Andrew Haley]

Diego Novillo writes:
 > On Saturday 12 November 2005 12:19, Andrew Haley wrote:
 > 
 > > Couldn't we attach an assertion to the tree?  That way we could just
 > > use the inference logic we already have.
 > >
 > We already do that.  In Per's test case, 
 > 
 > String x = shared ? "x" : new String("x");
 > 
 > we get into VRP with an SSA form along these lines:
 > 
 > if (shared_1)
 >    x_4 = "x"
 > else
 >   {
 >     x_5 = new String("x");
 >     x_6 = ASSERT_EXPR <x_5, x_5 != 0>
 >   }
 > x_7 = PHI <x_4, x_6>
 > 
 > VRP already knows that "x" is non-NULL.  The new function attribute will 
 > cause VRP to insert the ASSERT_EXPR for x_5.  VRP will detetermine that 
 > x_7 is non-NULL.

OK, so what's to stop the front-end from generating the assertion at
gimplification time?  Then we don't need any new attributes in the
middle-end.

Andrew.

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 12:24, Laurent GUERBY wrote:
> Note that this correspond to the "not null" feature added to Ada 2006
> in various places, including pointer type definitions:
>
>    type Ptr is not null access Integer;
>
Ah, this is different and it would be very helpful.  If it's a language 
mandated thing, then VRP could just rely in this type attribute and 
default to 'non-zero' when it can't infer any other useful value.

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 12:27, Per Bothner wrote:

> I think you're missing the point.  The proposal is for a "type variant"
> -  not that different from say "constant".
>
Ah, yes, sorry about that.  Yes, that would be useful as well.  However, 
that is an orthogonal issue to having non-NULL function attributes.  We 
can use both.

If the front end guarantees that all instances of a type are non-NULL, as 
in the Ada case just posted, then VRP can and should make use of that.

Re: Null pointer check elimination

[Laurent GUERBY]

On Sat, 2005-11-12 at 12:30 -0500, Diego Novillo wrote:
> On Saturday 12 November 2005 12:24, Laurent GUERBY wrote:
> > Note that this correspond to the "not null" feature added to Ada 2006
> > in various places, including pointer type definitions:
> >
> >    type Ptr is not null access Integer;
> >
> Ah, this is different and it would be very helpful.  If it's a language 
> mandated thing, then VRP could just rely in this type attribute and 
> default to 'non-zero' when it can't infer any other useful value.

Yes it's language mandated (well when the ISO Ada 2006 revision is out
next year :), my guess is that the Ada front-end remove some of it's own
checks based on this but that this information is not passed outside the
front-end, may be Richard Kenner or Robert Dewar can comment on this.

Laurent

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 12:29, Andrew Haley wrote:
> Diego Novillo writes:
>
>  > if (shared_1)
>  >    x_4 = "x"
>  > else
>  >   {
>  >     x_5 = new String("x");
>  >     x_6 = ASSERT_EXPR <x_5, x_5 != 0>
>  >   }
>  > x_7 = PHI <x_4, x_6>
>  >
>  > VRP already knows that "x" is non-NULL.  The new function attribute
>  > will cause VRP to insert the ASSERT_EXPR for x_5.  VRP will
>  > detetermine that x_7 is non-NULL.
>
> OK, so what's to stop the front-end from generating the assertion at
> gimplification time?  Then we don't need any new attributes in the
> middle-end.
>
The FE is not emitting SSA code.  In 'x = new String("x")', it will know 
that 'x' is non-NULL at that point, but it cannot prove that 'x' will 
remain non-NULL everywhere.  When you are in SSA form, x_6 is non-NULL and 
everywhere you see x_6 you are guaranteed to be dealing with a non-NULL 
value.

The helpful hint we need from the FE inside VRP is for it to mark the 
actual call as returning non-NULL.

Re: Null pointer check elimination

[Gabriel Dos Reis]

Per Bothner <per@bothner.com> writes:

| A "function-never-returns-null" attribute doesn't seem like
| the right mechanism.  Instead, there should be a "never-null"
| attribute on pointer types.  A "function-never-returns-null" is
| just a function whose return-type has the "never-null" attribute.

We already have such mechanism: a reference type -- which morally is
implemented as a pointer type.

-- Gaby

Re: Null pointer check elimination

[Gabriel Dos Reis]

Diego Novillo <dnovillo@redhat.com> writes:

| On Saturday 12 November 2005 12:05, Per Bothner wrote:
| > A "function-never-returns-null" attribute doesn't seem like
| > the right mechanism.  Instead, there should be a "never-null"
| > attribute on pointer types.  A "function-never-returns-null" is
| > just a function whose return-type has the "never-null" attribute.
| >
| I disagree.  We would have to prove that every possible instance of this 
| type is non-NULL.

No, you don't have to.  Just in the same way you don't have to prove
that a function with "function-never-returns-null" attributes never
returns null.

-- Gaby

Re: Null pointer check elimination

[Gabriel Dos Reis]

Diego Novillo <dnovillo@redhat.com> writes:

| On Saturday 12 November 2005 12:27, Per Bothner wrote:
| 
| > I think you're missing the point.  The proposal is for a "type variant"
| > -  not that different from say "constant".
| >
| Ah, yes, sorry about that.  Yes, that would be useful as well.  However, 
| that is an orthogonal issue to having non-NULL function attributes.  We 
| can use both.

I'm not convinced.  I believe Per's suggestion is far superior, and
more general and does cover pretty well the issue at hand.  Plus,
a pointer-type-without-null is another spelling for reference type.

-- Gaby

Re: Null pointer check elimination

[Andrew Pinski]

> 
> Per Bothner <per@bothner.com> writes:
> 
> | A "function-never-returns-null" attribute doesn't seem like
> | the right mechanism.  Instead, there should be a "never-null"
> | attribute on pointer types.  A "function-never-returns-null" is
> | just a function whose return-type has the "never-null" attribute.
> 
> We already have such mechanism: a reference type -- which morally is
> implemented as a pointer type.

That was mentioned a way ago as being wrong.  A reference type can be NULL.

-- Pinski

Re: Null pointer check elimination

[Paul Brook]

On Saturday 12 November 2005 18:32, Gabriel Dos Reis wrote:
> Per Bothner <per@bothner.com> writes:
> | A "function-never-returns-null" attribute doesn't seem like
> | the right mechanism.  Instead, there should be a "never-null"
> | attribute on pointer types.  A "function-never-returns-null" is
> | just a function whose return-type has the "never-null" attribute.
>
> We already have such mechanism: a reference type

No. We've had this discussion before, and the conclusion what that reference 
types can be NULL.

http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html

Paul

Re: Null pointer check elimination

[Per Bothner]

Per Bothner  wrote:
>A "function-never-returns-null" attribute doesn't seem like
> the right mechanism.  Instead, there should be a "never-null"
> attribute on pointer types.  A "function-never-returns-null" is
> just a function whose return-type has the "never-null" attribute.

Gabriel Does Reis wrote:
>We already have such mechanism: a reference type -- which morally is
>implemented as a pointer type.

Andrew Pinski wrote:
> That was mentioned a way ago as being wrong.  A reference type can be NULL.

There are other differences, at least in C++: If you assign to a
pointer, you change the pointer, while if you assign to a reference
you modify the referenced object.  I.e. if a variable has reference
type, then the reference itself is constant.
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 13:36, Gabriel Dos Reis wrote:

> I'm not convinced.  I believe Per's suggestion is far superior, and
> more general and does cover pretty well the issue at hand.  Plus,
> a pointer-type-without-null is another spelling for reference type.
>
I'm thinking of C here, where we don't have that luxury.  The original RFE 
was in 20318 where they have some C functions that are guaranteed to 
return non-NULL (I'm quoting from memory here):

int *this_never_returns_NULL (void)  __attribute__ ((never_returns_null));

We would not want to pin the never-null attribute to 'int *':

foo()
{
   int *p = this_never_returns_NULL ();
   < ... use p without modifying it ... >	<-- p is never NULL here.	
   p = other_fn ();
   < ... use p without modifying it ... >	<-- p may be NULL here.
}

In languages where you could make the type itself have that guarantee, then 
great, let's use the type attributes.  In type-challenged languages, we 
use whatever we can get our hands on.

Re: Null pointer check elimination

[Per Bothner]

Diego Novillo wrote:
 > int *this_never_returns_NULL (void)  __attribute__ 
((never_returns_null));
 >
 > We would not want to pin the never-null attribute to 'int *':

Well, of course.  That's why we're talking about a type *variant*.

To emphasise: this is a type variant *in the gcc internals* - i.e.
using a distinct POINTER_TYPE node.  To what extent this is reflected
at the source level is up to front-ends.

Thus:
int *this_never_returns_NULL(void) __attribute__((never_returns_null));

could be viewed as syntactic sugar for:

(int __attribute__((never_null)) *) this_never_returns_NULL(void);

[Note I'm unsure about __attribute__ and declaration syntax, so it
is possible this wouldn't work.  But that's a syntax issue, so it ignore
it in the following.]

 >
 > foo()
 > {
 >    int *p = this_never_returns_NULL ();
 >    < ... use p without modifying it ... > <-- p is never NULL here.	
 >    p = other_fn ();
 >    < ... use p without modifying it ... >	<-- p may be NULL here.
 > }

We could allow, if desired:
foo()
{
    int __attribute__((never_null)) *p = this_never_returns_NULL ();
    < ... use p without modifying it ... > <-- p is never NULL here.	
    p = other_fn (); /* error - caught by the compiler */
}

Consider:
foo()
{
    int *p;
    if (test)
      {
        p = this_never_returns_NULL ();
        < ... use p without modifying it ... >	<-- p never NULL here.
      }
    else
     {	
       p = other_fn ();
       < ... use p without modifying it ... >	<-- p may be NULL here.
     }
    ... more uses of p ...;
}

The internal SSA form might be something like:

foo()
{
    if (test)
      {
        int __attribute__((never_null)) *p_1 = this_never_returns_NULL();
        < ... use p without modifying it ... >	<-- p_1 never NULL here.
      }
    else
     {	
       int *p_2 = other_fn ();
       < ... use p without modifying it ... > <-- p_2 may be NULL here.
     }
   int *p_3 = PHI(p_1, p_2);
    ... more uses of p ...;
}
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/

Re: Null pointer check elimination

[Tom Tromey]

>>>>> "Per" == Per Bothner <per@bothner.com> writes:

Per> A type attribute is much more useful.  For example it allows:
Per> String x = shared ? "x" : new String("x");
Per> // The type of x [in a single-assignment-world] is non-null.

I think we will need extra code to recognize that String references
via the constant pool will never be null.

Since we make direct references to the constant pool (i.e., we don't
emit a function call), a purely function-call-based approach to
handling non-nullity won't be sufficient.

Tom

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 14:35, Per Bothner wrote:

> The internal SSA form might be something like:
>
> foo()
> {
>     if (test)
>       {
>         int __attribute__((never_null)) *p_1 =
> this_never_returns_NULL(); < ... use p without modifying it ... >	<--
> p_1 never NULL here. }
>     else
>      {
>        int *p_2 = other_fn ();
>        < ... use p without modifying it ... > <-- p_2 may be NULL here.
>      }
>    int *p_3 = PHI(p_1, p_2);
>     ... more uses of p ...;
> }
>
Well, I am not an FE person, so I don't much care how you convey the 
information into the optimizers.

From a user's perspective I see the obvious drawback that you've just 
forced me to edit a potentially large number of source files just to add 
the __attribute__((never_null)).  The other approach just needs a single 
__attribute__ in the function declaration.

Another problem I would have as a user is if you suddenly make 'int *' and 
'int * __attribute__((non_null))' different/incompatible types.  If I have 
a function that takes 'int *' as argument, I don't want to start adding 
tons of type casts to get around compiler warnings/errors.

From an optimizer perspective, I fail to see how would your approach give 
me better information inside VRP.  But since your approach seems to give 
me the same information, I don't much care how the FE implements this.  If 
you decide to have type attributes, I'll use it.  If you mark the 
function, I'll use it with the same effect.

Re: Null pointer check elimination

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| > 
| > Per Bothner <per@bothner.com> writes:
| > 
| > | A "function-never-returns-null" attribute doesn't seem like
| > | the right mechanism.  Instead, there should be a "never-null"
| > | attribute on pointer types.  A "function-never-returns-null" is
| > | just a function whose return-type has the "never-null" attribute.
| > 
| > We already have such mechanism: a reference type -- which morally is
| > implemented as a pointer type.
| 
| That was mentioned a way ago as being wrong.  A reference type can be NULL.

You have to explain me why a reference can be null.

-- Gaby

Re: Null pointer check elimination

[Gabriel Dos Reis]

Paul Brook <paul@codesourcery.com> writes:

| On Saturday 12 November 2005 18:32, Gabriel Dos Reis wrote:
| > Per Bothner <per@bothner.com> writes:
| > | A "function-never-returns-null" attribute doesn't seem like
| > | the right mechanism.  Instead, there should be a "never-null"
| > | attribute on pointer types.  A "function-never-returns-null" is
| > | just a function whose return-type has the "never-null" attribute.
| >
| > We already have such mechanism: a reference type
| 
| No. We've had this discussion before, and the conclusion what that reference 
| types can be NULL.
| 
| http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html

That simply means GCC got it wrong. 

-- Gaby

Re: Null pointer check elimination

[Gabriel Dos Reis]

Diego Novillo <dnovillo@redhat.com> writes:

| On Saturday 12 November 2005 13:36, Gabriel Dos Reis wrote:
| 
| > I'm not convinced.  I believe Per's suggestion is far superior, and
| > more general and does cover pretty well the issue at hand.  Plus,
| > a pointer-type-without-null is another spelling for reference type.
| >
| I'm thinking of C here, where we don't have that luxury.

I know you're thinking of C. But we're talking about implementatin
here.  We have the luxury to -- and we must -- introduce types that
are not expressible at the pure C source level.  

-- Gaby

Re: Null pointer check elimination

[Andrew Pinski]

> 
> Paul Brook <paul@codesourcery.com> writes:
> 
> | On Saturday 12 November 2005 18:32, Gabriel Dos Reis wrote:
> | > Per Bothner <per@bothner.com> writes:
> | > | A "function-never-returns-null" attribute doesn't seem like
> | > | the right mechanism.  Instead, there should be a "never-null"
> | > | attribute on pointer types.  A "function-never-returns-null" is
> | > | just a function whose return-type has the "never-null" attribute.
> | >
> | > We already have such mechanism: a reference type
> | 
> | No. We've had this discussion before, and the conclusion what that reference 
> | types can be NULL.
> | 
> | http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html
> 
> That simply means GCC got it wrong. 


Was there an example of:


int f(int &);

int g(void)
{
  int *a = 0;
  return f(*a);
}


Yes this would be undefined code but so what.

-- Pinski

Re: Null pointer check elimination

[Per Bothner]

Diego Novillo wrote:
>From a user's perspective I see the obvious drawback that you've just 
> forced me to edit a potentially large number of source files just to add 
> the __attribute__((never_null)).

I'm clearly not explaining myself ...

Of course I'm not proposing that.   My point was that my proposal
*allows* explicit setting of the __attribute__((never_null)).  But
more likely it's the *compiler* (optimizer) that sets the attribute.

> The other approach just needs a single 
> __attribute__ in the function declaration.

You missed this
 > int *this_never_returns_NULL(void) __attribute__((never_returns_null));
 > could be viewed as syntactic sugar for:
 > (int __attribute__((never_null)) *) this_never_returns_NULL(void);

I.e. just a single attribute in the function declaration.
The phrase "syntactic sugar" means that people can write the former,
and it's equivalent to the latter.

> Another problem I would have as a user is if you suddenly make 'int *' and 
> 'int * __attribute__((non_null))' different/incompatible types.  If I have 
> a function that takes 'int *' as argument, I don't want to start adding 
> tons of type casts to get around compiler warnings/errors.

Bad example.  The 'int *' type is more general than
'int*__attribute__((non_null))', so assigning an expression that
has type 'int*__attribute__((non_null))' to a variable or parameter
that has type 'int*' is always safe, and shouldn't warn.

As to the other way round, that is a user interface issue, orthognal to
the semantic issue.  But if a variable is explicitly declared
'int * __attribute__((non_null))' and you pass it an 'int *' expression
then a warning is probably in order, since you're doing something dangerous.

One more point:  If someone writes:
   int *x = this_never_returns_NULL();
Then the type of x is 'int *' and that of this_never_returns_NULL()
is 'int __attribute__((never_null)) *'.  This is fine and safe.
However, ideally the compiler should realize that x actually has
the more specific type 'int __attribute__((never_null)) *', and
should use that information to generate better code.  It seems
this should be straightforward using SSA, as I sketched in my
previous message.
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/

Re: Null pointer check elimination

[Per Bothner]

Tom Tromey wrote:
>>>>>>"Per" == Per Bothner <per@bothner.com> writes:
> 
> 
> Per> A type attribute is much more useful.  For example it allows:
> Per> String x = shared ? "x" : new String("x");
> Per> // The type of x [in a single-assignment-world] is non-null.
> 
> I think we will need extra code to recognize that String references
> via the constant pool will never be null.
> 
> Since we make direct references to the constant pool (i.e., we don't
> emit a function call), a purely function-call-based approach to
> handling non-nullity won't be sufficient.

Right - the "type-variant" approach handles that smoothly.
I.e. in Java a string literal would have type
"never-null pointer to java.lang.String".
-- 
	--Per Bothner
per@bothner.com   http://per.bothner.com/

Re: Null pointer check elimination

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| Was there an example of:
| 
| 
| int f(int &);
| 
| int g(void)
| {
|   int *a = 0;
|   return f(*a);
| }
| 
| 
| Yes this would be undefined code but so what.

So it is NOT a compeling example that a reference can be null.  You
have to try harder, Andrew.

-- Gaby

Re: Null pointer check elimination

[Paul Brook]

On Saturday 12 November 2005 20:57, Gabriel Dos Reis wrote:
> Paul Brook <paul@codesourcery.com> writes:
> | On Saturday 12 November 2005 18:32, Gabriel Dos Reis wrote:
> | > Per Bothner <per@bothner.com> writes:
> | > | A "function-never-returns-null" attribute doesn't seem like
> | > | the right mechanism.  Instead, there should be a "never-null"
> | > | attribute on pointer types.  A "function-never-returns-null" is
> | > | just a function whose return-type has the "never-null" attribute.
> | >
> | > We already have such mechanism: a reference type
> |
> | No. We've had this discussion before, and the conclusion what that
> | reference types can be NULL.
> |
> | http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html
>
> That simply means GCC got it wrong.

If by "GCC got it wrong" you mean several key GCC developers disagree with 
your opinion of what the semantics of REFERENCE_TYPE are/should be, then yes.

Paul

Re: Null pointer check elimination

[Gabriel Dos Reis]

Paul Brook <paul@codesourcery.com> writes:

| On Saturday 12 November 2005 20:57, Gabriel Dos Reis wrote:
| > Paul Brook <paul@codesourcery.com> writes:
| > | On Saturday 12 November 2005 18:32, Gabriel Dos Reis wrote:
| > | > Per Bothner <per@bothner.com> writes:
| > | > | A "function-never-returns-null" attribute doesn't seem like
| > | > | the right mechanism.  Instead, there should be a "never-null"
| > | > | attribute on pointer types.  A "function-never-returns-null" is
| > | > | just a function whose return-type has the "never-null" attribute.
| > | >
| > | > We already have such mechanism: a reference type
| > |
| > | No. We've had this discussion before, and the conclusion what that
| > | reference types can be NULL.
| > |
| > | http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html
| >
| > That simply means GCC got it wrong.
| 
| If by "GCC got it wrong" you mean several key GCC developers disagree with 
| your opinion

Do you need to get it personal?

| of what the semantics of REFERENCE_TYPE are/should be, then yes.

See, it is not a semantics I made up.  Even people arguing for null
reference recognize it is undefined behaviour.

-- Gaby

Re: Null pointer check elimination

[Andrew Pinski]

> | of what the semantics of REFERENCE_TYPE are/should be, then yes.
> 
> See, it is not a semantics I made up.  Even people arguing for null
> reference recognize it is undefined behaviour.

With C++ yes but not with Fortran where there are optional arguments.

So What you are saying is that Fortran should not use reference types.
Well in fortran, all agruments are passed via a reference so that is just
wrong.  Using pointers there would be just wrong, as that is not the
semantics for the variable.

-- Pinski

Re: Null pointer check elimination

[Diego Novillo]

On Saturday 12 November 2005 16:11, Per Bothner wrote:

> I'm clearly not explaining myself ...
>
Well, it doesn't help that I'm not really good at language stuff, so don't 
worry and thanks for putting up with the silly questions.

> However, ideally the compiler should realize that x actually has
> the more specific type 'int __attribute__((never_null)) *', and
> should use that information to generate better code.  It seems
> this should be straightforward using SSA, as I sketched in my
> previous message.
>
Aha, yes, that's fine then.

I'll defer the decision of type vs function attribute to you folks.  
However you end up marking it, that will only mean a couple line change in 
VRP.

Re: Null pointer check elimination

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| > | of what the semantics of REFERENCE_TYPE are/should be, then yes.
| > 
| > See, it is not a semantics I made up.  Even people arguing for null
| > reference recognize it is undefined behaviour.
| 
| With C++ yes but not with Fortran where there are optional arguments.

Then what is the difference between a pointer type and a reference type?

| So What you are saying is that Fortran should not use reference types.

No.  What I'm saying is that the use of "reference" to model
optional arguments needs more work in terms of explanation and
justification. 

| Well in fortran, all agruments are passed via a reference so that is just
| wrong.  Using pointers there would be just wrong, as that is not the
| semantics for the variable.

So, what is the semantics?  What is the real difference?

-- Gaby

Re: Null pointer check elimination

[Paul Brook]

> | Well in fortran, all agruments are passed via a reference so that is just
> | wrong.  Using pointers there would be just wrong, as that is not the
> | semantics for the variable.
>
> So, what is the semantics?  What is the real difference?

Did you actually read the thread I referenced?

The short answer is debug info.

Paul

Re: Null pointer check elimination

[Andrew Pinski]

> 
> Andrew Pinski <pinskia@physics.uc.edu> writes:
> 
> | > | of what the semantics of REFERENCE_TYPE are/should be, then yes.
> | > 
> | > See, it is not a semantics I made up.  Even people arguing for null
> | > reference recognize it is undefined behaviour.
> | 
> | With C++ yes but not with Fortran where there are optional arguments.
> 
> Then what is the difference between a pointer type and a reference type?

To the middle-end nothing, to the debugging info there is something.


> | Well in fortran, all agruments are passed via a reference so that is just
> | wrong.  Using pointers there would be just wrong, as that is not the
> | semantics for the variable.
> 
> So, what is the semantics?  What is the real difference?

The semantics for reference type to the middle-end is no different from a pointer
type, it is only when printing out what the debug info should include.


Let me ask you this, how would represent agruments for Fortran then as pointers
but then we get much worse debug info as we get currently?


GCC is not a C++ play ground.


-- Pinski

Re: Null pointer check elimination

[Gabriel Dos Reis]

Paul Brook <paul@codesourcery.com> writes:

| > | Well in fortran, all agruments are passed via a reference so that is just
| > | wrong.  Using pointers there would be just wrong, as that is not the
| > | semantics for the variable.
| >
| > So, what is the semantics?  What is the real difference?
| 
| Did you actually read the thread I referenced?

Yes, I did.  Why are you willing to assume I did not?

| The short answer is debug info.

You see, I asked for semantics at the language level, you answer "side
implementation detail".  Yet, you're willing to jump to the conclusion
that I did not read the thread.

-- Gaby

Re: Null pointer check elimination

[Gabriel Dos Reis]

Andrew Pinski <pinskia@physics.uc.edu> writes:

| > 
| > Andrew Pinski <pinskia@physics.uc.edu> writes:
| > 
| > | > | of what the semantics of REFERENCE_TYPE are/should be, then yes.
| > | > 
| > | > See, it is not a semantics I made up.  Even people arguing for null
| > | > reference recognize it is undefined behaviour.
| > | 
| > | With C++ yes but not with Fortran where there are optional arguments.
| > 
| > Then what is the difference between a pointer type and a reference type?
| 
| To the middle-end nothing,

That is why GCC got it wrong.

[...]

| GCC is not a C++ play ground.

?

-- Gaby

Re: Null pointer check elimination

[Richard Guenther]

On 13 Nov 2005 02:00:08 +0100, Gabriel Dos Reis
<gdr@integrable-solutions.net> wrote:
> Andrew Pinski <pinskia@physics.uc.edu> writes:
>
> | >
> | > Andrew Pinski <pinskia@physics.uc.edu> writes:
> | >
> | > | > | of what the semantics of REFERENCE_TYPE are/should be, then yes.
> | > | >
> | > | > See, it is not a semantics I made up.  Even people arguing for null
> | > | > reference recognize it is undefined behaviour.
> | > |
> | > | With C++ yes but not with Fortran where there are optional arguments.
> | >
> | > Then what is the difference between a pointer type and a reference type?
> |
> | To the middle-end nothing,
>
> That is why GCC got it wrong.

And this is why there seemed to be consensus to merge the two in the
middle-end and preserve debug-info somehow differently.  Like with
a "frontend type-id" on the decl.  That would allow lowering of f.i.
integral types to their modes at some point, too.

Richard.

(blue)
> [...]
>
> | GCC is not a C++ play ground.
>
> ?
>
> -- Gaby
>
>

Re: Null pointer check elimination

[Robert Dewar]

Richard Guenther wrote:

> And this is why there seemed to be consensus to merge the two in the
> middle-end and preserve debug-info somehow differently.  Like with
> a "frontend type-id" on the decl.  That would allow lowering of f.i.
> integral types to their modes at some point, too.

It seems a clear mistake to me to tie debug information so closely
to the actual gcc type information, and this is another example
of it causing unnecessary trouble.

Re: Null pointer check elimination

[Joe Buck]

On Sun, Nov 13, 2005 at 04:29:26AM -0500, Robert Dewar wrote:
> Richard Guenther wrote:
> 
> >And this is why there seemed to be consensus to merge the two in the
> >middle-end and preserve debug-info somehow differently.  Like with
> >a "frontend type-id" on the decl.  That would allow lowering of f.i.
> >integral types to their modes at some point, too.
> 
> It seems a clear mistake to me to tie debug information so closely
> to the actual gcc type information, and this is another example
> of it causing unnecessary trouble.

It seems that there are two separate attributes that distinguish reference
types from pointer types ...

1) auto-dereferencing: debuggers interpret a.field, where a is a
   reference, as dereference(a).field.  This is a feature that both
   C++ and Fortran want.

2) in C++, references are assumed never to be null.  My Fortran is very
   rusty (I wrote vast amounts of Fortran in the 80s, but those brain
   cells are mostly gone), but I had naively assumed that the same was
   true in Fortran-land, however there appear to be some cases where it
   is not true.  But even in Fortran, it seems there are many cases where
   we know that references cannot be null.

(There may be other implicit attributes as well).

Maybe the middle end should only have one pointer type, but with at
least two attributes, one to tell the debugger to auto-dereference,
one to mark those pointers that cannot point to null.  This might enable
more optimization.

Re: Null pointer check elimination

[Joe Buck]

On Sat, Nov 12, 2005 at 04:01:07PM -0500, Andrew Pinski wrote:
> Was there an example of:
> 
> int f(int &);
> 
> int g(void)
> {
>   int *a = 0;
>   return f(*a);
> }
> 
> 
> Yes this would be undefined code but so what.

In a case like this, gcc could emit an error (since we can already
detect that a reference is always initialized to a null pointer).
If it did so, I can almost guarantee that some free software package
will be flagged (I recall writing such code myself 10+ years ago, before I
knew better), but it still might be a good thing.

Of course, it's not hard to hide the fact that a reference is null from
the compiler, and the compiler might then do optimizations based on the
assumption that the argument to f is a non-null reference.  That would
be valid according to the standard.

Re: Null pointer check elimination

[Joe Buck]

On Sat, Nov 12, 2005 at 10:47:33AM -0800, Per Bothner wrote:
> Per Bothner  wrote:
> >A "function-never-returns-null" attribute doesn't seem like
> >the right mechanism.  Instead, there should be a "never-null"
> >attribute on pointer types.  A "function-never-returns-null" is
> >just a function whose return-type has the "never-null" attribute.
> 
> Gabriel Does Reis wrote:
> >We already have such mechanism: a reference type -- which morally is
> >implemented as a pointer type.
> 
> Andrew Pinski wrote:
> >That was mentioned a way ago as being wrong.  A reference type can be NULL.
> 
> There are other differences, at least in C++: If you assign to a
> pointer, you change the pointer, while if you assign to a reference
> you modify the referenced object.  I.e. if a variable has reference
> type, then the reference itself is constant.

That's two separate features: the first is about how the source code
is interpreted (and that corresponds to informing the debugger that
the object is auto-dereferenced).  The second corresponds to declaring
that a pointer is itself const.

So a C++ reference could be represented as a middle-end pointer type,
provided that it is marked as auto-dereferencing, never null, and
constant.

Re: Null pointer check elimination

[Michael N. Moran]

Joe Buck wrote:
> On Sat, Nov 12, 2005 at 04:01:07PM -0500, Andrew Pinski wrote:
> 
>>Was there an example of:
>>
>>int f(int &);
>>
>>int g(void)
>>{
>>  int *a = 0;
>>  return f(*a);
>>}
>>
>>
>>Yes this would be undefined code but so what.
> 
> 
> In a case like this, gcc could emit an error (since we can already
> detect that a reference is always initialized to a null pointer).
> If it did so, I can almost guarantee that some free software package
> will be flagged (I recall writing such code myself 10+ years ago, before I
> knew better), but it still might be a good thing.
> 
> Of course, it's not hard to hide the fact that a reference is null from
> the compiler, and the compiler might then do optimizations based on the
> assumption that the argument to f is a non-null reference.  That would
> be valid according to the standard.

Excuse me. IANALL nor am I a compiler expert but ...
what kind of optimization might be done with the information
that a reference *should* never be null? Especially within
the server code (the implementation of "int f(int& a)" in this case.)

Perhaps incorrectly, but I tend to use a (C++) reference when I
require the caller/client to supply a non-null "pointer" to a
single object (as opposed to an array of objects.) Client code
is free to dereference a pointer to an object (perhaps allocated
in the heap) and invoke the operation.

And what is the meaning of code that does this:

int foo(int& a)
{
     int*    b = &a;

     if(b ==0)
     {
         a();
     }
     else
     {
         b();
     }
}

Not that this example makes any sense, nor would
I intentionally code this way ... but...

Is function a() invoked?
Is function b() invoked?

Or (most likely) am I just one of those people
that hasn't groked the subtleties of the C++ standard
despite having used it for more years than I care to
remember ;-)


-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Joe Buck]

On Mon, Nov 14, 2005 at 01:43:38PM -0500, Michael N. Moran wrote:
> Excuse me. IANALL nor am I a compiler expert but ...
> what kind of optimization might be done with the information
> that a reference *should* never be null? Especially within
> the server code (the implementation of "int f(int& a)" in this case.)

There are several examples.  One is converting from a derived class
to a base class when there is multiple inheritance.  An offset must
be subtracted, unless it is a null pointer.

Another is the "delete" operator.  It must first check that the
argument is null; it only calls the underlying memory allocator if it is
not.

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

| And what is the meaning of code that does this:
| 
| int foo(int& a)
| {
|      int*    b = &a;
| 
|      if(b ==0)
|      {
|          a();
|      }
|      else
|      {
|          b();
|      }

According to the standard, the compiler can assume that the test is
always false, therefore rewrite the if-else as an unconditional call to
b().  GCC already does some null-pointer check deleting.

-- Gaby

Re: Null pointer check elimination

[Michael N. Moran]

Joe Buck wrote:
> On Mon, Nov 14, 2005 at 01:43:38PM -0500, Michael N. Moran wrote:
> 
>>Excuse me. IANALL nor am I a compiler expert but ...
>>what kind of optimization might be done with the information
>>that a reference *should* never be null? Especially within
>>the server code (the implementation of "int f(int& a)" in this case.)
> 
> 
> There are several examples.  One is converting from a derived class
> to a base class when there is multiple inheritance.  An offset must
> be subtracted, unless it is a null pointer.

Why does it matter if the pointer is null? It is an error
in the program if it uses the result, but the same is true for
using null pointers. Do we try to do something if the reference
is to another invalid address (e.g. 0x01)?

Do we want to hide the error by not crashing? Why not just do the
math and keep running? This seems like a run-time check that
is not a part of the C/C++ language as I understand it.

> Another is the "delete" operator.  It must first check that the
> argument is null; it only calls the underlying memory allocator if it is
> not.

I have a similar problem with this.

Neither of these appear to be optimizations. As far as I know
there is nothing that requires an implementation to do this kind
of run-time checking even if we are dealing with pointers instead
of references.

Of course ... I *could* be wrong ;-)

Perhaps I am not understanding (most likely), but I am still
interested... Sorry if I'm just way off course.

-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Michael N. Moran]

Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> 
> | And what is the meaning of code that does this:
> | 
> | int foo(int& a)
> | {
> |      int*    b = &a;
> | 
> |      if(b ==0)
> |      {
> |          a();
> |      }
> |      else
> |      {
> |          b();
> |      }
> 
> According to the standard, the compiler can assume that the test is
> always false, therefore rewrite the if-else as an unconditional call to
> b().  GCC already does some null-pointer check deleting.

Wow. I'm sure there is sound reasoning for this ... but I can't
understand what that might be given a client module could intentionally
(if ill-adviseadly) simply invoke the function:

void bar()
{
     int*  z=0;
     foo(*z);
}

In short this is "surprising" to clearly under-informed me.

-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

[...]

| Do we want to hide the error by not crashing? Why not just do the
| math and keep running? This seems like a run-time check that
| is not a part of the C/C++ language as I understand it.

defined by which standards?

-- Gaby

Re: Null pointer check elimination

[Michael N. Moran]

Joe Buck wrote:
> On Mon, Nov 14, 2005 at 01:43:38PM -0500, Michael N. Moran wrote:
> 
>>Excuse me. IANALL nor am I a compiler expert but ...
>>what kind of optimization might be done with the information
>>that a reference *should* never be null? Especially within
>>the server code (the implementation of "int f(int& a)" in this case.)
> 
> 
> There are several examples.  One is converting from a derived class
> to a base class when there is multiple inheritance.  An offset must
> be subtracted, unless it is a null pointer.
> 
> Another is the "delete" operator.  It must first check that the
> argument is null; it only calls the underlying memory allocator if it is
> not.

It's also surprising to me that the delete operator can
be used on a reference when the new operator returns a pointer
and the only way to get that (possibly null) pointer to be
used as a reference is to dereference it and then apply
delete on the pointer formed by the address-of operator on
the resulting reference....

void buzz(Abc& b)
{
     delete &b;
}

void baz()
{
     Abc& a = * new Abc();
     buzz(a);
}

-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

| Gabriel Dos Reis wrote:
| > "Michael N. Moran" <mike@mnmoran.org> writes:
| > | And what is the meaning of code that does this:
| > | | int foo(int& a)
| > | {
| > |      int*    b = &a;
| > | |      if(b ==0)
| > |      {
| > |          a();
| > |      }
| > |      else
| > |      {
| > |          b();
| > |      }
| > According to the standard, the compiler can assume that the test is
| > always false, therefore rewrite the if-else as an unconditional call to
| > b().  GCC already does some null-pointer check deleting.
| 
| Wow. I'm sure there is sound reasoning for this ... but I can't
| understand what that might be given a client module could intentionally
| (if ill-adviseadly) simply invoke the function:

then it gets what it deserves.  Check out GCC manual for null-pointer
check.

-- Gaby

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

| Joe Buck wrote:
| > On Mon, Nov 14, 2005 at 01:43:38PM -0500, Michael N. Moran wrote:
| >
| >>Excuse me. IANALL nor am I a compiler expert but ...
| >>what kind of optimization might be done with the information
| >>that a reference *should* never be null? Especially within
| >>the server code (the implementation of "int f(int& a)" in this case.)
| > There are several examples.  One is converting from a derived class
| > to a base class when there is multiple inheritance.  An offset must
| > be subtracted, unless it is a null pointer.
| > Another is the "delete" operator.  It must first check that the
| > argument is null; it only calls the underlying memory allocator if it is
| > not.
| 
| It's also surprising to me that the delete operator can
| be used on a reference when the new operator returns a pointer
| and the only way to get that (possibly null) pointer to be
| used as a reference is to dereference it and then apply
| delete on the pointer formed by the address-of operator on
| the resulting reference....
| 
| void buzz(Abc& b)
| {
|      delete &b;
| }
| 
| void baz()
| {
|      Abc& a = * new Abc();

If no memory is available, the new-expression throws an exception so
the dereference never occurs.  Check out C++ manuals.

-- Gaby

Re: Null pointer check elimination

[Michael N. Moran]

Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> 
> [...]
> 
> | Do we want to hide the error by not crashing? Why not just do the
> | math and keep running? This seems like a run-time check that
> | is not a part of the C/C++ language as I understand it.
> 
> defined by which standards?

At this point, I am entirely out of my league. As I said in
my initial post, IANALL, I am simply one who has lurked on this
list for years because of my interest in GCC as it applies to
C/C++ .

I freely admit to my ignorance on issues of the standards, but
this behavior is surprising to me.

You guys do a great job, and I depend on your compiler. I *want*
GCC to be standards compliant, so I am not complaining. Its just
that given the systems programming roots of C/C++ and the "you don't
pay for what you don't use" and the "least surprise" maxims, I
feel a bit confused.

Sorry, I'll shut-up or go complain to the standards bodies
... yikes! ;-)


-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Michael N. Moran]

Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> | void buzz(Abc& b)
> | {
> |      delete &b;
> | }
> | 
> | void baz()
> | {
> |      Abc& a = * new Abc();
> 
> If no memory is available, the new-expression throws an exception so
> the dereference never occurs.  Check out C++ manuals.

As a systems programmer (embedded), I frequently use "-fno-exceptions".
What behavior can I expect under these circumstances?


-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Michael N. Moran]

Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> | Wow. I'm sure there is sound reasoning for this ... but I can't
> | understand what that might be given a client module could intentionally
> | (if ill-adviseadly) simply invoke the function:
> 
> then it gets what it deserves.  Check out GCC manual for null-pointer
> check.

 From info gcc:

`-fdelete-null-pointer-checks'
      Use global dataflow analysis to identify and eliminate useless
      checks for null pointers.  The compiler assumes that dereferencing
      a null pointer would have halted the program.  If a pointer is
      checked after it has already been dereferenced, it cannot be null.

The second sentence makes me question the difference between an
actual dereferencing operation and the use of a dereferencing
operator used to convert a pointer to a C++ reference. Clearly
(to me anyway ;-) the conversion case does not actually cause
an access to the object.


-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

| Gabriel Dos Reis wrote:
| > "Michael N. Moran" <mike@mnmoran.org> writes:
| > | void buzz(Abc& b)
| > | {
| > |      delete &b;
| > | }
| > | | void baz()
| > | {
| > |      Abc& a = * new Abc();
| > If no memory is available, the new-expression throws an exception so
| > the dereference never occurs.  Check out C++ manuals.
| 
| As a systems programmer (embedded), I frequently use "-fno-exceptions".
| What behavior can I expect under these circumstances?

You have to manually check the return value of new.  There is no
substitute for that.  At least, if you don't want to invoke that kind
of undefined behaviour.

-- Gaby

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

| Gabriel Dos Reis wrote:
| > "Michael N. Moran" <mike@mnmoran.org> writes:
| > | Wow. I'm sure there is sound reasoning for this ... but I can't
| > | understand what that might be given a client module could intentionally
| > | (if ill-adviseadly) simply invoke the function:
| > then it gets what it deserves.  Check out GCC manual for null-pointer
| > check.
| 
|  From info gcc:
| 
| `-fdelete-null-pointer-checks'
|       Use global dataflow analysis to identify and eliminate useless
|       checks for null pointers.  The compiler assumes that dereferencing
|       a null pointer would have halted the program.  If a pointer is
|       checked after it has already been dereferenced, it cannot be null.
| 
| The second sentence makes me question the difference between an
| actual dereferencing operation and the use of a dereferencing
| operator used to convert a pointer to a C++ reference. Clearly
| (to me anyway ;-) the conversion case does not actually cause
| an access to the object.

It is not a conversion. It is a dereference operation that is defined
only for non-null operand.  No ifs, no buts.

-- Gaby

Re: Null pointer check elimination

[Michael N. Moran]

Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> 
> | Gabriel Dos Reis wrote:
> | > "Michael N. Moran" <mike@mnmoran.org> writes:
> | > | void buzz(Abc& b)
> | > | {
> | > |      delete &b;
> | > | }
> | > | | void baz()
> | > | {
> | > |      Abc& a = * new Abc();
> | > If no memory is available, the new-expression throws an exception so
> | > the dereference never occurs.  Check out C++ manuals.
> | 
> | As a systems programmer (embedded), I frequently use "-fno-exceptions".
> | What behavior can I expect under these circumstances?
> 
> You have to manually check the return value of new.  There is no
> substitute for that.  At least, if you don't want to invoke that kind
> of undefined behaviour.

Fine. I must relent and remain surprised.
Going back to the root of this discussion, however:

| Joe Buck wrote:
| > Another is the "delete" operator.  It must first check that the
| > argument is null; it only calls the underlying memory allocator
| > if it is not.

I would simply expect the underlying memory allocator to be
invoked regardless of whether or not a pointer was null, but
honestly, in my line of work I rarely use the delete operator.


-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Michael N. Moran]

Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> |  From info gcc:
> | 
> | `-fdelete-null-pointer-checks'
> |       Use global dataflow analysis to identify and eliminate useless
> |       checks for null pointers.  The compiler assumes that dereferencing
> |       a null pointer would have halted the program.  If a pointer is
> |       checked after it has already been dereferenced, it cannot be null.
> | 
> | The second sentence makes me question the difference between an
> | actual dereferencing operation and the use of a dereferencing
> | operator used to convert a pointer to a C++ reference. Clearly
> | (to me anyway ;-) the conversion case does not actually cause
> | an access to the object.
> 
> It is not a conversion. It is a dereference operation that is defined
> only for non-null operand.  No ifs, no buts.

I'm in over my head, but ... (oops there's a but ;-) here goes:

void bar(int& a);

void foo(int* a)
{
     // dereference: conversion to reference
     // Since there is not necessarily any object access,
     // thus no assured SEGFAULT.
     bar(*a);

     // dereference: access to object
     // If a is null, then SEGFAULT
     *a	= 0;
}

Sorry to drag this out. I'm sure its just one of those
"that's the way the language is defined Moran get over it"
issues, but (no ifs) ...

-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

| Gabriel Dos Reis wrote:
| > "Michael N. Moran" <mike@mnmoran.org> writes:
| > |  From info gcc:
| > | | `-fdelete-null-pointer-checks'
| > |       Use global dataflow analysis to identify and eliminate useless
| > |       checks for null pointers.  The compiler assumes that dereferencing
| > |       a null pointer would have halted the program.  If a pointer is
| > |       checked after it has already been dereferenced, it cannot be null.
| > | | The second sentence makes me question the difference between an
| > | actual dereferencing operation and the use of a dereferencing
| > | operator used to convert a pointer to a C++ reference. Clearly
| > | (to me anyway ;-) the conversion case does not actually cause
| > | an access to the object.
| > It is not a conversion. It is a dereference operation that is defined
| > only for non-null operand.  No ifs, no buts.
| 
| I'm in over my head, but ... (oops there's a but ;-) here goes:
| 
| void bar(int& a);
| 
| void foo(int* a)
| {
|      // dereference: conversion to reference
|      // Since there is not necessarily any object access,
|      // thus no assured SEGFAULT.
|      bar(*a);

SEGFAULT is not a behaviour defined by the language.  It is *just* one
form of undefined behaviour.  If you execute that function, it might
reformat your harddrive and that woud be fine -- though I know of no
compiler that does that on purpose.  But, the point is that your
program in erring in the outer space.

|      // dereference: access to object
|      // If a is null, then SEGFAULT
|      *a	= 0;

Again, that may or may not happen. 

| }
| 
| Sorry to drag this out. I'm sure its just one of those
| "that's the way the language is defined Moran get over it"
| issues, but (no ifs) ...

Indeed.

-- Gaby

Re: Null pointer check elimination

[Janis Johnson]

On Mon, Nov 14, 2005 at 11:56:16PM +0100, Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> SEGFAULT is not a behaviour defined by the language.  It is *just* one
> form of undefined behaviour.  If you execute that function, it might
> reformat your harddrive and that woud be fine -- though I know of no
> compiler that does that on purpose.  But, the point is that your
> program in erring in the outer space.
> 
> |      // dereference: access to object
> |      // If a is null, then SEGFAULT
> |      *a	= 0;
> 
> Again, that may or may not happen. 

Some operating systems load a page of zeroes at address zero, so the
dereference of a null pointer has no visible effect; a different form
of undefined behavior.  DYNIX/ptx did that by default, and I think
that HP-UX does it.  I much prefer a segfault.

Janis

Re: Null pointer check elimination

[Michael N. Moran]

Gabriel Dos Reis wrote:
> "Michael N. Moran" <mike@mnmoran.org> writes:
> | void bar(int& a);
> | 
> | void foo(int* a)
> | {
> |      // dereference: conversion to reference
> |      // Since there is not necessarily any object access,
> |      // thus no assured SEGFAULT.
> |      bar(*a);
> 
> SEGFAULT is not a behaviour defined by the language.  

Even *I* know that, in spite of my lack of legal expertise.

> It is *just* one form of undefined behaviour.  

Are you saying that this portion of the code *will*
invoke undefined behavior even if the pointer "a"
is valid?

Notice this example has nothing to do with null
pointers. It is a demonstration of the two kinds
of dereferences that I identified.

Perhaps the problem is that I am assuming the same
object code generated by this function is used for
all cases (e.g. null or valid values of "a",) and
that assumption falls apart in the presence of
optimizations such as inlining and inter procedural
optimizations.

> If you execute that function, it might
> reformat your harddrive and that woud be fine -- though I know of no
> compiler that does that on purpose.  But, the point is that your
> program in erring in the outer space.
> 
> |      // dereference: access to object
> |      // If a is null, then SEGFAULT
> |      *a	= 0;
> 
> Again, that may or may not happen. 

I understand that specifically a SEGFAULT may not happen,
but according to the excerpt from the GCC info page above,

"The compiler assumes that dereferencing a null pointer
would have halted the program."

In the first case, the result of the dereferencing *seems*
to be an address of the object in the form of a reference,
whereas the second case *seems* to clearly modify the object
(assuming the object is in memory ... whatever that means in
standardise).

<sigh>
FWIW, I appreciate your help, and realize that this is not
the forum for this kind of discussion. I apparently need to
get educated . Thank you for your patience.

-- 
Michael N. Moran           (h) 770 516 7918
5009 Old Field Ct.         (c) 678 521 5460
Kennesaw, GA, USA 30144    http://mnmoran.org

"So often times it happens, that we live our lives in chains
  and we never even know we have the key."
The Eagles, "Already Gone"

The Beatles were wrong: 1 & 1 & 1 is 1

Re: Null pointer check elimination

[Gabriel Dos Reis]

"Michael N. Moran" <mike@mnmoran.org> writes:

| Gabriel Dos Reis wrote:
| > "Michael N. Moran" <mike@mnmoran.org> writes:
| > | void bar(int& a);
| > | | void foo(int* a)
| > | {
| > |      // dereference: conversion to reference
| > |      // Since there is not necessarily any object access,
| > |      // thus no assured SEGFAULT.
| > |      bar(*a);
| > SEGFAULT is not a behaviour defined by the language.
| 
| Even *I* know that, in spite of my lack of legal expertise.

It is not really a matter of legal expertise.  It is just hard to pin
down where you're driving at.

| > It is *just* one form of undefined behaviour.
| 
| Are you saying that this portion of the code *will*
| invoke undefined behavior even if the pointer "a"
| is valid?

I'm saying that if you call foo with a null pointer, you get into
undefined behaviour territory.  And GCC is founded to make
optimization based on that. And you -- as a user -- generally don't
know how and when GCC can apply that assumption.  And it is already
doing so in known cases; it may do more in the future.  I don't want
to go and give a long list of the specific cases; there is no point in
it. The transformation is general and will be applied where the
opportunity arises.  Just don't count on dereferencing a null pointer
to result you or not result in a segfault in general.

-- Gaby

Re: Null pointer check elimination

[David Daney]

Gabriel Dos Reis wrote:
> I'm saying that if you call foo with a null pointer, you get into
> undefined behaviour territory.  And GCC is founded to make
> optimization based on that. And you -- as a user -- generally don't
> know how and when GCC can apply that assumption.  And it is already
> doing so in known cases; it may do more in the future.  I don't want
> to go and give a long list of the specific cases; there is no point in
> it. The transformation is general and will be applied where the
> opportunity arises.  Just don't count on dereferencing a null pointer
> to result you or not result in a segfault in general.

Perhaps not in general, but one unstated premise of this whole thread is 
that for some GCC targets (most Unix like operating systems) you *can* 
count on a SIGSEGV when you dereference a null pointer.  The java front 
end takes advantage of this fact to eliminate explicit checks for 
dereferencing of null pointers.

The Java Language Specification requires that NullPointerExceptions are 
thrown when calling a method via a null 'this'.  But since a method call 
does not usually involve dereferencing 'this', an explicit check for 
null must be made when it cannot be proven that 'this' is not null.  The 
original point of this thread was that some of these explicit checks may 
be eliminated based on a priori knowledge about the behavior of certain 
standard library methods.

Which leads me to the (unrelated) thought that inserting an instruction 
that dereferences the pointer may be more efficient (from a code size 
point of view) than an explicit check for null and then branching around 
  the code that creates and throws the exception.

David Daney

Java on uClinux (was: Null pointer check elimination)

[Bernd Schmidt]

David Daney wrote:
> Perhaps not in general, but one unstated premise of this whole thread is 
> that for some GCC targets (most Unix like operating systems) you *can* 
> count on a SIGSEGV when you dereference a null pointer.  The java front 
> end takes advantage of this fact to eliminate explicit checks for 
> dereferencing of null pointers.

Oh.

Speaking of which, has anyone ported gcj to a MMU-less uClinux platform yet?


Bernd

Re: Java on uClinux (was: Null pointer check elimination)

[Andrew Haley]

Bernd Schmidt writes:
 > David Daney wrote:
 > > Perhaps not in general, but one unstated premise of this whole thread is 
 > > that for some GCC targets (most Unix like operating systems) you *can* 
 > > count on a SIGSEGV when you dereference a null pointer.  The java front 
 > > end takes advantage of this fact to eliminate explicit checks for 
 > > dereferencing of null pointers.
 > 
 > Oh.
 > 
 > Speaking of which, has anyone ported gcj to a MMU-less uClinux platform yet?

It's impossible with the current config.  This is because some of
libgcj is written on C++, and the C++ compiler FE does not insert
checks for null pointer accesses.  I wrote a small patch to do this
but it was rejected.

Andrew.

Re: Java on uClinux

[Bernd Schmidt]

Andrew Haley wrote:
> Bernd Schmidt writes:
>  > David Daney wrote:
>  > > Perhaps not in general, but one unstated premise of this whole thread is 
>  > > that for some GCC targets (most Unix like operating systems) you *can* 
>  > > count on a SIGSEGV when you dereference a null pointer.  The java front 
>  > > end takes advantage of this fact to eliminate explicit checks for 
>  > > dereferencing of null pointers.
>  > 
>  > Oh.
>  > 
>  > Speaking of which, has anyone ported gcj to a MMU-less uClinux platform yet?
> 
> It's impossible with the current config.  This is because some of
> libgcj is written on C++, and the C++ compiler FE does not insert
> checks for null pointer accesses.  I wrote a small patch to do this
> but it was rejected.

Hmm, we can trap null pointer accesses, but I don't think we deliver 
reliable SIGSEGV signals yet or provide a means of getting the faulting 
address.  If that was fixed, is there anything obvious that stands in 
the way of a uClinux/uClibc port?


Bernd

Re: Java on uClinux

[Andrew Haley]

Bernd Schmidt writes:
 > Andrew Haley wrote:
 > > Bernd Schmidt writes:
 > >  > David Daney wrote:
 > >  > > Perhaps not in general, but one unstated premise of this whole thread is 
 > >  > > that for some GCC targets (most Unix like operating systems) you *can* 
 > >  > > count on a SIGSEGV when you dereference a null pointer.  The java front 
 > >  > > end takes advantage of this fact to eliminate explicit checks for 
 > >  > > dereferencing of null pointers.
 > >  > 
 > >  > Oh.
 > >  > 
 > >  > Speaking of which, has anyone ported gcj to a MMU-less uClinux platform yet?
 > > 
 > > It's impossible with the current config.  This is because some of
 > > libgcj is written on C++, and the C++ compiler FE does not insert
 > > checks for null pointer accesses.  I wrote a small patch to do this
 > > but it was rejected.
 > 
 > Hmm, we can trap null pointer accesses, but I don't think we deliver 
 > reliable SIGSEGV signals yet or provide a means of getting the faulting 
 > address.  If that was fixed, is there anything obvious that stands in 
 > the way of a uClinux/uClibc port?

I don't think so.  The only other dependency we have is POSIX threads.

Andrew.

Re: Null pointer check elimination

[Tom Tromey]

>>>>> "David" == David Daney <ddaney@avtrex.com> writes:

David> The Java Language Specification requires that NullPointerExceptions
David> are thrown when calling a method via a null 'this'.  But since a
David> method call does not usually involve dereferencing 'this', an explicit
David> check for null must be made when it cannot be proven that 'this' is
David> not null.

Note that on ports where we rely on SEGV generation on a null pointer
dereference, we actually only emit these explicit checks for calls to
final methods (and methods in final classes).  That's because plain
old virtual calls do require a dereference.  (This is all detailed
at length in the PR for this issue..)

David> Which leads me to the (unrelated) thought that inserting an
David> instruction that dereferences the pointer may be more efficient (from
David> a code size point of view) than an explicit check for null and then
David> branching around the code that creates and throws the exception.

I remember writing a patch that did this, a long time ago.  But I
don't recall why we didn't do it.  Note that the branch in this
question should always be marked 'unlikely' by GCC, as it is a branch
to an exception handler.  And, we ordinarily must load the value
anyway since we're going to pass it as 'this' to the method call...
so perhaps the cost is low.

On MMU-less ports the situation is different.  There, we emit a lot
of null pointer checks.

Tom

Re: Java on uClinux (was: Null pointer check elimination)

[Tom Tromey]

>>>>> "Andrew" == Andrew Haley <aph@redhat.com> writes:

Bernd> Speaking of which, has anyone ported gcj to a MMU-less uClinux
Bernd> platform yet?

Andrew> It's impossible with the current config.  This is because some of
Andrew> libgcj is written on C++, and the C++ compiler FE does not insert
Andrew> checks for null pointer accesses.

I prefer to think of these ports as degraded, not impossible.  You
won't get NPEs in all situations, due to how we wrote the CNI code.
(This could be fixed, of course, but motivation is low.)  Well-behaved
code will still work fine.

We've done plenty of ports to MMU-less systems in the past.  In fact
the first port was to a MIPS platform with no MMU, no threads (we used
a "qthreads" package based on setjmp), no I/O, etc.  This is still
possible in theory, though probably bits of configury have rotted over
time out of disuse.  (Though I think Anthony does builds like this
from time to time, doesn't he?)

Tom

Re: Java on uClinux (was: Null pointer check elimination)

[Andrew Haley]

Tom Tromey writes:
 > >>>>> "Andrew" == Andrew Haley <aph@redhat.com> writes:
 > 
 > Bernd> Speaking of which, has anyone ported gcj to a MMU-less uClinux
 > Bernd> platform yet?
 > 
 > Andrew> It's impossible with the current config.  This is because some of
 > Andrew> libgcj is written on C++, and the C++ compiler FE does not insert
 > Andrew> checks for null pointer accesses.
 > 
 > I prefer to think of these ports as degraded, not impossible.

Can we agree on "broken" ?

Andrew.

Re: Null pointer check elimination

[Joe Buck]

On Mon, Nov 14, 2005 at 04:16:43PM -0800, Janis Johnson wrote:
> On Mon, Nov 14, 2005 at 11:56:16PM +0100, Gabriel Dos Reis wrote:
> > "Michael N. Moran" <mike@mnmoran.org> writes:
> > SEGFAULT is not a behaviour defined by the language.  It is *just* one
> > form of undefined behaviour.  If you execute that function, it might
> > reformat your harddrive and that woud be fine -- though I know of no
> > compiler that does that on purpose.  But, the point is that your
> > program in erring in the outer space.
> > 
> > |      // dereference: access to object
> > |      // If a is null, then SEGFAULT
> > |      *a	= 0;
> > 
> > Again, that may or may not happen. 
> 
> Some operating systems load a page of zeroes at address zero, so the
> dereference of a null pointer has no visible effect; a different form
> of undefined behavior.  DYNIX/ptx did that by default, and I think
> that HP-UX does it.  I much prefer a segfault.

(I'm about to reveal just how old I am).

Actually, there was a time when this was just the way C worked: you
got the tape from Bell Labs and ran it on your PDP-11, and people wrote
C programs that relied on *NULL returning an all-zero object (sometimes
by accident).  Every C implementation in the world worked this way
at one time.  It was the same on early VAX BSD releases, and then a
linker option was added to decide whether the zero page was all-zero or
inaccessible, and then SEGV became the default but the option (of an
all-zero page) was still needed to make old software work.

(We're talking 1980-82 time frame here).

Re: Null pointer check elimination

[Mike Stump]

On Nov 14, 2005, at 11:36 PM, David Daney wrote:
> Perhaps not in general, but one unstated premise of this whole  
> thread is that for some GCC targets (most Unix like operating  
> systems) you *can* count on a SIGSEGV when you dereference a null  
> pointer.

Unless that null pointer points to an object that is of the wrong  
size (too large), such as an array or a structure.

Re: Null pointer check elimination

[Paolo Bonzini]

>> There are several examples.  One is converting from a derived class
>> to a base class when there is multiple inheritance.  An offset must
>> be subtracted, unless it is a null pointer.
> 
> Why does it matter if the pointer is null? It is an error
> in the program if it uses the result, but the same is true for
> using null pointers.

No, because for example if the base class is passed to a function as an 
argument, you want that function to be able to distinguish if its 
argument is a NULL pointer.

>> Another is the "delete" operator.  It must first check that the
>> argument is null; it only calls the underlying memory allocator if it is
>> not.
> 
> I have a similar problem with this.

... for example, if you pass the base class to delete, it must detect 
that it is a NULL pointer and not invoke undefined behavior.

In other words, something like this (untested) program

#include <iostream>

class A { int x, y; };
class B : virtual public A { int z, w; };
class C : virtual public A { int j, k; };
class D : virtual public B, C { };

void f(A *a)
{
   if (a == NULL)
     std::cout << "a is NULL, but it works the same!\n";

   delete a;
}

void g(D *d)
{
   f (static_cast <A *> (d));
}

int main(void)
{
   g (NULL);
}

must work.  operator delete must not try to free the NULL pointer, and 
the message should be displayed.

Paolo

Re: Null pointer check elimination

[David Daney]

Mike Stump wrote:
> On Nov 14, 2005, at 11:36 PM, David Daney wrote:
> 
>> Perhaps not in general, but one unstated premise of this whole  thread 
>> is that for some GCC targets (most Unix like operating  systems) you 
>> *can* count on a SIGSEGV when you dereference a null  pointer.
> 
> 
> Unless that null pointer points to an object that is of the wrong  size 
> (too large), such as an array or a structure.

The java front end ignores this case.  I mean what are the chances that 
someone would try to access something near the end of such an object 
with out first trying to access something near the beginning of it?

IIRC, in java an object can only have 2^16 fields, so if the maximum 
field size is 8 bytes (a reference), That means you only have to keep 
the first 2^19 bytes unmapped.  For arrays, we would generally have to 
examine the 'length' field before any other access, and it would be near 
the beginning also.

I think that in practice the os/runtime linker will leave a piece of the 
address space much larger than 2^19 unmapped.


David Daney

Re: Null pointer check elimination

[Richard Henderson]

On Sat, Nov 12, 2005 at 09:57:10PM +0100, Gabriel Dos Reis wrote:
> | http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html
> 
> That simply means GCC got it wrong. 

The world is not all C++, Gaby.


r~

Re: Null pointer check elimination

[Gabriel Dos Reis]

Richard Henderson <rth@redhat.com> writes:

| On Sat, Nov 12, 2005 at 09:57:10PM +0100, Gabriel Dos Reis wrote:
| > | http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html
| > 
| > That simply means GCC got it wrong. 
| 
| The world is not all C++, Gaby.

But that wasn't the point.

-- Gaby

Re: Null pointer check elimination

[Joe Buck]

On Wed, Nov 16, 2005 at 09:15:33PM +0100, Gabriel Dos Reis wrote:
> Richard Henderson <rth@redhat.com> writes:
> 
> | On Sat, Nov 12, 2005 at 09:57:10PM +0100, Gabriel Dos Reis wrote:
> | > | http://gcc.gnu.org/ml/gcc-patches/2004-08/msg01463.html
> | > 
> | > That simply means GCC got it wrong. 
> | 
> | The world is not all C++, Gaby.
> 
> But that wasn't the point.

While not all the world is C++, GCC should be able to correctly represent
the constraints on C++ references, in a way that's general enough for use
in other languages.  I think this discussion has already produced some
progress on that front.

Re: Java on uClinux

[Bernd Schmidt]

Andrew Haley wrote:
> Bernd Schmidt writes:

>  > Hmm, we can trap null pointer accesses, but I don't think we deliver 
>  > reliable SIGSEGV signals yet or provide a means of getting the faulting 
>  > address.  If that was fixed, is there anything obvious that stands in 
>  > the way of a uClinux/uClibc port?
> 
> I don't think so.  The only other dependency we have is POSIX threads.

Ok, thanks.  Assuming I get around to porting them, where do I submit 
libffi/boehm_gc changes?  Is there an upstream version to worry about?


Bernd

Re: Java on uClinux

[Andrew Pinski]

> 
> Andrew Haley wrote:
> > Bernd Schmidt writes:
> 
> >  > Hmm, we can trap null pointer accesses, but I don't think we deliver 
> >  > reliable SIGSEGV signals yet or provide a means of getting the faulting 
> >  > address.  If that was fixed, is there anything obvious that stands in 
> >  > the way of a uClinux/uClibc port?
> > 
> > I don't think so.  The only other dependency we have is POSIX threads.
> 
> Ok, thanks.  Assuming I get around to porting them, where do I submit 
> libffi/boehm_gc changes?  Is there an upstream version to worry about?

There is an upsteam for beohm_gc (Boehm himself).

For libffi, unoffficially GCC is the maintainer.

-- Pinski

Re: Java on uClinux

[Eric Botcazou]

> There is an upsteam for beohm_gc (Boehm himself).

Yes, but you usually can modify the local copy and simply CC Hans.

-- 
Eric Botcazou

RE: Null pointer check elimination

[Boehm, Hans]

> From: David Daney
> Sent: Tuesday, November 15, 2005 11:44 AM
> To: Mike Stump
> Cc: gcc@gcc.gnu.org; java@gcc.gnu.org
> Subject: Re: Null pointer check elimination
> 
> 
> Mike Stump wrote:
> > On Nov 14, 2005, at 11:36 PM, David Daney wrote:
> > 
> >> Perhaps not in general, but one unstated premise of this whole  
> >> thread
> >> is that for some GCC targets (most Unix like operating  
> systems) you 
> >> *can* count on a SIGSEGV when you dereference a null  pointer.
> > 
> > 
> > Unless that null pointer points to an object that is of the wrong  
> > size
> > (too large), such as an array or a structure.
> 
> The java front end ignores this case.  I mean what are the 
> chances that 
> someone would try to access something near the end of such an object 
> with out first trying to access something near the beginning of it?
If the code is malicious, probably about 100%.

It seems to me that we probably do want a solid guarantee here
eventually.  As David wrote later, we probably already have one on most
platforms.

The libjava GC code also currently makes some weaker assumptions along
these lines.  It believes that none of the GC heap resides at addresses
below 16K (see _Jv_AllocArray in boehm.cc).  But that's more of a
performance than correctness issue.

Hans

Re: Null pointer check elimination

[Richard Kenner]

    Maybe the middle end should only have one pointer type, but with at
    least two attributes, one to tell the debugger to auto-dereference,
    one to mark those pointers that cannot point to null.  This might
    enable more optimization.

That would certainly be my recommendation.  It would also get rid of the
TYPE_REFERENCE_TO field in types, which would save space.

We originally had at most one POINTER_TYPE and at most one REFERENCE_TYPE
pointing at each type.  But that changed with code (partly mine) that allowed
for a sort of "variant" of pointers, so that they could have a different mode
and a "deref aliases all" flag.  Added the suggested flags would just be an
extension of this, would eliminate the question of "what's the difference
between POINTER_TYPE and REFERENCE_TYPE" once and for all, and would simplify
some code.  Because build_reference_type would still exist, front end changes
would be minimized.

Re: Null pointer check elimination

[Diego Novillo]

On Sunday 13 November 2005 08:23, Richard Kenner wrote:
>     > A "function-never-returns-null" attribute doesn't seem like
>     > the right mechanism.  Instead, there should be a "never-null"
>     > attribute on pointer types.  A "function-never-returns-null" is
>     > just a function whose return-type has the "never-null" attribute.
>
>     I disagree.  We would have to prove that every possible instance of
> this type is non-NULL.
>
> I thought the idea being proposed was a flag on a type where we were
> *asserting* that all objects of that type were non-NULL, not where we
> have to prove it.  Such types do exist at the language level for some
> languages.
>
Yeah, check the rest of the thread.  I had originally missed that point.  
To summarize, either marking the function or marking its type is the same 
from my point of view.  Both approaches give the optimizers the exact same 
information.

So, I will leave it up to the FE folks to figure out how they want to mark 
the non-NULL attribute.