From 351e7c3b5fbd45bde3efb601f7fee9a31c4f2063 Mon Sep 17 00:00:00 2001 From: Feng Xue Date: Tue, 17 Sep 2019 12:30:08 +0000 Subject: [PATCH] PR ipa/91089 - Setup predicate for switch default case in IPA 2019-09-17 Feng Xue PR ipa/91089 * doc/invoke.texi (ipa-max-switch-predicate-bounds): Document new option. * params.def (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS): New. * ipa-fnsummary.c (set_switch_stmt_execution_predicate): Add predicate for switch default case using range analysis information. 2019-09-17 Feng Xue PR ipa/91089 * gcc.dg/ipa/pr91089.c: New test. From-SVN: r275802 --- gcc/ChangeLog | 9 +++ gcc/doc/invoke.texi | 6 ++ gcc/ipa-fnsummary.c | 123 +++++++++++++++++++++++++++-- gcc/params.def | 6 ++ gcc/testsuite/ChangeLog | 5 ++ gcc/testsuite/gcc.dg/ipa/pr91089.c | 62 +++++++++++++++ 6 files changed, 204 insertions(+), 7 deletions(-) create mode 100644 gcc/testsuite/gcc.dg/ipa/pr91089.c diff --git a/gcc/ChangeLog b/gcc/ChangeLog index 144ed9bb861..0cbb512bb1d 100644 --- a/gcc/ChangeLog +++ b/gcc/ChangeLog @@ -1,3 +1,12 @@ +2019-09-17 Feng Xue + + PR ipa/91089 + * doc/invoke.texi (ipa-max-switch-predicate-bounds): Document new + option. + * params.def (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS): New. + * ipa-fnsummary.c (set_switch_stmt_execution_predicate): Add predicate + for switch default case using range analysis information. + 2019-09-17 Christophe Lyon PR target/91749 diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi index fe5cf35bc12..0e3693598e7 100644 --- a/gcc/doc/invoke.texi +++ b/gcc/doc/invoke.texi @@ -11937,6 +11937,12 @@ not spend too much time analyzing huge functions, it gives up and consider all memory clobbered after examining @option{ipa-max-aa-steps} statements modifying memory. +@item ipa-max-switch-predicate-bounds +Maximal number of boundary endpoints of case ranges of switch statement. +For switch exceeding this limit, IPA-CP will not construct cloning cost +predicate, which is used to estimate cloning benefit, for default case +of the switch statement. + @item lto-partitions Specify desired number of partitions produced during WHOPR compilation. The number of partitions should exceed the number of CPUs used for compilation. diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c index 278bf606661..1bf1806eaf8 100644 --- a/gcc/ipa-fnsummary.c +++ b/gcc/ipa-fnsummary.c @@ -1269,13 +1269,21 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, if (!unmodified_parm_or_parm_agg_item (fbi, last, op, &index, &size, &aggpos)) return; + auto_vec > ranges; + tree type = TREE_TYPE (op); + int bound_limit = PARAM_VALUE (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS); + int bound_count = 0; + wide_int vr_wmin, vr_wmax; + value_range_kind vr_type = get_range_info (op, &vr_wmin, &vr_wmax); + FOR_EACH_EDGE (e, ei, bb->succs) { e->aux = edge_predicate_pool.allocate (); *(predicate *) e->aux = false; } + n = gimple_switch_num_labels (last); - for (case_idx = 0; case_idx < n; ++case_idx) + for (case_idx = 1; case_idx < n; ++case_idx) { tree cl = gimple_switch_label (last, case_idx); tree min, max; @@ -1285,12 +1293,7 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, min = CASE_LOW (cl); max = CASE_HIGH (cl); - /* For default we might want to construct predicate that none - of cases is met, but it is bit hard to do not having negations - of conditionals handy. */ - if (!min && !max) - p = true; - else if (!max) + if (!max) p = add_condition (summary, index, size, &aggpos, EQ_EXPR, unshare_expr_without_location (min)); else @@ -1304,7 +1307,113 @@ set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi, } *(class predicate *) e->aux = p.or_with (summary->conds, *(class predicate *) e->aux); + + /* If there are too many disjoint case ranges, predicate for default + case might become too complicated. So add a limit here. */ + if (bound_count > bound_limit) + continue; + + bool new_range = true; + + if (!ranges.is_empty ()) + { + wide_int curr_wmin = wi::to_wide (min); + wide_int last_wmax = wi::to_wide (ranges.last ().second); + + /* Merge case ranges if they are continuous. */ + if (curr_wmin == last_wmax + 1) + new_range = false; + else if (vr_type == VR_ANTI_RANGE) + { + /* If two disjoint case ranges can be connected by anti-range + of switch index, combine them to one range. */ + if (wi::lt_p (vr_wmax, curr_wmin - 1, TYPE_SIGN (type))) + vr_type = VR_UNDEFINED; + else if (wi::le_p (vr_wmin, last_wmax + 1, TYPE_SIGN (type))) + new_range = false; + } + } + + if (!max) + max = min; + + /* Create/extend a case range. And we count endpoints of range set, + this number nearly equals to number of conditions that we will create + for predicate of default case. */ + if (new_range) + { + bound_count += (min == max) ? 1 : 2; + ranges.safe_push (std::make_pair (min, max)); + } + else + { + bound_count += (ranges.last ().first == ranges.last ().second); + ranges.last ().second = max; + } + } + + e = gimple_switch_edge (cfun, last, 0); + if (bound_count > bound_limit) + { + *(class predicate *) e->aux = true; + return; } + + predicate p_seg = true; + predicate p_all = false; + + if (vr_type != VR_RANGE) + { + vr_wmin = wi::to_wide (TYPE_MIN_VALUE (type)); + vr_wmax = wi::to_wide (TYPE_MAX_VALUE (type)); + } + + /* Construct predicate to represent default range set that is negation of + all case ranges. Case range is classified as containing single/non-single + values. Suppose a piece of case ranges in the following. + + [D1...D2] [S1] ... [Sn] [D3...D4] + + To represent default case's range sets between two non-single value + case ranges (From D2 to D3), we construct predicate as: + + D2 < x < D3 && x != S1 && ... && x != Sn + */ + for (size_t i = 0; i < ranges.length (); i++) + { + tree min = ranges[i].first; + tree max = ranges[i].second; + + if (min == max) + p_seg &= add_condition (summary, index, size, &aggpos, NE_EXPR, + unshare_expr_without_location (min)); + else + { + /* Do not create sub-predicate for range that is beyond low bound + of switch index. */ + if (wi::lt_p (vr_wmin, wi::to_wide (min), TYPE_SIGN (type))) + { + p_seg &= add_condition (summary, index, size, &aggpos, LT_EXPR, + unshare_expr_without_location (min)); + p_all = p_all.or_with (summary->conds, p_seg); + } + + /* Do not create sub-predicate for range that is beyond up bound + of switch index. */ + if (wi::le_p (vr_wmax, wi::to_wide (max), TYPE_SIGN (type))) + { + p_seg = false; + break; + } + + p_seg = add_condition (summary, index, size, &aggpos, GT_EXPR, + unshare_expr_without_location (max)); + } + } + + p_all = p_all.or_with (summary->conds, p_seg); + *(class predicate *) e->aux + = p_all.or_with (summary->conds, *(class predicate *) e->aux); } diff --git a/gcc/params.def b/gcc/params.def index 13001a7bb2d..5fe33976b37 100644 --- a/gcc/params.def +++ b/gcc/params.def @@ -1123,6 +1123,12 @@ DEFPARAM (PARAM_IPA_MAX_AA_STEPS, "parameter analysis based on alias analysis in any given function.", 25000, 0, 0) +DEFPARAM (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS, + "ipa-max-switch-predicate-bounds", + "Maximal number of boundary endpoints of case ranges of switch " + "statement used during IPA functoin summary generation.", + 5, 0, 0) + /* WHOPR partitioning configuration. */ DEFPARAM (PARAM_LTO_PARTITIONS, diff --git a/gcc/testsuite/ChangeLog b/gcc/testsuite/ChangeLog index de8b5a66feb..1afad7897f7 100644 --- a/gcc/testsuite/ChangeLog +++ b/gcc/testsuite/ChangeLog @@ -1,3 +1,8 @@ +2019-09-17 Feng Xue + + PR ipa/91089 + * gcc.dg/ipa/pr91089.c: New test. + 2019-09-17 Paul Thomas PR fortran/91588 diff --git a/gcc/testsuite/gcc.dg/ipa/pr91089.c b/gcc/testsuite/gcc.dg/ipa/pr91089.c new file mode 100644 index 00000000000..e9e206fc24d --- /dev/null +++ b/gcc/testsuite/gcc.dg/ipa/pr91089.c @@ -0,0 +1,62 @@ +/* { dg-do compile } */ +/* { dg-options "-O3 -fdump-ipa-cp-details -fdump-ipa-fnsummary-details --param ipa-max-switch-predicate-bounds=10 -fno-inline" } */ + +int fn (); + +int data; + +int callee (int i) +{ + switch (i) + { + case -126: return i + 13; + case -127: return i + 5; + case -8: return i * i; + case 0: return i % 9; + case 5: + case 7: + case 6: return 3; + default: + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + fn (); + } + + return data += i; +} + +int caller () +{ + return callee (-127) + + callee (-126) + + callee (-8) + + callee (0) + + callee (5) + + callee (6) + + callee (7) + + callee (100); +} + +/* { dg-final { scan-ipa-dump-times "Creating a specialized node of callee" 7 "cp" } } */ +/* { dg-final { scan-ipa-dump "op0 < -127" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 > -126" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 != -8" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 != 0" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 < 5" "fnsummary" } } */ +/* { dg-final { scan-ipa-dump "op0 > 7" "fnsummary" } } */ -- 2.30.2