[Bug tree-optimization/31412] New: [4.3] inf loop/long compile time, time spent in var-tracking.c

[Bug tree-optimization/31412] New: [4.3] inf loop/long compile time, time spent in var-tracking.c

[tbm at cyrius dot com]

GCC 4.3 spent several hours compiling the attached program before I gave up.
I have no idea whether it would ever complete or not.  All I know is that it
is spending an awful lot of time in var-tracking.c.

You need the following parameters to see this problem:

-g -O1 -fno-strict-aliasing -fwrapv -fexpensive-optimizations -fforce-addr
-fPIC

This is on x86_64, btw; I believe the program compiles on ia64, but I'm
not sure.

In the hours that GCC ran, it spent all its time in vt_find_locations():

#3  0x00000000007b6cd1 in vt_find_locations () at gcc/var-tracking.c:1858
#4  0x00000000007b9f14 in variable_tracking_main () at gcc/var-tracking.c:2976
#5  0x00000000005f2fe1 in execute_one_pass (pass=0xcd8b20) at gcc/passes.c:1058
#6  0x00000000005f319c in execute_pass_list (pass=0xcd8b20)
    at gcc/passes.c:1110
#7  0x00000000005f31ae in execute_pass_list (pass=0xcd5f40)
    at gcc/passes.c:1111
#8  0x00000000005f31ae in execute_pass_list (pass=0xcd5ee0)
    at gcc/passes.c:1111
#9  0x00000000006c0028 in tree_rest_of_compilation (fndecl=0x2ae7782e9ee0)
    at gcc/tree-optimize.c:412
#10 0x0000000000440cd1 in c_expand_body (fndecl=0x61a12c8)
    at gcc/c-common.c:4285
#11 0x00000000007f5e40 in cgraph_expand_function (node=0x2ae77878b000)
    at gcc/cgraphunit.c:1015
#12 0x00000000007f80c2 in cgraph_optimize () at gcc/cgraphunit.c:1084
#13 0x00000000004145e9 in c_write_global_declarations () at gcc/c-decl.c:7930
#14 0x000000000066c13d in toplev_main (argc=<value optimized out>, argv=<value
optimized out>)
    at gcc/toplev.c:1063
#15 0x00002ae777a024ca in __libc_start_main () from /lib/libc.so.6
#16 0x0000000000403c7a in _start () at ../sysdeps/x86_64/elf/start.S:113

Richi, do you think you could take a look?


-- 
           Summary: [4.3] inf loop/long compile time, time spent in var-
                    tracking.c
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: tree-optimization
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: tbm at cyrius dot com


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

[Bug tree-optimization/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[tbm at cyrius dot com]

------- Comment #1 from tbm at cyrius dot com  2007-03-31 18:20 -------
Created an attachment (id=13309)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13309&action=view)
preprocessed source


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[tbm at cyrius dot com]

------- Comment #2 from tbm at cyrius dot com  2007-03-31 18:29 -------
Created an attachment (id=13310)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=13310&action=view)
preprocessed source

I attached the wrong file before.  This one is correct.


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[rguenth at gcc dot gnu dot org]

------- Comment #3 from rguenth at gcc dot gnu dot org  2007-04-03 13:24 -------
Well, vt_find_locations is quadratic in the number of edges and basic blocks
which
we have a _lot_ in this testcase.  Now, with the dataflow rewrite there may be
an easier way to compute the df problem.  Maybe Paolo has a suggestion here...


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |bonzini at gnu dot org
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-04-03 13:24:54
               date|                            |


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[rguenth at gcc dot gnu dot org]

------- Comment #4 from rguenth at gcc dot gnu dot org  2007-04-03 13:30 -------
The easiest thing is probably to ignore abnormal edges:

Index: var-tracking.c
===================================================================
*** var-tracking.c      (revision 123450)
--- var-tracking.c      (working copy)
*************** vt_find_locations (void)
*** 1855,1861 ****
              dataflow_set_clear (&VTI (bb)->in);
              FOR_EACH_EDGE (e, ei, bb->preds)
                {
!                 dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
                }

              changed = compute_bb_dataflow (bb);
--- 1855,1862 ----
              dataflow_set_clear (&VTI (bb)->in);
              FOR_EACH_EDGE (e, ei, bb->preds)
                {
!                 if (!(e->flags & EDGE_ABNORMAL))
!                   dataflow_set_union (&VTI (bb)->in, &VTI (e->src)->out);
                }

              changed = compute_bb_dataflow (bb);


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[bonzini at gnu dot org]

