Re: GCC optimizes integer overflow: bug or feature?

[Michael Veksler]

This overflow attitude has some resemblance to the attitude that 
resulted in the Y2K issues. I don't try to troll, I have a detailed 
explanation below.
Some time ago (a year?) I was told on this mailing-list that code 
breakage due to undefinedness of signed overflow is not too common (I at 
least claimed with no evidence that it was more than one bug per 1,000 
lines). My claim was counterclaimed by something like "most of the time 
people work with small enough values, so overflows don't happen too many 
times in practice". At first, this sounds reasonable. Then, I realized 
that it sounds awfully similar to "two digits are enough to represent a 
year".
You may think that the analogy is far fetched? In that case, I'll pick 
some gcc source file, at random and look for signed operations in it:

categorize_ctor_elements_1(..) in gcc/expr.c:
_elts += mult * nz;
elt_count += mult * ic;
Both assume that neither the multiplication, nor the addition overflow. 
Can GCC be really sure that this case will be caught outside this 
function, before it is called? Will it be always so in the future? You 
can't even add an assert to make sure that no overflow had occurred. You 
can't write:

temp=mult*nz;
a_gcc_assert(mult !=0 && temp/mult==nz);
a_gcc_assert(_elts+temp >= _elts);
_elts += temp;
You'd have to add a very weird looking assert like:
some_gcc_assert(
nz !=0 || (unsigned HOST_WIDE_INT)mult*nz/nz == (unsigned 
HOST_WIDE_INT)mult &&

(HOST_WIDE_INT)((unsigned HOST_WIDE_INT)mult*nz) >= 0
);
This is very ugly. You see, it was quite easy to find code that works 
today but may be easily break due to unrelated code shuffling that 
happen in other source files, without any warning!



I don't understand why the standard committee did not add a new keyword 
(say nowrap) instead of going from implementation defined overflows to 
undefined. If one wants fast induction variables, it would have been 
possible to write:

int f(int k)
{
nowrap int i;
int ret=k;
for (i=0; i <= k ; ++i)
++ret;
return ret;
}
and get the code transformed to the simple "return k*2+1;" which will be 
implementation defined for k >= MAX_INT/2 and undefined only for k==MAX_INT.


I know, adding a keyword may break existing code, but so does adding 
rules for "undefined" behavior. Having a predictable breakage at compile 
time is better than having code break at random at runtime.



Gabriel Dos Reis wrote:

The problem is that what constitutes a valid program tends to differ
from what constitutes a useful program found in the wild.  The
question for GCC is how to accomodate for the useful uses without
getting far away from both conformance and non-conformance.

I don't believe this particular issue of optimization based on
"undefined behaviour" can be resolved by just telling people "hey
look, the C standard says it is undefined, therefore we can optimize.
  
Exactly. For example take a look at the strict-aliasing issue. First 
optimizations were introduced such that if you did not conform to strict 
aliasing rules your code would silently break. In later gcc versions, 
warnings have been introduced in order to tell the user "hey, this code 
might break strict aliasing, are you sure you know what you are doing?". 
The current state of the strict-aliasing warnings is still imperfect, 
but much better and improving.
On the other hand, the state of signed overflow is quite grim. Even 
though the signed overflow issue has been here for over a decade, there 
is almost no warning on high risk code. Unfortunately, it is much more 
difficult to have good warning on potential overflow bugs than for 
strict-aliasing (with negligible false positive, and reasonable false 
negative). This is true, at least for predictable warnings (that don't 
depend on "irrelevant" architecture/code-gen/optimization flags).

And if you're not happy, just tell the compiler not to optimize".
For not all undefined behaviour are equal, and undefined behaviour is
also a latitude given to implementors to better serve their base
users.
  
Undefined behavior is bad. I think that any language spec should keep 
the amount of "undefined" behavior at a bare minimum. The whole issue of 
C's (or C++'s) undefined behavior is very unintuitive for most code writers:


   * Students that learn C/C++ have too much at their hands as it is.
 They won't be able to internalize these issues on top of other new
 concepts they have to learn: recursion, free store, algorithms, etc.
   * Many lecturers (I have a gut feeling that most) that teach C/C++
 don't understand these issues well enough to teach them in a basic
 C/C++ course.
   * Books barely cover (if at all) these issues. Certainly, these
 issues are not stressed every time the terms "signed" or "type
 casting" are mentioned.
   * At verification conferences (and in other cases) I had the
 opportunity to talk to people that work on formal verification of
 C/C++ from the industry and academia. Surprisingly t

3 new GCC mirrors

[Marco Rinaudo - Internet.bs Corp.]

Dear Collegues,
I am pleased to announce 3 new GCC mirrors located in London (UK), Hong Kong
and Toronto (CANADA), daily resync.

1) Hong Kong: http://gcc-hk.internet.bs thanks to http://www.internet.bs
(info at internet dot bs)
2) London (UK): http://gcc-uk.internet.bs thanks to http://www.internet.bs
(info at internet dot bs)
3) Toronto (Canada): http://gcc-ca.internet.bs thanks to
http://www.internet.bs (info at internet dot bs)

Please feel free to add the 3 mirrors to the official list of mirrors
located here: http://gcc.gnu.org/mirrors.html

Best regards,
Marco Rinaudo - CEO
Internet.bs Corp. - Internet domain registrations
http://www.INTERNET.bs

Re: GCC optimizes integer overflow: bug or feature?

[Paolo Bonzini]

Some time ago (a year?) I was told on this mailing-list that code 
breakage due to undefinedness of signed overflow is not too common (I at 
least claimed with no evidence that it was more than one bug per 1,000 
lines). My claim was counterclaimed by something like "most of the time 
people work with small enough values, so overflows don't happen too many 
times in practice".


This claim is a non sequitur.

What I would say is, people *don't understand why a compiler needs to 
assume undefined overflow semantics*, because people work with small 
values and don't care about the boundary conditions.


For example, most programmers that know assembly language will 
appreciate if the compiler can use the processor's support for loop with 
a known number of iterations (mtctr on PPC, for example).  However, I'm 
pretty sure that, if you present these two pieces of code to some good 
programmers,


  unsigned int i;
  for (i = 0; i <= n; i++)
...

  unsigned int i;
  for (i = 0; i < n; i++)
...

where the compiler uses mtctr only in the second case, most of them will 
think that the compiler has bug.  Almost nobody will realize that the 
first can loop infinitely, and the second cannot (which is the reason 
why the compiler cannot optimize them in the same way).


Well, these programmers *are* assuming undefined overflow semantics even 
on unsigned types.  Maybe they would like overflow semantics should be 
defined in some cases and undefined in others?  Fine by me, that would 
be -fwrapv -funsafe-loop-optimizations in GCC; but a language standard 
cannot go to such detail!


On the autoconf mailing list, Paul Eggert mentioned as a good compromise 
that GCC could treat signed overflow as undefined only for loops and not 
in general.  Except that the original gnulib bug report was in a loop, 
so this compromise would leave that case undefined.


You may think that the analogy is far fetched? In that case, I'll pick 
some gcc source file, at random and look for signed operations in it:

categorize_ctor_elements_1(..) in gcc/expr.c:
_elts += mult * nz;
elt_count += mult * ic;
Both assume that neither the multiplication, nor the addition overflow. 


I see this as a *counterexample*: it shows that programmers don't care 
about having wrapping overflow, in fact they don't care about overflow 
at all.  This code is incorrect not only if overflow is undefined, but 
also if overflow wraps (-fwrapv); it is correct if overflow aborts 
(-ftrapv).


Paolo

Re: GCC optimizes integer overflow: bug or feature?

[Paolo Bonzini]

foo->bar = make_a_bar();
foo->bar->none = value;

being rendered as:

call make_a_bar
foo->bar->none = value
foo->bar = 


You are not describing a C compiler.


Um, I'm describing what gcc did?


I think he meant

x = make_a_bar ();
x->none = value;
foo->bar = x;

I don't know if this is a valid optimization, but I wouldn't be 
surprised if it is.


Palo

Re: GCC optimizes integer overflow: bug or feature?

[Michael Veksler]

Paolo Bonzini wrote:



foo->bar = make_a_bar();
foo->bar->none = value;

being rendered as:

call make_a_bar
foo->bar->none = value
foo->bar = 


You are not describing a C compiler.


Um, I'm describing what gcc did?


I think he meant

x = make_a_bar ();
x->none = value;
foo->bar = x;

I don't know if this is a valid optimization, but I wouldn't be 
surprised if it is.


Maybe he forgot the delicate details? The issue may happen if this 
example was incomplete (my "completion" may need some tweaking to make 
it more realistic):


   #define make_a_bar(ppInstance)  
   *(unsigned**)(&ppInstance)=make_a_uint(sizeof(struct bar))

   make_a_bar(foo->bar);
   foo->bar->none = value;


In this case strict-aliasing starts its act. The store to foo->bar is 
done through a different type (pointer to unsigned), which tells gcc 
that foo->bar->none accesses one  object (type bar), while the 
construction of foo->bar accesses a different object type (unsigned 
int). In this case this code is undefined and the compiler can reorder 
these two lines.


I am not sure if the following would break as well:

   #define make_a_bar()   (struct bar*)make_a_uint(sizeof(struct bar))
   foo->bar=make_a_bar();
   foo->bar->none = value;

Since gcc should know that foo->bar of type "struct bar" has been 
updated before "value" gets written to "none" which is a field on object 
of type "struct bar".



 Michael

Re: GCC optimizes integer overflow: bug or feature?

[Paolo Bonzini]

Maybe he forgot the delicate details? The issue may happen if this 
example was incomplete (my "completion" may need some tweaking to make 
it more realistic):


   #define make_a_bar(ppInstance) 
*(unsigned**)(&ppInstance)=make_a_uint(sizeof(struct bar))

   make_a_bar(foo->bar);
   foo->bar->none = value;


Then, the author of make_a_bar() is getting what he deserved.


I am not sure if the following would break as well:

   #define make_a_bar()   (struct bar*)make_a_uint(sizeof(struct bar))
   foo->bar=make_a_bar();
   foo->bar->none = value;

