[InstCombine] Compacting or instructions whose operands are shift instructions

[opaparo]

Summary

Adding two kinds of transformations:

1. Change order of or instructions to group together identical opcodes and constants:
   • (or (or (op1 A C1)(op2 B C2)) (or (op1 D C1)(op2 E C2))) --> (or (or (op1 A C1)(op1 D C1)) (or (op2 B C2)(op2 E C2)))
2. Or of shifts and ands:
   • ((V<<C3)&C1) | ((V<<C4)&C2) --> ((V&C5)<<C3) | ((V&C5)<<C4), if C5 = C1>>C3 == C2>>C4, for both logical shifts
   • ((V&C5)<<C3) | ((V<<C4)&C2) --> ((V&C5)<<C3) | ((V&C5)<<C4)
   • ((V<<C3)&C1) | ((V&C5)<<C4) --> ((V&C5)<<C3) | ((V&C5)<<C4)

For the first transformation note that although op1 and op2 are not limited to shifts, cases where they are shifts will greatly benefit from it.

[craig.topper]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2237

Shift of Ands are canonicalized to And of Shifts unless the 'and' has an additional use. I don't think your test cases cover that.

2255

I don't think there's any reason to make these lambda's "static"

2305

Why the replaceAllUsesWith call? We don't normally do this in InstCombine. Are you trying to replace other uses than this OR? Do you have test cases for that?

[spatel]

I haven't looked much at the reassociation pass, but this seems like something that would be simpler to canonicalize there. Did you look at adding a rule there?

Eg, in the "or_or_shift" test, you have a tree of 'or' ops. If you reassociate those so that similar shifts are paired together, instcombine would manage to fold that using existing patterns (although maybe not optimally yet):

define i32 @or_or_shift(i32 %x) local_unnamed_addr #0  {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = shl nuw nsw i32 %2, 6
  %6 = lshr exact i32 %2, 1
  %7 = or i32 %3, %5    <--- shl with shl
  %8 = or i32 %4, %6    <--- lshr with lshr
  %9 = or i32 %7, %8
  ret i32 %9
}

$ ./opt -instcombine reass.ll -S

define i32 @or_or_shift(i32 %x) local_unnamed_addr {
  %1 = shl i32 %x, 6
  %2 = and i32 %1, 384
  %3 = lshr i32 %x, 1
  %4 = and i32 %3, 3
  %5 = or i32 %2, %4
  ret i32 %5
}

[m_zuckerman]

test/Transforms/InstCombine/or-xor.ll

419

(((x ^ C1) | (y ^ C2)) | ((x | y) & C2)) - > (((x ^ C1) | (y ^ C1)) | ((x | y) & C2))

[opaparo]

1. Removed the lambda MatchShiftOfAnd as Shift of And is canonicalized to And of Shift, so the lambda MatchAndOfShift is sufficient.
2. The lambda MatchAndOfShift is now not static.
3. Removed unnecessary calls to replaceAllUsesWith.
4. Fixed test documentation.

[opaparo]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2237

The lambda MatchShiftOfAnd was indeed unnecessary. I've removed it.

2305

The calls to replaceAllUsesWith were indeed unnecessary. I removed them.

[opaparo]

In D38037#882371, @spatel wrote:

I haven't looked much at the reassociation pass, but this seems like something that would be simpler to canonicalize there. Did you look at adding a rule there?

Eg, in the "or_or_shift" test, you have a tree of 'or' ops. If you reassociate those so that similar shifts are paired together, instcombine would manage to fold that using existing patterns (although maybe not optimally yet):

define i32 @or_or_shift(i32 %x) local_unnamed_addr #0  {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = shl nuw nsw i32 %2, 6
  %6 = lshr exact i32 %2, 1
  %7 = or i32 %3, %5    <--- shl with shl
  %8 = or i32 %4, %6    <--- lshr with lshr
  %9 = or i32 %7, %8
  ret i32 %9
}

$ ./opt -instcombine reass.ll -S

define i32 @or_or_shift(i32 %x) local_unnamed_addr {
  %1 = shl i32 %x, 6
  %2 = and i32 %1, 384
  %3 = lshr i32 %x, 1
  %4 = and i32 %3, 3
  %5 = or i32 %2, %4
  ret i32 %5
}

