[3.4 PATCH] PR c++/20995: Type-unsafe trees for templates

[Roger Sayle]

On Sun, 24 Apr 2005, Mark Mitchell wrote:
> Roger Sayle wrote:
> > The following patch is my proposed solution for PR c++/20995.  Looking
> > through the code in the C++ front-end, I'll admit that I'm a bit shocked
> > and in one of those how could C++ templates have ever worked dazes.
>
> That reflects a fundamental on your part to understand how, or perhaps
> why, the C++ front end works the way it does.  That's not meant as an
> insult; I'm not claiming it's obvious.

None taken!  You're quite right, the misunderstanding has been mine all
along.  Investigating this PR has been a personal eye-opening "a-ha"
experience for me.  I realize that obviously the C++ front-end maintainers
fully understand the current implementation from a high-level perspective,
it's just in all of our/my previous discussions on the g++ front-end's
interaction with the middle-end, I've had a slightly distorted view due
to incorrect assumptions of how things were intended to work.

In my defense, my misunderstanding of how C++ works is based largely on
reading the code, and as you point out until recently a large fraction
of this code has been incorrect, but lucky.  All of the g++ interactions
with fold, prior to gcc 4.0 give a disceptive picture of the "intended"
interactions between the two.  "Of course, template trees are valid
generic, or you obviously wouldn't be calling fold on them" logic.


I should probably apologise.  In previous discussions you've hinted
and I've agreed that folding should probably occur as a follow-up
pass immediately before gimplification.  My perspective was that this
was an arbitrary design choice to be made by the front-end.  For
example, the C front-end could adopt an identical strategy, or the
C++ could optionally keep both a folded and unfolded tree at parse
time.  Indeed, the current (read 3.x) behaviour seemed to work well
[OpenEye have several hundred thousand lines of C++ code that compile
flawlessly with g++].  What's only now clear, is that for templates
atleast, the 3.x approach of folding at parse-time is fundamentally
broken, but we've been lucky for years due to fold's previous tolerance
of type mismatches, and the fact that most well-formed template code
shouldn't trigger these issues.


I still think that restricted folding is possible during parsing,
provided that it's done carefully.  For example, for the testcase
attached to the PR, I believe that:

template<int N> void foo()
{
    double d = (N ? 0.0 : 0) + 1;
}

could be simplified to

template<int N> void foo()
{
  double d = 1.0;
}

[or even further].  Current C++ compilers are expected to handle code
and headers with large numbers of template declarations, and the less
space that these templates occupy, the faster the compiler, both from
resident set size issues and from less work at instiation time.


However, as you've been trying to tell me for years and I've just
been to dumb/blind to grasp, the current infrastructure just isn't
set up for this and the existing implementation is misleading.



> Most leaks of uninstantiated templates outside of the front end are
> bugs.  There are exceptions, like calling simple DECL_P-style
> But, as I've explained several times, calling fold from the C++ front
> end proper is a bug anyhow.

Now understood.  This is an artifact of g++'s design decisions.
Correspondingly, calling fold from the C front-end isn't a bug,
at least not from a correctness perspective as it is in C++.
You've been calling it a "bug" all along, to which I've tried
countering that it's a style issue.  But it really is a "bug".


> I'm actually not sure why the issues around fold remain so troubling to
> you.  I understand why you think that fold is valuable, but I'm not sure
> why you think it's something that ought to be called as expressions are
> parsed, rather than at a later point when they are to be presented to
> the middle end.

My misunderstanding has always been to assume that where/when "fold"
was called was a freedom.  Aside from the ability to reproduce the
original input (less pragmas, comments, indentation, etc..), I'd assumed
that g++ had a choice in when it called fold.  With the new APIs,
expressions such as "!!!!!!!!!!!!!x" can be constructed via fold_build1
in less space that GCC has ever used previously.  On the flip side
of the representation issue, PRs, such as PR middle-end/12454, show the
performance impact of the new recursive descent parser's strict adherence
to faithful representation of a grammar compared to the GCC's previous
parser's "massaged grammars".  Whilst admittedly not a fold issue, the
abilty to omit empty scopes when not required is a form of
tree-manipulation that improves the compiler memory usage/performance at
the cost of the fidelity with which the source code is reproduced.


My position previously was there were advantages to calling fold as
well as disadvantages, and that the decision/choice needed to be an
informed one.  What I now understand, is that in the case of templates
at least, there currently is no choice.  The C++ front-end can't safely
take advantage of any of the benefits of smaller/canonical
representations.  My words of caution in the past to think carefully
about the decision, were in hindsight pointless, given some of g++'s
preexisting design decisions/constraints.

I might now argue that C++ should probably improve the methods by
which it tracks dependent vs. non-dependent expressions and/or simplify
the large amount of redundant processing it does for no reason on
templates.  For example, build_x_binary_op could probably become
just a call to build2.  But those battles are on completely different
battlefields.


> > For gcc 4.x, this issue has been resolved by Mark's patch for bugzilla
> > PR c++/17642, that introduces a new function fold_if_not_in_template,
> > that avoids ever calling "fold" whilst processing template declarations.
> > That PR was also just another symptom of the fact that g++ doesn't
> > create valid trees for templates until they are instantiated.
>
> The word "symptom" isn't appropriate because there's no "disease" here.
> The behavior you note is by design and identical to the analagous
> behavior in other C++ front ends.  The bug is just that for historical
> reasons we're calling fold at what is clearly the wrong time.


My apologies the word "symptom" is perhaps a bit strong here, and
certainly not intended to imply a disease.  PR c++/17642 was marked
as a 4.0 regression, where in fact the real problem was a fundamental
design flaw that's been in the g++ front-end since it was contributed.
Whilst this may be identical and analogous to other C++ compilers, its
completely unlike any other GCC front-end that uses trees as its internal
representation.  With the possible exception of gcj, which maintains
expression trees where the TREE_TYPE is NULL_TREE.



> I agree that backporting fold_if_not_in_template along with all of its
> uses would be too risky.  But how about just backporting the function
> and using it from the two places you identified?  I expect that would
> work, and would be slightly preferable in that it would reduce
> divergence.  That change is preapproved, assuming it works OK.

This sounds like a excellent recommendation.  I'll give it a try.



Sorry again if my earlier post sounded argumentative.  It was really
just a poorly phrased shriek of "Eureka!".  The complaint by folks that
the C++ front-end is creating trees with mismatched types, implied
the problem was with the "bad trees", when in reality that's intentional
and it's the fact that these mismatched trees shouldn't leak to the
middle-end that's the problem.  Subtle, but it changes everything.

I hope this explains why I may have appeared so pig-headed previously.

Roger
--