Since gcc should know that foo->bar of type "struct bar" has been 
updated before "value" gets written to "none" which is a field on object 
of type "struct bar".


Of course it wouldn't break.

But the reason I say that this is what you deserved, is that the cast is 
completely unnecessary.  You should write this:


#define make_a_bar (ppInstance) \
 ((ppInstance)=(void *)make_a_uint(sizeof(struct bar)))

that is, you put the cast on the other side and don't play with the 
types of the lvalues.  This is what happens all the time with malloc.


Paolo

Re: GCC optimizes integer overflow: bug or feature?

[Michael Veksler]

Paolo Bonzini wrote:


Some time ago (a year?) I was told on this mailing-list that code 
breakage due to undefinedness of signed overflow is not too common (I 
at least claimed with no evidence that it was more than one bug per 
1,000 lines). My claim was counterclaimed by something like "most of 
the time people work with small enough values, so overflows don't 
happen too many times in practice".


This claim is a non sequitur.

What I would say is, people *don't understand why a compiler needs to 
assume undefined overflow semantics*, because people work with small 
values and don't care about the boundary conditions.


But that is generally true for stuff like gets/sprintf/strcpy/unsafe 
operation de-jour . People don't care for overflow cases of sprintf 
because they work with small data. Yet when, suddenly, the size of the 
data grows and funny stuff start to happen *due* to their  sprintf et. al.
For example, most programmers that know assembly language will 
appreciate if the compiler can use the processor's support for loop 
with a known number of iterations (mtctr on PPC, for example).  
However, I'm pretty sure that, if you present these two pieces of code 
to some good programmers,


  unsigned int i;
  for (i = 0; i <= n; i++)
...

  unsigned int i;
  for (i = 0; i < n; i++)
...

where the compiler uses mtctr only in the second case, most of them 
will think that the compiler has bug.  Almost nobody will realize that 
the first can loop infinitely, and the second cannot (which is the 
reason why the compiler cannot optimize them in the same way).


Unfortunately, some compilers (not gcc) would optimize both cases the 
same way.
Well, these programmers *are* assuming undefined overflow semantics 
even on unsigned types.  Maybe they would like overflow semantics 
should be defined in some cases and undefined in others?  Fine by me, 
that would be -fwrapv -funsafe-loop-optimizations in GCC; but a 
language standard cannot go to such detail!


It could add the type modifier "nowrap", such that loop indexes can be 
marked this way explicitly, signed or unsigned.
On the autoconf mailing list, Paul Eggert mentioned as a good 
compromise that GCC could treat signed overflow as undefined only for 
loops and not in general.  Except that the original gnulib bug report 
was in a loop, so this compromise would leave that case undefined.



I'd vote for Paul's suggestion. It would have the least-surprise effect.
You may think that the analogy is far fetched? In that case, I'll 
pick some gcc source file, at random and look for signed operations 
in it:

categorize_ctor_elements_1(..) in gcc/expr.c:
_elts += mult * nz;
elt_count += mult * ic;
Both assume that neither the multiplication, nor the addition overflow. 


I see this as a *counterexample*: it shows that programmers don't care 
about having wrapping overflow, in fact they don't care about overflow 
at all.  This code is incorrect not only if overflow is undefined, but 
also if overflow wraps (-fwrapv); it is correct if overflow aborts 
(-ftrapv).
No, it is an example for a bug which is difficult to protect against 
with an assertion. Even more seriously, instead of a simple mere bug 
with bad behavior we get escalated to undefined behavior. "Undefined" is 
the worst kind since in theory it is allowed to clean-up your disk, and 
explode your computer and start WW-III. Can this happen in this case? it 
depends what the caller does and if gcc can see the caller and the 
callee at the same time (e.g. if gcc knows that a caller causes  
mult=MAX_INT/2, it might assume that nz <=2 for that caller, and perform 
some nasty transformations down the line).


I am not saying that GCC should abandon all optimizations that assume 
that no execution path gets to undefined cases. I am saying that these 
things should not be taken lightly. Saying "programmers don't care about 
having [something leading to undefined behavior]" is simply ignoring 
the graveness of the bad effects. By taking seriously I include the VRP 
that due to its lacking data structure (at least it used to be so) would 
be much less effective if gcc would to assume wrapping int.


Instead of having to choose between the bad alternatives of  VRP that 
gives weird results for undefined cases or does barely anything, its 
data structure should be improved, and each variable should have a set 
of ranges instead of a single range (like what I have seen in some 
Constraints/CP papers).




The second point in this example is:

Checking for buffer overflows (undefined code) before they occur is 
trivial in most cases. Checking for a wrapping "signed int" before it 
actually wraps is relatively complex and unintuitive (e.g. it is 
unintuitive why should a/b ever overflow, hint: MIN_INT/-1 --> MIN_INT). 
I would prefer plain bugs, in which -g and -O3 act just the same, over 
undefined behavior when I have no choice but to debug a -O3 code !!!
I can't forget the day (several 

Re: Reload Pass

[Ian Lance Taylor]

Rajkishore Barik <[EMAIL PROTECTED]> writes:

> Does anyone know of any document describing (in details) the reload phase 
> of GCC?

There isn't one.  The closest such document is
http://gcc.gnu.org/wiki/reload
which is accurate despite, or perhaps because of, starting out by
equating reload with Satan.

> I am planning to write a linear scan reload for GCC (one that does not 
> take reg_renumber
> but takes instruction specific register allocation and move information). 
> Can anyone point me
> to some existing code/literature for this in GCC? 

There is none.

If you expect this pass to actually replace reload, then I advise you
to reconsider.  That would be a hopeless task.  Well, maybe you could
do it if you restrict yourself to a single architecture.

If you want to run this pass in between the register allocator and
reload, that would probably be doable.  Of course, reload will then
muck up your decisions, and the resulting code will sometimes be worse
than what you get today.  But it might be an interesting experiment.

Ian

SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

In my ongoing plumbing work on Dan Berlin's Operator Strength
Reduction implementation, I've encountered what seems to me like a
bug. On IRC yesterday everyone seemed to agree that it was a bug.
Zdenek, OTOH, says it is not a bug.

I would like it to be a bug (so it will get fixed everywhere), so I'm
interested in getting consensus here. Hopefully Zdenek will speak up
and explain why he thinks it needs to be allowed.

The situation is that some SSA_NAMEs are disused (removed from the
code) without being released onto the free list by release_ssa_name().
I have found only one place where this happens, but Zdenek claims
there are other places. The result is that it is apparently impossible
to tell by iterating over the vector of SSA_NAMEs whether any
particular SSA_NAME is currently in use by the code. What I would like
is for the SSA_NAME_IN_FREE_LIST bit to indicate reliably whether the
SSA_NAME is unused. If there is no way to deduce what I want by
looking at an SSA_NAME, it will be necessary to walk over the code
whenever we simply want to iterate over SSA_NAMEs that are in use.

Please discuss.

   -- Robert Kennedy

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Diego Novillo]

Robert Kennedy wrote on 12/21/06 11:37:

The situation is that some SSA_NAMEs are disused (removed from the 
code) without being released onto the free list by 
release_ssa_name().


Yes, it happens if a name is put into the set of names to be updated by 
update_ssa.


After update_ssa, it should be true that every SSA name with no 
SSA_NAME_DEF_STMT is in the free list.


However, if we have SSA names with no defining statement that are still 
in considered active, I would hardly consider it a serious bug.  It's a 
waste of memory, which you are more than welcome to fix, but it should 
not cause correctness issues.



Please discuss.


Test case?

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Daniel Berlin]

On 12/21/06, Diego Novillo <[EMAIL PROTECTED]> wrote:

Robert Kennedy wrote on 12/21/06 11:37:

> The situation is that some SSA_NAMEs are disused (removed from the
> code) without being released onto the free list by
> release_ssa_name().
>
Yes, it happens if a name is put into the set of names to be updated by
update_ssa.

After update_ssa, it should be true that every SSA name with no
SSA_NAME_DEF_STMT is in the free list.


In this case this isn't true, because we have code that orphans ssa
names without releasing them.
I'm sure Robert will explain further details in a few moments :)


However, if we have SSA names with no defining statement that are still
in considered active, I would hardly consider it a serious bug.  It's a
waste of memory, which you are more than welcome to fix, but it should
not cause correctness issues.


It will cause not code correctness issues, but make life very very
annoying.  If you walk the ssa names one by one, and you have some
pointing to statements that don't exist anymore, because the names
were not released and defining statements nulled out by
release_ssa_name,  you are going to run into segfaults trying to walk
them.

This is exactly what happens in the case we have.

BTW, the reason we walk the list of ssa names is to DFS them.

IE the code is someting like:

for (i = 0; i < num_ssa_names; i++)
{
 tree name = ssa_name (i);
 if (name && !SSA_NAME_IN_FREELIST (name)
  DFS (name)
}

IIRC, DFS will crash trying to touch the def statement because it's
been GC'd if the ssa name is orphaned.

Anyway, it seems you still agree this is a bug in any case, even if
you don't think it's a serious bug.

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Jeffrey Law]

On Thu, 2006-12-21 at 12:21 -0500, Daniel Berlin wrote:
> On 12/21/06, Diego Novillo <[EMAIL PROTECTED]> wrote:
> > Robert Kennedy wrote on 12/21/06 11:37:
> >
> > > The situation is that some SSA_NAMEs are disused (removed from the
> > > code) without being released onto the free list by
> > > release_ssa_name().
> > >
> > Yes, it happens if a name is put into the set of names to be updated by
> > update_ssa.
> >
> > After update_ssa, it should be true that every SSA name with no
> > SSA_NAME_DEF_STMT is in the free list.
> 
> In this case this isn't true, because we have code that orphans ssa
> names without releasing them.
> I'm sure Robert will explain further details in a few moments :)
True.  But remember, the stated purpose of the SSA_NAME recycling
code was _not_ to track every SSA_NAME that went "dead" and recycle
it, but instead to get the majority of them (and to ultimately save
memory by recycling them).  Orphan SSA_NAME were always expected.

