[LLVMdev] [Target] Custom Lowering expansion of 32-bit ISD::SHL, ISD::SHR without barrel shifter

[Steve Montgomery]

Hi Dave,

I wasn't sure whether I was "allowed" to use EXTRACT_ELEMENT either but, as you say, it's used in other targets and it seems to work so I'll stick with it.

No, I didn't use Glue or Chain operands because I'm lowering each shift operation to a single node corresponding to a pseudo-instruction which is expanded into Machineinstrs either by the custom inserter or by a later pass. I think the MSP430 does it in a similar way, the difference being that it always expands shifts using a loop whereas I chose to leave some to be expanded later without use of a loop.

Steve

On 11 Nov 2013, at 06:18, MathOnNapkins . <mathonnapkins at gmail.com> wrote:

> Hi Steve,
> 
> Thanks for confirming that EXTRACT_ELEMENT is something I can use. I had seen it in the generated DAGs but was unsure whether I was "allowed" to use it, if that's the right word. I checked up on it more and indeed the mainstream targets like ARM use that node type in custom lowering code, so that should solve that. Perhaps in the future I might submit a patch for TargetLowering to set whether the target has a barrel shifter, because I believe that should alter the default emitted DAGs considerably. For example, I tried lowering SHL %a, 5 to a series of SHL %a, 1's at one point and the framework somewhat hilariously (to me) recombined them. If CodeGen knew not to do that, it could save some effort for people trying to target instruction sets with this limitation. The only current mainstream target without a barrel shifter, though, is the MSP430, and it's still a bit experimental (though a very helpful example for me at times).
> 
> Could I also ask whether you had to design your shift nodes with Glue or Chain operands? I haven't taken extra that step yet, but I imagine it will be necessary.
> 
> Sincerely,
> ~Dave Waggoner / MathOnNapkins
> 
> 
> On Sun, Nov 10, 2013 at 1:35 PM, Steve Montgomery <stephen.montgomery3 at btinternet.com> wrote:
> I forgot to mention that I used EXTRACT_ELEMENT in my backend to get the high and low parts of an SDValue.
> 
> On 10 Nov 2013, at 17:50, Steve Montgomery <stephen.montgomery3 at btinternet.com> wrote:
> 
> > I had a similar problem with a backend for the 68HC12 family which also has no barrel shifter. Some 68HC12 CPUs support shift for just one of the 16-bit registers and only support rotation on the 2 8-bit subregs of that 16-bit register. That means the only practical solution for 32-bit shifts is to lower to a libcall but my situation for 16-bit shifts sounds similar to yours for 32-bit shifts.
> >
> > I defined pseudo-instructions in my InstrInfo.td that implemented 8 and 16-bit SHL, SRL and SRA with one variant of each for the shift count in a register and another for an immediate shift count. Some shifts by immediate values and all shifts by non-immediate values need to be implemented using a loop so I used a custom inserter. I added a pass to expand the remaining shift pseudos into shift and rotate sequences with masking where required (e.g. replacing SRL x,7 with ROL x,2)
> >
> > I've no idea if that's the best way but it seems to work for me.
> >
> > Steve
> >
> > On 9 Nov 2013, at 21:29, MathOnNapkins . <mathonnapkins at gmail.com> wrote:
> >
> >> Dear All,
> >>
> >> I am trying to custom lower 32-bit ISD::SHL and SHR in a backend for 6502 family CPUs. The particular subtarget has 16-bit registers at most, so a 32-bit result is not legal. Normally, if you mark this as "Legal" or "Expand", then it will expand the node into a more nodes as follows in an example:
> >>
> >> shl i32 %a , 2
> >>
> >> => high_sdvalue = (or (shr %b, 14), (shl %c, 2) )
> >> => low_sdvalue = (shl %b, 2)
> >>
> >> where %b would be the lower 16 bits of %a, and %c is the upper 16 bits of %a.
> >>
> >> Since this target doesn't have a barrel shifter, it would be a huge performance hit to construct the DAG in this way, due to the large number of right shifts). Thus, I wish to mark ISD::SHL/SHR as "Custom" in setOperationAction(), but I'm unsure of how to manually split the 32-bit shiftee SDValue into two 16-bit values. The standard logic in /lib/CodeGen/SelectionDAG/LegalizeTypes.cpp and LegalizeIntegerTypes.cpp has a member function called GetExpandedInteger(). Unfortunately, this is a private method, so I can't gain access to this without hacking on code outside of my target's (/lib/Target/x65 in this case). To be 100% clear, I actually already did attempt this route, and when compiling received an error that GetExpandedInteger was a private method.
> >>
> >> What I would ultimately like to lower this to is probably a 16-bit ISD::SHL_PARTS, which I'd then further lower to a sequence of pairs of { shift left, rotate left through carry} instructions. Example of how that would look in relation to the aforementioned example:
> >>
> >> asl %b
> >> rol %c
> >> asl %b
> >> rol %c
> >>
> >> There doesn't seem to be a set of standard node types analogous to ADD / ADDC / ADDE for shift operations, which is really what I'm after here.
> >>
> >> I would very much appreciate any advice or insight you could provide on this matter.
> >>
> >> Thanks,
> >> ~Dave Waggoner / MathOnNapkins
> >> _______________________________________________
> >> LLVM Developers mailing list
> >> LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> >> http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> >
> >
> > _______________________________________________
> > LLVM Developers mailing list
> > LLVMdev at cs.uiuc.edu         http://llvm.cs.uiuc.edu
> > http://lists.cs.uiuc.edu/mailman/listinfo/llvmdev
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.llvm.org/pipermail/llvm-dev/attachments/20131111/25c1d6c0/attachment.html>