Hendrik Greving via llvm-dev
2020-Jul-20 14:44 UTC
[llvm-dev] Selection DAG chain question
I did it by code preparing into an intrinsic that has side effects. Pseudo instruction would work as well. I'm not sure if glue would help, since the nodes A->B, C->D from example above are not necessarily adjacent. More hooks into the selection DAG builder may be an idea for a LLVM extension. For example in this case, custom allowing for a node to be built with an existing chain would have been helpful. On Fri, Jul 17, 2020 at 11:06 AM Craig Topper via llvm-dev < llvm-dev at lists.llvm.org> wrote:> Chains represent a dependency between nodes that can't be represented by a > data dependency. For example a load following a store that might alias with > the address of the load. The store must happen before the load. So the > load's chain input is dependent on the store's chain output either > directly or through other intermediate nodes that also have chain inputs > and outputs. There can be multiple chains in parallel in the DAG. > TokenFactor nodes are used to merge separate chains. The InstrEmitter > ensures that the chain dependency is satisfied when emitting the linear > instruction sequence after isel. But nothing guarantees that parallel > chains won't be interleaved. After a node is schedule all of the nodes > dependent on it either through data or chain are checked to see if they are > now ready to schedule. The scheduler will pick from the ready to schedule > nodes without any concern for whether they were on the same chain as the > last node scheduled. > > Glue is stricter, it says that two nodes must be scheduled adjacent to > each other in the linear instruction sequence. > > ~Craig > > > On Fri, Jul 17, 2020 at 10:46 AM Rotate Right via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> newbee here. What's the difference between glue and chain? >> Why can't we add chains to any node we want? >> >> On Fri, Jul 17, 2020, 10:25 PM Björn Pettersson A via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> Still sounds to me as Glue might help (as already proposed by Craig), >>> but maybe I’ve misunderstood something. >>> >>> >>> >>> Another option is to do a simple lowering into pseudo instructions that >>> you expand after ISel. >>> >>> (might be easier than doing something before ISel and then having to >>> bother about chains, glue etc) >>> >>> >>> >>> Regards, >>> >>> Björn >>> >>> >>> >>> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of *Hendrik >>> Greving via llvm-dev >>> *Sent:* den 16 juli 2020 23:35 >>> *To:* Matt Arsenault <arsenm2 at gmail.com> >>> *Cc:* llvm-dev <llvm-dev at lists.llvm.org> >>> *Subject:* Re: [llvm-dev] Selection DAG chain question >>> >>> >>> >>> Yea. I think AMD chains the node they're expanding into, but they don't >>> chain it into an _existing_ chain. e.g. adding A->B to the DAG is ok. But >>> adding A->B and next C->D with B->C is the problem. I appreciate the input >>> >>> >>> >>> On Thu, Jul 16, 2020 at 2:04 PM Matt Arsenault <arsenm2 at gmail.com> >>> wrote: >>> >>> >>> >>> > On Jul 16, 2020, at 17:00, Hendrik Greving <hgreving at google.com> >>> wrote: >>> > >>> > > No, non-sideeffecting operations can be legalized as compiler-rt >>> calls >>> > >>> > Right, but not as "regular" nodes with side-effects? I guess you could >>> search and analyze the DAG manually but that seems hacky. Maybe something >>> that one day LLVM could support natively. >>> >>> >>> You can’t add arbitrary chains or glue to the regular nodes, but you can >>> define a custom node you select the same way with your chain/glue. You >>> don’t need to preprocess the IR and can do in the custom lowering. This is >>> what AMDGPU does for FDIV (see AMDGPUISD::FMA_W_CHAIN). GlobalISel avoids >>> these complications by not having nodes or chains, and just instructions >>> with side effects, so in that sense this is a solved problem. >>> >>> -Matt >>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200720/41b6cadd/attachment.html>
It sounds like this is effectively the divmod instruction writes to two special-purpose internal registers, which the div_consume and mod_consume instructions read. If those two special-purpose registers could be read/written, then you could actually model it that way, treat them as normal registers written by the first instruction and read by the latter 2. They could be spilled/restored as required. However, it seems probable that there is no instruction to write a value to these internal registers. In such a case, typically you'd expand the UDIVREM operation into 3 instructions, all attached to each-other with GLUE, so that other things cannot be inserted in between and mess up the secret handshake. You say you don't want to do that, but didn't say why. That would surely be the most straightforward implementation. On Mon, Jul 20, 2020 at 10:45 AM Hendrik Greving via llvm-dev < llvm-dev at lists.llvm.org> wrote:> I did it by code preparing into an intrinsic that has side effects. Pseudo > instruction would work as well. I'm not sure if glue would help, since the > nodes A->B, C->D from example above are not necessarily adjacent. > > More hooks into the selection DAG builder may be an idea for a LLVM > extension. For example in this case, custom allowing for a node to be built > with an existing chain would have been helpful. > > On Fri, Jul 17, 2020 at 11:06 AM Craig Topper via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> Chains represent a dependency between nodes that can't be represented by >> a data dependency. For example a load following a store that might alias >> with the address of the load. The store must happen before the load. So the >> load's chain input is dependent on the store's chain output either >> directly or through other intermediate nodes that also have chain inputs >> and outputs. There can be multiple chains in parallel in the DAG. >> TokenFactor nodes are used to merge separate chains. The InstrEmitter >> ensures that the chain dependency is satisfied when emitting the linear >> instruction sequence after isel. But nothing guarantees that parallel >> chains won't be interleaved. After a node is schedule all of the nodes >> dependent on it either through data or chain are checked to see if they are >> now ready to schedule. The scheduler will pick from the ready to schedule >> nodes without any concern for whether they were on the same chain as the >> last node scheduled. >> >> Glue is stricter, it says that two nodes must be scheduled adjacent to >> each other in the linear instruction sequence. >> >> ~Craig >> >> >> On Fri, Jul 17, 2020 at 10:46 AM Rotate Right via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> newbee here. What's the difference between glue and chain? >>> Why can't we add chains to any node we want? >>> >>> On Fri, Jul 17, 2020, 10:25 PM Björn Pettersson A via llvm-dev < >>> llvm-dev at lists.llvm.org> wrote: >>> >>>> Still sounds to me as Glue might help (as already proposed by Craig), >>>> but maybe I’ve misunderstood something. >>>> >>>> >>>> >>>> Another option is to do a simple lowering into pseudo instructions that >>>> you expand after ISel. >>>> >>>> (might be easier than doing something before ISel and then having to >>>> bother about chains, glue etc) >>>> >>>> >>>> >>>> Regards, >>>> >>>> Björn >>>> >>>> >>>> >>>> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of *Hendrik >>>> Greving via llvm-dev >>>> *Sent:* den 16 juli 2020 23:35 >>>> *To:* Matt Arsenault <arsenm2 at gmail.com> >>>> *Cc:* llvm-dev <llvm-dev at lists.llvm.org> >>>> *Subject:* Re: [llvm-dev] Selection DAG chain question >>>> >>>> >>>> >>>> Yea. I think AMD chains the node they're expanding into, but they don't >>>> chain it into an _existing_ chain. e.g. adding A->B to the DAG is ok. But >>>> adding A->B and next C->D with B->C is the problem. I appreciate the input >>>> >>>> >>>> >>>> On Thu, Jul 16, 2020 at 2:04 PM Matt Arsenault <arsenm2 at gmail.com> >>>> wrote: >>>> >>>> >>>> >>>> > On Jul 16, 2020, at 17:00, Hendrik Greving <hgreving at google.com> >>>> wrote: >>>> > >>>> > > No, non-sideeffecting operations can be legalized as compiler-rt >>>> calls >>>> > >>>> > Right, but not as "regular" nodes with side-effects? I guess you >>>> could search and analyze the DAG manually but that seems hacky. Maybe >>>> something that one day LLVM could support natively. >>>> >>>> >>>> You can’t add arbitrary chains or glue to the regular nodes, but you >>>> can define a custom node you select the same way with your chain/glue. You >>>> don’t need to preprocess the IR and can do in the custom lowering. This is >>>> what AMDGPU does for FDIV (see AMDGPUISD::FMA_W_CHAIN). GlobalISel avoids >>>> these complications by not having nodes or chains, and just instructions >>>> with side effects, so in that sense this is a solved problem. >>>> >>>> -Matt >>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> > _______________________________________________ > LLVM Developers mailing list > llvm-dev at lists.llvm.org > https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200720/46407b8f/attachment.html>
Hendrik Greving via llvm-dev
2020-Jul-21 21:27 UTC
[llvm-dev] Selection DAG chain question
So first, I did solve the problem by code-preparing. Alternatively, I could have used a pseudo-instruction. Secondly, I really appreciate everybody's input nevertheless. Re: " writes to two special-purpose internal registers" Not possible on our machine: not spillable, not arbitrarily writable, ordering constraints. Re: "You say you don't want to do that, but didn't say why" Thinking more about it, I am taking back what I said. I think it would work if there are no surprises. I may even implement and try, it seems better than what I currently have. On Mon, Jul 20, 2020 at 9:12 AM James Y Knight <jyknight at google.com> wrote:> It sounds like this is effectively the divmod instruction writes to two > special-purpose internal registers, which the div_consume and mod_consume > instructions read. If those two special-purpose registers could be > read/written, then you could actually model it that way, treat them as > normal registers written by the first instruction and read by the latter 2. > They could be spilled/restored as required. However, it seems probable that > there is no instruction to write a value to these internal registers. > > In such a case, typically you'd expand the UDIVREM operation into 3 > instructions, all attached to each-other with GLUE, so that other things > cannot be inserted in between and mess up the secret handshake. You say you > don't want to do that, but didn't say why. That would surely be the most > straightforward implementation. > > On Mon, Jul 20, 2020 at 10:45 AM Hendrik Greving via llvm-dev < > llvm-dev at lists.llvm.org> wrote: > >> I did it by code preparing into an intrinsic that has side effects. >> Pseudo instruction would work as well. I'm not sure if glue would help, >> since the nodes A->B, C->D from example above are not necessarily adjacent. >> >> More hooks into the selection DAG builder may be an idea for a LLVM >> extension. For example in this case, custom allowing for a node to be built >> with an existing chain would have been helpful. >> >> On Fri, Jul 17, 2020 at 11:06 AM Craig Topper via llvm-dev < >> llvm-dev at lists.llvm.org> wrote: >> >>> Chains represent a dependency between nodes that can't be represented by >>> a data dependency. For example a load following a store that might alias >>> with the address of the load. The store must happen before the load. So the >>> load's chain input is dependent on the store's chain output either >>> directly or through other intermediate nodes that also have chain inputs >>> and outputs. There can be multiple chains in parallel in the DAG. >>> TokenFactor nodes are used to merge separate chains. The InstrEmitter >>> ensures that the chain dependency is satisfied when emitting the linear >>> instruction sequence after isel. But nothing guarantees that parallel >>> chains won't be interleaved. After a node is schedule all of the nodes >>> dependent on it either through data or chain are checked to see if they are >>> now ready to schedule. The scheduler will pick from the ready to schedule >>> nodes without any concern for whether they were on the same chain as the >>> last node scheduled. >>> >>> Glue is stricter, it says that two nodes must be scheduled adjacent to >>> each other in the linear instruction sequence. >>> >>> ~Craig >>> >>> >>> On Fri, Jul 17, 2020 at 10:46 AM Rotate Right via llvm-dev < >>> llvm-dev at lists.llvm.org> wrote: >>> >>>> newbee here. What's the difference between glue and chain? >>>> Why can't we add chains to any node we want? >>>> >>>> On Fri, Jul 17, 2020, 10:25 PM Björn Pettersson A via llvm-dev < >>>> llvm-dev at lists.llvm.org> wrote: >>>> >>>>> Still sounds to me as Glue might help (as already proposed by Craig), >>>>> but maybe I’ve misunderstood something. >>>>> >>>>> >>>>> >>>>> Another option is to do a simple lowering into pseudo instructions >>>>> that you expand after ISel. >>>>> >>>>> (might be easier than doing something before ISel and then having to >>>>> bother about chains, glue etc) >>>>> >>>>> >>>>> >>>>> Regards, >>>>> >>>>> Björn >>>>> >>>>> >>>>> >>>>> *From:* llvm-dev <llvm-dev-bounces at lists.llvm.org> *On Behalf Of *Hendrik >>>>> Greving via llvm-dev >>>>> *Sent:* den 16 juli 2020 23:35 >>>>> *To:* Matt Arsenault <arsenm2 at gmail.com> >>>>> *Cc:* llvm-dev <llvm-dev at lists.llvm.org> >>>>> *Subject:* Re: [llvm-dev] Selection DAG chain question >>>>> >>>>> >>>>> >>>>> Yea. I think AMD chains the node they're expanding into, but they >>>>> don't chain it into an _existing_ chain. e.g. adding A->B to the DAG is ok. >>>>> But adding A->B and next C->D with B->C is the problem. I appreciate the >>>>> input >>>>> >>>>> >>>>> >>>>> On Thu, Jul 16, 2020 at 2:04 PM Matt Arsenault <arsenm2 at gmail.com> >>>>> wrote: >>>>> >>>>> >>>>> >>>>> > On Jul 16, 2020, at 17:00, Hendrik Greving <hgreving at google.com> >>>>> wrote: >>>>> > >>>>> > > No, non-sideeffecting operations can be legalized as compiler-rt >>>>> calls >>>>> > >>>>> > Right, but not as "regular" nodes with side-effects? I guess you >>>>> could search and analyze the DAG manually but that seems hacky. Maybe >>>>> something that one day LLVM could support natively. >>>>> >>>>> >>>>> You can’t add arbitrary chains or glue to the regular nodes, but you >>>>> can define a custom node you select the same way with your chain/glue. You >>>>> don’t need to preprocess the IR and can do in the custom lowering. This is >>>>> what AMDGPU does for FDIV (see AMDGPUISD::FMA_W_CHAIN). GlobalISel avoids >>>>> these complications by not having nodes or chains, and just instructions >>>>> with side effects, so in that sense this is a solved problem. >>>>> >>>>> -Matt >>>>> >>>>> _______________________________________________ >>>>> LLVM Developers mailing list >>>>> llvm-dev at lists.llvm.org >>>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>>> >>>> _______________________________________________ >>>> LLVM Developers mailing list >>>> llvm-dev at lists.llvm.org >>>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>>> >>> _______________________________________________ >>> LLVM Developers mailing list >>> llvm-dev at lists.llvm.org >>> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >>> >> _______________________________________________ >> LLVM Developers mailing list >> llvm-dev at lists.llvm.org >> https://lists.llvm.org/cgi-bin/mailman/listinfo/llvm-dev >> >-------------- next part -------------- An HTML attachment was scrubbed... URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20200721/a15e7616/attachment-0001.html>