From: Feng Xue OS <fxue@os.amperecomputing.com>
To: Jan Hubicka <hubicka@ucw.cz>
Cc: Martin Jambor <mjambor@suse.cz>,
"gcc-patches@gcc.gnu.org" <gcc-patches@gcc.gnu.org>
Subject: [PATCH 1/2 V3] Setup predicate for switch default case in IPA (PR ipa/91089)
Date: Mon, 16 Sep 2019 10:11:00 -0000 [thread overview]
Message-ID: <BYAPR01MB4869A47D390B3D4E2C15F82FF78C0@BYAPR01MB4869.prod.exchangelabs.com> (raw)
In-Reply-To: <20190914155710.kjmnk42tdkdgmzd7@kam.mff.cuni.cz>
>> + if (this_code != ERROR_MARK
>> + && !dominated_by_p (CDI_POST_DOMINATORS, bb, e->dest))
>> {
>> predicate p
>> = add_condition (summary, index, size, &aggpos, this_code,
> So this change is handling the diamond conditional you describe above?
> This is bit of hack since it leaves the edge predicate unnecesarily
> conservative though I see it saves some conditions to be inserted and
> makes things to go smoother.
>
> Please add a comment that explain this and reffers to the other places
> where we do this (in the switch handling below).
Done.
> I believe the case ranges always has to be INTEGER_CST. In this case all
> this can be written using wide ints and produce a lot better code
> (avoiding need to build & lookup & share all temporary tree codes).
> You can take a look at the tree-switch-conversion code which does quite
> some of this wide int handling.
>
> Richard may have an opinion on this.
Done.
> So this basically the idea is to or BB's predicate to the
> post-dominator predicate. This seems safe to do (we need to be careful
> so that the dataflow still converges), but I would preffer to get this
> in separately possibly with a testcase that shows an improvement in the
> dataflow answer.
I've split the patch to two.
Thanks for your comments.
Feng
---
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index 1391a562c35..7f312c96f37 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -11960,6 +11960,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<std::pair<tree, tree> > 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..1461aa4849d 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -1123,6 +1123,14 @@ 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. For switch exceeding this limit, do not construct cost-"
+ "evaluating predicate for default case during IPA function summary"
+ "generation.",
+ 5, 0, 0)
+
/* WHOPR partitioning configuration. */
DEFPARAM (PARAM_LTO_PARTITIONS,
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.17.1
next prev parent reply other threads:[~2019-09-16 10:11 UTC|newest]
Thread overview: 11+ messages / expand[flat|nested] mbox.gz Atom feed top
2019-07-12 8:51 [PATCH] " Feng Xue OS
2019-08-29 15:14 ` Martin Jambor
2019-08-30 8:32 ` Feng Xue OS
2019-09-02 3:06 ` [PATCH V2] " Feng Xue OS
2019-09-14 15:57 ` Jan Hubicka
2019-09-16 10:11 ` Feng Xue OS [this message]
2019-09-16 15:04 ` [PATCH 1/2 V3] " Jan Hubicka
2019-09-17 13:51 ` Feng Xue OS
2019-09-16 10:16 ` [PATCH 2/2 V3] Use post-dom info to update if/switch predicate " Feng Xue OS
2019-09-16 15:05 ` Jan Hubicka
2019-09-17 13:54 ` Feng Xue OS
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=BYAPR01MB4869A47D390B3D4E2C15F82FF78C0@BYAPR01MB4869.prod.exchangelabs.com \
--to=fxue@os.amperecomputing.com \
--cc=gcc-patches@gcc.gnu.org \
--cc=hubicka@ucw.cz \
--cc=mjambor@suse.cz \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for read-only IMAP folder(s) and NNTP newsgroup(s).