* [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions @ 2023-05-15 15:14 Pedro Falcato 2023-05-16 1:46 ` 回复: [edk2-devel] " gaoliming 0 siblings, 1 reply; 5+ messages in thread From: Pedro Falcato @ 2023-05-15 15:14 UTC (permalink / raw) To: devel Cc: Pedro Falcato, Michael D Kinney, Liming Gao, Zhiguang Liu, Marvin Häuser 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 ^ permalink raw reply related [flat|nested] 5+ messages in thread
* 回复: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions 2023-05-15 15:14 [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions Pedro Falcato @ 2023-05-16 1:46 ` gaoliming 2023-05-16 2:22 ` Pedro Falcato 0 siblings, 1 reply; 5+ messages in thread From: gaoliming @ 2023-05-16 1:46 UTC (permalink / raw) To: devel, pedro.falcato Cc: 'Michael D Kinney', 'Zhiguang Liu', 'Marvin Häuser' 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 > > > > > ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions 2023-05-16 1:46 ` 回复: [edk2-devel] " gaoliming @ 2023-05-16 2:22 ` Pedro Falcato 2023-05-16 7:18 ` Marvin Häuser 0 siblings, 1 reply; 5+ messages in thread From: Pedro Falcato @ 2023-05-16 2:22 UTC (permalink / raw) To: devel, gaoliming; +Cc: Michael D Kinney, Zhiguang Liu, Marvin Häuser 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions 2023-05-16 2:22 ` Pedro Falcato @ 2023-05-16 7:18 ` Marvin Häuser 2023-05-16 9:08 ` Marvin Häuser 0 siblings, 1 reply; 5+ messages in thread From: Marvin Häuser @ 2023-05-16 7:18 UTC (permalink / raw) To: Pedro Falcato; +Cc: devel, gaoliming, Michael D Kinney, Zhiguang Liu > 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 ^ permalink raw reply [flat|nested] 5+ messages in thread
* Re: [edk2-devel] [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions 2023-05-16 7:18 ` Marvin Häuser @ 2023-05-16 9:08 ` Marvin Häuser 0 siblings, 0 replies; 5+ messages in thread From: Marvin Häuser @ 2023-05-16 9:08 UTC (permalink / raw) To: Pedro Falcato Cc: edk2-devel-groups-io, Liming Gao, Michael D Kinney, Zhiguang Liu [-- 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 --] ^ permalink raw reply [flat|nested] 5+ messages in thread
end of thread, other threads:[~2023-05-16 9:08 UTC | newest] Thread overview: 5+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2023-05-15 15:14 [PATCH v2 1/1] MdePkg/Base.h: Simply alignment expressions Pedro Falcato 2023-05-16 1:46 ` 回复: [edk2-devel] " gaoliming 2023-05-16 2:22 ` Pedro Falcato 2023-05-16 7:18 ` Marvin Häuser 2023-05-16 9:08 ` Marvin Häuser
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox