[PowerPC] Exploit the rldicl + rldicl when and with mask

[steven.zhang]

Summary

If we are and the constant like 0xFFFFFFC00000, for now, we are using several instructions to generate this 48bit constant and final an "and". However, we could exploit it with two rotate instructions.

       MB          ME               MB+63-ME 
+----------------------+     +----------------------+
|0000001111111111111000| ->  |0000000001111111111111|
+----------------------+     +----------------------+
 0                    64      0                    64

Rotate left ME + 1 bit first, and then, mask it with (MB + 63 - ME, 63), finally, rotate back. Notice that, we need to round it with 64 bit for the wrapping case.

[steven.zhang]

Rebase the patch. Testing with spec and get about ~4k instructions reduce.

[steven.zhang]

Rebase the patch.

[steven.zhang]

ping

[steven.zhang]

ping

[steven.zhang]

ping

[shchenz]

Sorry for the delayed comments.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4368

andis. in .td handles 0xABCD0000 u32imm, will this makes this kind imm worse?

4380

s/64/63?

4384

ME could be 63, putting 63 + 1 here seems unreasonable.

4391

I personally think the logic for the special case is a little hard to follow.
I guess you want to convert the following imm: 0x00ffffffffff00ff,

can we first treat it as imm' 0xffffffffffff00ff? and we can call normal case like above, then we get

Val = SDValue(CurDAG->getMachineNode(PPC::RLDICL, Loc, MVT::i64, Val,
                                         getI64Imm(ME + 1, Loc),
                                         getI64Imm((MB + 63 - ME) & 63, Loc)),

SDValue Ops[] = {Val, getI64Imm(63 - ME, Loc), getI64Imm(0, Loc)};
CurDAG->SelectNodeTo(N, PPC::RLDICL, MVT::i64, Ops);

Notice that the second rldicl for above normal case has no clear operation, so its mb is 0, can we add the clear for the highest 8 bits here?
Make a call for above normal case and then clear the highest bits in the second rldicl?

4397

MB can be calculated after checking ME is valid?

4398

check last bit is 1? Is it too complicated to call countTrailingZeros?

4402

ME is always 63? Why not use 63 directly?

4420

s/32/31, s/64/63

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4391

No. The pattern is: 0x00fff00ff000. The idea is to calculate the position of [MB1, ME1] for fff, and [MB2, ME2] for ff. Then, use two rotate clear instructions to do the calculation,

4398

The last bit doesn't necessary to be 1. We need to get the number of trailing 0's.

4402

There won't be performance difference between the two. Use ME to make the logic clear.

[steven.zhang]

oops, we indeed could simplify the logic here.

[steven.zhang]

Address comments.

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4368

No. It will be caught by single rlwinm if it is the pattern that this patch matches.

4391

In fact, both works. The pattern is 0x00fff00fff. Update the patch to make it more clear.

4398

Good point. In fact, we don't need the check here as the isRunOfOnes64 will check it for us.

[shchenz]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4395

For special case, form a new Imm, like:

APInt Res(64, Imm64);                                                                                                                                
ClearBits = Res.countLeadingZeros();                                                                                                                 
if (ClearBits != 0) {                                                                                                                                
  // change pattern |0001111100000011111111|                                                                                                         
  //                       to |1111111100000011111111|                                                                                                         
  APInt Mask = APInt::getBitsSet(64, 64 - ClearBits, 64);                                                                                            
  Res = Res | Mask;                                                                                                                                  
  Imm64 = Res.getZExtValue();                                                                                                                        
}

And pass new Imm64 and ClearBits to normal case, I think logic here maybe a little simple?

[steven.zhang]

Address comments.

[steven.zhang]

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4395

Good suggestion.

[shchenz]

LGTM. Please hold on some days in case other reviewers have comments.

[nemanjai]

I think this would be immensely more readable if you use more descriptive names for variables. It is very hard to get this bit manipulation right in ones head so I really think you should try your best to make this as simple to follow as possible:

1. You use one mask in on line 4463 and then a different one on 4476. Please don't do this. Stick with a consistent example.
2. Rename RotateRightClearLeft to something like RightJustifyRangeAndClear as it appears that is what the function is doing.
3. Get rid of all the expressions involving ME/MB - especially things like <imm> +/- MB/ME as they are very difficult to reason about. For readability, favour defining temporary values just so they would have a name. For example: MB+63-ME is kind of meaningless to a reader. But if you do something like unsigned FirstBitSetWhenRightJustified = MB + 63 - ME; that is now much easier to follow. I realize that we are creating single-use temporaries this way, but I really think it is worth it for readability.

The algorithm appears to be something along the lines of:

if (!MaskIsTwoContiguousRunsOfOnes)
  return
// Add Missing Bits On Left To The Mask
// Right Justify Mask And Clear Bits Formerly In The Middle
// Rotate Back And Clear Bits Previously Added On Left

And I think the comments, function names and variable names should make it clear that this is what is happening.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

4373

I think it is confusing for a function called RotateRightClearLeft to emit a "Rotate Left Clear Left"

[steven.zhang]

In D71831#1936489, @nemanjai wrote:

I think this would be immensely more readable if you use more descriptive names for variables. It is very hard to get this bit manipulation right in ones head so I really think you should try your best to make this as simple to follow as possible:

1. You use one mask in on line 4463 and then a different one on 4476. Please don't do this. Stick with a consistent example.

Good catch.

2. Rename RotateRightClearLeft to something like RightJustifyRangeAndClear as it appears that is what the function is doing.

In ISA, the RLDICL is named as: "Rotate Left Doubleword Immediate then Clear Left". I am not sure if the right justify range make it more clear. Regarding to left or right, it is just a wrap rotate. The lambda here is trying to hide the detail that implement the right rotate with left rotate. Personally, I prefer the RotateRightClearLeft one, but also ok to the RightJustifyRangeAndClear if you insist.

3. Get rid of all the expressions involving ME/MB - especially things like <imm> +/- MB/ME as they are very difficult to reason about. For readability, favour defining temporary values just so they would have a name. For example: MB+63-ME is kind of meaningless to a reader. But if you do something like unsigned FirstBitSetWhenRightJustified = MB + 63 - ME; that is now much easier to follow. I realize that we are creating single-use temporaries this way, but I really think it is worth it for readability.

It is always a balance :) Agree that use the temp variable here as the rotate logic is indeed hard to follow.

