[Bug ada/34400] New: [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[Bug ada/34400] New: [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[ludovic at ludovic-brenta dot org]

The thread starts here: http://gcc.gnu.org/ml/gcc/2007-11/msg00791.html

In addition, I observe the same behaviour when building a native, SJLJ version
of libgnat on x86_64.

Krister Walfridsson says: "The problem was introduced by revision 125624 (the
dataflow merge).".


-- 
           Summary: [4.3 regression] gnat1 takes too long to compile g-
                    catiio.adb with SJLJ exceptions
           Product: gcc
           Version: 4.3.0
            Status: UNCONFIRMED
          Severity: normal
          Priority: P3
         Component: ada
        AssignedTo: unassigned at gcc dot gnu dot org
        ReportedBy: ludovic at ludovic-brenta dot org


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[pinskia at gcc dot gnu dot org]

-- 

pinskia at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |zadeck at gcc dot gnu dot
                   |                            |org, pinskia at gcc dot gnu
                   |                            |dot org
          Component|ada                         |middle-end
           Keywords|                            |compile-time-hog
   Target Milestone|---                         |4.3.0


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #1 from steven at gcc dot gnu dot org  2007-12-09 09:29 -------
A test case would be nice...  Asking people to grok a email list thread and do
the research probably will not help you getting this bug fixed.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |WAITING


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #2 from zadeck at naturalbridge dot com  2007-12-09 13:25 -------
Subject: Re:  [4.3 regression] gnat1 takes too long
 to compile g-catiio.adb with SJLJ exceptions

steven at gcc dot gnu dot org wrote:
> ------- Comment #1 from steven at gcc dot gnu dot org  2007-12-09 09:29 -------
> A test case would be nice...  Asking people to grok a email list thread and do
> the research probably will not help you getting this bug fixed.
>
>
>   
I agree

kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #3 from zadeck at naturalbridge dot com  2007-12-09 13:26 -------
Subject: Re:  [4.3 regression] gnat1 takes too long
 to compile g-catiio.adb with SJLJ exceptions

steven at gcc dot gnu dot org wrote:
> ------- Comment #1 from steven at gcc dot gnu dot org  2007-12-09 09:29 -------
> A test case would be nice...  Asking people to grok a email list thread and do
> the research probably will not help you getting this bug fixed.
>
>
>   
a set of config parameters would also help for those of us who have
never played with this type of exception modeling before.


-- 


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[ludovic at ludovic-brenta dot org]

------- Comment #4 from ludovic at ludovic-brenta dot org  2007-12-09 20:48 -------
First, read http://gcc.gnu.org/ml/gcc/2006-10/msg00303.html for a
little background information on ZCX and SJLJ in Ada.

Steps to reproduce:

- bootstrap with ada enabled (i.e. ../gcc/configure
  --enable-languages=ada)

$ rm gcc/ada/rts/g-catiio.{ali,o}
$ cd gcc/ada/rts
$ time ../../gnat1 -quiet -dumpbase g-catiio.adb -O2 -W -Wall -g -gnatpg
-mtune=generic -gnatO g-catiio.o g-catiio.adb

This will show you a reference time building the ZCX version.  

In my case (2.0 Ghz AMD Turion 64):
real    0m4.238s
user    0m3.664s
sys     0m0.060s

Now, edit gcc/ada/rts/system.ads; change ZCX_By_Default from True to
False.  This switches the run-time library to SJLJ.  Then, compile
again:

$ rm gcc/ada/rts/g-catiio.{ali,o}
$ cd gcc/ada/rts
$ time ../../gnat1 -quiet -dumpbase g-catiio.adb -O2 -W -Wall -g -gnatpg
-mtune=generic -gnatO g-catiio.o g-catiio.adb

In my case:
real    275m44.310s
user    271m41.839s
sys     0m9.585s


-- 

ludovic at ludovic-brenta dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|WAITING                     |UNCONFIRMED


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[ebotcazou at gcc dot gnu dot org]

------- Comment #5 from ebotcazou at gcc dot gnu dot org  2007-12-10 07:47 -------
Confirmed, probably platform-independent.


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|UNCONFIRMED                 |NEW
     Ever Confirmed|0                           |1
   Last reconfirmed|0000-00-00 00:00:00         |2007-12-10 07:47:26
               date|                            |


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[ebotcazou at gcc dot gnu dot org]

------- Comment #6 from ebotcazou at gcc dot gnu dot org  2007-12-10 07:47 -------
Trying to find a C testcase...


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |ebotcazou at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-12-10 07:47:26         |2007-12-10 07:47:55
               date|                            |


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[ebotcazou at gcc dot gnu dot org]

------- Comment #7 from ebotcazou at gcc dot gnu dot org  2007-12-10 09:40 -------
Created an attachment (id=14716)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14716&action=view)
Reduced Ada testcase.

Compile at -O -gnatp, after copying gcc/ada/rts/system.ads to the local dir and
changing ZCX_By_Default to False in this file.


-- 


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

[Bug middle-end/34400] [4.3 regression] gnat1 takes too long to compile g-catiio.adb with SJLJ exceptions

[ebotcazou at gcc dot gnu dot org]

------- Comment #8 from ebotcazou at gcc dot gnu dot org  2007-12-10 09:42 -------
Created an attachment (id=14717)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14717&action=view)
Reduced C testcase.

Compile at -O, almost instantaneous with GCC 4.2.x.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[ebotcazou at gcc dot gnu dot org]

------- Comment #9 from ebotcazou at gcc dot gnu dot org  2007-12-10 09:46 -------
It's apparently a DF problem:

 df live&initialized regs:  27.83 (97%) usr   0.01 (50%) sys  28.48 (97%) wall 
   0 kB ( 0%) ggc


-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
            Summary|[4.3 regression] gnat1 takes|[4.3 regression] bad
                   |too long to compile g-      |interaction between DF and
                   |catiio.adb with SJLJ        |SJLJ exceptions
                   |exceptions                  |


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[ebotcazou at gcc dot gnu dot org]

-- 

ebotcazou at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|ebotcazou at gcc dot gnu dot|unassigned at gcc dot gnu
                   |org                         |dot org
             Status|ASSIGNED                    |NEW


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #10 from steven at gcc dot gnu dot org  2007-12-10 12:32 -------
Thanks for the test case!

Will investigate.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|unassigned at gcc dot gnu   |steven at gcc dot gnu dot
                   |dot org                     |org
             Status|NEW                         |ASSIGNED
   Last reconfirmed|2007-12-10 07:47:55         |2007-12-10 12:32:25
               date|                            |


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #11 from zadeck at naturalbridge dot com  2007-12-10 13:02 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

steven at gcc dot gnu dot org wrote:
> ------- Comment #10 from steven at gcc dot gnu dot org  2007-12-10 12:32 -------
> Thanks for the test case!
>
> Will investigate.
>
>
>   
Thanks,

if the issue is uninitialized vars, it is my code.   however this is a
50 line pass, so there is nothing deep going on.

kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[joel at gcc dot gnu dot org]

------- Comment #12 from joel at gcc dot gnu dot org  2007-12-10 14:22 -------
I've seen this on PowerPC and SPARC now, so I can confirm it is target
independent.


-- 

joel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |joel at gcc dot gnu dot org,
                   |                            |joel dot sherrill at oarcorp
                   |                            |dot com


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #13 from steven at gcc dot gnu dot org  2007-12-10 18:40 -------
The problem seems to be that we just converge too slowly because the CFG is
densely connected: 566 basic blocks and 19925 edges.

Actually this is perfectly quadratic: Two basic blocks are fake (exit and
entry) so there are 564 real basic blocks.  (564 / 4)^2 = 141^2 = 19881. 
Indeed the number of edges scales with the number of MCASEs in the test case.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[ebotcazou at gcc dot gnu dot org]

------- Comment #15 from ebotcazou at gcc dot gnu dot org  2007-12-10 19:14 -------
> Actually this is perfectly quadratic: Two basic blocks are fake (exit and
> entry) so there are 564 real basic blocks.  (564 / 4)^2 = 141^2 = 19881. 
> Indeed the number of edges scales with the number of MCASEs in the test case.

