Re: Ada files now checked in

Re: Ada files now checked in

[dewar]

<<$ gcc -Wuninitialized -ftree-ssa foo.c -O -c
foo.c: In function `main':
foo.c:3: warning: `b' is used uninitialized in this function
>>

Right, I know about those messages, the trouble is that the message
does not point to the problem point, it points instead to the declaration
of b. What you need in more complex cases is a pointer to the exact
occurrence that is detected as potentially troublesome

Re: Ada files now checked in

[Diego Novillo]

On Sat, 06 Oct 2001, dewar@gnat.com wrote:

> <<$ gcc -Wuninitialized -ftree-ssa foo.c -O -c
> foo.c: In function `main':
> foo.c:3: warning: `b' is used uninitialized in this function
> >>
> 
> Right, I know about those messages, the trouble is that the message
> does not point to the problem point, it points instead to the declaration
> of b. What you need in more complex cases is a pointer to the exact
> occurrence that is detected as potentially troublesome
>
No, this is based on the new tree SSA infrastructure (BTW, I had
cut&pasted the wrong output in my inital message).

This will always point to the line with a use of an uninitialized
variable:

-----------------------------------------------------------------------------
$ cat rdefs.c
main()
{
  int a, b;

  a = b + 4;
  if (a > 0)
    b = b + 3;
}

$ gcc -Wuninitialized -ftree-ssa rdefs.c -O -c
rdefs.c: In function `main':
rdefs.c:5: warning: `b' is used uninitialized in this function
rdefs.c:7: warning: `b' is used uninitialized in this function
-----------------------------------------------------------------------------

As I said, I'm still debugging this work, but the basic
infrastructure is already in the AST branch.


Diego.

Re: Ada files now checked in

[Zack Weinberg]

On Sun, Oct 07, 2001 at 03:34:42AM -0400, Diego Novillo wrote:
> $ gcc -Wuninitialized -ftree-ssa rdefs.c -O -c
> rdefs.c: In function `main':
> rdefs.c:5: warning: `b' is used uninitialized in this function
> rdefs.c:7: warning: `b' is used uninitialized in this function
> -----------------------------------------------------------------------------
> 
> As I said, I'm still debugging this work, but the basic
> infrastructure is already in the AST branch.

Extremely cool.  That will make finding missing initializations much
easier.

Maybe you could change the warning message to "...used uninitialized
here" or "at this point" or something like that?  Just to be clear
it's not the same old "somewhere in the function" message.

I notice it says "_is_ used uninitialized".  Does that mean you've
eliminated the old false positive problems?

How expensive is it to calculate these?  It'd be nice if we could
generate the warnings with optimization off; that's always been a wart.

zw

Re: Ada files now checked in

[Diego Novillo]

On Sun, 07 Oct 2001, Zack Weinberg wrote:
> Maybe you could change the warning message to "...used uninitialized
> here" or "at this point" or something like that?  Just to be clear
> it's not the same old "somewhere in the function" message.
> 
Sure.


> I notice it says "_is_ used uninitialized".  Does that mean you've
> eliminated the old false positive problems?
> 
That's the intent.  The new code still spews out false positives,
that's what I'm now working on.

The analysis depends on the computation of reaching definitions.
Prior to computing the SSA form, we insert ghost definitions for
every symbol in the entry basic block.  After reaching
definitions, we traverse all the variable use references in the
function.  For every use:

- if its only reaching definition is the ghost def, the variable
  *is* used uninitialized.

- if one of its reaching definitions is the ghost def, the
  variable *may be* used uninitialized.

That's a very simplified view that will give you lots of false
positives (variables with its address taken, global variables,
etc).  I'm refining the criteria with each bootstrap.

Also, I'm about to add def-def chains to model non-killing
definitions like:

1: int a, b *p;
2: 
3: a = 4;
4: *p = 3;
5: b = a + 1;

The use of a at line 5 may be reached by the definitions of *p
and a at lines 4 and 3, respectively.  But this part is nowhere
near ready.


> How expensive is it to calculate these?> 
The analysis itself is relatively cheap once you have computed
the SSA form and reaching definitions of the function. It's
roughly O(SxR) where S is the number of symbols and R the number
of symbol references in the function.

