Setup predicate for switch default case in IPA (PR ipa/91089)
diff mbox series

Message ID BYAPR01MB48690FF0F2D7FCFE48DC17B7F7F20@BYAPR01MB4869.prod.exchangelabs.com
State New
Headers show
Series
  • Setup predicate for switch default case in IPA (PR ipa/91089)
Related show

Commit Message

Feng Xue OS July 12, 2019, 8:41 a.m. UTC
IPA does not construct executability predicate for default case of switch statement.
So execution cost of default case is not properly evaluated in IPA-cp, this might
prevent function clone for function containing switch statement, if certain non-default
case is proved to be executed after constant propagation.

This patch is composed to deduce predicate for default case, if it turns out to be a
relative simple one, for example, we can try to merge case range, and use
comparison upon range bounds, and also range analysis information to simplify 
predicate.

Feng

----

Patch
diff mbox series

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 3d92250b520..4de2f568990 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,10 @@ 
+2019-07-12  Feng Xue  <fxue@os.amperecomputing.com>
+
+	PR ipa/91089
+	* ipa-fnsummary.c (set_switch_stmt_execution_predicate): Add predicate
+	for switch default case using range analysis information.
+	* params.def (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS): New.
+
 2019-07-11  Sunil K Pandey  <sunil.k.pandey@intel.com>
 
 	PR target/90980
diff --git a/gcc/ipa-fnsummary.c b/gcc/ipa-fnsummary.c
index 09986211a1d..141fdce53c2 100644
--- a/gcc/ipa-fnsummary.c
+++ b/gcc/ipa-fnsummary.c
@@ -1289,30 +1289,35 @@  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);
+  tree one_cst = build_one_cst (type);
+  int bound_limit = PARAM_VALUE (PARAM_IPA_MAX_SWITCH_PREDICATE_BOUNDS);
+  int bound_count = 0;
+  value_range_base vr;
+
+  get_range_info (op, vr);
+
   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;
+      tree min = CASE_LOW (cl);
+      tree max = CASE_HIGH (cl);
       predicate p;
 
-      e = gimple_switch_edge (cfun, last, case_idx);
-      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)
-	p = add_condition (summary, index, size, &aggpos, EQ_EXPR,
-			   unshare_expr_without_location (min));
+      if (!max)
+	{
+	  max = min;
+
+	  p = add_condition (summary, index, size, &aggpos, EQ_EXPR,
+			     unshare_expr_without_location (min));
+	}
       else
 	{
 	  predicate p1, p2;
@@ -1322,9 +1327,112 @@  set_switch_stmt_execution_predicate (struct ipa_func_body_info *fbi,
 			      unshare_expr_without_location (max));
 	  p = p1 & p2;
 	}
+
+      e = gimple_switch_edge (cfun, last, case_idx);
       *(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 ())
+	{
+	  tree last_max_plus_one
+		= int_const_binop (PLUS_EXPR, ranges.last ().second, one_cst);
+
+	  /* Merge case ranges if they are continuous.  */
+	  if (tree_int_cst_equal (min, last_max_plus_one))
+	    new_range = false;
+	  else if (vr.kind () == VR_ANTI_RANGE)
+	    {
+	      tree min_minus_one = int_const_binop (MINUS_EXPR, min, one_cst);
+
+	      /* If anti-range of switch index can connect two disjoint case
+		 ranges, combine them to one range.  */
+	      if (tree_int_cst_lt (vr.max (), min_minus_one))
+		vr.set_undefined ();
+	      else if (tree_int_cst_le (vr.min (), last_max_plus_one))
+		new_range = false;
+	    }
+	}
+
+      /* 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;
+    }
+
+  tree vr_min = vr.kind () == VR_RANGE ? vr.min () : TYPE_MIN_VALUE (type);
+  tree vr_max = vr.kind () == VR_RANGE ? vr.max () : TYPE_MAX_VALUE (type);
+  predicate p_seg = true;
+  predicate p_all = false;
+
+  /* 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 (tree_int_cst_lt (vr_min, min))
+	    {
+	      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 (tree_int_cst_le (vr_max, max))
+	    {
+	      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 4567c17ba60..ff6920f287a 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -1121,6 +1121,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/ChangeLog b/gcc/testsuite/ChangeLog
index 6c40496db9c..ccb92bb8f7f 100644
--- a/gcc/testsuite/ChangeLog
+++ b/gcc/testsuite/ChangeLog
@@ -1,3 +1,8 @@ 
+2019-07-12  Feng Xue  <fxue@os.amperecomputing.com>
+
+	PR ipa/91089
+	* gcc.dg/ipa/pr91089.c: New test.
+
 2019-07-11  Sunil K Pandey  <sunil.k.pandey@intel.com>
 
 	PR target/90980
diff --git a/gcc/testsuite/gcc.dg/ipa/pr91089.c b/gcc/testsuite/gcc.dg/ipa/pr91089.c
new file mode 100644
index 00000000000..fa3111f565f
--- /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" } } */