[PATCH][RFC] Bit CCP and pointer alignment propagation

[Richard Guenther]

On Fri, 30 Jul 2010, Paolo Bonzini wrote:

> On 07/30/2010 02:39 PM, Richard Guenther wrote:
> > > > +     case LSHIFT_EXPR:
> > > > +     case RSHIFT_EXPR:
> > > > +       if (r2val.lattice_val == CONSTANT
> > > > + 	&&  double_int_zero_p (r2val.bit_lattice_val))
> > > 
> > > Even if some bits are varying, the result will have at least r2val.value&
> > > ~r2val.bit_lattice_val bits shifted in.  So you can do something like
> > > 
> > >        if (r2val.lattice_val != CONSTANT)
> > >          break;
> > >        if (double_int_zero_p (r2val.bit_lattice_val)) {
> > >          in_mask = r1val.bit_lattice_val;
> > >          in_value = r1val.value;
> > >        } else {
> > >          in_mask = double_int_minus_one;
> > >          in_value = double_int_minus_one;
> > >        }
> > > 
> > >        shift = r2val.value&  ~r2val.bit_lattice_val;
> > >        if (SHIFT_COUNT_TRUNCATED)
> > >          shift&= GETMODE_BITSIZE (TYPE_MODE (type)) - 1;
> > > 
> > >        val.lattice_val = CONSTANT;
> > >        val.bit_lattice_val
> > > 	= double_int_lshift (in_mask, shift,
> > > 			     TYPE_PRECISION (type), false);
> > >        val.value = double_int_lshift (in_value, shift,
> > > 				     TYPE_PRECISION (type), false);
> > 
> > Hmm.  I don't quite understand.  Are you saying that only the
> > lower bits of r2val are important if SHIFT_COUNT_TRUNCATED?
> > At least we need to know the sign of the shift amount
> > to be able to tell if we're shifting in zeros from the right
> > or ones from the left.
> 
> Well, yes. :)
> 
> I wonder if using negative shift counts is just a useless complication, since
> that's what got me confused.  If you just make "shift" a positive shift count
> and test the tree code rather than the sign of shift, the code I gave above to
> handle SHIFT_COUNT_TRUNCATED magically starts to work.

I think we can have negative shift counts (at least the constant folding
code suggests so), this is why I have the code as-is.

So if we know the MSB of the shift count we can for positive
shifts shift in v & ~m zeros and drop the rest to varying.
For negative shift counts we can shift in v & ~m and drop the
rest to varying.  So your (x << (y | 8)) & 255 becomes zero
if y is known to be non-negative.

I'll add a fixme for now.

> > > > + 	  else if (shift<  0)
> > > > + 	    {
> > > > + 	      val.lattice_val = CONSTANT;
> > > > + 	      val.bit_lattice_val
> > > > + 		= double_int_rshift (r1val.bit_lattice_val,
> > > > + 				     -shift, TYPE_PRECISION (type),
> > > > true);
> > > > + 	      val.value = double_int_rshift (r1val.value, shift,
> > > > + 					     TYPE_PRECISION (type),
> > > > true);
> > > > + 	    }
> > > 
> > > Here shifted in bits are varying for signed types (unless the sign bit is
> > > constant, but that's not handled here either).
> > 
> > That should be handled fine by using an arithmetic shift for both
> > the lattice and the value.
> 
> Aha, right.
> 
> > So for varying lattice "sign" bit we
> > shift in varying.  Hm, but indeed for unsigned constants we shift
> > in the sign bit - fixed to
> > 
> >            else if (shift<  0)
> >              {
> >                val.bit_lattice_val
> >                  = double_int_rshift (r1val.bit_lattice_val,
> >                                       -shift, TYPE_PRECISION (type), true);
> 
> This should be !uns too, since for unsigned values shifted-in bits are
> constant.  But it's much more clever than I thought: if the topmost bit is
> constant, the newly computed lattice is also constant.  Very nice.
> 
> This unfortunately wouldn't work if r1val.bit_lattice_val is changed to
> in_mask as in my example above.  To handle that you could use
> 
>    msb_constant = uns || !double_bit_set_p (r1val.bit_lattice_val,
>                                             TYPE_PRECISION (type) - 1)
> 
> and then you pass !msb_constant to this right shift.  I'll let you decide
> whether it's overkill, but in any case the current clever code needs
> documentation.

Yeah, I added some.

Richard.