Re: dataflow branch merging plans.

Re: dataflow branch merging plans.

[Kenneth Zadeck]

Ulrich Weigand wrote:
>
> Kenneth Zadeck <zadeck@naturalbridge.com> wrote on 05/23/2007 03:19:05 PM:
>
> > At this point, we know that the branch works correctly for x86-32,
> > x86-64, ppc-32, ppc-64 and ia-64 and sh.  We have not recently tested
> > the arm, spu, mips, z390, and spark.  These did work at some point but
> > need to be retested to see if any regressions have crept in.
>
> Andreas has provided updated test results for s390 and s390x:
> http://gcc.gnu.org/ml/gcc-testresults/2007-05/msg01365.html
> http://gcc.gnu.org/ml/gcc-testresults/2007-05/msg01371.html
>
> There are a number of FAILs, but as mainline currently doesn't
> appear to build at all in our regression tester, I'm not sure
> if those are specific to the dataflow branch.
>
> Andreas, do you have any updates on mainline?
>
Ulrich,

The best way to proceed here is to check out a trunk and then say
contrib/gcc_update -r 124834

This is the version of the truck that we last merged with and is now a
week or so out.  I would be surprised if you have any problems running
the regression tests on this version.  Eric Christopher has also had
problems with the trunk of later versions than we merged with the mips port.

If you do have trouble with 124834, i think that the dataflow branch
just has to declare victory, but this is unlikely.  The likely scenario
is that it will work and there might be a few regressions.

Thanks for getting this far. 

Kenny
>
> Mit freundlichen Gruessen / Best Regards
>
> Ulrich Weigand
>
> -- 
>  Dr. Ulrich Weigand | Phone: +49-7031/16-3727
>  GNU compiler/toolchain for Linux on System z and Cell BE
>  IBM Deutschland Entwicklung GmbH
>  Vorsitzender des Aufsichtsrats: Martin Jetter | Geschäftsführung:
> Herbert Kircher
>  Sitz der Gesellschaft: Böblingen | Registergericht: Amtsgericht
> Stuttgart, HRB 243294 

Re: dataflow branch merging plans.

[Andreas Krebbel1]

Hi,

dataflow branch is clean for s390 and s390x.

> The best way to proceed here is to check out a trunk and then say
> contrib/gcc_update -r 124834
>
> This is the version of the truck that we last merged with and is now a
> week or so out.  I would be surprised if you have any problems running
> the regression tests on this version.  Eric Christopher has also had
> problems with the trunk of later versions than we merged with the mips
port.
>
> If you do have trouble with 124834, i think that the dataflow branch
> just has to declare victory, but this is unlikely.  The likely scenario
> is that it will work and there might be a few regressions.

I've compared the mainline GCC from the last merge point with a recent
dataflow checkout:

s390 (31bit) Two ada testcase get fixed with the dataflow branch. No
regressions otherwise.

< LAST_UPDATED: Tue May 29 13:39:45 UTC 2007 (revision 125162)
---
> LAST_UPDATED: Tue May 29 07:01:10 UTC 2007 (revision 124834)
4a5,6
> FAIL: c36205l
> FAIL: cxg2009
22c24
< /build2/gcc-dataflow-build/gcc/testsuite/g++/../../g++  version 4.3.0
20070518 (experimental)
---
> /build2/gcc-4.3-build/gcc/testsuite/g++/../../g++  version 4.3.0 20070518
(experimental)
31a34,35
> XPASS: gcc.dg/cpp/cmdlne-dI-M.c scan-file
(^|\\\\n)cmdlne-dI-M.*:[^\\\\n]*cmdlne-dI-M.c
> XPASS: gcc.dg/cpp/cmdlne-dM-M.c scan-file
(^|\\\\n)cmdlne-dM-M[^\\\\n]*:[^\\\\n]*cmdlne-dM-M.c


s390x (64bit) No regressions at all. The fortran secnds.f testcase still
behaves indeterministic.

< LAST_UPDATED: Tue May 29 13:39:54 UTC 2007 (revision 125162)
---
> LAST_UPDATED: Tue May 29 07:00:56 UTC 2007 (revision 124834M)
22c22
< /build2/gcc-dataflow-build/gcc/testsuite/g++/../../g++  version 4.3.0
20070518 (experimental)
---
> /build2/gcc-4.3-build/gcc/testsuite/g++/../../g++  version 4.3.0 20070518
(experimental)
31a32,33
> XPASS: gcc.dg/cpp/cmdlne-dI-M.c scan-file
(^|\\\\n)cmdlne-dI-M.*:[^\\\\n]*cmdlne-dI-M.c
> XPASS: gcc.dg/cpp/cmdlne-dM-M.c scan-file
(^|\\\\n)cmdlne-dM-M[^\\\\n]*:[^\\\\n]*cmdlne-dM-M.c
...
< FAIL: gfortran.dg/secnds.f  -O2  execution test
---
> FAIL: gfortran.dg/secnds.f  -Os  execution test

Bye,

-Andreas-

Re: dataflow branch merging plans.

[Kenneth Zadeck]