I've looked into the reassociation pass a bit.
The kind of reassociation I'm interested in is somewhat different than the one implemented in this pass:
The pass takes a tree of a reassociable operator, and transforms it into a "linear tree", e.g. for addition a_0 + (a_1 + (a_2 + ... (a_n-1 + a_n))...). The tree is built such that the latter operands have lower "ranks". The ranking is such that, for example, constants have rank of zero which means they will be at the end of the tree which will cause them to eventually fold.
The kind of reassociation I'm looking for is different and is of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3).
Even when I changed the pass's code such that same-opcode-instructions-tree-operands will be grouped together, I got for my or_or_shift, which is:

define i32 @or_or_shift(i32 %x) local_unnamed_addr #0  {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = or i32 %3, %4
  %6 = shl nuw nsw i32 %2, 6
  %7 = lshr exact i32 %2, 1
  %8 = or i32 %6, %7
  %9 = or i32 %5, %8
  ret i32 %9
}

This output:

define i32 @or_or_shift(i32 %x) local_unnamed_addr {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = shl nuw nsw i32 %2, 6
  %6 = lshr exact i32 %2, 1
  %7 = or i32 %6, %4
  %8 = or i32 %7, %3
  %9 = or i32 %8, %5
  ret i32 %9
}

%7, being the leaf or in the tree, actually does InstCombine nicely. The rest, however, do not.
As I see it, if I wish to embed this change in the reassociation pass, I have two options:

1. Change the reassociation pass code such that the tree's topology will fit my needs.
2. Add more InstCombine code to handle the newly formed structure (Something like (or (or A (op B C1)) (op D C1)) --> (or A (or (op B C1) (op D C1))), which is still a kind of reassociation).

I strongly prefer not to change the reassociation pass's tree topology as I have a feeling it is greatly relied on. And if I add a reassociation to InstCombine, why not add my original one instead of adding that one in addition to the changes in the reassociation pass?

Please let me know your thoughts on this matter.

[spatel]

In D38037#906608, @opaparo wrote:

In D38037#882371, @spatel wrote:

I haven't looked much at the reassociation pass, but this seems like something that would be simpler to canonicalize there. Did you look at adding a rule there?

Eg, in the "or_or_shift" test, you have a tree of 'or' ops. If you reassociate those so that similar shifts are paired together, instcombine would manage to fold that using existing patterns (although maybe not optimally yet):

define i32 @or_or_shift(i32 %x) local_unnamed_addr #0  {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = shl nuw nsw i32 %2, 6
  %6 = lshr exact i32 %2, 1
  %7 = or i32 %3, %5    <--- shl with shl
  %8 = or i32 %4, %6    <--- lshr with lshr
  %9 = or i32 %7, %8
  ret i32 %9
}

$ ./opt -instcombine reass.ll -S

define i32 @or_or_shift(i32 %x) local_unnamed_addr {
  %1 = shl i32 %x, 6
  %2 = and i32 %1, 384
  %3 = lshr i32 %x, 1
  %4 = and i32 %3, 3
  %5 = or i32 %2, %4
  ret i32 %5
}

I've looked into the reassociation pass a bit.
The kind of reassociation I'm interested in is somewhat different than the one implemented in this pass:
The pass takes a tree of a reassociable operator, and transforms it into a "linear tree", e.g. for addition a_0 + (a_1 + (a_2 + ... (a_n-1 + a_n))...). The tree is built such that the latter operands have lower "ranks". The ranking is such that, for example, constants have rank of zero which means they will be at the end of the tree which will cause them to eventually fold.
The kind of reassociation I'm looking for is different and is of the form (a_0 + a_1) + (a_2 + a_3) -> (a_0 + a_2) + (a_1 + a_3).
Even when I changed the pass's code such that same-opcode-instructions-tree-operands will be grouped together, I got for my or_or_shift, which is:

define i32 @or_or_shift(i32 %x) local_unnamed_addr #0  {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = or i32 %3, %4
  %6 = shl nuw nsw i32 %2, 6
  %7 = lshr exact i32 %2, 1
  %8 = or i32 %6, %7
  %9 = or i32 %5, %8
  ret i32 %9
}

This output:

define i32 @or_or_shift(i32 %x) local_unnamed_addr {
  %1 = and i32 %x, 2
  %2 = and i32 %x, 4
  %3 = shl nuw nsw i32 %1, 6
  %4 = lshr exact i32 %1, 1
  %5 = shl nuw nsw i32 %2, 6
  %6 = lshr exact i32 %2, 1
  %7 = or i32 %6, %4
  %8 = or i32 %7, %3
  %9 = or i32 %8, %5
  ret i32 %9
}

