Page MenuHomePhabricator

[GISel]: Few InsertVecElt combines
ClosedPublic

Authored by aditya_nandakumar on Sep 21 2020, 5:43 PM.

Details

Summary

This adds the following combines that frequently occur

  1. build_vector formation from insert_vectors.
  2. insert_vec_elt(build_vector) -> build_vector

WRT (1), a few more cases need to be handled (such as handling multiple insert_vec_elts to the same index) and I'll try to add them shortly after this.

Also adds pattern matching for insert_vec_elts.

Diff Detail

Event Timeline

There are a very large number of changes, so older changes are hidden. Show Older Changes
Herald added a project: Restricted Project. · View Herald TranscriptSep 21 2020, 5:43 PM
aditya_nandakumar requested review of this revision.Sep 21 2020, 5:43 PM
arsenm added inline comments.Sep 22 2020, 2:25 PM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2425–2426

Should guard against UB out of bounds accesses

2433

BitVector?

llvm/test/CodeGen/AArch64/GlobalISel/combine-insert-vec-elt.mir
43

Should add test with out of bounds constant index

arsenm added inline comments.Sep 22 2020, 2:28 PM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2425–2426

Not actually UB, but undef

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2425–2426

Just to confirm, you mean wrt index(IntImm here)?

arsenm added inline comments.Sep 22 2020, 5:11 PM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2425–2426

Yes, index >= NumElts

aditya_nandakumar marked an inline comment as done.Sep 22 2020, 6:30 PM
aditya_nandakumar added inline comments.
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2433

Removed this. This is not used in this change, but will be in the subsequent one.

Updated to abandon combine if index is out of bounds.

arsenm added inline comments.Sep 23 2020, 5:48 AM
llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
419

SmallVectorImpl for all of these?

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2428

emplace_back?

2432

s/no/number. Couldn't this add undefs for the missing elements?

aditya_nandakumar marked 2 inline comments as done.Sep 23 2020, 9:54 AM
aditya_nandakumar added inline comments.
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2432

I was planning on handling the duplicate as well as missing cases in a follow up commit.

Updated to handle the missing index as well duplicate indices cases.

arsenm added inline comments.Sep 23 2020, 2:42 PM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2415

This could start at any index? Why give up at NumElts - 1?

2437

llvm::sort

2449

Optional doesn't really buy you anything here? You can just use Register()?

2453

I don't think you need to reset the insert point here

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2415

This is poorly attempting to match the highest index (assuming insert_vec_elts are found with increasing indices) so we can collect as many components as possible.
For eg if we traverse top down (like we currently do)

a = insert_vec_elt undef, x, 0
b = insert_vec_elt a, y, 1

We'll turn a into

a = build_vector x, undef
b = insert_vec_elt a, y, 1

Subsequently the insert_vec_elt(build_vec) combine would turn this into

b = build_vector x, y

Instead starting with b would give the build_vector in one shot.

Maybe the better option to do is check if the current insert_vec_elt is used by insert_vec_elts and bail out.

2437

Will do.

2449

Will update.

2453

I'm not resetting. I'm making sure it's set correctly (MI) so I can insert IMPLICIT_DEFs.

arsenm added inline comments.Sep 23 2020, 3:23 PM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2453

Oh, actually this is modifying the MIR in the match function which seems like a problem. Can you defer this to apply?

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2453

Updated.

Insert undef during the apply phase instead of the match as mentioned in the feedback.

s/std::sort/llvm::sort

Also missed some unstaged changes locally
s/push_back/emplace_back

arsenm added inline comments.Sep 29 2020, 7:45 AM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2415

It looks like the DAG handles this by separately canonicalizing the order of a pair of insert_vector_elts (it also seems to produce build_vector one element at a time, but I guess it makes sense to reduce the number of steps here)

2470

Braces

aditya_nandakumar marked an inline comment as done.

Address latest comments by Matt

foad added a subscriber: foad.Sep 30 2020, 5:00 AM
foad added inline comments.
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2413

Everything after this point looks way overcomplicated and could be replaced with something like:

MatchInfo.resize(NumElts);
while (mi_match(
    CurrInst->getOperand(0).getReg(), MRI,
    m_GInsertVecElt(m_MInstr(TmpInst), m_Reg(TmpReg), m_ICst(IntImm)))) {
  if (IntImm >= NumElts)
    return false;
  if (!MatchInfo[IntImm])
    MatchInfo[IntImm] = TmpReg;
  CurrInst = TmpInst;
}
return TmpInst->getOpcode() == TargetOpcode::G_IMPLICIT_DEF;
2491

Don't you have to defend against *IdxCst being out of range here too?

foad added inline comments.Sep 30 2020, 7:11 AM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2415

Maybe the better option to do is check if the current insert_vec_elt is used by insert_vec_elts and bail out.

Right, I think checking whether the current MI has a single use that is another eligible INSERT_VECTOR_ELT would work.

foad added a comment.Oct 14 2020, 3:09 AM

Reverse ping! If you just don't have time to work on this, I'd be interested in commandeering the "insert_vec_elt(build_vector) -> build_vector" part.

Reverse ping! If you just don't have time to work on this, I'd be interested in commandeering the "insert_vec_elt(build_vector) -> build_vector" part.

Sorry - your previous comment got lost in my mailbox. Update coming up.

Address Jay's comments.

foad added inline comments.Oct 14 2020, 10:49 AM
llvm/include/llvm/CodeGen/GlobalISel/MIPatternMatch.h
400

"Ternary" is the normal word for this.

llvm/include/llvm/CodeGen/GlobalISel/MIPatternMatch.h
400

Can do. Anything else besides this?

foad added inline comments.Oct 15 2020, 1:37 AM
llvm/include/llvm/Target/GlobalISel/Combine.td
496

Line length.

524

Line length.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2434

It seems like it would be very easy to handle G_BUILD_VECTOR here as well as G_IMPLICIT_DEF. Then it will handle a chain of G_INSERT_VECTOR_ELT ending in a G_BUILD_VECTOR, with no need for a separate match function. Win-win?

llvm/include/llvm/Target/GlobalISel/Combine.td
496

Can do.

524

Can do.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2434

While it's easy to do, I think it's important to not cram too many combines into one combine. IIUC, the goal with the current table gen wrapper/split is for us to be able to declare/express the same combines/matching ability with the new Combiner table gen framework. So conceptually we probably want to keep them separate for more match function/expressibility test cases for the new combiner (I guess how to separate is quite arbitrary at this point).
TLDR; I can certainly update this, but do we want to cram many peephole combines into one?

foad added inline comments.Oct 15 2020, 2:08 PM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2434

I see it as logically a single combine, which happens to handle "undef" sources as well as real build_vectors. I can't imagine why you'd want to split it into two and have it run twice as slow.

Updates as requested.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2434

In general it's possible to merge multiple combines into one c++ function and make the implementation simpler. However what's logically together is subjective.
In any case, I've updated as requested so we can get this in.

foad accepted this revision.Oct 23 2020, 1:54 AM

LGTM, thanks! Just a load of optional nits inline.

llvm/include/llvm/CodeGen/GlobalISel/CombinerHelper.h
421

Nit: make the "match" and "apply" function names match, now that they are one-to-one?

llvm/include/llvm/Target/GlobalISel/Combine.td
483

Nit: since you have given this a generic name, there are probably other places in this file that could make use of it instead of defining their own matchdata.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2412

Nit: the assert seems redundant since getNumElements will do it for you.

2429

Nit: I don't think you even need the .isValid() here, do you?

2434

Agreed it's subjective, but for compile time reasons I prefer to simplify the implementation unless there's a really good conceptual reason to separate it.

2451

Nit: could inline this into its only caller.

2459

Nit: don't need the .isValid() ?

This revision is now accepted and ready to land.Oct 23 2020, 1:54 AM
llvm/include/llvm/Target/GlobalISel/Combine.td
483

I'll clean them all up in a follow up NFC commit.

llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2451

This attempts to just cache UNDEFs without relying on CSE mechanism.

foad added inline comments.Oct 28 2020, 1:31 PM
llvm/lib/CodeGen/GlobalISel/CombinerHelper.cpp
2451

I'm saying the function (lambda) GetUndef is only caled once, so there's no real need for it to be a separate function.