Re: [Mesa-dev] [PATCH 8/9 v2] nir: Add partial redundancy elimination for compares
On 09/03/2018 03:17 AM, andrey simiklit wrote:
> Hi,
>
> I guess it is just a small mistake in description that:
> 'z' was before:
> z = y - x;
> and became after:
> z = x - y;
>
> I think you inadvertently misspelled in the description and you mean:
>
>
> This pass attempts to dectect code sequences like
>
> if (x < y) {
> z = y - x;
> ...
> }
>
> and replace them with sequences like
>
> t = *y - x*;
> if (t < 0) {
> z = t;
> ...
> }
There is a mistake in the original comment, but this isn't correct
either. (y - x) < 0 is not the same as x < y. :) The optimization does
detect cases like this, but it would replace the comparison with a zero
on the left (see the zero_on_left parameter to rewrite_compare_instruction):
if (x < y) {
z = y - x;
...
}
would become
t = y - x;
if (0 < t) {
z = t;
...
}
> Because the subtraction is not commutative operation)
> Please correct me if I am incorrect.
>
> Regards,
> Andrii.
>
> On Thu, Aug 30, 2018 at 8:36 AM Ian Romanick > wrote:
>
> From: Ian Romanick >
>
> This pass attempts to dectect code sequences like
>
> if (x < y) {
> z = y - x;
> ...
> }
>
> and replace them with sequences like
>
> t = x - y;
> if (t < 0) {
> z = t;
> ...
> }
>
> On architectures where the subtract can generate the flags used by the
> if-statement, this saves an instruction. It's also possible that moving
> an instruction out of the if-statement will allow
> nir_opt_peephole_select to convert the whole thing to a bcsel.
>
> Currently only floating point compares and adds are supported. Adding
> support for integer will be a challenge due to integer overflow. There
> are a couple possible solutions, but they may not apply to all
> architectures.
>
> v2: Fix a typo in the commit message and a couple typos in comments.
> Fix possible NULL pointer deref from result of push_block(). Add
> missing (-A + B) case. Suggested by Caio.
>
> Signed-off-by: Ian Romanick >
> ---
> src/compiler/Makefile.sources | 1 +
> src/compiler/nir/meson.build | 1 +
> src/compiler/nir/nir.h | 2 +
> src/compiler/nir/nir_opt_comparison_pre.c | 360
> ++
> src/compiler/nir/nir_search_helpers.h | 29 +++
> 5 files changed, 393 insertions(+)
> create mode 100644 src/compiler/nir/nir_opt_comparison_pre.c
>
> diff --git a/src/compiler/Makefile.sources
> b/src/compiler/Makefile.sources
> index d3b06564832..9fe8d5b8904 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -267,6 +267,7 @@ NIR_FILES = \
> nir/nir_move_load_const.c \
> nir/nir_move_vec_src_uses_to_dest.c \
> nir/nir_normalize_cubemap_coords.c \
> + nir/nir_opt_comparison_pre.c \
> nir/nir_opt_conditional_discard.c \
> nir/nir_opt_constant_folding.c \
> nir/nir_opt_copy_prop_vars.c \
> diff --git a/src/compiler/nir/meson.build b/src/compiler/nir/meson.build
> index 5438c17a8f8..2bcc854829e 100644
> --- a/src/compiler/nir/meson.build
> +++ b/src/compiler/nir/meson.build
> @@ -151,6 +151,7 @@ files_libnir = files(
> 'nir_move_load_const.c',
> 'nir_move_vec_src_uses_to_dest.c',
> 'nir_normalize_cubemap_coords.c',
> + 'nir_opt_comparison_pre.c',
> 'nir_opt_conditional_discard.c',
> 'nir_opt_constant_folding.c',
> 'nir_opt_copy_prop_vars.c',
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> index ddbcb3c647e..c78387d0acf 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -3000,6 +3000,8 @@ bool nir_convert_from_ssa(nir_shader *shader,
> bool phi_webs_only);
> bool nir_lower_phis_to_regs_block(nir_block *block);
> bool nir_lower_ssa_defs_to_regs_block(nir_block *block);
>
> +bool nir_opt_comparison_pre(nir_shader *shader);
> +
> bool nir_opt_algebraic(nir_shader *shader);
> bool nir_opt_algebraic_before_ffma(nir_shader *shader);
> bool nir_opt_algebraic_late(nir_shader *shader);
> diff --git a/src/compiler/nir/nir_opt_comparison_pre.c
> b/src/compiler/nir/nir_opt_comparison_pre.c
> new file mode 100644
> index 000..b2827c21816
> --- /dev/null
> +++ b/src/compiler/nir/nir_opt_comparison_pre.c
> @@ -0,0 +1,360 @@
> +/*
> + * Copyright © 2018 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person
> obtaining a
> + * copy of this
Re: [Mesa-dev] [PATCH 8/9 v2] nir: Add partial redundancy elimination for compares
Hi,
I guess it is just a small mistake in description that:
'z' was before:
z = y - x;
and became after:
z = x - y;
I think you inadvertently misspelled in the description and you mean:
>
> This pass attempts to dectect code sequences like
>
> if (x < y) {
> z = y - x;
> ...
> }
>
> and replace them with sequences like
>
> t = *y - x*;
> if (t < 0) {
> z = t;
> ...
> }
>
Because the subtraction is not commutative operation)
Please correct me if I am incorrect.
Regards,
Andrii.
On Thu, Aug 30, 2018 at 8:36 AM Ian Romanick wrote:
> From: Ian Romanick
>
> This pass attempts to dectect code sequences like
>
> if (x < y) {
> z = y - x;
> ...
> }
>
> and replace them with sequences like
>
> t = x - y;
> if (t < 0) {
> z = t;
> ...
> }
>
> On architectures where the subtract can generate the flags used by the
> if-statement, this saves an instruction. It's also possible that moving
> an instruction out of the if-statement will allow
> nir_opt_peephole_select to convert the whole thing to a bcsel.
>
> Currently only floating point compares and adds are supported. Adding
> support for integer will be a challenge due to integer overflow. There
> are a couple possible solutions, but they may not apply to all
> architectures.
>
> v2: Fix a typo in the commit message and a couple typos in comments.
> Fix possible NULL pointer deref from result of push_block(). Add
> missing (-A + B) case. Suggested by Caio.
>
> Signed-off-by: Ian Romanick
> ---
> src/compiler/Makefile.sources | 1 +
> src/compiler/nir/meson.build | 1 +
> src/compiler/nir/nir.h| 2 +
> src/compiler/nir/nir_opt_comparison_pre.c | 360
> ++
> src/compiler/nir/nir_search_helpers.h | 29 +++
> 5 files changed, 393 insertions(+)
> create mode 100644 src/compiler/nir/nir_opt_comparison_pre.c
>
> diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
> index d3b06564832..9fe8d5b8904 100644
> --- a/src/compiler/Makefile.sources
> +++ b/src/compiler/Makefile.sources
> @@ -267,6 +267,7 @@ NIR_FILES = \
> nir/nir_move_load_const.c \
> nir/nir_move_vec_src_uses_to_dest.c \
> nir/nir_normalize_cubemap_coords.c \
> + nir/nir_opt_comparison_pre.c \
> nir/nir_opt_conditional_discard.c \
> nir/nir_opt_constant_folding.c \
> nir/nir_opt_copy_prop_vars.c \
> diff --git a/src/compiler/nir/meson.build b/src/compiler/nir/meson.build
> index 5438c17a8f8..2bcc854829e 100644
> --- a/src/compiler/nir/meson.build
> +++ b/src/compiler/nir/meson.build
> @@ -151,6 +151,7 @@ files_libnir = files(
>'nir_move_load_const.c',
>'nir_move_vec_src_uses_to_dest.c',
>'nir_normalize_cubemap_coords.c',
> + 'nir_opt_comparison_pre.c',
>'nir_opt_conditional_discard.c',
>'nir_opt_constant_folding.c',
>'nir_opt_copy_prop_vars.c',
> diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
> index ddbcb3c647e..c78387d0acf 100644
> --- a/src/compiler/nir/nir.h
> +++ b/src/compiler/nir/nir.h
> @@ -3000,6 +3000,8 @@ bool nir_convert_from_ssa(nir_shader *shader, bool
> phi_webs_only);
> bool nir_lower_phis_to_regs_block(nir_block *block);
> bool nir_lower_ssa_defs_to_regs_block(nir_block *block);
>
> +bool nir_opt_comparison_pre(nir_shader *shader);
> +
> bool nir_opt_algebraic(nir_shader *shader);
> bool nir_opt_algebraic_before_ffma(nir_shader *shader);
> bool nir_opt_algebraic_late(nir_shader *shader);
> diff --git a/src/compiler/nir/nir_opt_comparison_pre.c
> b/src/compiler/nir/nir_opt_comparison_pre.c
> new file mode 100644
> index 000..b2827c21816
> --- /dev/null
> +++ b/src/compiler/nir/nir_opt_comparison_pre.c
> @@ -0,0 +1,360 @@
> +/*
> + * Copyright © 2018 Intel Corporation
> + *
> + * Permission is hereby granted, free of charge, to any person obtaining a
> + * copy of this software and associated documentation files (the
> "Software"),
> + * to deal in the Software without restriction, including without
> limitation
> + * the rights to use, copy, modify, merge, publish, distribute,
> sublicense,
> + * and/or sell copies of the Software, and to permit persons to whom the
> + * Software is furnished to do so, subject to the following conditions:
> + *
> + * The above copyright notice and this permission notice (including the
> next
> + * paragraph) shall be included in all copies or substantial portions of
> the
> + * Software.
> + *
> + * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
> EXPRESS OR
> + * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
> MERCHANTABILITY,
> + * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT
> SHALL
> + * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR
> OTHER
> + * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
> + * FROM, OUT OF OR IN CONNECTION WITH
[Mesa-dev] [PATCH 8/9 v2] nir: Add partial redundancy elimination for compares
From: Ian Romanick
This pass attempts to dectect code sequences like
if (x < y) {
z = y - x;
...
}
and replace them with sequences like
t = x - y;
if (t < 0) {
z = t;
...
}
On architectures where the subtract can generate the flags used by the
if-statement, this saves an instruction. It's also possible that moving
an instruction out of the if-statement will allow
nir_opt_peephole_select to convert the whole thing to a bcsel.
Currently only floating point compares and adds are supported. Adding
support for integer will be a challenge due to integer overflow. There
are a couple possible solutions, but they may not apply to all
architectures.
v2: Fix a typo in the commit message and a couple typos in comments.
Fix possible NULL pointer deref from result of push_block(). Add
missing (-A + B) case. Suggested by Caio.
Signed-off-by: Ian Romanick
---
src/compiler/Makefile.sources | 1 +
src/compiler/nir/meson.build | 1 +
src/compiler/nir/nir.h| 2 +
src/compiler/nir/nir_opt_comparison_pre.c | 360 ++
src/compiler/nir/nir_search_helpers.h | 29 +++
5 files changed, 393 insertions(+)
create mode 100644 src/compiler/nir/nir_opt_comparison_pre.c
diff --git a/src/compiler/Makefile.sources b/src/compiler/Makefile.sources
index d3b06564832..9fe8d5b8904 100644
--- a/src/compiler/Makefile.sources
+++ b/src/compiler/Makefile.sources
@@ -267,6 +267,7 @@ NIR_FILES = \
nir/nir_move_load_const.c \
nir/nir_move_vec_src_uses_to_dest.c \
nir/nir_normalize_cubemap_coords.c \
+ nir/nir_opt_comparison_pre.c \
nir/nir_opt_conditional_discard.c \
nir/nir_opt_constant_folding.c \
nir/nir_opt_copy_prop_vars.c \
diff --git a/src/compiler/nir/meson.build b/src/compiler/nir/meson.build
index 5438c17a8f8..2bcc854829e 100644
--- a/src/compiler/nir/meson.build
+++ b/src/compiler/nir/meson.build
@@ -151,6 +151,7 @@ files_libnir = files(
'nir_move_load_const.c',
'nir_move_vec_src_uses_to_dest.c',
'nir_normalize_cubemap_coords.c',
+ 'nir_opt_comparison_pre.c',
'nir_opt_conditional_discard.c',
'nir_opt_constant_folding.c',
'nir_opt_copy_prop_vars.c',
diff --git a/src/compiler/nir/nir.h b/src/compiler/nir/nir.h
index ddbcb3c647e..c78387d0acf 100644
--- a/src/compiler/nir/nir.h
+++ b/src/compiler/nir/nir.h
@@ -3000,6 +3000,8 @@ bool nir_convert_from_ssa(nir_shader *shader, bool
phi_webs_only);
bool nir_lower_phis_to_regs_block(nir_block *block);
bool nir_lower_ssa_defs_to_regs_block(nir_block *block);
+bool nir_opt_comparison_pre(nir_shader *shader);
+
bool nir_opt_algebraic(nir_shader *shader);
bool nir_opt_algebraic_before_ffma(nir_shader *shader);
bool nir_opt_algebraic_late(nir_shader *shader);
diff --git a/src/compiler/nir/nir_opt_comparison_pre.c
b/src/compiler/nir/nir_opt_comparison_pre.c
new file mode 100644
index 000..b2827c21816
--- /dev/null
+++ b/src/compiler/nir/nir_opt_comparison_pre.c
@@ -0,0 +1,360 @@
+/*
+ * Copyright © 2018 Intel Corporation
+ *
+ * Permission is hereby granted, free of charge, to any person obtaining a
+ * copy of this software and associated documentation files (the "Software"),
+ * to deal in the Software without restriction, including without limitation
+ * the rights to use, copy, modify, merge, publish, distribute, sublicense,
+ * and/or sell copies of the Software, and to permit persons to whom the
+ * Software is furnished to do so, subject to the following conditions:
+ *
+ * The above copyright notice and this permission notice (including the next
+ * paragraph) shall be included in all copies or substantial portions of the
+ * Software.
+ *
+ * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+ * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+ * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL
+ * THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+ * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING
+ * FROM, OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS
+ * IN THE SOFTWARE.
+ */
+
+#include "nir_instr_set.h"
+#include "nir_search_helpers.h"
+#include "nir_builder.h"
+#include "util/u_vector.h"
+
+/* Partial redundancy elimination of compares
+ *
+ * Seaches for comparisons of the form 'a cmp b' that dominate arithmetic
+ * instructions like 'b - a'. The comparison is replaced by the arithmetic
+ * instruction, and the result is compared with zero. For example,
+ *
+ * vec1 32 ssa_111 = flt 0.37, ssa_110.w
+ * if ssa_111 {
+ * block block_1:
+ * vec1 32 ssa_112 = fadd ssa_110.w, -0.37
+ * ...
+ *
+ * becomes
+ *
+ * vec1 32 ssa_111 = fadd ssa_110.w, -0.37
+ * vec1 32 ssa_112 = flt 0.0, ssa_111
+ * if ssa_112 {
+ * block block_1:
+