Andreas Krebbel1 wrote:
> Hi,
>
> dataflow branch is clean for s390 and s390x.
>
>   
>> The best way to proceed here is to check out a trunk and then say
>> contrib/gcc_update -r 124834
>>
>> This is the version of the truck that we last merged with and is now a
>> week or so out.  I would be surprised if you have any problems running
>> the regression tests on this version.  Eric Christopher has also had
>> problems with the trunk of later versions than we merged with the mips
>>     
> port.
>   
>> If you do have trouble with 124834, i think that the dataflow branch
>> just has to declare victory, but this is unlikely.  The likely scenario
>> is that it will work and there might be a few regressions.
>>     
>
> I've compared the mainline GCC from the last merge point with a recent
> dataflow checkout:
>
> s390 (31bit) Two ada testcase get fixed with the dataflow branch. No
> regressions otherwise.
>
> < LAST_UPDATED: Tue May 29 13:39:45 UTC 2007 (revision 125162)
> ---
>   
>> LAST_UPDATED: Tue May 29 07:01:10 UTC 2007 (revision 124834)
>>     
> 4a5,6
>   
>> FAIL: c36205l
>> FAIL: cxg2009
>>     
> 22c24
> < /build2/gcc-dataflow-build/gcc/testsuite/g++/../../g++  version 4.3.0
> 20070518 (experimental)
> ---
>   
>> /build2/gcc-4.3-build/gcc/testsuite/g++/../../g++  version 4.3.0 20070518
>>     
> (experimental)
> 31a34,35
>   
>> XPASS: gcc.dg/cpp/cmdlne-dI-M.c scan-file
>>     
> (^|\\\\n)cmdlne-dI-M.*:[^\\\\n]*cmdlne-dI-M.c
>   
>> XPASS: gcc.dg/cpp/cmdlne-dM-M.c scan-file
>>     
> (^|\\\\n)cmdlne-dM-M[^\\\\n]*:[^\\\\n]*cmdlne-dM-M.c
>
>
> s390x (64bit) No regressions at all. The fortran secnds.f testcase still
> behaves indeterministic.
>
> < LAST_UPDATED: Tue May 29 13:39:54 UTC 2007 (revision 125162)
> ---
>   
>> LAST_UPDATED: Tue May 29 07:00:56 UTC 2007 (revision 124834M)
>>     
> 22c22
> < /build2/gcc-dataflow-build/gcc/testsuite/g++/../../g++  version 4.3.0
> 20070518 (experimental)
> ---
>   
>> /build2/gcc-4.3-build/gcc/testsuite/g++/../../g++  version 4.3.0 20070518
>>     
> (experimental)
> 31a32,33
>   
>> XPASS: gcc.dg/cpp/cmdlne-dI-M.c scan-file
>>     
> (^|\\\\n)cmdlne-dI-M.*:[^\\\\n]*cmdlne-dI-M.c
>   
>> XPASS: gcc.dg/cpp/cmdlne-dM-M.c scan-file
>>     
> (^|\\\\n)cmdlne-dM-M[^\\\\n]*:[^\\\\n]*cmdlne-dM-M.c
> ...
> < FAIL: gfortran.dg/secnds.f  -O2  execution test
> ---
>   
>> FAIL: gfortran.dg/secnds.f  -Os  execution test
>>     
>
> Bye,
>
> -Andreas-
>
>   
thanks, this is great news.

Re: dataflow branch merging plans

[Zack Weinberg]

Steven Bosscher wrote:
>
> I also seem to recall I said that Zack has done all the good work on
> genautomata, and I think it's pretty much generally agreed that the
> algorithms you originally used to implement genautomata left some
> rather large room for improvement.

I don't know exactly what Steven is thinking of when he says this, but
I consider my contributions to genautomata to be quite minimal.  I
split genautomata out of genattrtab (in aid of removing dependencies
on tm.h, IIRC), and I was able to demonstrate *why* DFA pipeline
descriptions make genattrtab run so slowly[1], but I was not able to
fix it.  I also seem to have ripped out a bunch of unused code from
both, and tightened up the emitted data tables.  I did not make any
major algorithmic contributions to genattrtab/genautomata, and I
haven't touched the scheduler proper at all (that I can remember).

zw

[1] http://gcc.gnu.org/ml/gcc-patches/2006-01/msg00399.html

Re: dataflow branch merging plans.

[Andrew_Pinski]

