Bug 63338

Summary: Compiling large amounts of large switch cases takes a large amount of time
Product: gcc Reporter: Steven Stewart-Gallus <sstewartgallus00>
Component: tree-optimizationAssignee: Not yet assigned to anyone <unassigned>
Status: NEW ---    
Severity: normal CC: dimhen
Priority: P3 Keywords: compile-time-hog
Version: 4.9.1   
Target Milestone: ---   
Host: Target: x86_64-*-*
Build: Known to work:
Known to fail: Last reconfirmed: 2014-09-23 00:00:00
Bug Depends on:    
Bug Blocks: 47344    
Attachments: Preprocessed source code

Description Steven Stewart-Gallus 2014-09-23 01:12:03 UTC
Compiling a large amount of large switch cases takes a really large
amount of time. In the attached code I did two things which caused and
justify the large amounts of large switch cases. First, I emulated
computed gotos in a portable way by using a macro that expands to a
switch case that jumps to a label and second I optimized dispatching
of return value registers for an intepreter by folding the return
value register selection into the instruction dispatching. The
original source is at
https://gitorious.org/uvm/uvm/source/9c8afcef3b3e87a81ff0b948fc9525cf8ec82e77:src/vm/module.c
and the preprocessed file is attached here.

I think that this specific case might be optimizable to be
accomplished in a reasonable amount of time so I thought I might as
well ask but if compiling this case is too difficult that's fine then.

Thank you,
Steven Stewart-Gallus
Comment 1 Steven Stewart-Gallus 2014-09-23 01:14:28 UTC
Created attachment 33535 [details]
Preprocessed source code
Comment 2 Andrew Pinski 2014-09-23 01:23:00 UTC
What version of GCC and on which target?
Comment 3 Richard Biener 2014-09-23 08:26:41 UTC
And what compiler options?  With -O1 on x86_64-linux it takes around 1m30s to compile with GCC 4.8 with the biggest offenders being

 alias stmt walking      :  64.95 (70%) usr   0.15 (12%) sys  65.11 (69%) wall       0 kB ( 0%) ggc
 tree SSA incremental    :  11.83 (13%) usr   0.18 (14%) sys  12.04 (13%) wall   47726 kB (12%) ggc
 tree copy propagation   :   4.12 ( 4%) usr   0.00 ( 0%) sys   4.13 ( 4%) wall     515 kB ( 0%) ggc
 TOTAL                 :  92.99             1.29            94.23             383497 kB

with GCC 4.9 this improves to

 alias stmt walking      :  55.67 (66%) usr   0.26 (18%) sys  55.95 (65%) wall       0 kB ( 0%) ggc
 tree copy propagation   :   4.90 ( 6%) usr   0.01 ( 1%) sys   4.94 ( 6%) wall     522 kB ( 0%) ggc
 tree SSA incremental    :  10.89 (13%) usr   0.20 (14%) sys  11.02 (13%) wall   47751 kB (12%) ggc
 TOTAL                 :  83.95             1.45            85.55             390402 kB

most time is spent in early local cleanups at -O1.

With -O2 GCC 4.9 takes 95s.
Comment 4 Steven Stewart-Gallus 2014-09-23 18:23:09 UTC
> What version of GCC and on which target?

Right, I should have mentioned that earlier. 

> $ uname -a
> Linux alonzo 3.13.0-34-generic #1trisquel1 SMP Sun Aug 24 04:17:04 UTC 2014 x86_64 x86_64 x86_64 GNU/Linux

> gcc --version
> gcc (GCC) 4.9.1
> Copyright (C) 2014 Free Software Foundation, Inc.
> This is free software; see the source for copying conditions.  There is NO
> warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

> With -O2 GCC 4.9 takes 95s.

That's somewhat reasonable (not the best obviously but if it's only
one source file in the entire project that's okay.)

I probably should have posted numbers earlier. For reference on my
machine:

> $ time gcc -std=gnu99 -c module.i
> 11.365 secs

> $ time gcc -std=gnu99 -O1 -c module.i
> 161.176 secs
Comment 5 Richard Biener 2014-09-24 07:53:05 UTC
Well, confirmed to some extent.  Needs to be pin-pointed to a specific pass still
(bah, those infrastructure timevars make that difficult).