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]

[patch] O(1) PHI argument look-up - Part 1/n


Hi,

Attached is a patch to part 1 of my O(1) PHI argument look-up patch.

This patch adds a new member, dest_idx, to edge_def.  dest_idx is the
index of an edge within its destination edge vector.  In other words,
for any edge e, we establish

  EDGE_PRED (e->dest, e->dest_idx) == e

Currently, the only use of this dest_idx is to simplify remove_edge
and redirect_edge_succ, but when a PHI array is lined up with its
corresponding edge vector in near future, this dest_idx allows faster
access to PHI arguments given an edge.

To keep dest_idx consistent, I update it appropriately in remove_edge
and redirect_edge_succ.  Also, the patch adds a consistentcy check in
verify_flow_info.

On some testcases, including insn-attrtab.c, this patch itself brings
an improvement.

Tested on i686-pc-linux-gnu.  OK to apply?

Kazu Hirata

2004-11-18  Kazu Hirata  <kazu@cs.umass.edu>

	* basic-block.h (edge_def): Add dest_idx.
	* cfg.c (unchecked_make_edge): Initialize dest_idx.
	(remove_edge): Simplify the disconnection of an edge from its
	destination.
	(redirect_edge_succ): Likewise.
	* cfghooks.c (verify_flow_info): Check the consistency of
	dest_idx for each edge.

Index: basic-block.h
===================================================================
RCS file: /cvs/gcc/gcc/gcc/basic-block.h,v
retrieving revision 1.227
diff -c -d -p -r1.227 basic-block.h
*** basic-block.h	17 Nov 2004 22:05:58 -0000	1.227
--- basic-block.h	18 Nov 2004 06:49:17 -0000
*************** struct edge_def GTY(())
*** 154,159 ****
--- 154,162 ----
    int probability;		/* biased by REG_BR_PROB_BASE */
    gcov_type count;		/* Expected number of executions calculated
  				   in profile.c  */
+ 
+   /* The index within edge vector dest->preds.  */
+   unsigned int dest_idx;
  };
  
  typedef struct edge_def *edge;
Index: cfg.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfg.c,v
retrieving revision 1.73
diff -c -d -p -r1.73 cfg.c
*** cfg.c	9 Nov 2004 04:21:49 -0000	1.73
--- cfg.c	18 Nov 2004 06:49:17 -0000
*************** unchecked_make_edge (basic_block src, ba
*** 276,281 ****
--- 276,282 ----
    e->src = src;
    e->dest = dst;
    e->flags = flags;
+   e->dest_idx = EDGE_COUNT (dst->preds) - 1;
  
    return e;
  }
*************** remove_edge (edge e)
*** 355,365 ****
--- 356,368 ----
  {
    edge tmp;
    basic_block src, dest;
+   unsigned int dest_idx;
    bool found = false;
    edge_iterator ei;
  
    src = e->src;
    dest = e->dest;
+   dest_idx = e->dest_idx;
  
    for (ei = ei_start (src->succs); (tmp = ei_safe_edge (ei)); )
      {
*************** remove_edge (edge e)
*** 375,394 ****
  
    gcc_assert (found);
  
!   found = false;
!   for (ei = ei_start (dest->preds); (tmp = ei_safe_edge (ei)); )
!     {
!       if (tmp == e)
! 	{
! 	  VEC_unordered_remove (edge, dest->preds, ei.index);
! 	  found = true;
! 	  break;
! 	}
!       else
! 	ei_next (&ei);
!     }
! 
!   gcc_assert (found);
  
    free_edge (e);
  }
--- 378,386 ----
  
    gcc_assert (found);
  
!   VEC_unordered_remove (edge, dest->preds, dest_idx);
!   if (dest_idx < EDGE_COUNT (dest->preds))
!     EDGE_I (dest->preds, dest_idx)->dest_idx = dest_idx;
  
    free_edge (e);
  }
*************** remove_edge (edge e)
*** 398,425 ****
  void
  redirect_edge_succ (edge e, basic_block new_succ)
  {
!   edge tmp;
!   edge_iterator ei;
!   bool found = false;
! 
!   /* Disconnect the edge from the old successor block.  */
!   for (ei = ei_start (e->dest->preds); (tmp = ei_safe_edge (ei)); )
!     {
!       if (tmp == e)
! 	{
! 	  VEC_unordered_remove (edge, e->dest->preds, ei.index);
! 	  found = true;
! 	  break;
! 	}
!       else
! 	ei_next (&ei);
!     }
  
!   gcc_assert (found);
  
    /* Reconnect the edge to the new successor block.  */
    VEC_safe_push (edge, new_succ->preds, e);
    e->dest = new_succ;
  }
  
  /* Like previous but avoid possible duplicate edge.  */
--- 390,406 ----
  void
  redirect_edge_succ (edge e, basic_block new_succ)
  {
!   basic_block dest = e->dest;
!   unsigned int dest_idx = e->dest_idx;
  
!   VEC_unordered_remove (edge, dest->preds, dest_idx);
!   if (dest_idx < EDGE_COUNT (dest->preds))
!     EDGE_I (dest->preds, dest_idx)->dest_idx = dest_idx;
  
    /* Reconnect the edge to the new successor block.  */
    VEC_safe_push (edge, new_succ->preds, e);
    e->dest = new_succ;
+   e->dest_idx = EDGE_COUNT (new_succ->preds) - 1;
  }
  
  /* Like previous but avoid possible duplicate edge.  */
Index: cfghooks.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/cfghooks.c,v
retrieving revision 1.18
diff -c -d -p -r1.18 cfghooks.c
*** cfghooks.c	4 Nov 2004 22:02:55 -0000	1.18
--- cfghooks.c	18 Nov 2004 06:49:18 -0000
*************** verify_flow_info (void)
*** 178,183 ****
--- 178,197 ----
  	      fputc ('\n', stderr);
  	      err = 1;
  	    }
+ 
+ 	  if (ei.index != e->dest_idx)
+ 	    {
+ 	      error ("basic block %d pred edge is corrupted", bb->index);
+ 	      error ("its dest_idx should be %d, not %d",
+ 		     ei.index, e->dest_idx);
+ 	      fputs ("Predecessor: ", stderr);
+ 	      dump_edge_info (stderr, e, 0);
+ 	      fputs ("\nSuccessor: ", stderr);
+ 	      dump_edge_info (stderr, e, 1);
+ 	      fputc ('\n', stderr);
+ 	      err = 1;
+ 	    }
+ 
  	  edge_checksum[e->dest->index + 2] -= (size_t) e;
  	}
      }


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