[-- Attachment #1: Type: text/plain, Size: 1759 bytes --]

Andrew Pinski/R&D/SCEA wrote on 05/23/2007 06:29:17 PM:

> Kenneth Zadeck <zadeck@naturalbridge.com> wrote on 05/23/2007 06:19:05 
AM:
> 
> > We have not recently tested the arm, spu, mips, z390, and sparc.
> 
> For spu-elf, we have one regression:
> 
> /home/apinski/src/dataflow/gcc/gcc/testsuite/gcc.dg/pr27335.c: In 
function 'foo':^M
> /home/apinski/src/dataflow/gcc/gcc/testsuite/gcc.dg/pr27335.c:27: 
internal compiler error: in df_refs_verify, at df-scan.c:4075^M
> Please submit a full bug report,^M
>  with preprocessed source if appropriate.^M
> See <URL:http://gcc.gnu.org/bugs.html> for instructions.^M
>  FAIL: gcc.dg/pr27335.c (internal compiler error)
> FAIL: gcc.dg/pr27335.c (test for excess errors)
> Excess errors: 
/home/apinski/src/dataflow/gcc/gcc/testsuite/gcc.dg/pr27335.c:27: internal 
compiler error: in df_refs_verify, at df-scan.c:4075
> 
> The instruction at the time we are verifying:
> (insn 147 146 148 7 (set (reg:SI 240)
>         (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
>             (zero_extend:SI (subreg:HI (reg:SI 238) 2)))) -1 
(expr_list:REG_EQUAL (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
>             (const_int 43690 [0xaaaa]))
>         (nil)))
> 
> Note this is compiling with -O2 -funroll-loops.
> 
> If you need to debug this more than what I have given so far, I be 
willing to show you how to build a cross compiler for spu-elf.

Ok, thanks to Paolo, I found an easy fix, unshare the rtl during the 
expand.
Attached is the patch which I am testing right now and will apply to both 
the mainline and branch after the test is finished.

Thanks,
Andrew Pinski

ChangeLog:

        * config/spu/spu.md (smulsi3_highpart): Unshare the rtl chain.
        (umulsi3_highpart): Likewise.



[-- Attachment #2: fixspu-df.diff.txt --]
[-- Type: text/plain, Size: 1579 bytes --]

Index: spu.md
===================================================================
--- spu.md	(revision 124997)
+++ spu.md	(working copy)
@@ -1396,7 +1396,7 @@ (define_expand "smulsi3_highpart"
     rtx t0_hi = gen_rtx_SUBREG (HImode, t0, 2);
     rtx t1_hi = gen_rtx_SUBREG (HImode, t1, 2);
 
-    emit_insn (gen_lshrsi3 (t0, operands[1], GEN_INT (16)));
+    rtx insn = emit_insn (gen_lshrsi3 (t0, operands[1], GEN_INT (16)));
     emit_insn (gen_lshrsi3 (t1, operands[2], GEN_INT (16)));
     emit_insn (gen_umulhisi3 (t2, op1_hi, op2_hi));
     emit_insn (gen_mpyh_si (t3, operands[1], operands[2]));
@@ -1425,6 +1425,7 @@ (define_expand "smulsi3_highpart"
     emit_insn (gen_extendhisi2 (t20, t18));
     emit_insn (gen_addsi3 (t21, t19, t20));
     emit_insn (gen_addsi3 (operands[0], t14, t21));
+    unshare_all_rtl_in_chain (insn);
     DONE;
   })
 
@@ -1456,7 +1457,7 @@ (define_expand "umulsi3_highpart"
     rtx op2_hi = gen_rtx_SUBREG (HImode, operands[2], 2);
     rtx t0_hi = gen_rtx_SUBREG (HImode, t0, 2);
 
-    emit_insn (gen_rotlsi3 (t0, operands[2], GEN_INT (16)));
+    rtx insn = emit_insn (gen_rotlsi3 (t0, operands[2], GEN_INT (16)));
     emit_insn (gen_umulhisi3 (t1, op1_hi, op2_hi));
     emit_insn (gen_umulhisi3 (t2, op1_hi, t0_hi));
     emit_insn (gen_mpyhhu_si (t3, operands[1], t0));
@@ -1475,6 +1476,7 @@ (define_expand "umulsi3_highpart"
     emit_insn (gen_addx_si (t13, t4, t7, t10));
     emit_insn (gen_addx_si (t14, t13, t8, t12));
     emit_insn (gen_movsi (operands[0], t14));
+    unshare_all_rtl_in_chain (insn);
 
     DONE;
   })

dataflow branch merging plans.

[Kenneth Zadeck]

I believe that the dataflow branch is now ready to merge into the
mainline.  We have fixed almost all of the performance problems
associated with it.  While there are still some left, we feel
confident that these can be addressed during the rest of stage I and
during stage II.

At this point there is one known correctness regression
(fp-int-convert-float128-timode.c on the x86-64).  This is being
addressed.

I believe we are near or better on generated code on all platforms
than the current trunk.  The only spec performance regressions that we
have seen are tracable to the dataflow branch generating fewer
instructions and you get unlucky sometimes. This has been confirmed by
Vlad in his latest spec runs.

Serge Belyshev has confirmed that the branch builds an runs the x86-64
kernel.  

At this point, we know that the branch works correctly for x86-32,
x86-64, ppc-32, ppc-64 and ia-64 and sh.  We have not recently tested
the arm, spu, mips, z390, and spark.  These did work at some point but
need to be retested to see if any regressions have crept in.

We know there are regressions in the 68k, alpha and the pa-risc.
During the next few days we would like to work on clearing the 68k
regressions.  The alpha port needs attention from someone interested
in maintaining the port.  The pa is abusing regs_ever_live and this
will be addressed after the merge.

When ARM, SPU, Mips, SPARC, and z390 are reconfirmed, approximately
nine ports will work, which is well beyond the criteria approved for
the merge.

While the majority of the hard technical issues have been vetted with
the proper maintainers, most of the patches have not been looked at by
the people who care about the formatting and coding standards (or else
my typing skills have improved dramatically.)  I would invite anyone
who wants to comment on any part of the branch to do so in the next
few days.  You should take a diff with truck revision 124834, the
revision we merged with last Friday.  If you are going to send
comments based on this diff, please make sure to include enough
context to easily find the places that need to be fixed.  This is a
very large patch.

At this point I am closing the branch to improvement except for:
1) comments from above
2) those patches that directly fix regressions or
make more ports work.
3) one patch from Seonbae Park and a few patches from Paolo Bonzini
that are in the queue and will most likely go in today.

I hope to merge this into the truck around the first of next week.  

Thanks everyone for all of the help on this branch.

Kenny

Re: dataflow branch merging plans.

[Andrew_Pinski]

Kenneth Zadeck <zadeck@naturalbridge.com> wrote on 05/23/2007 06:19:05 AM:

> We have not recently tested the arm, spu, mips, z390, and sparc.

For spu-elf, we have one regression:

/home/apinski/src/dataflow/gcc/gcc/testsuite/gcc.dg/pr27335.c: In function 
'foo':^M
/home/apinski/src/dataflow/gcc/gcc/testsuite/gcc.dg/pr27335.c:27: internal 
compiler error: in df_refs_verify, at df-scan.c:4075^M
Please submit a full bug report,^M
 with preprocessed source if appropriate.^M
See <URL:http://gcc.gnu.org/bugs.html> for instructions.^M
 FAIL: gcc.dg/pr27335.c (internal compiler error)
