RFR: 8183390: Fix and re-enable post loop vectorization [v3]
Pengfei Li
pli at openjdk.java.net
Wed Jan 26 01:56:33 UTC 2022
On Mon, 10 Jan 2022 06:20:01 GMT, Pengfei Li <pli at openjdk.org> wrote:
>> ### Background
>>
>> Post loop vectorization is a C2 compiler optimization in an experimental
>> VM feature called PostLoopMultiversioning. It transforms the range-check
>> eliminated post loop to a 1-iteration vectorized loop with vector mask.
>> This optimization was contributed by Intel in 2016 to support x86 AVX512
>> masked vector instructions. However, it was disabled soon after an issue
>> was found. Due to insufficient maintenance in these years, multiple bugs
>> have been accumulated inside. But we (Arm) still think this is a useful
>> framework for vector mask support in C2 auto-vectorized loops, for both
>> x86 AVX512 and AArch64 SVE. Hence, we propose this to fix and re-enable
>> post loop vectorization.
>>
>> ### Changes in this patch
>>
>> This patch reworks post loop vectorization. The most significant change
>> is removing vector mask support in C2 x86 backend and re-implementing
>> it in the mid-end. With this, we can re-enable post loop vectorization
>> for platforms other than x86.
>>
>> Previous implementation hard-codes x86 k1 register as a reserved AVX512
>> opmask register and defines two routines (setvectmask/restorevectmask)
>> to set and restore the value of k1. But after [JDK-8211251](https://bugs.openjdk.java.net/browse/JDK-8211251) which encodes
>> AVX512 instructions as unmasked by default, generated vector masks are
>> no longer used in AVX512 vector instructions. To fix incorrect codegen
>> and add vector mask support for more platforms, we turn to add a vector
>> mask input to C2 mid-end IRs. Specifically, we use a VectorMaskGenNode
>> to generate a mask and replace all Load/Store nodes in the post loop
>> into LoadVectorMasked/StoreVectorMasked nodes with that mask input. This
>> IR form is exactly the same to those which are used in VectorAPI mask
>> support. For now, we only add mask inputs for Load/Store nodes because
>> we don't have reduction operations supported in post loop vectorization.
>> After this change, the x86 k1 register is no longer reserved and can be
>> allocated when PostLoopMultiversioning is enabled.
>>
>> Besides this change, we have fixed a compiler crash and five incorrect
>> result issues with post loop vectorization.
>>
>> **I) C2 crashes with segmentation fault in strip-mined loops**
>>
>> Previous implementation was done before C2 loop strip-mining was merged
>> into JDK master so it didn't take strip-mined loops into consideration.
>> In C2's strip mined loops, post loop is not the sibling of the main loop
>> in ideal loop tree. Instead, it's the sibling of the main loop's parent.
>> This patch fixed a SIGSEGV issue caused by NULL pointer when locating
>> post loop from strip-mined main loop.
>>
>> **II) Incorrect result issues with post loop vectorization**
>>
>> We have also fixed five incorrect vectorization issues. Some of them are
>> hidden deep and can only be reproduced with corner cases. These issues
>> have a common cause that it assumes the post loop can be vectorized if
>> the vectorization in corresponding main loop is successful. But in many
>> cases this assumption is wrong. Below are details.
>>
>> - **[Issue-1] Incorrect vectorization for partial vectorizable loops**
>>
>> This issue can be reproduced by below loop where only some operations in
>> the loop body are vectorizable.
>>
>> for (int i = 0; i < 10000; i++) {
>> res[i] = a[i] * b[i];
>> k = 3 * k + 1;
>> }
>>
>> In the main loop, superword can work well if parts of the operations in
>> loop body are not vectorizable since those parts can be unrolled only.
>> But for post loops, we don't create vectors through combining scalar IRs
>> generated from loop unrolling. Instead, we are doing scalars to vectors
>> replacement for all operations in the loop body. Hence, all operations
>> should be either vectorized together or not vectorized at all. To fix
>> this kind of cases, we add an extra field "_slp_vector_pack_count" in
>> CountedLoopNode to record the eventual count of vector packs in the main
>> loop. This value is then passed to post loop and compared with post loop
>> pack count. Vectorization will be bailed out in post loop if it creates
>> more vector packs than in the main loop.
>>
>> - **[Issue-2] Incorrect result in loops with growing-down vectors**
>>
>> This issue appears with growing-down vectors, that is, vectors that grow
>> to smaller memory address as the loop iterates. It can be reproduced by
>> below counting-up loop with negative scale value in array index.
>>
>> for (int i = 0; i < 10000; i++) {
>> a[MAX - i] = b[MAX - i];
>> }
>>
>> Cause of this issue is that for a growing-down vector, generated vector
>> mask value has reversed vector-lane order so it masks incorrect vector
>> lanes. Note that if negative scale value appears in counting-down loops,
>> the vector will be growing up. With this rule, we fix the issue by only
>> allowing positive array index scales in counting-up loops and negative
>> array index scales in counting-down loops. This check is done with the
>> help of SWPointer by comparing scale values in each memory access in the
>> loop with loop stride value.
>>
>> - **[Issue-3] Incorrect result in manually unrolled loops**
>>
>> This issue can be reproduced by below manually unrolled loop.
>>
>> for (int i = 0; i < 10000; i += 2) {
>> c[i] = a[i] + b[i];
>> c[i + 1] = a[i + 1] * b[i + 1];
>> }
>>
>> In this loop, operations in the 2nd statement duplicate those in the 1st
>> statement with a small memory address offset. Vectorization in the main
>> loop works well in this case because C2 does further unrolling and pack
>> combination. But we cannot vectorize the post loop through replacement
>> from scalars to vectors because it creates duplicated vector operations.
>> To fix this, we restrict post loop vectorization to loops with stride
>> values of 1 or -1.
>>
>> - **[Issue-4] Incorrect result in loops with mixed vector element sizes**
>>
>> This issue is found after we enable post loop vectorization for AArch64.
>> It's reproducible by multiple array operations with different element
>> sizes inside a loop. On x86, there is no issue because the values of x86
>> AVX512 opmasks only depend on which vector lanes are active. But AArch64
>> is different - the values of SVE predicates also depend on lane size of
>> the vector. Hence, on AArch64 SVE, if a loop has mixed vector element
>> sizes, we should use different vector masks. For now, we just support
>> loops with only one vector element size, i.e., "int + float" vectors in
>> a single loop is ok but "int + double" vectors in a single loop is not
>> vectorizable. This fix also enables subword vectors support to make all
>> primitive type array operations vectorizable.
>>
>> - **[Issue-5] Incorrect result in loops with potential data dependence**
>>
>> This issue can be reproduced by below corner case on AArch64 only.
>>
>> for (int i = 0; i < 10000; i++) {
>> a[i] = x;
>> a[i + OFFSET] = y;
>> }
>>
>> In this case, two stores in the loop have data dependence if the OFFSET
>> value is smaller than the vector length. So we cannot do vectorization
>> through replacing scalars to vectors. But the main loop vectorization
>> in this case is successful on AArch64 because AArch64 has partial vector
>> load/store support. It splits vector fill with different values in lanes
>> to several smaller-sized fills. In this patch, we add additional data
>> dependence check for this kind of cases. The check is also done with the
>> help of SWPointer class. In this check, we require that every two memory
>> accesses (with at least one store) of the same element type (or subword
>> size) in the loop has the same array index expression.
>>
>> ### Tests
>>
>> So far we have tested full jtreg on both x86 AVX512 and AArch64 SVE with
>> experimental VM option "PostLoopMultiversioning" turned on. We found no
>> issue in all tests. We notice that those existing cases are not enough
>> because some of above issues are not spotted by them. We would like to
>> add some new cases but we found existing vectorization tests are a bit
>> cumbersome - golden results must be pre-calculated and hard-coded in the
>> test code for correctness verification. Thus, in this patch, we propose
>> a new vectorization testing framework.
>>
>> Our new framework brings a simpler way to add new cases. For a new test
>> case, we only need to create a new method annotated with "@Test". The
>> test runner will invoke each annotated method twice automatically. First
>> time it runs in the interpreter and second time it's forced compiled by
>> C2. Then the two return results are compared. So in this framework each
>> test method should return a primitive value or an array of primitives.
>> In this way, no extra verification code for vectorization correctness is
>> required. This test runner is still jtreg-based and takes advantages of
>> the jtreg WhiteBox API, which enables test methods running at specific
>> compilation levels. Each test class inside is also jtreg-based. It just
>> need to inherit from the test runner class and run with two additional
>> options "-Xbootclasspath/a:." and "-XX:+WhiteBoxAPI".
>>
>> ### Summary & Future work
>>
>> In this patch, we reworked post loop vectorization. We made it platform
>> independent and fixed several issues inside. We also implemented a new
>> vectorization testing framework with many test cases inside. Meanwhile,
>> we did some code cleanups.
>>
>> This patch only touches C2 code guarded with PostLoopMultiversioning,
>> except a few data structure changes. So, there's no behavior change when
>> experimental VM option PostLoopMultiversioning is off. Also, to reduce
>> risks, we still propose to keep post loop vectorization experimental for
>> now. But if it receives positive feedback, we would like to change it to
>> non-experimental in the future.
>
> Pengfei Li has updated the pull request with a new target base due to a merge or a rebase. The incremental webrev excludes the unrelated changes brought in by the merge/rebase. The pull request contains five additional commits since the last revision:
>
> - Update copyright year and rename a function
>
> Change-Id: I15845ebd3982edebd4c151284cc6f2ff727630bb
> - Merge branch 'master' into postloop
>
> Change-Id: Ie639c79c9cf016dc68ebf2c0031b60453b45e9a4
> - Fix issues in newly added test framework
>
> Change-Id: I6e61abf05e9665325cb3abaf407360b18355c6b1
> - Merge branch 'master' into postloop
>
> Change-Id: I9bb5a808d7540426dedb141fd198d25eb1f569e6
> - 8183390: Fix and re-enable post loop vectorization
>
> ** Background
>
> Post loop vectorization is a C2 compiler optimization in an experimental
> VM feature called PostLoopMultiversioning. It transforms the range-check
> eliminated post loop to a 1-iteration vectorized loop with vector mask.
> This optimization was contributed by Intel in 2016 to support x86 AVX512
> masked vector instructions. However, it was disabled soon after an issue
> was found. Due to insufficient maintenance in these years, multiple bugs
> have been accumulated inside. But we (Arm) still think this is a useful
> framework for vector mask support in C2 auto-vectorized loops, for both
> x86 AVX512 and AArch64 SVE. Hence, we propose this to fix and re-enable
> post loop vectorization.
>
> ** Changes in this patch
>
> This patch reworks post loop vectorization. The most significant change
> is removing vector mask support in C2 x86 backend and re-implementing
> it in the mid-end. With this, we can re-enable post loop vectorization
> for platforms other than x86.
>
> Previous implementation hard-codes x86 k1 register as a reserved AVX512
> opmask register and defines two routines (setvectmask/restorevectmask)
> to set and restore the value of k1. But after JDK-8211251 which encodes
> AVX512 instructions as unmasked by default, generated vector masks are
> no longer used in AVX512 vector instructions. To fix incorrect codegen
> and add vector mask support for more platforms, we turn to add a vector
> mask input to C2 mid-end IRs. Specifically, we use a VectorMaskGenNode
> to generate a mask and replace all Load/Store nodes in the post loop
> into LoadVectorMasked/StoreVectorMasked nodes with that mask input. This
> IR form is exactly the same to those which are used in VectorAPI mask
> support. For now, we only add mask inputs for Load/Store nodes because
> we don't have reduction operations supported in post loop vectorization.
> After this change, the x86 k1 register is no longer reserved and can be
> allocated when PostLoopMultiversioning is enabled.
>
> Besides this change, we have fixed a compiler crash and five incorrect
> result issues with post loop vectorization.
>
> - 1) C2 crashes with segmentation fault in strip-mined loops
>
> Previous implementation was done before C2 loop strip-mining was merged
> into JDK master so it didn't take strip-mined loops into consideration.
> In C2's strip mined loops, post loop is not the sibling of the main loop
> in ideal loop tree. Instead, it's the sibling of the main loop's parent.
> This patch fixed a SIGSEGV issue caused by NULL pointer when locating
> post loop from strip-mined main loop.
>
> - 2) Incorrect result issues with post loop vectorization
>
> We have also fixed five incorrect vectorization issues. Some of them are
> hidden deep and can only be reproduced with corner cases. These issues
> have a common cause that it assumes the post loop can be vectorized if
> the vectorization in corresponding main loop is successful. But in many
> cases this assumption is wrong. Below are details.
>
> [Issue-1] Incorrect vectorization for partial vectorizable loops
>
> This issue can be reproduced by below loop where only some operations in
> the loop body are vectorizable.
>
> for (int i = 0; i < 10000; i++) {
> res[i] = a[i] * b[i];
> k = 3 * k + 1;
> }
>
> In the main loop, superword can work well if parts of the operations in
> loop body are not vectorizable since those parts can be unrolled only.
> But for post loops, we don't create vectors through combining scalar IRs
> generated from loop unrolling. Instead, we are doing scalars to vectors
> replacement for all operations in the loop body. Hence, all operations
> should be either vectorized together or not vectorized at all. To fix
> this kind of cases, we add an extra field "_slp_vector_pack_count" in
> CountedLoopNode to record the eventual count of vector packs in the main
> loop. This value is then passed to post loop and compared with post loop
> pack count. Vectorization will be bailed out in post loop if it creates
> more vector packs than in the main loop.
>
> [Issue-2] Incorrect result in loops with growing-down vectors
>
> This issue appears with growing-down vectors, that is, vectors that grow
> to smaller memory address as the loop iterates. It can be reproduced by
> below counting-up loop with negative scale value in array index.
>
> for (int i = 0; i < 10000; i++) {
> a[MAX - i] = b[MAX - i];
> }
>
> Cause of this issue is that for a growing-down vector, generated vector
> mask value has reversed vector-lane order so it masks incorrect vector
> lanes. Note that if negative scale value appears in counting-down loops,
> the vector will be growing up. With this rule, we fix the issue by only
> allowing positive array index scales in counting-up loops and negative
> array index scales in counting-down loops. This check is done with the
> help of SWPointer by comparing scale values in each memory access in the
> loop with loop stride value.
>
> [Issue-3] Incorrect result in manually unrolled loops
>
> This issue can be reproduced by below manually unrolled loop.
>
> for (int i = 0; i < 10000; i += 2) {
> c[i] = a[i] + b[i];
> c[i + 1] = a[i + 1] * b[i + 1];
> }
>
> In this loop, operations in the 2nd statement duplicate those in the 1st
> statement with a small memory address offset. Vectorization in the main
> loop works well in this case because C2 does further unrolling and pack
> combination. But we cannot vectorize the post loop through replacement
> from scalars to vectors because it creates duplicated vector operations.
> To fix this, we restrict post loop vectorization to loops with stride
> values of 1 or -1.
>
> [Issue-4] Incorrect result in loops with mixed vector element sizes
>
> This issue is found after we enable post loop vectorization for AArch64.
> It's reproducible by multiple array operations with different element
> sizes inside a loop. On x86, there is no issue because the values of x86
> AVX512 opmasks only depend on which vector lanes are active. But AArch64
> is different - the values of SVE predicates also depend on lane size of
> the vector. Hence, on AArch64 SVE, if a loop has mixed vector element
> sizes, we should use different vector masks. For now, we just support
> loops with only one vector element size, i.e., "int + float" vectors in
> a single loop is ok but "int + double" vectors in a single loop is not
> vectorizable. This fix also enables subword vectors support to make all
> primitive type array operations vectorizable.
>
> [Issue-5] Incorrect result in loops with potential data dependence
>
> This issue can be reproduced by below corner case on AArch64 only.
>
> for (int i = 0; i < 10000; i++) {
> a[i] = x;
> a[i + OFFSET] = y;
> }
>
> In this case, two stores in the loop have data dependence if the OFFSET
> value is smaller than the vector length. So we cannot do vectorization
> through replacing scalars to vectors. But the main loop vectorization
> in this case is successful on AArch64 because AArch64 has partial vector
> load/store support. It splits vector fill with different values in lanes
> to several smaller-sized fills. In this patch, we add additional data
> dependence check for this kind of cases. The check is also done with the
> help of SWPointer class. In this check, we require that every two memory
> accesses (with at least one store) of the same element type (or subword
> size) in the loop has the same array index expression.
>
> ** Tests
>
> So far we have tested full jtreg on both x86 AVX512 and AArch64 SVE with
> experimental VM option "PostLoopMultiversioning" turned on. We found no
> issue in all tests. We notice that those existing cases are not enough
> because some of above issues are not spotted by them. We would like to
> add some new cases but we found existing vectorization tests are a bit
> cumbersome - golden results must be pre-calculated and hard-coded in the
> test code for correctness verification. Thus, in this patch, we propose
> a new vectorization testing framework.
>
> Our new framework brings a simpler way to add new cases. For a new test
> case, we only need to create a new method annotated with "@Test". The
> test runner will invoke each annotated method twice automatically. First
> time it runs in the interpreter and second time it's forced compiled by
> C2. Then the two return results are compared. So in this framework each
> test method should return a primitive value or an array of primitives.
> In this way, no extra verification code for vectorization correctness is
> required. This test runner is still jtreg-based and takes advantages of
> the jtreg WhiteBox API, which enables test methods running at specific
> compilation levels. Each test class inside is also jtreg-based. It just
> need to inherit from the test runner class and run with two additional
> options "-Xbootclasspath/a:." and "-XX:+WhiteBoxAPI".
>
> ** Summary & Future work
>
> In this patch, we reworked post loop vectorization. We made it platform
> independent and fixed several issues inside. We also implemented a new
> vectorization testing framework with many test cases inside. Meanwhile,
> we did some code cleanups.
>
> This patch only touches C2 code guarded with PostLoopMultiversioning,
> except a few data structure changes. So, there's no behavior change when
> experimental VM option PostLoopMultiversioning is off. Also, to reduce
> risks, we still propose to keep post loop vectorization experimental for
> now. But if it receives positive feedback, we would like to change it to
> non-experimental in the future.
Don’t know why your reply is not displayed on Github page.
> “Thanks for clarification, can we not prevent generating post vector masked tail iteration in case there is no vector atomic loop after unrolled main vector loop. This can guard against any performance penalties associated with usage of 64 byte vectors in drain loop if main loop operates over smaller vectors.”
So far I haven’t found a good way to prevent generating vector masked tail loop if no atomic vector drain loop exists, because the scalar RCE’d post loop is inserted before the main loop is unrolled, but the vector drain loop is inserted in later ideal loop phase iteration after superword has done -- see “insert_scalar_rced_post_loop()” and “insert_vector_post_loop()” call sites in loopTransform.cpp.
But your suggestion is good. I believe we should fix that performance penalty before making post loop vectorization non-experimental. I have another idea that making the vector masked tail loop running more than 1 iteration. In this way, the cloned vector drain loop is no longer required. But it requires some bigger refactoring work. As this patch focuses on “fix and re-enablement” and already contains a lot of fixes of previously accumulated issues, I’d like to try my idea in later patches.
Thanks,
Pengfei
From: Jatin Bhateja ***@***.***>
Sent: Wednesday, January 26, 2022 00:42
To: openjdk/jdk ***@***.***>
Cc: Pengfei Li ***@***.***>; Mention ***@***.***>
Subject: Re: [openjdk/jdk] 8183390: Fix and re-enable post loop vectorization (PR #6828)
Hi Jatin,
BTW why have you kept a constraint on the vector size of post tail loop to match MaxVectorSize ?
I just did more investigation about why there was a MaxVectorSize constraint. By looking at the failure after removing that, I found in some smaller MaxVectorSize configurations, the main loop may unroll more times than the vector lane count. In this scenario, the vector drain loop is not cloned from the atomic vector main loop. Without the vector drain loop, 1 iteration would be NOT enough for the vector masked tail loop so the test case generates incorrect result. Hence, we need to keep the MaxVectorSize constraint to make sure it's enough for the vector masked tail loop to run at most 1 iteration.
I'd be glad if you have more suggestions.
Hi Pengfie,
Thanks for clarification, can we not prevent generating post vector masked tail iteration in case there is no vector atomic loop after unrolled main vector loop. This can guard against any performance penalties associated with usage of 64 byte vectors in drain loop if main loop operates over smaller vectors.
Regards,
Jatin
—
Reply to this email directly, view it on GitHub<https://github.com/openjdk/jdk/pull/6828#issuecomment-1021387403>, or unsubscribe<https://github.com/notifications/unsubscribe-auth/AKYYFPBCSOM6XIMOOB46QZTUX3HG5ANCNFSM5KAIUHMA>.
Triage notifications on the go with GitHub Mobile for iOS<https://apps.apple.com/app/apple-store/id1477376905?ct=notification-email&mt=8&pt=524675> or Android<https://play.google.com/store/apps/details?id=com.github.android&referrer=utm_campaign%3Dnotification-email%26utm_medium%3Demail%26utm_source%3Dgithub>.
You are receiving this because you were mentioned.Message ID: ***@***.******@***.***>>
-------------
PR: https://git.openjdk.java.net/jdk/pull/6828
More information about the hotspot-compiler-dev
mailing list