[tree-ssa] empty_stmt_nodes, deleted statements, iterators, andgsi_step_bb

[Andrew MacLeod <amacleod at redhat dot com>]

There is a problem with the way gsi_step_bb() traverses through a basic
block. Simply put, gsi_step_bb compares the current statement with the
end-of-block statement of bb_for_stmt(), which is never correct if the
statement happens to be empty_stmt_node. empty_stmt_node is shared, so
there is only one.

empty_stmt_nodes are generated by the front end on occasion, and we use
them as deleted statements.  This shows up as a bug in DCE when we don't
examine any stmt's following a (void *)0 in the block, so they are never
seen as necessary, and thus they get deleted. This will be even more of
an issue when we chain optimizations together (soon! :-) and there are
more and more deleted statements. 

So I've look at some alternatives, and this becomes a bit more
encompassing than I thought. So here are the alternatives that I looked
at, most of which I actually tried out.

1 - Mark deleted stmts with a flag , ie TF_DELETED.  The problem here is
that you have to check for the flag before actually processing a
statement. Thats less than ideal, not to mention the fact that it
*still* doesn't resolve the empty_stmt_nodes generated by the front
end.  Alternatively, you could have the iterator routines simply 'skip
over' deleted stmts. If you are going to do that, you might as well use
empty_stmt_node like we do now, and have the iterators skip over them,
then you don't need a flag at all.

2 - generate unique empty_stmt_nodes so we can set the block. We could
do this, but we can no longer make comparisons like
	if (st == empty_stmt_node)
and when I looked at the front end code, I was uncomfortable mucking
about with something as basic as the empty_stmt_node. besides, you still
have to check statements to see whether you are suppose to look at them
or not.

3 - modify the gsi_*_bb routines such that we don't get empty statement
nodes. 

I started implementing 1 & 2, and those lead me to conclude that I liked
3 better. This can be implemented 2 different ways.

The first and least intrusive is to modify gsi_start_bb() and
gsi_step_bb() to only return stmts which aren't empty_stmt_nodes, except
in the case where the basic block has nothing *but* empty_stmt_nodes in
it.   The rationale for that is that there is a lot of code that assumes
that if the basic block is present, there must be at least one
statement. This can be accomplished (and bootstrapped) by modifying
*only* gsi_start_bb and gsi_step_bb. This also gives you a statement in
the block which you can insert before or after.  
  I don't like the rationale for it however. Just because current code
does it that way doesn't mean its the best way. As far as I am
concerned, either you can see empty_stmt_nodes, or you can't. You
shouldn't see them 'sometimes' because they are convienient. It doesn't
seem clean.

So the second approach is to never return an empty_stmt_node.. This
means you can get a NULL back from first_stmt() and last_stmt(), among
other things. I've made all the changes required for this as well, and
*most* of the issues were in the CFG builder.. (this stuff bootstraps as
well now.)  

The drawback is that if a block has no statements, its not as
convienient to add a statement.  ie, if we write a gsi_insert_after()
routine, its likely to be used something like this:

gsi_stmt_interator i;
i = gsi_start_bb (bb);
...
n = new_stmt(...)
gsi_insert_after (n, i)    /* or something like this.  */

If there are nothing but empty_stmt_nodes in the block, gsi_start_bb
will set the iterator to NULL. So when it comes time to add the
statement, we don't even know what block we are adding this statement
to, let alone where....

The easiest thing to do to solve that problem would be to make the
iterator have 2 words, the stmt pointer and the basic block it belongs
to. This would simplify many things I think, but it does have the
drawback of passing a couple of words around as an iterator instead of
just one. I doubt thats a huge deal, especially since a lot of routines
which operate on interators are inlined. Perhaps there is a better
option.

What does everyone else think? Any other alternatives for tackling this?
what other issues are there going to be?

Andrew

PS We could also skip error_mark_nodes ther same way too I suppose,
that's then remove the need to use is_exec_stmt() when traversing within
a block.

PPS I also dont think its an issue that the non-bb versions of gsi_*
work differently.... ? They give you an alternative which allows you to
look at everything...