FAIL: gcc.dg/pr27335.c (test for excess errors)
Excess errors: 
/home/apinski/src/dataflow/gcc/gcc/testsuite/gcc.dg/pr27335.c:27: internal 
compiler error: in df_refs_verify, at df-scan.c:4075

The instruction at the time we are verifying:
(insn 147 146 148 7 (set (reg:SI 240)
        (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
            (zero_extend:SI (subreg:HI (reg:SI 238) 2)))) -1 
(expr_list:REG_EQUAL (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
            (const_int 43690 [0xaaaa]))
        (nil)))

Note this is compiling with -O2 -funroll-loops.

If you need to debug this more than what I have given so far, I be willing 
to show you how to build a cross compiler for spu-elf.

Thanks,
Andrew Pinski

Re: dataflow branch merging plans.

[Paolo Bonzini]

> The instruction at the time we are verifying:
> (insn 147 146 148 7 (set (reg:SI 240)
>         (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
>             (zero_extend:SI (subreg:HI (reg:SI 238) 2)))) -1 
> (expr_list:REG_EQUAL (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
>             (const_int 43690 [0xaaaa]))
>         (nil)))

This is an RTL sharing problem between insn 146 and insn 147, caused by 
the umulsi3_highpart pattern of spu.md (but the same applies to 
smulsi3_highpart), expanded by loop unrolling.

I think you have to use a define_insn_and_split the same way you do with 
mulsi3 vs. _mulsi3.

Paolo

Re: dataflow branch merging plans.

[Paolo Bonzini]

> The instruction at the time we are verifying:
> (insn 147 146 148 7 (set (reg:SI 240)
>         (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
>             (zero_extend:SI (subreg:HI (reg:SI 238) 2)))) -1 
> (expr_list:REG_EQUAL (mult:SI (zero_extend:SI (subreg:HI (reg:SI 234) 2))
>             (const_int 43690 [0xaaaa]))
>         (nil)))

This is an RTL sharing problem between insn 146 and insn 147, caused by 
the umulsi3_highpart pattern of spu.md (but the same applies to 
smulsi3_highpart), expanded by loop unrolling.

I think you have to use a define_insn_and_split the same way you do with 
mulsi3 vs. _mulsi3.

Paolo

Re: dataflow branch merging plans.

[Bernd Schmidt]

Kenneth Zadeck wrote:
> I believe that the dataflow branch is now ready to merge into the
> mainline.  We have fixed almost all of the performance problems
> associated with it.  While there are still some left, we feel
> confident that these can be addressed during the rest of stage I and
> during stage II.

Vlad's last benchmark run still showed up to 11% compile time
regression, didn't it?


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif

Re: dataflow branch merging plans.

[Kenneth Zadeck]

Bernd Schmidt wrote:
> Kenneth Zadeck wrote:
>   
>> I believe that the dataflow branch is now ready to merge into the
>> mainline.  We have fixed almost all of the performance problems
>> associated with it.  While there are still some left, we feel
>> confident that these can be addressed during the rest of stage I and
>> during stage II.
>>     
>
> Vlad's last benchmark run still showed up to 11% compile time
> regression, didn't it?
>
>
> Bernd
>   
The ia-64 is an outlier at 11% as is the ppc at .9%.  I think that it is
quite likely that there is some ia-64 unique pass, like one of the
schedulers, that needs a look at.  This will be addressed after the merge. 

Kenny

Re: dataflow branch merging plans.

[Bernd Schmidt]

Kenneth Zadeck wrote:
> Bernd Schmidt wrote:
>> Kenneth Zadeck wrote:
>>   
>>> I believe that the dataflow branch is now ready to merge into the
>>> mainline.  We have fixed almost all of the performance problems
>>> associated with it.  While there are still some left, we feel
>>> confident that these can be addressed during the rest of stage I and
>>> during stage II.
>>>     
>> Vlad's last benchmark run still showed up to 11% compile time
>> regression, didn't it?
>>
>>
>> Bernd
>>   
> The ia-64 is an outlier at 11% as is the ppc at .9%.  I think that it is
> quite likely that there is some ia-64 unique pass, like one of the
> schedulers, that needs a look at.  This will be addressed after the merge. 

Still, 6% compile time regression on several targets and typically a
(very small) regression in SPEC scores - am I the only one who's not
impressed?  We don't normally accept patches with these kinds of
results, and I don't see why we should make an exception here.

Why the rush to merge now?  How exactly will it make 4.3 better?

Finally, since a plan to merge next week was indicated - which
maintainer has approved it?


Bernd
-- 
This footer brought to you by insane German lawmakers.
Analog Devices GmbH      Wilhelm-Wagenfeld-Str. 6      80807 Muenchen
Sitz der Gesellschaft Muenchen, Registergericht Muenchen HRB 40368
Geschaeftsfuehrer Thomas Wessel, William A. Martin, Margaret Seif

Re: dataflow branch merging plans.

[Paolo Bonzini]

> Still, 6% compile time regression on several targets and typically a
> (very small) regression in SPEC scores - am I the only one who's not
> impressed?

I must say, I am not either despite the (not so big, but relevant) work 
I put in the branch.  I'm not sure whether this includes or not the 
dataflow checking code; this is way too expensive and it should be 
relocated to a separate --enable-checking=df option when we're closer to 
the release.

(Actually, I was supposed to do it in April, but I was swamped and -- 
anyway -- yesterday's spu bug convinced me that it is better to leave it 
in for a while).

One important thing is that this is also an enabling work for other 
improvements.  I remember Kenny had prespilling, but it didn't work 
because of the wrong liveness computation (it worked right on 
df-branch instead).	

> Finally, since a plan to merge next week was indicated - which
> maintainer has approved it?

I think the message was also meant to find a maintainer approving it.

Paolo

