SSA operand interface change proposal

[Andrew MacLeod <amacleod at redhat dot com>]

I've been looking at how we can integrate the immediate_uses inforamtion
directly into the operand management system. There are multiple reasons,
but primarily, 
  - Immediate uses is being built and throw away in many locations
  - updating is painful
  - memory use is large and manmaged via a VARRAY and locality sucks
with regards to the operands themselves
  - I've never liked the "free-wheeling" way we set things via 'tree *'
everywhere.  I prefer something a bit safer which hides the underlying
representation.

So a couple of things are required to do something like this.

In order to update the immediate_use information, we have to have some
semblemence of control over how things are modified. Currently, we
simply get a 'tree *' and change it. That ability has to be removed and
handled through a SET routine so that other bits can be done when the
value is changed. 

We also need to be able to handle operands of virtual uses and PHI nodes
the same way as normal operands, and currently they are simply 'tree's
instead of the 'tree *' we find in uses and defs.

And finally, I'd like to see it typechecked such that no one can
"accidentally" bypass the SET macros :-) Im sure it would be accidental
:-)

So, I've introduced 2 new types:

typedef struct def_operand_ptr GTY(())
{
  tree * GTY((skip(""))) def;
} def_operand_p;

typedef struct use_operand_ptr GTY(())
{
  tree * GTY((skip(""))) use;
} use_operand_p;


use_operand_p and def_operand_p  which perform the same functions as
'tree *' use to. It abstracts out what the actual type is, and
getting/setting values thorugh these pointer types are done thorugh
inlined functions/macros


#define USE_FROM_PTR(OP)	get_use_from_ptr (OP)
#define DEF_FROM_PTR(OP)	get_def_from_ptr (OP)
#define SET_USE(OP, V)		((*((OP).use)) = (V))
#define SET_DEF(OP, V)		((*((OP).def)) = (V))


All the existing operand macros remain, although many of them return
these new types. It totally transparent in those cases since they were
originally designed that way. 

There is a new set of macros for setting each of the operand types:
#define SET_USE_OP(OPS, I, V)	   (SET_USE (USE_OP_PTR ((OPS), (I)), (V)))
#define SET_DEF_OP(OPS, I, V)	   (SET_DEF (DEF_OP_PTR ((OPS), (I)), (V)))
#define SET_VDEF_RESULT(OPS, I, V) (SET_DEF (VDEF_RESULT_PTR ((OPS), (I)), (V)))
#define SET_VDEF_OP(OPS, I, V)	   (SET_USE (VDEF_OP_PTR ((OPS), (I)), (V)))
#define SET_VUSE_OP(OPS, I, V)	   (SET_USE (VUSE_OP_PTR ((OPS), (I)), (V)))


We also need to change the handling of PHI nodes. I renamed the macros
in tree.h to 
#define PHI_RESULT_TREE(NODE)         PHI_NODE_CHECK (NODE)->phi.result
#define PHI_ARG_DEF_TREE(NODE, I)     PHI_NODE_ELT_CHECK (NODE, I).def

And added a new set of definitions in the operand.h file:

#define PHI_RESULT_PTR(PHI)	get_phi_result_ptr (PHI)
#define PHI_RESULT(PHI)		DEF_FROM_PTR (PHI_RESULT_PTR (PHI))
#define SET_PHI_RESULT(PHI, V)	SET_DEF (PHI_RESULT_PTR (PHI), (V))

#define PHI_ARG_DEF_PTR(PHI, I)	get_phi_arg_def_ptr ((PHI), (I))
#define PHI_ARG_DEF(PHI, I)	USE_FROM_PTR (PHI_ARG_DEF_PTR ((PHI), (I)))
#define SET_PHI_ARG_DEF(PHI, I, V)					\
				SET_USE (PHI_ARG_DEF_PTR ((PHI), (I)), (V))
#define PHI_ARG_DEF_FROM_EDGE(PHI, E)					\
				PHI_ARG_DEF ((PHI),			\
					     phi_arg_from_edge ((PHI),(E)))