Yes, this is a known problem of the Ada SJLJ scheme, it's too "unstructured".


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #14 from zadeck at naturalbridge dot com  2007-12-10 19:13 -------
[13:51] <stevenb>       you wont believe this
[13:51] <zadeck>        yes ????
[13:51] <stevenb>       but that SJLJ thing, that's almost entirely call
overhead
[13:52] <spark> stevenb: calling what ?
[13:52] <stevenb>       the calls to df_live_{confluence_n,tranfer_function}
[13:52] <spark> we need c++ functor :(
[13:52] <stevenb>       yup
[13:53] <zadeck>        the thing that i do not understand is how/why it shows
up most uninitialized regs or am i reading comment #9 wrong
[13:53] <stevenb>       no, that is true
[13:53] <stevenb>       it seems this LIVE problem has more issues with a
densely connected CFG than RU and LR
[13:54] <stevenb>       it really is the LIVE problem only.
[13:55] <stevenb>       i'm not sure i understand why...
[13:55] <stevenb>       (actually I am sure I don't understand why ;))
[13:55] <spark> LR is fine but LIVE is not ?
[13:55] <stevenb>       yes
[13:57] <zadeck>        remember that live is one of the few forwards problems.
it could be that your (sparks) ordering of the blocks is wierd for forwards
problems
[13:57] <zadeck>        s/wierd/bad/
[13:57] <stevenb>       yeah, that crossed my mind too
[13:58] <spark> could be.
[13:58] <zadeck>        i see a reassignment in pr3400's future
[13:58] <stevenb>       or we may be passing it the wrong order
[13:58] <zadeck>        you could easily get n**2 behavior in either case.
[13:59] <stevenb>       what was it again, forward problems need pre-order??
[14:00] <spark> both reverse post order. but one is with inverted graph.
[14:00] <stevenb>       right
[14:00] <stevenb>       i always have to look this up :)
[14:01] <spark> actually there's no literature on this - cause the literature
is wrong.
[14:01] <stevenb>       we pass it postorder_inverted for DF_FORWARD
[14:02] <spark> hm. i think i might know what's wrong.
[14:03] <stevenb>       pray tell
[14:03] <spark> when the graph is inverted, it could have multiple entries.
[14:04] <spark> we deal with that by some hack.
[14:04] <stevenb>       you mean fake edges
[14:04] <spark> no. without fake edges.
[14:04] <stevenb>       uh...
[14:04] <spark> if we add fake edges, there's no multiple entries.
[14:05] <spark> but we can't, because some passes do not want to have those
fake edges.
[14:06] <spark> i think we might not have the correct order between regions
from multiple entries in an inverted graph - i haven't thought about that, and
i should have.
[14:07] <spark> hold on. i think it shouldn't matter for the forward problem.
hm.
[14:07] <stevenb>       are you going to think about it now then, and take the
bug?
[14:07] <spark> send it to me anyway :(


-- 

zadeck at naturalbridge dot com changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
         AssignedTo|steven at gcc dot gnu dot   |spark at gcc dot gnu dot org
                   |org                         |


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #16 from steven at gcc dot gnu dot org  2007-12-10 22:08 -------
The problem is similar to bug 17340.
And so is my proposed fix.

I've sent out a hack for testing to a few people.  We'll get back to this one
asap.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #17 from zadeck at naturalbridge dot com  2007-12-11 13:30 -------
Created an attachment (id=14729)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14729&action=view)
fixup of stevens hack

This hack cuts the -O compile time for the c testcase from 35 to 2 seconds.
my guess is that we will need a similar hack for the rd problem to get better.

interestingly the c test compiles in 4 seconds at -O2 both with and without
this patch. I assume that the tree level is cleaning things up.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #18 from zadeck at naturalbridge dot com  2007-12-11 13:55 -------
The thing i forgot to say in the previous post was that i had to change stevens
patch because the way that it was written causes df verify errors.  You cannot
make the gen set in a block dependent on the output of lr because there is no
way to track the dependencies without saying that each block for Live depends
on every block for LR.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[ludovic at ludovic-brenta dot org]

------- Comment #19 from ludovic at ludovic-brenta dot org  2007-12-11 20:36 -------
With the patch from comment #17, the compile time is down to
real    130m10.559s
user    130m9.104s
sys     0m0.388s

on my machine.  You seem to be on the right track :)


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[joel at gcc dot gnu dot org]

------- Comment #20 from joel at gcc dot gnu dot org  2007-12-14 19:41 -------
I left a build running all night and got ACATS results on the trunk on
powerpc-rtems, I get a lot of failures which appear to be constraint or
exception related.  I don't know if these are related or not. 


,.,. C34003C ACATS 2.5 88-01-01 00:00:00
---- C34003C CHECK THAT ALL VALUES OF THE PARENT (BASE) TYPE ARE PRESENT
               FOR THE DERIVED (BASE) TYPE WHEN THE DERIVED TYPE
               DEFINITION IS CONSTRAINED.  ALSO CHECK THAT ANY
               CONSTRAINT IMPOSED ON THE PARENT SUBTYPE IS ALSO IMPOSED
               ON THE DERIVED SUBTYPE.  CHECK FOR DERIVED FLOATING
               POINT TYPES.

raised CONSTRAINT_ERROR : c34003c.adb:104 range check failed


,.,. CXG2013 ACATS 2.5 88-01-01 00:00:00
---- CXG2013 Check the accuracy of the TAN and COT functions.

raised ADA.NUMERICS.ARGUMENT_ERROR : a-ngelfu.adb:969 instantiated at
cxg2013.adb:100 instantiated at cxg2013.adb:337

,.,. CXF3A03 ACATS 2.5 88-01-01 00:00:00
---- CXF3A03 Check that function Length returns the number of characters
               in the edited output string produced by function Image,         
      for a particular decimal type, currency string, and
               radix mark.  Check that function Valid returns correct
               results based on the particular decimal value, and the
               Picture and Currency string parameters.

raised ADA.IO_EXCEPTIONS.LAYOUT_ERROR : a-teioed.adb:300


,.,. CXF2001 ACATS 2.5 88-01-01 00:00:00
---- CXF2001 Check that the Divide procedure provides correct results.
               Check that the Remainder is calculated exactly.

raised CONSTRAINT_ERROR : a-decima.adb:59 divide by zero 


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #21 from zadeck at naturalbridge dot com  2007-12-14 19:55 -------
I am confused about comment #20.  Are these constraint failures caused by the
proposed patch? are they independent of the patch? why is this related to the
performance issues in doing SJLJ analysis? 


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[joel at gcc dot gnu dot org]

------- Comment #22 from joel at gcc dot gnu dot org  2007-12-14 20:00 -------
(In reply to comment #21)
> I am confused about comment #20.  Are these constraint failures caused by the
> proposed patch? are they independent of the patch? why is this related to the
> performance issues in doing SJLJ analysis? 

I do not have the proposed patch applied.  I only mentioned this because in
addition to the performance issue, there may also be a correctness issue.  If
you think it is unrelated, I will file a separate PR.  


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #23 from zadeck at naturalbridge dot com  2007-12-14 20:07 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

joel at gcc dot gnu dot org wrote:
> ------- Comment #22 from joel at gcc dot gnu dot org  2007-12-14 20:00 -------
> (In reply to comment #21)
>   
>> I am confused about comment #20.  Are these constraint failures caused by the
>> proposed patch? are they independent of the patch? why is this related to the
>> performance issues in doing SJLJ analysis? 
>>     
>
> I do not have the proposed patch applied.  I only mentioned this because in
> addition to the performance issue, there may also be a correctness issue.  If
> you think it is unrelated, I will file a separate PR.  
>
>
>   
I see no reason to believe that the two are related.  I think that the
current pr is a combination of four factors:
1) Each step of our analysis is a little more expensive than flow was. 

2) We also always solve the forwards problem and the predataflow merge
only did this for register allocation.

3) We may have some issues in ordering the nodes that we process.

4) We do not give up until the solution is found. 

It is possible that there is some interaction with the fact that we are
solving the intersection of forwards live and backwards live rather than
just relying on backwards live.  But even if that is the issue, it
should be treated as a separate problem.

Kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #24 from steven at gcc dot gnu dot org  2007-12-14 23:29 -------
Created an attachment (id=14759)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14759&action=view)
Eric's new test case


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #25 from steven at gcc dot gnu dot org  2007-12-15 00:29 -------
Created an attachment (id=14760)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14760&action=view)
hybrid search, resurrected

This new test case looks even worse for the typical work list algorithm, so I
had the idea to try the hybrid search algorithm again.  Seongbae resurrected it
and I have tried it on the new test case.  We still have large call overhead,
but it does cut time down even further.

Integrating it properly requires finding a heuristic to decide which solver to
use, depending on properties of the CFG.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #26 from steven at gcc dot gnu dot org  2007-12-16 01:50 -------
For Eric's second test case, pr24400-2.c, I have on cygwin in tree-ssa 1006
basic blocks, 2044 edges and "only" 840 DFS back edges.  After expanding to RTL
we have 1046 basic blocks, 78005 edges, and 38760 DFS back edges.

In terms of Muchnick's text on worklist dataflow solvers (section 8.4, p. 233
in my copy) we have A >> |N|, where A is the number of back edges on any
acyclic path in the flow graph.  The test case has no cyclic paths, so A is
38760 and the expected number of passes in an iterative solver is A + 2 = 38760
if the blocks are presented in reverse post order.

Measurements show that for the LR problem df_worklist_dataflow needs 39902
iterations to converge, and for the LIVE problem it also needs 39902 iterations
without df_hack2.diff, and 11442 with that patch applied.  I counted the number
of iterations in the "while (!bitmap_empty_p (pending))" loop.

My conclusion must be that df_worklist_dataflow really doesn't behave
unreasonably for the test case.

df_iterative_dataflow needs at most 5 iterations, counting the number of times
we loop in the "while (1)" main loop.  That is, 5 times visiting all basic
blocks, so in total 5*1046=5230 basic block visits.  Optimistically assuming
one block visted per iteration in df_worklist_dataflow, 39902 basic block
visits.


What are the reasons for not just *always* using the hybrid search solver?  The
comment before df_worklist_dataflow says that "measurements shows worklist
algorithm beats iterative algorithm by some margin overall".  Which
measurements are this?  And which iterative algorithm, i.e. the classic
iterative algorithm or the hybrid search??


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #27 from steven at gcc dot gnu dot org  2007-12-16 01:54 -------
Typos.  Wanted to say:

"The test case has no cyclic paths, so A is
38760 and the optimal number of passes in a worklist solver is A + 2 = 38762
if the blocks are presented in reverse post order."


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #28 from steven at gcc dot gnu dot org  2007-12-16 12:01 -------
Created an attachment (id=14778)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14778&action=view)
Change worklist solver to double queue algorithm

