From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from [87.239.111.99] (localhost [127.0.0.1]) by dev.tarantool.org (Postfix) with ESMTP id 30F636F8399; Wed, 22 Nov 2023 18:25:36 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 30F636F8399 DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=tarantool.org; s=dev; t=1700666736; bh=4+W9ZTNgJWgZUFIlQZ6fj/1nmm1yt5GLMiVoTE071Ug=; h=Date:To:Cc:References:In-Reply-To:Subject:List-Id: List-Unsubscribe:List-Archive:List-Post:List-Help:List-Subscribe: From:Reply-To:From; b=Vo2KrM9V+gdowCgC1sTG8bEe0F71ftv/5HtFbWrilQsyEmAzamKHzgAGhehTwsc2L wOCqcIWodZUfNLMtzmsfyGj2K+nRLizuCzuXh0V/1/SqJ+wAK1iflR3Lj0gAm8gqJ0 eSmImtUqoEUazeXcjDyDanjrdOagD1YTDdj0W3do= Received: from smtp30.i.mail.ru (smtp30.i.mail.ru [95.163.41.71]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256) (No client certificate requested) by dev.tarantool.org (Postfix) with ESMTPS id 12BD26F8050 for ; Wed, 22 Nov 2023 18:25:35 +0300 (MSK) DKIM-Filter: OpenDKIM Filter v2.11.0 dev.tarantool.org 12BD26F8050 Received: by smtp30.i.mail.ru with esmtpa (envelope-from ) id 1r5p6b-005zXl-27; Wed, 22 Nov 2023 18:25:34 +0300 Message-ID: Date: Wed, 22 Nov 2023 18:25:33 +0300 MIME-Version: 1.0 User-Agent: Mozilla Thunderbird Content-Language: en-US To: Sergey Kaplun , Maxim Kokryashkin Cc: tarantool-patches@dev.tarantool.org References: <20231109122628.19853-1-skaplun@tarantool.org> In-Reply-To: <20231109122628.19853-1-skaplun@tarantool.org> Content-Type: text/plain; charset=UTF-8; format=flowed Content-Transfer-Encoding: 7bit X-Mailru-Src: smtp X-4EC0790: 10 X-7564579A: 646B95376F6C166E X-77F55803: 4F1203BC0FB41BD92D71B79D2A671AE603E36BF1254C6C76F1226F493F8CB8BF182A05F538085040A7F96D5F0FFF98F2FB85BFA0EFD679AD58DFF73CFBFAB6A80EE9FF0B27C740B2 X-7FA49CB5: FF5795518A3D127A4AD6D5ED66289B5278DA827A17800CE7B114C2C2C20B7E62EA1F7E6F0F101C67BD4B6F7A4D31EC0BCC500DACC3FED6E28638F802B75D45FF8AA50765F79006376CE4E8B6A85920B98638F802B75D45FF36EB9D2243A4F8B5A6FCA7DBDB1FC311F39EFFDF887939037866D6147AF826D834EC36960E7F146D02E18FFE644585B0117882F4460429724CE54428C33FAD305F5C1EE8F4F765FC2EE5AD8F952D28FBA471835C12D1D9774AD6D5ED66289B52BA9C0B312567BB23117882F446042972877693876707352033AC447995A7AD18618001F51B5FD3F9D2E47CDBA5A96583BA9C0B312567BB2376E601842F6C81A19E625A9149C048EE0AC5B80A05675ACDE45489B29CB19804D8FC6C240DEA76429C9F4D5AE37F343AA9539A8B242431040A6AB1C7CE11FEE3DA7BFA4571439BB203F1AB874ED89028C4224003CC836476E2F48590F00D11D6E2021AF6380DFAD1A18204E546F3947CD2DCF9CF1F528DBC2E808ACE2090B5E1725E5C173C3A84C3E478A468B35FE767089D37D7C0E48F6C8AA50765F79006373B9693DF9B93E282731C566533BA786AA5CC5B56E945C8DA X-C1DE0DAB: 0D63561A33F958A50E32F4BF87FA671DEAAD9EB3659ED48881294F5DFBB85847F87CCE6106E1FC07E67D4AC08A07B9B01F9513A7CA91E555CB5012B2E24CD356 X-C8649E89: 1C3962B70DF3F0ADE00A9FD3E00BEEDF3FED46C3ACD6F73ED3581295AF09D3DF87807E0823442EA2ED31085941D9CD0AF7F820E7B07EA4CF203663978B9ADD4A59D1DDEED6FAA65CD23F97CF1F94369E1F3908FF616F9DBA110A92F5D16EB67F88AD3775A6B0C834B59C773B5522DAB5FB8A6921249E6F31E48CAC7CA610320002C26D483E81D6BE0DBAE6F56676BC7117BB6831D7356A2DEC5B5AD62611EEC62B5AFB4261A09AF0 X-D57D3AED: 3ZO7eAau8CL7WIMRKs4sN3D3tLDjz0dLbV79QFUyzQ2Ujvy7cMT6pYYqY16iZVKkSc3dCLJ7zSJH7+u4VD18S7Vl4ZUrpaVfd2+vE6kuoey4m4VkSEu530nj6fImhcD4MUrOEAnl0W826KZ9Q+tr5ycPtXkTV4k65bRjmOUUP8cvGozZ33TWg5HZplvhhXbhDGzqmQDTd6OAevLeAnq3Ra9uf7zvY2zzsIhlcp/Y7m53TZgf2aB4JOg4gkr2biojGZhPsaRkbbm13UwKk0MHZQ== X-Mailru-Sender: 11C2EC085EDE56FAC07928AF2646A769BFAC658F32F92004FB85BFA0EFD679AD49EBE2174CCC9479EBA65886582A37BD66FEC6BF5C9C28D98A98C1125256619760D574B6FC815AB872D6B4FCE48DF648AE208404248635DF X-Mras: Ok Subject: Re: [Tarantool-patches] [PATCH luajit] Fix HREFK forwarding vs. table.clear(). X-BeenThere: tarantool-patches@dev.tarantool.org X-Mailman-Version: 2.1.34 Precedence: list List-Id: Tarantool development patches List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , From: Sergey Bronnikov via Tarantool-patches Reply-To: Sergey Bronnikov Errors-To: tarantool-patches-bounces@dev.tarantool.org Sender: "Tarantool-patches" Sergey, thanks for the patch! LGTM On 11/9/23 15:26, Sergey Kaplun wrote: > From: Mike Pall > > Reported by XmiliaH. > > (cherry-picked from commit d5a237eae03d2ad346f82390836371a952e9a286) > > When performing HREFK (and also ALOAD, HLOAD) forwarding optimization, > the `table.clear()` function call may be performed on the table operand > from HREFK between table creation and IR, from which value is forwarded. > This call isn't taken in the account, so it may lead to too optimistic > value-forwarding from NEWREF (and also ASTORE, HSTORE), or the omitted > type guard for HREFK operation. Therefore, this leads to incorrect trace > behaviour (for example, taking a non-nil value from the cleared table). > > This patch adds necessary checks for `table.clear()` calls. > > 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-792-hrefk-table-clear > Tarantool PR: https://github.com/tarantool/tarantool/pull/9351 > Relate issues: > * https://github.com/LuaJIT/LuaJIT/issues/792 > * https://github.com/tarantool/tarantool/issues/9145 > > src/lj_opt_mem.c | 63 +++--- > .../lj-792-hrefk-table-clear.test.lua | 181 ++++++++++++++++++ > 2 files changed, 213 insertions(+), 31 deletions(-) > create mode 100644 test/tarantool-tests/lj-792-hrefk-table-clear.test.lua > > diff --git a/src/lj_opt_mem.c b/src/lj_opt_mem.c > index a83558ac..24a490d5 100644 > --- a/src/lj_opt_mem.c > +++ b/src/lj_opt_mem.c > @@ -72,6 +72,34 @@ static AliasRet aa_table(jit_State *J, IRRef ta, IRRef tb) > return aa_escape(J, taba, tabb); > } > > +/* Check whether there's no aliasing table.clear. */ > +static int fwd_aa_tab_clear(jit_State *J, IRRef lim, IRRef ta) > +{ > + IRRef ref = J->chain[IR_CALLS]; > + while (ref > lim) { > + IRIns *calls = IR(ref); > + if (calls->op2 == IRCALL_lj_tab_clear && > + (ta == calls->op1 || aa_table(J, ta, calls->op1) != ALIAS_NO)) > + return 0; /* Conflict. */ > + ref = calls->prev; > + } > + return 1; /* No conflict. Can safely FOLD/CSE. */ > +} > + > +/* Check whether there's no aliasing NEWREF/table.clear for the left operand. */ > +int LJ_FASTCALL lj_opt_fwd_tptr(jit_State *J, IRRef lim) > +{ > + IRRef ta = fins->op1; > + IRRef ref = J->chain[IR_NEWREF]; > + while (ref > lim) { > + IRIns *newref = IR(ref); > + if (ta == newref->op1 || aa_table(J, ta, newref->op1) != ALIAS_NO) > + return 0; /* Conflict. */ > + ref = newref->prev; > + } > + return fwd_aa_tab_clear(J, lim, ta); > +} > + > /* Alias analysis for array and hash access using key-based disambiguation. */ > static AliasRet aa_ahref(jit_State *J, IRIns *refa, IRIns *refb) > { > @@ -154,7 +182,8 @@ static TRef fwd_ahload(jit_State *J, IRRef xref) > IRIns *ir = (xr->o == IR_HREFK || xr->o == IR_AREF) ? IR(xr->op1) : xr; > IRRef tab = ir->op1; > ir = IR(tab); > - if (ir->o == IR_TNEW || (ir->o == IR_TDUP && irref_isk(xr->op2))) { > + if ((ir->o == IR_TNEW || (ir->o == IR_TDUP && irref_isk(xr->op2))) && > + fwd_aa_tab_clear(J, tab, tab)) { > /* A NEWREF with a number key may end up pointing to the array part. > ** But it's referenced from HSTORE and not found in the ASTORE chain. > ** Or a NEWREF may rehash the table and move unrelated number keys. > @@ -275,7 +304,7 @@ TRef LJ_FASTCALL lj_opt_fwd_hrefk(jit_State *J) > while (ref > tab) { > IRIns *newref = IR(ref); > if (tab == newref->op1) { > - if (fright->op1 == newref->op2) > + if (fright->op1 == newref->op2 && fwd_aa_tab_clear(J, ref, tab)) > return ref; /* Forward from NEWREF. */ > else > goto docse; > @@ -285,7 +314,7 @@ TRef LJ_FASTCALL lj_opt_fwd_hrefk(jit_State *J) > ref = newref->prev; > } > /* No conflicting NEWREF: key location unchanged for HREFK of TDUP. */ > - if (IR(tab)->o == IR_TDUP) > + if (IR(tab)->o == IR_TDUP && fwd_aa_tab_clear(J, tab, tab)) > fins->t.irt &= ~IRT_GUARD; /* Drop HREFK guard. */ > docse: > return CSEFOLD; > @@ -319,34 +348,6 @@ int LJ_FASTCALL lj_opt_fwd_href_nokey(jit_State *J) > return 1; /* No conflict. Can fold to niltv. */ > } > > -/* Check whether there's no aliasing table.clear. */ > -static int fwd_aa_tab_clear(jit_State *J, IRRef lim, IRRef ta) > -{ > - IRRef ref = J->chain[IR_CALLS]; > - while (ref > lim) { > - IRIns *calls = IR(ref); > - if (calls->op2 == IRCALL_lj_tab_clear && > - (ta == calls->op1 || aa_table(J, ta, calls->op1) != ALIAS_NO)) > - return 0; /* Conflict. */ > - ref = calls->prev; > - } > - return 1; /* No conflict. Can safely FOLD/CSE. */ > -} > - > -/* Check whether there's no aliasing NEWREF/table.clear for the left operand. */ > -int LJ_FASTCALL lj_opt_fwd_tptr(jit_State *J, IRRef lim) > -{ > - IRRef ta = fins->op1; > - IRRef ref = J->chain[IR_NEWREF]; > - while (ref > lim) { > - IRIns *newref = IR(ref); > - if (ta == newref->op1 || aa_table(J, ta, newref->op1) != ALIAS_NO) > - return 0; /* Conflict. */ > - ref = newref->prev; > - } > - return fwd_aa_tab_clear(J, lim, ta); > -} > - > /* ASTORE/HSTORE elimination. */ > TRef LJ_FASTCALL lj_opt_dse_ahstore(jit_State *J) > { > diff --git a/test/tarantool-tests/lj-792-hrefk-table-clear.test.lua b/test/tarantool-tests/lj-792-hrefk-table-clear.test.lua > new file mode 100644 > index 00000000..e662e0cc > --- /dev/null > +++ b/test/tarantool-tests/lj-792-hrefk-table-clear.test.lua > @@ -0,0 +1,181 @@ > +local tap = require('tap') > + > +-- Test file to demonstrate LuaJIT incorrect optimizations across > +-- the `table.clear()` call. > +-- See also: https://github.com/LuaJIT/LuaJIT/issues/792. > + > +local test = tap.test('lj-792-hrefk-table-clear'):skipcond({ > + ['Test requires JIT enabled'] = not jit.status(), > +}) > +local table_clear = require('table.clear') > + > +test:plan(7) > + > +local NITERATIONS = 4 > +local MAGIC = 42 > + > +local function test_aref_fwd_tnew(tab_number) > + local field_value_after_clear > + for i = 1, NITERATIONS do > + -- Create a table on trace to make the optimization work. > + -- Initialize the first field to work with the array part. > + local tab = {i} > + -- Use an additional table to alias the created table with the > + -- `1` key. > + local tab_array = {tab, {0}} > + -- AREF to be forwarded. > + tab[1] = MAGIC > + table_clear(tab_array[tab_number]) > + -- It should be `nil`, since table is cleared. > + field_value_after_clear = tab[1] > + end > + return field_value_after_clear > +end > + > +local function test_aref_fwd_tdup(tab_number) > + local field_value_after_clear > + for _ = 1, NITERATIONS do > + -- Create a table on trace to make the optimization work. > + local tab = {nil} > + -- Use an additional table to alias the created table with the > + -- `1` key. > + local tab_array = {tab, {0}} > + -- AREF to be forwarded. > + tab[1] = MAGIC > + table_clear(tab_array[tab_number]) > + -- It should be `nil`, since table is cleared. > + field_value_after_clear = tab[1] > + end > + return field_value_after_clear > +end > + > +local function test_href_fwd_tnew(tab_number) > + local field_value_after_clear > + for _ = 1, NITERATIONS do > + -- Create a table on trace to make the optimization work. > + local tab = {} > + -- Use an additional table to alias the created table with the > + -- `8` key. > + local tab_array = {tab, {0}} > + -- HREF to be forwarded. Use 8 to be in the hash part. > + tab[8] = MAGIC > + table_clear(tab_array[tab_number]) > + -- It should be `nil`, since table is cleared. > + field_value_after_clear = tab[8] > + end > + return field_value_after_clear > +end > + > +local function test_href_fwd_tdup(tab_number) > + local field_value_after_clear > + for _ = 1, NITERATIONS do > + -- Create a table on trace to make the optimization work. > + local tab = {nil} > + -- Use an additional table to alias the created table with the > + -- `8` key. > + local tab_array = {tab, {0}} > + -- HREF to be forwarded. Use 8 to be in the hash part. > + tab[8] = MAGIC > + table_clear(tab_array[tab_number]) > + -- It should be `nil`, since table is cleared. > + field_value_after_clear = tab[8] > + end > + return field_value_after_clear > +end > + > +jit.opt.start('hotloop=1') > + > +-- First compile the trace with a clearing not-interesting table. > +test_aref_fwd_tnew(2) > +-- Now run the trace with the clearing table, from which we take > +-- AREF. > +test:is(test_aref_fwd_tnew(1), nil, 'AREF forward from TNEW') > + > +-- XXX: Reset hotcounters to avoid collisions. > +jit.opt.start('hotloop=1') > + > +-- First compile the trace with a clearing not-interesting table. > +test_aref_fwd_tdup(2) > +-- Now run the trace with the clearing table, from which we take > +-- AREF. > +test:is(test_aref_fwd_tdup(1), nil, 'AREF forward from TDUP') > + > +-- XXX: Reset hotcounters to avoid collisions. > +jit.opt.start('hotloop=1') > + > +-- First compile the trace with a clearing not-interesting table. > +test_href_fwd_tnew(2) > +-- Now run the trace with the clearing table, from which we take > +-- HREF. > +test:is(test_href_fwd_tnew(1), nil, 'HREF forward from TNEW') > + > +-- XXX: Reset hotcounters to avoid collisions. > +jit.opt.start('hotloop=1') > + > +-- First compile the trace with a clearing not-interesting table. > +test_href_fwd_tdup(2) > +-- Now run the trace with the clearing table, from which we take > +-- HREF. > +test:is(test_href_fwd_tdup(1), nil, 'HREF forward from TDUP') > + > +local function test_not_forwarded_hrefk_val_from_newref(tab_number) > + local field_value_after_clear > + for _ = 1, NITERATIONS do > + -- Create a table on trace to make the optimization work. > + local tab = {} > + -- NEWREF to be forwarded. > + tab.hrefk = MAGIC > + -- Use an additional table to alias the created table with the > + -- `hrefk` key. > + local tab_array = {tab, {hrefk = 0}} > + table_clear(tab_array[tab_number]) > + -- It should be `nil`, since it is cleared. > + field_value_after_clear = tab.hrefk > + end > + return field_value_after_clear > +end > + > +-- XXX: Reset hotcounters to avoid collisions. > +jit.opt.start('hotloop=1') > + > +-- First compile the trace with a clearing not-interesting table. > +test_not_forwarded_hrefk_val_from_newref(2) > +-- Now run the trace with the clearing table, from which we take > +-- HREFK. > +local value_from_cleared_tab = test_not_forwarded_hrefk_val_from_newref(1) > + > +test:is(value_from_cleared_tab, nil, > + 'not forward the field value across table.clear') > + > +local function test_not_dropped_guard_on_hrefk(tab_number) > + local tab, field_value_after_clear > + for _ = 1, NITERATIONS do > + -- Create a table on trace to make the optimization work. > + tab = {hrefk = MAGIC} > + -- Use an additional table to alias the created table with the > + -- `hrefk` key. > + local tab_array = {tab, {hrefk = 0}} > + table_clear(tab_array[tab_number]) > + -- It should be `nil`, since it is cleared. > + -- If the guard is dropped for HREFK, the value from the TDUP > + -- table is taken instead, without the type check. This leads > + -- to incorrect (swapped) returned values. > + field_value_after_clear = tab.hrefk > + tab.hrefk = MAGIC > + end > + return field_value_after_clear, tab.hrefk > +end > + > +-- XXX: Reset hotcounters to avoid collisions. > +jit.opt.start('hotloop=1') > + > +-- First compile the trace with clearing not interesting table. > +test_not_dropped_guard_on_hrefk(2) > +-- Now run the trace with the clearing table, from which we take > +-- HREFK. > +local field_value_after_clear, tab_hrefk = test_not_dropped_guard_on_hrefk(1) > + > +test:is(field_value_after_clear, nil, 'correct field value after table.clear') > +test:is(tab_hrefk, MAGIC, 'correct value set in the table that was cleared') > + > +test:done(true)