PATCH: Re: A user question (was: Re: Faster compilation speed)

PATCH: Re: A user question (was: Re: Faster compilation speed)

[Mike Stump]

On Tuesday, August 13, 2002, at 02:29 PM, Mike Stump wrote:
> On Tuesday, August 13, 2002, at 10:37 AM, Marco Morandini wrote:
>> With Version 1 of the code below the compile time at -O2
>> is approx a quadratic function of the number of call to pippo(a);
>
> Yes, this seems wrong.  I'll take a look.

:-(  The biggest single culprit count wise is some aggressive checking 
code.  The below change save 1.5 minutes of compile time out of 5 
minutes on an n=20,000 case.  The top of the tree is much worse than a 
gcc 3.1 compiler, 5 minutes compared to 56 seconds.

The call count_or_remove_death_notes at:

           2      if (CHECK_DEAD_NOTES)
                     {
            2          blocks = sbitmap_alloc (last_basic_block);
            2          deaths_in_region = (int *) xmalloc (sizeof (int) 
* nr_regions);
                       /* Remove all death notes from the subroutine.  */
        40008          for (rgn = 0; rgn < nr_regions; rgn++)
                         {
        40006              int b;

        40006              sbitmap_zero (blocks);
        80012              for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b)
        40006                SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS 
(rgn) + b]);

        40006              deaths_in_region[rgn] = 
count_or_remove_death_notes (blocks, 1);
                         }
            2          sbitmap_free (blocks);
                     }
                   else
                     count_or_remove_death_notes (NULL, 1);
                 }

and:

            2      if (CHECK_DEAD_NOTES)
                     {
                       /* Verify the counts of basic block notes in 
single the basic block
                          regions.  */
        40008          for (rgn = 0; rgn < nr_regions; rgn++)
        40006            if (RGN_NR_BLOCKS (rgn) == 1)
                           {
        40006                sbitmap_zero (blocks);
        40006                SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS 
(rgn)]);

        40006                if (deaths_in_region[rgn]
                                 != count_or_remove_death_notes (blocks, 
0))
       ######                  abort ();
                           }
            2          free (deaths_in_region);
                     }

winds up calling into

                 int
                 count_or_remove_death_notes (blocks, kill)
                      sbitmap blocks;
                      int kill;
        80012    {
        80012      int count = 0;
        80012      basic_block bb;

   1600560048      FOR_EACH_BB_REVERSE (bb)
                     {
   1600480036          rtx insn;

   1600480036          if (blocks && ! TEST_BIT (blocks, bb->index))
   1600400024            continue;

thus chewing up lots of time.  The number was picked to keep the 
checking time reasonable (1.6 seconds), if one wants, we can entertain 
larger values for the limit.


2002-08-13  Mike Stump  <mrs@apple.com>

         * sched-rgn.c (CHECK_DEAD_NOTES): Limit how much checking we do 
to
         avoid n^2 behavior.

Doing diffs in sched-rgn.c.~1.48.~:
*** sched-rgn.c.~1.48.~ Tue Aug 13 16:00:48 2002
--- sched-rgn.c Tue Aug 13 16:34:50 2002
*************** Software Foundation, 59 Temple Place - S
*** 66,75 ****

   /* Define when we want to do count REG_DEAD notes before and after 
scheduling
      for sanity checking.  We can't do that when conditional execution 
is used,
!    as REG_DEAD exist only for unconditional deaths.  */

   #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
! #define CHECK_DEAD_NOTES 1
   #else
   #define CHECK_DEAD_NOTES 0
   #endif
--- 66,76 ----

   /* Define when we want to do count REG_DEAD notes before and after 
scheduling
      for sanity checking.  We can't do that when conditional execution 
is used,
!    as REG_DEAD exist only for unconditional deaths.  Also, we don't 
want to
!    check them if there are many regions, as the algorithm is n^2.  */

   #if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING)
! #define CHECK_DEAD_NOTES 1 && nr_regions < 1000
   #else
   #define CHECK_DEAD_NOTES 0
   #endif
--------------

Re: PATCH: Re: A user question (was: Re: Faster compilation speed)

[Richard Henderson]

On Tue, Aug 13, 2002 at 05:06:42PM -0700, Mike Stump wrote:
>       * sched-rgn.c (CHECK_DEAD_NOTES): Limit how much checking
>	we do to avoid n^2 behavior.

I don't like it.

Instead, arrange to make a single pass across the rtl removing
and counting death notes and storing the counts into an array
indexed by basic block.  The add up the counts for each block
in the region as is sort of done currently.



r~

Re: PATCH: Re: A user question (was: Re: Faster compilation speed)

[Michael Matz]

Hi,

On Tue, 13 Aug 2002, Mike Stump wrote:

> :-(  The biggest single culprit count wise is some aggressive checking
> code.  The below change save 1.5 minutes of compile time out of 5
> minutes on an n=20,000 case.  The top of the tree is much worse than a
> gcc 3.1 compiler, 5 minutes compared to 56 seconds.

This is a typical case why I strongly dislike such arbitrary cutoff means
to avoid slow behaviour instead of redesigning how it works.  From the
code you posted it seems, that the blocks bitmap is extremely sparse (in
the second loop only one bit is set in evry case, the second loop only
seems to set one bit each time by pure luck), but still it's completely
traversed, through pointer chasing even (the bb double linked list).
This suggests to change the interface of count_or_remove_death_notes() to
take a bitmap (not sbitmap), and rearrange the outer loop of it, to use
EXECUTE_IF_SET_IN_BITMAP().


Ciao,
Michael.

Re: PATCH: Re: A user question (was: Re: Faster compilation speed)

[Michael Matz]

On Wed, 14 Aug 2002, Michael Matz wrote:

> code you posted it seems, that the blocks bitmap is extremely sparse (in
> the second loop only one bit is set in evry case, the second loop only
                                                        ^^^^^^
                                                        first of course

> seems to set one bit each time by pure luck), but still it's completely


Ciao,
Michael.