I re-read Cooper, Harvey and Kennedy, who wrote a nice paper about various work
list based dataflow solvers.

The attached patch modifies df_worklist_dataflow to a double queue algorithm,
while retaining the property that basic blocks are added to the queue in RPO
order.  This approach gives me a speedup comparable to (but slightly less than)
the hybrid search algorithm.  This is not really surprising because the double
queue work list algorithm also completes full iterations over the CFG before
considering the second queue.

Seongbae, what are your ideas about the double queue approach (or maybe other
algorithms suggested by Harvey)?


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #29 from zadeck at naturalbridge dot com  2007-12-16 13:56 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

steven at gcc dot gnu dot org wrote:
> ------- Comment #28 from steven at gcc dot gnu dot org  2007-12-16 12:01 -------
> Created an attachment (id=14778)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14778&action=view)
>  --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14778&action=view)
> Change worklist solver to double queue algorithm
>
> I re-read Cooper, Harvey and Kennedy, who wrote a nice paper about various work
> list based dataflow solvers.
>
> The attached patch modifies df_worklist_dataflow to a double queue algorithm,
> while retaining the property that basic blocks are added to the queue in RPO
> order.  This approach gives me a speedup comparable to (but slightly less than)
> the hybrid search algorithm.  This is not really surprising because the double
> queue work list algorithm also completes full iterations over the CFG before
> considering the second queue.
>
> Seongbae, what are your ideas about the double queue approach (or maybe other
> algorithms suggested by Harvey)?
>
>
>   
The bottom line here is that all of these are heuristics.  There are no
tight time bounds here.  Each of these will have good cases and each
will have bad case.  So the only way that anyone can talk about best is
in term of the set of graphs they used to measure output.

Seongbae chose a technique that tends to work very well if the programs
are "normal" and the expense that fully connected programs are quite
bad.  The class of techniques that were used in hybrid search and that
you are looking at tend to do better for bad graphs but will be a little
slower on the "normal" cases.

If you can come up with some fast heuristic test to distinguish the
difference cases you can select between them.  Of course you only have
to do the tests once per function because the chances that optimization
will change the heuristic are vanishingly small.  This gives you a
little more room in terms of implementation cost. 

I think that I would vote for the "any bad back edges" plan to
distinguish the two because i think that Seonbae's technique was
designed to work well on that class of graphs.  But Seonbae may have
other thoughts especially if his technique requires only shallow maximum
nesting to really shine. 

Kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[ludovic at ludovic-brenta dot org]

------- Comment #30 from ludovic at ludovic-brenta dot org  2007-12-17 10:52 -------
(In reply to comment #28)
> Created an attachment (id=14778)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14778&action=view) [edit]
> Change worklist solver to double queue algorithm

I would like to try this patch: does it invalidate the patch from comment #17,
or should I apply both?


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #31 from steven at gcc dot gnu dot org  2007-12-17 10:55 -------
You could apply both, but numbers for the patch of comment #28 in isolation
would also be welcome.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #32 from zadeck at naturalbridge dot com  2007-12-17 13:21 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

steven at gcc dot gnu dot org wrote:
> ------- Comment #31 from steven at gcc dot gnu dot org  2007-12-17 10:55 -------
> You could apply both, but numbers for the patch of comment #28 in isolation
> would also be welcome.
>
>
>   
Note that this is not the final patch. I assume that steven is going to
clean that up and submit it soon.  The final patch only uses this
algorithm for certain kinds of graphs.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[ludovic at ludovic-brenta dot org]

------- Comment #33 from ludovic at ludovic-brenta dot org  2007-12-17 15:35 -------
Here are the numbers; there is a spectacular improvement, but 4.3 is still an
order of magnitude slower than 4.2:

With df_hack3 alone:
real    1m5.705s
user    1m5.184s
sys     0m0.412s

With df_double_queue_worklist alone:
real    4m8.383s
user    4m6.055s
sys     0m0.636s

With df_hack3 and df_double_queue_worklist:
real    1m6.834s
user    1m6.024s
sys     0m0.376s

With df_hack2 and df_hack3:
real    0m54.194s
user    0m53.511s
sys     0m0.324s

With df_hack2, df_hack3 and df_double_queue_worklist:
real    0m54.132s
user    0m53.691s
sys     0m0.372s


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #34 from zadeck at naturalbridge dot com  2007-12-17 16:01 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

ludovic at ludovic-brenta dot org wrote:
> ------- Comment #33 from ludovic at ludovic-brenta dot org  2007-12-17 15:35 -------
> Here are the numbers; there is a spectacular improvement, but 4.3 is still an
> order of magnitude slower than 4.2:
>
> With df_hack3 alone:
> real    1m5.705s
> user    1m5.184s
> sys     0m0.412s
>
> With df_double_queue_worklist alone:
> real    4m8.383s
> user    4m6.055s
> sys     0m0.636s
>
> With df_hack3 and df_double_queue_worklist:
> real    1m6.834s
> user    1m6.024s
> sys     0m0.376s
>
> With df_hack2 and df_hack3:
> real    0m54.194s
> user    0m53.511s
> sys     0m0.324s
>
> With df_hack2, df_hack3 and df_double_queue_worklist:
> real    0m54.132s
> user    0m53.691s
> sys     0m0.372s
>
>
>   
can you send us a time report for this so we can see if we have changed
who the bad actors are?

by "this" i mean all three patches together.

kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[ludovic at ludovic-brenta dot org]

------- Comment #35 from ludovic at ludovic-brenta dot org  2007-12-17 16:16 -------
Created an attachment (id=14784)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14784&action=view)
Results of gnat1 -ftime-report [...] g-catiio.adb with SJLJ exceptions

$ time ../../gnat1 -ftime-report -dumpbase g-catiio.adb -O2 -W -Wall -g -gnatpg
-mtune=generic -gnatO g-catiio.o g-catiio.adb > /tmp/pr34400-time-report.txt
2>&1

real    0m54.039s
user    0m53.647s
sys     0m0.332s

With df_hack2, df_hack3 and df_double_queue_worklist applied.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #36 from zadeck at naturalbridge dot com  2007-12-17 16:33 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

ludovic at ludovic-brenta dot org wrote:
> ------- Comment #35 from ludovic at ludovic-brenta dot org  2007-12-17 16:16 -------
> Created an attachment (id=14784)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14784&action=view)
>  --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14784&action=view)
> Results of gnat1 -ftime-report [...] g-catiio.adb with SJLJ exceptions
>
> $ time ../../gnat1 -ftime-report -dumpbase g-catiio.adb -O2 -W -Wall -g -gnatpg
> -mtune=generic -gnatO g-catiio.o g-catiio.adb > /tmp/pr34400-time-report.txt
> 2>&1
>
> real    0m54.039s
> user    0m53.647s
> sys     0m0.332s
>
> With df_hack2, df_hack3 and df_double_queue_worklist applied.
>
>
>   
I am looking at this time report and i do not see anything thing that
looks like df is taking an inordinate amount of time.  i could be
missing something. 

but it looks like there are a lot of passes that are eating big chunks
of time here.  At this point halving the amount of time that df takes is
going to give you a few percent. 

Kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[stevenb dot gcc at gmail dot com]

------- Comment #37 from stevenb dot gcc at gmail dot com  2007-12-17 16:55 -------
Subject: Re:  [4.3 regression] bad interaction between DF and SJLJ exceptions

Compiling with checking disabled might give a less unfair comparison.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #38 from steven at gcc dot gnu dot org  2007-12-17 19:33 -------
Applying df_hack3 and df_double_queue_worklist is pointless for your test cae. 
With df_hack3 the worklist algorithm never runs.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[bonzini at gnu dot org]

------- Comment #39 from bonzini at gnu dot org  2007-12-19 13:57 -------
Yes, we need a no-checking comparison.  And this might be a PR of its own, for
example:

 tree PRE              :   7.94 (15%) usr   0.10 (32%) sys   8.04 (15%) wall   
