[Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Sergey Kaplun via Tarantool-patches]

From: Mike Pall <mike>

Reported by XmiliaH.

(cherry-picked from commit c8bcf1e5fb8eb72c7e35604fdfd27bba512761bb)

`fold_abc_k()` doesn't patch the first ABC check when the right constant
operand is negative. This leads to out-of-bounds access from the array
on a trace. This patch casts to uint32_t the operands to compare. If the
right IR contains a negative integer, the second IR will always be
patched. Also, because the ABC check on the trace is unordered, this
guard will always fail.

Also, this fold rule creates new instructions that reference operands
across PHIs. This opens the room for other optimizations (like DCE), so
some guards become eliminated, and we use out-of-bounds access from the
array part of the table on trace. This patch adds the missing
`PHIBARRIER()` check.

Sergey Kaplun:
* added the description and the test for the problem

Part of tarantool/tarantool#9145
---
Branch: https://github.com/tarantool/luajit/tree/skaplun/lj-794-abc-fold-constants
Tarantool PR: https://github.com/tarantool/tarantool/pull/9364
Related issues:
* https://github.com/LuaJIT/LuaJIT/issues/794
* https://github.com/tarantool/tarantool/issues/9145

 src/lj_opt_fold.c                             |  5 +-
 .../lj-794-abc-fold-constants.test.lua        | 85 +++++++++++++++++++
 2 files changed, 88 insertions(+), 2 deletions(-)
 create mode 100644 test/tarantool-tests/lj-794-abc-fold-constants.test.lua

diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
index 944a9ecc..6175f7c1 100644
--- a/src/lj_opt_fold.c
+++ b/src/lj_opt_fold.c
@@ -1877,14 +1877,15 @@ LJFOLDF(abc_fwd)
 LJFOLD(ABC any KINT)
 LJFOLDF(abc_k)
 {
+  PHIBARRIER(fleft);
   if (LJ_LIKELY(J->flags & JIT_F_OPT_ABC)) {
     IRRef ref = J->chain[IR_ABC];
     IRRef asize = fins->op1;
     while (ref > asize) {
       IRIns *ir = IR(ref);
       if (ir->op1 == asize && irref_isk(ir->op2)) {
-	int32_t k = IR(ir->op2)->i;
-	if (fright->i > k)
+	uint32_t k = (uint32_t)IR(ir->op2)->i;
+	if ((uint32_t)fright->i > k)
 	  ir->op2 = fins->op2;
 	return DROPFOLD;
       }
diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
new file mode 100644
index 00000000..f8609933
--- /dev/null
+++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
@@ -0,0 +1,85 @@
+local tap = require('tap')
+
+-- Test file to demonstrate LuaJIT's incorrect fold optimization
+-- for Array Bound Check for constants.
+-- ABC(asize, k1), ABC(asize k2) ==> ABC(asize, max(k1, k2)).
+-- See also https://github.com/LuaJIT/LuaJIT/issues/794.
+
+local test = tap.test('lj-794-abc-fold-constants'):skipcond({
+  ['Test requires JIT enabled'] = not jit.status(),
+})
+
+local MAGIC_UNUSED = 42
+test:plan(2)
+
+local function abc_check_sign()
+  local tab = {MAGIC_UNUSED}
+  local return_value = 0
+  local abc_limit = 1
+  -- No need to run the loop on the first call. We will take
+  -- the side exit anyway.
+  for i = 1, 3 do
+    -- Add an additional ABC check to be merged with.
+    if i > 1 then
+      -- luacheck: ignore
+      return_value = tab[1]
+      return_value = tab[abc_limit]
+      -- XXX: Just use some negative number.
+      abc_limit = -1000000
+    end
+  end
+  return return_value
+end
+
+jit.opt.start('hotloop=1')
+
+-- Compile the loop.
+abc_check_sign()
+-- Run the loop.
+test:is(abc_check_sign(), nil, 'correct ABC constant rule for negative values')
+
+-- Now test the second issue, when ABC optimization applies for
+-- operands across PHIs.
+
+-- XXX: Reset hotcounters to avoid collisions.
+jit.opt.start('hotloop=1')
+
+local tab_array = {}
+local small_tab = {MAGIC_UNUSED}
+local full_tab = {}
+
+-- First, create tables with different asizes, to be used in PHI.
+-- Create a large enough array part for the noticeable
+-- out-of-bounds access.
+for i = 1, 8 do
+  full_tab[i] = MAGIC_UNUSED
+end
+
+-- We need 5 iterations to execute both the variant and the
+-- invariant parts of the trace below.
+for i = 1, 5 do
+  -- On the 3rd iteration, the recording is started.
+  if i > 3 then
+    tab_array[i] = small_tab
+  else
+    tab_array[i] = full_tab
+  end
+end
+
+local result
+local alias_tab = tab_array[1]
+-- Compile a trace.
+-- Run 5 iterations to execute both the variant and the invariant
+-- parts.
+for i = 1, 5 do
+  local local_tab = alias_tab
+  alias_tab = tab_array[i]
+  -- Additional ABC check to fold.
+  -- luacheck: ignore
+  result = alias_tab[1]
+  result = local_tab[8]
+end
+
+test:is(result, nil, 'correct ABC constant rule across PHI')
+
+test:done(true)
-- 
2.42.0

Re: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Maxim Kokryashkin via Tarantool-patches]

Hi, Sergey!
Thanks for the patch!
Please consider my comments below.

On Mon, Nov 13, 2023 at 06:05:01PM +0300, Sergey Kaplun wrote:
> From: Mike Pall <mike>
>
> Reported by XmiliaH.
>
> (cherry-picked from commit c8bcf1e5fb8eb72c7e35604fdfd27bba512761bb)
>
> `fold_abc_k()` doesn't patch the first ABC check when the right constant
> operand is negative. This leads to out-of-bounds access from the array
> on a trace. This patch casts to uint32_t the operands to compare. If the
It would be right to paraphrase this sentence like this:
"This patch casts the operands to uint32_t for comparison."
> right IR contains a negative integer, the second IR will always be
> patched. Also, because the ABC check on the trace is unordered, this
> guard will always fail.
>
> Also, this fold rule creates new instructions that reference operands
> across PHIs. This opens the room for other optimizations (like DCE), so
> some guards become eliminated, and we use out-of-bounds access from the
> array part of the table on trace. This patch adds the missing
> `PHIBARRIER()` check.
>
> Sergey Kaplun:
> * added the description and the test for the problem
>
> Part of tarantool/tarantool#9145
> ---
> Branch: https://github.com/tarantool/luajit/tree/skaplun/lj-794-abc-fold-constants
> Tarantool PR: https://github.com/tarantool/tarantool/pull/9364
> Related issues:
> * https://github.com/LuaJIT/LuaJIT/issues/794
> * https://github.com/tarantool/tarantool/issues/9145
>
>  src/lj_opt_fold.c                             |  5 +-
>  .../lj-794-abc-fold-constants.test.lua        | 85 +++++++++++++++++++
>  2 files changed, 88 insertions(+), 2 deletions(-)
>  create mode 100644 test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>
> diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
> index 944a9ecc..6175f7c1 100644
> --- a/src/lj_opt_fold.c
> +++ b/src/lj_opt_fold.c
<snipped>

> diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> new file mode 100644
> index 00000000..f8609933
> --- /dev/null
> +++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> @@ -0,0 +1,85 @@
<snipped>

> +-- Now test the second issue, when ABC optimization applies for
> +-- operands across PHIs.
> +
> +-- XXX: Reset hotcounters to avoid collisions.
> +jit.opt.start('hotloop=1')
> +
> +local tab_array = {}
> +local small_tab = {MAGIC_UNUSED}
> +local full_tab = {}
> +
> +-- First, create tables with different asizes, to be used in PHI.
> +-- Create a large enough array part for the noticeable
> +-- out-of-bounds access.
> +for i = 1, 8 do
> +  full_tab[i] = MAGIC_UNUSED
> +end
> +
> +-- We need 5 iterations to execute both the variant and the
> +-- invariant parts of the trace below.
> +for i = 1, 5 do
> +  -- On the 3rd iteration, the recording is started.
> +  if i > 3 then
> +    tab_array[i] = small_tab
> +  else
> +    tab_array[i] = full_tab
> +  end
> +end
> +
> +local result
> +local alias_tab = tab_array[1]
> +-- Compile a trace.
> +-- Run 5 iterations to execute both the variant and the invariant
> +-- parts.
> +for i = 1, 5 do
> +  local local_tab = alias_tab
> +  alias_tab = tab_array[i]
> +  -- Additional ABC check to fold.
> +  -- luacheck: ignore
> +  result = alias_tab[1]
> +  result = local_tab[8]
> +end

The black magic that happens here with tables is hard to understand.
Please drop a comment with a detailed explanations for why do we need
this complex `tab_array` construction and what effects does this have on
IRs.
> +
> +test:is(result, nil, 'correct ABC constant rule across PHI')
> +
> +test:done(true)
> --
> 2.42.0
>

Re: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Sergey Bronnikov via Tarantool-patches]

Hello, Sergey!

thanks for the patch! LGTM, see minor comments below.

Sergey

On 11/13/23 18:05, Sergey Kaplun wrote:
> From: Mike Pall <mike>
>
> Reported by XmiliaH.
>
> (cherry-picked from commit c8bcf1e5fb8eb72c7e35604fdfd27bba512761bb)
>
> `fold_abc_k()` doesn't patch the first ABC check when the right constant
> operand is negative. This leads to out-of-bounds access from the array
> on a trace. This patch casts to uint32_t the operands to compare. If the
> right IR contains a negative integer, the second IR will always be
> patched. Also, because the ABC check on the trace is unordered, this
> guard will always fail.
>
> Also, this fold rule creates new instructions that reference operands
IR output would be useful in a test, what do you think?
> across PHIs. This opens the room for other optimizations (like DCE), so
> some guards become eliminated, and we use out-of-bounds access from the
> array part of the table on trace. This patch adds the missing
> `PHIBARRIER()` check.
>
> Sergey Kaplun:
> * added the description and the test for the problem
>
> Part of tarantool/tarantool#9145
> ---
> Branch: https://github.com/tarantool/luajit/tree/skaplun/lj-794-abc-fold-constants
> Tarantool PR: https://github.com/tarantool/tarantool/pull/9364
> Related issues:
> * https://github.com/LuaJIT/LuaJIT/issues/794
> * https://github.com/tarantool/tarantool/issues/9145
>
>   src/lj_opt_fold.c                             |  5 +-
>   .../lj-794-abc-fold-constants.test.lua        | 85 +++++++++++++++++++
>   2 files changed, 88 insertions(+), 2 deletions(-)
>   create mode 100644 test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>
> diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
> index 944a9ecc..6175f7c1 100644
> --- a/src/lj_opt_fold.c
> +++ b/src/lj_opt_fold.c
> @@ -1877,14 +1877,15 @@ LJFOLDF(abc_fwd)
>   LJFOLD(ABC any KINT)
>   LJFOLDF(abc_k)
>   {
> +  PHIBARRIER(fleft);
>     if (LJ_LIKELY(J->flags & JIT_F_OPT_ABC)) {
>       IRRef ref = J->chain[IR_ABC];
>       IRRef asize = fins->op1;
>       while (ref > asize) {
>         IRIns *ir = IR(ref);
>         if (ir->op1 == asize && irref_isk(ir->op2)) {
> -	int32_t k = IR(ir->op2)->i;
> -	if (fright->i > k)
> +	uint32_t k = (uint32_t)IR(ir->op2)->i;
> +	if ((uint32_t)fright->i > k)
>   	  ir->op2 = fins->op2;
>   	return DROPFOLD;
>         }
> diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> new file mode 100644
> index 00000000..f8609933
> --- /dev/null
> +++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> @@ -0,0 +1,85 @@
> +local tap = require('tap')
> +
> +-- Test file to demonstrate LuaJIT's incorrect fold optimization
> +-- for Array Bound Check for constants.
> +-- ABC(asize, k1), ABC(asize k2) ==> ABC(asize, max(k1, k2)).
> +-- See also https://github.com/LuaJIT/LuaJIT/issues/794.
> +
> +local test = tap.test('lj-794-abc-fold-constants'):skipcond({
> +  ['Test requires JIT enabled'] = not jit.status(),
> +})
> +
> +local MAGIC_UNUSED = 42

AFAIK we put all test-related stuff after "test:plan".

Feel free to ignore.

> +test:plan(2)
> +
> +local function abc_check_sign()
> +  local tab = {MAGIC_UNUSED}
> +  local return_value = 0
> +  local abc_limit = 1
> +  -- No need to run the loop on the first call. We will take
> +  -- the side exit anyway.
> +  for i = 1, 3 do
> +    -- Add an additional ABC check to be merged with.
> +    if i > 1 then
> +      -- luacheck: ignore
> +      return_value = tab[1]
> +      return_value = tab[abc_limit]
> +      -- XXX: Just use some negative number.
> +      abc_limit = -1000000

With -1 works too, I would replace -10^6 with -1 for simplification.



<snipped>

Re: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Sergey Kaplun via Tarantool-patches]

Hi, Maxim!
Thanks for the review!
Please consider my answers below.

On 17.11.23, Maxim Kokryashkin wrote:
> Hi, Sergey!
> Thanks for the patch!
> Please consider my comments below.
> 
> On Mon, Nov 13, 2023 at 06:05:01PM +0300, Sergey Kaplun wrote:
> > From: Mike Pall <mike>
> >
> > Reported by XmiliaH.
> >
> > (cherry-picked from commit c8bcf1e5fb8eb72c7e35604fdfd27bba512761bb)
> >
> > `fold_abc_k()` doesn't patch the first ABC check when the right constant
> > operand is negative. This leads to out-of-bounds access from the array
> > on a trace. This patch casts to uint32_t the operands to compare. If the
> It would be right to paraphrase this sentence like this:
> "This patch casts the operands to uint32_t for comparison."

Replaced, thanks.

> > right IR contains a negative integer, the second IR will always be
> > patched. Also, because the ABC check on the trace is unordered, this
> > guard will always fail.
> >
> > Also, this fold rule creates new instructions that reference operands
> > across PHIs. This opens the room for other optimizations (like DCE), so
> > some guards become eliminated, and we use out-of-bounds access from the
> > array part of the table on trace. This patch adds the missing
> > `PHIBARRIER()` check.
> >
> > Sergey Kaplun:
> > * added the description and the test for the problem
> >
> > Part of tarantool/tarantool#9145
> > ---
> > Branch: https://github.com/tarantool/luajit/tree/skaplun/lj-794-abc-fold-constants
> > Tarantool PR: https://github.com/tarantool/tarantool/pull/9364
> > Related issues:
> > * https://github.com/LuaJIT/LuaJIT/issues/794
> > * https://github.com/tarantool/tarantool/issues/9145
> >
> >  src/lj_opt_fold.c                             |  5 +-
> >  .../lj-794-abc-fold-constants.test.lua        | 85 +++++++++++++++++++
> >  2 files changed, 88 insertions(+), 2 deletions(-)
> >  create mode 100644 test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> >
> > diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
> > index 944a9ecc..6175f7c1 100644
> > --- a/src/lj_opt_fold.c
> > +++ b/src/lj_opt_fold.c
> <snipped>
> 
> > diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> > new file mode 100644
> > index 00000000..f8609933
> > --- /dev/null
> > +++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> > @@ -0,0 +1,85 @@
> <snipped>
> 
> > +-- Now test the second issue, when ABC optimization applies for
> > +-- operands across PHIs.
> > +
> > +-- XXX: Reset hotcounters to avoid collisions.
> > +jit.opt.start('hotloop=1')
> > +
> > +local tab_array = {}
> > +local small_tab = {MAGIC_UNUSED}
> > +local full_tab = {}
> > +
> > +-- First, create tables with different asizes, to be used in PHI.
> > +-- Create a large enough array part for the noticeable
> > +-- out-of-bounds access.
> > +for i = 1, 8 do
> > +  full_tab[i] = MAGIC_UNUSED
> > +end
> > +
> > +-- We need 5 iterations to execute both the variant and the
> > +-- invariant parts of the trace below.
> > +for i = 1, 5 do
> > +  -- On the 3rd iteration, the recording is started.
> > +  if i > 3 then
> > +    tab_array[i] = small_tab
> > +  else
> > +    tab_array[i] = full_tab
> > +  end
> > +end
> > +
> > +local result
> > +local alias_tab = tab_array[1]
> > +-- Compile a trace.
> > +-- Run 5 iterations to execute both the variant and the invariant
> > +-- parts.
> > +for i = 1, 5 do
> > +  local local_tab = alias_tab
> > +  alias_tab = tab_array[i]
> > +  -- Additional ABC check to fold.
> > +  -- luacheck: ignore
> > +  result = alias_tab[1]
> > +  result = local_tab[8]
> > +end
> 
> The black magic that happens here with tables is hard to understand.
> Please drop a comment with a detailed explanations for why do we need
> this complex `tab_array` construction and what effects does this have on
> IRs.

Added the following comment for clarification:
Also, renaming `local_tab` -> `previous_tab` to avoid confusion and
emphasize that the table from the previous iteration, which ABC check IR
is used.

===================================================================
diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
index f8609933..c69d395b 100644
--- a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
+++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
@@ -55,6 +55,12 @@ for i = 1, 8 do
   full_tab[i] = MAGIC_UNUSED
 end
 
+-- Now, store these tables in the array. The PHI should be used in
+-- the trace to distinguish asizes from the variant and the
+-- invariant parts of the loop for the future ABC check.
+-- Nevertheless, before the patch, the ABC IR and the
+-- corresponding PHI are folded via optimization. This leads to
+-- incorrect behaviour.
 -- We need 5 iterations to execute both the variant and the
 -- invariant parts of the trace below.
 for i = 1, 5 do
@@ -72,12 +78,12 @@ local alias_tab = tab_array[1]
 -- Run 5 iterations to execute both the variant and the invariant
 -- parts.
 for i = 1, 5 do
-  local local_tab = alias_tab
+  local previous_tab = alias_tab
   alias_tab = tab_array[i]
   -- Additional ABC check to fold.
   -- luacheck: ignore
   result = alias_tab[1]
-  result = local_tab[8]
+  result = previous_tab[8]
 end
 
 test:is(result, nil, 'correct ABC constant rule across PHI')
===================================================================

> > +
> > +test:is(result, nil, 'correct ABC constant rule across PHI')
> > +
> > +test:done(true)
> > --
> > 2.42.0
> >

-- 
Best regards,
Sergey Kaplun

Re: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Sergey Kaplun via Tarantool-patches]

Hello, Sergey!
Thanks for the review!
Please consider my answers below.

On 18.11.23, Sergey Bronnikov wrote:
> Hello, Sergey!
> 
> thanks for the patch! LGTM, see minor comments below.
> 
> Sergey
> 
> On 11/13/23 18:05, Sergey Kaplun wrote:
> > From: Mike Pall <mike>
> >
> > Reported by XmiliaH.
> >
> > (cherry-picked from commit c8bcf1e5fb8eb72c7e35604fdfd27bba512761bb)
> >
> > `fold_abc_k()` doesn't patch the first ABC check when the right constant
> > operand is negative. This leads to out-of-bounds access from the array
> > on a trace. This patch casts to uint32_t the operands to compare. If the
> > right IR contains a negative integer, the second IR will always be
> > patched. Also, because the ABC check on the trace is unordered, this
> > guard will always fail.
> >
> > Also, this fold rule creates new instructions that reference operands
> IR output would be useful in a test, what do you think?

I am not really sure about that (if I did, I would add it).
The mention of missed IRs sounds like a good compromise.
Anyone interested in the output dump can observe it by running test from
the command line.

> > across PHIs. This opens the room for other optimizations (like DCE), so
> > some guards become eliminated, and we use out-of-bounds access from the
> > array part of the table on trace. This patch adds the missing
> > `PHIBARRIER()` check.
> >
> > Sergey Kaplun:
> > * added the description and the test for the problem
> >
> > Part of tarantool/tarantool#9145
> > ---
> > Branch: https://github.com/tarantool/luajit/tree/skaplun/lj-794-abc-fold-constants
> > Tarantool PR: https://github.com/tarantool/tarantool/pull/9364
> > Related issues:
> > * https://github.com/LuaJIT/LuaJIT/issues/794
> > * https://github.com/tarantool/tarantool/issues/9145
> >
> >   src/lj_opt_fold.c                             |  5 +-
> >   .../lj-794-abc-fold-constants.test.lua        | 85 +++++++++++++++++++
> >   2 files changed, 88 insertions(+), 2 deletions(-)
> >   create mode 100644 test/tarantool-tests/lj-794-abc-fold-constants.test.lua

<snipped>

> > diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> > new file mode 100644
> > index 00000000..f8609933
> > --- /dev/null
> > +++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
> > @@ -0,0 +1,85 @@
> > +local tap = require('tap')
> > +
> > +-- Test file to demonstrate LuaJIT's incorrect fold optimization
> > +-- for Array Bound Check for constants.
> > +-- ABC(asize, k1), ABC(asize k2) ==> ABC(asize, max(k1, k2)).
> > +-- See also https://github.com/LuaJIT/LuaJIT/issues/794.
> > +
> > +local test = tap.test('lj-794-abc-fold-constants'):skipcond({
> > +  ['Test requires JIT enabled'] = not jit.status(),
> > +})
> > +
> > +local MAGIC_UNUSED = 42
> 
> AFAIK we put all test-related stuff after "test:plan".
> 
> Feel free to ignore.

Fixed, thanks!
See the iterative patch below.

===================================================================
diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
index c69d395b..53e4d2eb 100644
--- a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
+++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
@@ -9,9 +9,10 @@ local test = tap.test('lj-794-abc-fold-constants'):skipcond({
   ['Test requires JIT enabled'] = not jit.status(),
 })
 
-local MAGIC_UNUSED = 42
 test:plan(2)
 
+local MAGIC_UNUSED = 42
+
 local function abc_check_sign()
   local tab = {MAGIC_UNUSED}
   local return_value = 0
===================================================================

Branch is force-pushed.

> 
> > +test:plan(2)
> > +
> > +local function abc_check_sign()
> > +  local tab = {MAGIC_UNUSED}
> > +  local return_value = 0
> > +  local abc_limit = 1
> > +  -- No need to run the loop on the first call. We will take
> > +  -- the side exit anyway.
> > +  for i = 1, 3 do
> > +    -- Add an additional ABC check to be merged with.
> > +    if i > 1 then
> > +      -- luacheck: ignore
> > +      return_value = tab[1]
> > +      return_value = tab[abc_limit]
> > +      -- XXX: Just use some negative number.
> > +      abc_limit = -1000000
> 
> With -1 works too, I would replace -10^6 with -1 for simplification.

Not always (I tried). I prefer to use the value from the reproducer that
fails stable.
Ignore for now.

> 
> 
> 
> <snipped>
> 

-- 
Best regards,
Sergey Kaplun

Re: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Sergey Bronnikov via Tarantool-patches]

On 11/20/23 14:12, Sergey Kaplun wrote:
> Hello, Sergey!
> Thanks for the review!
> Please consider my answers below.
Thanks! LGTM
>
> On 18.11.23, Sergey Bronnikov wrote:
>
<snipped>

Re: [Tarantool-patches] [PATCH luajit] Fix ABC FOLD rule with constants.

[Maxim Kokryashkin via Tarantool-patches]

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


Hi, Sergey!
Thanks for the fixes!
LGTM
--
Best regards,
Maxim Kokryashkin
 
  
>Понедельник, 20 ноября 2023, 14:03 +03:00 от Sergey Kaplun <skaplun@tarantool.org>:
> 
>Hi, Maxim!
>Thanks for the review!
>Please consider my answers below.
>
>On 17.11.23, Maxim Kokryashkin wrote:
>> Hi, Sergey!
>> Thanks for the patch!
>> Please consider my comments below.
>>
>> On Mon, Nov 13, 2023 at 06:05:01PM +0300, Sergey Kaplun wrote:
>> > From: Mike Pall <mike>
>> >
>> > Reported by XmiliaH.
>> >
>> > (cherry-picked from commit c8bcf1e5fb8eb72c7e35604fdfd27bba512761bb)
>> >
>> > `fold_abc_k()` doesn't patch the first ABC check when the right constant
>> > operand is negative. This leads to out-of-bounds access from the array
>> > on a trace. This patch casts to uint32_t the operands to compare. If the
>> It would be right to paraphrase this sentence like this:
>> "This patch casts the operands to uint32_t for comparison."
>
>Replaced, thanks.
>
>> > right IR contains a negative integer, the second IR will always be
>> > patched. Also, because the ABC check on the trace is unordered, this
>> > guard will always fail.
>> >
>> > Also, this fold rule creates new instructions that reference operands
>> > across PHIs. This opens the room for other optimizations (like DCE), so
>> > some guards become eliminated, and we use out-of-bounds access from the
>> > array part of the table on trace. This patch adds the missing
>> > `PHIBARRIER()` check.
>> >
>> > Sergey Kaplun:
>> > * added the description and the test for the problem
>> >
>> > Part of tarantool/tarantool#9145
>> > ---
>> > Branch:  https://github.com/tarantool/luajit/tree/skaplun/lj-794-abc-fold-constants
>> > Tarantool PR:  https://github.com/tarantool/tarantool/pull/9364
>> > Related issues:
>> > *  https://github.com/LuaJIT/LuaJIT/issues/794
>> > *  https://github.com/tarantool/tarantool/issues/9145
>> >
>> > src/lj_opt_fold.c | 5 +-
>> > .../lj-794-abc-fold-constants.test.lua | 85 +++++++++++++++++++
>> > 2 files changed, 88 insertions(+), 2 deletions(-)
>> > create mode 100644 test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>> >
>> > diff --git a/src/lj_opt_fold.c b/src/lj_opt_fold.c
>> > index 944a9ecc..6175f7c1 100644
>> > --- a/src/lj_opt_fold.c
>> > +++ b/src/lj_opt_fold.c
>> <snipped>
>>
>> > diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>> > new file mode 100644
>> > index 00000000..f8609933
>> > --- /dev/null
>> > +++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>> > @@ -0,0 +1,85 @@
>> <snipped>
>>
>> > +-- Now test the second issue, when ABC optimization applies for
>> > +-- operands across PHIs.
>> > +
>> > +-- XXX: Reset hotcounters to avoid collisions.
>> > +jit.opt.start('hotloop=1')
>> > +
>> > +local tab_array = {}
>> > +local small_tab = {MAGIC_UNUSED}
>> > +local full_tab = {}
>> > +
>> > +-- First, create tables with different asizes, to be used in PHI.
>> > +-- Create a large enough array part for the noticeable
>> > +-- out-of-bounds access.
>> > +for i = 1, 8 do
>> > + full_tab[i] = MAGIC_UNUSED
>> > +end
>> > +
>> > +-- We need 5 iterations to execute both the variant and the
>> > +-- invariant parts of the trace below.
>> > +for i = 1, 5 do
>> > + -- On the 3rd iteration, the recording is started.
>> > + if i > 3 then
>> > + tab_array[i] = small_tab
>> > + else
>> > + tab_array[i] = full_tab
>> > + end
>> > +end
>> > +
>> > +local result
>> > +local alias_tab = tab_array[1]
>> > +-- Compile a trace.
>> > +-- Run 5 iterations to execute both the variant and the invariant
>> > +-- parts.
>> > +for i = 1, 5 do
>> > + local local_tab = alias_tab
>> > + alias_tab = tab_array[i]
>> > + -- Additional ABC check to fold.
>> > + -- luacheck: ignore
>> > + result = alias_tab[1]
>> > + result = local_tab[8]
>> > +end
>>
>> The black magic that happens here with tables is hard to understand.
>> Please drop a comment with a detailed explanations for why do we need
>> this complex `tab_array` construction and what effects does this have on
>> IRs.
>
>Added the following comment for clarification:
>Also, renaming `local_tab` -> `previous_tab` to avoid confusion and
>emphasize that the table from the previous iteration, which ABC check IR
>is used.
>
>===================================================================
>diff --git a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>index f8609933..c69d395b 100644
>--- a/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>+++ b/test/tarantool-tests/lj-794-abc-fold-constants.test.lua
>@@ -55,6 +55,12 @@ for i = 1, 8 do
>   full_tab[i] = MAGIC_UNUSED
> end
> 
>+-- Now, store these tables in the array. The PHI should be used in
>+-- the trace to distinguish asizes from the variant and the
>+-- invariant parts of the loop for the future ABC check.
>+-- Nevertheless, before the patch, the ABC IR and the
>+-- corresponding PHI are folded via optimization. This leads to
>+-- incorrect behaviour.
> -- We need 5 iterations to execute both the variant and the
> -- invariant parts of the trace below.
> for i = 1, 5 do
>@@ -72,12 +78,12 @@ local alias_tab = tab_array[1]
> -- Run 5 iterations to execute both the variant and the invariant
> -- parts.
> for i = 1, 5 do
>- local local_tab = alias_tab
>+ local previous_tab = alias_tab
>   alias_tab = tab_array[i]
>   -- Additional ABC check to fold.
>   -- luacheck: ignore
>   result = alias_tab[1]
>- result = local_tab[8]
>+ result = previous_tab[8]
> end
> 
> test:is(result, nil, 'correct ABC constant rule across PHI')
>===================================================================
>
>> > +
>> > +test:is(result, nil, 'correct ABC constant rule across PHI')
>> > +
>> > +test:done(true)
>> > --
>> > 2.42.0
>> >
>
>--
>Best regards,
>Sergey Kaplun
 

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