This is the mail archive of the gcc-patches@gcc.gnu.org mailing list for the GCC project.


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: [tree-ssa] Walking blocks in reverse


On Fri, 2003-04-04 at 19:38, Daniel Berlin wrote:
> 
> On Friday, April 4, 2003, at 04:36  PM, Andrew MacLeod wrote:
> 
> I could use it, i had just figured i'd wait for bsi_prev to be more 
> efficient, or do it myself when i got around to it.
> 


OK, Since Dan has a use for it, I'm checking in the BSI_REVERSE code.
Its easy
enough to take out later when we don't need or want it.

It also turns out that I don't even want the iterators in reverse, all I
really need is the stmt's. So there is another macro
  FOR_EACH_STMT_IN_REVERSE (stack, bb, stmt)

which works like the BSI macro, except it simply pushes the bsi_stmt()
onto
a stack, and pops it off as needed. So if all you ever do is a

  FOR_EACH_BSI_IN_REVERSE (..)
    {
      stmt = bsi_stmt (bsi);

      ..  stmt ...
    }

Then thats the macro for you. Its more efficient. So its the macro for
me anyway :-)

The include file tree-flow-inline.h has comments about what needs to be
declared and how to use them.

I've checked this in. It appears to work fine. Noo ne is using it, so it
doesnt affect bootstrap or testcases...

Andrew



2003-04-06  Andrew MacLeod  <amacleod at redhat dot com>

	* tree-cfg.c (push_bsi): New. Push a block_stmt_iterator onto a stack.
	(pop_bsi): New. Pop a block_stmt_iterator off a stack.
	* tree-flow-inline.h (struct bsi_list_d): Block iterator stack struct.
	(new_bsi_list): Start a new bsi stack.
	(empty_bsi_stack): Is stack empty.
	(FOR_EACH_BSI_IN_REVERSE): Macro for processing bsi's in reverse.
	(FOR_EACH_STMT_IN_REVERSE): Macro for processing stmt's in reverse.


Index: tree-cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-cfg.c,v
retrieving revision 1.1.4.68
diff -c -p -r1.1.4.68 tree-cfg.c
*** tree-cfg.c	1 Apr 2003 23:04:02 -0000	1.1.4.68
--- tree-cfg.c	6 Apr 2003 16:36:48 -0000
*************** bsi_insert_on_edge (e, stmt)
*** 3126,3131 ****
--- 3126,3185 ----
    
  }
  