%7, being the leaf or in the tree, actually does InstCombine nicely. The rest, however, do not.
As I see it, if I wish to embed this change in the reassociation pass, I have two options:

1. Change the reassociation pass code such that the tree's topology will fit my needs.
2. Add more InstCombine code to handle the newly formed structure (Something like (or (or A (op B C1)) (op D C1)) --> (or A (or (op B C1) (op D C1))), which is still a kind of reassociation).

I strongly prefer not to change the reassociation pass's tree topology as I have a feeling it is greatly relied on. And if I add a reassociation to InstCombine, why not add my original one instead of adding that one in addition to the changes in the reassociation pass?

Please let me know your thoughts on this matter.

Thanks for looking at and explaining Reassociate's current behavior. I don't know what would be best, so cc'ing some others that might have a better idea.

[davide]

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

2291

IMHO, this got a little too far.
FWIW, matchers should look just a few instructions at the time and not whole trees.
Is there a way to split this up or do differently?
I really don't want reassociate to become the next instcombine.

[opaparo]

These changes will be handled by D41233, D39421 and perhaps a few more future changes.

lib/Transforms/InstCombine/InstCombineAndOrXor.cpp

if (Op0->hasOneUse() && Op1->hasOneUse() &&
         match(Op0, m_Select(m_Value(X), m_Value(A), m_Value(B))) &&
         match(Op1, m_Select(m_Value(Y), m_Value(C), m_Value(D))) && X == Y) {
       Value *orTrue = Builder.CreateOr(A, C);
       Value *orFalse = Builder.CreateOr(B, D);
       return SelectInst::Create(X, orTrue, orFalse);
     }
   }
 
