[RFC] ipa bitwise constant propagation

[Martin Jambor]

Hi,

generally speaking, the ipa-cp.c and ipa-cp.[hc] bits look reasonable,
but I have a few comments:

On Thu, Aug 04, 2016 at 12:06:18PM +0530, Prathamesh Kulkarni wrote:
> Hi,
> This is a prototype patch for propagating known/unknown bits inter-procedurally.
> for integral types which propagates info obtained from get_nonzero_bits ().
> 
> Patch required making following changes:
> a) To make info from get_nonzero_bits() available to ipa

in IPA phase, you should not be looking at SSA_NAMEs, those will not
be available with LTO when you do not have access to function bodies
and thus also not to SSA_NAMES.  In IPA, you should only rely on hat
you have in jump functions.

> , I had to remove
> guard !nonzero_p in ccp_finalize. However that triggered the following ICE
> in get_ptr_info() for default_none.f95 (and several other fortran tests)
> with options: -fopenacc -O2
> ICE: http://pastebin.com/KjD7HMQi
> I confirmed with Richard that this was a latent issue.
> 
> 
> I suppose we would want to gate this on some flag, say -fipa-bit-cp ?

Yes, definitely.

> I haven't yet gated it on the flag, will do in next version of patch.
> I have added some very simple test-cases, I will try to add more
> meaningful ones.


> 
> Patch passes bootstrap+test on x86_64-unknown-linux-gnu
> and cross-tested on arm*-*-* and aarch64*-*-* with the exception
> of some fortran tests failing due to above ICE.
> 
> As next steps, I am planning to extend it to handle alignment propagation,
> and do further testing (lto-bootstrap, chromium).
> I would be grateful for feedback on the current patch.
> 
> Thanks,
> Prathamesh