If we wanted to add a new policy that all dead SSA_NAMEs must be
released to the recycling code, then that's fine, I'm not going
to object.

Alternately we can revisit the entire recycling question as well --
things have changed significantly since that code was written and
I've speculated that the utility of the recycling code has
diminished, possibly to the point of being a useless waste of time
and code.

The last obvious alternative I see is to stop chaining free nodes using
the TREE_CHAIN field.  That at least avoids the sharing between
TREE_CHAIN and SSA_NAME_DEF_STMT which often causes problems.  The
downside is given an SSA_NAME it still won't be obvious if it is an
orphan or still in use.

Jef

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Jeffrey Law]

On Thu, 2006-12-21 at 11:55 -0500, Diego Novillo wrote:
> Robert Kennedy wrote on 12/21/06 11:37:
> 
> > The situation is that some SSA_NAMEs are disused (removed from the 
> > code) without being released onto the free list by 
> > release_ssa_name().
> > 
> Yes, it happens if a name is put into the set of names to be updated by 
> update_ssa.
> 
> After update_ssa, it should be true that every SSA name with no 
> SSA_NAME_DEF_STMT is in the free list.
> 
> However, if we have SSA names with no defining statement that are still 
> in considered active, I would hardly consider it a serious bug.  It's a 
> waste of memory, which you are more than welcome to fix, but it should 
> not cause correctness issues.
> 
> > Please discuss.
> > 
> Test case?
I think the discussion should begin with reevaluating whether or not
the memory savings from recycling SSA_NAMEs is still worth the headache.

Turning on GATHER_STATISITICS ought to give you some information about
the effectiveness of recycling.   Then build some code (GCC source,
particularly with ENABLE_CHECKING defined) with/without recycling and
compare memory usage for SSA_NAMES (IIRC that memory use is broken
out separately) before/after as well as total memory usage. 

Jeff

Re: question from imobilien

[Janis Johnson]

On Wed, Dec 20, 2006 at 03:06:34PM +0100, Jan Eissfeld wrote:
> Hi,
> 
> PR19978 reports that some overflow warnings are emitted multiple times. Like 
> for example,
> 
> test.c:6: warning: integer overflow in expression
> test.c:6: warning: integer overflow in expression
> test.c:6: warning: integer overflow in expression
> 
> The current testsuite will match any number of those to a single {
> dg-warning }. I don't know whether this is a known limitation, a bug
> on the testsuite or it just needs some magic.
> 
> How could I test that exactly one warning was emitted?

See http://gcc.gnu.org/ml/gcc/2006-12/msg0.html for an ugly solution,
and the rest of the thread for problems with this approach.  The check
for getting the warning must be in a separate test from the check for
multiple warnings.

Janis

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Ian Lance Taylor]

Jeffrey Law <[EMAIL PROTECTED]> writes:

> On Thu, 2006-12-21 at 11:55 -0500, Diego Novillo wrote:
> > Robert Kennedy wrote on 12/21/06 11:37:
> > 
> > > The situation is that some SSA_NAMEs are disused (removed from the 
> > > code) without being released onto the free list by 
> > > release_ssa_name().
> > > 
> > Yes, it happens if a name is put into the set of names to be updated by 
> > update_ssa.
> > 
> > After update_ssa, it should be true that every SSA name with no 
> > SSA_NAME_DEF_STMT is in the free list.
> > 
> > However, if we have SSA names with no defining statement that are still 
> > in considered active, I would hardly consider it a serious bug.  It's a 
> > waste of memory, which you are more than welcome to fix, but it should 
> > not cause correctness issues.
> > 
> > > Please discuss.
> > > 
> > Test case?
> I think the discussion should begin with reevaluating whether or not
> the memory savings from recycling SSA_NAMEs is still worth the headache.

I may be missing something, but I don't think that is the interesting
issue here.

I think the issue is whether we want to have a way to see all
currently valid SSA_NAMEs.  Right now we can have SSA_NAMEs in the
list which are no longer used, and we have no way to tell whether they
are used or not.  Thus the only way to see all valid SSA_NAMEs is to
walk the code.

If that is acceptable, then there is no issue here.  If that is not
acceptable, then we need to fix the code to correctly mark SSA_NAMEs
which are no longer used.  Whether we recycle the memory in the unused
SSA_NAMEs is a separate (and less interesting) discussion.

Ian

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Daniel Berlin]

I may be missing something, but I don't think that is the interesting
issue here.


I agree.



I think the issue is whether we want to have a way to see all
currently valid SSA_NAMEs.  Right now we can have SSA_NAMEs in the
list which are no longer used, and we have no way to tell whether they
are used or not.  Thus the only way to see all valid SSA_NAMEs is to
walk the code.

If that is acceptable, then there is no issue here.  If that is not
acceptable, then we need to fix the code to correctly mark SSA_NAMEs
which are no longer used.  Whether we recycle the memory in the unused
SSA_NAMEs is a separate (and less interesting) discussion.


IMHO, it's not acceptable, because it leaves no way to do DFS walks
that don't involve kludges and hacks.

Ian

[GCCWIKI] password reset borken?

[Dave Korn]

Afternoon all,

  I was trying to recover my password for the gcc wiki, and it doesn't work:
when I enter my email and click the button, I see an error message at the top
of the page saying:

{u'[EMAIL PROTECTED]': (550, 'relaying denied')}

  I believe this is reporting an error at the sourceware/gcc machine because I
have no problem receiving any other mail from external sources, so I don't
think it's our server generating the error.  Is whoever administers the wiki
around?  Could you take a quick look at it for me?  TIA!


cheers,
  DaveK
-- 
Can't think of a witty .sigline today

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

> I think the discussion should begin with reevaluating whether or not
> the memory savings from recycling SSA_NAMEs is still worth the headache.

That's a separate project that I'd rather not bundle with strength
reduction, because the two are unrelated conceptually.

My opinion is that instead, the following question should be the
starting point: Some code in GCC has a demonstrable need to iterate
over the SSA_NAMEs in current use by the program being compiled. Do we
want to provide a reasonable way to do that iteration? Currently we
don't provide it. That seems wrong to me.

I don't much care about the details of *how* the facility is provided,
although if implementing it doesn't divert me too much I'm happy to do
it. Plenty of people who know more than I do will have opinions about
how it should be done, and that's fine. I don't want to decide how it
should be done, necessarily.

I would simply like to begin with agreement that it should be
done. Or, if the consensus is that it should not be done in spite of
the need, some reasonable advice about what to do instead (I don't see
a good alternative).

-- Robert

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

I wrote:
> I don't much care about the details of *how* the facility is provided...

I should rephrase this. I do care about the interface to it. I don't
care so much about the implementation. I would like the interface to
be straightforward.

I don't want to do a separate project to reevaluate the need for
SSA_NAME recycling and build consensus about that as a prerequisite.

-- Robert

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Jeffrey Law]

On Thu, 2006-12-21 at 10:08 -0800, Ian Lance Taylor wrote:

First, let's go ahead and define an orphan.  An orphan is an SSA_NAME
which has SSA_NAME_DEF_STMT pointing to a statement which does not
appear in the IL.

> I may be missing something, but I don't think that is the interesting
> issue here.
I think we would both agree that the underlying issue is our inability
to efficiently determine if a given SSA_NAME:

  a. Appears in the IL
  b. Is in the free list
  c. Is an orphan

The overloading of TREE_CHAIN/SSA_NAME_DEF_STMT inside the recycling
code makes this problem somewhat uglier.   If we didn't have that
sharing (either because we took the hit of another field or we didn't
have a recycler), then the act of releasing an SSA_NAME would probably
look like:

TREE_CHAIN (node) = NULL;

Checking for an SSA_NAME being in-use would be

  TREE_CHAIN (node) != NULL

And TREE_CHAIN (node) would *always* point to a statement in the IL
rather than sometimes pointing to a statement (which may or may not
be in the IL) and sometimes pointing to another SSA_NAME or NULL
(as is the case currently for SSA_NAMEs in the free list).

Note we'd still have the problem of orphans for which I see only two
solutions.

First, we bite the bullet and find every point where we're not releasing
orphan and we make failure to release a dead SSA_NAME an error (which we
can check during the IL scan as part of verify_ssa).  The advantage is
we know at any point the set SSA_NAMEs which appear in the IL and we
have very clearly defined rules for dealing with SSA_NAMEs.  They are
either free or they appear in the IL -- no orphans.

The alternative is to mark/sweep them between passes.  The obvious
downside is that within a pass we can get orphans, which I think
is insufficient for the current needs.

> I think the issue is whether we want to have a way to see all
> currently valid SSA_NAMEs.  Right now we can have SSA_NAMEs in the
> list which are no longer used, and we have no way to tell whether they
> are used or not.  Thus the only way to see all valid SSA_NAMEs is to
> walk the code.
Depends on your definition of valid :-)  Until now we've allowed 
valid to include orphan SSA_NAMEs.  That's far from ideal.  But
it's worked marginally until now.

Note that an orphan SSA_NAME should still have a TREE_CHAIN which
points to a "valid" statement node.  God help you if you try to
interpret anything inside that statement node though.

Note that with clearly defined rules you can still do node recycling.
But the implementation would be simpler.  
Jeff

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

> In this case this isn't true, because we have code that orphans ssa
> names without releasing them.
> I'm sure Robert will explain further details in a few moments :)

Actually you explained all the relevant details. The question is
whether it should be allowed or not. So far almost everyone seems to
think not.

> It will cause not code correctness issues, but make life very very
> annoying.  If you walk the ssa names one by one, and you have some
> pointing to statements that don't exist anymore, because the names
> were not released and defining statements nulled out by
> release_ssa_name,  you are going to run into segfaults trying to walk
> them.

It isn't specifically important that the defining statements be nulled
out, of course. What matters is that there should be *some way* to
tell whether the item is in current use. Incidentally, checking for a
NULL defining statement currently doesn't work anyway because the same
field as SSA_NAME_DEF_STMT is reused for the free list
chaining. There's a flag to tell me whether a node is in the free
list, but of course that flag isn't set for the limbo nodes that you
and I agree are a problem -- because they aren't in the free list (and
they aren't in the program either).