Computing the SSA form is not cheap, but can be improved.
Essentially you need to:

- Build the flowgraph.  That's roughly linear in the number of
  statement tree nodes.

- Find all the variable references in the function.  Linear in
  the total number of tree nodes.

- Compute the SSA form.  This involves computing immediate
  dominators and dominance frontiers.  I believe the algorithms
  we have in GCC are quite quick, but I haven't really looked.

  Building the FUD chains is like O(SxNxE) (could be wrong, I'm
  quoting from memory).  There is a linear phi placing algorithm
  which I plan to switch to.

I want to hook-up all the tree SSA passes to -ftime-report.  That
will give us a better idea of how expensive this really is.

> It'd be nice if we could generate the warnings with
> optimization off; that's always been a wart.
>
Definitiely possible.  We only need to make -Wuninitialized
trigger -ftree-ssa.


Diego.

better -Wuninitialized (Re: Ada files now checked in)

[Zack Weinberg]

On Sun, Oct 07, 2001 at 01:21:01PM -0400, Diego Novillo wrote:
> On Sun, 07 Oct 2001, Zack Weinberg wrote:
> > Maybe you could change the warning message to "...used uninitialized
> > here" or "at this point" or something like that?  Just to be clear
> > it's not the same old "somewhere in the function" message.
> > 
> Sure.

Thanks.

> > I notice it says "_is_ used uninitialized".  Does that mean you've
> > eliminated the old false positive problems?
> > 
> That's the intent.  The new code still spews out false positives,
> that's what I'm now working on.
> 
> The analysis depends on the computation of reaching definitions.
> Prior to computing the SSA form, we insert ghost definitions for
> every symbol in the entry basic block.  After reaching
> definitions, we traverse all the variable use references in the
> function.  For every use:
> 
> - if its only reaching definition is the ghost def, the variable
>   *is* used uninitialized.
> 
> - if one of its reaching definitions is the ghost def, the
>   variable *may be* used uninitialized.
...

I'm not too familiar with reaching definitions, do they take control
dependencies into account?

It would often be helpful if an uninitialized variable could be
automatically set to a "poison" value by the compiler.  This would
prevent one major cause of hard-to-find context-dependent bugs.  It
sounds like this can easily be implemented by emitting real code for
the ghost definitions; dead code elimination would then zap it in all
cases where there isn't a problem.  Have you considered this?

> Also, I'm about to add def-def chains to model non-killing
> definitions like:
> 
> 1: int a, b *p;
> 2: 
> 3: a = 4;
> 4: *p = 3;
> 5: b = a + 1;
> 
> The use of a at line 5 may be reached by the definitions of *p
> and a at lines 4 and 3, respectively.  But this part is nowhere
> near ready.

Hmmm... since p itself is not initialized, it seems like you'd want to
complain about it and then assume it doesn't alias anything. 

> - Compute the SSA form.  This involves computing immediate
>   dominators and dominance frontiers.  I believe the algorithms
>   we have in GCC are quite quick, but I haven't really looked.

If I remember correctly we are using the state-of-the-art algorithm,
but its use of sbitmaps may cause problems.  (looking at ssa.c - dunno
if the same code is used for trees).

> > It'd be nice if we could generate the warnings with
> > optimization off; that's always been a wart.
> >
> Definitiely possible.  We only need to make -Wuninitialized
> trigger -ftree-ssa.

Cool.

zw

Re: better -Wuninitialized (Re: Ada files now checked in)

[Joseph S. Myers]

On Sun, 7 Oct 2001, Zack Weinberg wrote:

> > Definitiely possible.  We only need to make -Wuninitialized
> > trigger -ftree-ssa.
> 
> Cool.

Would -ftree-ssa ever affect code generation?  It seems a bad idea for
warning options to change code generation at all.

-- 
Joseph S. Myers
jsm28@cam.ac.uk

Re: better -Wuninitialized (Re: Ada files now checked in)

[Diego Novillo]

On Sun, 07 Oct 2001, Joseph S. Myers wrote:

> On Sun, 7 Oct 2001, Zack Weinberg wrote:
> 
> > > Definitiely possible.  We only need to make -Wuninitialized
> > > trigger -ftree-ssa.
> > 
> > Cool.
> 
> Would -ftree-ssa ever affect code generation?  It seems a bad idea for
> warning options to change code generation at all.
> 
No.  It only builds the analysis framework (flowgraph, data
references,  SSA web, reaching defs, reached uses, etc).

Diego.

Re: better -Wuninitialized (Re: Ada files now checked in)

[Diego Novillo]

On Sun, 07 Oct 2001, Zack Weinberg wrote:

> > - if its only reaching definition is the ghost def, the variable
> >   *is* used uninitialized.
> > 
> > - if one of its reaching definitions is the ghost def, the
> >   variable *may be* used uninitialized.
> ...
> 
> I'm not too familiar with reaching definitions, do they take control
> dependencies into account?
> 
Yes, that's what the SSA form is for:

1	  int a, b;
2	
3	  b = foo();
4	  if (b < 100)
5	    a = 10;
6	  b = b + a;

SSA will place a phi-term for A after line 5 (the first block
outisde the if-statement).  This will be a phi-term with two
arguments, one for the definition of A at line 5 and the other
for the ghost definition at line 0: phi(A) = (def(A,5), def(A, 0)).

When computing reaching definitions, the algorithm follows all
the use-def chains for every use.  The use of A at line 6 is
reached by that phi-term.  Following the phi-term arguments takes
you to def(A,5) and def(A,0).

So, you end up with the set {def(A,5), def(A,0)} as the set of
reaching definitions for A at line 6.  Since one of them is the
ghost definition, that use *may be* use uninitialized.


> It would often be helpful if an uninitialized variable could be
> automatically set to a "poison" value by the compiler.  This would
> prevent one major cause of hard-to-find context-dependent bugs.  It
> sounds like this can easily be implemented by emitting real code for
> the ghost definitions; dead code elimination would then zap it in all
> cases where there isn't a problem.  Have you considered this?
> 
Not really.  But it is definitely doable.  The only problem is
what to consider a 'poison' value.  OTOH, if the compiler is
already warning you that you're using the thing uninitialized,
why would you also need this run-time trick?


> > Also, I'm about to add def-def chains to model non-killing
> > definitions like:
> > 
> > 1: int a, b *p;
> > 2: 
> > 3: a = 4;
> > 4: *p = 3;
> > 5: b = a + 1;
> > 
> > The use of a at line 5 may be reached by the definitions of *p
> > and a at lines 4 and 3, respectively.  But this part is nowhere
> > near ready.
> 
> Hmmm... since p itself is not initialized, it seems like you'd want to
> complain about it and then assume it doesn't alias anything. 
> 
Hmm, I should've initialized p in the example.  But good point.
This would've given you a warning for *p.  De-referencing a
pointer is a use of the pointer and a def of every variable in
its equivalence set.  In this case, we could empty the
equivalence set if p is used uninitialized.



> > - Compute the SSA form.  This involves computing immediate
> >   dominators and dominance frontiers.  I believe the algorithms
> >   we have in GCC are quite quick, but I haven't really looked.
> 
> If I remember correctly we are using the state-of-the-art algorithm,
> but its use of sbitmaps may cause problems.  (looking at ssa.c - dunno
> if the same code is used for trees).
> 
In tree SSA we call calculate_dominance_info and
compute_dominance_frontiers directly.  Also, the code uses
sbitmaps quite frequently.  The bitmaps are typically
O(n_basic_blocks).  What problem are you referring to?


Diego.

Re: better -Wuninitialized (Re: Ada files now checked in)

[Zack Weinberg]

On Sun, Oct 07, 2001 at 02:21:31PM -0400, Diego Novillo wrote:
> On Sun, 07 Oct 2001, Zack Weinberg wrote:
> 
> > > - if its only reaching definition is the ghost def, the variable
> > >   *is* used uninitialized.
> > > 
> > > - if one of its reaching definitions is the ghost def, the
> > >   variable *may be* used uninitialized.
> > ...
> > 
> > I'm not too familiar with reaching definitions, do they take control
> > dependencies into account?
> > 
> Yes, that's what the SSA form is for:
> 
> 1	  int a, b;
> 2	
> 3	  b = foo();
> 4	  if (b < 100)
> 5	    a = 10;
> 6	  b = b + a;