#define PHI_ARG_DEF_PTR_FROM_EDGE(PHI, E)				\
				PHI_ARG_DEF_PTR ((PHI),			\
						 phi_arg_from_edge ((PHI),(E)))


Virtually all the changes this causes in the current files are fairly
mechanical changes. There were one or two places where I had to split a
function into two functions, one for handling use_operand_p and one for
def_operand_p.  Things like "rewrite_operand()". Interestingly, in every
case this was required, there was a boolean flag indicating whether the
operand being passed in was a use or a def, so the two new routines dont
need that argument, and argues that the two routines are not a bad thing
:-)


There were two places which cause some difficulty. one was in DOM, and
the other is in LNO (tree-ssa-loop-ivopts.c).

In both cases, the optimizer is stepping out of the SSA information in
some places, and directly accessing the TREE nodes:

ie, 
  stmt = SSA_NAME_DEF_STMT (op);
  if (TREE_CODE (stmt) == PHI_NODE) 
    op_p = &PHI_RESULT (stmt); 
  else if (TREE_CODE (stmt) == MODIFY_EXPR) 
    op_p = &TREE_OPERAND (stmt, 0); 
  else 
    abort (); 


DOM does a similar kind of thing, albeit in a much simpler way which I
could work around (DOM never wrote to the TREE_OPERAND argument, so I
could fake a 'use').  However, there is a larger issue here.


As best I can tell, the 'ivuse' structure used thorughout
tree-ssa-loop-ivopts.c contains a pointer to a tree which can be either
a use, a def, or an expression of some sort.  If we proceed with an
interface like this (which I think we ought to), this hunk of code will
need to be reworked. I dont want to make this unbearably difficult
however.  I guess the ivuse structure could have all three pointers
(use_operand_p, def_operand_p, and tree *) , and a flag indicating which
field it uses, but maybe there is a better solution.

I figured I ought to get feedback on what others think.

To prevent anyone from asking the question, I'll give you a quick
rundown on how this all works with an integrated immediate_uses.

Basically, the use_operand_p type will be a 2 word structure, one is a
'tree *' like it currently is, and the other will be a pointer to an
immediate_use structure contained in the operand. Everywhere this
structure is passed around is done via inlined functions, and I fully
expect SRA to simplify this all down to the basic operations required,
so there ought not be any performance hit as a result. (My last run
actually showed a minor speedup in generate.ii, but I'll attribute that
to noise pending further investigation :-)

Whenever a use is SET, the old value is removed form its immediate_use
list, and the new one is inserted, presuming that it is an SSA_NAME.

So all the accesses via SETs will keep things up to date. It is also
possible to change the underlying tree without going through a SET, and
it is also possible to change it with a SET to a non-ssa value (imaging
chainging an SSA_NAME to an expression or a constant).  These types of
things force the stmt_modified flag to be set on the stmt (since the
number of operands change), and the stmt's operand cache to be rebuilt.
When this happens, we delink all the things currently in the operand
cache, build a new one, and link all the new objects into their
respective lists.   So lazily updating stmts will work fine. If you
require that your immediate use information be up to date immeidately,
you ought to call get_stmt_operands() immediately after calling
modify_stmt()., Its conceivable we could add a parameter to modify_stmt
to do this automatically when we desire it.


We have no facility to lazily update PHI nodes right now, as there has
never been a need. I beleive that still to be true since all
modifications to the PHI nodes would be through SET macros.


Anyway, Thats the change I am proposing to allow immeidate_uses to be
integrated and updated automatically with the current operand management
system.  We do have to decide how to affect the change to
tree-ssa-loop-ivopts.c and other similar optimizations that I presume
people will eventually write. Things that work through both the operand
cache AND tree nodes directly... Having seperate variables and handling
them seperately seem reasonable to me, but I dont wnt to try to impose
that unless others agree.

I normally can't write a note this long and manage to be clear about
what Im saying, so feel free to ask for clarifications :-)

I havent posted a patch with all the changes simply because my current
patch is on a 2 week old branch, and I'm in the process of updating it.
I'll post one tonight after Ive updated and verified it.

Andrew