char*, aliasing and writing efficient code

["Peter A. Felvegi" <petschy at praire-chicken dot com>]

Hello,

recently, when writing a serializer for integers using variable length 
encoding, I noticed several inefficiencies in the generated code, the 
most severe being the reloading of the target ptr from the reference 
after each store. This lead to reading about all the aliasing rules, 
especially about char* aliasing _everything_. Now I understand why the 
compiler generated the code the way it did, but I'd like to know whether 
there is a way to tell it that 'I know what I'm doing and even though 
it's a char*, it doesn't alias anything' ?

This has a severe inpact on the generated code. If the dst ptr is passed 
via a reference (to be able to return the new value after a variable 
number of bytes were written), the ptr is reloaded after each store. 
This means the ptr is aliasing its own reference, which, for me sounds 
like stupid, but rules are rules. If I pass a stream object, with the 
dst and the end ptrs, then both will be reloaded after each store, 
moreover, the updates to the dst will not be amortized to a single 
update at the end.

Attached a little test case. Compiling with 4.8/4.9, -O3, the same 
functions for uint8 and uint16 are quite different, because for uint8, 
the 'unsigned char* aliases everything' rule kicks in. Adding 
__restrict__ to the ptr type doesn't help.

The issues in detail:

#1 dead stores are not eliminated:
(gdb) disassemble dead_store3_u8
Dump of assembler code for function dead_store3_u8(unsigned char*&):
   0x0000000000400710 <+0>:    mov    (%rdi),%rax
   0x0000000000400713 <+3>:    movb   $0x0,(%rax)
   0x0000000000400716 <+6>:    mov    (%rdi),%rax
   0x0000000000400719 <+9>:    movb   $0x1,(%rax)
   0x000000000040071c <+12>:    mov    (%rdi),%rax
   0x000000000040071f <+15>:    movb   $0x2,(%rax)
   0x0000000000400722 <+18>:    mov    (%rdi),%rax
   0x0000000000400725 <+21>:    movb   $0x3,(%rax)
   0x0000000000400728 <+24>:    retq

vs the 'short' version: only the last store is generated:
(gdb) disassemble dead_store3_u16
Dump of assembler code for function dead_store3_u16(unsigned short*&):
   0x00000000004007b0 <+0>:    mov    (%rdi),%rax
   0x00000000004007b3 <+3>:    mov    $0x3,%edx
   0x00000000004007b8 <+8>:    mov    %dx,(%rax)
   0x00000000004007bb <+11>:    retq

#2 reloading the variables
(gdb) disassemble write_v1v2_incstrm_u8
Dump of assembler code for function 
write_v1v2_incstrm_u8(OutputStream<unsigned char>&, unsigned char, 
unsigned char):
   0x0000000000400590 <+0>:    mov    0x8(%rdi),%rax
   0x0000000000400594 <+4>:    lea    0x1(%rax),%rcx
   0x0000000000400598 <+8>:    mov    %rcx,0x8(%rdi)
   0x000000000040059c <+12>:    mov    %sil,(%rax)
   0x000000000040059f <+15>:    mov    0x8(%rdi),%rax
   0x00000000004005a3 <+19>:    lea    0x1(%rax),%rcx
   0x00000000004005a7 <+23>:    mov    %rcx,0x8(%rdi)
   0x00000000004005ab <+27>:    mov    %dl,(%rax)
   0x00000000004005ad <+29>:    retq

with an end ptr check, the effect is more severe, as both members are 
reloaded, and cur is stored multiple times (+31, +48):
(gdb) disassemble write_v1v2_chkincstrm_u8
Dump of assembler code for function 
write_v1v2_chkincstrm_u8(OutputStream<unsigned char>&, unsigned char, 
unsigned char):
   0x00000000004005b0 <+0>:    mov    0x10(%rdi),%r8
   0x00000000004005b4 <+4>:    mov    0x8(%rdi),%rcx
   0x00000000004005b8 <+8>:    cmp    %rcx,%r8
   0x00000000004005bb <+11>:    jbe    0x4005c8 
<write_v1v2_chkincstrm_u8(OutputStream<unsigned char>&, unsigned char, 
unsigned char)+24>
   0x00000000004005bd <+13>:    mov    %sil,(%rcx)
   0x00000000004005c0 <+16>:    mov    0x8(%rdi),%rcx
   0x00000000004005c4 <+20>:    mov    0x10(%rdi),%r8
   0x00000000004005c8 <+24>:    lea    0x1(%rcx),%rax
   0x00000000004005cc <+28>:    cmp    %r8,%rax
   0x00000000004005cf <+31>:    mov    %rax,0x8(%rdi)
   0x00000000004005d3 <+35>:    jae    0x4005dc 