+ /* These 2 routines are used to process BSI's in reverse within a block.
+    When there is a decent implementation of bsi_prev, we can get rid of 
+    these forever!  */
+ 
+ /* Push another block_stmt_iterator onto the stack.  */
+ void 
+ push_bsi (list, bsi)
+      bsi_list_p *list;
+      block_stmt_iterator bsi;
+ {
+   bsi_list_p tmp;
+   if (*list == NULL)
+     {
+       *list = new_bsi_list ();
+       (*list)->bsi[0] = bsi;
+     }
+   else
+     {
+       if ((*list)->curr_index == (BSI_NUM_ELEMENTS - 1))
+         {
+ 	  tmp = new_bsi_list ();
+ 	  tmp->bsi[0] = bsi;
+ 	  tmp->next = *list;
+ 	  *list = tmp;
+ 	}
+       else
+         {
+ 	  (*list)->bsi[++((*list)->curr_index)] = bsi;
+ 	}
+     }
+ }
+ 
+ /* Pop a block_stmt_iterator off the stack.  */
+ block_stmt_iterator
+ pop_bsi (list)
+      bsi_list_p *list;
+ {
+   block_stmt_iterator bsi;
+   bsi_list_p tmp;
+   if (!list)
+     abort ();
+     
+   tmp = *list;
+   bsi = tmp->bsi[(tmp->curr_index)--];
+   if (tmp->curr_index< 0)
+     {
+       tmp = *list;
+       *list = (*list)->next;
+       free (tmp);
+     }
+   return bsi;
+ }
+ 
+ 
  /* Replace the statement pointed by TP1 with the statement pointed by TP2.
     Note that this function will not replace COMPOUND_EXPR nodes, only
     individual statements.
Index: tree-flow-inline.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/Attic/tree-flow-inline.h,v
retrieving revision 1.1.2.32
diff -c -p -r1.1.2.32 tree-flow-inline.h
*** tree-flow-inline.h	1 Apr 2003 23:04:02 -0000	1.1.2.32
--- tree-flow-inline.h	6 Apr 2003 16:36:48 -0000
*************** is_label_stmt (t)
*** 465,468 ****
--- 465,568 ----
    return false;
  }
  
+ /* Routines to allow a block to be walked backwards reasonably efficiently.
+    Once a decent implementation of bsi_prev() is implemented, this can
+    be removed.  */
+ 
+ #define BSI_NUM_ELEMENTS	50
+ 
+ typedef struct bsi_list_d {
+   block_stmt_iterator bsi[BSI_NUM_ELEMENTS];
+   int curr_index;
+   struct bsi_list_d *next;
+ } *bsi_list_p;
+ 
+ 
+ static inline bsi_list_p new_bsi_list	PARAMS ((void));
+ static inline int empty_bsi_stack	PARAMS ((bsi_list_p));
+ extern void push_bsi			PARAMS ((bsi_list_p *, 
+ 						 block_stmt_iterator));
+ extern block_stmt_iterator pop_bsi	PARAMS ((bsi_list_p *));
+ 
+ 
+ /* Allocate a bsi_list structure.  */
+ static inline bsi_list_p
+ new_bsi_list ()
+ {
+   bsi_list_p b;
+   b = (bsi_list_p) xmalloc (sizeof (struct bsi_list_d));
+   b->curr_index = 0;
+   b->next = NULL;
+ 
+   return b;
+ }
+ 
+ /* Is the iterator stack empty?  */
+ static inline int
+ empty_bsi_stack (list)
+      bsi_list_p list;
+ {
+   if (!list || (list->curr_index < 0 && list->next == NULL))
+     return 1;
+   return 0;
+ }
+ 
+ 
+ /* Process an entire block of bsi's in reverse by pushing them on a stack
+    as they are encountered, and then popping them off as they are needed.  
+    There are a couple of odd things. Since the last loop is a for loop, 
+    a dummy entry is pushed on the beginning of the stack, this allows the first
+    item pushed on the stack to be processed in the final for loop, as well
+    as guaranteeing there will be at least one to pop off.  
+ 
+    usage:
+      bsi_list_p  stack;
+      block_stmt_iterator bsi;
+      basic_block bb;
+ 
+      FOR_EACH_BSI_IN_REVERSE (stack, bb, bsi)
+        {
+          ...
+        }
+ */
+ #define FOR_EACH_BSI_IN_REVERSE(bsi_stack, bb, bsi)		\
+   bsi_stack = new_bsi_list ();					\
+   for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))	\
+     push_bsi (&bsi_stack, bsi);					\
+   bsi = pop_bsi (&bsi_stack);					\
+   for ( ; !empty_bsi_stack (bsi_stack); bsi = pop_bsi (&bsi_stack))
+ 
+ 
+ 
+ /* This macro can be used if all that is ever examined is the stmt nodes
+    of bsi. Ie, if the usage is
+       FOR_EACH_BSI_IN_REVERSE (stack, bb, bsi) 
+         {
+ 	  tree stmt = bsi_stmt (bsi);
+ 	  ...
+   Then less overhead exists to simply use this macro.  
+ 
+   usage:
+     varray_type stmt_stack;
+     basic_block bb;
+     tree stmt;
+ 
+     FOR_EACH_STMT_IN_REVERSE (stmt_stack, bb, stmt)
+       {
+         ...
+       }
+ */
+ #define FOR_EACH_STMT_IN_REVERSE(stmt_stack, bb, stmt)		\
+   VARRAY_TREE_INIT (stmt_stack, 50, "stmt_stack");		\
+   VARRAY_PUSH_TREE (stmt_stack, NULL_TREE);			\
+   {								\
+     block_stmt_iterator bsi;					\
+     for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))	\
+       VARRAY_PUSH_TREE (stmt_stack, bsi_stmt (bsi));		\
+   }								\
+   stmt = VARRAY_TOP_TREE (stmt_stack);				\
+   VARRAY_POP (stmt_stack);					\
+   for ( ; VARRAY_ACTIVE_SIZE (stmt_stack) > 0 ; 		\
+ 	      stmt = VARRAY_TOP_TREE (stmt_stack), VARRAY_POP (stmt_stack))	
+ 
  #endif /* _TREE_FLOW_INLINE_H  */


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]