-- Robert

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

> Right now we can have SSA_NAMEs in the
> list which are no longer used, and we have no way to tell whether they
> are used or not.  Thus the only way to see all valid SSA_NAMEs is to
> walk the code.

To wit: are there iteration macros somewhere that will help me walk
the code while abstracting away all the ugly details like stmt/bb
boundaries, etc.?

-- Robert

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Diego Novillo]

Daniel Berlin wrote on 12/21/06 12:21:


for (i = 0; i < num_ssa_names; i++)
{
  tree name = ssa_name (i);
  if (name && !SSA_NAME_IN_FREELIST (name)
   DFS (name)

>
I see that you are not checking for IS_EMPTY_STMT.  Does DFS need to 
access things like bb_for_stmt?


In any case, that is not important.  I agree that every SSA name in the 
SSA table needs to have a DEF_STMT that is either (a) an empty 
statement, or, (b) a valid statement still present in the IL.


Note that this is orthogonal to the problem of whether we free up unused 
names from this list.  Every time a statement S disappears, we should 
make sure that the names defined by S get their SSA_NAME_DEF_STMT set to 
 NOP.


Frankly, I'm a bit surprised that we are running into this. I'd like to 
see a test case, if you have one.

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Diego Novillo]

Robert Kennedy wrote on 12/21/06 13:58:

Right now we can have SSA_NAMEs in the
list which are no longer used, and we have no way to tell whether they
are used or not.  Thus the only way to see all valid SSA_NAMEs is to
walk the code.


To wit: are there iteration macros somewhere that will help me walk
the code while abstracting away all the ugly details like stmt/bb
boundaries, etc.?

No.  The code is segmented into basic blocks.  To walk the code, you 
must walk each basic block.


Something I forgot to add in my previous message.  Notice that it is not 
altogether rare to find cases where we have more SSA names than 
statements.  Are you walking the SSA names because you assume it's 
always shorter than walking the statements?

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Diego Novillo]

Jeffrey Law wrote on 12/21/06 12:48:

True.  But remember, the stated purpose of the SSA_NAME recycling
code was _not_ to track every SSA_NAME that went "dead" and recycle
it, but instead to get the majority of them (and to ultimately save
memory by recycling them).  Orphan SSA_NAME were always expected.

But this is orthogonal to the recycling issue.  They are traversing the 
SSA name table and finding SSA names that have invalid DEF_STMT entries. 
I believe that we should support this kind of usage of the SSA table.




Alternately we can revisit the entire recycling question as well --
things have changed significantly since that code was written and
I've speculated that the utility of the recycling code has
diminished, possibly to the point of being a useless waste of time
and code.

That'd be interesting to try, yes.  Though we *do* want to invalidate 
SSA_NAME_DEF_STMT for the SSA names whose defining statement gets deleted.

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Zdenek Dvorak]

Hello,

> > > > The situation is that some SSA_NAMEs are disused (removed from the
> > > > code) without being released onto the free list by
> > > > release_ssa_name().
> > > >
> > > Yes, it happens if a name is put into the set of names to be updated by
> > > update_ssa.
> > >
> > > After update_ssa, it should be true that every SSA name with no
> > > SSA_NAME_DEF_STMT is in the free list.
> > 
> > In this case this isn't true, because we have code that orphans ssa
> > names without releasing them.
> > I'm sure Robert will explain further details in a few moments :)
> True.  But remember, the stated purpose of the SSA_NAME recycling
> code was _not_ to track every SSA_NAME that went "dead" and recycle
> it, but instead to get the majority of them (and to ultimately save
> memory by recycling them).  Orphan SSA_NAME were always expected.
> 
> If we wanted to add a new policy that all dead SSA_NAMEs must be
> released to the recycling code, then that's fine, I'm not going
> to object.

I think this might be a good idea.  I think that this requires
a lot of changes (basically going through all uses of bsi_remove
and remove_phi_node and checking them), but it would be cleaner
than the current situation.

It should be however easy to add verification to verify_ssa, so
this project should be fairly straightforward (I hope).

Zdenek

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Diego Novillo]

Ian Lance Taylor wrote on 12/21/06 13:08:


If that is acceptable, then there is no issue here.  If that is not
acceptable, then we need to fix the code to correctly mark SSA_NAMEs
which are no longer used.  Whether we recycle the memory in the unused
SSA_NAMEs is a separate (and less interesting) discussion.


Agreed.

We have various passes that walk through the SSA table, so I want to 
keep supporting that.


We do have cases where an SSA name may get its defining statement zapped 
and yet we need to keep it around.  The renamer uses names_to_release in 
those cases, and makes sure not to visit the defining statement.


If every statement removal were to set SSA_NAME_DEF_STMT to NOP for 
every name generated by the removed statement, then the renamer would 
probably not need to do that.  However, the renamer *needs* the SSA name 
itself not to be recycled (for name->name mappings).

Re: GCC optimizes integer overflow: bug or feature?

[Paul Eggert]

Paolo Bonzini <[EMAIL PROTECTED]> writes:

> On the autoconf mailing list, Paul Eggert mentioned as a good
> compromise that GCC could treat signed overflow as undefined only for
> loops and not in general.

What I meant to propose (and perhaps did not propose clearly
enough) is that if the C application is checking for integer
overflow, GCC should not optimize that code away; but it is
OK for GCC to do other loop optimizations.  That is, some
overflow checking is done in loops, and GCC should not
optimize that away, but the other loop optimizations are OK.

That probably sounds vague, so here's the code that beta
gcc -O2 actually broke (which started this whole thread):

  int j;
  for (j = 1; 0 < j; j *= 2)
if (! bigtime_test (j))
  return 1;

Here it is obvious to a programmer that the comparison is
intended to do overflow checking, even though the test
controls the loop.  Can gcc -O2 be made "smart" enough to
notice this, and not optimize away the test?

Another question for the GCC experts: would it fix the bug
if we replaced "j *= 2" with "j <<= 1" in this sample code?

I ask the latter question partly because nobody has yet
proposed a portable fix for this bug.  The patch proposed in

worked for Ralf, but it does not work in general.  It
attacks the problem by changing "int j" to "unsigned j".
But because bigtime_test wants an int, this causes the test
program to compute the equivalent of (int) ((unsigned int)
INT_MAX + 1), and C99 says that if you cannot assume
wrapping semantics this expression has undefined behavior in
the common case where INT_MAX < UINT_MAX.

Obviously this latter can be worked around too, but what a
mess, huh?

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Daniel Berlin]

On 12/21/06, Diego Novillo <[EMAIL PROTECTED]> wrote:

Daniel Berlin wrote on 12/21/06 12:21:

> for (i = 0; i < num_ssa_names; i++)
> {
>   tree name = ssa_name (i);
>   if (name && !SSA_NAME_IN_FREELIST (name)
>DFS (name)
 >
I see that you are not checking for IS_EMPTY_STMT.  Does DFS need to
access things like bb_for_stmt?


I avoided including that part, but yes, we check for it.



In any case, that is not important.  I agree that every SSA name in the
SSA table needs to have a DEF_STMT that is either (a) an empty
statement, or, (b) a valid statement still present in the IL.


Then we've got a bug here :)



Note that this is orthogonal to the problem of whether we free up unused
names from this list.  Every time a statement S disappears, we should
make sure that the names defined by S get their SSA_NAME_DEF_STMT set to
  NOP.

Frankly, I'm a bit surprised that we are running into this. I'd like to
see a test case, if you have one.

Robert, can you attach the testcase you've been working with?
I'm not surprised, but only because I hit it before.   It's pretty rare.

IIRC, what happens it this:

1. We replace all uses of a phi node with something else
2. We then call remove_phi_node with false as the last parameter (only
3 places in the compiler), which ends up destroying the phi node but
not releasing the LHS name (since this is what the last parameter says
whether to do).


void
remove_phi_node (tree phi, tree prev, bool release_lhs_p)
{
...
 release_phi_node (phi);
 if (release_lhs_p)
   release_ssa_name (PHI_RESULT (phi));
}

3. PHI_RESULT (phi) is now in the ssa name list, but SSA_NAME_DEF_STMT
points to a released phi node.

4. We try to walk this at some point later, and crash.

You can see this happens in tree_merge_blocks:

 /* Remove all single-valued PHI nodes from block B of the form
V_i = PHI  by propagating V_j to all the uses of V_i.  */
 bsi = bsi_last (a);
 for (phi = phi_nodes (b); phi; phi = phi_nodes (b))
   {
 tree def = PHI_RESULT (phi), use = PHI_ARG_DEF (phi, 0);
...
else
 replace_uses_by (def, use);

 remove_phi_node (phi, NULL, false);
   }

Whenever we hit the else block we end up with a phi node result that
points to a released phi node.  It won't appear in the IR (sine the
phi node has been removed and all the result uses replaced), but will
appear in the ssa_names list.

There are only two other places that call remove_phi_node with false
as the last parameter.
One is moving a phi node, the other appears to be a bug just like the above.

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

> Robert, can you attach the testcase you've been working with?

One testcase is libstdc++-v3/libsupc++/vec.cc from mainline.

But it compiles without trouble unless you add verification or a walk
over the SSA_NAMEs at the right time.

> 1. We replace all uses of a phi node with something else
> 2. We then call remove_phi_node with false as the last parameter (only
> 3 places in the compiler), which ends up destroying the phi node but
> not releasing the LHS name (since this is what the last parameter says
> whether to do).

That's right. Zdenek recommended that I change one of those places
(the one in tree_merge_blocks that you quoted) to "true", but doing
that causes some other code of his to break. I haven't analyzed why he
needs those things to stay around, but I suspect it's because -- for a
while, anyway -- he needs the DEF_STMT for something that's been
removed.

-- Robert

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Ian Lance Taylor]

Jeffrey Law <[EMAIL PROTECTED]> writes:

> On Thu, 2006-12-21 at 10:08 -0800, Ian Lance Taylor wrote:
> 
> First, let's go ahead and define an orphan.  An orphan is an SSA_NAME
> which has SSA_NAME_DEF_STMT pointing to a statement which does not
> appear in the IL.

That's fine, that simply changes to the question to how you can tell,
given an SSA_NAME, whether it is an orphan or not.


> Note we'd still have the problem of orphans for which I see only two
> solutions.
> 
> First, we bite the bullet and find every point where we're not releasing
> orphan and we make failure to release a dead SSA_NAME an error (which we
> can check during the IL scan as part of verify_ssa).  The advantage is
> we know at any point the set SSA_NAMEs which appear in the IL and we
> have very clearly defined rules for dealing with SSA_NAMEs.  They are
> either free or they appear in the IL -- no orphans.
> 
> The alternative is to mark/sweep them between passes.  The obvious
> downside is that within a pass we can get orphans, which I think
> is insufficient for the current needs.

I can't see any reason that we would not want to adopt your first
solution.


> > I think the issue is whether we want to have a way to see all
> > currently valid SSA_NAMEs.  Right now we can have SSA_NAMEs in the
> > list which are no longer used, and we have no way to tell whether they
> > are used or not.  Thus the only way to see all valid SSA_NAMEs is to
> > walk the code.
> Depends on your definition of valid :-)  Until now we've allowed 
> valid to include orphan SSA_NAMEs.  That's far from ideal.  But
> it's worked marginally until now.
> 
> Note that an orphan SSA_NAME should still have a TREE_CHAIN which
> points to a "valid" statement node.  God help you if you try to
> interpret anything inside that statement node though.

Right, and since you currently can't tell whether an SSA_NAME is an
orphan or not, that makes the distinction currently useless.

Ian

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Daniel Berlin]

On 12/21/06, Robert Kennedy <[EMAIL PROTECTED]> wrote:

> Robert, can you attach the testcase you've been working with?

One testcase is libstdc++-v3/libsupc++/vec.cc from mainline.

But it compiles without trouble unless you add verification or a walk
over the SSA_NAMEs at the right time.

> 1. We replace all uses of a phi node with something else
> 2. We then call remove_phi_node with false as the last parameter (only
> 3 places in the compiler), which ends up destroying the phi node but
> not releasing the LHS name (since this is what the last parameter says
> whether to do).

That's right. Zdenek recommended that I change one of those places
(the one in tree_merge_blocks that you quoted) to "true", but doing
that causes some other code of his to break. I haven't analyzed why he
needs those things to stay around, but I suspect it's because -- for a
while, anyway -- he needs the DEF_STMT for something that's been
removed.


You can't change the last parameter to true in the if's true branch,
but you can in the else branch.
He's reusing the phi result's ssa_name on the true branch for a
statement copy, which will set the def_stmt to something valid.

I.E. this should work:

 if (!may_replace_uses)
{
  gcc_assert (is_gimple_reg (def));

  /* Note that just emitting the copies is fine -- there is no problem
 with ordering of phi nodes.  This is because A is the single
 predecessor of B, therefore results of the phi nodes cannot
 appear as arguments of the phi nodes.  */
  copy = build2_gimple (GIMPLE_MODIFY_STMT, def, use);
  bsi_insert_after (&bsi, copy, BSI_NEW_STMT);
  SSA_NAME_DEF_STMT (def) = copy;
   remove_phi_node (phi, NULL, false);
 }
 else
 {
replace_uses_by (def, use);
   remove_phi_node (phi, NULL, true);
 }



-- Robert

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

> Something I forgot to add in my previous message.  Notice that it is not 
> altogether rare to find cases where we have more SSA names than 
> statements.  Are you walking the SSA names because you assume it's 
> always shorter than walking the statements?

No. I'm walking the SSA names because logically that's what the
algorithm is interested in. At that level, the algorithm doesn't care
about statements.

-- Robert

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Diego Novillo]

Robert Kennedy wrote on 12/21/06 15:01:
Something I forgot to add in my previous message.  Notice that it is not 
altogether rare to find cases where we have more SSA names than 
statements.  Are you walking the SSA names because you assume it's 
always shorter than walking the statements?


No. I'm walking the SSA names because logically that's what the
algorithm is interested in. At that level, the algorithm doesn't care
about statements.

OK.  Good enough.  To fix this bug, I also suggest what Jeff and Ian 
have been discussing:


1- A verifier in verify_ssa

2- Fix bugs found in #1 by making sure that every time we remove a 
statement, the SSA_NAME_DEF_STMT of all the affected names is changed to 
point to an empty statement.

Re: GCC optimizes integer overflow: bug or feature?

[Joseph S. Myers]

On Thu, 21 Dec 2006, Paul Eggert wrote:

> But because bigtime_test wants an int, this causes the test
> program to compute the equivalent of (int) ((unsigned int)
> INT_MAX + 1), and C99 says that if you cannot assume
> wrapping semantics this expression has undefined behavior in
> the common case where INT_MAX < UINT_MAX.

Conversion of out-of-range integers to signed types is 
implementation-defined not undefined, and GCC duly documents the modulo 
semantics for that conversion.  I don't know if you have to deal with 
compilers applying different semantics there, but shared overflow checking 
functions in gnulib could deal with the differences between compilers.

(Conversion of out-of-range floating-point numbers to integer types *is* 
undefined, but Annex F changes this to returning an unspecified value so 
bounding the possible behavior, and I believe GCC follows Annex F for 
this: it's useful not to have to guarantee any particular result, since 
different machines have conversion instructions that may do different 
things for out-of-range values, and to be able to return different results 
for compile-time and run-time conversions, but floating-point conversions 
don't have the same scope as integer arithmetic for useful optimization 
based on undefined behavior.)

-- 
Joseph S. Myers
[EMAIL PROTECTED]

Re: GCC optimizes integer overflow: bug or feature?

[Richard B. Kreckel]

Marcin Dalecki wrote:

But the same applies to floating point numbers. There, the situation 
is even better, because nowadays I can rely on a float or double 
being the representation defined in IEEE 754 because there is such 
overwhelming hardware support.



You better don't. Really! Please just realize for example the impact 
of the (in)famous 80 bit internal (over)precision of a

very common IEEE 754 implementation...



Well, I know. Which is why I used the term "storage representation" down 
the rest of the paragraph that you decided not to quote. :)


However it's a quite common mistake to forget how "bad" floats 
"model" real numbers.



And it's quite a common mistake to forget how "bad" finite ints 
"model" integer numbers.



No it isn't. Most people don't think in terms of infinite arithmetics 
when programming.
And I hold up that the difference between finite and infinite is 
actually quite a fundamental

concept.



Let us agree to disagree.

However quite a lot of people expect the floating arithmetics rouding 
to give them

well behaved results.



I don't know what you mean by "well behaved" in this context, but I am 
beginning to suspect something: what you were trying to express with 
that algebra argument was a mere gut feeling of yours that there is a 
fundamental need to distinguish between discreet and continous domains. 
Let me just say that "algebra" has not much to do with that distinction 
and is off-topic. Anyway, you are entitled to feel that way or the 
other, but I cannot agree.


Leaving such gut feelings aside, I maintain: GCC has been careful not to 
violate a standard (IEEE 754) that was not binding, but assumed by many 
of its users, unless told otherwise (using -ffast-math). Now it is 
violating another standard (LIA-1) that is not binding, but assumed by 
many of its users, unless explicitly told to follow that standard (with 
-fwrapv). That is A Bad Idea.


Cheers
-richy.

--
Richard B. Kreckel

Re: GCC optimizes integer overflow: bug or feature?

[David Nicol]

On 12/20/06, Marcin Dalecki <[EMAIL PROTECTED]> wrote:

You better don't. Really! Please just realize for example the impact
of the (in)famous 80 bit internal (over)precision of a
very common IEEE 754 implementation...

volatile float b = 1.;

if (1. / 3. == b / 3.) {
printf("HALLO!\n")
} else {
printf("SURPRISE SURPRISE!\n");
}


It has always seemed to me that floating point comparison could
be standardized to regularize the exponent and ignore the least significant
few bits and doing so would save a lot of headaches.  Would it really save
the headaches or would it just make the cases where absolute comparisons
of fp results break less often, making the error more intermittent and
thereby worse?  Could a compiler switch be added that would alter
fp equality?

I have argued for "precision" to be included in numeric types in other forae
and have been stunned that all except people with a background in Chemistry
find the suggestion bizarre and unnecessary; I realize that GCC is not really
a good place to try to shift norms; but on the other hand if a patch was to
be prepared that would add a command-line switch (perhaps -sloppy-fpe and
-no-sloppy-fpe) that would govern wrapping ((fptype) == (fptype)) with something
that threw away the least sig. GCC_SLOPPY_FPE_SLOP_SIZE bits in
the mantissa, would it get accepted or considered silly?

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Robert Kennedy]

> You can't change the last parameter to true in the if's true branch.

Ouch. Duh. Thanks!

The worst of it is, Zdenek sent me a patch, and not only did I
misunderstand it, I then transcribed it wrong based on my
misunderstanding. Oh well. Thanks for guessing my mistake.

-- Robert

Re: question from imobilien

[Manuel López-Ibáñez]

On 21/12/06, Janis Johnson <[EMAIL PROTECTED]> wrote:

On Wed, Dec 20, 2006 at 03:06:34PM +0100, Jan Eissfeld wrote:
> Hi,
>
> PR19978 reports that some overflow warnings are emitted multiple times. Like 
for example,
>
> test.c:6: warning: integer overflow in expression
> test.c:6: warning: integer overflow in expression
> test.c:6: warning: integer overflow in expression
>
> The current testsuite will match any number of those to a single {
> dg-warning }. I don't know whether this is a known limitation, a bug
> on the testsuite or it just needs some magic.
>
> How could I test that exactly one warning was emitted?

See http://gcc.gnu.org/ml/gcc/2006-12/msg0.html for an ugly solution,
and the rest of the thread for problems with this approach.  The check
for getting the warning must be in a separate test from the check for
multiple warnings.

Janis



Or even better, see
http://gcc.gnu.org/ml/gcc-patches/2006-12/msg00588.html which fixes
that PR and adds testcases to prevent regressing on this.

It is still awaiting for review, though. ;-)

Re: GCC optimizes integer overflow: bug or feature?

[Marcin Dalecki]

On 2006-12-21, at 22:19, David Nicol wrote:



It has always seemed to me that floating point comparison could
be standardized to regularize the exponent and ignore the least  
significant

few bits and doing so would save a lot of headaches.


Well actually it wouldn't "save the world". However adding an
op-code implementing: x eqeps y <=> |x - y| < epsilion, would be  
indeed helpful.
Maybe some m-f has already patented it, and that's the reason we  
don't see it

already done. But that's of course only me speculating.


Would it really save
the headaches or would it just make the cases where absolute  
comparisons

of fp results break less often, making the error more intermittent and
thereby worse?  Could a compiler switch be added that would alter
fp equality?


However in numerical computation there isn't really a silver bullet  
to be found.
If you are serious about it you simply do the hard work - which is  
the numerical
analysis of your algorithms with respect to computational stability.  
That's the
real effort and perhaps the reason, why the peculiarities of the FP  
implementations

are not perceived as problematic.

I have argued for "precision" to be included in numeric types in  
other forae
and have been stunned that all except people with a background in  
Chemistry
find the suggestion bizarre and unnecessary; I realize that GCC is  
not really
a good place to try to shift norms; but on the other hand if a  
patch was to
be prepared that would add a command-line switch (perhaps -sloppy- 
fpe and
-no-sloppy-fpe) that would govern wrapping ((fptype) == (fptype))  
with something

that threw away the least sig. GCC_SLOPPY_FPE_SLOP_SIZE bits in
the mantissa, would it get accepted or considered silly?


No that's not sufficient. And a few bit's of precision are really not  
the
center-point of numerical stability of the overall calculation.  
Please look up
as an example a numerical phenomenon which is usually called  
"cancelation" to see

immediately why.

Marcin Dalecki

Re: GCC optimizes integer overflow: bug or feature?

[Paul Eggert]

"Joseph S. Myers" <[EMAIL PROTECTED]> writes:

> Conversion of out-of-range integers to signed types is 
> implementation-defined not undefined,

Thanks for the correction; I keep forgetting that.  However,
a conforming implementation is allowed to raise a signal for
those conversions, which could break the code in question,
i.e., it could cause the test to report the wrong result.
So the distinction between undefined and
implementation-defined behavior doesn't much matter here.
(Presumably the code could work around the problem by
trapping the signal, but that is another can of porting
worms.)

I daresay many conversions of out-of-range values to signed
integers are in a similar boat.

Re: Char shifts promoted to int. Why?

[Ayal Zaks]

>Something along these lines may be useful to do in the vectorizer when we
>get code like this:
>  > ((char)x) = ((char)( ((int)((char)x)) << ((int)c) ) )
>and don't feel like doing all the unpacking of chars to ints and then
>packing the ints to chars after the shift. An alternative could be to
>transform the above pattern to:
>  char_x1 = 0
>  char_x2 = char_x << c
>  char_x = ((int)c < size_of_char) ? char_x2 : char_x1
>and vectorize that (since we already know how to vectorize selects).

Alternatively, do
  char_c2 = (c < size_of_char ? c : 0)
  char_x2 = char_x << char_c2
which is like saturating the shift amount.

You could also try
  char_c2 = min(c, size_of_char)   /* And mask off a bit perhaps.  */
  char_x2 = char_x << char_c2
if you don't have general selects but do have min.

Ayal.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

 On 2006-12-21, at 22:19, David Nicol wrote:


It has always seemed to me that floating point comparison could
be standardized to regularize the exponent and ignore the least  
significant

few bits and doing so would save a lot of headaches.


This would be a real nuisance. This myth that you should
never compare fpt numbers for absolute equality is nonsense.
There are lots of algorithms where it is legitimate to
compare for absolute equality (various kinds of iterations
that converge reliably to a single bit pattern for example).

It *is* a problem to have the 80-bit stuff intefering (in fact
Kahan pronounced this a bug in a Fortran compiler. Ada gets
around this by providing the 'Machine attribute that forces
a fpt number to a canonical machine representation in its type,
but it's a bit cumbersome. Note that the use of SSE on the x86
eliminates this problem.

> Marcin Dalecki:


Well actually it wouldn't "save the world". However adding an
op-code implementing: x eqeps y <=> |x - y| < epsilion, would be  
indeed helpful.
Maybe some m-f has already patented it, and that's the reason we  
don't see it

already done. But that's of course only me speculating.


There would be nothing wrong in having such an operation, but
it is not equality!

> David Nicol wrote:


I have argued for "precision" to be included in numeric types in  
other forae
and have been stunned that all except people with a background in  
Chemistry
find the suggestion bizarre and unnecessary; 


if you are stunned by this, you need to study more about
computer arithmetic (btw I have a PhD in chemistry :-))

I realize that GCC is  
not really

a good place to try to shift norms;


especially if the attempt is misguided. Floating-point semantics
in languages have been studied by a lot of experts, they are not
accidental!


Marcin Dalecki:

No that's not sufficient. And a few bit's of precision are really not  
the
center-point of numerical stability of the overall calculation.  
Please look up
as an example a numerical phenomenon which is usually called  
"cancelation" to see

immediately why.


indeed!

Re: GCC optimizes integer overflow: bug or feature?

[Marcin Dalecki]

On 2006-12-21, at 23:17, Robert Dewar wrote:



> Marcin Dalecki:

Well actually it wouldn't "save the world". However adding an
op-code implementing: x eqeps y <=> |x - y| < epsilion, would be   
indeed helpful.
Maybe some m-f has already patented it, and that's the reason we   
don't see it

already done. But that's of course only me speculating.


There would be nothing wrong in having such an operation, but
it is not equality!


Of course I didn't think about a substitute for ==. Not! However I think
that checks for |x-y| < epsilion, could be really given a significant  
speed edge

if done in a single go in hardware.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Marcin Dalecki wrote:

On 2006-12-21, at 23:17, Robert Dewar wrote:


Marcin Dalecki:
Well actually it wouldn't "save the world". However adding an
op-code implementing: x eqeps y <=> |x - y| < epsilion, would be   
indeed helpful.
Maybe some m-f has already patented it, and that's the reason we   
don't see it

already done. But that's of course only me speculating.

There would be nothing wrong in having such an operation, but
it is not equality!


Of course I didn't think about a substitute for ==. Not! However I think
that checks for |x-y| < epsilion, could be really given a significant  
speed edge

if done in a single go in hardware.


I don't see this as viable, the choice of epsilon is too application
dependent.

gcc-4.0-20061221 is now available

[gccadmin]

Snapshot gcc-4.0-20061221 is now available on
  ftp://gcc.gnu.org/pub/gcc/snapshots/4.0-20061221/
and on various mirrors, see http://gcc.gnu.org/mirrors.html for details.

This snapshot has been generated from the GCC 4.0 SVN branch
with the following options: svn://gcc.gnu.org/svn/gcc/branches/gcc-4_0-branch 
revision 120122

You'll find:

gcc-4.0-20061221.tar.bz2  Complete GCC (includes all of below)

gcc-core-4.0-20061221.tar.bz2 C front end and core compiler

gcc-ada-4.0-20061221.tar.bz2  Ada front end and runtime

gcc-fortran-4.0-20061221.tar.bz2  Fortran front end and runtime

gcc-g++-4.0-20061221.tar.bz2  C++ front end and runtime

gcc-java-4.0-20061221.tar.bz2 Java front end and runtime

gcc-objc-4.0-20061221.tar.bz2 Objective-C front end and runtime

gcc-testsuite-4.0-20061221.tar.bz2The GCC testsuite

Diffs from 4.0-20061214 are available in the diffs/ subdirectory.

When a particular snapshot is ready for public consumption the LATEST-4.0
link is updated and a message is sent to the gcc list.  Please do not use
a snapshot before it has been announced that way.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Marcin Dalecki wrote:


Of course I didn't think about a substitute for ==. Not! However I think
that checks for |x-y| < epsilion, could be really given a significant  
speed edge

if done in a single go in hardware.


One thing to ponder here is that "thinks" like this are what lead
to CISC instruction messes. It just seems obvious to people that
it will help efficiency to have highly specialized instructions,
but in practice they gum up the architecture with junk, and a
careful analysis shows that the actual gain is small at best.
How many applications spend a significant amount of time doing
such an epsilon test -- best guess: none.

Re: GCC optimizes integer overflow: bug or feature?

[Marcin Dalecki]

On 2006-12-21, at 23:42, Robert Dewar wrote:


Marcin Dalecki wrote:

Of course I didn't think about a substitute for ==. Not! However I  
think
that checks for |x-y| < epsilion, could be really given a  
significant  speed edge

if done in a single go in hardware.


One thing to ponder here is that "thinks" like this are what lead
to CISC instruction messes. It just seems obvious to people that
it will help efficiency to have highly specialized instructions,
but in practice they gum up the architecture with junk, and a
careful analysis shows that the actual gain is small at best.
How many applications spend a significant amount of time doing
such an epsilon test -- best guess: none.


Well actually you are interpreting too much wight in to my speculations.
I was just curious whatever similar analysis has been already  
seriously done?

And after all, well the most commonly used instruction set architectures
for numerical calculations, are not exactly what one would call "lean  
and mean"...

People simply use what's already there and what is cheap.
Or could you imagine something uglier then the stacked/MMX/XMM/SSE4  
mess?
After all even the supposedly competent instructions set designers  
admitted their previous

fallacy by the introduction of SSE2.

Marcin Dalecki

Re: question from imobilien

[Janis Johnson]

On Thu, Dec 21, 2006 at 09:43:26PM +, Manuel López-Ibáñez wrote:
> On 21/12/06, Janis Johnson <[EMAIL PROTECTED]> wrote:
> >On Wed, Dec 20, 2006 at 03:06:34PM +0100, Jan Eissfeld wrote:
> >> Hi,
> >>
> >> PR19978 reports that some overflow warnings are emitted multiple times. 
> >Like for example,
> >>
> >> test.c:6: warning: integer overflow in expression
> >> test.c:6: warning: integer overflow in expression
> >> test.c:6: warning: integer overflow in expression
> >>
> >> The current testsuite will match any number of those to a single {
> >> dg-warning }. I don't know whether this is a known limitation, a bug
> >> on the testsuite or it just needs some magic.
> >>
> >> How could I test that exactly one warning was emitted?
> >
> >See http://gcc.gnu.org/ml/gcc/2006-12/msg0.html for an ugly solution,
> >and the rest of the thread for problems with this approach.  The check
> >for getting the warning must be in a separate test from the check for
> >multiple warnings.
> >
> >Janis
> >
> 
> Or even better, see
> http://gcc.gnu.org/ml/gcc-patches/2006-12/msg00588.html which fixes
> that PR and adds testcases to prevent regressing on this.
> 
> It is still awaiting for review, though. ;-)

I hadn't noticed that it's for the same PR!

Janis

Re: running bprob.exp tests in a cross-testing environment

[Janis Johnson]

On Thu, Dec 21, 2006 at 10:00:47AM +1100, Ben Elliston wrote:
> On Thu, 2006-12-21 at 09:56 +1100, Ben Elliston wrote:
> 
> > After some digging, I managed to work out why: the gcov runtime code
> > wants to create the .gcda file in the same directory that the object
> > file was created on the build system.  Unless the same directory
> > structure exists on the target, the gcov runtime code just skips writing
> > out the data file on exit.
> 
> To be more precise, the gcov runtime first tries to create the required
> path, but this is unlikely to succeed if it requires creating a new
> directory under / (which only root can typically do).  If it cannot
> create the full path before creating the data file, the gcov runtime
> code will just silently fail.

Ben, you understand what's going on here much better than I do, so if
you come up with a patch that works it's pre-approved.  Otherwise I
can take a look in a couple of weeks.

Janis

Re: GCC optimizes integer overflow: bug or feature?

[Ian Lance Taylor]

Paul Eggert <[EMAIL PROTECTED]> writes:

> That probably sounds vague, so here's the code that beta
> gcc -O2 actually broke (which started this whole thread):
> 
>   int j;
>   for (j = 1; 0 < j; j *= 2)
>   if (! bigtime_test (j))
> return 1;

It's interesting to note that in gcc 4.1 this turns into, essentially,

  for (j = 1, i = 0; i != 31; j *= 2, ++i)
   ...

That is, gcc 4.1 assumes wrapping semantics and works out that the
loop will iterate (up to) 31 times (I'm testing on a 32-bit system,
obviously).  This is also what mainline gcc does if you use -fwrapv.

> Here it is obvious to a programmer that the comparison is
> intended to do overflow checking, even though the test
> controls the loop.  Can gcc -O2 be made "smart" enough to
> notice this, and not optimize away the test?

Although this is in a loop, the test is actually being removed by VRP.
VRP cunningly sees that j has the range [1, +INF] in all cases.
Therefore, 0 < j is always true, and the test can be removed.  Using
the -fno-tree-vrp option causes the code to work as the programmer
expected.

Basically, VRP sees that j > 0, because the loop condition already
held.  Then it multiplies it by two.  Without -fwrapv, it concludes
that j > 0 is still true.  Then it tests the loop condition again, and
discovers that it is definitely true.  This is more or less the sort
of thing which VRP is supposed to do.

We could disable VRP's assumptions about signed overflow.  I don't
know what else we could do to fix this case.  I don't even know how we
could issue a useful warning.  Perhaps there is a way.

> Another question for the GCC experts: would it fix the bug
> if we replaced "j *= 2" with "j <<= 1" in this sample code?

Well, mainline VRP isn't clever enough to understand that case.  But
it doesn't make the code any more defined.  A left shift of a signed
value to a value which can not be represented in the signed type is
also undefined (C99 6.5.7).


> I ask the latter question partly because nobody has yet
> proposed a portable fix for this bug.  The patch proposed in
> 
> worked for Ralf, but it does not work in general.  It
> attacks the problem by changing "int j" to "unsigned j".
> But because bigtime_test wants an int, this causes the test
> program to compute the equivalent of (int) ((unsigned int)
> INT_MAX + 1), and C99 says that if you cannot assume
> wrapping semantics this expression has undefined behavior in
> the common case where INT_MAX < UINT_MAX.

No, as Joseph says, conversion from a unsigned value to a signed value
is implementation defined (C99 6.3.1.3).

Ian

Re: GCC optimizes integer overflow: bug or feature?

[Joseph S. Myers]

On Thu, 21 Dec 2006, Ian Lance Taylor wrote:

> > Another question for the GCC experts: would it fix the bug
> > if we replaced "j *= 2" with "j <<= 1" in this sample code?
> 
> Well, mainline VRP isn't clever enough to understand that case.  But
> it doesn't make the code any more defined.  A left shift of a signed
> value to a value which can not be represented in the signed type is
> also undefined (C99 6.5.7).

As noted, it's only undefined in C99 not C90 and we document that this 
undefinedness isn't used at present; and non-front-end code can't use 
flag_isoc99 since it isn't available in non-C-family front ends.

-- 
Joseph S. Myers
[EMAIL PROTECTED]

Re: GCC optimizes integer overflow: bug or feature?

[Paul Eggert]

Ian Lance Taylor <[EMAIL PROTECTED]> writes:

> We could disable VRP's assumptions about signed overflow.  I don't
> know what else we could do to fix this case.  I don't even know how we
> could issue a useful warning.  Perhaps there is a way.

It is a knotty problem.  Thanks for thinking about it.

I'm Handwaving with a capital H here, but one possibility is
for plain -O2 to keep VRP, but disable its assumption about
signed overflow when attempting to optimize away a
comparison that comes directly from the user's code (as
opposed to a comparison coming from subscript checking and
the like).

Here's another wild idea.  Perhaps GCC could add an option
"-fundefinedv" to request for aggressive optimizations
assuming that the program will never have an signed integer
overflow.  I.e., if you want the optimization that is
causing trouble here, you would specify "-O2 -fundefinedv";
but the default would be to disable this particular
troublesome optimization.

Re: GCC optimizes integer overflow: bug or feature?

[Denis Vlasenko]

On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
> There are a lot of 100.00% safe optimizations which gcc
> can do. Value range propagation for bitwise operations, for one

Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):

# cat tt.c
int f(char *p)
{
if (p[0] == 1 && p[1] == 2) return 1;
return 0;
}

# gcc -O2 -S -fomit-frame-pointer tt.c

# cat tt.s
.file   "tt.c"
.text
.p2align 2,,3
.globl f
.type   f, @function
f:
movl4(%esp), %eax
cmpb$1, (%eax)
je  .L2
xorl%eax, %eax
ret
.p2align 2,,3
.L2:
cmpb$2, 1(%eax)
sete%al
movzbl  %al, %eax
ret
.size   f, .-f
.ident  "GCC: (GNU) 4.2.0 20061128 (prerelease)"
.section.note.GNU-stack,"",@progbits

Re: GCC optimizes integer overflow: bug or feature?

[Paul Brook]

On Friday 22 December 2006 00:58, Denis Vlasenko wrote:
> On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
> > There are a lot of 100.00% safe optimizations which gcc
> > can do. Value range propagation for bitwise operations, for one
>
> Or this, absolutely typical C code. i386 arch can compare
> 16 bits at a time here (luckily, no alighment worries on this arch):
>
> int f(char *p)
> {
>     if (p[0] == 1 && p[1] == 2) return 1;
>     return 0;
> }

Definitely not 100% safe. p may point to memory that is sensitive to the 
access width and/or number of accesses. (ie. memory mapped IO).

Paul

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paul Brook wrote:

On Friday 22 December 2006 00:58, Denis Vlasenko wrote:

On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:

There are a lot of 100.00% safe optimizations which gcc
can do. Value range propagation for bitwise operations, for one

Or this, absolutely typical C code. i386 arch can compare
16 bits at a time here (luckily, no alighment worries on this arch):

int f(char *p)
{
if (p[0] == 1 && p[1] == 2) return 1;
return 0;
}


Definitely not 100% safe. p may point to memory that is sensitive to the 
access width and/or number of accesses. (ie. memory mapped IO).


A program that depends on this is plain wrong. There is no guarantee
that memory references are as they appear in the program. For a
non-volatile variable, any such optimization is valid. For instance
if the flow can be used to prove that p[0] is already 1, then there
is no need to repeat the read.


Paul

Re: Reload Pass

[Rajkishore Barik]

Hi,

Thanks very much. I still have doubts on your suggestion:

AFAIK, the back-end pass consists of (in order) : reg move -> insn sched 
-> reg class -> local alloc -> global alloc -> reload -> post-reload.
There are edges from reg move to reg class and reload back to global 
alloc.

In case I want to implement a linear scan which may split live ranges 
(pseudos) into live intervals(smaller pseudos) and allocate different 
registers
for each of them. This process would break the whole loop. 

So, what did you mean by --- "run this pass in between the register 
allocator and
reload, that would probably be doable."?

regards,
Raj


Ian Lance Taylor <[EMAIL PROTECTED]> wrote on 12/21/2006 09:02:04 PM:

> Rajkishore Barik <[EMAIL PROTECTED]> writes:
> 
> > Does anyone know of any document describing (in details) the reload 
phase 
> > of GCC?
> 
> There isn't one.  The closest such document is
> http://gcc.gnu.org/wiki/reload
> which is accurate despite, or perhaps because of, starting out by
> equating reload with Satan.
> 
> > I am planning to write a linear scan reload for GCC (one that does not 

> > take reg_renumber
> > but takes instruction specific register allocation and move 
information). 
> > Can anyone point me
> > to some existing code/literature for this in GCC? 
> 
> There is none.
> 
> If you expect this pass to actually replace reload, then I advise you
> to reconsider.  That would be a hopeless task.  Well, maybe you could
> do it if you restrict yourself to a single architecture.
> 
> If you want to run this pass in between the register allocator and
> reload, that would probably be doable.  Of course, reload will then
> muck up your decisions, and the resulting code will sometimes be worse
> than what you get today.  But it might be an interesting experiment.
> 
> Ian