<write_v1v2_chkincstrm_u8(OutputStream<unsigned char>&, unsigned char, 
unsigned char)+44>
   0x00000000004005d5 <+37>:    mov    %dl,0x1(%rcx)
   0x00000000004005d8 <+40>:    mov    0x8(%rdi),%rax
   0x00000000004005dc <+44>:    add    $0x1,%rax
   0x00000000004005e0 <+48>:    mov    %rax,0x8(%rdi)
   0x00000000004005e4 <+52>:    retq

vs the 'short' version:
(gdb) disassemble write_v1v2_incstrm_u16
Dump of assembler code for function 
write_v1v2_incstrm_u16(OutputStream<unsigned short>&, unsigned short, 
unsigned short):
   0x0000000000400650 <+0>:    mov    0x8(%rdi),%rax
   0x0000000000400654 <+4>:    lea    0x4(%rax),%rcx
   0x0000000000400658 <+8>:    mov    %si,(%rax)
   0x000000000040065b <+11>:    mov    %rcx,0x8(%rdi)
   0x000000000040065f <+15>:    mov    %dx,0x2(%rax)
   0x0000000000400663 <+19>:    retq
cur, end loaded only once, cur written only once, aggregating the two 
++'s. this is fine.

(gdb) disassemble write_v1v2_chkincstrm_u16
Dump of assembler code for function 
write_v1v2_chkincstrm_u16(OutputStream<unsigned short>&, unsigned short, 
unsigned short):
   0x0000000000400670 <+0>:    mov    0x10(%rdi),%r8
   0x0000000000400674 <+4>:    mov    0x8(%rdi),%rax
   0x0000000000400678 <+8>:    cmp    %rax,%r8
   0x000000000040067b <+11>:    jbe    0x400680 
<write_v1v2_chkincstrm_u16(OutputStream<unsigned short>&, unsigned 
short, unsigned short)+16>
   0x000000000040067d <+13>:    mov    %si,(%rax)
   0x0000000000400680 <+16>:    lea    0x2(%rax),%rcx
   0x0000000000400684 <+20>:    cmp    %rcx,%r8
   0x0000000000400687 <+23>:    mov    %rcx,0x8(%rdi)
   0x000000000040068b <+27>:    jbe    0x400691 
<write_v1v2_chkincstrm_u16(OutputStream<unsigned short>&, unsigned 
short, unsigned short)+33>
   0x000000000040068d <+29>:    mov    %dx,0x2(%rax)
   0x0000000000400691 <+33>:    add    $0x4,%rax
   0x0000000000400695 <+37>:    mov    %rax,0x8(%rdi)
   0x0000000000400699 <+41>:    retq
No multiple loads, but cur is stored twice, at +23 and +37. Is this a bug?

My major question is, given the char* aliasing rules, how can one write 
efficient code (serializer, compressior, decompressor, etc) that writes 
bytes, without all the artifacts listed above? In my varint encoder, I 
dodged the multiple reloads by passing the ptrs as args, and using 
template metaprogramming to calculate the offsets and the increment. 
This worked for my specific case, but it's quite some effort and can't 
be applied everywhere. Is there a generic solution? An attribute? A builtin?

Thanks, Peter

----8<----8<----8<----
template<typename T>
struct OutputStream
{
    void Wr(T v)
    {
        *cur = v;
    }

    void WrInc(T v)
    {
        *cur++ = v;
    }

    void WrChk(T v)
    {
        if (cur < end) {
            *cur = v;
        }
    }

    void WrChkInc(T v)
    {
        if (cur < end) {
            *cur = v;
        }
        ++cur;
    }

private:
    T*        beg;
    T*        cur;
    T*        end;
};

template<typename T>
struct InputStream
{
    T Rd()
    {
        return *cur;
    }

    T RdInc()
    {
        return *cur++;
    }

    T RdChk()
    {
        return cur < end ? *cur : 0;
    }

    T RdChkInc()
    {
        T r = cur < end ? *cur : 0;
        ++cur;
        return r;
    }

private:
    const T*    beg;
    const T*    cur;
    const T*    end;
};
///////////////////////////////////////////////////////////////////////////////
template<typename T>
inline
void write_v_ptr(T* p, T v)
{
    *p = v;
}

template<typename T>
inline
T read_v_ptr(const T* p)
{
    return *p;
}
///////////////////////////////////////////////////////////////////////////////
template<typename T>
void write_v1v2_incref(T*& p, T v1, T v2)
{
    write_v_ptr(p, v1);
    ++p;
    write_v_ptr(p, v2);
    ++p;
}

template<typename T>
T read_v1v2_incref(const T*& p)
{
    T v1 = read_v_ptr(p);
    ++p;
    T v2 = read_v_ptr(p);
    ++p;
    return v1 + v2;
}
///////////////////////////////////////////////////////////////////////////////
template<typename T>
void write_v1v2_incstrm(OutputStream<T>& s, T v1, T v2)
{
    s.WrInc(v1);
    s.WrInc(v2);
}