Re: dataflow branch merging plans.

[Kenneth Zadeck]

Bernd Schmidt wrote:
> Kenneth Zadeck wrote:
>   
>> Bernd Schmidt wrote:
>>     
>>> Kenneth Zadeck wrote:
>>>   
>>>       
>>>> I believe that the dataflow branch is now ready to merge into the
>>>> mainline.  We have fixed almost all of the performance problems
>>>> associated with it.  While there are still some left, we feel
>>>> confident that these can be addressed during the rest of stage I and
>>>> during stage II.
>>>>     
>>>>         
>>> Vlad's last benchmark run still showed up to 11% compile time
>>> regression, didn't it?
>>>
>>>
>>> Bernd
>>>   
>>>       
>> The ia-64 is an outlier at 11% as is the ppc at .9%.  I think that it is
>> quite likely that there is some ia-64 unique pass, like one of the
>> schedulers, that needs a look at.  This will be addressed after the merge. 
>>     
>
> Still, 6% compile time regression on several targets and typically a
> (very small) regression in SPEC scores - am I the only one who's not
> impressed?  We don't normally accept patches with these kinds of
> results, and I don't see why we should make an exception here.
>
>   
Bernd,

I certainly had little expectation that just replacing the dataflow
would, in itself, have a dramatic effect on the compiled code.  While
the analysis is more precise that what flow produces, that in itself was
not something that was going to change the world.
Nor was the replacement of the three optimizations, dse, dce and auto
inc detection,  that were embedded in flow.  While these passes are
finding many more opportunities for change than their predecessors in
flow, these passes themselves were not the underlying problems with the
back end.

The gains to be made are going to come from changing the way that
instruction selection, register allocation and scheduling are
implemented and these require a good dataflow foundation to get any
interesting improvements.

The problem is that much of that back end only makes cursory use of
dataflow information.  It either ignores the flow's information all
together, uses the current df,  rolls it's own (constant propagation) or
it is written using a much weaker technique that simply avoids global
information at all.

In many cases, those passes that did use flow had to be scaled back
(either deliberately or by being patched to death) because the flow was
not accurate.
Aside from changing the code to get the information from global_live_at
to DF_LIVE, we have made few other changes to these passes.  It is the
upgrading or flat out replacement of these passes which is the real
target of the df branch technology.

There were several paths that could have been taken for integration:
1) Just continue to replace passes one at a time with the df that is in
the trunk. 
This would have been much more expensive, in compile time and space than
the current approach.  As it turns out, the only way to make df
efficient is to have certain parts of it (the scanning an several other
structures) persistent.  Flow does the same thing with many of its
structures including the global_live_at vectors. 

Maintaining two sets of persistent information over the entire back end
would have been very expensive and it was clear that this was not going
to be a reasonable option.

2) Replace all of flow with df, then after the merge, then
replace/upgrade any other passes later.  The was the path that we have
set out on.  We have replaced flow, but as of yet we have not touched
any any of the passes that just roll their own. 

We have made large gains in the amount of time and space cost of this
conversion.  The time cost is really the only thing that remains, and we
will address that during the rest of stage I and stage II.

The reason for merging df now, rather than later is that we are still in
stage I, and the people who are working on df are now spending almost
all of their time fighting the differences between mainline and the
branch.  There are enough differences in the way that the mainline uses
flow, and those same passes use df to consume most of my time and great
deal of the time that seonbae, steven and paolo have to spend on this
branch.  We are no longer making any progress because of this.

I believe, and in private conversations with Vlad he believes, that we
have reached the point where there are no longer any performance
regressions introduced by the branch.  As Vlad correctly pointed out,
these would have been much more difficult to deal with once the merge
happened, and so resolving these has been our number one priority. 
> Why the rush to merge now?  How exactly will it make 4.3 better?
>   
We are in stage I.  As I have pointed out,  df provides the framework
for replacing /upgrading many of the other parts of the back end, but it
can only do that if it is actually in the compiler.   It does no good to
have it be a side branch that just diverges further and further away
from the trunk.

The truth is that there is never a great time to do a house cleaning. 
The is just the least worst time. 

> Finally, since a plan to merge next week was indicated - which
> maintainer has approved it?
>
>   
The steering committee set out criteria for merging the branch along the
lines that tree ssa was merged.  All of the work has been done in
public, and we have, as I pointed out been careful to vet the complex
interactions with the proper maintainers as we have done them. 

There is not a requirement that the branch be vetted, as in a normal
patch by a maintainer.  We certainly do not take that as a pass to just
go off and do what we want in a vacuum.  I and the rest of the people
who have worked on this branch have been quick to resolve any issues
brought up by anyone who has been watching the patches go in. 

My announcement was consistent with this.  If you or anyone else have
problems with any part of the branch, we will certainly try to address
those issues both before and after the merge.

Kenny
> Bernd
>   

Re: dataflow branch merging plans.

[Mark Mitchell]

Bernd Schmidt wrote:

> Still, 6% compile time regression on several targets and typically a
> (very small) regression in SPEC scores - am I the only one who's not
> impressed?  We don't normally accept patches with these kinds of
> results, and I don't see why we should make an exception here.

If Kenny commits to continuing to work on these issues, I think we
should trust him.  We've been around on this issue before, and we all
need to bear in mind that the point of the dataflow branch is not to
have better code immediately, but to have infrastructure that helps us
get better code.  So, as long as we're not significantly moving
backwards on generated code performance, I'm not worried about that
aspect.

As for compilation time, yes, that's a concern.  However, I think it's
reasonable to move forward, as long as Kenny commits to continuing to
work on this.  That might include, for example, converting more passes
to use the new machinery, so as to get more benefit from it.

