[PPC] Better codegen for AND, ANY_EXT, SRL sequence

[amehsan]

Summary

This fixes the first issue exposed by PR30483. (See comment 1 in the IR).

First I tried to fix a more general problem in dag combine. I wanted to address all code sequences of shifts and ands, with an extension in the middle. My solution was to bring the extension insn to the beginning of the sequence so the sequence of shifts and ands can be merged together during isel. That approach did not work because this particular sequence is created in target independent dag combine in DAGCombiner::visitSRL.

So alternatively I decided to address this particular sequence in isel. If we encounter similar issues, we can think of a more general solution.

[amehsan]

test/CodeGen/PowerPC/anyext_srl.ll

25

I should probably remove this line :)

[amehsan]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2639

I am not sure if this is always legal. Will check that.

[hfinkel]

Alternatively, we might teach the BitPermutationSelector to look through extends, which would be more general. Had you looked at that?

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2647

We shouldn't speculatively create new nodes if we can avoid it.

test/CodeGen/PowerPC/anyext_srl.ll

2

You need an architecture or a triple here too.

25

Yes, although if you keep the cpu attribute here, you don't need it on the command line.

[amehsan]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2647

Sorry, I am not sure I understand this comment. What is speculative here? I have a i32 and want to convert it to i64. I tried a couple of different options and this sequence was the only one that worked. This appeared in a small kernel that I wrote and included a similar conversion.

[hfinkel]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2647

No, I mean that you're calling getMachineNode here to generate new SDAG nodes; are you sure that when you do this one of the conditions below will match and these will never just end up being garbage collected?

[amehsan]

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

2647

The conditions below and the ones that reaches this line of code are mutually exclusive. Note that this basic block is ended in line 2650. The next condition will not be satisfied (because we have proved that Val.getOpcode() == ISD::ANY_EXTEND and in the next condition they want Val.getOpcode() == ISD::SRL) and we go straight to the line 2665 and generate code.

[amehsan]

In D24924#552610, @hfinkel wrote:

Alternatively, we might teach the BitPermutationSelector to look through extends, which would be more general. Had you looked at that?

There is potentially a more general solution as well. I can call it "bubbling up" any_ext and zero_ext. So for example in the following selection DAG

Optimized type-legalized selection DAG: BB#0 '_Z3fooRK3PB2S1_:entry'
SelectionDAG has 17 nodes:
  t0: ch = EntryToken
              t2: i64,ch = CopyFromReg t0, Register:i64 %vreg0
            t37: i32,ch = load<LD1[%arrayidx.i6](align=8), anyext from i8> t0, t2, undef:i64
              t4: i64,ch = CopyFromReg t0, Register:i64 %vreg1
            t42: i32,ch = load<LD1[%arrayidx.i37](align=8), anyext from i8> t0, t4, undef:i64
          t54: i32 = xor t37, t42
        t55: i32 = srl t54, Constant:i64<3>
      t56: i64 = any_extend t55
    t51: i64 = and t56, Constant:i64<1>
  t20: ch,glue = CopyToReg t0, Register:i64 %X3, t51
  t21: ch = PPCISD::RET_FLAG t20, Register:i64 %X3, t20:1

We can first push any_ext before srl. (This is what I did in my first attempt). But we don't need to stop here. We can then push it before xor and apply (and merge it) to load instructions that feed xor. Given that zero extension is free for PPC loads this is easier than applying the similar idea to sign_extend.

I also played a little bit with BitPermutationSelector. I added the following code to BitPermutationSelector::getValueBits

+    case ISD::ANY_EXTEND: {
+        auto Size = V.getOperand(0).getNode()->getValueType(0).getSizeInBits();
+        DEBUG(dbgs() << "LOC B1\n" << NumBits << "\n" << Size <<"\n" ; );
+        const SmallVector<ValueBit, 64> *InnerBits;
+        std::tie(Interesting, InnerBits) = getValueBits(V.getOperand(0), Size);
+        for (unsigned i = 0; i < Size; ++i)
+          Bits[i] = (*InnerBits)[i];
+        for (unsigned i = Size; i < NumBits; ++i) {
+          Bits[i] = ValueBit(ValueBit::ConstZero);
+        }
+        return std::make_pair(Interesting, &Bits);
+      }
+      break;

