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]: Correct iteration order of calculate_reg_pav


The docs and comments claim it wants to iterate in reverse post order
numbers, however, it *actually* iterates in regular post order order.
That is what flow_reverse_topsort_order_compute computes.

I've taken it at face value that RPO is really the ordering you want.

The RPO numbers can be computed by flow_depth_first_order_compute.

I verified this by hand by writing the natural recursive postorder
traversal

bbs = result for flow_reverse_topsort_order_compute
bbs2 = result for regular postorder traversal

(gdb) p bbs[0]@17
$14 = {16, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 15, 0}
(gdb) p bbs2[0]@17
$14 = {16, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 15, 0}


Then, we look at the output of flow_depth_first_order_compute's
rc_array, and we get:

(gdb) p bbs[0]@17
$15 = {0, 15, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16}

IE reverse post order

Thus, i changed everything to use what it claims it wants to use, which
seems right since it is a forward dataflow problem.

Bootstrapped and regtested on i686-pc-linux-gnu.
Okay for mainline?
2005-09-14  Daniel Berlin  <dberlin@dberlin.org>

	* global.c (set_up_bb_rpo_numbers): Renamed from
	set_up_bb_rts_numbers.
	rts_number->rpo_number.
	Use flow_depth_first_order_compute.
	(struct bb_info): rts_number->rpo_number.
	(rpost_cmp): Ditto.
	(make_accurate_live_analysis): Ditto.
Index: global.c
===================================================================
RCS file: /cvs/gcc/gcc/gcc/global.c,v
retrieving revision 1.132
diff -u -p -r1.132 global.c
--- global.c	1 Sep 2005 05:29:02 -0000	1.132
+++ global.c	14 Sep 2005 23:12:52 -0000
@@ -317,7 +317,7 @@ static bool check_earlyclobber (rtx);
 static void mark_reg_use_for_earlyclobber_1 (rtx *, void *);
 static int mark_reg_use_for_earlyclobber (rtx *, void *);
 static void calculate_local_reg_bb_info (void);
-static void set_up_bb_rts_numbers (void);
+static void set_up_bb_rpo_numbers (void);
 static int rpost_cmp (const void *, const void *);
 static void calculate_reg_pav (void);
 static void modify_reg_pav (void);
@@ -2011,7 +2011,7 @@ dump_global_regs (FILE *file)
 struct bb_info
 {
   /* The basic block reverse post-order number.  */
-  int rts_number;
+  int rpo_number;
   /* Registers used uninitialized in an insn in which there is an
      early clobbered register might get the same hard register.  */
   bitmap earlyclobber;
@@ -2276,16 +2276,16 @@ calculate_local_reg_bb_info (void)
    block.  */
 
 static void
-set_up_bb_rts_numbers (void)
+set_up_bb_rpo_numbers (void)
 {
   int i;
-  int *rts_order;
+  int *rpo_order;
   
-  rts_order = xmalloc (sizeof (int) * n_basic_blocks);
-  flow_reverse_top_sort_order_compute (rts_order);
+  rpo_order = xmalloc (sizeof (int) * n_basic_blocks);
+  flow_depth_first_order_compute (NULL, rpo_order);
   for (i = 0; i < n_basic_blocks; i++)
-    BB_INFO_BY_INDEX (rts_order [i])->rts_number = i;
-  free (rts_order);
+    BB_INFO_BY_INDEX (rpo_order [i])->rpo_number = i;
+  free (rpo_order);
 }
 
 /* Compare function for sorting blocks in reverse postorder.  */
@@ -2295,7 +2295,7 @@ rpost_cmp (const void *bb1, const void *
 {
   basic_block b1 = *(basic_block *) bb1, b2 = *(basic_block *) bb2;
 
-  return BB_INFO (b2)->rts_number - BB_INFO (b1)->rts_number;
+  return BB_INFO (b2)->rpo_number - BB_INFO (b1)->rpo_number;
 }
 
 /* Temporary bitmap used for live_pavin, live_pavout calculation.  */
@@ -2471,7 +2471,7 @@ make_accurate_live_analysis (void)
   compact_blocks ();
   allocate_bb_info ();
   calculate_local_reg_bb_info ();
-  set_up_bb_rts_numbers ();
+  set_up_bb_rpo_numbers ();
   calculate_reg_pav ();
   modify_reg_pav ();
   FOR_EACH_BB (bb)

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