Kenny, I think that what I would like to hear is that, roughly in order
of urgency:

(1) You will promptly address any regressions introduced by the merge
for all targets, provided you get a decent test-case.

(2) You will continue to work on integrating the new dataflow machinery
into the compiler, to help with the compile-time performance and to help
get better results out of the passes that roll their own dataflow stuff.

(3) You will promptly fix up coding standards issues that people point out.

That's what I understand you to be saying, and on that basis, I think
you should proceed with the merge.  If there are objections from other
global write maintainers in the next 48 hours, then let's try to get
consensus before you go ahead.  However, I would hope that we can all
agree to let Kenny move forward with this important piece of infrastructure.

Thanks,

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: dataflow branch merging plans.

[Kenneth Zadeck]

Mark Mitchell wrote:
> Bernd Schmidt wrote:
>
>   
>> Still, 6% compile time regression on several targets and typically a
>> (very small) regression in SPEC scores - am I the only one who's not
>> impressed?  We don't normally accept patches with these kinds of
>> results, and I don't see why we should make an exception here.
>>     
>
> If Kenny commits to continuing to work on these issues, I think we
> should trust him.  We've been around on this issue before, and we all
> need to bear in mind that the point of the dataflow branch is not to
> have better code immediately, but to have infrastructure that helps us
> get better code.  So, as long as we're not significantly moving
> backwards on generated code performance, I'm not worried about that
> aspect.
>
> As for compilation time, yes, that's a concern.  However, I think it's
> reasonable to move forward, as long as Kenny commits to continuing to
> work on this.  That might include, for example, converting more passes
> to use the new machinery, so as to get more benefit from it.
>
> Kenny, I think that what I would like to hear is that, roughly in order
> of urgency:
>
> (1) You will promptly address any regressions introduced by the merge
> for all targets, provided you get a decent test-case.
>
> (2) You will continue to work on integrating the new dataflow machinery
> into the compiler, to help with the compile-time performance and to help
> get better results out of the passes that roll their own dataflow stuff.
>
> (3) You will promptly fix up coding standards issues that people point out.
>
> That's what I understand you to be saying, and on that basis, I think
> you should proceed with the merge.  If there are objections from other
> global write maintainers in the next 48 hours, then let's try to get
> consensus before you go ahead.  However, I would hope that we can all
> agree to let Kenny move forward with this important piece of infrastructure.
>
> Thanks,
>
>   
Mark,

We will continue to work on these issues after the merge. 

My priorities have generally been (3) (1) (2).  The reason that I put
(3) in front is that these generally do not take any time in terms of
investigation or testing, so it is easiest to just do them and move on.

I put (1) next because these problem generally effect peoples ability to
work on gcc and it is unreasonable that this branch should hinder people
in their work.    However, the reports on the rest of the ports are
coming in generally good.  The sh, and arm are regression free.   The
mips may have one exception handling failure, but Eric seems to have hit
a similar problem to Ulrich, in that the trunk has destabilized since
our last merge and just checking regression against the latest mainline
is pretty iffy because of this instability. 

The performance issues will then be address, first with ia-64 since that
has been the odd man out.  Both seonbae and i have access to ia-64's so
access is not a problem.

Kenny

Re: dataflow branch merging plans.

[Mark Mitchell]

Kenneth Zadeck wrote:

>> (1) You will promptly address any regressions introduced by the merge
>> for all targets, provided you get a decent test-case.
>>
>> (2) You will continue to work on integrating the new dataflow machinery
>> into the compiler, to help with the compile-time performance and to help
>> get better results out of the passes that roll their own dataflow stuff.
>>
>> (3) You will promptly fix up coding standards issues that people point out.

> We will continue to work on these issues after the merge. 

Thank you for explicitly confirming that.

-- 
Mark Mitchell
CodeSourcery
mark@codesourcery.com
(650) 331-3385 x713

Re: dataflow branch merging plans.

[Steven Bosscher]

On 5/24/07, Bernd Schmidt <bernds_cb1@t-online.de> wrote:
> Kenneth Zadeck wrote:
> > I believe that the dataflow branch is now ready to merge into the
> > mainline.  We have fixed almost all of the performance problems
> > associated with it.  While there are still some left, we feel
> > confident that these can be addressed during the rest of stage I and
> > during stage II.
>
> Vlad's last benchmark run still showed up to 11% compile time
> regression, didn't it?

