This is an archive of the discontinued LLVM Phabricator instance.

[RISCV] Optimize emission of SELECT sequences
ClosedPublic

Authored by luismarques on Mar 14 2019, 4:08 AM.

Details

Summary

This patch optimizes the emission of a sequence of SELECTs with the same
condition, avoiding the insertion of unnecessary control flow. Such a sequence
often occurs when a SELECT of values wider than XLEN is legalized into two
SELECTs with legal types. We have identified several use cases where the
SELECTs could be interleaved with other instructions. Therefore, we extend the
sequence to include non-SELECT instructions if we are able to detect that the
non-SELECT instructions do not impact the optimization.
This patch supersedes https://reviews.llvm.org/D59096, which attempted to
address this issue by introducing a new SelectionDAG node. Hat tip to Eli
Friedman for his feedback on how to best handle this issue.

Diff Detail

Repository
rL LLVM

Event Timeline

luismarques created this revision.Mar 14 2019, 4:08 AM
Herald added a project: Restricted Project. · View Herald TranscriptMar 14 2019, 4:08 AM
luismarques edited the summary of this revision. (Show Details)Mar 14 2019, 4:37 AM

Thanks @luismarques

Looks good to me, just a minor suggestion above.

lib/Target/RISCV/RISCVISelLowering.cpp
839 ↗(On Diff #190589)

The coding standards suggests not to evaluate ->end() at each iteration. Given that SequenceMBBI is dead after this loop, perhaps you can rewrite the loop like this (warning, untested code might not compile nor work!)

for (auto E = BB->end(), SequenceMBBI = skipDebugInstructionsForward(
                             MachineOperand::iterator(MI), E);
     SequenceMBBI != E;
     SequenceMBBI = skipDebugInstructionsForward(std::next(SequenceMBBI), E)) {
   ...
}

That would imply removing the final ++SequenceMBBI, too.

Alternative to calling skipDebugInstructionForward, you might just evaluate SequenceMBBI->isDebugInstr() inside of the loop and just continue which would simplify the for even further.

luismarques updated this revision to Diff 191037.EditedMar 17 2019, 12:40 PM

Updated with the suggestions made by Roger Ferrer Ibanez. Thanks!

asb added a comment.Mar 17 2019, 10:31 PM

Added a few minor nits. You'll want to add a test for debug info to select-optimize-multiple.mir. I had a quick play with this and https://reviews.llvm.org/P8135 looks like a sensible way to do it.

lib/Target/RISCV/RISCVISelLowering.cpp
876 ↗(On Diff #191037)

"associated with the selects" might be clearer phrasing

902 ↗(On Diff #191037)

The creation of these phi nodes is part of the pseudo select "insertion" process. Perhaps "Create PHIs for the select pseudo-instructions in order to finish the custom insertion." Or really "Create PHIs for all of the select pseudo-instructions." would do.

911 ↗(On Diff #190589)

This inserts PHIs in the opposite order to the original selects. I'd maybe edit the comment at the head of the comment to say "The sequence of PHIs will be in the opposite order to the original selects, but this has no semantic impact".

Adds a MIR test to show that debug instructions are conditionally moved to the tail basic block depending on whether they are associated with select or non-select instructions.

This update changes the patch to emit the PHIs in the order of the select instructions and improves the wording of some comments, as suggested by Alex Bradbury.

asb accepted this revision.Mar 22 2019, 3:39 AM

This looks good to me, and given @rogfer01 indicated he's also happy, I think it's ready to merge. Thanks Luis!

This revision is now accepted and ready to land.Mar 22 2019, 3:39 AM
This revision was automatically updated to reflect the committed changes.