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

[Mike Stump <mrs at apple dot com>]

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
--------------