Page MenuHomePhabricator

[InstCombine] Narrow type of logical operation chains in certain cases
Changes PlannedPublic

Authored by mnadeem on Tue, Sep 14, 8:33 PM.

Details

Summary

Reassociate chains of
extend(X) | (extend(Y) | Z) --> (extend(X) | extend(Y)) | Z
which will then get optimized to --> extend(X | Y) | Z

Allows performing operations with a higher vector factor when vectorized.
https://alive2.llvm.org/ce/z/ha4JJC

Diff Detail

Unit TestsFailed

TimeTest
60 msx64 windows > LLVM.Transforms/InstCombine::and-xor-or.ll
Script: -- : 'RUN: at line 2'; c:\ws\w8\llvm-project\premerge-checks\build\bin\opt.exe < C:\ws\w8\llvm-project\premerge-checks\llvm\test\Transforms\InstCombine\and-xor-or.ll -instcombine -S | c:\ws\w8\llvm-project\premerge-checks\build\bin\filecheck.exe C:\ws\w8\llvm-project\premerge-checks\llvm\test\Transforms\InstCombine\and-xor-or.ll

Event Timeline

mnadeem created this revision.Tue, Sep 14, 8:33 PM
mnadeem requested review of this revision.Tue, Sep 14, 8:33 PM
Herald added a project: Restricted Project. · View Herald TranscriptTue, Sep 14, 8:33 PM
mnadeem edited the summary of this revision. (Show Details)Tue, Sep 14, 8:39 PM
mnadeem added reviewers: spatel, lebedev.ri, nikic.

Please

  1. Reduce the tests - they should only contain the minimal needed pattern - two extends and two logical ops.
  2. Add tests with extra uses - this fold can not be performed when the existing logical ops have other uses.
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1635–1638
1639–1641

You should create the inner op with Builder,
and outer BinaryOperator::Create, and just return latter.

mnadeem updated this revision to Diff 373368.Fri, Sep 17, 4:43 PM
mnadeem retitled this revision from [InstCombine] Narrow type of logical operation chains where one side is an extend to [InstCombine] Narrow type of logical operation chains when possible.

Address comments.

mnadeem marked 2 inline comments as done.Fri, Sep 17, 4:44 PM

Please precommit the tests

mnadeem updated this revision to Diff 373429.Sat, Sep 18, 11:41 AM

rebase on precommited tests

lebedev.ri added inline comments.Sun, Sep 19, 8:08 AM
llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1638

Wait, why are you checking that I, the root instruction, is a single-use?

I think I looked at this as a problem for -reassociate a long time ago. It makes changes on larger patterns like:
https://alive2.llvm.org/ce/z/UD56tJ
...but misses the shorter sequences.

(and this patch would not help match that example in -instcombine alone IIUC)

I think this patch also misses cases where we have a logic op with a wide constant:
https://alive2.llvm.org/ce/z/Ls8hXZ

Do you plan to extend it to deal with those patterns too?

mnadeem updated this revision to Diff 373769.Mon, Sep 20, 7:24 PM
mnadeem marked an inline comment as done.
mnadeem retitled this revision from [InstCombine] Narrow type of logical operation chains when possible to [InstCombine] Narrow type of logical operation chains in certain cases.

remove base instruction's check for one use

mnadeem added a comment.EditedMon, Sep 20, 7:25 PM

I think I looked at this as a problem for -reassociate a long time ago. It makes changes on larger patterns like:
https://alive2.llvm.org/ce/z/UD56tJ
...but misses the shorter sequences.

(and this patch would not help match that example in -instcombine alone IIUC)

I think this patch also misses cases where we have a logic op with a wide constant:
https://alive2.llvm.org/ce/z/Ls8hXZ

Do you plan to extend it to deal with those patterns too?

I shouldn't have given this revision a general title, I was only targeting a specific case i.e. extend(X) | (extend(Y) | Z)

But your first case can probably be handled in instcombine like this (I havent tested this though):

// %conv1 = sext i4 %c to i6
// %conv2 = sext i4 %d to i6
// %or1 = or i6 %conv1, %a
// %or2 = or i6 %conv2, %b
// %or3 = or i6 %or1, %or2
// to
// %conv1 = sext i4 %c to i6
// %conv2 = sext i4 %d to i6
// %or1 = or i6 %conv1, %conv2 --> will later be converted to extend (or i4 ...)
// %or2 = or i6 %a, %b
// %or3 = or i6 %or1, %or2
Instruction *InstCombinerImpl::reassosNestedCastedBitwiseLogic(BinaryOperator &I) {
  auto LogicOpc = I.getOpcode();
  assert(I.isBitwiseLogicOp() && "Unexpected opcode for bitwise logic instcombine");

  auto *Op0 = dyn_cast<BinaryOperator>(I.getOperand(0));
  auto *Op1 = dyn_cast<BinaryOperator>(I.getOperand(1));
  if (!Op0 || !Op1)
    return nullptr;
  if (Op0->getOpcode() != Op1->getOpcode() || Op0->getOpcode() != LogicOpc)
    return nullptr;
  if (match(Op0, m_OneUse(m_c_BinOp(m_CombineAnd(m_ZExtOrSExt(m_Value()), m_Value(A)), m_Value(B)))) &&
      match(Op1, m_OneUse(m_c_BinOp(m_CombineAnd(m_ZExtOrSExt(m_Value()), m_Value(C)), m_Value(D))))) {
    Value *OrWithExtends = Builder.CreateBinOp(LogicOpc, A, Z);
    Value *OrWithOutExtends = Builder.CreateBinOp(LogicOpc, B, D);
    return BinaryOperator::Create(LogicOpc, NewOp, Z);
  }
  return nullptr;
}

I shouldn't have given this revision a general title, I was only targeting a specific case i.e. extend(X) | (extend(Y) | Z)

No problem - I was just wondering if you had a more general solution in mind. We handle some of the most basic reassociation patterns in instcombine already, so this patch seems fine to me.

if (match(Op0, m_OneUse(m_c_BinOp(m_CombineAnd(m_ZExtOrSExt(m_Value()), m_Value(A)), m_Value(B)))) &&
    match(Op1, m_OneUse(m_c_BinOp(m_CombineAnd(m_ZExtOrSExt(m_Value()), m_Value(C)), m_Value(D))))) {

On the other hand, this is probably going too far. We can keep adding logic ops to the chain to move the casts further and further apart, and there's no realistic way to bring them back together in instcombine. That's the job of the -reassociate pass.

llvm/lib/Transforms/InstCombine/InstCombineAndOrXor.cpp
1613

It's not clear to me why this swap is necessary. Do you have a test case where a logic binop has a cast as operand 0 and a binop as operand 1? Complexity-based canonicalization is supposed to prevent that. See InstCombinerImpl::SimplifyAssociativeOrCommutative().

llvm/test/Transforms/InstCombine/and-xor-or.ll
474

I think we're missing tests:

  1. Negative test with different logic opcodes.
  2. Negative test with different cast opcodes.
  3. Test with different cast source types.
  4. Test with multiple uses of cast instruction(s).
  5. Tests where the first cast is operand 1 of the logic op (notice in the original tests that the operands are commuted from where they started - search around the test directory for "thwart complexity-based canonicalization" for ways to prevent that).
mnadeem planned changes to this revision.Tue, Sep 21, 10:07 AM