No, 8% in ia64, and somewhere between 5% and 6% on the other targets
Vlad's tested.  The 5-6% is mostly due to computing more accurate
liveness information and keeping the operands cache up to date. We'd
win a significant amount of time back if more passes would actually
use this information (esp. gcse's CPROP, and regmove, and combine).
The additional slowdown for ia64 is in the scheduler, which apparently
has more insns available to schedule. Note that the scheduler on ia64
is already dog slow even on the trunk. The DFA for Itanium is the
problem here.

Gr.
Steven

Re: dataflow branch merging plans.

[Vladimir N. Makarov]

Steven Bosscher wrote:

> On 5/24/07, Bernd Schmidt <bernds_cb1@t-online.de> wrote:
>
>> Kenneth Zadeck wrote:
>> > I believe that the dataflow branch is now ready to merge into the
>> > mainline.  We have fixed almost all of the performance problems
>> > associated with it.  While there are still some left, we feel
>> > confident that these can be addressed during the rest of stage I and
>> > during stage II.
>>
>> Vlad's last benchmark run still showed up to 11% compile time
>> regression, didn't it?
>
>
> No, 8% in ia64, and somewhere between 5% and 6% on the other targets
> Vlad's tested.

Yes, 11% is the worst dataflow branch compile time regression which is 
achieved on SPEC2000 on Itanium.  8% is on SPECINT on Itanium.

>   Note that the scheduler on ia64
> is already dog slow even on the trunk. The DFA for Itanium is the
> problem here.

Scheduler is slow on Itanium.  That is true.  But the DFA (used for fast 
pipeline hazard recognizing) was a big step forward.  It sped up all 
Itanium compiler (not only scheduler) up to 2 times and give about 3% 
improvement on SPECINT2000 (which is much harder then get the same 
improvement on SPECFP2000).  You can read more details about it in my 
artcile for the 1st GCC summit.

I am not saying that there is no better solution.  I encorauge you to 
write the scheduler (and insn bundling) faster and better without the 
DFA.  Although I should say that usage of DFA is common practise for 
Itanium schedulers.  For example, Open64 got this a few years later than 
GCC.

By the way, if you switch off scheduler (-fno-schedule-insns and 
-fno-schedule-insns2) the datafalow branch compilation speed degradation 
on Itanium will be not 11% but almost 14% on SPECFP2000.

Steven, I really value your help in rewriting old pipileine descriptions 
to the DFA ones but  please be more accurate when you jump the 
conclusion like "the DFA for Itanium is the problem here" or saying on 
IRC that most interesting work on the DFA was done by Zack.  That is not 
true.

Re: dataflow branch merging plans.

[Steven Bosscher]

On 5/25/07, Vladimir N. Makarov <vmakarov@redhat.com> wrote:
> Steven, I really value your help in rewriting old pipileine descriptions
> to the DFA ones but  please be more accurate when you jump the
> conclusion like "the DFA for Itanium is the problem here" or saying on
> IRC that most interesting work on the DFA was done by Zack.  That is not
> true.

I never said there is anything wrong with the DFA approach to
scheduling. All I said is that the compile time bottleneck for Itanium
is the DFA for itanium, i.e. the automaton that's generated from the
MD files in config/ia64/.  They're huge, and they probably have to be
given the complexity of the architecture, but it makes the whole thing
slow enough to be consistent top hits on the profiles.

I also seem to recall I said that Zack has done all the good work on
genautomata, and I think it's pretty much generally agreed that the
algorithms you originally used to implement genautomata left some
rather large room for improvement.

The only one jumping to conclusions here is you, twisting my words
somehow in ways to make them offending to you.  That is your problem,
not mine.

Gr.
Steven

Re: dataflow branch merging plans.

[Vladimir N. Makarov]

Steven Bosscher wrote:

> On 5/25/07, Vladimir N. Makarov <vmakarov@redhat.com> wrote:
>
>> Steven, I really value your help in rewriting old pipileine descriptions
>> to the DFA ones but  please be more accurate when you jump the
>> conclusion like "the DFA for Itanium is the problem here" or saying on
>> IRC that most interesting work on the DFA was done by Zack.  That is not
>> true.
>
>
> I never said there is anything wrong with the DFA approach to
> scheduling. All I said is that the compile time bottleneck for Itanium
> is the DFA for itanium, i.e. the automaton that's generated from the
> MD files in config/ia64/.  They're huge, and they probably have to be
> given the complexity of the architecture, but it makes the whole thing
> slow enough to be consistent top hits on the profiles.
>
> I also seem to recall I said that Zack has done all the good work on
> genautomata, and I think it's pretty much generally agreed that the
> algorithms you originally used to implement genautomata left some
> rather large room for improvement.
>
What you wrote was:

<stevenb> honza: you know vlad... he has great ideas, in theory, but there's a reason why he never manages to actually finish something properly ;-)
<honza> hmm, for example dfa automatos does their job relatively well...
<stevenb> ...if you're willing to accept that:
<stevenb> a) it takes 30% of the total compile time
<stevenb> b) all the good parts are written by zack
<stevenb> c) all the scheduler descriptions except itanium are written by me
<stevenb> (oh, and mips, which paolo bonzini took care of)
<stevenb> wrt. a, that's on itanium SPEC.

Well a) is not true. Probably 30% is true for all scheduler and the
DFA takes about 2-3% as I remember profile for combine.i.  Slow insn
scheduler is Itanium specific.  Intel even designed and patented path
based data dependence representation to speed up their
wavefront-scheduler.

I read b) as I wrote bad parts.  The most interesting part what Zack
changed in the DFA is 4KB savings in generated tables.  I don't know
why you mentioned Zack, there were many contributors to genautomata.c.

May be you meant something else.  Then I am sorry for
misunderstanding.  Therefore I asked you to be more accurate.

As for your the very first remark above, that is your typical
generalization.  I managed to write many things.  The last big ones
were an optimizing cross-compiler of an extendend Pascal for one
american company (I wrote all the compiler except tests.  That was
about 100K lines of C) and ongoing project cocom (cocom.sf.net) for
which sloccount gives

Total Physical Source Lines of Code (SLOC)                = 218,688
Development Effort Estimate, Person-Years (Person-Months) = 57.26 (687.11)

> The only one jumping to conclusions here is you, twisting my words
> somehow in ways to make them offending to you.  That is your problem,
> not mine.

Sory if I am twisting your words but I feel offended by your remarks on
IRC about me like "vlad's_latest_doomed_before_started_project" about
my register allocator project (by the way I am planning to put IRA to
gcc-4.4) or about my style of work.  You know I think I am not alone:
if collect your remarks on IRC about other people, probably it would
be not a great portrait.

Re: dataflow branch merging plans.

[Richard Sandiford]

"Vladimir N. Makarov" <vmakarov@redhat.com> writes:
> <stevenb> honza: you know vlad... he has great ideas, in theory, but there's a reason why he never manages to actually finish something properly ;-)
> <honza> hmm, for example dfa automatos does their job relatively well...
> <stevenb> ...if you're willing to accept that:
> <stevenb> a) it takes 30% of the total compile time
> <stevenb> b) all the good parts are written by zack
> <stevenb> c) all the scheduler descriptions except itanium are written by me
> <stevenb> (oh, and mips, which paolo bonzini took care of)