The algorithm appears to be something along the lines of:

if (!MaskIsTwoContiguousRunsOfOnes)
  return
// Add Missing Bits On Left To The Mask
// Right Justify Mask And Clear Bits Formerly In The Middle
// Rotate Back And Clear Bits Previously Added On Left

And I think the comments, function names and variable names should make it clear that this is what is happening.

That is nice. Thank you.

[steven.zhang]

Address comments.

[steven.zhang]

@nemanjai Any more comments ?

[nemanjai]

In D71831#1938331, @steven.zhang wrote:

In D71831#1936489, @nemanjai wrote:

2. Rename RotateRightClearLeft to something like RightJustifyRangeAndClear as it appears that is what the function is doing.

In ISA, the RLDICL is named as: "Rotate Left Doubleword Immediate then Clear Left". I am not sure if the right justify range make it more clear. Regarding to left or right, it is just a wrap rotate. The lambda here is trying to hide the detail that implement the right rotate with left rotate. Personally, I prefer the RotateRightClearLeft one, but also ok to the RightJustifyRangeAndClear if you insist.

I think we can retire this discussion quite easily by just removing the lambda. There isn't a whole lot of point to a lambda that is used only once. If it helped with readability I would be in favour of it, but I think it actually makes the code less readable.

In any case, I described the concise algorithm in pseudo-code not so much because I think it is a useful comment, but because I think that is how the function should flow. For example, isn't something like this much more readable:

bool PPCDAGToDAGISel::tryAsPairOfRLDICL(SDNode *N) {
  assert(N->getOpcode() == ISD::AND && "ISD::AND SDNode expected");
  uint64_t Imm64;

  // Do nothing if it is 16-bit imm as the pattern in the .td file handles
  // it well with "andi.".
  if (!isInt64Immediate(N->getOperand(1).getNode(), Imm64) || isUInt<16>(Imm64))
    return false;

  SDLoc Loc(N);
  SDValue Val = N->getOperand(0);

  // Optimized with two rldicl's as follows:
  // Add missing bits on left to the mask and check that the mask is a
  // wrapped run of ones, i.e.
  // Change pattern |0001111100000011111111|
  //             to |1111111100000011111111|.
  unsigned NumOfLeadingZeros = countLeadingZeros(Imm64);
  if (NumOfLeadingZeros != 0)
    Imm64 |= maskLeadingOnes<uint64_t>(NumOfLeadingZeros);
  unsigned MB, ME;
  if (!isRunOfOnes64(Imm64, MB, ME))
    return false;

  //         ME     MB
  // +----------------------+     +----------------------+
  // |1111111100000011111111| ->  |0000001111111111111111|
  // +----------------------+     +----------------------+
  //  0                    63      0                    63
  // There are ME + 1 ones on the left and (MB - ME + 63) & 63 zeros in between.
  unsigned OnesOnLeft = ME + 1;
  unsigned ZerosInBetween = (MB - ME + 63) & 63;

  // Rotate left by OnesOnLeft (so leading ones are now trailing ones) and clear
  // on the left the bits that are already zeros in the mask.
  Val = SDValue(CurDAG->getMachineNode(PPC::RLDICL, Loc, MVT::i64, Val,
                                       getI64Imm(OnesOnLeft, Loc),
                                       getI64Imm(ZerosInBetween, Loc)),
                0);

  //                                      ME     MB
  // +----------------------+     +----------------------+
  // |0000001111111111111111| ->  |0001111100000011111111|
  // +----------------------+     +----------------------+
  //  0                    63      0                    63
  // Rotate back by 64 - OnesOnLeft to undo previous rotate. Then clear on the
  // left the number of ones we previously added.
  SDValue Ops[] = {Val, getI64Imm(64 - OnesOnLeft, Loc),
                   getI64Imm(NumOfLeadingZeros, Loc)};
  CurDAG->SelectNodeTo(N, PPC::RLDICL, MVT::i64, Ops);
  return true;
}

Note that the above is just a sample of how I think the code should be structured for readability. While I am fairly sure it is semantically equivalent to what you have, I did not carefully verify this.

[steven.zhang]

Make sense. I will update the patch. Thank you for the comments.

[steven.zhang]

Address Nemanjai's comments.

[steven.zhang]

I will upstream this patch if no more comments in several days. Thank you for the nice refactor. (@nemanjai )

[nemanjai]

LGTM. Thanks for your patience. As far as I'm concerned, feel free to commit when you're ready.

llvm/lib/Target/PowerPC/PPCISelDAGToDAG.cpp

if (isInt32Immediate(N->getOperand(1), Imm)) {
     if (isRunOfOnes(Imm, MB, ME) &&
         N->getOperand(0).getOpcode() != ISD::ROTL) {
       SDValue Ops[] = { Val, getI32Imm(0, dl), getI32Imm(MB, dl),
                         getI32Imm(ME, dl) };
       CurDAG->SelectNodeTo(N, PPC::RLWINM, MVT::i32, Ops);
       return true;
     }
     // AND X, 0 -> 0, not "rlwinm 32".
     if (Imm == 0) {
       ReplaceUses(SDValue(N, 0), N->getOperand(1));
       return true;
     }
 
     // ISD::OR doesn't get all the bitfield insertion fun.
     // (and (or x, c1), c2) where isRunOfOnes(~(c1^c2)) might be a
     // bitfield insert.
     if (N->getOperand(0).getOpcode() == ISD::OR &&
         isInt32Immediate(N->getOperand(0).getOperand(1), Imm2)) {
       // The idea here is to check whether this is equivalent to:
       //   (c1 & m) | (x & ~m)
       // where m is a run-of-ones mask. The logic here is that, for each bit in
       // c1 and c2:
       //  - if both are 1, then the output will be 1.
       //  - if both are 0, then the output will be 0.
       //  - if the bit in c1 is 0, and the bit in c2 is 1, then the output will
       //    come from x.
       //  - if the bit in c1 is 1, and the bit in c2 is 0, then the output will
       //    be 0.
       //  If that last condition is never the case, then we can form m from the
       //  bits that are the same between c1 and c2.
       unsigned MB, ME;
       if (isRunOfOnes(~(Imm^Imm2), MB, ME) && !(~Imm & Imm2)) {
         SDValue Ops[] = { N->getOperand(0).getOperand(0),
                             N->getOperand(0).getOperand(1),
                             getI32Imm(0, dl), getI32Imm(MB, dl),
                             getI32Imm(ME, dl) };
         ReplaceNode(N, CurDAG->getMachineNode(PPC::RLWIMI, dl, MVT::i32, Ops));
         return true;
       }
     }
   } else if (isInt64Immediate(N->getOperand(1).getNode(), Imm64)) {
     // If this is a 64-bit zero-extension mask, emit rldicl.
     if (isMask_64(Imm64)) {
       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 &&
if (isRunOfOnes64(Imm64, MB, ME)) {
         // +----------------------+
         //  0         32         64
         // We can only do it if the MB is larger than 32 and MB <= ME
         // as RLWINM will replace the content of [0 - 32) with [32 - 64) even
         // we didn't rotate it.
         SDValue Ops[] = { Val, getI64Imm(0, dl), getI64Imm(MB - 32, dl),
                           getI64Imm(ME - 32, dl) };
         CurDAG->SelectNodeTo(N, PPC::RLWINM8, MVT::i64, Ops);
-        return true;
       } else {
-        // TODO - handle it with rldicl + rldicl
+        //        MB          ME               MB+63-ME 
+        // +----------------------+     +----------------------+
+        // |0000001111111111111000| ->  |0000000001111111111111|
+        // +----------------------+     +----------------------+
+        //  0                    64      0                    64
+        // Left rotate ME + 1 bit first and then, mask with (MB + 63 - ME, 63),
+        // and then, rotate back.
+        SH = ME + 1;
+        Val = SDValue(CurDAG->getMachineNode(PPC::RLDICL, dl,
+                      MVT::i64, Val, getI64Imm(SH, dl),
+                      getI64Imm((MB + 63 - ME) & 63, dl)), 0);
+        SDValue Ops[] = { Val, getI64Imm(64 - SH, dl),
+                          getI64Imm(0, dl) };
+        CurDAG->SelectNodeTo(N, PPC::RLDICL, MVT::i64, Ops);
       }
+      return true;
     }
   }
 
   return false;
 }
 
 // Select - Convert the specified operand from a target-independent to a
 // target-specific node if it hasn't already been changed.

