SMS improvements branch

SMS improvements branch

[Mostafa Hagog]

There are several improvements of SMS that were introduced to 4.0 but
rejected and are waiting for 4.1 to open.  There is also additional
work that we are planning to do for improving SMS, here is a list
of the items and their status:
I. Infrastructure work:
    1. Change SMS to work in cfglayout mode. (DONE, for 4.1)
    2. Build and use loop information in SMS. (DONE, for 4.1)
    3. Add loop versioning to RTL (in cfglayout mode). (DONE, for 4.1)
    4. Loop peeling in SMS to make SMS applicable for more loops.
       (Started, for 4.1)
    5. Use doloop analysis instead of BCT to check for counted loops.
      (Started, for 4.1)
    6. Port tree data dependency analysis routines to the RTL level
       so we can have better dependancy. (Future, Beyond 4.1)
    7. Improve alias analysis in the RTL level. (Future, Beyond 4.1)

II. SMS related work :
   1. Use of alias sets to remove memory dependencies. (DONE, for 4.1)
   2. Remove register anti-dependencies. (DONE, for 4.1)
   3. Add backtracking to the SMS. (DONE, for 4.1)
   4. Consider register pressure in SMS. (Beyond 4.1)

I am thinking of opening a development branch for the sake of SMS
improvements, unless someone knows of an existing branch that
this work could be put in.

Mostafa.

Re: SMS improvements branch

[Dorit Naishlos]

> I am thinking of opening a development branch for the sake of SMS
> improvements, unless someone knows of an existing branch that
> this work could be put in.

I think the autovect-branch could be an option - it is intended to host
work on loop optimizations. Also sounds like some of the infrastructure you
need for SMS is related to infrastructure developed on autovect (inter-loop
dependences for example). Another thing in common to SMS and vectorization
is that both target single-basic-block countable loops. I don't know if SMS
would directly benefit from the tree-level loop-optimization work that
is/will be taking place in autovect-branch, but I'm sure vectorized loops
would benefit from SMS.

dorit




                                                                                                                                     
                      Mostafa                                                                                                        
                      Hagog/Haifa/IBM@I        To:       gcc@gcc.gnu.org                                                             
                      BMIL                     cc:                                                                                   
                      Sent by:                 Subject:  SMS improvements branch                                                     
                      gcc-owner@gcc.gnu                                                                                              
                      .org                                                                                                           
                                                                                                                                     
                                                                                                                                     
                      09/12/2004 21:45                                                                                               
                                                                                                                                     








There are several improvements of SMS that were introduced to 4.0 but
rejected and are waiting for 4.1 to open.  There is also additional
work that we are planning to do for improving SMS, here is a list
of the items and their status:
I. Infrastructure work:
    1. Change SMS to work in cfglayout mode. (DONE, for 4.1)
    2. Build and use loop information in SMS. (DONE, for 4.1)
    3. Add loop versioning to RTL (in cfglayout mode). (DONE, for 4.1)
    4. Loop peeling in SMS to make SMS applicable for more loops.
       (Started, for 4.1)
    5. Use doloop analysis instead of BCT to check for counted loops.
      (Started, for 4.1)
    6. Port tree data dependency analysis routines to the RTL level
       so we can have better dependancy. (Future, Beyond 4.1)
    7. Improve alias analysis in the RTL level. (Future, Beyond 4.1)

II. SMS related work :
   1. Use of alias sets to remove memory dependencies. (DONE, for 4.1)
   2. Remove register anti-dependencies. (DONE, for 4.1)
   3. Add backtracking to the SMS. (DONE, for 4.1)
   4. Consider register pressure in SMS. (Beyond 4.1)

I am thinking of opening a development branch for the sake of SMS
improvements, unless someone knows of an existing branch that
this work could be put in.

Mostafa.

Re: SMS improvements branch

[Sebastian Pop]

On Thu, Dec 09, 2004 at 09:45:41PM +0200, Mostafa Hagog wrote:
> 
>     6. Port tree data dependency analysis routines to the RTL level
>        so we can have better dependancy. (Future, Beyond 4.1)

Seems a reasonable alternative approach to the transmission of data
dependence information from GIMPLE to the RTL level.

However (the following is just a guess, I have no numbers ;-) at RTL
level, a data dependence analyzer would obtain less precise
information than at tree level, because the informations such as the
dimensions of arrays are lost.  There are solutions for each of the
problems that could occur during the data dependence analysis at RTL
level, and this is why I have said that it was just a guess.

> II. SMS related work :
>    1. Use of alias sets to remove memory dependencies. (DONE, for 4.1)
>    2. Remove register anti-dependencies. (DONE, for 4.1)
>    3. Add backtracking to the SMS. (DONE, for 4.1)
>    4. Consider register pressure in SMS. (Beyond 4.1)
> 

Sid-Ahmed-Ali Touati has pointed me to the following report by the
author of the SMS algorithm, that shows some drawbacks of the SMS
algorithm:

http://www.hpl.hp.com/techreports/2002/HPL-2002-239.html

but anyway, you're probably aware of this work.

Sebastian

Re: SMS improvements branch

[Mostafa Hagog]

gcc-owner@gcc.gnu.org wrote on 12/12/2004 13:35:48:

>
>
>
>
> > I am thinking of opening a development branch for the sake of SMS
> > improvements, unless someone knows of an existing branch that
> > this work could be put in.
>
> I think the autovect-branch could be an option - it is intended to host
> work on loop optimizations. Also sounds like some of the infrastructure
you
> need for SMS is related to infrastructure developed on autovect
(inter-loop
> dependences for example). Another thing in common to SMS and
vectorization
> is that both target single-basic-block countable loops. I don't know if
SMS
> would directly benefit from the tree-level loop-optimization work that
> is/will be taking place in autovect-branch, but I'm sure vectorized loops
> would benefit from SMS.

OK, if no one from the autovect-branch developers has an objection about
it,
I am going to commit SMS changes to autovect-branch.

Mostafa.

Re: SMS improvements branch

[Devang Patel]

On Dec 23, 2004, at 6:40 AM, Mostafa Hagog wrote:

> OK, if no one from the autovect-branch developers has an objection 
> about
> it,
> I am going to commit SMS changes to autovect-branch.

Fine with me :)
-
Devang