[GCC8,20/33] Support compare iv_use which is compared against arbitrary variable

Submitted by Bin Cheng on April 18, 2017, 10:47 a.m.

Details

Message ID VI1PR0802MB21760BE875C82470094064BCE7190@VI1PR0802MB2176.eurprd08.prod.outlook.com
State New
Headers show

Commit Message

Bin Cheng April 18, 2017, 10:47 a.m.
Hi,
Currently we only support compare iv_use if the other side of comparison is loop invariant.
Such compare iv_use can never be eliminated, but it still can be expressed.  This patch
supports the case that the other side of comparison is an arbitrary non-iv variables.
Is it OK?

Thanks,
bin

2017-04-11  Bin Cheng  <bin.cheng@arm.com>

	* tree-ssa-loop-ivopts.c (enum comp_iv_rewrite): New.
	(extract_cond_operands): Detect condition comparing against non-
	invariant bound and return appropriate enum value.
	(find_interesting_uses_cond): Update use of extract_cond_operands.
	Handle its return value accordingly.
	(determine_group_iv_cost_cond, rewrite_use_compare): Ditto.
From e280e72f2019f1fab7048a5f81534ac509066825 Mon Sep 17 00:00:00 2001
From: Bin Cheng <binche01@e108451-lin.cambridge.arm.com>
Date: Wed, 1 Mar 2017 17:17:52 +0000
Subject: [PATCH 20/33] iv-comparing-against-non_invariant-20170220.txt

---
 gcc/tree-ssa-loop-ivopts.c | 71 ++++++++++++++++++++++++++++++----------------
 1 file changed, 46 insertions(+), 25 deletions(-)

Patch hide | download patch | download mbox

diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index 6e9df43..08b6245 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -1645,6 +1645,17 @@  find_interesting_uses_op (struct ivopts_data *data, tree op)
   return use;
 }
 
+/* Indicate how compare type iv_use can be handled.  */
+enum comp_iv_rewrite
+{
+  COMP_IV_NA,
+  /* We may rewrite compare type iv_use by expressing value of the iv_use.  */
+  COMP_IV_EXPR,
+  /* We may rewrite compare type iv_use by expressing value of the iv_use
+     or by eliminating it with other iv_cand.  */
+  COMP_IV_ELIM
+};
+
 /* Given a condition in statement STMT, checks whether it is a compare
    of an induction variable and an invariant.  If this is the case,
    CONTROL_VAR is set to location of the iv, BOUND to the location of
@@ -1653,7 +1664,7 @@  find_interesting_uses_op (struct ivopts_data *data, tree op)
    the case, CONTROL_VAR and BOUND are set to the arguments of the
    condition and false is returned.  */
 
-static bool
+static enum comp_iv_rewrite
 extract_cond_operands (struct ivopts_data *data, gimple *stmt,
 		       tree **control_var, tree **bound,
 		       struct iv **iv_var, struct iv **iv_bound)