Re: GCC optimizes integer overflow: bug or feature?

[Gabriel Dos Reis]

Paul Eggert <[EMAIL PROTECTED]> writes:

| Ian Lance Taylor <[EMAIL PROTECTED]> writes:
| 
| > We could disable VRP's assumptions about signed overflow.  I don't
| > know what else we could do to fix this case.  I don't even know how we
| > could issue a useful warning.  Perhaps there is a way.
| 
| It is a knotty problem.  Thanks for thinking about it.
| 
| I'm Handwaving with a capital H here, but one possibility is
| for plain -O2 to keep VRP, but disable its assumption about
| signed overflow when attempting to optimize away a
| comparison that comes directly from the user's code (as
| opposed to a comparison coming from subscript checking and
| the like).

If that is workable, it would be a good compromise.

-- Gaby

Re: GCC optimizes integer overflow: bug or feature?

[Paul Brook]

On Friday 22 December 2006 02:06, Robert Dewar wrote:
> Paul Brook wrote:
> > On Friday 22 December 2006 00:58, Denis Vlasenko wrote:
> >> On Tuesday 19 December 2006 23:39, Denis Vlasenko wrote:
> >>> There are a lot of 100.00% safe optimizations which gcc
> >>> can do. Value range propagation for bitwise operations, for one
> >>
> >> Or this, absolutely typical C code. i386 arch can compare
> >> 16 bits at a time here (luckily, no alighment worries on this arch):
> >>
> >> int f(char *p)
> >> {
> >> if (p[0] == 1 && p[1] == 2) return 1;
> >> return 0;
> >> }
> >
> > Definitely not 100% safe. p may point to memory that is sensitive to the
> > access width and/or number of accesses. (ie. memory mapped IO).
>
> A program that depends on this is plain wrong. There is no guarantee
> that memory references are as they appear in the program.  For a 
> non-volatile variable, any such optimization is valid. For instance
> if the flow can be used to prove that p[0] is already 1, then there
> is no need to repeat the read.

Who says the optimisation is valid? The language standard?

The example was given as something that's 100% safe to optimize. I'm 
disagreeing with that assertion. The use I describe isn't that unlikely if 
the code was written by someone with poor knowledge of C.

My point is that it's not that hard to invent plausible code that "breaks" 
when pretty much any transformation is applied. We have to decide how close 
to the standard we want to fly.

"Optimization should never change the behavior of any program accepted by the 
compiler" is not a useful constraint for an optimizing compiler. If program 
behavior includes the ability to debug the program, then I'd go as far as 
saying this should be the definition of -O0.

"Optimization should never change the behavior of a valid program" is useful 
definition because it forces you to define what constitutes a valid program.


There's actually a much better reason why the transformation is not safe. 
Consider a data structure where a byte of 1 indicates the end of the object. 
Under normal circumstances short-circuiting of the && operator prevents 
anything bad happening. If you merge the two accesses you've just read past 
the end of the object and all kinds of bad things may happen (eg. a 
segfault).

Paul

P.S. I think I'm repeating myself now, so this is the last time I intend to 
comment on this thread.

Re: GCC optimizes integer overflow: bug or feature?

[Robert Dewar]

Paul Brook wrote:


Who says the optimisation is valid? The language standard?

The example was given as something that's 100% safe to optimize. I'm 
disagreeing with that assertion. The use I describe isn't that unlikely if 
the code was written by someone with poor knowledge of C.


My point is that it's not that hard to invent plausible code that "breaks" 
when pretty much any transformation is applied. We have to decide how close 
to the standard we want to fly.


I did not find that plausible at all, for someone to depend on memory
mapped references without using volatile is indeed such junk code that
we don't need to care about it.

"Optimization should never change the behavior of a valid program" is useful 
definition because it forces you to define what constitutes a valid program.


No, no, let's not start calling these programs that violate the standard
valid. That's going much too far. Also, sometimes code is inherently
non-deterministic, so you have to be careful talking about change of
behavior.

"Optimization should never result in violating the required semantics of
a valid (standard) C program"

is of course criterion 1

Criterion 2 is something like "Optimization should not cause non-valid
non-standard programs to fail as a result of using a common idiom, which
though non-standard is generally expected to "work", unless the 
optimization can be demonstrated to be valuable enough to be worth

generating the effective incompatibility with expected practice"

is a half baked statement of criterion 2 (and it is not so easy to
bake this one!)

There's actually a much better reason why the transformation is not safe. 
Consider a data structure where a byte of 1 indicates the end of the object. 
Under normal circumstances short-circuiting of the && operator prevents 
anything bad happening. If you merge the two accesses you've just read past 
the end of the object and all kinds of bad things may happen (eg. a 
segfault).


You may well know that it is safe to go one past the last object 
(generally this will be the case, because of the strange semantics

of being allowed to address past the last byte). You do indeed have
to be careful of this

P.S. I think I'm repeating myself now, so this is the last time I intend to 
comment on this thread.


OK!

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Jeffrey Law]

On Thu, 2006-12-21 at 14:05 -0500, Diego Novillo wrote:
> In any case, that is not important.  I agree that every SSA name in the 
> SSA table needs to have a DEF_STMT that is either (a) an empty 
> statement, or, (b) a valid statement still present in the IL.
Just to be 100% clear.  This is not true at the current time; see the
discussion about the sharing of a single field for TREE_CHAIN and
SSA_NAME_DEF_STMT.  If you want to make that statement true, then
you need to fix both the orphan problem and the sharing of a field
for SSA_NAME_DEF_STMT and TREE_CHAIN.
.
> 
> Frankly, I'm a bit surprised that we are running into this. I'd like to 
> see a test case, if you have one.
I'm not surprised at all.  We've never systematically tried to identify
leaks of SSA_NAMEs.

Jeff

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Jeffrey Law]

On Thu, 2006-12-21 at 20:18 +0100, Zdenek Dvorak wrote:

> I think this might be a good idea.  I think that this requires
> a lot of changes (basically going through all uses of bsi_remove
> and remove_phi_node and checking them), but it would be cleaner
> than the current situation.
Agreed.  Tedious work, but it shouldn't be terribly difficult (famous
last words).


> It should be however easy to add verification to verify_ssa, so
> this project should be fairly straightforward (I hope).
The verify step is relatively simple.

  FOR_EACH_BB
FOR_EACH_STMT
  mark any SSA_NAMEs in stmt

  FOR_EACH_SSA_NAME
if (!marked && !in_freelist)
  checking failure




jeff

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Jeffrey Law]

On Thu, 2006-12-21 at 10:58 -0800, Robert Kennedy wrote:
> > Right now we can have SSA_NAMEs in the
> > list which are no longer used, and we have no way to tell whether they
> > are used or not.  Thus the only way to see all valid SSA_NAMEs is to
> > walk the code.
> 
> To wit: are there iteration macros somewhere that will help me walk
> the code while abstracting away all the ugly details like stmt/bb
> boundaries, etc.?
Not really.  Note that based on the ongoing discussion any such code
would have a short life since it sounds like the general direction is
to fix this long standing issue.
jeff

Re: SSA_NAMES: should there be an unused, un-free limbo?

[Jeffrey Law]

On Thu, 2006-12-21 at 10:54 -0800, Robert Kennedy wrote:
> > In this case this isn't true, because we have code that orphans ssa
> > names without releasing them.
> > I'm sure Robert will explain further details in a few moments :)
> 
> Actually you explained all the relevant details. The question is
> whether it should be allowed or not. So far almost everyone seems to
> think not.
More correctly, it has been allowed in the past, but the consensus that
seems to be forming is to disallow it in the future.

jeff

Re: GCC optimizes integer overflow: bug or feature?

[Roberto Bagnara]

Paul Eggert wrote:
> Also, such an approach assumes that unsigned long long int
> has at least as many bits as long long int.  But this is an
> unportable assumption; C99 does not require this.  We have
> run into hosts where the widest signed integer type has much
> greater range than the widest unsigned type.  I hope these
> hosts go away in the long run, but they're in production use
> today.  (The platform I'm thinking of is Tandem NSK/OSS.)

Is this correct?  Doesn't C99's 6.2.5#6 mandate that unsigned
long long int has exactly the same number of bits as long long int?
Perhaps you mean that in Tandem NSK/OSS unsigned long long ints
do not use several bits of the representation?
Am I missing something else?
All the best,

Roberto


ISO/IEC 9899:1999 6.2.5

[...]

4 There are five standard signed integer types, designated as signed
  char, short int, int, long int, and long long int. [...]

[...]

6 For each of the signed integer types, there is a corresponding (but
  different) unsigned integer type (designated with the keyword
  unsigned) that uses the same amount of storage (including sign
  information) and has the same alignment requirements. [...]

[...]


--
Prof. Roberto Bagnara
Computer Science Group
Department of Mathematics, University of Parma, Italy
http://www.cs.unipr.it/~bagnara/
mailto:[EMAIL PROTECTED]

Re: GCC optimizes integer overflow: bug or feature?

[Paul Eggert]

Roberto Bagnara <[EMAIL PROTECTED]> writes:

> (The platform I'm thinking of is Tandem NSK/OSS.)
>
> Is this correct?  Doesn't C99's 6.2.5#6 mandate that...

This is straying from the subject of GCC and into the
problems of writing portable C code, but since you asked

The Tandem NSK/OSS environment does not claim full
conformance to C99.  The NSK/OSS community is conservative
(fault-tolerance does that do you :-) and has introduced
only some C99 features, more as time progresses.  The
NSK/OSS developers did not introduce 64-bit unsigned int
until last year.  I'm no expert in the area, but I'd guess
that most NSK/OSS production shops are still running older
releases, which have 64-bit signed int but only 32-bit
unsigned int.