SSA operand iterator

[Andrew MacLeod <amacleod at redhat dot com>]

Zdenek proposed a couple of iterator patches a while back, but there
were minor problems with them. I've been thinking about it a bit, and
have come up with the following patch which makes use of his ideas. I've
posted it in 2 chunks, the first one is the really relevant one, it
implements the iterators. The second one is simply replacing most uses
of the _optype loops with the new iterator. 

This is implemented as a macro, but its a macro for just a loop header,
meaning that the body of the loop isnt part of the macro, so debugging
works fine with it, and there is no code duplication as in previous
implementations.

The iterator structure is a general purpose object which contains lots
of variables used to control the loops. We fully scalarize the
structure, and optimize out the unused portions, resulting in pretty
decent code for the loop.

This implementation has insignificant cost. It occasionally wins
(probably due to the reduction in code duplication, reducing register
pressure), and ocassionally loses,  My guess is that since there is no
code duplication now, we end up producing less register pressure in some
routines and thus end up with a slight win. In any case, There is no
noticable penalty for using it, which was a strike against the earlier
versions.

I'll provide a quick synopsis of how the new iterator works, and you can
let me know if there is something that should maybe be changed. 

There are basically 3 types of iterator loops. 
Loops which work with use_operand_p, def_operand_p and trees. 
Actually, there is a 4th type of loop, one that loops at just MAYDEFs...
this is unique in that they have both a use and a def associated with
them. 

Each iteraotr loop takes 4 parameters:
  - The variable each iteration is assigned into
  - The stmt which is being looked at
  - An iterator structure which is used to control the loop
  - Flags indicating which operands to look at.


So a typical translation from the previous method to the current looks
something like :

      stmt_ann_t ann = get_stmt_ann (old);
      use_optype uses = USE_OPS (ann);
      vuse_optype vuses = VUSE_OPS (ann);
      v_may_def_optype v_may_defs = V_MAY_DEF_OPS (ann);
      unsigned int i;
    
      /* Look at USE_OPS or VUSE_OPS according to FLAGS.  */
      for (i = 0; i < NUM_USES (uses); i++)
        redirect_immediate_use (USE_OP (uses, i), old, new);
    
      for (i = 0; i < NUM_VUSES (vuses); i++)
        redirect_immediate_use (VUSE_OP (vuses, i), old, new);
    
      for (i = 0; i < NUM_V_MAY_DEFS (v_may_defs); i++)
        redirect_immediate_use (V_MAY_DEF_OP (v_may_defs, i), old, new);
    
Can be rewritten as :

      ssa_op_iter iter;
      tree val;
    
      FOR_EACH_SSA_TREE_OPERAND (val, old, iter, SSA_OP_ALL_USES)
        redirect_immediate_use (val, old, new);
    

Of the other 3 types of loops, here are examples of each:

      ssa_op_iter iter;
      use_operand_p use_p;
      
      FOR_EACH_SSA_USE_OPERAND (use_p, stmt, iter, SSA_OP_USE)
          {
            if (prepare_use_operand_for_rename (use_p, &uid)
              && !TEST_BIT (kills, uid))
            set_livein_block (USE_FROM_PTR (use_p), bb);
          }
    
      ssa_op_iter iter;
      def_operand_p def_p;
    
      FOR_EACH_SSA_DEF_OPERAND (def_p, stmt, iter, SSA_OP_ALL_DEFS)
          {
            if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
            SET_DEF (def_p, make_ssa_name (DEF_FROM_PTR (def_p), stmt));
          }
    
    
      FOR_EACH_SSA_MAYDEF_OPERAND (def_p, use_p, stmt, iter)
          {
            if (prepare_use_operand_for_rename (use_p, &uid))
            {
              /* If we do not already have an SSA_NAME for our destination,
                 then set the destination to the source.  */
              if (TREE_CODE (DEF_FROM_PTR (def_p)) != SSA_NAME)
                SET_DEF (def_p, USE_FROM_PTR (use_p));
    
                set_livein_block (USE_FROM_PTR (use_p), bb);
              set_def_block (DEF_FROM_PTR (def_p), bb, false, false);
            }
          }
    
    