@@ -1663,7 +1674,7 @@  extract_cond_operands (struct ivopts_data *data, gimple *stmt,
   static tree zero;
   tree *op0 = &zero, *op1 = &zero;
   struct iv *iv0 = &const_iv, *iv1 = &const_iv;
-  bool ret = false;
+  enum comp_iv_rewrite rewrite_type = COMP_IV_NA;
 
   if (gimple_code (stmt) == GIMPLE_COND)
     {
@@ -1685,18 +1696,27 @@  extract_cond_operands (struct ivopts_data *data, gimple *stmt,
   if (TREE_CODE (*op1) == SSA_NAME)
     iv1 = get_iv (data, *op1);
 
-  /* Exactly one of the compared values must be an iv, and the other one must
-     be an invariant.  */
-  if (!iv0 || !iv1)
+  /* If both sides of comparison are IVs.  */
+  if (iv0 && iv1 && !integer_zerop (iv0->step) && !integer_zerop (iv1->step))
     goto end;
 
-  if (integer_zerop (iv0->step))
+  /* If none side of comparison is IV.  */
+  if ((!iv0 || integer_zerop (iv0->step))
+      && (!iv1 || integer_zerop (iv1->step)))
+    goto end;
+
+  /* Control variable may be on the other side.  */
+  if (!iv0 || integer_zerop (iv0->step))
     {
-      /* Control variable may be on the other side.  */
       std::swap (op0, op1);
       std::swap (iv0, iv1);
     }
-  ret = !integer_zerop (iv0->step) && integer_zerop (iv1->step);
+  /* If one side is IV and the other side isn't loop invariant.  */
+  if (!iv1)
+    rewrite_type = COMP_IV_EXPR;
+  /* If one side is IV and the other side is loop invariant.  */
+  else if (!integer_zerop (iv0->step) && integer_zerop (iv1->step))
+    rewrite_type = COMP_IV_ELIM;
 
 end:
   if (control_var)
@@ -1708,7 +1728,7 @@  end:
   if (iv_bound)
     *iv_bound = iv1;
 
-  return ret;
+  return rewrite_type;
 }
 
 /* Checks whether the condition in STMT is interesting and if so,
@@ -1719,15 +1739,17 @@  find_interesting_uses_cond (struct ivopts_data *data, gimple *stmt)
 {
   tree *var_p, *bound_p;
   struct iv *var_iv;
+  enum comp_iv_rewrite ret;
 
-  if (!extract_cond_operands (data, stmt, &var_p, &bound_p, &var_iv, NULL))
+  ret = extract_cond_operands (data, stmt, &var_p, &bound_p, &var_iv, NULL);
+  if (ret == COMP_IV_NA)
     {
       find_interesting_uses_op (data, *var_p);
       find_interesting_uses_op (data, *bound_p);
       return;
     }
 
-  record_group_use (data, NULL, var_iv, stmt, USE_COMPARE);
+  record_group_use (data, var_p, var_iv, stmt, USE_COMPARE);
 }
 
 /* Returns the outermost loop EXPR is obviously invariant in
@@ -5068,15 +5090,21 @@  determine_group_iv_cost_cond (struct ivopts_data *data,
   struct iv *cmp_iv;
   bitmap inv_exprs = NULL;
   bitmap inv_vars_elim = NULL, inv_vars_express = NULL, inv_vars;
-  comp_cost elim_cost, express_cost, cost, bound_cost;
-  bool ok;
+  comp_cost elim_cost = infinite_cost, express_cost, cost, bound_cost;
+  enum comp_iv_rewrite rewrite_type;
   iv_inv_expr_ent *inv_expr_elim = NULL, *inv_expr_express = NULL, *inv_expr;
   tree *control_var, *bound_cst;
   enum tree_code comp = ERROR_MARK;
   struct iv_use *use = group->vuses[0];
 
+  /* Extract condition operands.  */
+  rewrite_type = extract_cond_operands (data, use->stmt, &control_var,
+					&bound_cst, NULL, &cmp_iv);
+  gcc_assert (rewrite_type != COMP_IV_NA);
+
   /* Try iv elimination.  */
-  if (may_eliminate_iv (data, use, cand, &bound, &comp))
+  if (rewrite_type == COMP_IV_ELIM
+      && may_eliminate_iv (data, use, cand, &bound, &comp))
     {
       elim_cost = force_var_cost (data, bound, &inv_vars_elim);
       if (elim_cost.cost == 0)
@@ -5098,14 +5126,6 @@  determine_group_iv_cost_cond (struct ivopts_data *data,
 	 once.  */
       elim_cost.cost = adjust_setup_cost (data, elim_cost.cost);
     }
-  else
-    elim_cost = infinite_cost;
-
-  /* Try expressing the original giv.  If it is compared with an invariant,
-     note that we cannot get rid of it.  */
-  ok = extract_cond_operands (data, use->stmt, &control_var, &bound_cst,
-			      NULL, &cmp_iv);
-  gcc_assert (ok);
 
   /* When the condition is a comparison of the candidate IV against
      zero, prefer this IV.
@@ -6938,7 +6958,7 @@  rewrite_use_compare (struct ivopts_data *data,
   enum tree_code compare;
   struct iv_group *group = data->vgroups[use->group_id];
   struct cost_pair *cp = get_group_iv_cost (data, group, cand);
-  bool ok;
+  enum comp_iv_rewrite rewrite_type;
 
   bound = cp->value;
   if (bound)
@@ -6972,8 +6992,9 @@  rewrite_use_compare (struct ivopts_data *data,
   comp = get_computation_at (data->current_loop, use->stmt, use, cand);
   gcc_assert (comp != NULL_TREE);
 
-  ok = extract_cond_operands (data, use->stmt, &var_p, NULL, NULL, NULL);
-  gcc_assert (ok);
+  rewrite_type = extract_cond_operands (data, use->stmt,
+					&var_p, NULL, NULL, NULL);
+  gcc_assert (rewrite_type != COMP_IV_NA);
 
   *var_p = force_gimple_operand_gsi (&bsi, comp, true, SSA_NAME_VAR (*var_p),
 				     true, GSI_SAME_STMT);