Language-independent functions-as-trees representation

[Jason Merrill]

I'd like to bring this subject up yet again, last discussed in

  http://gcc.gnu.org/ml/gcc/2002-07/threads.html#00890

I continue to believe that the current tree IR is fundamentally flawed; it
was designed as a convenient shorthand for representing C parse trees, and
is fairly unwieldy for use by optimizers.  I laid out various problems in
the message above.  One primary weakness is that many of the _STMT
codes just mean "call expand_foo now", and as such are a reasonable
representation if we are only going to pass them to the expander, as has
been the case in the past, but not if we want them to actually express
program semantics in a properly structured way.

I also continue to take issue with the distinction between _STMT and _EXPR
nodes.  Discussing this with other folks, I have come to the conclusion
that the real distinction between statements and expressions is that a
statement is something for which we are only interested in its
side-effects, not its value.  It's a difference of evaluation context, not
always an intrinsic difference.  Something like a cleanup can appear in
either context; it seems sensible to use TRY_FINALLY_EXPR to express it in
both, rather than convert it to a TRY_FINALLY_STMT when it moves to
statement context.

I've been working for a couple of weeks off and on to retarget the
simplifier to generate something much more like the Java frontend tree IR,
which seems much cleaner to me, largely by virtue of working mostly in the
existing backend tree codes.  I've made a lot of progress, though
significant things are still broken, but my morale is fading.  I see more
and more people building things on the current IR every day, increasing the
work that will be necessary to switch optimizers and such over to the
hypothetical new scheme.

It seems to me that these fundamental design questions need to be
straightened out now, before we build anything more on top of the current
IR, or we're just digging ourselves a deeper hole.  As long as we're
building something new, we should take the time to do it right.  Do others
disagree?  I suppose another strategy would be to clean up the expand
placeholders in the C/C++ IR one by one, rather than try to simplify it to
something rather different all at once, but that would not address the
STMT/EXPR issue.

Basically, I'm wondering if other people are interested enough in this
change to 1) help with the design for the IR and 2) help with porting the
existing tree optimizers to the new IR.

In any case, here's a draft of a design of a new SIMPLE representation.
It's a bit sketchy at this point, but I'm very interested in comments.

------

   function:
     FUNCTION_DECL
       DECL_SAVED_TREE -> block
   block:
     BIND_EXPR
       BIND_EXPR_VARS -> DECL chain
       BIND_EXPR_BLOCK -> BLOCK
       BIND_EXPR_BODY -> compound-stmt

A BIND_EXPR takes the place of the current COMPOUND_STMT, SCOPE_STMT and
DECL_STMT; all of the decls for a block are given RTL at the beginning of
the block.  DECLs with static initializers keep their DECL_INITIAL; other
initializations are implemented with INIT_EXPRs in the codestream.  The
Java "BLOCK_EXPR" is very similar.

   compound-stmt:
     COMPOUND_EXPR
       op0 -> non-compound-stmt
       op1 -> stmt

rth has raised some questions about the advisability of using COMPOUND_EXPR
to chain statements; the current scheme uses TREE_CHAIN of the statements
themselves.  To me, the benefit is modularity; apart from the earlier
complaints about the STMT/EXPR distinction, using COMPOUND_EXPR makes it
easy to replace a single complex expression with a sequence of simple ones,
simply by plugging in a COMPOUND_EXPR in its place.  The current scheme
requires a lot more pointer management in order to splice the new STMTs in
at both ends.

It seems to me that double-chaining could be provided by using the
TREE_CHAIN of the COMPOUND_EXPRs.

   stmt: compound-stmt | non-compound-stmt
   non-compound-stmt:
     block
     | loop-stmt
     | if-stmt
     | switch-stmt
     | labeled-block-stmt
     | jump-stmt
     | label-stmt
     | try-stmt
     | modify-stmt
     | call-stmt
   loop-stmt:
     LOOP_EXPR
       LOOP_EXPR_BODY -> stmt | NULL_TREE
     | DO_LOOP_EXPR
       (to be defined later)

The Java loop has 1 (or 0) EXIT_EXPR, used to express the loop condition.
This makes it easy to distinguish from 'break's, which are expressed
with EXIT_BLOCK_EXPR.  

EXIT_EXPR is a bit backwards for this purpose, as its sense is opposite to
that of the loop condition, so we end up calling invert_truthvalue twice in
the process of generating and expanding it.  But that's not a big deal.

