You are right: select in SDAG has to be poison-blocking as well, otherwise the current lowering from IR's select to SDAG's select would be wrong. Which makes the select->or transformation incorrect at SDAG level as well. I guess until recently people believed that poison in SDAG wasn't much of a problem (myself included). I was convinced otherwise with the test cases that Juneyoung found a few weeks ago: https://bugs.llvm.org/show_bug.cgi?id=40657 MI doesn't have poison AFAIK, so at least we are safe there, I hope (not sure about undef, though). I don't know if there was a thorough discussion on the performance benefits of having poison in SDAG, though. Is it that important? are there loop-related optimizations that require nsw information? If so, then we should pay the price and fix SDAG. (and extend Alive to verify SDAG as well -- ok, I'm hanging myself here, but..). If not, maybe getting rid of poison in SDAG could be a good thing. There's also undef, which I don't know exactly what's the semantics, but AFAIR is as bad as the IR's. Nuno Quoting Sanjay Patel via llvm-dev <llvm-dev at lists.llvm.org>:> I don't object to deferring the optimization, but let me check my poison > understanding... > select i1 %cond, i1 true, i1 %x --> or i1 %cond, %x > > 1. 'select' is a poison-blocking operation, but 'or' is > non-poison-blocking, so we are propagating a potentially poisonous %x with > this transform. > 2. We will fix the problem in IR by removing this transform in IR > 3. The backend (SDAG) has that same transform. > 4. SDAG has poison because we propagate the wrapping/exact flags to DAG > nodes. > 5. Are we just sweeping the bug under the rug? Nobody cares because SDAG is > undocumented, so anything goes down there? > > > On Tue, Feb 26, 2019 at 2:06 PM John Regehr via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> > Transforms/InstCombine/select.ll >> > ===============================>> > define i1 @trueval_is_true(i1 %C, i1 %X) { >> > %R = select i1 %C, i1 1, i1 %X >> > ret i1 %R >> > } >> > => >> > define i1 @trueval_is_true(i1 %C, i1 %X) { >> > %R = or i1 %C, %X >> > ret i1 %R >> > } >> > ERROR: Target is more poisonous than source (when %C = #x1 & %X = poison) >> > >> > (there are many variations of these select->arithmetic transformations) >> >> This particular little family of transformations can be reliably done by >> all of the backends I looked at, so disabling them at the IR level >> should be OK. See a bit more discussion here: >> >> > https://bugs.llvm.org/show_bug.cgi?id=40768 >> >> John
Sanjay Patel via llvm-dev
2019-Feb-27 17:37 UTC
[llvm-dev] funnel shift, select, and poison
I don't think anyone at that time realized that we were poisoning SDAG by extending the flags. :) So yes - and this is probably setting myself up for a suicide mission - I think we should undo that decision. A transform that I remember adding to SDAG that depends on wrapping was here: https://reviews.llvm.org/D13757 ...and that shows that the cleanup would have to extend to target-specific files. It also suggests the solution: deal with all poison-related transforms in IR in CGP (or a dedicated codegen IR pass) before we form the DAG, and then drop those bits. On Wed, Feb 27, 2019 at 9:12 AM Nuno Lopes <nunoplopes at sapo.pt> wrote:> You are right: select in SDAG has to be poison-blocking as well, > otherwise the current lowering from IR's select to SDAG's select would > be wrong. Which makes the select->or transformation incorrect at SDAG > level as well. > I guess until recently people believed that poison in SDAG wasn't much > of a problem (myself included). I was convinced otherwise with the > test cases that Juneyoung found a few weeks ago: > https://bugs.llvm.org/show_bug.cgi?id=40657 > > MI doesn't have poison AFAIK, so at least we are safe there, I hope > (not sure about undef, though). > > I don't know if there was a thorough discussion on the performance > benefits of having poison in SDAG, though. Is it that important? are > there loop-related optimizations that require nsw information? > If so, then we should pay the price and fix SDAG. (and extend Alive to > verify SDAG as well -- ok, I'm hanging myself here, but..). If not, > maybe getting rid of poison in SDAG could be a good thing. > There's also undef, which I don't know exactly what's the semantics, > but AFAIR is as bad as the IR's. > > Nuno > > > Quoting Sanjay Patel via llvm-dev <llvm-dev at lists.llvm.org>: > > > I don't object to deferring the optimization, but let me check my poison > > understanding... > > select i1 %cond, i1 true, i1 %x --> or i1 %cond, %x > > > > 1. 'select' is a poison-blocking operation, but 'or' is > > non-poison-blocking, so we are propagating a potentially poisonous %x > with > > this transform. > > 2. We will fix the problem in IR by removing this transform in IR > > 3. The backend (SDAG) has that same transform. > > 4. SDAG has poison because we propagate the wrapping/exact flags to DAG > > nodes. > > 5. Are we just sweeping the bug under the rug? Nobody cares because SDAG > is > > undocumented, so anything goes down there? > > > > > > On Tue, Feb 26, 2019 at 2:06 PM John Regehr via llvm-dev < > > llvm-dev at lists.llvm.org> wrote: > > > >> > Transforms/InstCombine/select.ll > >> > ===============================> >> > define i1 @trueval_is_true(i1 %C, i1 %X) { > >> > %R = select i1 %C, i1 1, i1 %X > >> > ret i1 %R > >> > } > >> > => > >> > define i1 @trueval_is_true(i1 %C, i1 %X) { > >> > %R = or i1 %C, %X > >> > ret i1 %R > >> > } > >> > ERROR: Target is more poisonous than source (when %C = #x1 & %X > poison) > >> > > >> > (there are many variations of these select->arithmetic > transformations) > >> > >> This particular little family of transformations can be reliably done by > >> all of the backends I looked at, so disabling them at the IR level > >> should be OK. See a bit more discussion here: > >> > >> > https://bugs.llvm.org/show_bug.cgi?id=40768 > >> > >> John > >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190227/4e18936f/attachment.html>
I agree it makes sense to reevaluate the decision. Can we change the hasNoSignedWrap() functions to always return false and benchmark what's the worst-case scenario? (i.e., do you have resources to do that experiment?) If it's negligible,then we should just get rid of poison in SDAG given the complications it brings. Thanks, Nuno -----Original Message----- From: Sanjay Patel Sent: Wednesday, February 27, 2019 5:37 PM Subject: Re: [llvm-dev] funnel shift, select, and poison I don't think anyone at that time realized that we were poisoning SDAG by extending the flags. :) So yes - and this is probably setting myself up for a suicide mission - I think we should undo that decision. A transform that I remember adding to SDAG that depends on wrapping was here: https://reviews.llvm.org/D13757 ...and that shows that the cleanup would have to extend to target-specific files. It also suggests the solution: deal with all poison-related transforms in IR in CGP (or a dedicated codegen IR pass) before we form the DAG, and then drop those bits. On Wed, Feb 27, 2019 at 9:12 AM Nuno Lopes <nunoplopes at sapo.pt> wrote: You are right: select in SDAG has to be poison-blocking as well, otherwise the current lowering from IR's select to SDAG's select would be wrong. Which makes the select->or transformation incorrect at SDAG level as well. I guess until recently people believed that poison in SDAG wasn't much of a problem (myself included). I was convinced otherwise with the test cases that Juneyoung found a few weeks ago: https://bugs.llvm.org/show_bug.cgi?id=40657 MI doesn't have poison AFAIK, so at least we are safe there, I hope (not sure about undef, though). I don't know if there was a thorough discussion on the performance benefits of having poison in SDAG, though. Is it that important? are there loop-related optimizations that require nsw information? If so, then we should pay the price and fix SDAG. (and extend Alive to verify SDAG as well -- ok, I'm hanging myself here, but..). If not, maybe getting rid of poison in SDAG could be a good thing. There's also undef, which I don't know exactly what's the semantics, but AFAIR is as bad as the IR's. Nuno Quoting Sanjay Patel via llvm-dev <llvm-dev at lists.llvm.org>:> I don't object to deferring the optimization, but let me check my poison > understanding... > select i1 %cond, i1 true, i1 %x --> or i1 %cond, %x > > 1. 'select' is a poison-blocking operation, but 'or' is > non-poison-blocking, so we are propagating a potentially poisonous %x with > this transform. > 2. We will fix the problem in IR by removing this transform in IR > 3. The backend (SDAG) has that same transform. > 4. SDAG has poison because we propagate the wrapping/exact flags to DAG > nodes. > 5. Are we just sweeping the bug under the rug? Nobody cares because SDAG > is > undocumented, so anything goes down there? > > > On Tue, Feb 26, 2019 at 2:06 PM John Regehr via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> > Transforms/InstCombine/select.ll >> > ===============================>> > define i1 @trueval_is_true(i1 %C, i1 %X) { >> > %R = select i1 %C, i1 1, i1 %X >> > ret i1 %R >> > } >> > => >> > define i1 @trueval_is_true(i1 %C, i1 %X) { >> > %R = or i1 %C, %X >> > ret i1 %R >> > } >> > ERROR: Target is more poisonous than source (when %C = #x1 & %X = >> > poison) >> > >> > (there are many variations of these select->arithmetic transformations) >> >> This particular little family of transformations can be reliably done by >> all of the backends I looked at, so disabling them at the IR level >> should be OK. See a bit more discussion here: >> >> > https://bugs.llvm.org/show_bug.cgi?id=40768 >> >> John
Eli Friedman via llvm-dev
2019-Feb-27 21:25 UTC
[llvm-dev] funnel shift, select, and poison
Flags isn’t the only way you can get poison in SelectionDAG; a bunch of operations produce poison. Among other things, we have shifts with an overflowing shift amount, overflowing fptosi, and AssertZext. IIRC we take advantage of the fptosi UB to avoid redundant masking in some cases. I guess we could go through and limit those operations to something else instead… but I’m not quite sure what that would look like. Getting rid of poison isn’t that helpful if we still have undef (particularly if we’re going to try to get rid of undef at the IR level at some point). I guess we could get rid of undef too, but at that point I think you start seriously hurting target-independent SelectionDAG optimizations: every operation has to have a defined output for every possible input (except operations with a chain can be UB, or produce an output that’s “defined” based on the chain). I guess that would involve adding target-defined behavior for a bunch of operations, along the lines of getBooleanContents(). It makes sense say poison/undef don’t exist after isel. That might block some optimizations in theory, I guess, but I think that matches the way it currently works. (We currently have “undef” operands in MachineInstrs, but that isn’t the same thing.) Well, actually, I think the use of alias analysis in scheduling breaks this (since the result of a load which violates TBAA can be changed by the scheduler), but I don’t think that’s ever led to a practical issue. -Eli From: llvm-dev <llvm-dev-bounces at lists.llvm.org> On Behalf Of Sanjay Patel via llvm-dev Sent: Wednesday, February 27, 2019 9:38 AM To: Nuno Lopes <nunoplopes at sapo.pt> Cc: llvm-dev <llvm-dev at lists.llvm.org>; John Regehr <regehr at cs.utah.edu> Subject: [EXT] Re: [llvm-dev] funnel shift, select, and poison I don't think anyone at that time realized that we were poisoning SDAG by extending the flags. :) So yes - and this is probably setting myself up for a suicide mission - I think we should undo that decision. A transform that I remember adding to SDAG that depends on wrapping was here: https://reviews.llvm.org/D13757 ...and that shows that the cleanup would have to extend to target-specific files. It also suggests the solution: deal with all poison-related transforms in IR in CGP (or a dedicated codegen IR pass) before we form the DAG, and then drop those bits. On Wed, Feb 27, 2019 at 9:12 AM Nuno Lopes <nunoplopes at sapo.pt<mailto:nunoplopes at sapo.pt>> wrote: You are right: select in SDAG has to be poison-blocking as well, otherwise the current lowering from IR's select to SDAG's select would be wrong. Which makes the select->or transformation incorrect at SDAG level as well. I guess until recently people believed that poison in SDAG wasn't much of a problem (myself included). I was convinced otherwise with the test cases that Juneyoung found a few weeks ago: https://bugs.llvm.org/show_bug.cgi?id=40657 MI doesn't have poison AFAIK, so at least we are safe there, I hope (not sure about undef, though). I don't know if there was a thorough discussion on the performance benefits of having poison in SDAG, though. Is it that important? are there loop-related optimizations that require nsw information? If so, then we should pay the price and fix SDAG. (and extend Alive to verify SDAG as well -- ok, I'm hanging myself here, but..). If not, maybe getting rid of poison in SDAG could be a good thing. There's also undef, which I don't know exactly what's the semantics, but AFAIR is as bad as the IR's. Nuno Quoting Sanjay Patel via llvm-dev <llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>>:> I don't object to deferring the optimization, but let me check my poison > understanding... > select i1 %cond, i1 true, i1 %x --> or i1 %cond, %x > > 1. 'select' is a poison-blocking operation, but 'or' is > non-poison-blocking, so we are propagating a potentially poisonous %x with > this transform. > 2. We will fix the problem in IR by removing this transform in IR > 3. The backend (SDAG) has that same transform. > 4. SDAG has poison because we propagate the wrapping/exact flags to DAG > nodes. > 5. Are we just sweeping the bug under the rug? Nobody cares because SDAG is > undocumented, so anything goes down there? > > > On Tue, Feb 26, 2019 at 2:06 PM John Regehr via llvm-dev < > llvm-dev at lists.llvm.org<mailto:llvm-dev at lists.llvm.org>> wrote: > >> > Transforms/InstCombine/select.ll >> > ===============================>> > define i1 @trueval_is_true(i1 %C, i1 %X) { >> > %R = select i1 %C, i1 1, i1 %X >> > ret i1 %R >> > } >> > => >> > define i1 @trueval_is_true(i1 %C, i1 %X) { >> > %R = or i1 %C, %X >> > ret i1 %R >> > } >> > ERROR: Target is more poisonous than source (when %C = #x1 & %X = poison) >> > >> > (there are many variations of these select->arithmetic transformations) >> >> This particular little family of transformations can be reliably done by >> all of the backends I looked at, so disabling them at the IR level >> should be OK. See a bit more discussion here: >> >> > https://bugs.llvm.org/show_bug.cgi?id=40768 >> >> John-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20190227/2223f3a1/attachment.html>