[Bug middle-end/37567] New: tree SSA to normal checking takes abnormally long time

[Bug middle-end/37567] New: tree SSA to normal checking takes abnormally long time

[lucier at math dot purdue dot edu]

When configured with

Configured with: ../../mainline/configure --with-gmp=/pkgs/gmp-4.2.2/
--with-mpfr=/pkgs/gmp-4.2.2/ --prefix=/pkgs/gcc-mainline
--enable-gather-detailed-mem-stats

and run on the testcase of PR 26854 with

/pkgs/gcc-mainline/bin/gcc -Wall -W -Wno-unused -O1 -fno-math-errno
-fschedule-insns2 -fno-trapping-math -fno-strict-aliasing -fwrapv
-fomit-frame-pointer -fPIC -ftime-report -fmem-report -c all.i >>&
mainline-stats-2008-09-17-c

one line stands out:

 tree SSA to normal    : 485.81 (61%) usr   0.12 ( 0%) sys 486.01 (59%) wall  
93945 kB (12%) ggc
 TOTAL                 : 793.99            24.78           819.45            
795105 kB

without checking, this is

 tree SSA to normal    :  13.31 ( 8%) usr   0.10 ( 1%) sys  13.42 ( 7%) wall  
93945 kB (12%) ggc
 TOTAL                 : 168.33            14.57           183.12            
794201 kB

The timings of other parts of a checking-enabled compiler seem reasonable.


-- 
           Summary: tree SSA to normal checking takes abnormally long time
           Product: gcc
           Version: 4.4.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: middle-end
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: lucier at math dot purdue dot edu
 GCC build triplet: x86_64-unknown-linux-gnu
  GCC host triplet: x86_64-unknown-linux-gnu
GCC target triplet: x86_64-unknown-linux-gnu


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[rguenth at gcc dot gnu dot org]

------- Comment #1 from rguenth at gcc dot gnu dot org  2008-09-18 08:49 -------
While there's a lot of checking code in out-of-ssa I don't see any that
should cause this slowdown.  Can you possibly profile it and point to
the worts offender?


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |rguenth at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[amacleod at redhat dot com]

------- Comment #2 from amacleod at redhat dot com  2008-09-18 20:00 -------
I will also look into it and take out some of the excess checking which is
probably not necessary anymore.


-- 

amacleod at redhat dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |amacleod at redhat dot com
                   |dot org                     |
             Status|UNCONFIRMED                 |ASSIGNED
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2008-09-18 20:00:46
               date|                            |


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[lucier at math dot purdue dot edu]

------- Comment #3 from lucier at math dot purdue dot edu  2008-09-18 20:07 -------
Created an attachment (id=16358)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16358&action=view)
gprof output for the test case

The compiler (which was bootstrapped with BOOT_CFLAGS='-O2 -g -pg'):

Using built-in specs.
Target: x86_64-unknown-linux-gnu
Configured with: ../../mainline/configure --with-gmp=/pkgs/gmp-4.2.2/
--with-mpfr=/pkgs/gmp-4.2.2/ --prefix=/pkgs/gcc-mainline --enable-languages=c
--enable-gather-detailed-mem-stats
Thread model: posix
gcc version 4.4.0 20080917 (experimental) [trunk revision 140425] (GCC) 
GNU C (GCC) version 4.4.0 20080917 (experimental) [trunk revision 140425]
(x86_64-unknown-linux-gnu)
        compiled by GNU C version 4.4.0 20080917 (experimental) [trunk revision
140425], GMP version 4.2.2, MPFR version 2.3.0-p4.
GGC heuristics: --param ggc-min-expand=30 --param ggc-min-heapsize=4096

the command line


/export/pkgs/gcc-mainline/bin/../libexec/gcc/x86_64-unknown-linux-gnu/4.4.0/cc1
-fpreprocessed all.i -quiet -dumpbase all.i -mtune=generic -auxbase all -O1
-Wall -W -Wno-unused -version -fno-math-errno -fschedule-insns2
-fno-trapping-math -fno-strict-aliasing -fwrapv -fomit-frame-pointer -fPIC
-ftime-report -fmem-report -o all.s >>& mainline-stats-2008-09-18

Highlights of the gprof output:

Flat profile:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
 63.13    422.59   422.59        3   140.86   141.03  find_replaceable_exprs