The question is what happens with

1	int a, b;
2
3	b = foo();
4	if (b < 100)
5	  a = 10;
6	bar();
7	if (b < 100)
8	  b = b + a;

which is the canonical case that the current code gets wrong.  (And
imagine that line 7 is actually several hundred lines of spaghetti
which do not touch A or B.)

hmm... At line 6, the reaching set for A is {def(A, 5), def(A, 0)},
but at line 7 it ought to be just {def(A, 5)}.  Does it know that?

> > It would often be helpful if an uninitialized variable could be
> > automatically set to a "poison" value by the compiler.  This would
> > prevent one major cause of hard-to-find context-dependent bugs.  It
> > sounds like this can easily be implemented by emitting real code for
> > the ghost definitions; dead code elimination would then zap it in all
> > cases where there isn't a problem.  Have you considered this?
> > 
> Not really.  But it is definitely doable.  The only problem is
> what to consider a 'poison' value.

Something that will cause an immediate fault in the program if it gets
used.  More, you want a value that is *likely* to get used and
therefore to expose the bug.  (Zero, for instance, is a bad choice.)

For pointers, this is easy - pick a non-NULL value pointing into
unmapped memory.  Floats should probably get a signalling NaN.
Integers are harder, but on the theory that numbers in real life tend
to be small, use a big one.  For signed int, probably it should be
negative on the theory that the programmer may not have considered
negative numbers.  (But *not* -1.)

Booleans you are probably up a creek with.

Another consideration is that the bit pattern ought to be recognizable
as a poison value.  The garbage collector uses 0xA5A5A5A5.... for this
reason.

It's also an opportunity to make jokes with the hexadecimal constant.
Dead beef anyone?

> OTOH, if the compiler is already warning you that you're using the
> thing uninitialized, why would you also need this run-time trick?

Because you may incorrectly think you have inspected the code and
determined that there is no actual problem.  This is of course more
likely the more false positives there are.

> Hmm, I should've initialized p in the example.  But good point.
> This would've given you a warning for *p.  De-referencing a
> pointer is a use of the pointer and a def of every variable in
> its equivalence set.  In this case, we could empty the
> equivalence set if p is used uninitialized.

Sounds good.

> In tree SSA we call calculate_dominance_info and
> compute_dominance_frontiers directly.  Also, the code uses
> sbitmaps quite frequently.  The bitmaps are typically
> O(n_basic_blocks).  What problem are you referring to?

The bitmaps are probably sparse, and n_basic_blocks can blow up, at
which point your memory usage blows up too.  Brad Lucier has some good
examples of this problem.

zw

Re: better -Wuninitialized (Re: Ada files now checked in)

[Daniel Berlin]

>
>> In tree SSA we call calculate_dominance_info and
>> compute_dominance_frontiers directly.  Also, the code uses
>> sbitmaps quite frequently.  The bitmaps are typically
>> O(n_basic_blocks).  What problem are you referring to?
>
> The bitmaps are probably sparse,
Definitely, actually.
Dominance frontiers have to be sparse.

>  and n_basic_blocks can blow up, at
> which point your memory usage blows up too.  Brad Lucier has some good
> examples of this problem.
Yes, but i'm taking care of this, so no worries.
Without ssa even enabled, the new bitmaps i'm performance tuning 
(still),  saves about 30% memory over current bitmaps.
For instance, compiling one file (I can't remember if it's expr.c or 
20001226-1.c, i forget at the moment) at -O2 normally takes 130 meg, 
peak. It now takes 100 meg, peak.
This is without modifying anything to use sparse bitmaps, just replacing 
the existing bitmap implementation.

>
> zw

Re: better -Wuninitialized (Re: Ada files now checked in)

[Diego Novillo]

On Sun, 07 Oct 2001, Zack Weinberg wrote:

> 1	int a, b;
> 2
> 3	b = foo();
> 4	if (b < 100)
> 5	  a = 10;
> 6	bar();
> 7	if (b < 100)
> 8	  b = b + a;
> 
Ah, now I see what you're getting at.  You would get a warning in
this case.  Currently there is no pruning of reaching definitions
sets.  We could add some, but you have to be careful not to make
it excessively expensive.