template<typename T>
void write_v1v2_chkincstrm(OutputStream<T>& s, T v1, T v2)
{
    s.WrChkInc(v1);
    s.WrChkInc(v2);
}

template<typename T>
T read_v1v2_incstrm(InputStream<T>& s)
{
    T v1 = s.RdInc();
    T v2 = s.RdInc();
    return v1 + v2;
}

template<typename T>
T read_v1v2_chkincstrm(InputStream<T>& s)
{
    T v1 = s.RdChkInc();
    T v2 = s.RdChkInc();
    return v1 + v2;
}
///////////////////////////////////////////////////////////////////////////////
template<typename T>
void dead_store(T* p)
{
    *p = 0;
    *p = 1;
    *p = 2;
    *p = 3;
}

template<typename T>
void dead_store2(T** p)
{
    **p = 0;
    **p = 1;
    **p = 2;
    **p = 3;
}

template<typename T>
void dead_store3(T*& __restrict__ p)
{
    *p = 0;
    *p = 1;
    *p = 2;
    *p = 3;
}

template<typename T>
void dead_store4(OutputStream<T>& s)
{
    s.Wr(0);
    s.Wr(1);
    s.Wr(2);
    s.Wr(3);
}

template<typename T>
void dead_store5(OutputStream<T>& s)
{
    s.WrChk(0);
    s.WrChk(1);
    s.WrChk(2);
    s.WrChk(3);
}
///////////////////////////////////////////////////////////////////////////////
void write_v1v2_incref_u8(unsigned char*& p, unsigned char v1, unsigned 
char v2)
{
    write_v1v2_incref<unsigned char>(p, v1, v2);
}

void write_v1v2_incstrm_u8(OutputStream<unsigned char>& s, unsigned char 
v1, unsigned char v2)
{
    write_v1v2_incstrm<unsigned char>(s, v1, v2);
}

void write_v1v2_chkincstrm_u8(OutputStream<unsigned char>& s, unsigned 
char v1, unsigned char v2)
{
    write_v1v2_chkincstrm<unsigned char>(s, v1, v2);
}

unsigned char read_v1v2_incref_u8(const unsigned char*& p)
{
    return read_v1v2_incref<unsigned char>(p);
}

unsigned char read_v1v2_incstrm_u8(InputStream<unsigned char>& s)
{
    return read_v1v2_incstrm<unsigned char>(s);
}
///////////////////////////////////////////////////////////////////////////////
void write_v1v2_incref_u16(unsigned short*& p, unsigned short v1, 
unsigned short v2)
{
    write_v1v2_incref<unsigned short>(p, v1, v2);
}

void write_v1v2_incstrm_u16(OutputStream<unsigned short>& s, unsigned 
short v1, unsigned short v2)
{
    write_v1v2_incstrm<unsigned short>(s, v1, v2);
}

void write_v1v2_chkincstrm_u16(OutputStream<unsigned short>& s, unsigned 
short v1, unsigned short v2)
{
    write_v1v2_chkincstrm<unsigned short>(s, v1, v2);
}

unsigned short read_v1v2_incref_u16(const unsigned short*& p)
{
    return read_v1v2_incref<unsigned short>(p);
}

unsigned short read_v1v2_incstrm_u16(InputStream<unsigned short>& s)
{
    return read_v1v2_incstrm<unsigned short>(s);
}
///////////////////////////////////////////////////////////////////////////////
void dead_store_u8(unsigned char* p)
{
    dead_store<unsigned char>(p);
}

void dead_store2_u8(unsigned char** p)
{
    dead_store2<unsigned char>(p);
}

void dead_store3_u8(unsigned char*& p)
{
    dead_store3<unsigned char>(p);
}

void dead_store4_u8(OutputStream<unsigned char>& s)
{
    dead_store4<unsigned char>(s);
}

void dead_store5_u8(OutputStream<unsigned char>& s)
{
    dead_store5<unsigned char>(s);
}
///////////////////////////////////////////////////////////////////////////////
void dead_store_u16(unsigned short* p)
{
    dead_store<unsigned short>(p);
}

void dead_store2_u16(unsigned short** p)
{
    dead_store2<unsigned short>(p);
}

void dead_store3_u16(unsigned short*& p)
{
    dead_store3<unsigned short>(p);
}

void dead_store4_u16(OutputStream<unsigned short>& s)
{
    dead_store4<unsigned short>(s);
}

void dead_store5_u16(OutputStream<unsigned short>& s)
{
    dead_store5<unsigned short>(s);
}
///////////////////////////////////////////////////////////////////////////////

int main()
{
}