> diff --git a/gcc/ipa-cp.c b/gcc/ipa-cp.c
> index 5b6cb9a..b770f6a 100644
> --- a/gcc/ipa-cp.c
> +++ b/gcc/ipa-cp.c
> @@ -120,6 +120,7 @@ along with GCC; see the file COPYING3.  If not see
>  #include "params.h"
>  #include "ipa-inline.h"
>  #include "ipa-utils.h"
> +#include "tree-ssa-ccp.h"
>  
>  template <typename valtype> class ipcp_value;
>  
> @@ -266,6 +267,40 @@ private:
>    bool meet_with_1 (unsigned new_align, unsigned new_misalign);
>  };
>  
> +/* Lattice of known bits, only capable of holding one value.
> +   Similar to ccp_prop_value_t, mask represents which bits of value are constant.
> +   If a bit in mask is set to 0, then the corresponding bit in
> +   value is known to be constant.  */
> +
> +class ipcp_bits_lattice
> +{
> +public:
> +  bool bottom_p () { return lattice_val == IPA_BITS_VARYING; }
> +  bool top_p () { return lattice_val == IPA_BITS_UNDEFINED; }
> +  bool constant_p () { return lattice_val == IPA_BITS_CONSTANT; }
> +  bool set_to_bottom ();
> +  bool set_to_constant (widest_int, widest_int, signop, unsigned);
> + 
> +  widest_int get_value () { return value; }
> +  widest_int get_mask () { return mask; }
> +  signop get_sign () { return sgn; }
> +  unsigned get_precision () { return precision; }
> +
> +  bool meet_with (ipcp_bits_lattice& other, enum tree_code, tree);
> +  bool meet_with (widest_int, widest_int, signop, unsigned);
> +
> +  void print (FILE *);
> +
> +private:
> +  enum { IPA_BITS_UNDEFINED, IPA_BITS_CONSTANT, IPA_BITS_VARYING } lattice_val;
> +  widest_int value, mask;
> +  signop sgn;
> +  unsigned precision;
> +
> +  bool meet_with_1 (widest_int, widest_int); 
> +  void get_value_and_mask (tree, widest_int *, widest_int *);
> +}; 
> +
>  /* Structure containing lattices for a parameter itself and for pieces of
>     aggregates that are passed in the parameter or by a reference in a parameter
>     plus some other useful flags.  */
> @@ -281,6 +316,8 @@ public:
>    ipcp_agg_lattice *aggs;
>    /* Lattice describing known alignment.  */
>    ipcp_alignment_lattice alignment;
> +  /* Lattice describing known bits.  */
> +  ipcp_bits_lattice bits_lattice;
>    /* Number of aggregate lattices */
>    int aggs_count;
>    /* True if aggregate data were passed by reference (as opposed to by
> @@ -458,6 +495,21 @@ ipcp_alignment_lattice::print (FILE * f)
>      fprintf (f, "         Alignment %u, misalignment %u\n", align, misalign);
>  }
>  
> +void
> +ipcp_bits_lattice::print (FILE *f)
> +{
> +  if (top_p ())
> +    fprintf (f, "         Bits unknown (TOP)\n");
> +  else if (bottom_p ())
> +    fprintf (f, "         Bits unusable (BOTTOM)\n");
> +  else
> +    {
> +      fprintf (f, "         Bits: value = "); print_hex (get_value (), f);
> +      fprintf (f, ", mask = "); print_hex (get_mask (), f);
> +      fprintf (f, "\n");
> +    }
> +}
> +
>  /* Print all ipcp_lattices of all functions to F.  */
>  
>  static void
> @@ -484,6 +536,7 @@ print_all_lattices (FILE * f, bool dump_sources, bool dump_benefits)
>  	  fprintf (f, "         ctxs: ");
>  	  plats->ctxlat.print (f, dump_sources, dump_benefits);
>  	  plats->alignment.print (f);
> +	  plats->bits_lattice.print (f);
>  	  if (plats->virt_call)
>  	    fprintf (f, "        virt_call flag set\n");
>  
> @@ -911,6 +964,161 @@ ipcp_alignment_lattice::meet_with (const ipcp_alignment_lattice &other,
>    return meet_with_1 (other.align, adjusted_misalign);
>  }
>  
> +/* Set lattice value to bottom, if it already isn't the case.  */
> +
> +bool
> +ipcp_bits_lattice::set_to_bottom ()
> +{
> +  if (bottom_p ())
> +    return false;
> +  lattice_val = IPA_BITS_VARYING;
> +  value = 0;
> +  mask = -1;
> +  return true;
> +}
> +
> +/* Set to constant if it isn't already. Only meant to be called
> +   when switching state from TOP.  */
> +
> +bool
> +ipcp_bits_lattice::set_to_constant (widest_int value, widest_int mask,
> +				    signop sgn, unsigned precision)
> +{
> +  gcc_assert (top_p ());
> +  this->lattice_val = IPA_BITS_CONSTANT;
> +  this->value = value;
> +  this->mask = mask;
> +  this->sgn = sgn;
> +  this->precision = precision;
> +  return true;
> +}
> +
> +/* Convert operand to value, mask form.  */
> +
> +void
> +ipcp_bits_lattice::get_value_and_mask (tree operand, widest_int *valuep, widest_int *maskp)
> +{
> +  wide_int get_nonzero_bits (const_tree);
> +
> +  if (TREE_CODE (operand) == INTEGER_CST)
> +    {
> +      *valuep = wi::to_widest (operand); 
> +      *maskp = 0;
> +    }
> +  else if (TREE_CODE (operand) == SSA_NAME)

IIUC, operand is the operand from pass-through jump function and that
should never be an SSA_NAME.  I have even looked at how we generate
them and it seems fairly safe to say that they never are.  If you have
seen an SSA_NAME here, it is a bug and please let me know because
sooner or later it will cause an assert.

> +    {
> +      *valuep = 0;
> +      *maskp = widest_int::from (get_nonzero_bits (operand), UNSIGNED);
> +    }
> +  else
> +    gcc_unreachable ();

The operand however can be any any other is_gimple_ip_invariant tree.
I assume that you could hit this gcc_unreachable only in a program
with undefined behavior (or with a Fortran CONST_DECL?) but you should
not ICE here.


> +}  
> +
> +/* Meet operation, similar to ccp_lattice_meet, we xor values
> +   if this->value, value have different values at same bit positions, we want
> +   to drop that bit to varying. Return true if mask is changed.
> +   This function assumes that the lattice value is in CONSTANT state  */
> +
> +bool
> +ipcp_bits_lattice::meet_with_1 (widest_int value, widest_int mask)
> +{
> +  gcc_assert (constant_p ());
> +  
> +  widest_int old_mask = this->mask;
> +  this->mask = (this->mask | mask) | (this->value ^ value);
> +
> +  if (wi::sext (this->mask, this->precision) == -1)
> +    return set_to_bottom ();
> +
> +  bool changed = this->mask != old_mask;
> +  return changed;
> +}
> +
> +/* Meet the bits lattice with operand
> +   described by <value, mask, sgn, precision.  */
> +
> +bool
> +ipcp_bits_lattice::meet_with (widest_int value, widest_int mask,
> +			      signop sgn, unsigned precision)
> +{
> +  if (bottom_p ())
> +    return false;
> +
> +  if (top_p ())
> +    {
> +      if (wi::sext (mask, precision) == -1)
> +	return set_to_bottom ();
> +      return set_to_constant (value, mask, sgn, precision);
> +    }
> +
> +  return meet_with_1 (value, mask);

What if precisions do not match?

> +}
> +
> +/* Meet bits lattice with the result of bit_value_binop_1 (other, operand)
> +   if code is binary operation or bit_value_unop_1 (other) if code is unary op.
> +   In the case when code is nop_expr, no adjustment is required. */
> +
> +bool
> +ipcp_bits_lattice::meet_with (ipcp_bits_lattice& other, enum tree_code code, tree operand)
> +{
> +  if (other.bottom_p ())
> +    return set_to_bottom ();
> +
> +  if (bottom_p () || other.top_p ())
> +    return false;
> +
> +  widest_int adjusted_value, adjusted_mask;
> +
> +  if (TREE_CODE_CLASS (code) == tcc_binary)
> +    {
> +      tree type = TREE_TYPE (operand);
> +      gcc_assert (INTEGRAL_TYPE_P (type));
> +      widest_int o_value, o_mask;
> +      get_value_and_mask (operand, &o_value, &o_mask);
> +
> +      signop sgn = other.get_sign ();
> +      unsigned prec = other.get_precision ();
> +
> +      bit_value_binop_1 (code, sgn, prec, &adjusted_value, &adjusted_mask,
> +			 sgn, prec, other.get_value (), other.get_mask (),
> +			 TYPE_SIGN (type), TYPE_PRECISION (type), o_value, o_mask);

It is probably just me not being particularly sharp on a Friday
afternoon and I might not understand the semantics of mask well (also,
you did not document it :-), but... assume that we are looking at a
binary and operation, other comes from an SSA pointer and its mask
would be binary 100 and its value 0 because that's what you set for
ssa names in ipa-prop.h, and the operand is binary value 101, which
means that get_value_and_mask returns mask 0 and value 101.  Now,
bit_value_binop_1 would return value 0 & 101 = 0 and mask according to

(m1 | m2) & ((v1 | m1) & (v2 | m2))

so in our case

(100b & 0) & ((0 | 100b) & (101b | 0)) = 0 & 100b = 0.

So both value and mask would be zero, which, if this was the only
incoming value to the lattice, I am afraid you would later on in
ipcp_update_bits interpret as that no bits can be non-zero.  Yet the
third bit clearly could.

I think that this is the only place where you interpret mask as a mask
and actually use it for and-ing, everywhere else you interpret it
basically only as the result of get_nonzero_bits and use it for
or-ing.

> +
> +      if (wi::sext (adjusted_mask, prec) == -1)
> +	return set_to_bottom ();
> +    }
> +
> +  else if (TREE_CODE_CLASS (code) == tcc_unary)
> +    {
> +      signop sgn = other.get_sign ();
> +      unsigned prec = other.get_precision ();
> +
> +      bit_value_unop_1 (code, sgn, prec, &adjusted_value,
> +			&adjusted_mask, sgn, prec, other.get_value (),
> +			other.get_mask ());
> +
> +      if (wi::sext (adjusted_mask, prec) == -1)
> +	return set_to_bottom ();
> +    }
> +
> +  else if (code == NOP_EXPR)
> +    {
> +      adjusted_value = other.value;
> +      adjusted_mask = other.mask;
> +    }
> +
> +  else
> +    return set_to_bottom ();
> +
> +  if (top_p ())
> +    {
> +      if (wi::sext (adjusted_mask, other.get_precision ()) == -1)
> +	return set_to_bottom ();
> +      return set_to_constant (adjusted_value, adjusted_mask, other.get_sign (), other.get_precision ());
> +    }
> +  else
> +    return meet_with_1 (adjusted_value, adjusted_mask);

Again, What if precisions do not match?

> +}
> +
>  /* Mark bot aggregate and scalar lattices as containing an unknown variable,
>     return true is any of them has not been marked as such so far.  */
>  
> @@ -922,6 +1130,7 @@ set_all_contains_variable (struct ipcp_param_lattices *plats)
>    ret |= plats->ctxlat.set_contains_variable ();
>    ret |= set_agg_lats_contain_variable (plats);
>    ret |= plats->alignment.set_to_bottom ();
> +  ret |= plats->bits_lattice.set_to_bottom ();
>    return ret;
>  }
>  
> @@ -1003,6 +1212,7 @@ initialize_node_lattices (struct cgraph_node *node)
>  	      plats->ctxlat.set_to_bottom ();
>  	      set_agg_lats_to_bottom (plats);
>  	      plats->alignment.set_to_bottom ();
> +	      plats->bits_lattice.set_to_bottom ();
>  	    }
>  	  else
>  	    set_all_contains_variable (plats);
> @@ -1621,6 +1831,57 @@ propagate_alignment_accross_jump_function (cgraph_edge *cs,
>      }
>  }
>  
> +/* Propagate bits across jfunc that is associated with
> +   edge cs and update dest_lattice accordingly.  */
> +
> +bool
> +propagate_bits_accross_jump_function (cgraph_edge *cs, ipa_jump_func *jfunc,
> +				      ipcp_bits_lattice *dest_lattice)
> +{
> +  if (dest_lattice->bottom_p ())
> +    return false;
> +
> +  if (jfunc->type == IPA_JF_PASS_THROUGH)
> +    {
> +      struct ipa_node_params *caller_info = IPA_NODE_REF (cs->caller);
> +      enum tree_code code = ipa_get_jf_pass_through_operation (jfunc);
> +      tree operand = NULL_TREE;
> +
> +      if (code != NOP_EXPR)
> +	operand = ipa_get_jf_pass_through_operand (jfunc);
> +
> +      int src_idx = ipa_get_jf_pass_through_formal_id (jfunc);
> +      struct ipcp_param_lattices *src_lats
> +	= ipa_get_parm_lattices (caller_info, src_idx);
> +
> +      /* Try to proapgate bits if src_lattice is bottom, but jfunc is known.

propagate

> +	 for eg consider:
> +	 int f(int x)
> +	 {
> +	   g (x & 0xff);
> +	 }
> +	 Assume lattice for x is bottom, however we can still propagate
> +	 result of x & 0xff == 0xff, which gets computed during ccp1 pass
> +	 and we store it in jump function during analysis stage.  */
> +
> +      if (src_lats->bits_lattice.bottom_p ()
> +	  && jfunc->bits.known)
> +	return dest_lattice->meet_with (jfunc->bits.value, jfunc->bits.mask,
> +				        jfunc->bits.sgn, jfunc->bits.precision);
> +      else
> +	return dest_lattice->meet_with (src_lats->bits_lattice, code, operand);
> +    }
> +
> +  else if (jfunc->type == IPA_JF_ANCESTOR)
> +    return dest_lattice->set_to_bottom ();
> +
> +  else if (jfunc->bits.known) 
> +    return dest_lattice->meet_with (jfunc->bits.value, jfunc->bits.mask,
> +				    jfunc->bits.sgn, jfunc->bits.precision);
> +  else
> +    return dest_lattice->set_to_bottom ();
> +}
> +

...

> diff --git a/gcc/ipa-prop.h b/gcc/ipa-prop.h
> index e32d078..d69a071 100644
> --- a/gcc/ipa-prop.h
> +++ b/gcc/ipa-prop.h
> @@ -154,6 +154,16 @@ struct GTY(()) ipa_alignment
>    unsigned misalign;
>  };
>  
> +/* Information about zero/non-zero bits.  */
> +struct GTY(()) ipa_bits
> +{
> +  bool known;
> +  widest_int value;
> +  widest_int mask;
> +  enum signop sgn;
> +  unsigned precision;
> +};

Please order the fields according to their size, the largest first and
add a comment describing each one of them.  As I explained above, it
is not immediately clear why the mask would be a mask, for example.

Nevertheless, thanks for looking into this.  It would be nice to have
this for pointers too, not least because we could represent
non-NULL-ness this way, which could be very interesting for cloning
and inlining.  But those are further steps, once normal propagation
works.

Martin