This works, but the codegen currently does not generate correct code for i32 to i64 conversions. So more work is needed. As we discussed, this pattern might be special given it is generated in the target independent codegen. So a more general solution may not be needed. So I will add a note to our readme files, with a pointer to this comment, so in future if we need better handling of this opcodes, we follow one of these ideas.

[kbarton]

LGTM

[amehsan]

Commited 284983

lib/Target/PowerPC/PPCISelDAGToDAG.cpp

case ISD::AND: {
     }
     // If this is a 64-bit zero-extension mask, emit rldicl.
     if (isInt64Immediate(N->getOperand(1).getNode(), Imm64) &&
         isMask_64(Imm64)) {
       SDValue Val = N->getOperand(0);
       MB = 64 - countTrailingOnes(Imm64);
       SH = 0;
 
+      if (Val.getOpcode() == ISD::ANY_EXTEND) {
+        auto Op0 = Val.getOperand(0);
+        if ( Op0.getOpcode() == ISD::SRL &&
+           isInt32Immediate(Op0.getOperand(1).getNode(), Imm) && Imm <= MB) {
+
+           auto ResultType = Val.getNode()->getValueType(0);
+           auto ImDef = CurDAG->getMachineNode(PPC::IMPLICIT_DEF, dl,
+                                               ResultType);
+           SDValue IDVal (ImDef, 0);
+
+           Val = SDValue(CurDAG->getMachineNode(PPC::INSERT_SUBREG, dl,
+                         ResultType, IDVal, Op0.getOperand(0),
+                         getI32Imm(1, dl)), 0);
+           SH = 64 - Imm;
+        }
+      }
+
       // If the operand is a logical right shift, we can fold it into this
       // instruction: rldicl(rldicl(x, 64-n, n), 0, mb) -> rldicl(x, 64-n, mb)
       // for n <= mb. The right shift is really a left rotate followed by a
       // mask, and this mask is a more-restrictive sub-mask of the mask implied
       // by the shift.
       if (Val.getOpcode() == ISD::SRL &&
           isInt32Immediate(Val.getOperand(1).getNode(), Imm) && Imm <= MB) {
         assert(Imm < 64 && "Illegal shift amount");

lib/Target/PowerPC/README.txt

 We would not need denote reserved fields in names of instruction formats.
 
 //===----------------------------------------------------------------------===//
 
 Instruction fusion was introduced in ISA 2.06 and more opportunities added in
 ISA 2.07.  LLVM needs to add infrastructure to recognize fusion opportunities
 and force instruction pairs to be scheduled together.
 
+-----------------------------------------------------------------------------
+
+More general handling of any_extend and zero_extend:
+
+See https://reviews.llvm.org/D24924#555306
+

test/CodeGen/PowerPC/anyext_srl.ll

+; RUN: llc -verify-machineinstrs -mtriple=powerpc64le-unknown-linux-gnu \
+; RUN:     -mcpu=pwr8 < %s | FileCheck %s
+
+%class.PB2 = type { [1 x i32], %class.PB1* }
+%class.PB1 = type { [1 x i32], i64, i64, i32 }
+
+; Function Attrs: norecurse nounwind readonly
+define zeroext i1 @foo(%class.PB2* %s_a, %class.PB2* %s_b) local_unnamed_addr {
+entry:
+  %arrayidx.i6 = bitcast %class.PB2* %s_a to i32*
+  %0 = load i32, i32* %arrayidx.i6, align 8, !tbaa !1
+  %and.i = and i32 %0, 8
+  %cmp.i = icmp ne i32 %and.i, 0
+  %arrayidx.i37 = bitcast %class.PB2* %s_b to i32*
+  %1 = load i32, i32* %arrayidx.i37, align 8, !tbaa !1
+  %and.i4 = and i32 %1, 8
+  %cmp.i5 = icmp ne i32 %and.i4, 0
+  %cmp = xor i1 %cmp.i, %cmp.i5
+  ret i1 %cmp
+; CHECK-LABEL: @foo
+; CHECK: rldicl  {{[0-9]+}}, {{[0-9]+}}, 61, 63
+
+}
+
+!1 = !{!2, !2, i64 0}
+!2 = !{!"int", !3, i64 0}
+!3 = !{!"omnipotent char", !4, i64 0}
+!4 = !{!"Simple C++ TBAA"}
+