+  // ((V<<C3)&C1) | ((V<<C4)&C2) --> ((V&C5)<<C3) | ((V&C5)<<C4)
+  // if C5 = C1>>C3 == C2>>C4, for both logical shifts
+  {
+    auto MatchAndOfShift = [](Value *V, Value *&Source,
+                              Instruction::BinaryOps &ShiftOpcode,
+                              ConstantInt *&ShiftBy, ConstantInt *&PreShiftMask,
+                              ConstantInt *&PostShiftMask,
+                              BinaryOperator *&IntermediateInstr) -> bool {
+      if (!match(V, m_And(m_BinOp(IntermediateInstr),
+                          m_ConstantInt(PostShiftMask))) ||
+          !match(IntermediateInstr,
+                 m_LogicalShift(m_Value(Source), m_ConstantInt(ShiftBy))))
+        return false;
+      ShiftOpcode = IntermediateInstr->getOpcode();
+      Instruction::BinaryOps InverseOpcode =
+          IntermediateInstr->getOpcode() == Instruction::Shl ? Instruction::LShr
+                                                             : Instruction::Shl;
+      PreShiftMask = cast<ConstantInt>(
+          ConstantExpr::get(InverseOpcode, PostShiftMask, ShiftBy));
+      return true;
+    };
+    Value *Source0, *Source1;
+    Instruction::BinaryOps ShiftOpcode0, ShiftOpcode1;
+    ConstantInt *ShiftBy0, *ShiftBy1, *PreShiftMask0, *PreShiftMask1,
+        *PostShiftMask0, *PostShiftMask1;
+    BinaryOperator *IntermediateInstr0, *IntermediateInstr1;
+    if (MatchAndOfShift(Op0, Source0, ShiftOpcode0, ShiftBy0, PreShiftMask0,
+                        PostShiftMask0, IntermediateInstr0) &&
+        MatchAndOfShift(Op1, Source1, ShiftOpcode1, ShiftBy1, PreShiftMask1,
+                        PostShiftMask1, IntermediateInstr1) &&
+        Source0 == Source1) {
+      if (ShiftBy0 == ShiftBy1 && ShiftOpcode0 == ShiftOpcode1) {
+        // ((V<<C3)&C1) | ((V<<C3)&C2) --> (V<<C3)&(C1|C2)
+        unsigned SavedInstructions = Op0->hasOneUse() + Op1->hasOneUse() +
+                                     IntermediateInstr0->hasOneUse() +
+                                     IntermediateInstr1->hasOneUse();
+        if (SavedInstructions >= 2) {
+          Value *Sh = Builder.CreateBinOp(ShiftOpcode0, Source0, ShiftBy0);
+          Constant *Mask = ConstantExpr::get(Instruction::Or, PostShiftMask0,
+                                             PostShiftMask1);
+          return BinaryOperator::CreateAnd(Sh, Mask);
+        }
+      }
+      Value *CommonOperand;
+      if (PreShiftMask0 == PreShiftMask1 &&
+          match(Op0, m_BinOp(m_Value(CommonOperand), m_Value())) &&
+          !match(Op1, m_BinOp(m_Specific(CommonOperand), m_Value())) &&
+          (IntermediateInstr0->hasOneUse() ||
+           IntermediateInstr1->hasOneUse())) {
+        Value *MaskedSource = Builder.CreateAnd(Source0, PreShiftMask0);
+        Value *NewOp0 =
+            Builder.CreateBinOp(ShiftOpcode0, MaskedSource, ShiftBy0);
+        Value *NewOp1 =
+            Builder.CreateBinOp(ShiftOpcode1, MaskedSource, ShiftBy1);
+        return BinaryOperator::CreateOr(NewOp0, NewOp1);
+      }
+    }
+  }
+
+  // (or (or (op1 A C1)(op2 B C2)) (or (op1 D C1)(op2 E C2))) -->
+  // (or (or (op1 A C1)(op1 D C1)) (or (op2 B C2)(op2 E C2)))
+  {
+    BinaryOperator *BinOp00, *BinOp01, *BinOp10, *BinOp11;
+    ConstantInt *C00, *C01, *C10, *C11;
+    if (match(Op0, m_OneUse(m_Or(m_BinOp(BinOp00), m_BinOp(BinOp01)))) &&
+        match(BinOp00, m_BinOp(m_Value(), m_ConstantInt(C00))) &&
+        match(BinOp01, m_BinOp(m_Value(), m_ConstantInt(C01))) &&
+        match(Op1, m_OneUse(m_Or(m_BinOp(BinOp10), m_BinOp(BinOp11)))) &&
+        match(BinOp10, m_BinOp(m_Value(), m_ConstantInt(C10))) &&
+        match(BinOp11, m_BinOp(m_Value(), m_ConstantInt(C11))) &&
+        !(BinOp00->getOpcode() == BinOp01->getOpcode() && C00 == C01) &&
+        !(BinOp10->getOpcode() == BinOp11->getOpcode() && C10 == C11)) {
+      if (BinOp00->getOpcode() == BinOp10->getOpcode() && C00 == C10 &&
+          BinOp01->getOpcode() == BinOp11->getOpcode() && C01 == C11)
+        return BinaryOperator::CreateOr(Builder.CreateOr(BinOp00, BinOp10),
+                                        Builder.CreateOr(BinOp01, BinOp11));
+      if (BinOp00->getOpcode() == BinOp11->getOpcode() && C00 == C11 &&
+          BinOp01->getOpcode() == BinOp10->getOpcode() && C01 == C10)
+        return BinaryOperator::CreateOr(Builder.CreateOr(BinOp00, BinOp11),
+                                        Builder.CreateOr(BinOp01, BinOp10));
+    }
+  }
+
   return Changed ? &I : nullptr;
 }
 
 /// A ^ B can be specified using other logic ops in a variety of patterns. We
 /// can fold these early and efficiently by morphing an existing instruction.
 static Instruction *foldXorToXor(BinaryOperator &I,
                                  InstCombiner::BuilderTy &Builder) {
   assert(I.getOpcode() == Instruction::Xor);

test/Transforms/InstCombine/or-or-shift.ll

+; RUN: opt -S -instcombine < %s | FileCheck %s
+
+; (((A & 2) >> 1) | ((A & 2) << 6)) | (((A & 4) >> 1) | ((A & 4) << 6))
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | (((A & 2) << 6) | ((A & 4) << 6))
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | (((A & 2) | (A & 4)) << 6)
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | ((A & 6) << 6)
+; --> (((A & 2) >> 1) | ((A & 4) >> 1)) | ((A << 6) & 384)
+; --> (((A & 2) | (A & 4)) >> 1) | ((A << 6) & 384)
+; --> ((A & 6) >> 1) | ((A << 6) & 384)
+; --> ((A >> 1) & 3) | ((A << 6) & 384)
+; --> ((A & 6) >> 1) | ((A & 6) << 6)
+
+define i32 @or_or_shift(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @or_or_shift(
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 6
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i32 [[AND]], 6
+; CHECK-NEXT:    [[SHR:%.*]] = lshr exact i32 [[AND]], 1
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], [[SHR]]
+; CHECK-NEXT:    ret i32 [[OR]]
+;
+  %1 = and i32 %x, 2
+  %2 = and i32 %x, 4
+  %3 = shl nuw nsw i32 %1, 6
+  %4 = lshr exact i32 %1, 1
+  %5 = or i32 %3, %4
+  %6 = shl nuw nsw i32 %2, 6
+  %7 = lshr exact i32 %2, 1
+  %8 = or i32 %6, %7
+  %9 = or i32 %5, %8
+  ret i32 %9
+}
+
+define i32 @or_and_shifts1(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @or_and_shifts1(
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 1
+; CHECK-NEXT:    [[SHL1:%.*]] = shl nuw nsw i32 [[AND]], 3
+; CHECK-NEXT:    [[SHL2:%.*]] = shl nuw nsw i32 [[AND]], 5
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL1]], [[SHL2]]
+; CHECK-NEXT:    ret i32 [[OR]]
+;
+  %1 = shl i32 %x, 3
+  %2 = and i32 %1, 15
+  %3 = shl i32 %x, 5
+  %4 = and i32 %3, 60
+  %5 = or i32 %2, %4
+  ret i32 %5
+}
+
+define i32 @or_and_shifts2(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @or_and_shifts2(
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 112
+; CHECK-NEXT:    [[SHL:%.*]] = shl nuw nsw i32 [[AND]], 3
+; CHECK-NEXT:    [[SHR:%.*]] = lshr exact i32 [[AND]], 4
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL]], [[SHR]]
+; CHECK-NEXT:    ret i32 [[OR]]
+;
+  %1 = shl i32 %x, 3
+  %2 = and i32 %1, 896
+  %3 = lshr i32 %x, 4
+  %4 = and i32 %3, 7
+  %5 = or i32 %2, %4
+  ret i32 %5
+}
+
+define i32 @or_and_shift_shift_and(i32 %x) local_unnamed_addr #0  {
+; CHECK-LABEL: @or_and_shift_shift_and(
+; CHECK-NEXT:    [[AND:%.*]] = and i32 %x, 7
+; CHECK-NEXT:    [[SHL1:%.*]] = shl nuw nsw i32 [[AND]], 3
+; CHECK-NEXT:    [[SHL2:%.*]] = shl nuw nsw i32 [[AND]], 2
+; CHECK-NEXT:    [[OR:%.*]] = or i32 [[SHL1]], [[SHL2]]
+; CHECK-NEXT:    ret i32 [[OR]]
+;
+  %1 = and i32 %x, 7
+  %2 = shl i32 %1, 3
+  %3 = shl i32 %x, 2
+  %4 = and i32 %3, 28
+  %5 = or i32 %2, %4
+  ret i32 %5
+}
+