So thats what it looks like. The first patch implements the iterator,
and has the flags and such. The second one is all the changes required
to the rest of the compiler to replace the operand loops with this
general iterator. I replaced almost all them, even the ones which only
loop over a single operand type.

Anyone have any issues with this? Wanna see something changed? Does it
accomplish what you are looking for? I'll check it in if its sufficient.

It bootstraps on i686-pc-linux-gnu and produces no new testsuite
failures.

Andrew


2004-08-24  Andrew MacLeod  <amacleod@redhat.com>

	* tree-ssa-operands.h (struct ssa_operand_iterator_d): New.  SSA operand
	iterator controlling structure.
	(SSA_OP_USE, SSA_OP_DEF, SSA_OP_VUSE, SSA_OP_VMAYUSE, SSA_OP_VMAYDEF,
	SSA_OP_VMUSTDEF, SSA_OP_VIRTUAL_USES, SSA_OP_VIRTUAL_DEFS,
	SSA_OP_ALL_USES, SSA_OP_ALL_DEFS, SSA_OP_ALL_OPERANDS): New.  Operand
	iterator flags.
	(FOR_EACH_SSA_TREE_OPERAND): New.  Iterate over operands as trees.
	(FOR_EACH_SSA_USE_OPERAND): New.  Iterate over operands as uses.
	(FOR_EACH_SSA_DEF_OPERAND): New.  Iterate over operands as defs.
	(FOR_EACH_SSA_MAYDEF_OPERAND): New.  Iterate over V_MAY_DEFs.
	* tree-ssa-operands.c (NULL_DEF_OPERAND_P, NULL_USE_OPERAND_P): New. 
	Empty operand pointers.
	* tree-flow-inline.h (op_iter_done): New.  Return true if finished.
	(op_iter_next_use): New.  Return next use_operand_p.
	(op_iter_next_def): New.  Return next def_operand_p.
	(op_iter_next_tree): New.  Return next operands as a tree.
	(op_iter_init): New.  Initialize an iterator structure.
	(op_iter_init_use): New.  Initialize structure and get the first use.
	(op_iter_init_def): New.  Initialize structure and get the first def.
	(op_iter_init_tree): New.  Initialize structure and get the first tree.
	(op_iter_next_maydef): New.  Return next V_MAY_DEF operands.
	(op_iter_init_maydef): New.  Initialize structure and get the first 
	V_MAY_DEF operands.



Index: tree-ssa-operands.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.h,v
retrieving revision 2.5
diff -c -p -r2.5 tree-ssa-operands.h
*** tree-ssa-operands.h	11 Aug 2004 17:50:47 -0000	2.5
--- tree-ssa-operands.h	24 Aug 2004 14:29:49 -0000
*************** typedef struct use_operand_ptr GTY(())
*** 36,41 ****
--- 36,43 ----
    tree * GTY((skip(""))) use;
  } use_operand_p;
  
+ extern def_operand_p NULL_DEF_OPERAND_P;
+ extern use_operand_p NULL_USE_OPERAND_P;
  
  /* This represents the DEF operands of a stmt.  */
  typedef struct def_optype_d GTY(())
*************** extern void get_stmt_operands (tree);
*** 184,187 ****
--- 186,261 ----
  extern void copy_virtual_operands (tree, tree);
  extern void create_ssa_artficial_load_stmt (stmt_operands_p, tree);
  