-----------------------------------------------
              422.59    0.50       3/3           rewrite_out_of_ssa [6]
[7]     63.2  422.59    0.50       3         find_replaceable_exprs [7]
                0.20    0.30   63203/63203       find_replaceable_in_bb [290]
                0.00    0.00       6/13254347     bitmap_obstack_free [162]
                0.00    0.00       6/6476878     bitmap_obstack_alloc_stat
[339]
-----------------------------------------------

Doesn't tell me much ...


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[lucier at math dot purdue dot edu]

------- Comment #4 from lucier at math dot purdue dot edu  2008-09-18 20:09 -------
Actually, it's pretty clear this is the problem:

extern gimple *
find_replaceable_exprs (var_map map)
{
  basic_block bb;
  temp_expr_table_p table;
  gimple *ret;

  table = new_temp_expr_table (map);
  FOR_EACH_BB (bb)
    {
      find_replaceable_in_bb (table, bb);
      gcc_assert (bitmap_empty_p (table->partition_in_use));

#ifdef ENABLE_CHECKING
      {
        unsigned i;
        /* Make sure all the tables have been cleared out.  */
        for (i = 0; i < num_ssa_names + 1; i++)
          {
            gcc_assert (table->partition_dependencies[i] == NULL);
            gcc_assert (table->expr_decl_uids[i] == NULL);
            if (i < num_var_partitions (map))
              gcc_assert (table->kill_list[i] == NULL);
          }
      }
#endif
    }

  ret = free_temp_expr_table (table);
  return ret;
}


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[amacleod at redhat dot com]

------- Comment #5 from amacleod at redhat dot com  2008-09-18 20:19 -------
huh, didn't I already see a patch go by to move this check to after all the
BB's were processed instead of doing it after each BB??


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[amacleod at redhat dot com]

------- Comment #6 from amacleod at redhat dot com  2008-09-18 20:23 -------
here it is

http://gcc.gnu.org/ml/gcc-patches/2008-09/msg01072.html


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[lucier at math dot purdue dot edu]

------- Comment #7 from lucier at math dot purdue dot edu  2008-09-18 20:28 -------
I just found it, too; it's been approved, but it hasn't been installed yet.

Wow, fixing bugs before they're reported, that's pretty efficient ;-)!

I'll wait until it's installed.

Thanks.


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[rguenth at gcc dot gnu dot org]

------- Comment #8 from rguenth at gcc dot gnu dot org  2008-09-19 08:36 -------
Indeed ;)  Honza, mention this PR in the changelog please.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |hubicka at gcc dot gnu dot
                   |                            |org


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[amacleod at redhat dot com]

------- Comment #9 from amacleod at redhat dot com  2008-09-19 13:27 -------
Created an attachment (id=16362)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=16362&action=view)
patch to fix the bug

Looking a little closer, Im going to change Honza's patch a little. Since the
checks are no longer being done after each BB is processed, they serve less
purpose, and are runn just before the free_() routine. 

Moving them to the free_ routine makes more sense, and when I did that, it was
clear then that there was a duplicate check there, as well as an extra loop of
potential free()s which could never be called.  so this cleans that all up.

I'll check this in once its finishes testing this morning


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[amacleod at gcc dot gnu dot org]

------- Comment #10 from amacleod at redhat dot com  2008-09-19 17:38 -------
Subject: Bug 37567

Author: amacleod
Date: Fri Sep 19 17:37:13 2008
New Revision: 140494

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=140494
Log:

        PR middle-end/37567
        * tree-ssa-ter.c (free_temp_expr_table): Make sure fields are actually
        empty before freeing them.
        (find_replaceable_exprs): Move asserts to free_temp_expr_table.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/tree-ssa-ter.c


-- 


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567

[Bug middle-end/37567] tree SSA to normal checking takes abnormally long time

[lucier at math dot purdue dot edu]

------- Comment #11 from lucier at math dot purdue dot edu  2008-09-26 15:33 -------
This problem is fixed by my reckoning, so I'm taking the liberty of closing the
bug report.


-- 

lucier at math dot purdue dot edu changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|ASSIGNED                    |RESOLVED
         Resolution|                            |FIXED


http://gcc.gnu.org/bugzilla/show_bug.cgi?id=37567