Re: [patch] Remove strange case cost code
Hello, There is code in stmt.c since the initial checkin, that tries to balance a switch tree according to some ascii heuristics. I see a couple of problems with this code: 1. It doesn't seem to help much. With the attached patch to remove the code, I see no compile time changes to e.g. compile GCC itself. 2. It isn't clear what the heuristic is based on (no reference to any testing done, or a reference to a book or paper). 3. The heuristic is applied for case values in the range -1,127 (inclusive) even if the type of the switch expression isn't char or int but e.g. an enum. This results in funny application of this heuristic in GCC itself to e.g. some cases of enum rtx_code and enum tree_code. Note that it would make a lot of sense to teach this heuristics predict.c and properly identify chars. Also it is possble to get an historgrams from profile feedback into switch expansion. I always wanted to do that once switch expansion code is cleaned up and moved to gimple level... Honza The attached patch removes the heuristic. Bootstrapped and tested on powerpc-unknown-linux-gnu. OK for trunk? Ciao! Steven
Re: [patch] Remove strange case cost code
On Tue, Apr 17, 2012 at 8:49 AM, Jan Hubicka hubi...@ucw.cz wrote: Hello, There is code in stmt.c since the initial checkin, that tries to balance a switch tree according to some ascii heuristics. I see a couple of problems with this code: 1. It doesn't seem to help much. With the attached patch to remove the code, I see no compile time changes to e.g. compile GCC itself. 2. It isn't clear what the heuristic is based on (no reference to any testing done, or a reference to a book or paper). 3. The heuristic is applied for case values in the range -1,127 (inclusive) even if the type of the switch expression isn't char or int but e.g. an enum. This results in funny application of this heuristic in GCC itself to e.g. some cases of enum rtx_code and enum tree_code. Note that it would make a lot of sense to teach this heuristics predict.c and properly identify chars. Indeed this would be the proper place to implement this logic. Also it is possble to get an historgrams from profile feedback into switch expansion. I always wanted to do that once switch expansion code is cleaned up and moved to gimple level... Indeed. At least the parts that expand switch stmts to (balanced) trees should be moved to the GIMPLE level, retaining only the table-jump-like expansions as switch stmts. The attached patch removes the heuristic. Bootstrapped and tested on powerpc-unknown-linux-gnu. OK for trunk? Ok. Thanks, Richard. Ciao! Steven
Re: [patch] Remove strange case cost code
Note that it would make a lot of sense to teach this heuristics predict.c and properly identify chars. Indeed this would be the proper place to implement this logic. TO a degree - switch expansion needs more info than it can obtain from edge profile. Having switch case 1,3,5,7,8,9: aaa case 2,4,6,8,10,12: bbb to produce well ballanced decision tree, it is not enough to know how often the value is even and how often it is odd... Thus there is a need for value histograms. Also it is possble to get an historgrams from profile feedback into switch expansion. I always wanted to do that once switch expansion code is cleaned up and moved to gimple level... Indeed. At least the parts that expand switch stmts to (balanced) trees should be moved to the GIMPLE level, retaining only the table-jump-like expansions as switch stmts. Yep. Honza The attached patch removes the heuristic. Bootstrapped and tested on powerpc-unknown-linux-gnu. OK for trunk? Ok. Thanks, Richard. Ciao! Steven
Re: [patch] Remove strange case cost code
Il 17/04/2012 10:45, Richard Guenther ha scritto: Also it is possble to get an historgrams from profile feedback into switch expansion. I always wanted to do that once switch expansion code is cleaned up and moved to gimple level... Indeed. At least the parts that expand switch stmts to (balanced) trees should be moved to the GIMPLE level, retaining only the table-jump-like expansions as switch stmts. This would also make it much easier to drop the range checking from switch statements (VRP would just fold those away). Also, targets could choose between casesi and tablejump. ARM can benefit from that. Paolo
Re: [patch] Remove strange case cost code
On Tue, Apr 17, 2012 at 10:45 AM, Richard Guenther richard.guent...@gmail.com wrote: Also it is possble to get an historgrams from profile feedback into switch expansion. I always wanted to do that once switch expansion code is cleaned up and moved to gimple level... Indeed. At least the parts that expand switch stmts to (balanced) trees should be moved to the GIMPLE level, retaining only the table-jump-like expansions as switch stmts. My goal for GCC 4.8 is to do just that: Move switch expansion to GIMPLE and add value profiling for switch expressions. I may put back that heuristic as a branch predictor, but I doubt it makes much of a difference. Besides, it is actually hard to figure out whether a switch expression is for characters in an ascii string because char is promoted to int. Ciao! Steven
Re: [patch] Remove strange case cost code
On Tue, Apr 17, 2012 at 10:45 AM, Richard Guenther richard.guent...@gmail.com wrote: Also it is possble to get an historgrams from profile feedback into switch expansion. I always wanted to do that once switch expansion code is cleaned up and moved to gimple level... Indeed. At least the parts that expand switch stmts to (balanced) trees should be moved to the GIMPLE level, retaining only the table-jump-like expansions as switch stmts. My goal for GCC 4.8 is to do just that: Move switch expansion to GIMPLE and add value profiling for switch expressions. I may put back that heuristic as a branch predictor, but I doubt it makes much of a difference. Besides, it is actually hard to figure out whether a I have my doubts, too, this is why it is not implemented. Lets see if the removal changes anything. Currently the branch prediction code is extraordinarily stupid on switches. We still could do better - i.e. be able to combine other types of predictions on them (i.e. switch edge leading to abort() is unlikely) and eventually we could teach VRP about value range histograms. switch expression is for characters in an ascii string because char is promoted to int. Good plan! Can you two symchonize your efforts, please? Honza Ciao! Steven
Re: [patch] Remove strange case cost code
On Tue, Apr 17, 2012 at 1:48 AM, Jan Hubicka hubi...@ucw.cz wrote: Note that it would make a lot of sense to teach this heuristics predict.c and properly identify chars. Indeed this would be the proper place to implement this logic. TO a degree - switch expansion needs more info than it can obtain from edge profile. Having switch case 1,3,5,7,8,9: aaa case 2,4,6,8,10,12: bbb to produce well ballanced decision tree, it is not enough to know how often the value is even and how often it is odd... Why is that? In this case, the expanded switch case does not use BST, but testing against bit patterns. Thus there is a need for value histograms. None of the existing value profiler will be powerful enough for this though: the one_value profiler only tracks one value. The interval profiler can potentially be used if the switch case range is small -- otherwise the runtime memory overhead will be too large. Thanks, David Also it is possble to get an historgrams from profile feedback into switch expansion. I always wanted to do that once switch expansion code is cleaned up and moved to gimple level... Indeed. At least the parts that expand switch stmts to (balanced) trees should be moved to the GIMPLE level, retaining only the table-jump-like expansions as switch stmts. Yep. Honza The attached patch removes the heuristic. Bootstrapped and tested on powerpc-unknown-linux-gnu. OK for trunk? Ok. Thanks, Richard. Ciao! Steven
Re: [patch] Remove strange case cost code
On Tue, Apr 17, 2012 at 1:48 AM, Jan Hubicka hubi...@ucw.cz wrote: Note that it would make a lot of sense to teach this heuristics predict.c and properly identify chars. Indeed this would be the proper place to implement this logic. TO a degree - switch expansion needs more info than it can obtain from edge profile. Having switch case 1,3,5,7,8,9: aaa case 2,4,6,8,10,12: bbb to produce well ballanced decision tree, it is not enough to know how often the value is even and how often it is odd... Why is that? In this case, the expanded switch case does not use BST, but testing against bit patterns. Yep, oversimplified example... Thus there is a need for value histograms. None of the existing value profiler will be powerful enough for this though: the one_value profiler only tracks one value. The interval profiler can potentially be used if the switch case range is small -- otherwise the runtime memory overhead will be too large. Adding profiler to profile individual value ranges is not that hard... But indeed, at the moment we have single value profiler only... Honza
[patch] Remove strange case cost code
Hello, There is code in stmt.c since the initial checkin, that tries to balance a switch tree according to some ascii heuristics. I see a couple of problems with this code: 1. It doesn't seem to help much. With the attached patch to remove the code, I see no compile time changes to e.g. compile GCC itself. 2. It isn't clear what the heuristic is based on (no reference to any testing done, or a reference to a book or paper). 3. The heuristic is applied for case values in the range -1,127 (inclusive) even if the type of the switch expression isn't char or int but e.g. an enum. This results in funny application of this heuristic in GCC itself to e.g. some cases of enum rtx_code and enum tree_code. The attached patch removes the heuristic. Bootstrapped and tested on powerpc-unknown-linux-gnu. OK for trunk? Ciao! Steven stmt_c_cleanup_1.diff Description: Binary data
