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

[Steve Montgomery]

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