>From an optimization perspective, are LABELED_BLOCK_EXPR/EXIT_BLOCK_EXPR
easier to deal with than plain gotos?  I assume they're preferable to the
current loosely bound BREAK_STMT, which has no information about what it's
exiting.  EXIT_EXPR would have the same problem if it were used to express
'break'.

   if-stmt:
     COND_EXPR
       op0 -> condition
       op1 -> stmt
       op2 -> stmt
   switch-stmt:
     SWITCH_EXPR
       op0 -> val
       op1 -> stmt

The McCAT SIMPLE requires the simplifier to make case labels disjoint by
copying shared code around, allowing a more structured representation of a
switch.  I think this is too dubious an optimization to be performed by
default, but might be interesting as part of a goto-elimination pass; a
possible representation would be to also allow a TREE_LIST for op1.

   labeled-block-stmt:
     LABELED_BLOCK_EXPR
       op0 -> LABEL_DECL
       op1 -> stmt
   jump-stmt:
     EXIT_EXPR
         op0 -> condition
     | GOTO_EXPR
         op0 -> LABEL_DECL | '*' ID
     | RETURN_EXPR
         op0 -> modify-stmt | NULL_TREE

I had thought about always moving the assignment to the return value out of
the RETURN_EXPR, but it seems like expand_return depends on getting a
MODIFY_EXPR in order to handle some return semantics.

     | EXIT_BLOCK_EXPR
         op0 -> ref to LABELED_BLOCK_EXPR
         op1 -> NULL_TREE
     | THROW_EXPR? 

I'm not sure how we want to represent throws for the purpose of to
generating an ERT_THROW region?  I had thought about using a THROW_EXPR
wrapper, but that wouldn't work in non-simplified code where calls can have
complex args.  Perhaps annotation of the CALL_EXPR would work better.

     | RESX_EXPR
   label-stmt:
     LABEL_EXPR
         op0 -> LABEL_DECL
     | CASE_LABEL_EXPR
         CASE_LOW -> val | NULL_TREE
         CASE_HIGH -> val | NULL_TREE
   try-stmt:
     TRY_CATCH_EXPR

This will need to be extended to handle type-based catch clauses as well.

     | TRY_FINALLY_EXPR

I think it makes sense to leave this as a separate tree code for handling
cleanups.

   modify-stmt:
     MODIFY_EXPR | INIT_EXPR
       op0 -> lhs
       op1 -> rhs
   call-stmt: CALL_EXPR
     op0 -> ID
     op1 -> arglist

Assignment and calls are the only expressions with intrinsic side-effects,
so only they can appear at statement context.

The rest of this is basically copied from the McCAT design.  I think it
still needs some tweaking, but that can wait until after the
statement-level stuff is worked out.

   varname : compref | ID (rvalue)
   lhs: varname | '*' ID  (lvalue)
   pseudo-lval: ID | '*' ID  (either)
   compref :
     COMPONENT_REF
       op0 -> compref | pseudo-lval
     | ARRAY_REF
       op0 -> compref | pseudo-lval
       op1 -> val

   condition : val | val relop val
   val : ID | CONST

   rhs        : varname | CONST
	      | '*' ID
	      | '&' varname_or_temp
	      | call_expr
	      | unop val
	      | val binop val
	      | '(' cast ')' varname

   unop    : '+' | '-' | '!' | '~'
   binop   : relop | '-' | '+' | '/' | '*' | '%' | '&' | '|' | '<<' | '>>' | '^'
   relop   : '<' | '<=' | '>' | '>=' | '==' | '!='

-----
Other thoughts:

I've gotten questions about what GENERIC means, and whether it's worth
designing yet another IR.  I don't think any design is necessary; GENERIC
is just whatever can be expressed in the generic trees.  The l-i simplifier
should be able to reduce any valid tree structure to SIMPLE.

It's still not clear to me how best to represent line number information.
I'd appreciate someone from the Java team explaining to me how it's handled
there, particularly the use of EXPR_WFL_LINECOL on
non-EXPR_WITH_FILE_LOCATION nodes.

There has been uncertainty about what to do with frontend trees that we
want to wait and lower after inlining; the problem is how to treat them in
dataflow optimizations.  I think that we don't actually need to worry about
that; we can do more localized optimizations, such as inlining, and then
lower them to backend trees.

I've attached my current patch below; it's still in the toy stages, but
gives an idea of my implementation strategy.

Jason