[PATCH] Extend CSE to use constant anchors

[Eric Botcazou]

> The patch does not directly fix PR/33699 anymore.  That will require
> further modifications in the cost model and possibly fwprop.  Should I
> still put the PR number in the changelog?

I think so.

> 	* target.h (struct gcc_target): Fix indentation.  Add
> 	const_anchor.
> 	* target-def.h (TARGET_CONST_ANCHOR): New macro.
> 	(TARGET_INITIALIZER): Use it.
> 	* cse.c (insert): Rename this ...
> 	(insert_with_costs): ... to this.  Add cost parameters.  Update
> 	function comment.
> 	(insert): New function.  Call insert_with_costs.
> 	(compute_const_anchors, insert_const_anchor, insert_const_anchors,
> 	find_reg_offset_for_const, try_const_anchors): New functions.
> 	(cse_insn): Call try_const_anchors.  Adjust cost of src_related
> 	when using a const-anchor.  Call insert_const_anchors.

Looks good, but see the nits below:

> +/* Compute upper and lower anchors for CST.  Also compute the offset of
> CST +   from these anchors/bases such that *_BASE + *_OFFS = CST.  Return
> false iff +   CST is equal to an anchor.  */
> +
> +static bool
> +compute_const_anchors (rtx cst,
> +		       HOST_WIDE_INT *lower_base, HOST_WIDE_INT *lower_offs,
> +		       HOST_WIDE_INT *upper_base, HOST_WIDE_INT *upper_offs)
> +{
> +  HOST_WIDE_INT n = INTVAL (cst);
> +
> +  *lower_base = n & ~(targetm.const_anchor - 1);
> +  if (*lower_base == n)
> +    return false;
> +
> +  *upper_base =
> +    (n + (targetm.const_anchor - 1)) & ~(targetm.const_anchor - 1);

This requires targetm.const_anchor to be a power of 2.

> +  *upper_offs = n - *upper_base;
> +  *lower_offs = n - *lower_base;
> +  return true;
> +}
> +
> +/* Insert the equivalence between ANCHOR and EXP in mode MODE.  REG is
> +   the register in EXP.  */
> +
> +static void
> +insert_const_anchor (HOST_WIDE_INT anchor, rtx exp, enum machine_mode
> mode, +		     rtx reg)
> +{
> +  struct table_elt *elt;
> +  unsigned hash;
> +  rtx anchor_exp;
> +
> +  anchor_exp = GEN_INT (anchor);
> +  hash = HASH (anchor_exp, mode);
> +  elt = lookup (anchor_exp, hash, mode);
> +  if (!elt)
> +    elt = insert (anchor_exp, NULL, hash, mode);
> +
> +  hash = HASH (exp, mode);
> +  if (insert_regs (exp, elt, 0))
> +    {
> +      rehash_using_reg (exp);
> +      hash = HASH (exp, mode);
> +    }

exp is a plus_constant (reg, xxx) so rehash_using_reg (exp) is a no-op.

You don't need to call insert_regs since it's done just before the call to 
insert_const_anchors in cse_insn.

> +  /* Use the cost of the register rather than the whole expression.
> +     When looking up constant anchors we will further offset the
> +     corresponding expression therefore it does not make sense to
> +     prefer REGs over reg-immediate additions.  Instead prefer the
> +     oldest expression.  Also don't prefer pseudos over hard regs.  */
> +  insert_with_costs (exp, elt, hash, mode, COST (reg), 1);

Why the last sentence?

> +
> +/* The constant CST is equivalent to the register REG.  Create
> +   equivalences between the two anchors of CST and the corresponding
> +   register-offset expressions using REG.  */
> +
> +static void
> +insert_const_anchors (rtx reg, rtx cst, enum machine_mode mode)
> +{
> +  HOST_WIDE_INT lower_base, lower_offs, upper_base, upper_offs;
> +
> +  if (!compute_const_anchors (cst, &lower_base, &lower_offs,
> +			      &upper_base, &upper_offs))
> +      return;
> +
> +  /* Ignore anchors of value 0.  Constants accessible from zero are
> +     simple.  */
> +  if (lower_base != 0)
> +    insert_const_anchor (lower_base, plus_constant (reg, -lower_offs),
> mode, +			 reg);
> +
> +  if (upper_base != 0)
> +    insert_const_anchor (upper_base, plus_constant (reg, -upper_offs),
> mode, +			 reg);
> +}

I would pass the naked offset to insert_const_anchor:

insert_const_anchor (upper_base, mode, reg, -offset);

> +/* We need to express ANCHOR_ELT->exp + OFFS.  Walk the equivalence list
> of +   ANCHOR_ELT and see if offsetting any of the entries by OFFS would
> create a +   valid expression.  */

Missing comment about the return value.

> +static rtx
> +find_reg_offset_for_const (struct table_elt *anchor_elt, HOST_WIDE_INT
> offs, +			   unsigned *old)
> +{
> +  struct table_elt *elt;
> +  unsigned idx;
> +  struct table_elt *match_elt;
> +  rtx match;
> +
> +  /* Find the cheapest and *oldest* expression to maximize the chance of
> +     reusing the same pseudo.  */
> +
> +  match_elt = NULL;
> +  match = NULL_RTX;
> +  for (elt = anchor_elt->first_same_value, idx = 0;
> +       elt;
> +       elt = elt->next_same_value, idx++)
> +    {
> +      if (match_elt && CHEAPER (match_elt, elt))
> +	return match;
> +
> +      if (REG_P (elt->exp)
> +	  || (GET_CODE (elt->exp) == PLUS
> +	      && REG_P (XEXP (elt->exp, 0))
> +	      && GET_CODE (XEXP (elt->exp, 1)) == CONST_INT))
> +	{
> +	  rtx x;
> +
> +	  /* Ignore expressions that are no longer valid.  */
> +	  if (!REG_P (elt->exp) && !exp_equiv_p (elt->exp, elt->exp, 1, false))
> +	    continue;

Why excluding REGs from the validity check?

> +	  x = plus_constant (elt->exp, offs);
> +	  if (REG_P (x)
> +	      || (GET_CODE (x) == PLUS
> +		  && IN_RANGE (INTVAL (XEXP (x, 1)),
> +			       -targetm.const_anchor,
> +			       targetm.const_anchor - 1)))
> +	    {
> +	      match = x;
> +	      match_elt = elt;
> +	      *old = idx;
> +	    }
> +	}
> +    }
> +
> +  return match;
> +}
> +
> +/* Try to express the constant SRC_CONST using a register-offset
> expression +   derived from a constant anchor.  */

register+offset :-)  "Return it on success and NULL_RTX on failure".