I know this wasn't meant to be taken seriously, but since Vlad has
already dissed (a) and (b), I don't think (c) is true either.
I'm not aware that Paolo wrote any of the MIPS scheduler descriptions.
(Forgive me if I'm wrong Paolo.)  The define_function_unit-to-DFA
conversion was done my Eric and myself, and the DFA-from-scratch
schedulers were written by an unholy alliance of Eric, Mike Meissner,
David Ung, Joseph Myers and me.  (Sorry again if I've missed anyone.)

And for the record, it's just as well the above wasn't meant to be
taken seriously, as I think it would do Vlad a great disservice.

Richard

Re: dataflow branch merging plans.

[Jan Hubicka]

> "Vladimir N. Makarov" <vmakarov@redhat.com> writes:
> > <stevenb> honza: you know vlad... he has great ideas, in theory, but there's a reason why he never manages to actually finish something properly ;-)
> > <honza> hmm, for example dfa automatos does their job relatively well...
> > <stevenb> ...if you're willing to accept that:
> > <stevenb> a) it takes 30% of the total compile time
> > <stevenb> b) all the good parts are written by zack
> > <stevenb> c) all the scheduler descriptions except itanium are written by me
> > <stevenb> (oh, and mips, which paolo bonzini took care of)
> 
> I know this wasn't meant to be taken seriously, but since Vlad has
> already dissed (a) and (b), I don't think (c) is true either.

Because I was quoted above, I guess I should also add that I like the
Vladimir's work.  I familiarized myself with the automaton generation
code when I needed to speed it up to get Athlon machine description
generated in resonable time and I think I know what I am speaking about
when I say that it is very nice piece of work. It was definitly hard to
implement and the problems that occured after merge was relatively
little given the complexity of project (and I probably should've
commented more on the IRC originally).  Overall I think Vladimir work is
of very good quality, a lot of it seems to end up unmerged because it
don't seems to meet orignal expectations that might be a pity as the
code might be useful anyway. (However not every developer has enought of
discipline to drop a code he spent a lot of work on when it don't seems
to do what it was supposed to very well.) DFA or new YARA are definitly
dificult projects and I am happy we have someone who can track them
down.

In general it seems to me that there is a conflict of development
philosphies.  While Vladimir is trying to get his project done to the
degree that they are stable and overall win before merging, proposed
dataflow merge is on different basis.  Main motivation for dataflow
merge seems to be that there seems to be overall agreement that we want
a new dataflow implementation and further delaying the merge don't seem
to make it significantly more ready.  It up to us, other developers,
whether we want to take responsibility to get it done for 4.3 to the
level so it is not causing compilation time, memory or wrong code bugs.

This scheme seemed to wrok for tree-SSA and might be only way to deal
with some of very dificult projects.  (Even though I am trying to merge
my larger projects when they are done, I had similar merge with original
cgraph unit-at-a-time implementation that caused a lot more problems
that I would anticipated at that time). So I would suggest to give it a
try with dataflow too. I see only other sensible option to drop it
completely that would be IMO a considerable mistake, as we will need to
modernize RTL backend sooner or later and there don't seem to be
anything fundamentally wrong with dataflow branch design as far as I can
tell. So as I admire the Vladimir's work, I admire the efforts put to
dataflow as well.

Honza

Re: dataflow branch merging plans.

[Steven Bosscher]

On 5/25/07, Richard Sandiford <richard@codesourcery.com> wrote:
> "Vladimir N. Makarov" <vmakarov@redhat.com> writes:
> > <stevenb> honza: you know vlad... he has great ideas, in theory, but there's a reason why he never manages to actually finish something properly ;-)
> > <honza> hmm, for example dfa automatos does their job relatively well...
> > <stevenb> ...if you're willing to accept that:
> > <stevenb> a) it takes 30% of the total compile time
> > <stevenb> b) all the good parts are written by zack
> > <stevenb> c) all the scheduler descriptions except itanium are written by me
> > <stevenb> (oh, and mips, which paolo bonzini took care of)
>
> I know this wasn't meant to be taken seriously,

Obviously.


> I'm not aware that Paolo wrote any of the MIPS scheduler descriptions.
> (Forgive me if I'm wrong Paolo.)  The define_function_unit-to-DFA
> conversion was done my Eric and myself, and the DFA-from-scratch
> schedulers were written by an unholy alliance of Eric, Mike Meissner,
> David Ung, Joseph Myers and me.  (Sorry again if I've missed anyone.)

Right.  To complete the record, what happened is that I converted a
bunch of old descriptions but didn't know how to handle MIPS because
there were so many rather compilcated descriptions.  Paolo came up
with a script to batch-convert the MIPS descriptions to the DFA
descriptions, but IFAIK we ended up not using those because you and
Eric (and others) helped do the conversion properly.

Gr.
Steven

Re: dataflow branch merging plans.

[Steven Bosscher]

On 5/25/07, Vladimir N. Makarov <vmakarov@redhat.com> wrote:
> Sory if I am twisting your words but I feel offended by your remarks on
> IRC about me like "vlad's_latest_doomed_before_started_project" about
> my register allocator project (by the way I am planning to put IRA to
> gcc-4.4) or about my style of work.  You know I think I am not alone:
> if collect your remarks on IRC about other people, probably it would
> be not a great portrait.

So you throw my conversations with other individuals on the mailing
list to somehow smear me and have your revenge?  Tsssk...

Gr.
Steven