+ 
+ /* This structure is used in the operand iterator loops.  It contains the 
+    items required to determine which operand is retreived next.  During
+    optimization, this structure is scalarized, and any unused fields are 
+    optimized away, resulting in little overhead.  */
+ 
+ typedef struct ssa_operand_iterator_d
+ {
+   int num_use;
+   int num_def;
+   int num_vuse;
+   int num_v_mayu;
+   int num_v_mayd;
+   int num_v_must;
+   int use_i;
+   int def_i;
+   int vuse_i;
+   int v_mayu_i;
+   int v_mayd_i;
+   int v_must_i;
+   stmt_operands_p ops;
+   bool done;
+ } ssa_op_iter;
+ 
+ /* These flags are used to determine which operands are returned during 
+    execution of the loop.  */
+ #define SSA_OP_USE		0x01	/* Real USE operands.  */
+ #define SSA_OP_DEF		0x02	/* Real DEF operands.  */
+ #define SSA_OP_VUSE		0x04	/* VUSE operands.  */
+ #define SSA_OP_VMAYUSE		0x08	/* USE portion of V_MAY_DEFS.  */
+ #define SSA_OP_VMAYDEF		0x10	/* DEF portion of V_MAY_DEFS.  */
+ #define SSA_OP_VMUSTDEF		0x20	/* V_MUST_DEF defintions.  */
+ 
+ /* These are commonly grouped operand flags.  */
+ #define SSA_OP_VIRTUAL_USES	(SSA_OP_VUSE | SSA_OP_VMAYUSE)
+ #define SSA_OP_VIRTUAL_DEFS	(SSA_OP_VMAYDEF | SSA_OP_VMUSTDEF)
+ #define SSA_OP_ALL_USES		(SSA_OP_VIRTUAL_USES | SSA_OP_USE)
+ #define SSA_OP_ALL_DEFS		(SSA_OP_VIRTUAL_DEFS | SSA_OP_DEF)
+ #define SSA_OP_ALL_OPERANDS	(SSA_OP_ALL_USES | SSA_OP_ALL_DEFS)
+ 
+ /* This macro executes a loop over the operands of STMT specified in FLAG, 
+    returning each operand as a 'tree' in the variable TREEVAR.  ITER is an
+    ssa_op_iter structure used to control the loop.  */
+ #define FOR_EACH_SSA_TREE_OPERAND(TREEVAR, STMT, ITER, FLAGS)	\
+   for (TREEVAR = op_iter_init_tree (&(ITER), STMT, FLAGS);	\
+        !op_iter_done (&(ITER));					\
+        TREEVAR = op_iter_next_tree (&(ITER)))
+ 
+ /* This macro executes a loop over the operands of STMT specified in FLAG, 
+    returning each operand as a 'use_operand_p' in the variable USEVAR.  
+    ITER is an ssa_op_iter structure used to control the loop.  */
+ #define FOR_EACH_SSA_USE_OPERAND(USEVAR, STMT, ITER, FLAGS)	\
+   for (USEVAR = op_iter_init_use (&(ITER), STMT, FLAGS);	\
+        !op_iter_done (&(ITER));					\
+        USEVAR = op_iter_next_use (&(ITER)))
+ 
+ /* This macro executes a loop over the operands of STMT specified in FLAG, 
+    returning each operand as a 'def_operand_p' in the variable DEFVAR.  
+    ITER is an ssa_op_iter structure used to control the loop.  */
+ #define FOR_EACH_SSA_DEF_OPERAND(DEFVAR, STMT, ITER, FLAGS)	\
+   for (DEFVAR = op_iter_init_def (&(ITER), STMT, FLAGS);	\
+        !op_iter_done (&(ITER));					\
+        DEFVAR = op_iter_next_def (&(ITER)))
+ 
+ /* This macro executes a loop over the V_MAY_DEF operands of STMT.  The def
+    and use for each V_MAY_DEF is returned in DEFVAR and USEVAR. 
+    ITER is an ssa_op_iter structure used to control the loop.  */
+ #define FOR_EACH_SSA_MAYDEF_OPERAND(DEFVAR, USEVAR, STMT, ITER)	\
+   for (op_iter_init_maydef (&(ITER), STMT, &(USEVAR), &(DEFVAR));	\
+        !op_iter_done (&(ITER));					\
+        op_iter_next_maydef (&(USEVAR), &(DEFVAR), &(ITER)))
+ 
  #endif  /* GCC_TREE_SSA_OPERANDS_H  */
Index: tree-ssa-operands.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-ssa-operands.c,v
retrieving revision 2.31
diff -c -p -r2.31 tree-ssa-operands.c
*** tree-ssa-operands.c	23 Aug 2004 07:47:31 -0000	2.31
--- tree-ssa-operands.c	24 Aug 2004 14:29:49 -0000
*************** static GTY (()) varray_type build_vuses;
*** 114,124 ****
--- 114,128 ----
  /* Array for building all the v_must_def operands.  */
  static GTY (()) varray_type build_v_must_defs;
  
