[PATCH V2] IRA: Speed up setup_left_conflict_sizes_p

[PATCH V2] IRA: Speed up setup_left_conflict_sizes_p

[Zhouyi Zhou]

From: Zhouyi Zhou <zhouzhouyi@gmail.com>

In function setup_left_conflict_sizes_p, left conflict subnodes sizes
are computed in a bottom-to-up fashion through the regnodes foreast.

Speed up the process from prevent node itself to involve in this 
computation. 

I have no write access to GCC SVN repository, if it OK, can you commit
for me?

(Thanks Richard for reviewing)

Bootstrap and regtest scheduled on x86_64 GNU/Linux
Signed-off-by: Zhouyi Zhou <yizhouzhou@ict.ac.cn>
---
 gcc/ChangeLog   |    5 +++++
 gcc/ira-color.c |    8 +++-----
 2 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 53f582b..a495dfc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@
+2015-03-12  Zhouyi Zhou  <yizhouzhou@ict.ac.cn> 
+
+	* ira-color.c (setup_left_conflict_sizes_p): Prevent node itself
+	from computing left conflict subnodes size.
+	
 2015-03-10  Jan Hubicka  <hubicka@ucw.cz>
 
 	* cgraph.c (cgraph_node::release_body): Free function_in_decl_state.
diff --git a/gcc/ira-color.c b/gcc/ira-color.c
index ff1fe8a..d2d5102 100644
--- a/gcc/ira-color.c
+++ b/gcc/ira-color.c
@@ -938,7 +938,7 @@ setup_left_conflict_sizes_p (ira_allocno_t a)
       subnodes[i].left_conflict_subnodes_size = 0;
     }
   start = node_preorder_num * allocno_hard_regs_nodes_num;
-  for (i = data->hard_regs_subnodes_num - 1; i >= 0; i--)
+  for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
     {
       int size, parent_i;
       allocno_hard_regs_node_t parent;
@@ -948,12 +948,10 @@ setup_left_conflict_sizes_p (ira_allocno_t a)
 		     - subnodes[i].left_conflict_subnodes_size,
 		     subnodes[i].left_conflict_size));
       parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
-      if (parent == NULL)
-	continue;
+      gcc_checking_assert(parent);
       parent_i
 	= allocno_hard_regs_subnode_index[start + parent->preorder_num];
-      if (parent_i < 0)
-	continue;
+      gcc_checking_assert(parent_i >= 0);
       subnodes[parent_i].left_conflict_subnodes_size += size;
     }
   left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
-- 
1.7.10.4

Ping: [PATCH V2] IRA: Speed up setup_left_conflict_sizes_p

[Zhouyi Zhou]

Hi Vladimir,
  I am studying IRA in my offer hours because it is marvellous and very educative.
  Did you get a chance to look at the below patch.
  The elements of allocno_hard_regs_subnode_index are setup in function 
setup_allocno_hard_regs_subnode_index where elements representing subnodes of a node
are nonegative. I think we can avoid involving the parent itself into the loop below 
because when the loop invariant i == 0, allocno_hard_regs_nodes[i + node_preorder_num]
will be current node, I guess we are not interested in computing left conflict subnodes
size of current node's parent in current function context.

Thanks and Regards
Zhouyi
    
---------- Forwarded message ----------
From: Zhouyi Zhou <zhouzhouyi@gmail.com>
Date: Thu, Mar 12, 2015 at 9:34 AM
Subject: [PATCH V2] IRA: Speed up setup_left_conflict_sizes_p
To: gcc-patches@gcc.gnu.org, richard.guenther@gmail.com
Cc: Zhouyi Zhou <zhouzhouyi@gmail.com>, Zhouyi Zhou <yizhouzhou@ict.ac.cn>


From: Zhouyi Zhou <zhouzhouyi@gmail.com>

In function setup_left_conflict_sizes_p, left conflict subnodes sizes
are computed in a bottom-to-up fashion through the regnodes foreast.

Speed up the process from prevent node itself to involve in this
computation.

I have no write access to GCC SVN repository, if it OK, can you commit
for me?

(Thanks Richard for reviewing)

Bootstrap and regtest scheduled on x86_64 GNU/Linux
Signed-off-by: Zhouyi Zhou <yizhouzhou@ict.ac.cn>
---
 gcc/ChangeLog   |    5 +++++
 gcc/ira-color.c |    8 +++-----
 2 files changed, 8 insertions(+), 5 deletions(-)

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 53f582b..a495dfc 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,8 @@
+2015-03-12  Zhouyi Zhou  <yizhouzhou@ict.ac.cn>
+
+       * ira-color.c (setup_left_conflict_sizes_p): Prevent node itself
+       from computing left conflict subnodes size.
+
 2015-03-10  Jan Hubicka  <hubicka@ucw.cz>

        * cgraph.c (cgraph_node::release_body): Free function_in_decl_state.
diff --git a/gcc/ira-color.c b/gcc/ira-color.c
index ff1fe8a..d2d5102 100644
--- a/gcc/ira-color.c
+++ b/gcc/ira-color.c
@@ -938,7 +938,7 @@ setup_left_conflict_sizes_p (ira_allocno_t a)
       subnodes[i].left_conflict_subnodes_size = 0;
     }
   start = node_preorder_num * allocno_hard_regs_nodes_num;
-  for (i = data->hard_regs_subnodes_num - 1; i >= 0; i--)
+  for (i = data->hard_regs_subnodes_num - 1; i > 0; i--)
     {
       int size, parent_i;
       allocno_hard_regs_node_t parent;
@@ -948,12 +948,10 @@ setup_left_conflict_sizes_p (ira_allocno_t a)
                     - subnodes[i].left_conflict_subnodes_size,
                     subnodes[i].left_conflict_size));
       parent = allocno_hard_regs_nodes[i + node_preorder_num]->parent;
-      if (parent == NULL)
-       continue;
+      gcc_checking_assert(parent);
       parent_i
        = allocno_hard_regs_subnode_index[start + parent->preorder_num];
-      if (parent_i < 0)
-       continue;
+      gcc_checking_assert(parent_i >= 0);
       subnodes[parent_i].left_conflict_subnodes_size += size;
     }
   left_conflict_subnodes_size = subnodes[0].left_conflict_subnodes_size;
--
1.7.10.4

Re: Ping: [PATCH V2] IRA: Speed up setup_left_conflict_sizes_p

[Vladimir Makarov]

On 2015-03-23 9:50 PM, Zhouyi Zhou wrote:
> Hi Vladimir,
>   I am studying IRA in my offer hours because it is marvellous and very educative.

Thanks.  If you are interesting in RA whose code is available, you could
also look at Fred Chow's RA code in Pathscale compiler.
 
>   Did you get a chance to look at the below patch.
>   The elements of allocno_hard_regs_subnode_index are setup in function 
> setup_allocno_hard_regs_subnode_index where elements representing subnodes of a node
> are nonegative. I think we can avoid involving the parent itself into the loop below 
> because when the loop invariant i == 0, allocno_hard_regs_nodes[i + node_preorder_num]
> will be current node, I guess we are not interested in computing left conflict subnodes
> size of current node's parent in current function context.
>
Thanks for the patch.  I believe your patch is doing a right thing.  It
should be committed but I'd rather wait for stage1 start which probably
will happen in 2-3 weeks.

I'll commit your patch right after stage1 start.  If I don't do this at
this time, please ping me again, Zhouyi.

Re: [PATCH V2] IRA: Speed up setup_left_conflict_sizes_p

[Jeff Law]

On 03/11/2015 07:34 PM, Zhouyi Zhou wrote:
> From: Zhouyi Zhou <zhouzhouyi@gmail.com>
>
> In function setup_left_conflict_sizes_p, left conflict subnodes sizes
> are computed in a bottom-to-up fashion through the regnodes foreast.
>
> Speed up the process from prevent node itself to involve in this
> computation.
>
> I have no write access to GCC SVN repository, if it OK, can you commit
> for me?
>
> (Thanks Richard for reviewing)
>
> Bootstrap and regtest scheduled on x86_64 GNU/Linux
> Signed-off-by: Zhouyi Zhou <yizhouzhou@ict.ac.cn>
> ---
>   gcc/ChangeLog   |    5 +++++
>   gcc/ira-color.c |    8 +++-----
>   2 files changed, 8 insertions(+), 5 deletions(-)
>
> diff --git a/gcc/ChangeLog b/gcc/ChangeLog
> index 53f582b..a495dfc 100644
> --- a/gcc/ChangeLog
> +++ b/gcc/ChangeLog
> @@ -1,3 +1,8 @@
> +2015-03-12  Zhouyi Zhou  <yizhouzhou@ict.ac.cn>
> +
> +	* ira-color.c (setup_left_conflict_sizes_p): Prevent node itself
> +	from computing left conflict subnodes size.
Approved and installed after the usual bootstrap and regression testing.

Thanks,
jeff