test/Transforms/InstCombine/or-xor.ll

 ;
   %noty = xor i32 %y, -1
   %notx = xor i32 %x, -1
   %or1 = or i32 %notx, %noty
   %or2 = or i32 %y, %x
   %xor = xor i32 %or1, %or2
   ret i32 %xor
 }
+
+; (((x ^ C1) | (x & C2)) | ((y ^ C1) | (y & C2))) ->
+; (((x ^ C1) | (y ^ C1)) | ((x | y) & C2))
+define i32 @or_or_xor_and(i32 %x, i32 %y) local_unnamed_addr #0  {
+; CHECK-LABEL: @or_or_xor_and(
+; CHECK-NEXT:    [[XOR1:%.*]] = xor i32 %x, 15
+; CHECK-NEXT:    [[XOR2:%.*]] = xor i32 %y, 15
+; CHECK-NEXT:    [[OR1:%.*]] = or i32 %x, %y
+; CHECK-NEXT:    [[AND:%.*]] = and i32 [[OR1]], 38
+; CHECK-NEXT:    [[OR2:%.*]] = or i32 [[XOR1]], [[XOR2]]
+; CHECK-NEXT:    [[OR3:%.*]] = or i32 [[OR2]], [[AND]]
+; CHECK-NEXT:    ret i32 [[OR3]]
+;
+  %1 = xor i32 %x, 15
+  %2 = and i32 %x, 38
+  %3 = or i32 %1, %2
+  %4 = xor i32 %y, 15
+  %5 = and i32 %y, 38
+  %6 = or i32 %4, %5
+  %7 = or i32 %3, %6
+  ret i32 %7
+}
 No newline at end of file