+ 
  #ifdef ENABLE_CHECKING
  /* Used to make sure operand construction is working on the proper stmt.  */
  tree check_build_stmt;
  #endif
  
+ def_operand_p NULL_DEF_OPERAND_P = { NULL };
+ use_operand_p NULL_USE_OPERAND_P = { NULL };
+ 
  static void note_addressable (tree, stmt_ann_t);
  static void get_expr_operands (tree, tree *, int);
  static void get_asm_expr_operands (tree);
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/tree-flow-inline.h,v
retrieving revision 2.20
diff -c -p -r2.20 tree-flow-inline.h
*** tree-flow-inline.h	12 Aug 2004 14:33:58 -0000	2.20
--- tree-flow-inline.h	24 Aug 2004 14:29:49 -0000
*************** get_tree_ann (tree t)
*** 673,676 ****
--- 673,848 ----
    return (ann) ? ann : create_tree_ann (t);
  }
  
+ /*  -----------------------------------------------------------------------  */
+ 
+ /* The following set of routines are used to iterator over various type of
+    SSA operands.  */
+ 
+ /* Return true if PTR is finished iterating.  */
+ static inline bool
+ op_iter_done (ssa_op_iter *ptr)
+ {
+   return ptr->done;
+ }
+ 
+ /* Get the next iterator use value for PTR.  */
+ static inline use_operand_p
+ op_iter_next_use (ssa_op_iter *ptr)
+ {
+   if (ptr->use_i < ptr->num_use)
+     {
+       return USE_OP_PTR (ptr->ops->use_ops, (ptr->use_i)++);
+     }
+   if (ptr->vuse_i < ptr->num_vuse)
+     {
+       return VUSE_OP_PTR (ptr->ops->vuse_ops, (ptr->vuse_i)++);
+     }
+   if (ptr->v_mayu_i < ptr->num_v_mayu)
+     {
+       return V_MAY_DEF_OP_PTR (ptr->ops->v_may_def_ops,
+ 				       (ptr->v_mayu_i)++);
+     }
+   ptr->done = true;
+   return NULL_USE_OPERAND_P;
+ }
+ 
+ /* Get the next iterator def value for PTR.  */
+ static inline def_operand_p
+ op_iter_next_def (ssa_op_iter *ptr)
+ {
+   if (ptr->def_i < ptr->num_def)
+     {
+       return DEF_OP_PTR (ptr->ops->def_ops, (ptr->def_i)++);
+     }
+   if (ptr->v_must_i < ptr->num_v_must)
+     {
+       return V_MUST_DEF_OP_PTR (ptr->ops->v_must_def_ops, 
+ 					(ptr->v_must_i)++);
+     }
+   if (ptr->v_mayd_i < ptr->num_v_mayd)
+     {
+       return V_MAY_DEF_RESULT_PTR (ptr->ops->v_may_def_ops,
+ 					   (ptr->v_mayd_i)++);
+     }
+   ptr->done = true;
+   return NULL_DEF_OPERAND_P;
+ }
+ 
+ /* Get the next iterator tree value for PTR.  */
+ static inline tree
+ op_iter_next_tree (ssa_op_iter *ptr)
+ {
+   if (ptr->use_i < ptr->num_use)
+     {
+       return USE_OP (ptr->ops->use_ops, (ptr->use_i)++);
+     }
+   if (ptr->vuse_i < ptr->num_vuse)
+     {
+       return VUSE_OP (ptr->ops->vuse_ops, (ptr->vuse_i)++);
+     }
+   if (ptr->v_mayu_i < ptr->num_v_mayu)
+     {
+       return V_MAY_DEF_OP (ptr->ops->v_may_def_ops, (ptr->v_mayu_i)++);
+     }
+   if (ptr->def_i < ptr->num_def)
+     {
+       return DEF_OP (ptr->ops->def_ops, (ptr->def_i)++);
+     }
+   if (ptr->v_must_i < ptr->num_v_must)
+     {
+       return V_MUST_DEF_OP (ptr->ops->v_must_def_ops, 
+ 					(ptr->v_must_i)++);
+     }
+   if (ptr->v_mayd_i < ptr->num_v_mayd)
+     {
+       return V_MAY_DEF_RESULT (ptr->ops->v_may_def_ops,
+ 					   (ptr->v_mayd_i)++);
+     }
+   ptr->done = true;
+   return NULL;
+ }
+ 
+ /* Initialize the iterator PTR to the virtual defs in STMT.  */
+ static inline void
+ op_iter_init (ssa_op_iter *ptr, tree stmt, int flags)
+ {
+   stmt_operands_p ops;
+   stmt_ann_t ann = get_stmt_ann (stmt);
+ 
+   ops = &(ann->operands);
+   ptr->done = false;
+   ptr->ops = ops;
+   ptr->num_def = (flags & SSA_OP_DEF) ? NUM_DEFS (ops->def_ops) : 0;
+   ptr->num_use = (flags & SSA_OP_USE) ? NUM_USES (ops->use_ops) : 0;
+   ptr->num_vuse = (flags & SSA_OP_VUSE) ? NUM_VUSES (ops->vuse_ops) : 0;
+   ptr->num_v_mayu = (flags & SSA_OP_VMAYUSE)
+ 		     ?  NUM_V_MAY_DEFS (ops->v_may_def_ops) : 0;
+   ptr->num_v_mayd = (flags & SSA_OP_VMAYDEF) 
+ 		     ?  NUM_V_MAY_DEFS (ops->v_may_def_ops) : 0;
+   ptr->num_v_must = (flags & SSA_OP_VMUSTDEF) 
+ 		     ? NUM_V_MUST_DEFS (ops->v_must_def_ops) : 0;
+   ptr->def_i = 0;
+   ptr->use_i = 0;
+   ptr->vuse_i = 0;
+   ptr->v_mayu_i = 0;
+   ptr->v_mayd_i = 0;
+   ptr->v_must_i = 0;
+ }
+ 
+ /* Initialize iterator PTR to the use operands in STMT based on FLAGS. Return
+    the first use.  */
+ static inline use_operand_p
+ op_iter_init_use (ssa_op_iter *ptr, tree stmt, int flags)
+ {
+   op_iter_init (ptr, stmt, flags);
+   return op_iter_next_use (ptr);
+ }
+ 
+ /* Initialize iterator PTR to the def operands in STMT based on FLAGS. Return
+    the first def.  */
+ static inline def_operand_p
+ op_iter_init_def (ssa_op_iter *ptr, tree stmt, int flags)
+ {
+   op_iter_init (ptr, stmt, flags);
+   return op_iter_next_def (ptr);
+ }
+ 
+ /* Initialize iterator PTR to the operands in STMT based on FLAGS. Return
+    the first operand as a tree.  */
+ static inline tree
+ op_iter_init_tree (ssa_op_iter *ptr, tree stmt, int flags)
+ {
+   op_iter_init (ptr, stmt, flags);
+   return op_iter_next_tree (ptr);
+ }
+ 
+ /* Get the next iterator maydef value for PTR, returning the maydef values in
+    USE and DEF.  */
+ static inline void
+ op_iter_next_maydef (use_operand_p *use, def_operand_p *def, ssa_op_iter *ptr)
+ {
+   if (ptr->v_mayu_i < ptr->num_v_mayu)
+     {
+       *def = V_MAY_DEF_RESULT_PTR (ptr->ops->v_may_def_ops, ptr->v_mayu_i);
+       *use = V_MAY_DEF_OP_PTR (ptr->ops->v_may_def_ops, (ptr->v_mayu_i)++);
+       return;
+     }
+   else
+     {
+       *def = NULL_DEF_OPERAND_P;
+       *use = NULL_USE_OPERAND_P;
+     }
+   ptr->done = true;
+   return;
+ }
+ 
+ /* Initialize iterator PTR to the operands in STMT.  Return the first operands
+    in USE and DEF.  */
+ static inline void
+ op_iter_init_maydef (ssa_op_iter *ptr, tree stmt, use_operand_p *use, 
+ 		     def_operand_p *def)
+ {
+   op_iter_init (ptr, stmt, SSA_OP_VMAYUSE);
+   op_iter_next_maydef (use, def, ptr);
+ }
  #endif /* _TREE_FLOW_INLINE_H  */

Attachment: F2
Description: Text document