This is an archive of the discontinued LLVM Phabricator instance.

[SelectionDAG][RISCV] Add a SELECT_PARTS SelectionDAG node
AbandonedPublic

Authored by luismarques on Mar 7 2019, 7:51 AM.

Details

Summary

The SELECT_PARTS node is especially useful for targets like RISC-V, ARM Thumb,
MIPSR2, etc. that don't have a native conditional move instruction. In such
targets SELECT is implemented using control flow. When you legalize a SELECT of
double-word values you get two legal SELECTs. In those targets it's easy to end
up with nonoptimal control flow for conditionally moving both parts. Rather
than attempting to do a late stage optimization of that flow, you can lower
such SELECTs to SELECT_PARTS. The targets can then easily lower the
SELECT_PARTS to a pseudo-instruction that only branches once on the condition
code. This patch also includes the RISC-V implementation of such a custom
lowering, and accompanying tests.

Diff Detail

Repository
rL LLVM

Event Timeline

luismarques created this revision.Mar 7 2019, 7:51 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 7 2019, 7:51 AM

I'm not sure generating SELECT_PARTS in type legalization is the best approach. Instead of specifically considering the case of a SELECT whose result is split by legalization exactly once, you could more generally consider DAGs which, after type legalization, contain multiple SELECTs with the same condition.

The x86 backend actually has some code to try improve the lowering for this sort of construct after isel, in cases where there is no native cmov instruction; see X86TargetLowering::EmitLoweredSelect. As written, it's not completely reliable; it depends on the DAG scheduler to schedule the relevant nodes next to each other. Not suggesting that's the best approach, but maybe a useful reference point.

asb added a comment.Mar 7 2019, 12:30 PM

I'm not sure generating SELECT_PARTS in type legalization is the best approach. Instead of specifically considering the case of a SELECT whose result is split by legalization exactly once, you could more generally consider DAGs which, after type legalization, contain multiple SELECTs with the same condition.

The x86 backend actually has some code to try improve the lowering for this sort of construct after isel, in cases where there is no native cmov instruction; see X86TargetLowering::EmitLoweredSelect. As written, it's not completely reliable; it depends on the DAG scheduler to schedule the relevant nodes next to each other. Not suggesting that's the best approach, but maybe a useful reference point.

Thanks Eli. One reason we were drawn to this approach is it seemed a reasonable analogue of the situation with SHL_PARTS. That code has of course been in LLVM for a very very long time, and perhaps would be done another way now, and of course there are other differences.

I hadn't realised X86 made a similar optimisation. Handling it in EmitInstrWithCustomInserter seems a promising approach (or as you suggest, at least something along those lines).

luismarques abandoned this revision.Mar 14 2019, 3:41 AM

I will submit an alternative approach, as suggested by Eli Friedman.