------- Comment #5 from bonzini at gnu dot org  2007-04-03 13:31 -------
well, for sure it would be possible to use df and a good example of that too. 
But I'm not *that* knowledgeable about the df-*.c implementation.


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[bonzini at gnu dot org]

------- Comment #6 from bonzini at gnu dot org  2007-04-03 13:33 -------
anyway, the code looks well written.  the dataflow_set_* functions look
inefficient, though.  maybe it's also possible to replace hash tables with
pointer maps (there is a 1:1 relationships between decl nodes and their
DECL_UID, right?)


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[rguenth at gcc dot gnu dot org]

------- Comment #7 from rguenth at gcc dot gnu dot org  2007-04-03 13:36 -------
Ok, let's defer a solution to after the df merge.  Certainly something to look
at.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zadeck at naturalbridge dot
                   |                            |com


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[bonzini at gnu dot org]

------- Comment #8 from bonzini at gnu dot org  2007-04-03 13:38 -------
I wouldn't say so.  If there is a bug and the df solver oscillates, that's the
reason for the infinite loop.


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[rguenth at gcc dot gnu dot org]

------- Comment #9 from rguenth at gcc dot gnu dot org  2007-04-03 13:45 -------
If I ignore abnormal edges the computation finishes.  Of course I have no idea
what happens in that case ;)


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[rguenth at gcc dot gnu dot org]

------- Comment #10 from rguenth at gcc dot gnu dot org  2007-04-03 13:50 -------
At least all the attr_list stuff is O(N) as it uses a linked list for

static attrs
attrs_list_member (attrs list, tree decl, HOST_WIDE_INT offset)
{
  for (; list; list = list->next)
    if (list->decl == decl && list->offset == offset)
      return list;
  return NULL;
}

static void
attrs_list_union (attrs *dstp, attrs src)
{
  for (; src; src = src->next)
    {
      if (!attrs_list_member (*dstp, src->decl, src->offset))
        attrs_list_insert (dstp, src->decl, src->offset, src->loc);
    }
}

(thats quadratic already, ugh)

it's a map of <decl, offset> mapping to a rtx location.


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[rguenth at gcc dot gnu dot org]

------- Comment #11 from rguenth at gcc dot gnu dot org  2007-04-03 13:56 -------
With dataflow branch that was compiled with profiling the testcase finishes
not too slow:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls   s/call   s/call  name    
  7.48      1.07     1.07        3     0.36     1.37  vt_find_locations
  5.59      1.87     0.80  6339766     0.00     0.00  variable_union
  4.69      2.54     0.67  3617450     0.00     0.00  htab_find_with_hash
  4.06      3.12     0.58 14114686     0.00     0.00  htab_find_slot_with_hash
  2.80      3.52     0.40   810633     0.00     0.00  bitmap_ior_into
  2.73      3.91     0.39 65064909     0.00     0.00  int_tree_map_eq
  1.61      4.14     0.23  8049101     0.00     0.00  bitmap_elt_insert_after
  1.54      4.36     0.22   271906     0.00     0.00  htab_traverse_noresize
  1.50      4.58     0.22 10925677     0.00     0.00  bitmap_bit_p
  1.40      4.78     0.20 12645563     0.00     0.00  pool_alloc
  1.33      4.97     0.19      431     0.00     0.00 
add_location_or_const_valu
e_attribute
  1.19      5.14     0.17  3991364     0.00     0.00  mark_insn
  1.12      5.30     0.16   101241     0.00     0.00 
df_chain_create_bb_process
_use
  1.12      5.46     0.16       94     0.00     0.01  df_worklist_dataflow
  1.05      5.61     0.15 13657110     0.00     0.00  variable_htab_eq
  0.98      5.75     0.14  6126572     0.00     0.00  variable_htab_hash


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[paolo dot bonzini at lu dot unisi dot ch]

------- Comment #12 from paolo dot bonzini at lu dot unisi dot ch  2007-04-03 13:59 -------
Subject: Re:  [4.3] inf loop/long compile time, time spent
 in var-tracking.c


> With dataflow branch that was compiled with profiling the testcase finishes
> not too slow:

This suggest that it is a bug in the dataflow computation, causing
it to oscillate and not terminate.  Different RTL just causes the
bug not to trigger.

Paolo


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[steven at gcc dot gnu dot org]

------- Comment #13 from steven at gcc dot gnu dot org  2007-04-03 16:40 -------
So this may be a non-monotonous dataflow problem...?

Do we have the dataflow equations of the var-tracking problem somewhere?  It'd
be interesting to check them against the actual implementation.


-- 


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

[Bug debug/31412] [4.3] inf loop/long compile time, time spent in var-tracking.c

[zadeck at naturalbridge dot com]

------- Comment #14 from zadeck at naturalbridge dot com  2007-04-03 16:47 -------
Subject: Re:  [4.3] inf loop/long compile time, time spent
 in var-tracking.c

steven at gcc dot gnu dot org wrote:
> ------- Comment #13 from steven at gcc dot gnu dot org  2007-04-03 16:40 -------
> So this may be a non-monotonous dataflow problem...?
>
> Do we have the dataflow equations of the var-tracking problem somewhere?  It'd
> be interesting to check them against the actual implementation.
>
>
>   
this is a pretty complex problem.  I gave it a cursory once over and it
looks like the problem may not terminate if the location (stack offset)
of a variable is not the same on all paths into a block.  (the code may
be different than the comments and i did just scan this) I assume that
this case has a "bug" where a variable appears to be at a different
location coming across an exception edge. 


-- 


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

[Bug debug/31412] inf loop/long compile time, time spent in var-tracking.c

[rguenth at gcc dot gnu dot org]

------- Comment #15 from rguenth at gcc dot gnu dot org  2007-10-24 12:01 -------
Btw, I can no longer reproduce the problem.  var-tracking is not fast, but
even a cc1 compiled with checking and -O0 does not take multiple hours to
compile this (but just a minute):

 variable tracking     :  11.34 (23%) usr   0.20 (12%) sys  11.54 (23%) wall  
46131 kB (25%) ggc
 TOTAL                 :  48.36             1.66            50.07            
183405 kB


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |WAITING
            Summary|[4.3] inf loop/long compile |inf loop/long compile time,
                   |time, time spent in var-    |time spent in var-tracking.c
                   |tracking.c                  |


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

[Bug debug/31412] inf loop/long compile time, time spent in var-tracking.c

[zadeck at naturalbridge dot com]

------- Comment #16 from zadeck at naturalbridge dot com  2007-10-24 12:14 -------
Subject: Re:  inf loop/long compile time, time spent in var-tracking.c

rguenth at gcc dot gnu dot org wrote:
> ------- Comment #15 from rguenth at gcc dot gnu dot org  2007-10-24 12:01 -------
> Btw, I can no longer reproduce the problem.  var-tracking is not fast, but
> even a cc1 compiled with checking and -O0 does not take multiple hours to
> compile this (but just a minute):
>
>  variable tracking     :  11.34 (23%) usr   0.20 (12%) sys  11.54 (23%) wall  
> 46131 kB (25%) ggc
>  TOTAL                 :  48.36             1.66            50.07            
> 183405 kB
>
>
>   
I think that given the most likely cause of the problem, the problem is
just hiding.  My guess is that the problem is that there is an oddball
case where the dataflow equations do not converge and we will see this
again.  But it is clearly very rare.

kenny


-- 


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

[Bug debug/31412] inf loop/long compile time, time spent in var-tracking.c

[jason at gcc dot gnu dot org]

------- Comment #17 from jason at gcc dot gnu dot org  2008-02-12 06:44 -------
PR 35065 has a testcase that exhibits this same bug in the current pre-4.3.0
sources.


-- 

jason at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
OtherBugsDependingO|                            |35065
              nThis|                            |
             Status|WAITING                     |NEW
   Last reconfirmed|2007-04-03 13:24:54         |2008-02-12 06:44:30
               date|                            |


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

[Bug debug/31412] var-tracking.c is slow

[rguenth at gcc dot gnu dot org]

------- Comment #18 from rguenth at gcc dot gnu dot org  2008-02-13 15:03 -------
I'll leave this PR open because the testcase shows the bad compile-time
performance of the var-tracking df solver in general.  The original bug,
infinite compile-time is probably fixed.


-- 

rguenth at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|inf loop/long compile time, |var-tracking.c is slow
                   |time spent in var-tracking.c|


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

[Bug debug/31412] var-tracking.c is slow

[rguenth at gcc dot gnu dot org]

------- Comment #19 from rguenth at gcc dot gnu dot org  2008-02-13 15:12 -------

 variable tracking     :   6.52 (17%) usr   0.10 ( 7%) sys   6.62 (17%) wall  
41452 kB (25%) ggc

so this is still in the same order of magnitude than with the earlier reports.


-- 


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