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

Question

Как работает маскирование веток в 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, загруженными на разных сайтах, но никаких обсуждений об этом конкретном.

12

c++cryengine loops optimization

Решение

Другие решения

Других решений пока нет …

Источник

Accepted Answer

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

Например:

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);

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

12