This is the mail archive of the
gcc-patches@gcc.gnu.org
mailing list for the GCC project.
Re: [PATCH][PR 59521] Respect probabilities when expanding switch statement
On Tue, Jul 18, 2017 at 8:45 AM, Jan Hubicka <hubicka@ucw.cz> wrote:
>> Hi all,
>>
>> Currently all cases in switch statement are treated as having equal
>> probabilities which causes suboptimal code as demonstrated in
>> https://gcc.gnu.org/bugzilla/show_bug.cgi?id=59521 . This patch
>> modifies expander to select pivot point for decision tree so that
>> probabilities of cases on the left are roughly equal to probabilities
>> on the right.
>>
>> Patch survives bootstrap and regtesting on x64 but has some issues:
>> * tests are fragile but I'm not sure how to make them better
>> * I haven't done any performance measurements - would these be needed?
>> I don't have access to SPEC these days, any other suggestions?
>
> I think we could just check if daily testers shows some regressions after
> patch is comitted. It seems right think to do.
You mean gcc.opensuse.org? Makes sense.
>> Patch is jointly authored with Martin.
>
> 2017-06-29 Yury Gribov <tetra2005@gmail.com>
> Martin Liska <marxin@gcc.gnu.org>
>
> PR middle-end/59521
> gcc/
> * predict.c (set_even_probabilities): Handle case of a single
> likely edge.
>
> I have made some changes to this fuction to fix other PR. So you may need
> to update the patch.
Will do.
> What exactly is set_even_probabilities and combine_predictions_for_bb shooting for?
combine_predictions_for_bb calculates final probability for edges of
if-else or switch statements.
For if-elses this is done by combining values computed by different
predictors using Dempster-Shafer theory. For switch statement DS is
not used, mainly because we do not have heuristics for predicting
which case will be taken (paper by Larus concluded that using if-else
heuristics does not give good results).
So until this patch we just used set_even_probabilities. The name of
this function is misleading, in addition to setting even probabilities
it can also understand that some edges are very unlikely and set
unlikely probs for those. With patch it now also understands that one
edge is very likely.
> @@ -2451,7 +2484,30 @@ tree_predict_by_opcode (basic_block bb)
> edge_iterator ei;
> enum br_predictor predictor;
>
> - if (!stmt || gimple_code (stmt) != GIMPLE_COND)
> + if (!stmt)
> + return;
> +
> + if (gswitch *sw = dyn_cast <gswitch *> (stmt))
> + {
> + tree index = gimple_switch_index (sw);
> + tree val = expr_expected_value (index, auto_bitmap (),
> + &predictor);
> + if (val && TREE_CODE (val) == INTEGER_CST)
> + {
> + edge e = find_taken_edge_switch_expr (sw, bb, val);
> + if (predictor == PRED_BUILTIN_EXPECT)
> + {
> + int percent = PARAM_VALUE (BUILTIN_EXPECT_PROBABILITY);
> + gcc_assert (percent >= 0 && percent <= 100);
> + predict_edge (e, PRED_BUILTIN_EXPECT,
> + HITRATE (percent));
> + }
> + else
> + predict_edge_def (e, predictor, TAKEN);
> + }
> + }
> +
> + if (gimple_code (stmt) != GIMPLE_COND)
>
> I think this change can go in separately and is OK
> (along with a testcase that checks that tree profile is right).
Ok.
> I will look into the RTL bits next.
>
> Honza