1687 kB ( 2%) ggc


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #40 from steven at gcc dot gnu dot org  2007-12-19 22:49 -------
The issue with tree PRE is probably the quadratic behavior of insert().  Easily
tested by lowering the maximum number of basic blocks from 4000 to 2000 (even
though that's obviously not an actual fix for this problem).


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #41 from steven at gcc dot gnu dot org  2007-12-19 23:57 -------
Patches attached to this bug report address more general issues, namely:

1. The LIVE problem allocates too many bitmaps (xf. df_hack2.diff)
2. Large and very connected CFGs are a time problem

Bug 26854 is another example of bad DF behavior, without SJLJ exceptions.  I'm
making this bug depend on bug 26854 because bug 26854 shows there is more work
to do than just fixing the above mentioned two issues.

I suspect other problems than LIVE also allocate too many bitmaps.  We badly
need a mechanism to track memory usage of DF.


-- 

steven at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
  BugsThisDependsOn|                            |26854


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #42 from zadeck at naturalbridge dot com  2007-12-20 01:56 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

steven at gcc dot gnu dot org wrote:
> ------- Comment #41 from steven at gcc dot gnu dot org  2007-12-19 23:57 -------
> Patches attached to this bug report address more general issues, namely:
>
> 1. The LIVE problem allocates too many bitmaps (xf. df_hack2.diff)
> 2. Large and very connected CFGs are a time problem
>
> Bug 26854 is another example of bad DF behavior, without SJLJ exceptions.  I'm
> making this bug depend on bug 26854 because bug 26854 shows there is more work
> to do than just fixing the above mentioned two issues.
>
> I suspect other problems than LIVE also allocate too many bitmaps.  We badly
> need a mechanism to track memory usage of DF.
>
>
>   
The df_hack2.diff actually allocates 1 more bitmap than without it.  the
space difference comes from the fact that a large number of the bitmaps
have fewer bits.  Remember that the implementation of bitmaps allocates
a block of memory for each 64 bit unit that contains some ones, so there
is a price paid in time and space for having more 1's in your maps.

the implementation of df actually uses 2 different memory allocation
frameworks.  The local data structures are based on alloc_pools and i do
not think that it would be hard to add a little code to this say how
many pools had been allocated.  However the bitmaps use obstacks which
are a completely different beast.   It would probably be best to just
convert bitmaps to use alloc pools since these seem to be better than
obstacks, but either way makes the accounting of space complex. 

I can work on the an addition to df_hack2.diff that does the same thing
for the reaching defs problem.  It will be a more tricky patch, but the
space gains may be even more significant because there are a lot more 1
bits flying thru the air in this problem.  As far as the time, doing
this will not make that much difference unless you are at -O2 or higher
since this is rarely (if at all) used at -O1.

Kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[stevenb dot gcc at gmail dot com]

------- Comment #43 from stevenb dot gcc at gmail dot com  2007-12-20 06:15 -------
Subject: Re:  [4.3 regression] bad interaction between DF and SJLJ exceptions

I did not mean more bitmaps but more elements per bitmap, obviously.
I know the effect of the patch, or I wouldn't have written it  ;-)

I tried to add something like df_hack2 to the reaching defs problem,
but I didn't succeed the first time.  It is indeed harder.  If you
could work in it, that would be terrific.

I will work on some tools to investigate DF memory usage.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[mmitchel at gcc dot gnu dot org]

------- Comment #44 from mmitchel at gcc dot gnu dot org  2008-01-02 23:12 -------
I've marked this as P2 because it seems to depend on the less-used SJLJ EH
method, and, as I understand it, in Ada.  (The comments above suggest that the
C testcase is not actually so problematic.)


-- 

mmitchel at gcc dot gnu dot org changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Priority|P3                          |P2


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #45 from zadeck at naturalbridge dot com  2008-01-02 23:17 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

mmitchel at gcc dot gnu dot org wrote:
> ------- Comment #44 from mmitchel at gcc dot gnu dot org  2008-01-02 23:12 -------
> I've marked this as P2 because it seems to depend on the less-used SJLJ EH
> method, and, as I understand it, in Ada.  (The comments above suggest that the
> C testcase is not actually so problematic.)
>
>
>   
I think that we have some patches in the air that are going to make a
lot of progress with this.
we will most likely fail to get it to pre dataflow levels.  We should be
able to get these in by the end of next week.  I do not know how this
effects your plans to close stage 3.

Kenny


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[bonzini at gnu dot org]

------- Comment #46 from bonzini at gnu dot org  2008-01-04 11:01 -------
on a non-checking compiler:

4.1                                1.8s

on a checking compiler:

unpatched                          21s
hybrid search, no pruning          3.6s
hybrid search, LIVE pruning        3.5s
hybrid search, LIVE+RD pruning     3.4s
dq search, no pruning              3.5s
dq search, LIVE pruning            3.5s
dq search, LIVE+RD pruning         3.5s

LIVE pruning is df_hack2.diff.
RD pruning is Kenny's latest patch which I'll attach soon.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[bonzini at gnu dot org]

------- Comment #47 from bonzini at gnu dot org  2008-01-04 11:11 -------
Created an attachment (id=14874)
 --> (http://gcc.gnu.org/bugzilla/attachment.cgi?id=14874&action=view)
kenny's trimmed rd patch


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #48 from zadeck at naturalbridge dot com  2008-01-10 18:44 -------
Subject: Re:  

I do not want to commit this patch until after seongbae gets the new
node visiting sorted out.
This patch does for the rd problem what
http://gcc.gnu.org/bugzilla/attachment.cgi?id=14729
does for the live problem.  The gains on the test cases are less dramatic.

There has also been a small amount of cleanup in this patch (the rename
of *local_finalize to *finalize. 

Other issues with the patch:

The patch adds a flag for the rd problem to either trim the sets with
the lr information (as we always do with the live problem) or to leave
it as it was (setting the DF_RD_NO_TRIM flag.)

The loop optimizations need this flag since they only compute the
solution over a subset of the cfg.  The problem with using a subset is
that def that occurs inside the subset whose only use occurs outside the
subset will look dead if you trim the sets with the lr infomation.  This
causes the rtl loop passes, which are the only passes to still compute
dataflow over a subset of the function, to make mistakes.   If you are
computing rd over the entire program, this flag should not be set. 

There is also code in here not to consider the invalidated_by_call sets
in the confluence function unless you are do not want the sets trimmed. 
This saves a little time.  The point is that the lr problem already
considers the invalidated_by_call sets so when you trim, you get the
result of this and it is not necessary for the forwards case.

I also added a quickout if the confluence function is called on an fake
edge (as in the live confluence function).  This is a latent bug that
does not show up because the passes that use this problem currently do
not use fake edges. 

When bootstrapping this patch is a mild win in terms of time.  The main
reason for it are the really large or badly structured programs in which
it should help (see the prs).

This patch is part of at least three patches that each make headway on
these two prs.  There is still some room for more improvement so it is
not clear that these prs should close when all of these patches are
applied. 

I have at least one more idea to attack the space in 26854, but
(assuming i even do the patch before the end of stage 3), it will be up
to Mitchell to decide if that is too much code for this late date.

i have bootstrapped and regression tested this patch on x86-64, ppc-32,
ia-64.

ok for commit after seonbae gets his patch in?

kenny

2008-01-05  Kenneth Zadeck <zadeck@naturalbridge.com>

    PR rtl-optimization/26854
    PR rtl-optimization/34400
    * ddg.c (create_ddg_dep_from_intra_loop_link): Do not use
    DF_RD->gen.
    * df.h (df_changeable_flags.DF_RD_NO_TRIM): New.
    (df_rd_bb_info.expanded_lr_out): New.
    * loop_invariant.c (find_defs): Added DF_RD_NO_TRIM flag.
    * loop_iv.c (iv_analysis_loop_init): Ditto.
    * df-problems.c (df_rd_free_bb_info, df_rd_alloc, df_rd_confluence_n,
    df_rd_bb_local_compute, df_rd_transfer_function, df_rd_free):
    Added code to allocate, initialize or free expanded_lr_out.
    (df_rd_bb_local_compute_process_def): Restructured to make
    more understandable.
    (df_rd_confluence_n): Add code to do nothing with fake edges and
    code to no apply invalidate_by_call sets if the sets are being trimmed.
    (df_lr_local_finalize): Renamed to df_lr_finalize.
    (df_live_local_finalize): Renamed to df_live_finalize.


Index: ddg.c
===================================================================
--- ddg.c       (revision 131439)
+++ ddg.c       (working copy)
@@ -184,12 +184,13 @@ create_ddg_dep_from_intra_loop_link (ddg
         {
           int regno = REGNO (SET_DEST (set));
           struct df_ref *first_def;
-          struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (g->bb);
+          struct df_ref *last_def;

           first_def = df_bb_regno_first_def_find (g->bb, regno);
           gcc_assert (first_def);

-          if (bitmap_bit_p (bb_info->gen, first_def->id))
+          last_def = df_bb_regno_last_def_find (g->bb, regno);
+          if (first_def == last_def)
             return;
         }
     }
Index: df.h
===================================================================
--- df.h        (revision 131439)
+++ df.h        (working copy)
@@ -402,22 +402,30 @@ enum df_changeable_flags 
 {
   /* Scanning flags.  */
   /* Flag to control the running of dce as a side effect of building LR.  */
-  DF_LR_RUN_DCE           =  1, /* Run DCE.  */
-  DF_NO_HARD_REGS         =  2, /* Skip hard registers in RD and CHAIN
Building.  */
-  DF_EQ_NOTES             =  4, /* Build chains with uses present in
EQUIV/EQUAL notes. */
-  DF_NO_REGS_EVER_LIVE    =  8, /* Do not compute the regs_ever_live.  */
+  DF_LR_RUN_DCE           = 1 << 0, /* Run DCE.  */
+  DF_NO_HARD_REGS         = 1 << 1, /* Skip hard registers in RD and CHAIN
Building.  */
+
+  /* Do not trim the solution using the LR result.  This can make the
+     solution take much longer and take more memory.  This is
+     necessary for the loop optimizations, but has a very small time
+     and space penalty because the loop optimizations process only a
+     single loop at a time.  Any pass that looks at the entire
+     function should not set this flag.  */
+  DF_RD_NO_TRIM           = 1 << 2,
+  DF_EQ_NOTES             = 1 << 3, /* Build chains with uses present in
EQUIV/EQUAL notes. */
+  DF_NO_REGS_EVER_LIVE    = 1 << 4, /* Do not compute the regs_ever_live.  */

   /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
   return immediately.  This is used by passes that know how to update
   the scanning them selves.  */
-  DF_NO_INSN_RESCAN       = 16,
+  DF_NO_INSN_RESCAN       = 1 << 5,

   /* Cause df_insn_rescan df_notes_rescan and df_insn_delete, to
   return after marking the insn for later processing.  This allows all
   rescans to be batched.  */
-  DF_DEFER_INSN_RESCAN    = 32,
+  DF_DEFER_INSN_RESCAN    = 1 << 6,

-  DF_VERIFY_SCHEDULED     = 64
+  DF_VERIFY_SCHEDULED     = 1 << 7
 };

 /* Two of these structures are inline in df, one for the uses and one
@@ -705,16 +713,43 @@ struct df_scan_bb_info


 /* Reaching definitions.  All bitmaps are indexed by the id field of
-   the ref except sparse_kill (see above).  */
+   the ref except sparse_kill which is indexed by regno.  */
 struct df_rd_bb_info 
 {
-  /* Local sets to describe the basic blocks.  See the note in the RU
-     datastructures for kill and sparse_kill.  */
+  /* Local sets to describe the basic blocks.   */
   bitmap kill;  
   bitmap sparse_kill;
-  bitmap gen;   /* The set of defs generated in this block.  */

-  /* The results of the dataflow problem.  */
+  /* Expanded version of the DF_LT->out bitmap to match the positions
+     of gen, in and out here.  Only allocated if DF_RD_NO_TRIM is
+     false.  */
+  bitmap expanded_lr_out;
+
+  /* The set of defs generated in this block.  This is not set unless
+     the def reaches the end of the block.  */
+  bitmap gen;
+
+  /* The results of the dataflow problem.  
+
+     If DF_RD_NO_TRIM is not set, these sets are SOMEWHAT trimmed by
+     the output of the DF_LR problem.  The out set is precisely
+     trimmed during propagation which means that the result is also
+     trimmed when the propagation terminates.  The in set is not
+     explicitly trimmed, because this is expensive (adding about 5% to
+     the cost of a bootstrap).  However since the out sets are trimmed
+     and the in sets are built from the out of the pred, the in set is
+     MOSTLY trimmed.
+
+     The counter case happens at a branch where the variable V is in
+     DF_LR->in the true branch but not the false branch.  If V is
+     defined before the branch, RD will propagate that into the
+     DF_RD_in sets of both branches.  When the block is processed, the
+     DF_RD->out set will have V trimmed out of it but it will still be
+     left in DF_RD->in.  
+
+     If this not a problem for the current optimizers since they were
+     designed before any trimming was available.  This can be fixed by
+     checking the DF_LR->in set directly.  */
   bitmap in;    /* At the top of the block.  */
   bitmap out;   /* At the bottom of the block.  */
 };
Index: loop-invariant.c
===================================================================
--- loop-invariant.c    (revision 131439)
+++ loop-invariant.c    (working copy)
@@ -639,6 +639,7 @@ find_defs (struct loop *loop, basic_bloc
   df_remove_problem (df_chain);
   df_process_deferred_rescans ();
   df_chain_add_problem (DF_UD_CHAIN);
+  df_set_flags (DF_RD_NO_TRIM);
   df_set_blocks (blocks);
   df_analyze ();

Index: loop-iv.c
===================================================================
--- loop-iv.c   (revision 131439)
+++ loop-iv.c   (working copy)
@@ -22,9 +22,10 @@ along with GCC; see the file COPYING3.  
    doloop optimization and branch prediction.  The iv information is computed
    on demand.

-   Induction variable is analyzed by walking the use-def chains.  When a biv
-   is found, it is cached in the bivs hash table.  When register is proved
-   to be a giv, its description is stored to DF_REF_DATA of the def reference.
+   Induction variables are analyzed by walking the use-def chains.  When
+   a basic induction variable (biv) is found, it is cached in the bivs
+   hash table.  When register is proved to be a biv, its description
+   is stored to DF_REF_DATA of the def reference.

    The analysis works always with one loop -- you must call
    iv_analysis_loop_init (loop) for it.  All the other functions then work
with
@@ -277,6 +278,7 @@ iv_analysis_loop_init (struct loop *loop
   df_remove_problem (df_chain);
   df_process_deferred_rescans ();
   df_chain_add_problem (DF_UD_CHAIN);
+  df_set_flags (DF_RD_NO_TRIM);
   df_set_blocks (blocks);
   df_analyze ();
   if (dump_file)
Index: df-problems.c
===================================================================
--- df-problems.c       (revision 131439)
+++ df-problems.c       (working copy)
@@ -245,6 +245,8 @@ df_rd_free_bb_info (basic_block bb ATTRI
   struct df_rd_bb_info *bb_info = (struct df_rd_bb_info *) vbb_info;
   if (bb_info)
     {
+      if (bb_info->expanded_lr_out)
+       BITMAP_FREE (bb_info->expanded_lr_out);
       BITMAP_FREE (bb_info->kill);
       BITMAP_FREE (bb_info->sparse_kill);
       BITMAP_FREE (bb_info->gen);
@@ -298,6 +300,8 @@ df_rd_alloc (bitmap all_blocks)
       struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
       if (bb_info)
        { 
+         if (bb_info->expanded_lr_out)
+           bitmap_clear (bb_info->expanded_lr_out);
          bitmap_clear (bb_info->kill);
          bitmap_clear (bb_info->sparse_kill);
          bitmap_clear (bb_info->gen);
@@ -306,6 +310,10 @@ df_rd_alloc (bitmap all_blocks)
        { 
          bb_info = (struct df_rd_bb_info *) pool_alloc (df_rd->block_pool);
          df_rd_set_bb_info (bb_index, bb_info);
+         if (df->changeable_flags & DF_RD_NO_TRIM)
+           bb_info->expanded_lr_out = NULL;
+         else
+           bb_info->expanded_lr_out = BITMAP_ALLOC
(&problem_data->rd_bitmaps);
          bb_info->kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
          bb_info->sparse_kill = BITMAP_ALLOC (&problem_data->rd_bitmaps);
          bb_info->gen = BITMAP_ALLOC (&problem_data->rd_bitmaps);
@@ -320,56 +328,53 @@ df_rd_alloc (bitmap all_blocks)
 /* Process a list of DEFs for df_rd_bb_local_compute.  */

 static void
-df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info, 
+df_rd_bb_local_compute_process_def (struct df_rd_bb_info *bb_info,
                                    struct df_ref **def_rec,
                                    enum df_ref_flags top_flag)
 {
-  while (*def_rec)
+  for (; *def_rec; def_rec++)
     {
       struct df_ref *def = *def_rec;
-      if (top_flag == (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+      unsigned int regno = DF_REF_REGNO (def);
+
+      /* This makes sure we do the artificial defs in the right order
+        since they are all in the same list.  */
+      if (top_flag != (DF_REF_FLAGS (def) & DF_REF_AT_TOP))
+       continue;
+
+      /* Skip over the hard regs if we do not care about them.  */
+      if ((df->changeable_flags & DF_NO_HARD_REGS) && 
+         (regno < FIRST_PSEUDO_REGISTER))
+       continue;
+
+      /* Only the last def(s) for a regno in the block has any
+        effect.  */ 
+      if (bitmap_bit_p (seen_in_block, regno))
+       continue;
+
+      /* The first def for regno in insn gets to knock out the
+        defs from other instructions.  */
+      if ((!bitmap_bit_p (seen_in_insn, regno))
+         /* If the def is to only part of the reg, it does
+            not kill the other defs that reach here.  */
+         && (!(DF_REF_FLAGS (def) & 
+               (DF_REF_PARTIAL | DF_REF_CONDITIONAL | DF_REF_MAY_CLOBBER))))
        {
-         unsigned int regno = DF_REF_REGNO (def);
          unsigned int begin = DF_DEFS_BEGIN (regno);
          unsigned int n_defs = DF_DEFS_COUNT (regno);
-         
-         if ((!(df->changeable_flags & DF_NO_HARD_REGS))
-             || (regno >= FIRST_PSEUDO_REGISTER))
-           {
-             /* Only the last def(s) for a regno in the block has any
-                effect.  */ 
-             if (!bitmap_bit_p (seen_in_block, regno))
-               {
-                 /* The first def for regno in insn gets to knock out the
-                    defs from other instructions.  */
-                 if ((!bitmap_bit_p (seen_in_insn, regno))
-                     /* If the def is to only part of the reg, it does
-                        not kill the other defs that reach here.  */
-                     && (!(DF_REF_FLAGS (def) & 
-                           (DF_REF_PARTIAL | DF_REF_CONDITIONAL |
DF_REF_MAY_CLOBBER))))
-                   {
-                     if (n_defs > DF_SPARSE_THRESHOLD)
-                       {
-                         bitmap_set_bit (bb_info->sparse_kill, regno);
-                         bitmap_clear_range(bb_info->gen, begin, n_defs);
-                       }
-                     else
-                       {
-                         bitmap_set_range (bb_info->kill, begin, n_defs);
-                         bitmap_clear_range (bb_info->gen, begin, n_defs);
-                       }
-                   }
-                 
-                 bitmap_set_bit (seen_in_insn, regno);
-                 /* All defs for regno in the instruction may be put into
-                    the gen set.  */
-                 if (!(DF_REF_FLAGS (def) 
-                       & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
-                   bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
-               }
-           }
+         if (n_defs > DF_SPARSE_THRESHOLD)
+           bitmap_set_bit (bb_info->sparse_kill, regno);
+         else
+           bitmap_set_range (bb_info->kill, begin, n_defs);
+         bitmap_clear_range(bb_info->gen, begin, n_defs);
        }
-      def_rec++;
+      
+      bitmap_set_bit (seen_in_insn, regno);
+      /* All defs for regno in the instruction may be put into
+        the gen set.  */
+      if (!(DF_REF_FLAGS (def) 
+           & (DF_REF_MUST_CLOBBER | DF_REF_MAY_CLOBBER)))
+       bitmap_set_bit (bb_info->gen, DF_REF_ID (def));
     }
 }

@@ -380,14 +385,28 @@ df_rd_bb_local_compute (unsigned int bb_
 {
   basic_block bb = BASIC_BLOCK (bb_index);
   struct df_rd_bb_info *bb_info = df_rd_get_bb_info (bb_index);
+  struct df_lr_bb_info *lr_bb_info = df_lr_get_bb_info (bb_index);
   rtx insn;

   bitmap_clear (seen_in_block);
   bitmap_clear (seen_in_insn);

+  if (!(df->changeable_flags & DF_RD_NO_TRIM))
+    {
+      unsigned int regno;
+      bitmap_iterator bi;
+      int first_reg = (df->changeable_flags & DF_NO_HARD_REGS) ?
FIRST_PSEUDO_REGISTER : 0;
+      EXECUTE_IF_SET_IN_BITMAP (lr_bb_info->out, first_reg, regno, bi)
+       {
+         unsigned int begin = DF_DEFS_BEGIN (regno);
+         unsigned int n_defs = DF_DEFS_COUNT (regno);
+         bitmap_set_range (bb_info->expanded_lr_out, begin, n_defs);
+       }
+    }
+
   /* Artificials are only hard regs.  */
   if (!(df->changeable_flags & DF_NO_HARD_REGS))
-    df_rd_bb_local_compute_process_def (bb_info, 
+    df_rd_bb_local_compute_process_def (bb_info,
                                        df_get_artificial_defs (bb_index),
                                        0);

@@ -398,7 +417,7 @@ df_rd_bb_local_compute (unsigned int bb_
       if (!INSN_P (insn))
        continue;

-      df_rd_bb_local_compute_process_def (bb_info, 
+      df_rd_bb_local_compute_process_def (bb_info,
                                          DF_INSN_UID_DEFS (uid), 0);

       /* This complex dance with the two bitmaps is required because
@@ -415,7 +434,7 @@ df_rd_bb_local_compute (unsigned int bb_
      are going backwards through the block and these are logically at
      the start.  */
   if (!(df->changeable_flags & DF_NO_HARD_REGS))
-    df_rd_bb_local_compute_process_def (bb_info, 
+    df_rd_bb_local_compute_process_def (bb_info,
                                        df_get_artificial_defs (bb_index),
                                        DF_REF_AT_TOP);
 }
@@ -482,7 +501,13 @@ df_rd_confluence_n (edge e)
   bitmap op1 = df_rd_get_bb_info (e->dest->index)->in;
   bitmap op2 = df_rd_get_bb_info (e->src->index)->out;

-  if (e->flags & EDGE_EH)
+  if (e->flags & EDGE_FAKE) 
+    return;
+
+  /* If we are trimming the solution, the invalidated_by_call code in
+     the lr problem makes this unnecessary.  However, if we do not
+     trim, we must take this into account.  */
+  if ((df->changeable_flags & DF_RD_NO_TRIM) && e->flags & EDGE_EH)
     {
       struct df_rd_problem_data *problem_data
        = (struct df_rd_problem_data *) df_rd->problem_data;
@@ -490,7 +515,7 @@ df_rd_confluence_n (edge e)
       bitmap dense_invalidated = problem_data->dense_invalidated_by_call;
       bitmap_iterator bi;
       unsigned int regno;
-      bitmap tmp = BITMAP_ALLOC (&df_bitmap_obstack);
+      bitmap tmp = BITMAP_ALLOC (&problem_data->rd_bitmaps);

       bitmap_copy (tmp, op2);
       bitmap_and_compl_into (tmp, dense_invalidated);
@@ -522,13 +547,13 @@ df_rd_transfer_function (int bb_index)
   bitmap gen = bb_info->gen;
   bitmap kill = bb_info->kill;
   bitmap sparse_kill = bb_info->sparse_kill;
+  bool changed = false;

-  if (bitmap_empty_p (sparse_kill))
-    return  bitmap_ior_and_compl (out, gen, in, kill);
+  if ((df->changeable_flags & DF_RD_NO_TRIM) && bitmap_empty_p (sparse_kill))
+    changed = bitmap_ior_and_compl (out, gen, in, kill);
   else 
     {
       struct df_rd_problem_data *problem_data;
-      bool changed = false;
       bitmap tmp;

       /* Note that TMP is _not_ a temporary bitmap if we end up replacing
@@ -545,6 +570,8 @@ df_rd_transfer_function (int bb_index)
        }
       bitmap_and_compl_into (tmp, kill);
       bitmap_ior_into (tmp, gen);
+      if (!(df->changeable_flags & DF_RD_NO_TRIM))
+       bitmap_and_into (tmp, bb_info->expanded_lr_out);
       changed = !bitmap_equal_p (tmp, out);
       if (changed)
        {
@@ -552,9 +579,10 @@ df_rd_transfer_function (int bb_index)
          bb_info->out = tmp;
        }
       else 
-         BITMAP_FREE (tmp);
-      return changed;
+       BITMAP_FREE (tmp);
     }
+
+  return changed;
 }


@@ -574,6 +602,8 @@ df_rd_free (void)
          struct df_rd_bb_info *bb_info = df_rd_get_bb_info (i);
          if (bb_info)
            {
+             if (bb_info->expanded_lr_out)
+               BITMAP_FREE (bb_info->expanded_lr_out);
              BITMAP_FREE (bb_info->kill);
              BITMAP_FREE (bb_info->sparse_kill);
              BITMAP_FREE (bb_info->gen);
@@ -1015,7 +1045,7 @@ df_lr_transfer_function (int bb_index)
 /* Run the fast dce as a side effect of building LR.  */

 static void
-df_lr_local_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
+df_lr_finalize (bitmap all_blocks ATTRIBUTE_UNUSED)
 {
   if (df->changeable_flags & DF_LR_RUN_DCE)
     {
@@ -1161,7 +1191,7 @@ df_lr_verify_solution_end (void)

   if (df_lr->solutions_dirty)
     /* Do not check if the solution is still dirty.  See the comment
-       in df_lr_local_finalize for details.  */
+       in df_lr_finalize for details.  */
     df_lr->solutions_dirty = false;
   else
     FOR_ALL_BB (bb)
@@ -1204,7 +1234,7 @@ static struct df_problem problem_LR =
   df_lr_confluence_0,         /* Confluence operator 0.  */ 
   df_lr_confluence_n,         /* Confluence operator n.  */ 
   df_lr_transfer_function,    /* Transfer function.  */
-  df_lr_local_finalize,       /* Finalize function.  */
+  df_lr_finalize,             /* Finalize function.  */
   df_lr_free,                 /* Free all of the problem information.  */
   NULL,                       /* Remove this problem from the stack of
dataflow problems.  */
   NULL,                       /* Debugging.  */
@@ -1549,7 +1579,7 @@ df_live_transfer_function (int bb_index)
 /* And the LR info with the must-initialized registers, to produce the LIVE
info.  */

 static void
-df_live_local_finalize (bitmap all_blocks)
+df_live_finalize (bitmap all_blocks)
 {

   if (df_live->solutions_dirty)
@@ -1737,7 +1767,7 @@ static struct df_problem problem_LIVE =
   NULL,                         /* Confluence operator 0.  */ 
   df_live_confluence_n,         /* Confluence operator n.  */ 
   df_live_transfer_function,    /* Transfer function.  */
-  df_live_local_finalize,       /* Finalize function.  */
+  df_live_finalize,             /* Finalize function.  */
   df_live_free,                 /* Free all of the problem information.  */
   df_live_free,                 /* Remove this problem from the stack of
dataflow problems.  */
   NULL,                         /* Debugging.  */


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[spark at gcc dot gnu dot org]

------- Comment #49 from spark at gcc dot gnu dot org  2008-01-17 20:03 -------
Subject: Bug 34400

Author: spark
Date: Thu Jan 17 20:02:56 2008
New Revision: 131608

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131608
Log:
2008-01-17  Seongbae Park  <seongbae.park@gmail.com>

        PR rtl-optimization/34400
        * df-core.c (df_worklist_dataflow_overeager,
        df_worklist_dataflow_doublequeue): New functions.
        (df_worklist_dataflow): Two different worklist solvers.
        * params.def (PARAM_DF_DOUBLE_QUEUE_THRESHOLD_FACTOR):
        New param.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/df-core.c
    trunk/gcc/params.def


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #50 from zadeck at naturalbridge dot com  2008-01-17 21:06 -------
Subject:  [4.3 regression] bad interaction between DF
 and SJLJ exceptions

This is the second of three patches to fix 34400.  This patch also makes
some progress on 26854 but more work is required that is not going to be
done in 4.3 to fix the problems here. 

This patch uses the output of the df_lr problem to make the df_live
problem converge faster. 
This not only saves time but also space since the size of the df_live
bitmaps never grows and the space of our bitmaps is proportional to the
number of 1 bits.

This has been tested on several platforms and along with the patch just
committed cuts the time on the 34400 problems significantly.  I believe
that this patch also has some modest improvement on bootstrap time, i.e
regular programs.

The change to df_live_reset is a slightly related latent bug fix.

Ok to commit?

Kenny


2008-01-17  Kenneth Zadeck  <zadeck@naturalbridge.com>
        Steven Bosscher  <stevenb.gcc@gmail.com>

    PR rtl-optimization/26854
    PR rtl-optimization/34400
    * df-problems.c (df_live_scratch): New scratch bitmap.
    (df_live_alloc): Allocate df_live_scratch when doing df_live.
    (df_live_reset): Clear the proper bitmaps.
    (df_live_bb_local_compute): Only process the artificial defs once
    since the order is not important.
    (df_live_init): Init the df_live sets only with the variables
    found live by df_lr.
    (df_live_transfer_function): Use the df_lr sets to prune the
    df_live sets as they are being computed.  
    (df_live_free): Free df_live_scratch.

Index: df-problems.c
===================================================================
--- df-problems.c       (revision 130752)
+++ df-problems.c       (working copy)
@@ -1323,6 +1323,8 @@ struct df_live_problem_data
   bitmap *out;
 };

+/* Scratch var used by transfer functions.  */
+static bitmap df_live_scratch;

 /* Set basic block info.  */

@@ -1366,6 +1368,8 @@ df_live_alloc (bitmap all_blocks ATTRIBU
   if (!df_live->block_pool)
     df_live->block_pool = create_alloc_pool ("df_live_block pool", 
                                           sizeof (struct df_live_bb_info),
100);
+  if (!df_live_scratch)
+    df_live_scratch = BITMAP_ALLOC (NULL);

   df_grow_bb_info (df_live);

@@ -1401,7 +1405,7 @@ df_live_reset (bitmap all_blocks)

   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
-      struct df_lr_bb_info *bb_info = df_lr_get_bb_info (bb_index);
+      struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
       gcc_assert (bb_info);
       bitmap_clear (bb_info->in);
       bitmap_clear (bb_info->out);
@@ -1420,13 +1424,6 @@ df_live_bb_local_compute (unsigned int b
   struct df_ref **def_rec;
   int luid = 0;

-  for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
-    {
-      struct df_ref *def = *def_rec;
-      if (DF_REF_FLAGS (def) & DF_REF_AT_TOP)
-       bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
-    }
-
   FOR_BB_INSNS (bb, insn)
     {
       unsigned int uid = INSN_UID (insn);
@@ -1467,8 +1464,7 @@ df_live_bb_local_compute (unsigned int b
   for (def_rec = df_get_artificial_defs (bb_index); *def_rec; def_rec++)
     {
       struct df_ref *def = *def_rec;
-      if ((DF_REF_FLAGS (def) & DF_REF_AT_TOP) == 0)
-       bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
+      bitmap_set_bit (bb_info->gen, DF_REF_REGNO (def));
     }
 }

@@ -1504,8 +1500,11 @@ df_live_init (bitmap all_blocks)
   EXECUTE_IF_SET_IN_BITMAP (all_blocks, 0, bb_index, bi)
     {
       struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
+      struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);

-      bitmap_copy (bb_info->out, bb_info->gen);
+      /* No register may reach a location where it is not used.  Thus
+        we trim the rr result to the places where it is used.  */
+      bitmap_and (bb_info->out, bb_info->gen, bb_lr_info->out);
       bitmap_clear (bb_info->in);
     }
 }
@@ -1531,12 +1530,18 @@ static bool
 df_live_transfer_function (int bb_index)
 {
   struct df_live_bb_info *bb_info = df_live_get_bb_info (bb_index);
+  struct df_lr_bb_info *bb_lr_info = df_lr_get_bb_info (bb_index);
   bitmap in = bb_info->in;
   bitmap out = bb_info->out;
   bitmap gen = bb_info->gen;
   bitmap kill = bb_info->kill;

-  return bitmap_ior_and_compl (out, gen, in, kill);
+  bitmap_and (df_live_scratch, gen, bb_lr_info->out);
+  /* No register may reach a location where it is not used.  Thus
+     we trim the rr result to the places where it is used.  */
+  bitmap_and_into (in, bb_lr_info->in);
+
+  return bitmap_ior_and_compl (out, df_live_scratch, in, kill);
 }


@@ -1591,6 +1596,9 @@ df_live_free (void)
       free_alloc_pool (df_live->block_pool);
       df_live->block_info_size = 0;
       free (df_live->block_info);
+
+      if (df_live_scratch)
+       BITMAP_FREE (df_live_scratch);
     }
   BITMAP_FREE (df_live->out_of_date_transfer_functions);
   free (df_live);


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[seongbae dot park at gmail dot com]

------- Comment #51 from seongbae dot park at gmail dot com  2008-01-17 21:31 -------
Subject: Re:  [4.3 regression] bad interaction between DF and SJLJ exceptions

In df_live_transfer_function:

Doesn't look like we need df_live_scratch - can't we do:

bitmap_and (out, gen, bb_lr_info->out);
bitmap_and_into (in, bb_lr_info->in);
return bitmap_ior_and_compl_into (out, in, kill);

?

Seongbae

On Jan 17, 2008 1:05 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> This is the second of three patches to fix 34400.  This patch also makes
> some progress on 26854 but more work is required that is not going to be
> done in 4.3 to fix the problems here.
>
> This patch uses the output of the df_lr problem to make the df_live
> problem converge faster.
> This not only saves time but also space since the size of the df_live
> bitmaps never grows and the space of our bitmaps is proportional to the
> number of 1 bits.
>
> This has been tested on several platforms and along with the patch just
> committed cuts the time on the 34400 problems significantly.  I believe
> that this patch also has some modest improvement on bootstrap time, i.e
> regular programs.
>
> The change to df_live_reset is a slightly related latent bug fix.
>
> Ok to commit?
>
> Kenny
>
>
> 2008-01-17  Kenneth Zadeck  <zadeck@naturalbridge.com>
>         Steven Bosscher  <stevenb.gcc@gmail.com>
>
>     PR rtl-optimization/26854
>     PR rtl-optimization/34400
>     * df-problems.c (df_live_scratch): New scratch bitmap.
>     (df_live_alloc): Allocate df_live_scratch when doing df_live.
>     (df_live_reset): Clear the proper bitmaps.
>     (df_live_bb_local_compute): Only process the artificial defs once
>     since the order is not important.
>     (df_live_init): Init the df_live sets only with the variables
>     found live by df_lr.
>     (df_live_transfer_function): Use the df_lr sets to prune the
>     df_live sets as they are being computed.
>     (df_live_free): Free df_live_scratch.
>
>


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[seongbae dot park at gmail dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2932 bytes --]



------- Comment #52 from seongbae dot park at gmail dot com  2008-01-17 22:31 -------
Subject: Re:  [4.3 regression] bad interaction between DF and SJLJ exceptions

I just talked to Kenny on the phone, and my suggestion is wrong
since it changes the return value - doing my naive suggestion
would lead to infinite loop, as the transfer function will almost always
return true, even when the out set didn't change.
Can you add a comment to that effect there ?
Also please add a comment above df_live_scratch definition
that this is an optimization to reduce memory allocation overhead
for the scratch.

Can you explain why the hunk in df_live_bb_local_compute() is correct ?
As this seems to change what DF_REF_AT_TOP means for artificial defs...

Seongbae

On Jan 17, 2008 1:31 PM, Seongbae Park (¹Ú¼º¹è, ÚÓà÷ÛÆ)
<seongbae.park@gmail.com> wrote:
> In df_live_transfer_function:
>
> Doesn't look like we need df_live_scratch - can't we do:
>
> bitmap_and (out, gen, bb_lr_info->out);
> bitmap_and_into (in, bb_lr_info->in);
> return bitmap_ior_and_compl_into (out, in, kill);
>
> ?
>
> Seongbae
>
>
> On Jan 17, 2008 1:05 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
> > This is the second of three patches to fix 34400.  This patch also makes
> > some progress on 26854 but more work is required that is not going to be
> > done in 4.3 to fix the problems here.
> >
> > This patch uses the output of the df_lr problem to make the df_live
> > problem converge faster.
> > This not only saves time but also space since the size of the df_live
> > bitmaps never grows and the space of our bitmaps is proportional to the
> > number of 1 bits.
> >
> > This has been tested on several platforms and along with the patch just
> > committed cuts the time on the 34400 problems significantly.  I believe
> > that this patch also has some modest improvement on bootstrap time, i.e
> > regular programs.
> >
> > The change to df_live_reset is a slightly related latent bug fix.
> >
> > Ok to commit?
> >
> > Kenny
> >
> >
> > 2008-01-17  Kenneth Zadeck  <zadeck@naturalbridge.com>
> >         Steven Bosscher  <stevenb.gcc@gmail.com>
> >
> >     PR rtl-optimization/26854
> >     PR rtl-optimization/34400
> >     * df-problems.c (df_live_scratch): New scratch bitmap.
> >     (df_live_alloc): Allocate df_live_scratch when doing df_live.
> >     (df_live_reset): Clear the proper bitmaps.
> >     (df_live_bb_local_compute): Only process the artificial defs once
> >     since the order is not important.
> >     (df_live_init): Init the df_live sets only with the variables
> >     found live by df_lr.
> >     (df_live_transfer_function): Use the df_lr sets to prune the
> >     df_live sets as they are being computed.
> >     (df_live_free): Free df_live_scratch.
> >
> >
>
>
>
> --
> #pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com"
>


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 3493 bytes --]



------- Comment #53 from zadeck at naturalbridge dot com  2008-01-17 22:37 -------
Subject: Re:  [4.3 regression] bad interaction between
 DF and SJLJ exceptions

seongbae dot park at gmail dot com wrote:
> ------- Comment #52 from seongbae dot park at gmail dot com  2008-01-17 22:31 -------
> Subject: Re:  [4.3 regression] bad interaction between DF and SJLJ exceptions
>
> I just talked to Kenny on the phone, and my suggestion is wrong
> since it changes the return value - doing my naive suggestion
> would lead to infinite loop, as the transfer function will almost always
> return true, even when the out set didn't change.
> Can you add a comment to that effect there ?
> Also please add a comment above df_live_scratch definition
> that this is an optimization to reduce memory allocation overhead
> for the scratch.
>
>   
will do.

> Can you explain why the hunk in df_live_bb_local_compute() is correct ?
> As this seems to change what DF_REF_AT_TOP means for artificial defs...
>
>   
In the old code we went thru the artificial defs twice, once for the
defs at the bottom and once for the defs at the top.  This is a waste of
time.  we only need to go thru them once since, for this problem, the
processing is order independent.


> Seongbae
>
> On Jan 17, 2008 1:31 PM, Seongbae Park (¹Ú¼º¹è, ÚÓà÷ÛÆ)
> <seongbae.park@gmail.com> wrote:
>   
>> In df_live_transfer_function:
>>
>> Doesn't look like we need df_live_scratch - can't we do:
>>
>> bitmap_and (out, gen, bb_lr_info->out);
>> bitmap_and_into (in, bb_lr_info->in);
>> return bitmap_ior_and_compl_into (out, in, kill);
>>
>> ?
>>
>> Seongbae
>>
>>
>> On Jan 17, 2008 1:05 PM, Kenneth Zadeck <zadeck@naturalbridge.com> wrote:
>>     
>>> This is the second of three patches to fix 34400.  This patch also makes
>>> some progress on 26854 but more work is required that is not going to be
>>> done in 4.3 to fix the problems here.
>>>
>>> This patch uses the output of the df_lr problem to make the df_live
>>> problem converge faster.
>>> This not only saves time but also space since the size of the df_live
>>> bitmaps never grows and the space of our bitmaps is proportional to the
>>> number of 1 bits.
>>>
>>> This has been tested on several platforms and along with the patch just
>>> committed cuts the time on the 34400 problems significantly.  I believe
>>> that this patch also has some modest improvement on bootstrap time, i.e
>>> regular programs.
>>>
>>> The change to df_live_reset is a slightly related latent bug fix.
>>>
>>> Ok to commit?
>>>
>>> Kenny
>>>
>>>
>>> 2008-01-17  Kenneth Zadeck  <zadeck@naturalbridge.com>
>>>         Steven Bosscher  <stevenb.gcc@gmail.com>
>>>
>>>     PR rtl-optimization/26854
>>>     PR rtl-optimization/34400
>>>     * df-problems.c (df_live_scratch): New scratch bitmap.
>>>     (df_live_alloc): Allocate df_live_scratch when doing df_live.
>>>     (df_live_reset): Clear the proper bitmaps.
>>>     (df_live_bb_local_compute): Only process the artificial defs once
>>>     since the order is not important.
>>>     (df_live_init): Init the df_live sets only with the variables
>>>     found live by df_lr.
>>>     (df_live_transfer_function): Use the df_lr sets to prune the
>>>     df_live sets as they are being computed.
>>>     (df_live_free): Free df_live_scratch.
>>>
>>>
>>>       
>>
>> --
>> #pragma ident "Seongbae Park, compiler, http://seongbae.blogspot.com"
>>
>>     
>
>
>   


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at gcc dot gnu dot org]

------- Comment #54 from zadeck at gcc dot gnu dot org  2008-01-19 00:39 -------
Subject: Bug 34400

Author: zadeck
Date: Sat Jan 19 00:38:34 2008
New Revision: 131649

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131649
Log:
2008-01-18  Kenneth Zadeck  <zadeck@naturalbridge.com>
            Steven Bosscher  <stevenb.gcc@gmail.com>

        PR rtl-optimization/26854
        PR rtl-optimization/34400
        * df-problems.c (df_live_scratch): New scratch bitmap.
        (df_live_alloc): Allocate df_live_scratch when doing df_live.
        (df_live_reset): Clear the proper bitmaps.
        (df_live_bb_local_compute): Only process the artificial defs once
        since the order is not important.
        (df_live_init): Init the df_live sets only with the variables
        found live by df_lr.
        (df_live_transfer_function): Use the df_lr sets to prune the
        df_live sets as they are being computed.  
        (df_live_free): Free df_live_scratch.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/df-problems.c


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[steven at gcc dot gnu dot org]

------- Comment #55 from steven at gcc dot gnu dot org  2008-01-19 09:41 -------
IMHO we can close this one now as fixed.  Objections to that, anyone?


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #56 from zadeck at naturalbridge dot com  2008-01-19 13:09 -------
Subject: Re:  [4.3 regression] bad interaction between DF and SJLJ exceptions

Let me commit the patch first.

Sent from my iPod

On Jan 19, 2008, at 4:41 AM, "steven at gcc dot gnu dot org"
<gcc-bugzilla@gcc.gnu.org 
 > wrote:

>
>
> ------- Comment #55 from steven at gcc dot gnu dot org  2008-01-19  
> 09:41 -------
> IMHO we can close this one now as fixed.  Objections to that, anyone?
>
>
> -- 
>
>
> http://gcc.gnu.org/bugzilla/show_bug.cgi?id=34400
>
> ------- You are receiving this mail because: -------
> You are on the CC list for the bug, or are watching someone who is.


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at gcc dot gnu dot org]

------- Comment #57 from zadeck at gcc dot gnu dot org  2008-01-20 01:49 -------
Subject: Bug 34400

Author: zadeck
Date: Sun Jan 20 01:48:25 2008
New Revision: 131670

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131670
Log:
2008-01-19  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR rtl-optimization/26854
        PR rtl-optimization/34400
        * ddg.c (create_ddg_dep_from_intra_loop_link): Do not use
        DF_RD->gen.
        * df.h (df_changeable_flags.DF_RD_NO_TRIM): New.
        (df_rd_bb_info.expanded_lr_out): New.
        * loop_invariant.c (find_defs): Added DF_RD_NO_TRIM flag.
        * loop_iv.c (iv_analysis_loop_init): Ditto.
        * df-problems.c (df_rd_free_bb_info, df_rd_alloc, df_rd_confluence_n,
        df_rd_bb_local_compute, df_rd_transfer_function, df_rd_free):
        Added code to allocate, initialize or free expanded_lr_out.
        (df_rd_bb_local_compute_process_def): Restructured to make
        more understandable.
        (df_rd_confluence_n): Add code to do nothing with fake edges and
        code to no apply invalidate_by_call sets if the sets are being trimmed.
        (df_lr_local_finalize): Renamed to df_lr_finalize.
        (df_live_local_finalize): Renamed to df_live_finalize.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ddg.c
    trunk/gcc/df-problems.c
    trunk/gcc/df.h
    trunk/gcc/loop-invariant.c
    trunk/gcc/loop-iv.c


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at naturalbridge dot com]

------- Comment #58 from zadeck at naturalbridge dot com  2008-01-20 02:13 -------
The three patches that have been committed seem to have brought this under
control.


-- 

zadeck at naturalbridge dot com changed:

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


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[zadeck at gcc dot gnu dot org]

------- Comment #59 from zadeck at gcc dot gnu dot org  2008-01-22 13:57 -------
Subject: Bug 34400

Author: zadeck
Date: Tue Jan 22 13:57:01 2008
New Revision: 131719

URL: http://gcc.gnu.org/viewcvs?root=gcc&view=rev&rev=131719
Log:
2008-01-22  Kenneth Zadeck <zadeck@naturalbridge.com>

        PR rtl-optimization/26854
        PR rtl-optimization/34400
        PR rtl-optimization/34884
        * ddg.c (create_ddg_dep_from_intra_loop_link): Use
        DF_RD->gen.
        * df.h (df_changeable_flags.DF_RD_NO_TRIM): Deleted
        (df_rd_bb_info.expanded_lr_out): Deleted
        * loop_invariant.c (find_defs): Deleted DF_RD_NO_TRIM flag.
        * loop_iv.c (iv_analysis_loop_init): Ditto.  * df-problems.c
        (df_rd_free_bb_info, df_rd_alloc, df_rd_confluence_n,
        df_rd_bb_local_compute, df_rd_transfer_function, df_rd_free):
        Removed code to allocate, initialize or free expanded_lr_out.
        (df_rd_bb_local_compute_process_def): Restructured to make more
        understandable.
        (df_rd_confluence_n): Removed code to no apply invalidate_by_call
        sets if the sets are being trimmed.


Modified:
    trunk/gcc/ChangeLog
    trunk/gcc/ddg.c
    trunk/gcc/df-problems.c
    trunk/gcc/df.h
    trunk/gcc/loop-invariant.c
    trunk/gcc/loop-iv.c


-- 


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

[Bug middle-end/34400] [4.3 regression] bad interaction between DF and SJLJ exceptions

[joel at gcc dot gnu dot org]

------- Comment #60 from joel at gcc dot gnu dot org  2008-01-23 15:12 -------
I did a build of powerpc-rtems4.9 on the trunk and it built much more quickly. 
I haven't had a chance to run the ACATS yet to check run-time behavior.  Thanks
for all the effort for this one.


-- 


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