tile: Fix up corner cases with signed relocations

Some types of relocations technically need to be signed rather than
unsigned: in particular ones that are used with moveli or movei,
or for jump and branch.  This is almost never a problem.  Jump and
branch opcodes are pretty much uniformly resolved by the static linker
(unless you omit -fpic for a shared library, which is not recommended).
The moveli and movei opcodes that need to be sign-extended generally
are for positive displacements, like the construction of the address of
main() from _start().  However, tst-pie1 ends up with main below _start
(in a different module) and the test failed due to signedness issues in
relocation handling.

This commit treats the value as signed when shifting (to preserve the
high bit) and also sign-extends the value generated from the updated
bundle when comparing with the desired bundle, which we do to make sure
no overflow occurred.  As a result, the tst-pie1 test now passes.
---
 sysdeps/tile/dl-machine.h |   40 ++++++++++++++++++++++------------------
 1 files changed, 22 insertions(+), 18 deletions(-)

This is the change I wanted to push before 2.20 froze.  It turns out
not to be a regression, so arguably the conservative thing may to wait
until after 2.21 opens.  I've done reasonable internal testing (and
will have more results by Saturday morning after a full rebuild and
test suite run) but could easily be swayed one way or the other.

Chris Metcalf <cmetcalf@tilera.com> writes:

> @@ -686,13 +686,17 @@ elf_machine_rela (struct link_map *map, const ElfW(Rela) *reloc,
>    tile_bundle_bits *p = (tile_bundle_bits *) reloc_addr;
>    tile_bundle_bits bits = *p;
>  
> -#define MUNGE(func) do {                                            \
> +#define MUNGE_SIGNED(func, length) do {                             \
>      bits = ((bits & ~create_##func (-1)) | create_##func (value));  \
> -    if (get_##func (bits) != value)                                 \
> +    ElfW(Addr) result = (long) get_##func (bits)                    \
> +      << (__WORDSIZE - length) >> (__WORDSIZE - length);            \

Left shifting a negative value has undefined value.

Andreas.

On 9/5/2014 4:33 PM, Andreas Schwab wrote:
> Chris Metcalf <cmetcalf@tilera.com> writes:
>
>> @@ -686,13 +686,17 @@ elf_machine_rela (struct link_map *map, const ElfW(Rela) *reloc,
>>     tile_bundle_bits *p = (tile_bundle_bits *) reloc_addr;
>>     tile_bundle_bits bits = *p;
>>   
>> -#define MUNGE(func) do {                                            \
>> +#define MUNGE_SIGNED(func, length) do {                             \
>>       bits = ((bits & ~create_##func (-1)) | create_##func (value));  \
>> -    if (get_##func (bits) != value)                                 \
>> +    ElfW(Addr) result = (long) get_##func (bits)                    \
>> +      << (__WORDSIZE - length) >> (__WORDSIZE - length);            \
> Left shifting a negative value has undefined value.

The shift is always a non-negative value less than __WORDSIZE here, by intention.  Are you seeing something I'm missing?

Chris Metcalf <cmetcalf@tilera.com> writes:

> On 9/5/2014 4:33 PM, Andreas Schwab wrote:
>> Chris Metcalf <cmetcalf@tilera.com> writes:
>>
>>> @@ -686,13 +686,17 @@ elf_machine_rela (struct link_map *map, const ElfW(Rela) *reloc,
>>>     tile_bundle_bits *p = (tile_bundle_bits *) reloc_addr;
>>>     tile_bundle_bits bits = *p;
>>>   -#define MUNGE(func) do {
>>> \
>>> +#define MUNGE_SIGNED(func, length) do {                             \
>>>       bits = ((bits & ~create_##func (-1)) | create_##func (value));  \
>>> -    if (get_##func (bits) != value)                                 \
>>> +    ElfW(Addr) result = (long) get_##func (bits)                    \
>>> +      << (__WORDSIZE - length) >> (__WORDSIZE - length);            \
>> Left shifting a negative value has undefined value.
>
> The shift is always a non-negative value less than __WORDSIZE here, by intention.  Are you seeing something I'm missing?

I'm talking about the value, not the shift amount.

Andreas.

On Fri, Sep 05, 2014 at 11:40:20PM +0200, Andreas Schwab wrote:
> Chris Metcalf <cmetcalf@tilera.com> writes:
> 
> > On 9/5/2014 4:33 PM, Andreas Schwab wrote:
> >> Chris Metcalf <cmetcalf@tilera.com> writes:
> >>
> >>> @@ -686,13 +686,17 @@ elf_machine_rela (struct link_map *map, const ElfW(Rela) *reloc,
> >>>     tile_bundle_bits *p = (tile_bundle_bits *) reloc_addr;
> >>>     tile_bundle_bits bits = *p;
> >>>   -#define MUNGE(func) do {
> >>> \
> >>> +#define MUNGE_SIGNED(func, length) do {                             \
> >>>       bits = ((bits & ~create_##func (-1)) | create_##func (value));  \
> >>> -    if (get_##func (bits) != value)                                 \
> >>> +    ElfW(Addr) result = (long) get_##func (bits)                    \
> >>> +      << (__WORDSIZE - length) >> (__WORDSIZE - length);            \
> >> Left shifting a negative value has undefined value.
> >
> > The shift is always a non-negative value less than __WORDSIZE
> > here, by intention. Are you seeing something I'm missing?
> 
> I'm talking about the value, not the shift amount.

In general, this issue should always be solvable, in cases where
overflow won't happen, by replacing a<<b with a*(1<<b).

Rich

On 9/5/2014 5:40 PM, Andreas Schwab wrote:
>> On 9/5/2014 4:33 PM, Andreas Schwab wrote:
>>> Chris Metcalf <cmetcalf@tilera.com> writes:
>>>
>>>> @@ -686,13 +686,17 @@ elf_machine_rela (struct link_map *map, const ElfW(Rela) *reloc,
>>>>      tile_bundle_bits *p = (tile_bundle_bits *) reloc_addr;
>>>>      tile_bundle_bits bits = *p;
>>>>    -#define MUNGE(func) do {
>>>> \
>>>> +#define MUNGE_SIGNED(func, length) do {                             \
>>>>        bits = ((bits & ~create_##func (-1)) | create_##func (value));  \
>>>> -    if (get_##func (bits) != value)                                 \
>>>> +    ElfW(Addr) result = (long) get_##func (bits)                    \
>>>> +      << (__WORDSIZE - length) >> (__WORDSIZE - length);            \
>>> Left shifting a negative value has undefined value.
>>>
> I'm talking about the value, not the shift amount.

Right, sorry.  On tile, the compiler will always generate a "shli" for shifting an unknown value by a known constant, and shli is defined with unsigned semantics on tile, so in practice this code generates the correct value.

That said, you're right that we're better off to avoid relying on undefined behavior, so, thanks.  I've changed that part of the code to look like:

     ElfW(Addr) result = get_##func (bits); \
     int signbits = __WORDSIZE - length; \
     result = (long) (result << signbits) >> signbits;               \

I'll go ahead and push the commit with that change.

On Sat, 6 Sep 2014, Chris Metcalf wrote:

> Right, sorry.  On tile, the compiler will always generate a "shli" for
> shifting an unknown value by a known constant, and shli is defined with
> unsigned semantics on tile, so in practice this code generates the correct
> value.

In any case, the GNU C language defines signed shifts (as long as the 
shift amount is >= 0 and < width of type), although it may still be useful 
to avoid the cases that are outside what ISO C defines.

On Mon, Sep 08, 2014 at 03:20:59PM +0000, Joseph S. Myers wrote:
> On Sat, 6 Sep 2014, Chris Metcalf wrote:
> 
> > Right, sorry.  On tile, the compiler will always generate a "shli" for
> > shifting an unknown value by a known constant, and shli is defined with
> > unsigned semantics on tile, so in practice this code generates the correct
> > value.
> 
> In any case, the GNU C language defines signed shifts (as long as the 
> shift amount is >= 0 and < width of type), although it may still be useful 
> to avoid the cases that are outside what ISO C defines.

I don't think this is true. For example, in many versions of GCC, this
is (rightfully!) an infinite loop:

	int i;
	for (i=1; i>0; i<<=1);

On the other hand, defining a<<b when a is negative but a*(2**b) does
not overflow makes sense, and it's frustrating that the C standard
doesn't already define this (but see my workaround, i.e. just using
*(1<<b) or similar). But defining a<<b when it would overflow is
inconsistent and unreasonable.

Rich

On Mon, 8 Sep 2014, Rich Felker wrote:

> > In any case, the GNU C language defines signed shifts (as long as the 
> > shift amount is >= 0 and < width of type), although it may still be useful 
> > to avoid the cases that are outside what ISO C defines.
> 
> I don't think this is true. For example, in many versions of GCC, this
> is (rightfully!) an infinite loop:
> 
> 	int i;
> 	for (i=1; i>0; i<<=1);

That would be a bug (I fixed such a bug ten years ago, PR 7284); please 
report it if present in trunk.  Signed shifts are documented in 
implement-c.texi; C90 makes some things implementation-defined even when 
C99/C11 make them undefined.

On Mon, Sep 08, 2014 at 03:34:18PM +0000, Joseph S. Myers wrote:
> On Mon, 8 Sep 2014, Rich Felker wrote:
> 
> > > In any case, the GNU C language defines signed shifts (as long as the 
> > > shift amount is >= 0 and < width of type), although it may still be useful 
> > > to avoid the cases that are outside what ISO C defines.
> > 
> > I don't think this is true. For example, in many versions of GCC, this
> > is (rightfully!) an infinite loop:
> > 
> > 	int i;
> > 	for (i=1; i>0; i<<=1);
> 
> That would be a bug (I fixed such a bug ten years ago, PR 7284); please 
> report it if present in trunk.  Signed shifts are documented in 
> implement-c.texi; C90 makes some things implementation-defined even when 
> C99/C11 make them undefined.

OK, yet another reason to avoid << operator: GCC intentionally fails
to optimize it right. Thankfully *(1<<y) solves that too.

As for versions where the above loop condition gets optimized out, I
don't recall which ones, but I do recall seeing it (broken configure
scripts checking the range of time_t going into an infinite loop) in
the past 3 or 4 years. But it's very possible that the users who
experienced it were using a much older version of GCC such as 3.4,
4.2, or 4.4.

Rich