Also remember that this warning is triggered rather early in the
analysis.  Well before any transformations are done, suppose that
for whatever reason B is deemed to always be greater than 100.
You would've gotten a warning for dead code.


> > OTOH, if the compiler is already warning you that you're using the
> > thing uninitialized, why would you also need this run-time trick?
> 
> Because you may incorrectly think you have inspected the code and
> determined that there is no actual problem.  This is of course more
> likely the more false positives there are.
> 
True.  0xdeadbeef sounds good for pointers and word integers.

> The bitmaps are probably sparse, and n_basic_blocks can blow up, at
> which point your memory usage blows up too.  Brad Lucier has some good
> examples of this problem.
> 
OK.  We should take a look at this once the implementation starts
to stabilize.


Diego.

Re: better -Wuninitialized (Re: Ada files now checked in)

[Daniel Berlin]

On Sunday, October 7, 2001, at 01:53  PM, Zack Weinberg wrote:

> On Sun, Oct 07, 2001 at 01:21:01PM -0400, Diego Novillo wrote:
>> On Sun, 07 Oct 2001, Zack Weinberg wrote:
>>> Maybe you could change the warning message to "...used uninitialized
>>> here" or "at this point" or something like that?  Just to be clear
>>> it's not the same old "somewhere in the function" message.
>>>
>> Sure.
>
> Thanks.
>
>>> I notice it says "_is_ used uninitialized".  Does that mean you've
>>> eliminated the old false positive problems?
>>>
>> That's the intent.  The new code still spews out false positives,
>> that's what I'm now working on.
>>
>> The analysis depends on the computation of reaching definitions.
>> Prior to computing the SSA form, we insert ghost definitions for
>> every symbol in the entry basic block.  After reaching
>> definitions, we traverse all the variable use references in the
>> function.  For every use:
>>
>> - if its only reaching definition is the ghost def, the variable
>>   *is* used uninitialized.
>>
>> - if one of its reaching definitions is the ghost def, the
>>   variable *may be* used uninitialized.
> ...
>
> I'm not too familiar with reaching definitions, do they take control
> dependencies into account?
>
> It would often be helpful if an uninitialized variable could be
> automatically set to a "poison" value by the compiler.  This would
> prevent one major cause of hard-to-find context-dependent bugs.  It
> sounds like this can easily be implemented by emitting real code for
> the ghost definitions; dead code elimination would then zap it in all
> cases where there isn't a problem.  Have you considered this?
>
>> Also, I'm about to add def-def chains to model non-killing
>> definitions like:
>>
>> 1: int a, b *p;
>> 2:
>> 3: a = 4;
>> 4: *p = 3;
>> 5: b = a + 1;
>>
>> The use of a at line 5 may be reached by the definitions of *p
>> and a at lines 4 and 3, respectively.  But this part is nowhere
>> near ready.
>
> Hmmm... since p itself is not initialized, it seems like you'd want to
> complain about it and then assume it doesn't alias anything.
>
>> - Compute the SSA form.  This involves computing immediate
>>   dominators and dominance frontiers.  I believe the algorithms
>>   we have in GCC are quite quick, but I haven't really looked.
>
> If I remember correctly we are using the state-of-the-art algorithm,
Not anymore, at least for phi placement.
Dominance calculation is as fast as it's gonna get without using *much* 
more complex datastructures (microtrees and whatnot).

> but its use of sbitmaps may cause problems.  (looking at ssa.c - dunno
> if the same code is used for trees).
>

Re: Ada files now checked in

[Daniel Berlin]

....
>   Building the FUD chains is like O(SxNxE) (could be wrong, I'm
>   quoting from memory).  There is a linear phi placing algorithm
>   which I plan to switch to.

You meen Sreedhar and gao's?
If so, i've got it coded already for the tree ssa stuff.
....

> Diego.

Re: Ada files now checked in

[Diego Novillo]

On Sun, 07 Oct 2001, Daniel Berlin wrote:

> ....
> >   Building the FUD chains is like O(SxNxE) (could be wrong, I'm
> >   quoting from memory).  There is a linear phi placing algorithm
> >   which I plan to switch to.
> 
> You meen Sreedhar and gao's?
>
Yes.  These two:

@InProceedings{	  bib:johnson.ea-94,
  title		= "The Program Structure Tree: Computing Control Regions in
		  Linear Time",
  author	= "R. Johnson and D. Pearson and K. Pingali",
  booktitle	= pldi94,
  address	= "Orlando, Florida",
  month		= jun,
  year		= "1994",
  pages		= "171--185"
}

@InProceedings{	  bib:sreedhar.ea-95,
  author	= "V. C. Sreedhar and G. R. Gao",
  title		= "A Linear Time Algorithm for Placing ${\phi}$-nodes",
  pages		= "62--73",
  isbn		= "0-89791-692-1",
  booktitle	= popl95,
  month		= jan,
  publisher	= "ACM Press",
  address	= "New York, NY, USA",
  year		= "1995"
}

> If so, i've got it coded already for the tree ssa stuff.
>
Cool.  Mind submitting the patch?

Thanks.  Diego.

Re: Ada files now checked in

[Daniel Berlin]

On Sunday, October 7, 2001, at 02:26  PM, Diego Novillo wrote:

> On Sun, 07 Oct 2001, Daniel Berlin wrote:
>
>> ....
>>>   Building the FUD chains is like O(SxNxE) (could be wrong, I'm
>>>   quoting from memory).  There is a linear phi placing algorithm
>>>   which I plan to switch to.
>>
>> You meen Sreedhar and gao's?
>>
> Yes.  These two:
>
> @InProceedings{	  bib:johnson.ea-94,
>   title		= "The Program Structure Tree: Computing Control Regions in
> 		  Linear Time",
>   author	= "R. Johnson and D. Pearson and K. Pingali",
>   booktitle	= pldi94,
>   address	= "Orlando, Florida",
>   month		= jun,
>   year		= "1994",
>   pages		= "171--185"
> }
>
> @InProceedings{	  bib:sreedhar.ea-95,
>   author	= "V. C. Sreedhar and G. R. Gao",
>   title		= "A Linear Time Algorithm for Placing ${\phi}$-nodes",
>   pages		= "62--73",
>   isbn		= "0-89791-692-1",
>   booktitle	= popl95,
>   month		= jan,
>   publisher	= "ACM Press",
>   address	= "New York, NY, USA",
>   year		= "1995"
> }
>
>> If so, i've got it coded already for the tree ssa stuff.
>>
> Cool.  Mind submitting the patch?
>
It's not a single patch (functionally, anyway), but i'll submit it 
sometime soon.
I construct an explicit dominator tree (from the idoms), then augment it 
with the DJ graph info.
This is because APT ("APT: a data structure for optimal control 
dependence computation", 
http://www.acm.org/pubs/citations/proceedings/pldi/207110/p32-pingali/ ) 
uses a dominator tree augmented with info as well, so it didn't make 
sense to just make a dj-graph specific version.
It's of course, largely non-tree-ssa specific, however, i used it in 
doing loop optimizations for tree-ssa.

> Thanks.  Diego.

Re: Ada files now checked in

[Joern Rennecke]

> - if its only reaching definition is the ghost def, the variable
>   *is* used uninitialized.

Not generally true.  The uninitialized use might never be executed.
Back to the halting problem...

Re: better -Wuninitialized (Re: Ada files now checked in)

[dewar]

<<1       int a, b;
2
3       b = foo();
4       if (b < 100)
5         a = 10;
6       bar();
7       if (b < 100)
8         b = b + a;

which is the canonical case that the current code gets wrong.  (And
imagine that line 7 is actually several hundred lines of spaghetti
which do not touch A or B.)
>>

I am not sure I would say that current code gets this "wrong". Sure you
can imagine building this particular theorem into the code, but you will
always have cases involving arbitrarily complex theorems. I do agree
it would be desirable to go just far enough to catch this case, i.e.
recognize absolutely identical conditions with invariant operands, but
even this is much trickier than people might imagine.

<<> > It would often be helpful if an uninitialized variable could be
> > automatically set to a "poison" value by the compiler.  This would
>>

In Ada, there is Normalize_Scalars which has this kind of effect, and
it has been extended in GNAT with the addition of Initialize_Scalars,
which allows the value set to be specified at bind time. So you can
see if your code depends on the value used.