This is an archive of the discontinued LLVM Phabricator instance.

[InstCombine] Improve select -> phi canonicalization: consider more blocks
ClosedPublic

Authored by mkazantsev on Jul 7 2020, 1:45 AM.

Details

Summary

We can try to replace select with a Phi not in its parent block alone, but also in blocks of its arguments.
We benefit from it when select's argument is a Phi.

Diff Detail

Event Timeline

mkazantsev created this revision.Jul 7 2020, 1:45 AM
Herald added a project: Restricted Project. · View Herald TranscriptJul 7 2020, 1:45 AM

Ideally we could consider all dominator chain, but this is too expensive. This is attempt to reduce the impact.

nikic added inline comments.Jul 7 2020, 11:35 AM
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2518

It seems quite likely that some of the parents (or all of them) are going to be the same. Might it make sense to deduplicate?

// Collect likely candidates for placing the phi node.
SmallPtrSet<BasicBlock *, 4> CandidateBlocks;
CandidateBlocks.insert(Sel.getParent();
for (Value *V : Sel.operands())
  if (auto *I = dyn_cast<Instruction>(V))
    CandidateBlocks.insert(I->getParent());

for (BasicBlock *BB : CandidateBlocks)
  if (auto *PN = foldSelectToPhiImpl(Sel, BB, DT, Builder))
    return PN;
mkazantsev marked an inline comment as done.Jul 9 2020, 11:35 PM
mkazantsev added inline comments.
llvm/lib/Transforms/InstCombine/InstCombineSelect.cpp
2518

Agreed.

Implemented deduplication (used SetVector to ensure that we have deterministic fold order).

mkazantsev marked an inline comment as done.Jul 10 2020, 12:29 AM
nikic added inline comments.Jul 10 2020, 12:46 AM
llvm/test/Transforms/InstCombine/select.ll
2417

I don't understand why this returns %B (and what the difference to the previous test is, for that matter).

mkazantsev marked an inline comment as done.Jul 10 2020, 4:57 AM
mkazantsev added inline comments.
llvm/test/Transforms/InstCombine/select.ll
2417

It actually returns %A, %B here is just a regex name. Seems that I miscopied it on revase, it was supposed to exertice scenario

%sel = select i1 %cond, i32 %A, i32 %phi
mkazantsev marked an inline comment as done.

Fixed var naming in test that went astray after rebase.

mkazantsev marked an inline comment as done.Jul 10 2020, 5:07 AM
mkazantsev added inline comments.
llvm/test/Transforms/InstCombine/select.ll
2417

Fixed the test test_select_into_phi_not_idom_2 and var naming in it. It was supposed to show that we can replace Phi that is a false value of select (the previous test shows when it's a true value).

This revision is now accepted and ready to land.Jul 10 2020, 9:48 AM
This revision was automatically updated to reflect the committed changes.