Как работает маскирование веток в CryENGINE 3?

Эта часть заголовков CryENGINE SDK привлекла мое внимание:

branchmask.h

#ifndef __BRANCHLESS_MASK__
#define __BRANCHLESS_MASK__

///////////////////////////////////////////
// helper functions for branch elimination
//
// msb/lsb - most/less significant byte
//
// mask - 0xFFFFFFFF
// nz   - not zero
// zr   - is zero

ILINE const uint32 nz2msb(const uint32 x)
{
    return -(int32)x | x;
}

ILINE const uint32 msb2mask(const uint32 x)
{
    return (int32)(x) >> 31;
}

ILINE const uint32 nz2one(const uint32 x)
{
    return nz2msb(x) >> 31; // int((bool)x);
}

ILINE const uint32 nz2mask(const uint32 x)
{
    return (int32)msb2mask(nz2msb(x)); // -(int32)(bool)x;
}


ILINE const uint32 iselmask(const uint32 mask, uint32 x, const uint32 y)// select integer with mask (0xFFFFFFFF or 0x0 only!!!)
{
    return (x & mask) | (y & ~mask);
}


ILINE const uint32 mask_nz_nz(const uint32 x, const uint32 y)// mask if( x != 0 && y != 0)
{
    return msb2mask(nz2msb(x) & nz2msb(y));
}

ILINE const uint32 mask_nz_zr(const uint32 x, const uint32 y)// mask if( x != 0 && y == 0)
{
    return msb2mask(nz2msb(x) & ~nz2msb(y));
}


ILINE const uint32 mask_zr_zr(const uint32 x, const uint32 y)// mask if( x == 0 && y == 0)
{
    return ~nz2mask(x | y);
}

#endif//__BRANCHLESS_MASK__

Может кто-нибудь бросить краткое объяснение, как именно эти функции предназначены для сокращения ветвей? ILINE Я предполагаю, что это предопределенная сила, встроенная или что-то в этом роде. Я искал Google об этом, но все, что я нашел, это копии заголовков CryENGINE, загруженных на разных сайтах, но никаких обсуждений об этом конкретном не было.

Ответы

Ответ 1

Эти функции возвращают бит-маски, которые могут быть получены с результатами других вычислений, для выполнения операций без условных выражений и, таким образом, без введения ветвей.

Например:

  • nz2mask возвращает 0, если аргумент 0 и 0xffffffff в противном случае.
  • msb2mask возвращает 0, если верхний бит аргумента 0 и 0xffffffff, если он 1.

Итак, если у вас есть код (с инструкциями x86 для справки):

if(a != 0) x += y;
    //  test        ebx,ebx  
    //  je          skip  
    //  add         dword ptr [x],eax  
    // skip:

Вы можете заменить его на:

x += y & (nz2mask(a));
    //  mov     ecx,ebx  
    //  neg     ecx  
    //  or      ecx,ebx  
    //  sar     ecx,1Fh  
    //  and     ecx,eax  
    //  add     ecx,dword ptr [x]

Он создает больше инструкций (по крайней мере, на x86), но избегает ветки.

Затем есть дополнительные функции, такие как iselmask(), которые позволяют выбирать любой вход на основе маски, поэтому вы можете заменить:

x = (a != 0) ? r1 : r2;

с

x = iselmask(nz2mask(a), r1, r2);

Опять же, эти функции должны встроить и скомпилировать до относительно эффективного ассемблера, торгуя с лишним математическими вычислениями без ветвления.