Daniel Berlin via llvm-dev
2016-Oct-24 20:31 UTC
[llvm-dev] RFC: Killing undef and spreading poison
On Mon, Oct 24, 2016 at 1:26 PM, Daniel Berlin <dberlin at dberlin.org> wrote:> > > On Sun, Oct 23, 2016 at 9:30 AM, Nuno Lopes <nuno.lopes at ist.utl.pt> wrote: > >> > So just to be clear (mainly so i can go back to letting y'all hash this >> out), in value numbering: >> > 1. I can value number all freeze operations on the same operand to the >> same value >> > *as long as* >> > 2. I replace all freeze values of the same operand with a single one. >> > >> > Or am i misunderstanding? >> > If i've got it right, the issue i see with #2 is whether i can hoist >> freezes or not. >> > >> > If not, it may not be possible to cover all uses. >> > >> > IE >> > if (a) { >> > %1 = freeze (%x) >> > } else if (b) { >> > %2 = freeze (%x) >> > } else if (c){ >> > %3 = freeze (%x) >> > } >> > >> > I cannot replace these with a single freeze def without placing a >> freeze above the if block. >> >> As Sanjoy said, hoisting freeze is fine, but movement is not without >> constraints. For example, you cannot duplicate execution of freeze. >> e.g. the following is wrong (assuming loop body may execute multiple >> times): >> >> %x = freeze %y >> while(...) { use %x } >> => >> while(...) { >> %x = freeze %y >> use %x >> } >> >> So Sanjoy saying that freeze can be thought as an atomic/volatile >> operation seems like a good intuition. >> >> >> > *If* i need to replace them all with the same freeze def in order to be >> able to consider them the same value, (...) >> >> Right, so just to make it very clear, the following would be wrong: >> %x = freeze %y >> %w = freeze %y >> use_1 %x >> use_2 %w >> use_3 %x >> => >> %x = freeze %y >> %w = freeze %y >> use_1 %w >> use_2 %w >> use_3 %x >> >> If you replace one use of %x, all uses have to be replaced, since >> different freezes of the same operand *may* return different values. >> I guess that since we are never (err, most of the times) sure of whether >> a value may come out of freeze, this rule needs to be applied to any value. >> Daniel: is that fine for GVN, or would it make things too complicated? >> > > Current GVN will definitely get this wrong an d would be hard to fix > because of how it eliminates (IE it may cause performance regression) >To be clear, i mean: "If you make current GVN understand freeze x has the same value everywhere, it will do the wrong thing. If you make it think freeze x has a different value everywhere, it will never eliminate anything, which is a regression" But again, just to make sure i understand, is the following legal: %x = freeze %y %w = freeze %y use_1 %x use_2 %w use_3 %x => %x = freeze %y use_1 %x use_2 %x use_3 %x (assuming use_2 is the only use of %w) We can make newgvn get it right.> > >> >> Nuno >> >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161024/ac3dbcf1/attachment.html>
Nuno Lopes via llvm-dev
2016-Oct-25 17:19 UTC
[llvm-dev] RFC: Killing undef and spreading poison
>>>> So just to be clear (mainly so i can go back to letting y'all hash this out), in value numbering: >>>> 1. I can value number all freeze operations on the same operand to the same value >>>> *as long as* >>>> 2. I replace all freeze values of the same operand with a single one. >>>> >>>> Or am i misunderstanding? >>>> If i've got it right, the issue i see with #2 is whether i can hoist freezes or not. >>>> >>>> If not, it may not be possible to cover all uses. >>>> >>>> IE >>>> if (a) { >>>> %1 = freeze (%x) >>>> } else if (b) { >>>> %2 = freeze (%x) >>>> } else if (c){ >>>> %3 = freeze (%x) >>>> } >>>> >>>> I cannot replace these with a single freeze def without placing a freeze above the if block. >>> >>> As Sanjoy said, hoisting freeze is fine, but movement is not without constraints. For example, you cannot duplicate execution of freeze. >>> e.g. the following is wrong (assuming loop body may execute multiple times): >>> >>> %x = freeze %y >>> while(...) { use %x } >>> => >>> while(...) { >>> %x = freeze %y >>> use %x >>> } >>> >>> So Sanjoy saying that freeze can be thought as an atomic/volatile operation seems like a good intuition. >>> >>> >>>> *If* i need to replace them all with the same freeze def in order to be able to consider them the same value, (...) >>> >>> Right, so just to make it very clear, the following would be wrong: >>> %x = freeze %y >>> %w = freeze %y >>> use_1 %x >>> use_2 %w >>> use_3 %x >>> => >>> %x = freeze %y >>> %w = freeze %y >>> use_1 %w >>> use_2 %w >>> use_3 %x >>> >>> If you replace one use of %x, all uses have to be replaced, since different freezes of the same operand *may* return different values. >>> I guess that since we are never (err, most of the times) sure of whether a value may come out of freeze, this rule needs to be applied to any value. >>> Daniel: is that fine for GVN, or would it make things too complicated? >>> >> Current GVN will definitely get this wrong an d would be hard to fix because of how it eliminates (IE it may cause performance regression) > > To be clear, i mean: "If you make current GVN understand freeze x has the same value everywhere, it will do the wrong thing. If you make it think freeze x has a different value everywhere, it will never eliminate anything, which is a regression" > > But again, just to make sure i understand, is the following legal: > %x = freeze %y > %w = freeze %y > use_1 %x > use_2 %w > use_3 %x > => > %x = freeze %y > use_1 %x > use_2 %x > use_3 %x > > > (assuming use_2 is the only use of %w)Yes, that's legal. It might not be profitable, though, since a freeze with just one use is easier to optimize. But I guess that's a trade-off we need to explore later. We hope the number of freezes will be small, but in bad cases we currently see 5% of instructions being freeze.>> We can make newgvn get it right.Cool, glad to hear that, thanks! Nuno
Daniel Berlin via llvm-dev
2016-Oct-25 17:44 UTC
[llvm-dev] RFC: Killing undef and spreading poison
On Tue, Oct 25, 2016 at 10:19 AM, Nuno Lopes <nuno.lopes at ist.utl.pt> wrote:> >>>> So just to be clear (mainly so i can go back to letting y'all hash > this out), in value numbering: > >>>> 1. I can value number all freeze operations on the same operand to > the same value > >>>> *as long as* > >>>> 2. I replace all freeze values of the same operand with a single one. > >>>> > >>>> Or am i misunderstanding? > >>>> If i've got it right, the issue i see with #2 is whether i can hoist > freezes or not. > >>>> > >>>> If not, it may not be possible to cover all uses. > >>>> > >>>> IE > >>>> if (a) { > >>>> %1 = freeze (%x) > >>>> } else if (b) { > >>>> %2 = freeze (%x) > >>>> } else if (c){ > >>>> %3 = freeze (%x) > >>>> } > >>>> > >>>> I cannot replace these with a single freeze def without placing a > freeze above the if block. > >>> > >>> As Sanjoy said, hoisting freeze is fine, but movement is not without > constraints. For example, you cannot duplicate execution of freeze. > >>> e.g. the following is wrong (assuming loop body may execute multiple > times): > >>> > >>> %x = freeze %y > >>> while(...) { use %x } > >>> => > >>> while(...) { > >>> %x = freeze %y > >>> use %x > >>> } > >>> > >>> So Sanjoy saying that freeze can be thought as an atomic/volatile > operation seems like a good intuition. > >>> > >>> > >>>> *If* i need to replace them all with the same freeze def in order to > be able to consider them the same value, (...) > >>> > >>> Right, so just to make it very clear, the following would be wrong: > >>> %x = freeze %y > >>> %w = freeze %y > >>> use_1 %x > >>> use_2 %w > >>> use_3 %x > >>> => > >>> %x = freeze %y > >>> %w = freeze %y > >>> use_1 %w > >>> use_2 %w > >>> use_3 %x > >>> > >>> If you replace one use of %x, all uses have to be replaced, since > different freezes of the same operand *may* return different values. > >>> I guess that since we are never (err, most of the times) sure of > whether a value may come out of freeze, this rule needs to be applied to > any value. > >>> Daniel: is that fine for GVN, or would it make things too complicated? > >>> > >> Current GVN will definitely get this wrong an d would be hard to fix > because of how it eliminates (IE it may cause performance regression) > > > > To be clear, i mean: "If you make current GVN understand freeze x has > the same value everywhere, it will do the wrong thing. If you make it think > freeze x has a different value everywhere, it will never eliminate > anything, which is a regression" > > > > But again, just to make sure i understand, is the following legal: > > %x = freeze %y > > %w = freeze %y > > use_1 %x > > use_2 %w > > use_3 %x > > => > > %x = freeze %y > > use_1 %x > > use_2 %x > > use_3 %x > > > > > > (assuming use_2 is the only use of %w) > > Yes, that's legal. > It might not be profitable, though, since a freeze with just one use is > easier to optimize.Easier is a relative term. I expect optimally choosing which freezes to eliminate where, etc, reduces to a covering problem variant (or just straight ILP) :)> But I guess that's a trade-off we need to explore later. > We hope the number of freezes will be small, but in bad cases we currently > see 5% of instructions being freeze. >> > > >> We can make newgvn get it right. > > Cool, glad to hear that, thanks! > > Nuno > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20161025/70e8f782/attachment.html>