llvm/test/CodeGen/PowerPC/2016-04-17-combine.ll

 ; RUN: llc -verify-machineinstrs <%s | FileCheck %s
 target datalayout = "e-m:e-i64:64-n32:64"
 target triple = "powerpc64le-unknown-linux-gnu"
 
 ; PR27390 crasher
 
 %typ = type { i32, i32 }
 
 ; On release builds, it doesn't crash, spewing nonsense instead.
-; To make sure it works, check that and is still alive.
-; CHECK: and
+; To make sure it works, check that rldicl is still alive.
+; CHECK: rldicl
 ; Also, in release, it emits a COPY from a 32-bit register to
 ; a 64-bit register, which happens to be emitted as cror [!]
 ; by the confused CodeGen.  Just to be sure, check there isn't one.
 ; CHECK-NOT: cror
 ; Function Attrs: uwtable
 define signext i32 @_Z8access_pP1Tc(%typ* %p, i8 zeroext %type) {
   %b = getelementptr inbounds %typ, %typ* %p, i64 0, i32 1
   %1 = load i32, i32* %b, align 4
   %2 = ptrtoint i32* %b to i64
   %3 = and i64 %2, -35184372088833
   %4 = inttoptr i64 %3 to i32*
   %_msld = load i32, i32* %4, align 4
   %zzz = add i32 %1,  %_msld
   ret i32 %zzz
 }

llvm/test/CodeGen/PowerPC/and-mask.ll

; CHECK-NEXT:    blr
   %and = and i64 %a, -7
   ret i64 %and
 }
 
 ; mask: 0xFFFFFFC00000
 define i64 @test3(i64 %a) {
 ; CHECK-LABEL: test3:
 ; CHECK:       # %bb.0:
-; CHECK-NEXT:    lis 4, 1023
-; CHECK-NEXT:    ori 4, 4, 65535
-; CHECK-NEXT:    sldi 4, 4, 22
-; CHECK-NEXT:    and 3, 3, 4
+; CHECK-NEXT:    rldicl 3, 3, 42, 38
+; CHECK-NEXT:    rotldi 3, 3, 22
 ; CHECK-NEXT:    blr
   %and = and i64 %a, 281474972516352
   ret i64 %and
 }
 
 ; mask: 0xC000000FF
 define i64 @test4(i64 %a) {
 ; CHECK-LABEL: test4: