Re: Specification issues

[Norm: please ignore the private copy of this -- I intended to reply to
the list, and for some reason "reply all" failed to do so.]

On Mon, 2005-09-05 at 17:48 -0400, Norman Ramsey wrote:
> I am trying to keep the specification relatively stable, 

Oh, I am all in favor of that, and I do not wish to disrupt or
destabilize!

>  >   I'm thinking here
>  >   about numerical analysis codes, where the front end has carefully
>  >   preserved a user-provided statement of computation order, and the back
>  >   end must not rearrange this inappropriately.
> 
> I'm not quite sure what you're saying here.
> If you are saying 'the C-- back end must not, for purposes of
> optimization, assume that floating-point operations are associative', 
> then we're in violent agreement :-)

Just to be sure we are having the same conversation, let me give a
concrete example:

Traditionally, optimizers have taken two schizophrenically simultaneous
views of floating point computation. One view in which the user input

	((A + B) + (C + D))

is viewed loosely, and another in which it is viewed as a constraint on
operation order. In the first case, it would be permissable to rearrange
the computation as *either* of:

	(((A + B) + C) +D)
or	((A + C) + (B + D))

in the second view, neither rearrangement is permissable.

I believe that (a) it is a legitimate choice for C-- to declare that
such rearrangements are the responsibility of the front end, or (b) it
is legitimate for C-- to provide a means to express which intent was
desired.

In either case, I think this issue is concretely important enough to
warrant mention explicitly. Given your response, I think it should take
the form of a prescriptive constraint in section 7.4. If you will pardon
me for presuming to suggest specifics, I might add a new paragraph in
section 7.4 prior to the current second full paragraph (beginning "Table
2 lists...). This paragraph might read something along the lines of:

  The C-- compiler is free to rearrange and/or optimize expressions
  provided that this rearrangement does not alter the values of
  computational results or the observable sequential control flow.
  For this purpose, rearrangements that would alter the precision of
  results are considered to alter computational results.
  Similarly, rearrangements that would modify the ordering of exception
  generation are considered to modify observable control flow.

Depending on the design objectives, it may also be appropriate to add
some statement of constraint on alterations to the lifetimes of values
under instruction reordering. Given that the scope of local declarations
is the procedure, I'm not sure (i.e. I do not understand) whether the
back end has sufficient lifetime and scoping information to satisfy such
a constraint. I'm thinking here about liveness for purposes of "safe for
space" GC per Appel et al.
  
> If you can suggest a place in the specification for me to put this
> information, I will do so.

I have attempted to suggest one above, but it is *only* a suggestion for
consideration!

>  >   If it is indeed intended to allow the back end this latitude, then
>  >   some mechanism to prevent mishandling is required.
> 
> My thinking is more that the back end should never have this latitude.
> I know there are people out there who like this kind of behavior, and
> maybe one day we will allow a front end to say 'I'm really keen to get
> wrong answers fast; for purposes of optimization, please assume that
> floating-point arithmetic behaves like real-number arithmetic.'  But
> I'm not keen to add such a feature any time soon.

I concur with your intuitions here, but I am also torn. This has the
positive effect of precise behavior, and the potential negative effect
of disrupting language comparison by increasing the burden of
optimization. In spite of this, I believe that yours is the right
position.

The wording that I proposed above, or something like it, will serve to
clarify this.

However: there is another issue that concerns me in this regard. I am
sure that you are familiar with all of the older GC vs. optimization
issues, most notably the problem of iterating pointers that point into
the middle of vectors. I see nothing in the specification that would
either (a) preclude, or (b) remediate the effects of such an
optimization. Did I miss something?

>  > + In order for debugging and related information to be meaningful,
>  >   the specification needs to be clear about the limits of code motion.
>  >   I would suggest a block-structured barrier construct.
>  >   Regardless of debugging, the specification needs to be clearer about
>  >   the degree of code motion that the C-- back end is entitled to
>  >   undertake.
> 
> This is a problem we have failed several times to solve.  We have
> considered barrier constructs, but when we have tried to give them a
> precise semantics, we have succeeded only in choosing between one of
> two evils:
>   * Essentially no code motion
>   * All barrier constructs can be squeezed together and moved to 
>     the code point of your choice
> I have graduate students looking for PhD topics who ought to be aware
> of this problem, but until we have some kind of reasonable solution, 
> I'm reluctant to bake anything into the specification.

Yep. This is a very hard problem. I had a hand in two generations of the
DWARF specification, and I'm *still* not convinced that we got it right.
Since it seems like an active discussion, I will take this up in a
separate line of email. Some of what we learned in DWARF may prove
useful.

>  > + If loop optimizations are contemplated, then I question the
>  >   wisdom of removing loop primitives from the language. Perhaps
>  >   the state of the art has changed, but my experience was that
>  >   loop rediscovery was painful, and that you really want to do
>  >   this to guide the optimizer in attempting strength reduction,
>  >   hoisting, and so forth.
> 
> We're drawing on the work of Jack Davidson, who has shown that it's
> actually pretty easy to do loop optimization on very low-level
> intermediate codes.  It's been years since I looked at the details,l
> but if I remember correctly, given a control-flow graph it's fairly
> straightforward to compute a dominator tree and then use it to
> identify loops.  At present, our implementation has the dominator
> tree, but we haven't actually written any interesting loop
> optimizations.

Jack is a very smart guy, and I will be interested to see where this
goes. The position you outline is inconsistent with my memory of
discussions with Monica Lam circa 1990. It is not clear to me in
hindsight whether the issue then was the compute cost of rediscovering
the dominator graphs (which wouldn't be an issue now) or some other,
more fundamental issue. I have memories of this being an issue in the
implementation of DOACROSS like constructs, and in optimizations that
spanned multiple iterations. I'ld have to go back to the papers then in
vogue to recover details, and my attention is elsewhere at present. I'm
sure Jack will remember the relevant work off the top of his head, and I
would definitely trust his recollection ahead of my own on this subject.

>  > + The current #line directive is horribly bad. We would have killed it
>  >   at Bell Labs 20 years ago if we could have figured out how to do so
>  >   compatibly. Don't replicate our error purely for the sake of
>  >   verisimilitude. ADD A CHARACTER OFFSET! Allow -1 for "unspecified".
> 
> I take your point, but I'm reluctant.  That we support #line is
> primarily a concession to people who are really, really keen to push
> their C-- code through cpp.  C-- is intended to be generated by a
> compiler, not to be preprocessed, and I'm reluctant to invest even
> more effort in a strategy that I think is bad.

The current outcome of your policy is to force the front end to throw
away information that it definitively has. Unless you can give a
compelling reason for throwing my front end content away, you shouldn't
make me do it.

>  > + A directive is needed to allow (line, offset, file) information
>  >   to be associated with labels so that source locations of labels
>  >   can be accurately represented.
> 
> That would be one of the many uses of the 'span' directive.

Interesting. Can you give a concrete example? It was not my intention (I
thought) to label spans, but rather to label sequence points. However, I
am tacitly assuming that there is a 1:1 inverse mapping from instruction
addresses to lines, which is untrue under code motion assumptions.

>  > + Since register selection is deferred to the C-- implementation,
>  >   serious debugging support requires that the C-- compiler emit
>  >   detailed location maps for variables, of the form:
>  > 
>  >     (PC start, PC end, variable, location)
>  > 
>  >   This can be represented compactly, but lesser information
>  >   is insufficient for debugging in the face of code rearrangement.
>  > 
>  >   Such n-tuples should be present for all live addresses. The
>  >   absence of a statement of location should be interpreted by
>  >   the debugger as a statement that the variable is not live.
>  > 
>  >   Unfortunately, I see no way to emit this information from
>  >   any place other than the back end.
> 
> You are exactly right, but the details are private to the
> implementation of C--.  If your debugger wants access to register
> variables, it must use the Cmm_FindLocalVar function.
> This function does indeed look at 'PC maps' in much the spirit you
> describe.

It is wonderful that you have considered this! That said, I think it is
necessary to specify what is emitted into the ELF (or whatever) file.
One should not assume that I will be debugging from within the C--
environment. From the front end perspective, I would be happy to take
responsibility for the ELF output myself by means of the section
directives, but I need some mechanism to capture this data set into the
ELF section from within the C-- section directives (or, equally good, a
well-defined section already supplied by the object file emitter). My
intuition here is that the front end has better knowledge of its
intended use of the prevailing object file format than the back end, and
that exposing this information for encapsulation in sections is
therefore a better design.

Truth in advertising: I architected both the first ELF-based debugger
and the first ELF-based incremental compiler. There are more sleazy
tricks feasible in ELF than in any other object file format in history.
With the benefit of hindsight, we probably went overboard on
flexibility, but at least we had a real motivating case for every major
design decision.

> 
>  > + Floating point literals need to be fixed. Support for a 128 bit
>  >   floating point representation should be supported, and support
>  >   for rounding modes needs to be implemented. [Deferable]
> 
> I'm not aware of anything broken about floating-point literals.

I beg your pardon. This is an issue documented in the current "Quick
C--" release notes. Please accept my apologies for the conflating this
with discussion of the specification -- it was a late night last night.

> If IEEE 754 defines a semantics for 128-bit literals, then the C--
> specification incorporates that semantics by reference.  If not, who
> defines the meaning of a 128-bit floating-point literal.

Either IEEE 754 or an addendum circa 1990 defines this semantics. Quads
are extended precision floating point values that simply have a longer
mantissa and are subject to the usual rounding rules at the limits of
representation. They have the same exponent size as the 80 bit Intel
floats.

> In the current implementation, owing to a bad decision made by a
> person who shall remain nameless, there's no support for literals of
> any kind wider than 64 bits.

Heck, nobody will ever need addresses larger than 64 bits anyway... :-)

For any of you who are history impaired, Bill Gates said effectively
this about the 64K segment size limit back in the DOS days.

In any case, there is an old document -- I want to say Dybvig -- on how
to do the input processing correctly. BitC isn't getting it right yet
either.

> Support for rounding modes is implemented (and tested!) in the current
> compiler. 

Wonderful! Perhaps the "known issues" list wants to be updated? [The one
I was reading was the one in the current web-browsable tree as of last
night; perhaps it is not the most recent.]

>  > + BitC would tremendously benefit from support for unicode literals.
>  >   It would be entirely sufficient if we simply encoded them using
>  >   octal escapes, but I suspect it is desirable to have distinguished
>  >   character and string types for these. I don't see how to do this
>  >   without taking a position on encoding. The right position is UTF-8,
>  >   not the screwed up Java/C# double byte code point screwup -- but
>  >   the mere fact that I need to say so serves to illustrate why this
>  >   is a hairball.
>  > 
>  >   Perhaps it is simpler here, because the backend really doesn't
>  >   need to understand the literal content. It might be sufficient
>  >   for the front end to qualify the literal syntax for strings; the
>  >   issue here is the need to know which NUL characters in the string
>  >   are significant.
> 
> We lost a good 4 weeks in 2000 discussing proper C-- support for
> Unicode.  And in the end, we couldn't figure out what we should do.
> If my sysadmins can ever get the spam scrubbed out of the mailing-list
> archives, you can see that traffic.
> 
> In the meantime, what I know is that nobody on the C-- team
> understands Unicode.  If someone who does can make a proposal that I
> can understand and can implement, we will run it by this list, and if
> it doesn't go down in flames, we will adopt it and implement it.

I am painfully familiar with the problem, and I will try to synopsize
our discussions in the BitC context in another mailing. Note that I did
*not* hit you with the Unicode identifiers problem, which is the *hard*
issue. The Unicode literal issues for the back end are relatively tame.

>  > + I suggest that all string literals be optionally length prefixed.
>  >   Length in *bytes* is sufficient (and avoids unicode hassles). This is
>  >   comparable to the .ASCII/.ASCIIZ distinction.
> 
> In C--, string literals are used in two contexts:
> 
>   * To communicate various machine-dependent bits and pieces, e.g.,
>     the names of sections, foreign calling conventions, and parameter
>     kinds.
> 
>   * To define values in initialized data.
> 
> Because it is already possible to put an explicit length in
> initialized data, I'm puzzled as to why you want a length on string
> literals.

I was referring to the second usage, and it is likely that I simply
missed the length specification option in haste.


Jonathan