Re: Hash Function for "switch statement"
Thank you Basile.
The article you pointed is exactly what I wanted to find.
The paper summarized switch optimization very well, and it enlightened me.
I am also glad that it mentioned imperfect and perfect hash for switch
statement.
Unfortunately, the super-optimization that the paper suggests doesn't
adopt any of hash table ways. In addition, the paper skimmed the
advantage of perfect hash table and it didn't even mention minimal
perfect hash table at all.
I think that for the "speed" optimization, perfect hash way is the
best candidate after jump table if it is applicable. I am currently
working on PlayStation3 game development, and we don't want to use
branch operation. Since 3d games value relatively more on speed than
space, I am still interested on perfect hash for switch statement,
because it is more generic than others the paper mentioned. It will
also require (possibly) zero branching. It would be not only my
personal preference but also the favorite of most game developers.
As usual for 3d game programming process, we have pre-calculation
steps for graphics data. During the process I am thinking to add one
more process that generates perfect hash table. The manual
implementation of perfect hash table as an alternative mean for switch
statement does not seem hard. So I may do it by myself without too
much pain, but It can make my job easier if gcc can play the role.
I wish to see gcc can adopt any of better switch optimization ways in
near future.
I haven't heard about "MELT" before and still don't know what exactly
it is. Is it able to deal with this kind of problem?
Thank you anyway.
Without the reply mail, I couldn't be satisfied this much. :-)
Regards,
Jay
On Sun, Mar 14, 2010 at 3:59 PM, Basile Starynkevitch
wrote:
> Jae Hyuk Kwak wrote:
>>
>> Hello, GCC developers.
>>
>> In addition, I found that switch statement can use "Hash Table" rather
>> than just replacing with "else if".
>> Besides using "jump table", "Hash Table" can increase speed.
>> Hash table idea can alleviate the problem of a huge size of jump table as
>> well.
>>
>
>
> It is much more complex than that. Read the paper "A Superoptimizer
> Analysis of Multiway Branch Code Generation" by Roger A. Sayle in GCC summit
> 2008 proceedings. www.gccsummit.org/2008/gcc-2008-proceedings.pdf
>
> Regards.
> --
> Basile STARYNKEVITCH http://starynkevitch.net/Basile/
> email: basilestarynkevitchnet mobile: +33 6 8501 2359
> 8, rue de la Faiencerie, 92340 Bourg La Reine, France
> *** opinions {are only mines, sont seulement les miennes} ***
>
Question on mips multiply patterns in md file
Hi : I am studying multiplication-accumulate patterns for mips and noticed there are some changes when IRA was merged. There are two pattern which confused me, as : 1: In pattern "*mul_acc_si", there's constraint like "*?*?". what does this supposed to do? I could not connect "*?" with document on constraints in gcc internal document, and totally have no idea about it. 2: there is a split pattern for "*mul_acc_si" as following: (define_split [(set (match_operand:SI 0 "d_operand") (plus:SI (mult:SI (match_operand:SI 1 "d_operand") (match_operand:SI 2 "d_operand")) (match_operand:SI 3 "d_operand"))) (clobber (match_operand:SI 4 "lo_operand")) (clobber (match_operand:SI 5 "d_operand"))] "reload_completed" [(parallel [(set (match_dup 5) (mult:SI (match_dup 1) (match_dup 2))) (clobber (match_dup 4))]) (set (match_dup 0) (plus:SI (match_dup 5) (match_dup 3)))] "") this will generate integer multiply instruction with register write, but what if the processor has only integer multiply instructions, which only store results in HILO? So, any tips? Thanks a lot. -- Best Regards.
Re: status of GCC 4.5 w.r.t. plugins?
2010/3/13 Basile Starynkevitch : > b. the plugin invocation convention could be improved. In particular, one > could have (as it is the case of many other major plugin-ehancable software, > e.g. Mozilla, Qt, Gtk, ...) a specific directory to install plugins, and > invoke gcc -fplugin=treehydra instead of gcc > -fplugin=/some/distribution/specific/path/to/treehydra.so ; I did propose a > patch for that http://gcc.gnu.org/ml/gcc-patches/2010-02/msg00353.html > http://gcc.gnu.org/ml/gcc-patches/2010-01/msg00476.html but nobody really > cares :-( Would it be appropriate to issue a ping^5 for it? Sure. I'd say it's unlikely that a review of that patch would jump out of nowhere now, so ping away. -- Laurynas
GCC 4.5 Status Report (2010-03-15)
Status == The trunk is still in stage 4 which means it is open under the usual release branch rules. Thus the trunk is open for regression and documentation fixes only. There are currently 16 P1 bugs that block the release. If you are assigned to any P1 GCC 4.5 regression please either work on them or unassign yourself. We have been in stage 4 for three and a half month now, so you can expect that some bugs that are now P1 will be downgraded to P2 at the point a release candidate is made available, simply to not block the release of 4.5.0 forever. As maintainers do not care for P1 bugs in their maintainance area so will the release managers not consider them P1. The following is a list of P1 GCC 4.5 regressions that look serious enough to myself to ping them explicitly here: 42509, arm-gnueabi doesn't bootstrap but is a primary target 43873, var-tracking deadlocks 43087, C++ ICE in tsubst 43206, C++ ICE in cp/pt.c:9249 43300, ICE during SSA expand 4, C++ __is_pod is broken 43365, EH lowering/optimization causes wrong-code 43375, ICE caused by the new vector type mangling Overall GCC 4.5 does not look bad. But we are still sorting out VTA related bugs (and improvements as it appears to me). Quality Data Priority # Change from Last Report --- --- P1 16 - 8 P2 98 + 4 P33 - 3 --- --- Total 117 - 7 Previous Report === http://gcc.gnu.org/ml/gcc/2010-02/msg00270.html The next status report will be sent by Jakub. -- Richard Guenther Novell / SUSE Labs SUSE LINUX Products GmbH - Nuernberg - AG Nuernberg - HRB 16746 - GF: Markus Rex
Re: GCC 4.5 Status Report (2010-03-15)
On 03/15/10 10:18, Richard Guenther wrote: Status == The trunk is still in stage 4 which means it is open under the usual release branch rules. Thus the trunk is open for regression and documentation fixes only. There are currently 16 P1 bugs that block the release. If you are assigned to any P1 GCC 4.5 regression please either work on them or unassign yourself. We have been in stage 4 for three and a half month now, so you can expect that some bugs that are now P1 will be downgraded to P2 at the point a release candidate is made available, simply to not block the release of 4.5.0 forever. As maintainers do not care for P1 bugs in their maintainance area so will the release managers not consider them P1. The following is a list of P1 GCC 4.5 regressions that look serious enough to myself to ping them explicitly here: 42509, arm-gnueabi doesn't bootstrap but is a primary target 43873, var-tracking deadlocks 43087, C++ ICE in tsubst 43206, C++ ICE in cp/pt.c:9249 43300, ICE during SSA expand 4, C++ __is_pod is broken 43365, EH lowering/optimization causes wrong-code 43375, ICE caused by the new vector type mangling Overall GCC 4.5 does not look bad. But we are still sorting out VTA related bugs (and improvements as it appears to me). FWIW, it might be helpful to include the list of _all_ P1s in these reports -- there may be people that have some time to help out, but don't know precisely which bugs are the most critical right now. Jeff
Re: GCC 4.5 Status Report (2010-03-15)
On Mon, 15 Mar 2010, Jeff Law wrote: > On 03/15/10 10:18, Richard Guenther wrote: > > Status > > == > > > > The trunk is still in stage 4 which means it is open under the usual > > release branch rules. Thus the trunk is open for regression and > > documentation fixes only. > > > > There are currently 16 P1 bugs that block the release. If you are > > assigned to any P1 GCC 4.5 regression please either work on them > > or unassign yourself. We have been in stage 4 for three and a half > > month now, so you can expect that some bugs that are now P1 will > > be downgraded to P2 at the point a release candidate is made > > available, simply to not block the release of 4.5.0 forever. > > As maintainers do not care for P1 bugs in their maintainance area > > so will the release managers not consider them P1. > > > > The following is a list of P1 GCC 4.5 regressions that look serious > > enough to myself to ping them explicitly here: > > > > 42509, arm-gnueabi doesn't bootstrap but is a primary target > > 43873, var-tracking deadlocks > > 43087, C++ ICE in tsubst > > 43206, C++ ICE in cp/pt.c:9249 > > 43300, ICE during SSA expand > > 4, C++ __is_pod is broken > > 43365, EH lowering/optimization causes wrong-code > > 43375, ICE caused by the new vector type mangling > > > > Overall GCC 4.5 does not look bad. But we are still sorting out > > VTA related bugs (and improvements as it appears to me). > > > FWIW, it might be helpful to include the list of _all_ P1s in these reports -- > there may be people that have some time to help out, but don't know precisely > which bugs are the most critical right now. The rest of the P1 are 41371, var-tracking slowness (fixed, waiting for more testcases) 42181, wrong-code with -fgraphite-identity 42450, cgraph checking ICE, patch available 42917, -fcompare-debug failure with -ftree-loop-linear, patch available 42977, -fcompare-debug failure with even more weird flags 43051, debug quality issue with VTA 43058, var-tracking using up all virtual memory on 32bit hosts 43092, debug correctness issue with VTA Bugzilla queries for all P1 GCC 4.5 regressions is http://gcc.gnu.org/bugzilla/buglist.cgi?query_format=advanced&short_desc_type=allwordssubstr&short_desc=4.5&target_milestone=4.3.0&target_milestone=4.3.1&target_milestone=4.3.2&target_milestone=4.3.3&target_milestone=4.3.4&target_milestone=4.3.5&target_milestone=4.3.6&target_milestone=4.4.0&target_milestone=4.4.1&target_milestone=4.4.2&target_milestone=4.4.3&target_milestone=4.4.4&target_milestone=4.4.5&target_milestone=4.5.0&known_to_fail_type=allwordssubstr&known_to_work_type=allwordssubstr&long_desc_type=allwordssubstr&long_desc=&bug_file_loc_type=allwordssubstr&bug_file_loc=&gcchost_type=allwordssubstr&gcchost=&gcctarget_type=allwordssubstr&gcctarget=&gccbuild_type=allwordssubstr&gccbuild=&keywords_type=allwords&keywords=&bug_status=UNCONFIRMED&bug_status=NEW&bug_status=ASSIGNED&bug_status=SUSPENDED&bug_status=WAITING&bug_status=REOPENED&priority=P1&emailtype1=substring&email1=&emailtype2=substring&email2=&bugidtype=include&bug_id=&votes=&chfieldfrom=&chfieldto=Now&chfiel dvalue=&cmdtype=doit&order=Reuse+same+sort+as+last+time&query_based_on=4.5+blocker&field0-0-0=noop&type0-0-0=noop&value0-0-0= Richard.
Re: GCC 4.5 Status Report (2010-03-15)
On Mon, Mar 15, 2010 at 12:18 PM, Richard Guenther wrote: > As maintainers do not care for P1 bugs in their maintainance area > so will the release managers not consider them P1. Probably not the best reason to downgrade a bug, eh?
Re: GCC 4.5 Status Report (2010-03-15)
Richard Guenther wrote:
Status
==
The trunk is still in stage 4 which means it is open under the usual
release branch rules. Thus the trunk is open for regression and
documentation fixes only.
What does that means with respect to plugin related code? See my message
on http://gcc.gnu.org/ml/gcc/2010-03/msg00140.html
Regards.
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basilestarynkevitchnet mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***
Re: Question on mips multiply patterns in md file
On 03/15/2010 01:00 AM, Amker.Cheng wrote: 1: In pattern "*mul_acc_si", there's constraint like "*?*?". what does this supposed to do? '*' is in the Constraint Modifier Characters section of the docs. It means ignore the next character for register class preferencing. '?' is in the Multiple Alternative Constraints section. It means that this alternative is less desirable than the others. So '*?' will be ignored by the register class preferencing code. It will be used in reload when computing which alternative is better though. Reload computes a cost for each alternative, and then chooses the cheapest one, or which ever one occurs first (left to right) when there are ties. '*?' has the effect of slightly increasing the reload cost of an alternative, and is used when you want to discourage reload from picking this particular alternative. If you don't know anything about register class preferencing or reload as yet, then this is probably not going to make much sense to you, but it isn't anything important you need to worry about at this point. It is a very minor performance optimization. 2: there is a split pattern for "*mul_acc_si" as following: this will generate integer multiply instruction with register write, but what if the processor has only integer multiply instructions, which only store results in HILO? A define_split can only match something generated by a define_insn, and the mul_acc_si define_insn is testing "GENERATE_MADD_MSUB && !TARGET_MIPS16" so there is no serious problem. We are just running a define_split that can never match anything. This could be cleaned up a little by adding an appropriate condition to the define_split, or by combining the define_insn and define_split patterns into a define_insn_and_split pattern. Jim
fixed-point support in c++
It looks like my patches for avr target to get native fixed-point
support may be included soon. I realized that many users use avr-g++
for their projects, and I cannot get the fixed point types working in
c++. The question is generic and should apply to all targets.
Compiling a simple test program:
int main()
{
_Accum x;
}
Works fine in c, but under c++ I get:
test.cpp:5: error: ‘_Accum’ was not declared in this scope
So I modified c-common.c:
Index: c-common.c
===
--- c-common.c (revision 157409)
+++ c-common.c (working copy)
@@ -561,9 +561,9 @@
{ "_Decimal32", RID_DFLOAT32, D_CONLY | D_EXT },
{ "_Decimal64", RID_DFLOAT64, D_CONLY | D_EXT },
{ "_Decimal128", RID_DFLOAT128, D_CONLY | D_EXT },
- { "_Fract", RID_FRACT, D_CONLY | D_EXT },
- { "_Accum", RID_ACCUM, D_CONLY | D_EXT },
- { "_Sat", RID_SAT, D_CONLY | D_EXT },
+ { "_Fract", RID_FRACT, D_EXT },
+ { "_Accum", RID_ACCUM, D_EXT },
+ { "_Sat", RID_SAT, D_EXT },
{ "__FUNCTION__",RID_FUNCTION_NAME, 0 },
{ "__PRETTY_FUNCTION__", RID_PRETTY_FUNCTION_NAME, 0 },
{ "__alignof", RID_ALIGNOF,0 },
Now the error is:
test.cpp:5:4: error: expected primary-expression before ‘_Accum’
Does anyone have clues as to the problem? I have tried a few other
things with no success.
Thanks
Sean
Re: fixed-point support in c++
On 15/03/2010 22:03, Sean D'Epagnier wrote:
> - { "_Fract", RID_FRACT, D_CONLY | D_EXT },
> - { "_Accum", RID_ACCUM, D_CONLY | D_EXT },
> - { "_Sat", RID_SAT, D_CONLY | D_EXT },
> + { "_Fract", RID_FRACT, D_EXT },
> + { "_Accum", RID_ACCUM, D_EXT },
> + { "_Sat", RID_SAT, D_EXT },
> Now the error is:
>
> test.cpp:5:4: error: expected primary-expression before ‘_Accum’
>
> Does anyone have clues as to the problem?
The problem is that it won't be as simple as that. You'll have to extend
the C++ parser to accept those new RID_ values that it was previously never
expecting to see in those contexts, I would think (but haven't verified
against the source yet). The C++ parser is a hand-coded recursive-descent
parser, so I wouldn't expect it to be generically able to deal with
previously-unknown token types suddenly appearing in its input stream at
arbitrary points.
cheers,
DaveK
Re: Hash Function for "switch statement"
I found that I had a wrong assumption on this issue.
In order to use Perfect Hash Table, we need to know every key values
at compile time, but the key values are determined at run-time so that
it is not feasible idea.
On my project, however, the key values were fixed amount, so that I
confused at that point.
I'm sorry...
Jay
On Mon, Mar 15, 2010 at 12:19 AM, Jae Hyuk Kwak wrote:
> Thank you Basile.
> The article you pointed is exactly what I wanted to find.
> The paper summarized switch optimization very well, and it enlightened me.
> I am also glad that it mentioned imperfect and perfect hash for switch
> statement.
>
> Unfortunately, the super-optimization that the paper suggests doesn't
> adopt any of hash table ways. In addition, the paper skimmed the
> advantage of perfect hash table and it didn't even mention minimal
> perfect hash table at all.
>
> I think that for the "speed" optimization, perfect hash way is the
> best candidate after jump table if it is applicable. I am currently
> working on PlayStation3 game development, and we don't want to use
> branch operation. Since 3d games value relatively more on speed than
> space, I am still interested on perfect hash for switch statement,
> because it is more generic than others the paper mentioned. It will
> also require (possibly) zero branching. It would be not only my
> personal preference but also the favorite of most game developers.
>
> As usual for 3d game programming process, we have pre-calculation
> steps for graphics data. During the process I am thinking to add one
> more process that generates perfect hash table. The manual
> implementation of perfect hash table as an alternative mean for switch
> statement does not seem hard. So I may do it by myself without too
> much pain, but It can make my job easier if gcc can play the role.
>
> I wish to see gcc can adopt any of better switch optimization ways in
> near future.
>
> I haven't heard about "MELT" before and still don't know what exactly
> it is. Is it able to deal with this kind of problem?
>
> Thank you anyway.
> Without the reply mail, I couldn't be satisfied this much. :-)
>
> Regards,
>
> Jay
>
>
> On Sun, Mar 14, 2010 at 3:59 PM, Basile Starynkevitch
> wrote:
>> Jae Hyuk Kwak wrote:
>>>
>>> Hello, GCC developers.
>>>
>>> In addition, I found that switch statement can use "Hash Table" rather
>>> than just replacing with "else if".
>>> Besides using "jump table", "Hash Table" can increase speed.
>>> Hash table idea can alleviate the problem of a huge size of jump table as
>>> well.
>>>
>>
>>
>> It is much more complex than that. Read the paper "A Superoptimizer
>> Analysis of Multiway Branch Code Generation" by Roger A. Sayle in GCC summit
>> 2008 proceedings. www.gccsummit.org/2008/gcc-2008-proceedings.pdf
>>
>> Regards.
>> --
>> Basile STARYNKEVITCH http://starynkevitch.net/Basile/
>> email: basilestarynkevitchnet mobile: +33 6 8501 2359
>> 8, rue de la Faiencerie, 92340 Bourg La Reine, France
>> *** opinions {are only mines, sont seulement les miennes} ***
>>
>
Re: Hash Function for "switch statement"
On 15/03/2010 07:19, Jae Hyuk Kwak wrote:
> I think that for the "speed" optimization, perfect hash way is the
> best candidate after jump table if it is applicable.
It should be pointed out that your article contains a false assumption
about how fast the various options are relative to each other:
> For example, when we have a piece of code like this:
>
> if( a == 1 ) doSomething1();
> else if( a == 2 ) doSomething2();
> else if( a == 3 ) doSomething3();
>
> else if( a == 4 ) doSomething4();
>
> For each line, CPU, more precisely ALU, will evaluate each statement: "a ==
> 1", "a == 2" and so on. In other words, CPU need to calculate 4 times
> for the same value "a".
This is not true unless a is a volatile variable. The compiler will
evaluate a once and then compare it against the constants.
> More intuitive representation for this testing can be like this:
>
> switch( a )
> {
> case 1: doSomething1(); break;
> case 2: doSomething2(); break;
> case 3: doSomething3(); break;
> ...
> case 4: doSomething4000(); break;
> }
>
> This "switch statement" gives us an illusion that CPU will evaluate the
> value of "a" only one time.
>
> According to an article on CodeGuru, however, "switch" statement will be
> replaced by "else if"
It may, but in this case, the result is even better; the compiler will only
ever evaluate "a" once even if it *is* volatile.
cheers,
DaveK
fixincl 'make check' regressions...
Ever since your changes installed on March 12th, I've been getting fixincludes testsuite failures of the form below. I also notice that none of these changes added ChangeLog entries, and furthermore the SVN commit messages were extremely terse so it was hard to diagnose the intent or reasoning behind your changes. iso/math_c99.h /home/davem/src/GIT/GCC/gcc/fixincludes/tests/base/iso/math_c99.h differ: char 1366, line 52 *** iso/math_c99.h Mon Mar 15 22:55:36 2010 --- /home/davem/src/GIT/GCC/gcc/fixincludes/tests/base/iso/math_c99.h Thu Jan 21 04:06:11 2010 *** *** 49,55 ? __builtin_signbitf(x) \ : sizeof(x) == sizeof(long double) \ ? __builtin_signbitl(x) \ !: __builtin_signbit(x)); #endif /* SOLARIS_MATH_8_CHECK */ --- 49,55 ? __builtin_signbitf(x) \ : sizeof(x) == sizeof(long double) \ ? __builtin_signbitl(x) \ !: __builtin_signbit(x)) #endif /* SOLARIS_MATH_8_CHECK */ There were fixinclude test FAILURES
Re: Hash Function for "switch statement"
Jae Hyuk Kwak wrote:
I haven't heard about "MELT" before and still don't know what exactly
it is. Is it able to deal with this kind of problem?
MELT is a GCC branch and a GCC plugin. It provides a Lispy domain
specific language to code GCC extensions in. More details on the GCC
wiki, in particular http://gcc.gnu.org/wiki/MiddleEndLispTranslator &
http://gcc.gnu.org/wiki/MELT%20tutorial
I believe that MELT would be a good tool for Jae to experiment his ideas
on the switch statements. He probably needs to implement a new GIMPLE
pass which tranform a GIMPLE representation into another, and MELT is
well suited for that. Feel free to ask more.
Cheers
--
Basile STARYNKEVITCH http://starynkevitch.net/Basile/
email: basilestarynkevitchnet mobile: +33 6 8501 2359
8, rue de la Faiencerie, 92340 Bourg La Reine, France
*** opinions {are only mines, sont seulement les miennes} ***
