[PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions

[PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions

[Pedro Falcato]

Simplify ALIGN_VALUE and ALIGN_VALUE_ADDEND into simpler expressions.

ALIGN_VALUE can simply be a (value + (align - 1)) & ~align
expression, which works for any power of 2 alignment and generates
smaller code sequences. For instance:
	ALIGN_VALUE(15, 16) = (15 + 15) & ~16 = 16
	ALIGN_VALUE(16, 16) = (16 + 15) & ~16 = 16

Old codegen:
	movq    %rdi, %rax
	negq    %rax
	andl    $15, %eax
	addq    %rdi, %rax

New codegen:
	leaq    15(%rdi), %rax
	andq    $-16, %rax

ALIGN_VALUE_ADDEND can simply use a bitwise NOT of Value to get the
addend for alignment, as, for instance:
	~15 & (16 - 1) = 1
	15 + 1 = 16

This change does not necessarily affect the end result, as the GCC and
clang compilers were already able to see through things and optimize
them into optimal instruction sequences, in the ALIGN_VALUE_ADDEND case.

Cc: Michael D Kinney <michael.d.kinney@intel.com>
Cc: Liming Gao <gaoliming@byosoft.com.cn>
Cc: Zhiguang Liu <zhiguang.liu@intel.com>
Cc: Marvin Häuser <mhaeuser@posteo.de>
Signed-off-by: Pedro Falcato <pedro.falcato@gmail.com>
---

v2:
	Addressed concerns expressed on Discord by Marvin
		- Added missing parens around Alignment in ALIGN_VALUE
		- Replaced -1 with -1U, as in the other macros.

 MdePkg/Include/Base.h | 4 ++--
 1 file changed, 2 insertions(+), 2 deletions(-)

diff --git a/MdePkg/Include/Base.h b/MdePkg/Include/Base.h
index 6597e441a6e2..422f80aff53d 100644
--- a/MdePkg/Include/Base.h
+++ b/MdePkg/Include/Base.h
@@ -931,7 +931,7 @@ STATIC_ASSERT (ALIGNOF (__VERIFY_INT32_ENUM_SIZE) == sizeof (__VERIFY_INT32_ENUM
 
   @return  Addend to round Value up to alignment boundary Alignment.
 **/
-#define ALIGN_VALUE_ADDEND(Value, Alignment)  (((Alignment) - (Value)) & ((Alignment) - 1U))
+#define ALIGN_VALUE_ADDEND(Value, Alignment)  ((~(Value)) & ((Alignment) - 1U))
 
 /**
   Rounds a value up to the next boundary using a specified alignment.
@@ -945,7 +945,7 @@ STATIC_ASSERT (ALIGNOF (__VERIFY_INT32_ENUM_SIZE) == sizeof (__VERIFY_INT32_ENUM
   @return  A value up to the next boundary.
 
 **/
-#define ALIGN_VALUE(Value, Alignment)  ((Value) + ALIGN_VALUE_ADDEND (Value, Alignment))
+#define ALIGN_VALUE(Value, Alignment)  (((Value) + ((Alignment) - 1U)) & ~(Alignment))
 
 /**
   Adjust a pointer by adding the minimum offset required for it to be aligned on
-- 
2.40.1

回复: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions

[gaoliming]

Pedro:

> -----邮件原件-----
> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 Pedro Falcato
> 发送时间: 2023年5月15日 23:15
> 收件人: devel@edk2.groups.io
> 抄送: Pedro Falcato <pedro.falcato@gmail.com>; Michael D Kinney
> <michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>;
> Zhiguang Liu <zhiguang.liu@intel.com>; Marvin Häuser
> <mhaeuser@posteo.de>
> 主题: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment
> expressions
> 
> Simplify ALIGN_VALUE and ALIGN_VALUE_ADDEND into simpler expressions.
> 
> ALIGN_VALUE can simply be a (value + (align - 1)) & ~align
> expression, which works for any power of 2 alignment and generates
> smaller code sequences. For instance:
> 	ALIGN_VALUE(15, 16) = (15 + 15) & ~16 = 16
> 	ALIGN_VALUE(16, 16) = (16 + 15) & ~16 = 16
> 
> Old codegen:
> 	movq    %rdi, %rax
> 	negq    %rax
> 	andl    $15, %eax
> 	addq    %rdi, %rax
> 
> New codegen:
> 	leaq    15(%rdi), %rax
> 	andq    $-16, %rax
> 
> ALIGN_VALUE_ADDEND can simply use a bitwise NOT of Value to get the
> addend for alignment, as, for instance:
> 	~15 & (16 - 1) = 1
> 	15 + 1 = 16
> 

> 	~15 & (16 - 1) = 1
Its value should be zero, not 1. I also verify the updated ALIGN_VALUE_ADDEND. 
Its value is incorrect. Please double check. 

Thanks
Liming

> This change does not necessarily affect the end result, as the GCC and
> clang compilers were already able to see through things and optimize
> them into optimal instruction sequences, in the ALIGN_VALUE_ADDEND case.
> 
> Cc: Michael D Kinney <michael.d.kinney@intel.com>
> Cc: Liming Gao <gaoliming@byosoft.com.cn>
> Cc: Zhiguang Liu <zhiguang.liu@intel.com>
> Cc: Marvin Häuser <mhaeuser@posteo.de>
> Signed-off-by: Pedro Falcato <pedro.falcato@gmail.com>
> ---
> 
> v2:
> 	Addressed concerns expressed on Discord by Marvin
> 		- Added missing parens around Alignment in ALIGN_VALUE
> 		- Replaced -1 with -1U, as in the other macros.
> 
>  MdePkg/Include/Base.h | 4 ++--
>  1 file changed, 2 insertions(+), 2 deletions(-)
> 
> diff --git a/MdePkg/Include/Base.h b/MdePkg/Include/Base.h
> index 6597e441a6e2..422f80aff53d 100644
> --- a/MdePkg/Include/Base.h
> +++ b/MdePkg/Include/Base.h
> @@ -931,7 +931,7 @@ STATIC_ASSERT (ALIGNOF
> (__VERIFY_INT32_ENUM_SIZE) == sizeof (__VERIFY_INT32_ENUM
> 
>    @return  Addend to round Value up to alignment boundary Alignment.
>  **/
> -#define ALIGN_VALUE_ADDEND(Value, Alignment)  (((Alignment) - (Value))
> & ((Alignment) - 1U))
> +#define ALIGN_VALUE_ADDEND(Value, Alignment)  ((~(Value)) &
> ((Alignment) - 1U))
> 
>  /**
>    Rounds a value up to the next boundary using a specified alignment.
> @@ -945,7 +945,7 @@ STATIC_ASSERT (ALIGNOF
> (__VERIFY_INT32_ENUM_SIZE) == sizeof (__VERIFY_INT32_ENUM
>    @return  A value up to the next boundary.
> 
>  **/
> -#define ALIGN_VALUE(Value, Alignment)  ((Value) +
> ALIGN_VALUE_ADDEND (Value, Alignment))
> +#define ALIGN_VALUE(Value, Alignment)  (((Value) + ((Alignment) - 1U)) &
> ~(Alignment))
> 
>  /**
>    Adjust a pointer by adding the minimum offset required for it to be aligned
> on
> --
> 2.40.1
> 
> 
> 
> 
> 

Re: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions

[Pedro Falcato]

On Tue, May 16, 2023 at 2:46 AM gaoliming via groups.io
<gaoliming=byosoft.com.cn@groups.io> wrote:
>
> Pedro:
>
> > -----邮件原件-----
> > 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 Pedro Falcato
> > 发送时间: 2023年5月15日 23:15
> > 收件人: devel@edk2.groups.io
> > 抄送: Pedro Falcato <pedro.falcato@gmail.com>; Michael D Kinney
> > <michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>;
> > Zhiguang Liu <zhiguang.liu@intel.com>; Marvin Häuser
> > <mhaeuser@posteo.de>
> > 主题: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment
> > expressions
> >
> > Simplify ALIGN_VALUE and ALIGN_VALUE_ADDEND into simpler expressions.
> >
> > ALIGN_VALUE can simply be a (value + (align - 1)) & ~align
> > expression, which works for any power of 2 alignment and generates
> > smaller code sequences. For instance:
> >       ALIGN_VALUE(15, 16) = (15 + 15) & ~16 = 16
> >       ALIGN_VALUE(16, 16) = (16 + 15) & ~16 = 16
> >
> > Old codegen:
> >       movq    %rdi, %rax
> >       negq    %rax
> >       andl    $15, %eax
> >       addq    %rdi, %rax
> >
> > New codegen:
> >       leaq    15(%rdi), %rax
> >       andq    $-16, %rax
> >
> > ALIGN_VALUE_ADDEND can simply use a bitwise NOT of Value to get the
> > addend for alignment, as, for instance:
> >       ~15 & (16 - 1) = 1
> >       15 + 1 = 16
> >
>
> >       ~15 & (16 - 1) = 1
> Its value should be zero, not 1. I also verify the updated ALIGN_VALUE_ADDEND.
> Its value is incorrect. Please double check.

Hi Liming, you're 100% right. There was a mixup when we were
discussing this optimization, and I got the mental calculations wrong
there.
Two's complement is definitely what we want, as one's complement is
always off by one (from what we want).

So negation (-) works beautifully, as seen in the old codegen (we
figured this out from the compiler's output).

Sent a v3.

-- 
Pedro

Re: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions

[Marvin Häuser]

> On 16. May 2023, at 04:22, Pedro Falcato <pedro.falcato@gmail.com> wrote:
> 
> On Tue, May 16, 2023 at 2:46 AM gaoliming via groups.io
> <gaoliming=byosoft.com.cn@groups.io> wrote:
>> 
>> Pedro:
>> 
>>> -----邮件原件-----
>>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 Pedro Falcato
>>> 发送时间: 2023年5月15日 23:15
>>> 收件人: devel@edk2.groups.io
>>> 抄送: Pedro Falcato <pedro.falcato@gmail.com>; Michael D Kinney
>>> <michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>;
>>> Zhiguang Liu <zhiguang.liu@intel.com>; Marvin Häuser
>>> <mhaeuser@posteo.de>
>>> 主题: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment
>>> expressions
>>> 
>>> Simplify ALIGN_VALUE and ALIGN_VALUE_ADDEND into simpler expressions.
>>> 
>>> ALIGN_VALUE can simply be a (value + (align - 1)) & ~align
>>> expression, which works for any power of 2 alignment and generates
>>> smaller code sequences. For instance:
>>>      ALIGN_VALUE(15, 16) = (15 + 15) & ~16 = 16
>>>      ALIGN_VALUE(16, 16) = (16 + 15) & ~16 = 16
>>> 
>>> Old codegen:
>>>      movq    %rdi, %rax
>>>      negq    %rax
>>>      andl    $15, %eax
>>>      addq    %rdi, %rax
>>> 
>>> New codegen:
>>>      leaq    15(%rdi), %rax
>>>      andq    $-16, %rax
>>> 
>>> ALIGN_VALUE_ADDEND can simply use a bitwise NOT of Value to get the
>>> addend for alignment, as, for instance:
>>>      ~15 & (16 - 1) = 1
>>>      15 + 1 = 16
>>> 
>> 
>>>      ~15 & (16 - 1) = 1
>> Its value should be zero, not 1. I also verify the updated ALIGN_VALUE_ADDEND.
>> Its value is incorrect. Please double check.
> 
> Hi Liming, you're 100% right. There was a mixup when we were
> discussing this optimization, and I got the mental calculations wrong
> there.
> Two's complement is definitely what we want, as one's complement is
> always off by one (from what we want).
> 
> So negation (-) works beautifully, as seen in the old codegen (we
> figured this out from the compiler's output).

To be clear on the maths side of things:

“& (Alignment - 1U)” is equivalent to “mod Alignment” for powers of two.
“-Value” is equivalent to “2^N - Value” once the expression is promoted to an unsigned type, where N is the precision of said type.

So, the old expression basically was “(Alignment - Value) mod Alignment” and the new expression is “(2^N - Value) mod Alignment”. By modulo laws, we can apply the mod to the operands, which for the left ones gives us “Alignment mod Alignment = 0” and “2^N mod Alignment = 0”, obviously for Alignment being a power of two. They’re trivially equivalent.

If you want a more technical explanation - previously, only the lower “Alignment - 1” Bits of the result were considered. As they are 0 for Alignment, the left operand, basically you get:

Result = (Alignment - Value) & (Alignment - 1) = (Alignment - Value)[0 : Alignment - 1] = (Alignment[0 : Alignment - 1] - Value[0 : Alignment - 1])[…] = (0 - Value[…])[…]

As you can see, only the lower Alignment -1 Bits of both operands matter and they are always equal for Alignment and 0.

Best regards,
Marvin

> 
> Sent a v3.
> 
> -- 
> Pedro

Re: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions

[Marvin Häuser]

[-- Attachment #1: Type: text/plain, Size: 4172 bytes --]



> On 16. May 2023, at 09:18, Marvin Häuser <mhaeuser@posteo.de> wrote:
> 
> 
> 
>> On 16. May 2023, at 04:22, Pedro Falcato <pedro.falcato@gmail.com> wrote:
>> 
>> On Tue, May 16, 2023 at 2:46 AM gaoliming via groups.io
>> <gaoliming=byosoft.com.cn@groups.io> wrote:
>>> 
>>> Pedro:
>>> 
>>>> -----邮件原件-----
>>>> 发件人: devel@edk2.groups.io <devel@edk2.groups.io> 代表 Pedro Falcato
>>>> 发送时间: 2023年5月15日 23:15
>>>> 收件人: devel@edk2.groups.io
>>>> 抄送: Pedro Falcato <pedro.falcato@gmail.com>; Michael D Kinney
>>>> <michael.d.kinney@intel.com>; Liming Gao <gaoliming@byosoft.com.cn>;
>>>> Zhiguang Liu <zhiguang.liu@intel.com>; Marvin Häuser
>>>> <mhaeuser@posteo.de>
>>>> 主题: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment
>>>> expressions
>>>> 
>>>> Simplify ALIGN_VALUE and ALIGN_VALUE_ADDEND into simpler expressions.
>>>> 
>>>> ALIGN_VALUE can simply be a (value + (align - 1)) & ~align
>>>> expression, which works for any power of 2 alignment and generates
>>>> smaller code sequences. For instance:
>>>>     ALIGN_VALUE(15, 16) = (15 + 15) & ~16 = 16
>>>>     ALIGN_VALUE(16, 16) = (16 + 15) & ~16 = 16
>>>> 
>>>> Old codegen:
>>>>     movq    %rdi, %rax
>>>>     negq    %rax
>>>>     andl    $15, %eax
>>>>     addq    %rdi, %rax
>>>> 
>>>> New codegen:
>>>>     leaq    15(%rdi), %rax
>>>>     andq    $-16, %rax
>>>> 
>>>> ALIGN_VALUE_ADDEND can simply use a bitwise NOT of Value to get the
>>>> addend for alignment, as, for instance:
>>>>     ~15 & (16 - 1) = 1
>>>>     15 + 1 = 16
>>>> 
>>> 
>>>>     ~15 & (16 - 1) = 1
>>> Its value should be zero, not 1. I also verify the updated ALIGN_VALUE_ADDEND.
>>> Its value is incorrect. Please double check.
>> 
>> Hi Liming, you're 100% right. There was a mixup when we were
>> discussing this optimization, and I got the mental calculations wrong
>> there.
>> Two's complement is definitely what we want, as one's complement is
>> always off by one (from what we want).
>> 
>> So negation (-) works beautifully, as seen in the old codegen (we
>> figured this out from the compiler's output).
> 
> To be clear on the maths side of things:
> 
> “& (Alignment - 1U)” is equivalent to “mod Alignment” for powers of two.
> “-Value” is equivalent to “2^N - Value” once the expression is promoted to an unsigned type, where N is the precision of said type.
> 
> So, the old expression basically was “(Alignment - Value) mod Alignment” and the new expression is “(2^N - Value) mod Alignment”. By modulo laws, we can apply the mod to the operands, which for the left ones gives us “Alignment mod Alignment = 0” and “2^N mod Alignment = 0”, obviously for Alignment being a power of two. They’re trivially equivalent.

Sorry, I have to add a correction here. This assumes that 2^N >= Alignment, which somehow I took for granted, but by removing Alignment from the expression, -Value will have the precision of Value rather than the higher precision out of {Alignment, Value}, which silently changes the semantics of N and thus 2^N. For Alignment > 2^(precision of Value), this will indeed not work.

Both current issues would be resolved by some mechanism to type-promote on demand. I.e. if for ALIGN_VALUE, the sub-expression (Alignment - 1U) in ~(Alignment - 1U) was promoted to the precision of Value, and for ALIGN_VALUE_ADDEND, the sub-expression Value in -Value was promoted to the precision of Alignment, both would be correct.

Best regards,
Marvin.

> 
> If you want a more technical explanation - previously, only the lower “Alignment - 1” Bits of the result were considered. As they are 0 for Alignment, the left operand, basically you get:
> 
> Result = (Alignment - Value) & (Alignment - 1) = (Alignment - Value)[0 : Alignment - 1] = (Alignment[0 : Alignment - 1] - Value[0 : Alignment - 1])[…] = (0 - Value[…])[…]
> 
> As you can see, only the lower Alignment -1 Bits of both operands matter and they are always equal for Alignment and 0.
> 
> Best regards,
> Marvin
> 
>> 
>> Sent a v3.
>> 
>> -- 
>> Pedro


[-- Attachment #2: Type: text/html, Size: 15175 bytes --]