> +
> +static rtx
> +try_const_anchors (rtx src_const, enum machine_mode mode)
> +{
> +  struct table_elt *lower_elt, *upper_elt;
> +  HOST_WIDE_INT lower_base, lower_offs, upper_base, upper_offs;
> +  rtx lower_anchor_rtx, upper_anchor_rtx;
> +  rtx lower_exp = NULL_RTX, upper_exp = NULL_RTX;
> +  unsigned lower_old, upper_old;
> +
> +  if (!compute_const_anchors (src_const, &lower_base, &lower_offs,
> +			      &upper_base, &upper_offs))
> +    return NULL_RTX;
> +
> +  lower_anchor_rtx = GEN_INT (lower_base);
> +  upper_anchor_rtx = GEN_INT (upper_base);
> +  lower_elt = lookup (lower_anchor_rtx, HASH (lower_anchor_rtx, mode),
> mode); +  upper_elt = lookup (upper_anchor_rtx, HASH (upper_anchor_rtx,
> mode), mode); +
> +  if (lower_elt)
> +    lower_exp = find_reg_offset_for_const (lower_elt, lower_offs,
> &lower_old); +  if (upper_elt)
> +    upper_exp = find_reg_offset_for_const (upper_elt, upper_offs,
> &upper_old); +
> +  if (!lower_exp)
> +    return upper_exp;
> +  if (!upper_exp)
> +    return lower_exp;
> +  /* Return the older expression.  */
> +  if (lower_old < upper_old)
> +    return upper_exp;
> +  return lower_exp;

  if (!lower_exp)
    return upper_exp;
  if (!upper_exp)
    return lower_exp;

  /* Return the older expression.  */
  return (upper_old > lower_old ? upper_exp : lower_exp);

>  

>  /* CSE processing for one instruction.
>     First simplify sources and addresses of all assignments
> @@ -4249,6 +4429,7 @@ cse_insn (rtx insn)
>        rtx src_eqv_here;
>        rtx src_const = 0;
>        rtx src_related = 0;
> +      bool src_related_is_const_anchor = false;
>        struct table_elt *src_const_elt = 0;
>        int src_cost = MAX_COST;
>        int src_eqv_cost = MAX_COST;
> @@ -4598,6 +4779,19 @@ cse_insn (rtx insn)
>  	}
>  #endif /* LOAD_EXTEND_OP */
>
> +      /* Try to express the constant using a register-offset expression
> +	 derived from a constant anchor.  */

register+offset :-)

> @@ -5436,6 +5642,14 @@ cse_insn (rtx insn)
>  	elt = insert (dest, sets[i].src_elt,
>  		      sets[i].dest_hash, GET_MODE (dest));
>
> +	/* If this is a constant, insert the constant anchors with the
> +	   equivalent register-offset expressions using register DEST.  */
> +	if (targetm.const_anchor
> +	    && REG_P (dest)
> +	    && SCALAR_INT_MODE_P (GET_MODE (dest))
> +	    && GET_CODE (sets[i].src_elt->exp) == CONST_INT)
> +	  insert_const_anchors (dest, sets[i].src_elt->exp, GET_MODE (dest));

Why not do that in insert instead? It does similar special processing already

-- 
Eric Botcazou