Re: Great example of why "everything is a tree" sucks

["Joseph S. Myers" <joseph at codesourcery dot com>]

On Wed, 13 Nov 2013, Steven Bosscher wrote:

> Really the best place to start IMHO would be to evict 'tree' from the
> front ends. That would really be a step towards making the front ends
> independent of the rest of the compiler, and it would simplify changes
> towards static 'tree' types.

 From a C perspective, a useful change that would facilitate moving the IR 
away from tree would be moving most of fold to operate on GIMPLE instead 
of on trees (that is, rewriting it as GIMPLE optimizations; I don't think 
this can be a mechanical refactoring).

There are at least the following types of folding that can get called from 
the C front end:

(a) Folding required for standard language semantics of constant 
expressions.

(b) Other trivial folding (e.g. && || ?: with constant controlling 
expression, even if the ignored half isn't valid in ISO C constant 
expressions; comma operators whose LHS has no side effects; __builtin 
function calls with constant operands; differences of addresses within an 
object with static storage duration).  Needed in many cases for GNU C 
semantics (implementing ISO C constant expression semantics showed that 
many cases did in fact need folding, with just pedwarns-if-pedantic if 
something should be a constant expression but isn't in ISO C terms, 
because code bases such as the Linux kernel used such not-ISO-constant 
expressions in places needing constant expressions).  Needed in some cases 
for ISO C semantics in the standard library (e.g. __builtin_nanf ("") is 
what we provide for a library to define NAN, which must be usable in 
static initializers).

(c) More complicated optimization transforms that aren't really constant 
folding but are done by fold-const.c.

(d) Like (c), but done in convert.c (see convert_to_real for example).

(e) Like (c), but done in the front end (including c-family/ code, see 
shorten_compare).

Types (c), (d) and (e) should become GIMPLE optimizations (everything in 
(a) and (b) should *also* be done on GIMPLE when GIMPLE optimizations 
result in operands being constant, but I hope that's already the case).  
That would massively reduce the amount of folding code called by the C 
front end, so making what's left much easier to reimplement on a better IR 
(the reimplementation would still need to call into language-independent 
code e.g. for built-in functions with constant operands, but I don't think 
that's a problem to handle with different IR in front end and middle end).  
However:

(i) Distinguishing (c), (d) and (e) from (b) can be tricky; GNU/Linux 
distribution rebuilds would be helpful in making sure changes didn't 
remove too much from fold.

(ii) Some places where the C front end calls c_fully_fold before complete 
expressions have been built up are because warnings rely on 
transformations carried out by fold in order to avoid false positives 
(i.e. there were failures of warning testcases unless the folding was 
done).  I think this is generally about warnings relating to implicit 
conversions.  So to the extent that such transformations would otherwise 
fall in (c), (d) or (e), maybe the GIMPLE needs annotating in some way "if 
this conversion can change the numerical value of its operand, give this 
warning", with the warnings then being output after enough optimization 
has taken place.

-- 
Joseph S. Myers
joseph@codesourcery.com