[RFC] ipa bitwise constant propagation

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, 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.

b) I chose widest_int for representing value, mask in ipcp_bits_lattice
and correspondingly changed declarations for
bit_value_unop_1/bit_value_binop_1 to take
precision and sign instead of type (those are the only two fields that
were used). Both these functions are exported by tree-ssa-ccp.h
I hope that's ok ?

c) Changed streamer_read_wi/streamer_write_wi to non-static.
Ah I see Kugan has submitted a patch for this, so I will drop this hunk.

d) We have following in tree-ssa-ccp.c:get_default_value ():
          if (flag_tree_bit_ccp)
            {
              wide_int nonzero_bits = get_nonzero_bits (var);
              if (nonzero_bits != -1)
                {
                  val.lattice_val = CONSTANT;
                  val.value = build_zero_cst (TREE_TYPE (var));
                  val.mask = extend_mask (nonzero_bits);
                }

extend_mask() sets all upper bits to 1 in nonzero_bits, ie, varying
in terms of bit-ccp.
I suppose in tree-ccp we need to extend mask if var is parameter since we don't
know in advance what values it will receive from different callers and mark all
upper bits as 1 to be safe.
However I suppose with ipa, we can determine exactly which bits of
parameter are constant and
setting all upper bits to 1 will become unnecessary ?

For example, consider following artificial test-case:
int f(int x)
{
  if (x > 300)
    return 1;
  else
    return 2;
}

int main(int argc, char **argv)
{
  return f(argc & 0xc) + f (argc & 0x3);
}

For x, the mask would be meet of:
<0, 0xc> meet <0, 0x3> == (0x3 | 0xc) | (0 ^ 0) == 0xf
and ipcp_update_bits() sets nonzero_bits for x to 0xf.
However get_default_value then calls extend_mask (0xf), resulting in
all upper bits
being set to 1 and consequently the condition if (x > 300) doesn't get folded.

To resolve this, I added a new flag "set_by_ipa" to decl_common,
which is set to true if the mask of parameter is determined by ipa-cp,
and the condition changes to:

if (SSA_NAME_VAR (var)
    && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
    && DECL_SET_BY_IPA (SSA_NAME_VAR (var))
  val.mask = widest_int::from (nonzero_bits,
                          TYPE_SIGN (TREE_TYPE (SSA_NAME_VAR (var)));
else
  val.mask = extend_mask (nonzero_bits);

I am not sure if adding a new flag to decl_common is a good idea. How
do other ipa passes deal with this/similar issue ?

I suppose we would want to gate this on some flag, say -fipa-bit-cp ?
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

On Thu, 4 Aug 2016, 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, 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.

Can you plase bootstrap/test the fix for this separately?  (doesn't
seem to be included in this patch btw)

> b) I chose widest_int for representing value, mask in ipcp_bits_lattice
> and correspondingly changed declarations for
> bit_value_unop_1/bit_value_binop_1 to take
> precision and sign instead of type (those are the only two fields that
> were used). Both these functions are exported by tree-ssa-ccp.h
> I hope that's ok ?

That's ok, but please change the functions to overloads of
bit_value_binop / bit_value_unop to not export ugly _1 names.

-  signop sgn = TYPE_SIGN (type);
-  int width = TYPE_PRECISION (type);
+  signop sgn = type_sgn;
+  int width = (int) type_precision;

please adjust parameter names to get rid of those now unnecessary
locals (and make the precision parameter an 'int').

> c) Changed streamer_read_wi/streamer_write_wi to non-static.
> Ah I see Kugan has submitted a patch for this, so I will drop this hunk.

But he streams wide_int, not widest_int.  I followed up on his
patch.

> d) We have following in tree-ssa-ccp.c:get_default_value ():
>           if (flag_tree_bit_ccp)
>             {
>               wide_int nonzero_bits = get_nonzero_bits (var);
>               if (nonzero_bits != -1)
>                 {
>                   val.lattice_val = CONSTANT;
>                   val.value = build_zero_cst (TREE_TYPE (var));
>                   val.mask = extend_mask (nonzero_bits);
>                 }
> 
> extend_mask() sets all upper bits to 1 in nonzero_bits, ie, varying
> in terms of bit-ccp.
> I suppose in tree-ccp we need to extend mask if var is parameter since we don't
> know in advance what values it will receive from different callers and mark all
> upper bits as 1 to be safe.

Not sure, it seems to me that we can zero-extend for unsigned types
and sign-extend for signed types (if the "sign"-bit of nonzero_bits
is one it properly makes higher bits undefined).  Can you change
the code accordingly?  (simply give extend_mask a sign-op and use
that appropriately?)  Please split out this change so it can be
tested separately.

> However I suppose with ipa, we can determine exactly which bits of
> parameter are constant and
> setting all upper bits to 1 will become unnecessary ?
> 
> For example, consider following artificial test-case:
> int f(int x)
> {
>   if (x > 300)
>     return 1;
>   else
>     return 2;
> }
> 
> int main(int argc, char **argv)
> {
>   return f(argc & 0xc) + f (argc & 0x3);
> }
> 
> For x, the mask would be meet of:
> <0, 0xc> meet <0, 0x3> == (0x3 | 0xc) | (0 ^ 0) == 0xf
> and ipcp_update_bits() sets nonzero_bits for x to 0xf.
> However get_default_value then calls extend_mask (0xf), resulting in
> all upper bits
> being set to 1 and consequently the condition if (x > 300) doesn't get folded.

But then why would the code trying to optimize the comparison look at
bits that are outside of the precision?  (where do we try to use this
info?  I see that VRP misses to use nonzero bits if no range info
is present - I suppose set_nonzero_bits misses to eventually adjust
the range.

That said, where is the folding code and why does it care for those
"uninteresting" bits at all?

> To resolve this, I added a new flag "set_by_ipa" to decl_common,
> which is set to true if the mask of parameter is determined by ipa-cp,
> and the condition changes to:
> 
> if (SSA_NAME_VAR (var)
>     && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
>     && DECL_SET_BY_IPA (SSA_NAME_VAR (var))
>   val.mask = widest_int::from (nonzero_bits,
>                           TYPE_SIGN (TREE_TYPE (SSA_NAME_VAR (var)));
> else
>   val.mask = extend_mask (nonzero_bits);
> 
> I am not sure if adding a new flag to decl_common is a good idea. How
> do other ipa passes deal with this/similar issue ?
> 
> I suppose we would want to gate this on some flag, say -fipa-bit-cp ?
> 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.

See above - we should avoid needing this.

> 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.

I see you do

@@ -895,7 +899,7 @@ do_dbg_cnt (void)
    Return TRUE when something was optimized.  */

 static bool
-ccp_finalize (bool nonzero_p)
+ccp_finalize (bool nonzero_p ATTRIBUTE_UNUSED)
 {
   bool something_changed;
   unsigned i;
@@ -913,10 +917,7 @@ ccp_finalize (bool nonzero_p)

       if (!name
          || (!POINTER_TYPE_P (TREE_TYPE (name))
-             && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
-                 /* Don't record nonzero bits before IPA to avoid
-                    using too much memory.  */
-                 || !nonzero_p)))
+             && (!INTEGRAL_TYPE_P (TREE_TYPE (name)))))
        continue;

can you instead adjust the caller to do sth like

  if (ccp_finalize (nonzero_p || flag_ipa_cp))
    {

?  What we miss to optimize memory usage in the early CCP case
(it's run very early, before dead code elimination) is to
avoid setting alignment / nonzero bits for the case of
fully propagatable (and thus dead after substitute_and_fold)
SSA names.

So in ccp_finalize do sth like

      val = get_value (name);
      if (val->lattice_val != CONSTANT
          || TREE_CODE (val->value) != INTEGER_CST
          || val->mask == 0)
        continue;

That should cut down early CCP memory use in case of nonzero
setting significantly.

I didn't look at the propagation part but eventually the IPA-CP
lattice gets quite big.  Also the alignment lattice is very
similar to the bits lattice so why not merge those two?  But
in the end it's Martins/Honzas call here.  Note there is
trailing_wide_ints <> which could be used to improve memory usage
based on the underlying type.

Thanks,
Richard.

On 4 August 2016 at 13:31, Richard Biener <rguenther@suse.de> wrote:
> On Thu, 4 Aug 2016, 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, 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.
>
> Can you plase bootstrap/test the fix for this separately?  (doesn't
> seem to be included in this patch btw)
Well I don't have the fix available -;)
>
>> b) I chose widest_int for representing value, mask in ipcp_bits_lattice
>> and correspondingly changed declarations for
>> bit_value_unop_1/bit_value_binop_1 to take
>> precision and sign instead of type (those are the only two fields that
>> were used). Both these functions are exported by tree-ssa-ccp.h
>> I hope that's ok ?
>
> That's ok, but please change the functions to overloads of
> bit_value_binop / bit_value_unop to not export ugly _1 names.
>
> -  signop sgn = TYPE_SIGN (type);
> -  int width = TYPE_PRECISION (type);
> +  signop sgn = type_sgn;
> +  int width = (int) type_precision;
>
> please adjust parameter names to get rid of those now unnecessary
> locals (and make the precision parameter an 'int').
>
>> c) Changed streamer_read_wi/streamer_write_wi to non-static.
>> Ah I see Kugan has submitted a patch for this, so I will drop this hunk.
>
> But he streams wide_int, not widest_int.  I followed up on his
> patch.
Oops, I got confused, sorry about that.
>
>> d) We have following in tree-ssa-ccp.c:get_default_value ():
>>           if (flag_tree_bit_ccp)
>>             {
>>               wide_int nonzero_bits = get_nonzero_bits (var);
>>               if (nonzero_bits != -1)
>>                 {
>>                   val.lattice_val = CONSTANT;
>>                   val.value = build_zero_cst (TREE_TYPE (var));
>>                   val.mask = extend_mask (nonzero_bits);
>>                 }
>>
>> extend_mask() sets all upper bits to 1 in nonzero_bits, ie, varying
>> in terms of bit-ccp.
>> I suppose in tree-ccp we need to extend mask if var is parameter since we don't
>> know in advance what values it will receive from different callers and mark all
>> upper bits as 1 to be safe.
>
> Not sure, it seems to me that we can zero-extend for unsigned types
> and sign-extend for signed types (if the "sign"-bit of nonzero_bits
> is one it properly makes higher bits undefined).  Can you change
> the code accordingly?  (simply give extend_mask a sign-op and use
> that appropriately?)  Please split out this change so it can be
> tested separately.
>
>> However I suppose with ipa, we can determine exactly which bits of
>> parameter are constant and
>> setting all upper bits to 1 will become unnecessary ?
>>
>> For example, consider following artificial test-case:
>> int f(int x)
>> {
>>   if (x > 300)
>>     return 1;
>>   else
>>     return 2;
>> }
>>
>> int main(int argc, char **argv)
>> {
>>   return f(argc & 0xc) + f (argc & 0x3);
>> }
>>
>> For x, the mask would be meet of:
>> <0, 0xc> meet <0, 0x3> == (0x3 | 0xc) | (0 ^ 0) == 0xf
>> and ipcp_update_bits() sets nonzero_bits for x to 0xf.
>> However get_default_value then calls extend_mask (0xf), resulting in
>> all upper bits
>> being set to 1 and consequently the condition if (x > 300) doesn't get folded.
>
> But then why would the code trying to optimize the comparison look at
> bits that are outside of the precision?  (where do we try to use this
> info?  I see that VRP misses to use nonzero bits if no range info
> is present - I suppose set_nonzero_bits misses to eventually adjust
> the range.
>
> That said, where is the folding code and why does it care for those
> "uninteresting" bits at all?
Well there is following in bit_value_binop_1 for case LT_EXPR / LE_EXPR:
        /* If the most significant bits are not known we know nothing.  */
        if (wi::neg_p (o1mask) || wi::neg_p (o2mask))
          break;

IIUC extend_mask extends all upper bits to 1, and we hit break and
thus not perform folding.
ccp2 dump shows:
Folding statement: if (x_2(D) > 300)
which is likely CONSTANT
Not folded

Instead if we extend based on signop, then the condition gets folded correctly:
Folding statement: if (x_2(D) > 300)
which is likely CONSTANT
Folding predicate x_2(D) > 300 to 0
gimple_simplified to if (0 != 0)
Folded into: if (0 != 0)

I thought it was unsafe for ccp to extend based on sign-op,
so I guarded that on DECL_SET_BY_IPA.
I will try to change extend_mask to extend the mask based on signop
and get rid of the flag.

I will address your other comments in follow-up patch.

Thanks,
Prathamesh
>
>> To resolve this, I added a new flag "set_by_ipa" to decl_common,
>> which is set to true if the mask of parameter is determined by ipa-cp,
>> and the condition changes to:
>>
>> if (SSA_NAME_VAR (var)
>>     && TREE_CODE (SSA_NAME_VAR (var)) == PARM_DECL
>>     && DECL_SET_BY_IPA (SSA_NAME_VAR (var))
>>   val.mask = widest_int::from (nonzero_bits,
>>                           TYPE_SIGN (TREE_TYPE (SSA_NAME_VAR (var)));
>> else
>>   val.mask = extend_mask (nonzero_bits);
>>
>> I am not sure if adding a new flag to decl_common is a good idea. How
>> do other ipa passes deal with this/similar issue ?
>>
>> I suppose we would want to gate this on some flag, say -fipa-bit-cp ?
>> 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.
>
> See above - we should avoid needing this.
>
>> 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.
>
> I see you do
>
> @@ -895,7 +899,7 @@ do_dbg_cnt (void)
>     Return TRUE when something was optimized.  */
>
>  static bool
> -ccp_finalize (bool nonzero_p)
> +ccp_finalize (bool nonzero_p ATTRIBUTE_UNUSED)
>  {
>    bool something_changed;
>    unsigned i;
> @@ -913,10 +917,7 @@ ccp_finalize (bool nonzero_p)
>
>        if (!name
>           || (!POINTER_TYPE_P (TREE_TYPE (name))
> -             && (!INTEGRAL_TYPE_P (TREE_TYPE (name))
> -                 /* Don't record nonzero bits before IPA to avoid
> -                    using too much memory.  */
> -                 || !nonzero_p)))
> +             && (!INTEGRAL_TYPE_P (TREE_TYPE (name)))))
>         continue;
>
> can you instead adjust the caller to do sth like
>
>   if (ccp_finalize (nonzero_p || flag_ipa_cp))
>     {
>
> ?  What we miss to optimize memory usage in the early CCP case
> (it's run very early, before dead code elimination) is to
> avoid setting alignment / nonzero bits for the case of
> fully propagatable (and thus dead after substitute_and_fold)
> SSA names.
>
> So in ccp_finalize do sth like
>
>       val = get_value (name);
>       if (val->lattice_val != CONSTANT
>           || TREE_CODE (val->value) != INTEGER_CST
>           || val->mask == 0)
>         continue;
>
> That should cut down early CCP memory use in case of nonzero
> setting significantly.
>
> I didn't look at the propagation part but eventually the IPA-CP
> lattice gets quite big.  Also the alignment lattice is very
> similar to the bits lattice so why not merge those two?  But
> in the end it's Martins/Honzas call here.  Note there is
> trailing_wide_ints <> which could be used to improve memory usage
> based on the underlying type.
>
> Thanks,
> Richard.

On 04/08/16 18:57, Prathamesh Kulkarni wrote:
> On 4 August 2016 at 13:31, Richard Biener <rguenther@suse.de> wrote:
>> On Thu, 4 Aug 2016, 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, 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.
>>
>> Can you plase bootstrap/test the fix for this separately?  (doesn't
>> seem to be included in this patch btw)
> Well I don't have the fix available -;)

This looks like what I fixed in 
https://patchwork.ozlabs.org/patch/648662/. I will commit that soon.

Thanks,
Kugan

> I didn't look at the propagation part but eventually the IPA-CP
> lattice gets quite big.  Also the alignment lattice is very
> similar to the bits lattice so why not merge those two?  But

This was always the original idea to replace alignment propagation by bitwise
ccp.  I suppose we only have issue here because nonzero bits are not tracked for
pointers so we need to feed the original lattices by hand?

We could also make use of VR ranges and bits while evaultaing predicates
in ipa-inline-analysis. I can look into it after returning from Leeds.

Honza
> in the end it's Martins/Honzas call here.  Note there is
> trailing_wide_ints <> which could be used to improve memory usage
> based on the underlying type.
> 
> Thanks,
> Richard.

Hi Honza,

On 04/08/16 23:05, Jan Hubicka wrote:
>> I didn't look at the propagation part but eventually the IPA-CP
>> lattice gets quite big.  Also the alignment lattice is very
>> similar to the bits lattice so why not merge those two?  But
>
> This was always the original idea to replace alignment propagation by bitwise
> ccp.  I suppose we only have issue here because nonzero bits are not tracked for
> pointers so we need to feed the original lattices by hand?

I also raised this one with Prathamesh off line. With the early-vrp, we 
should have nonzero_bits for non pointers. For pointers we should feed 
the lattices with get_pointer_alignment_1 as it is done in 
ipa-cpalignment propagation.

> We could also make use of VR ranges and bits while evaultaing predicates
> in ipa-inline-analysis. I can look into it after returning from Leeds.

Indeed. With ealrly dom based VRP (non iterative at this point), some of 
the ranges can be pessimistic and can impact the estimation. Let me have 
a look at this.

Thanks,
Kugan

> Hi Honza,
> 
> On 04/08/16 23:05, Jan Hubicka wrote:
> >>I didn't look at the propagation part but eventually the IPA-CP
> >>lattice gets quite big.  Also the alignment lattice is very
> >>similar to the bits lattice so why not merge those two?  But
> >
> >This was always the original idea to replace alignment propagation by bitwise
> >ccp.  I suppose we only have issue here because nonzero bits are not tracked for
> >pointers so we need to feed the original lattices by hand?
> 
> I also raised this one with Prathamesh off line. With the early-vrp,
> we should have nonzero_bits for non pointers. For pointers we should
> feed the lattices with get_pointer_alignment_1 as it is done in
> ipa-cpalignment propagation.

Yes, that is the general idea. Note that also for pointers it would be
very useful to track what pointers are non-NULL (C++ multiple inheritance inserts
a lot of NULL pointer checks that confuse us in later analysis and it would
be nice to optimize them out). I am not very convinced saving a pointer is
worth to make difference between pointers/nonpointers for all the local
tracking.
> 
> >We could also make use of VR ranges and bits while evaultaing predicates
> >in ipa-inline-analysis. I can look into it after returning from Leeds.
> 
> Indeed. With ealrly dom based VRP (non iterative at this point),
> some of the ranges can be pessimistic and can impact the estimation.
> Let me have a look at this.

Yes, but those are independent issues - size/time estimates should
take into account the new info we have and we should work on getting
it better when we can ;)

I will try to revisit the size/time code after returning from
my vacation and turn it into sreals for time + cleanup/generalize the APIs
a bit. I tried to do it last stage1 but got stuck on some of ugly side cases
+ gengtype not liking sreal type.

Honza
> 
> Thanks,
> Kugan
>

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