[PPC CodeGen] Fix the bitreverse.i64 intrinsic.

[MaskRay]

Summary

The two 32-bit words were swapped. Update a test omitted in reverted r316270.

[jtony]

lib/Target/PowerPC/PPCInstrInfo.td

4670 ↗

(On Diff #119776)

This name is outdated now. Can you go through all the logic here and make sure all the names still make sense (i.e. make sure the name represents what it does) ? To help you understand this code sequence, you can also refer the gcc generated code sequence for the C test case listed in the bug (https://bugs.llvm.org/show_bug.cgi?id=33093). And make sure you run all the LIT/LNT test cases and 3-stage bootstrap and they are all clean.

[MaskRay]

Rename some def to be clearer.

% ~/Dev/llvm/build/bin/llvm-lit test/CodeGen/PowerPC/pr33093.ll test/CodeGen/PowerPC/testBitReverse.ll

• Testing: 2 tests, 2 threads --

PASS: LLVM :: CodeGen/PowerPC/pr33093.ll (1 of 2)
PASS: LLVM :: CodeGen/PowerPC/testBitReverse.ll (2 of 2)
Testing Time: 0.51s

Expected Passes    : 2

% ~/Dev/llvm/build/bin/llvm-lit test/CodeGen/PowerPC/
Testing Time: 10.62s
Expected Passes : 819
Expected Failures : 96

[MaskRay]

@jtony I have renamed Extend Shift to Bytes0123 Bytes3012 ... because I think the new names are clearer.

32-bit __builtin_bitreverse needs a similar change and also I think there is a missing optimization:

def DWBytes0123 {

dag Word = (i32 (EXTRACT_SUBREG (RLDICL DWSwapInByte.Swap4, 32, 32), sub_32));

}

This could be msvsrld (lower doubleword) if Power ISA 3.0 is available. The original fix was my first revision and I did not expect it would take so much to time to fix a bug... I don't know much about .td but I think the`[IsISA3_0]` optimization and bitreverse32 deserve revisions of their own?

[jtony]

In D39163#908211, @MaskRay wrote:

@jtony I have renamed Extend Shift to Bytes0123 Bytes3012 ... because I think the new names are clearer.

32-bit __builtin_bitreverse needs a similar change and also I think there is a missing optimization:

def DWBytes0123 {

dag Word = (i32 (EXTRACT_SUBREG (RLDICL DWSwapInByte.Swap4, 32, 32), sub_32));

}

This could be msvsrld (lower doubleword) if Power ISA 3.0 is available. The original fix was my first revision and I did not expect it would take so much to time to fix a bug... I don't know much about .td but I think the`[IsISA3_0]` optimization and bitreverse32 deserve revisions of their own?

Thanks MaskRay for rewriting the 64 bit reverse, this new patch is way clear than the last patch. Especially, I like the idea using numbers to indicate which state you are for the byte swapping. If you have more optimization for 32 bit, I would leave it to another patch. The community prefers to keep each commit small and focus on one problem. I saw you new patch still passes all the PPC IR test cases, which is good. But we want to run the whole LIT/LNT tests and bootstrap before posting it, could you also do these testing for your patch? Thank you very much for your time and effort for fixing this.

[MaskRay]

% build/bin/llvm-lit test

Failing Tests (29): [6/46367]

  LLVM-Unit :: IR/./IRTests/CGSCCCallbacksTest.PassUtilities                                                                          
  LLVM-Unit :: IR/./IRTests/CGSCCCallbacksTest.Passes                                                                                 
  LLVM-Unit :: IR/./IRTests/FunctionCallbacksTest.AnalysisUtilities                                                                   
  LLVM-Unit :: IR/./IRTests/FunctionCallbacksTest.Passes                                                                              
  LLVM-Unit :: IR/./IRTests/LoopCallbacksTest.PassUtilities                                                                           
  LLVM-Unit :: IR/./IRTests/LoopCallbacksTest.Passes                                                                                  
  LLVM-Unit :: IR/./IRTests/ModuleCallbacksTest.AnalysisUtilities                                                                     
  LLVM-Unit :: IR/./IRTests/ModuleCallbacksTest.ParseTopLevelPipeline                                                                 
  LLVM-Unit :: IR/./IRTests/ModuleCallbacksTest.Passes                                                                                
  LLVM-Unit :: IR/./IRTests/PassManagerTest.Basic                                                                                     
  LLVM-Unit :: IR/./IRTests/PassManagerTest.CustomizedPassManagerArgs                                                                 
  LLVM-Unit :: IR/./IRTests/PassManagerTest.IndirectAnalysisInvalidation                                                              
  LLVM-Unit :: IR/./IRTests/PreservedAnalysesTest.Basic                        
  LLVM-Unit :: IR/./IRTests/PreservedAnalysesTest.PreserveSets                                                                        
  LLVM-Unit :: IR/./IRTests/PreservedAnalysisTest.Intersect                                              
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.Basic               
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.FunctionPassInvalidationOfLoopAnalyses
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.IndirectInvalidation         
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.IndirectOuterPassInvalidation
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.InvalidationOfBundledAnalyses
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.LoopChildInsertion
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.LoopDeletion                                                       
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.LoopPeerInsertion
  LLVM-Unit :: Transforms/Scalar/./ScalarTests/LoopPassManagerTest.ModulePassInvalidationOfLoopAnalyses
  LLVM-Unit :: Transforms/Utils/./UtilsTests/CloneFunc.DebugIntrinsics        
  LLVM-Unit :: Transforms/Utils/./UtilsTests/CloneFunc.InstructionOwnership
  LLVM-Unit :: Transforms/Utils/./UtilsTests/CloneFunc.NewFunctionCreated
  LLVM-Unit :: Transforms/Utils/./UtilsTests/CloneFunc.Subprogram
  LLVM-Unit :: Transforms/Utils/./UtilsTests/CloneModule.OldModuleUnchanged

Expected Passes    : 21021
Expected Failures  : 226
Unsupported Tests  : 470
Unexpected Failures: 29

% ninja check
[139/140] Running the LLVM regression tests
Testing Time: 149.61s

Expected Passes    : 21750      
Expected Failures  : 226        
Unsupported Tests  : 470

[jtony]

LGTM.

[jtony]

For the Unexpected Failures: 29, do they still fail without your patch?

[MaskRay]

I reran the test just now. They did not fail.

% cat /tmp/old /tmp/new
Testing Time: 152.80s                                               
  Expected Passes    : 21750                                        
  Expected Failures  : 226                                          
  Unsupported Tests  : 470
Testing Time: 150.72s
  Expected Passes    : 21750
  Expected Failures  : 226
  Unsupported Tests  : 470

llvm/trunk/lib/Target/PowerPC/PPCInstrInfo.td

 
 // Fast 64-bit reverse bits algorithm:
 // Step 1: 1-bit swap (swap odd 1-bit and even 1-bit):
 // n = ((n >> 1) & 0x5555555555555555) | ((n << 1) & 0xAAAAAAAAAAAAAAAA);
 // Step 2: 2-bit swap (swap odd 2-bit and even 2-bit):
 // n = ((n >> 2) & 0x3333333333333333) | ((n << 2) & 0xCCCCCCCCCCCCCCCC);
 // Step 3: 4-bit swap (swap odd 4-bit and even 4-bit):
 // n = ((n >> 4) & 0x0F0F0F0F0F0F0F0F) | ((n << 4) & 0xF0F0F0F0F0F0F0F0);
-// Step 4: byte reverse (Suppose n = [B1,B2,B3,B4,B5,B6,B7,B8]):
+// Step 4: byte reverse (Suppose n = [B0,B1,B2,B3,B4,B5,B6,B7]):
 // Apply the same byte reverse algorithm mentioned above for the fast 32-bit
 // reverse to both the high 32 bit and low 32 bit of the 64 bit value. And
 // then OR them together to get the final result.
 def MaskValues64 {
   dag Lo1 = (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), MaskValues.Lo1, sub_32));
   dag Hi1 = (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), MaskValues.Hi1, sub_32));
   dag Lo2 = (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), MaskValues.Lo2, sub_32));
   dag Hi2 = (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), MaskValues.Hi2, sub_32));
   dag Lo4 = (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), MaskValues.Lo4, sub_32));
   dag Hi4 = (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), MaskValues.Hi4, sub_32));
 }
 
 def DWMaskValues {
   dag Lo1 = (ORI8 (ORIS8 (RLDICR MaskValues64.Lo1, 32, 31), 0x5555), 0x5555);
   dag Hi1 = (ORI8 (ORIS8 (RLDICR MaskValues64.Hi1, 32, 31), 0xAAAA), 0xAAAA);
   dag Lo2 = (ORI8 (ORIS8 (RLDICR MaskValues64.Lo2, 32, 31), 0x3333), 0x3333);
   dag Hi2 = (ORI8 (ORIS8 (RLDICR MaskValues64.Hi2, 32, 31), 0xCCCC), 0xCCCC);
   dag Lo4 = (ORI8 (ORIS8 (RLDICR MaskValues64.Lo4, 32, 31), 0x0F0F), 0x0F0F);
   dag Hi4 = (ORI8 (ORIS8 (RLDICR MaskValues64.Hi4, 32, 31), 0xF0F0), 0xF0F0);
 }
 
-def DWShift1 {
-  dag Right = (RLDICL $A, 63, 1);
-  dag Left = (RLDICR $A, 1, 62);
+def DWSwapInByte {
+  dag Swap1 = (OR8 (AND8 (RLDICL $A, 63, 1), DWMaskValues.Lo1),
+                   (AND8 (RLDICR $A, 1, 62), DWMaskValues.Hi1));
+  dag Swap2 = (OR8 (AND8 (RLDICL DWSwapInByte.Swap1, 62, 2), DWMaskValues.Lo2),
+                   (AND8 (RLDICR DWSwapInByte.Swap1, 2, 61), DWMaskValues.Hi2));
+  dag Swap4 = (OR8 (AND8 (RLDICL DWSwapInByte.Swap2, 60, 4), DWMaskValues.Lo4),
+                   (AND8 (RLDICR DWSwapInByte.Swap2, 4, 59), DWMaskValues.Hi4));
 }
 
-def DWSwap1 {
-  dag Bit = (OR8 (AND8 DWShift1.Right, DWMaskValues.Lo1),
-                 (AND8 DWShift1.Left, DWMaskValues.Hi1));
+// Intra-byte swap is done, now start inter-byte swap.
+def DWBytes4567 {
+  dag Word = (i32 (EXTRACT_SUBREG DWSwapInByte.Swap4, sub_32));
 }
 
-def DWShift2 {
-  dag Right = (RLDICL DWSwap1.Bit, 62, 2);
-  dag Left = (RLDICR DWSwap1.Bit, 2, 61);
+def DWBytes7456 {
+  dag Word = (RLWINM DWBytes4567.Word, 24, 0, 31);
 }
 
-def DWSwap2 {
-  dag Bits = (OR8 (AND8 DWShift2.Right, DWMaskValues.Lo2),
-                  (AND8 DWShift2.Left, DWMaskValues.Hi2));
+def DWBytes7656 {
+  dag Word = (RLWIMI DWBytes7456.Word, DWBytes4567.Word, 8, 8, 15);
 }
 
-def DWShift4 {
-  dag Right = (RLDICL DWSwap2.Bits, 60, 4);
-  dag Left = (RLDICR DWSwap2.Bits, 4, 59);
+// B7 B6 B5 B4 in the right order
+def DWBytes7654 {
+  dag Word = (RLWIMI DWBytes7656.Word, DWBytes4567.Word, 8, 24, 31);
+  dag DWord =
+    (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), DWBytes7654.Word, sub_32));
 }
 
-def DWSwap4 {
-  dag Bits = (OR8 (AND8 DWShift4.Right, DWMaskValues.Lo4),
-                  (AND8 DWShift4.Left, DWMaskValues.Hi4));
+def DWBytes0123 {
+  dag Word = (i32 (EXTRACT_SUBREG (RLDICL DWSwapInByte.Swap4, 32, 32), sub_32));
 }
 
-// Bit swap is done, now start byte swap.
-def DWExtractLo32 {
-  dag SubReg = (i32 (EXTRACT_SUBREG DWSwap4.Bits, sub_32));
+def DWBytes3012 {
+  dag Word = (RLWINM DWBytes0123.Word, 24, 0, 31);
 }
 
-def DWRotateLo32 {
-  dag Left24 = (RLWINM DWExtractLo32.SubReg, 24, 0, 31);
+def DWBytes3212 {
+  dag Word = (RLWIMI DWBytes3012.Word, DWBytes0123.Word, 8, 8, 15);
 }
 
-def DWLo32RotateInsertByte3 {
-  dag Left = (RLWIMI DWRotateLo32.Left24, DWExtractLo32.SubReg, 8, 8, 15);
-}
-
-// Lower 32 bits in the right order
-def DWLo32RotateInsertByte1 {
-  dag Left =
-    (RLWIMI DWLo32RotateInsertByte3.Left, DWExtractLo32.SubReg, 8, 24, 31);
-}
-
-def ExtendLo32 {
-  dag To64Bit =
-    (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)),
-          DWLo32RotateInsertByte1.Left, sub_32));
-}
-
-def DWShiftHi32 { // SRDI DWSwap4.Bits, 32)
-  dag ToLo32 = (RLDICL DWSwap4.Bits, 32, 32);
-}
-
-def DWExtractHi32 {
-  dag SubReg = (i32 (EXTRACT_SUBREG DWShiftHi32.ToLo32, sub_32));
-}
-
-def DWRotateHi32 {
-  dag Left24 = (RLWINM DWExtractHi32.SubReg, 24, 0, 31);
-}
-
-def DWHi32RotateInsertByte3 {
-  dag Left = (RLWIMI DWRotateHi32.Left24, DWExtractHi32.SubReg, 8, 8, 15);
-}
-
-// High 32 bits in the right order, but in the low 32-bit position
-def DWHi32RotateInsertByte1 {
-  dag Left =
-    (RLWIMI DWHi32RotateInsertByte3.Left, DWExtractHi32.SubReg, 8, 24, 31);
-}
-
-def ExtendHi32 {
-  dag To64Bit =
-    (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)),
-          DWHi32RotateInsertByte1.Left, sub_32));
-}
-
-def DWShiftLo32 { // SLDI ExtendHi32.To64Bit, 32
-  dag ToHi32 = (RLDICR ExtendHi32.To64Bit, 32, 31);
+// B3 B2 B1 B0 in the right order
+def DWBytes3210 {
+  dag Word = (RLWIMI DWBytes3212.Word, DWBytes0123.Word, 8, 24, 31);
+  dag DWord =
+    (i64 (INSERT_SUBREG (i64 (IMPLICIT_DEF)), DWBytes3210.Word, sub_32));
 }
 
+// Now both high word and low word are reversed, next
+// swap the high word and low word.
 def : Pat<(i64 (bitreverse i64:$A)),
-  (OR8 DWShiftLo32.ToHi32, ExtendLo32.To64Bit)>;
+  (OR8 (RLDICR DWBytes7654.DWord, 32, 31), DWBytes3210.DWord)>;

llvm/trunk/test/CodeGen/PowerPC/pr33093.ll

 ; CHECK-NEXT:    ori 4, 4, 43690
 ; CHECK-NEXT:    ori 5, 5, 21845
 ; CHECK-NEXT:    and 3, 3, 5
 ; CHECK-NEXT:    sldi 5, 6, 32
 ; CHECK-NEXT:    sldi 6, 7, 32
 ; CHECK-NEXT:    and 4, 8, 4
 ; CHECK-NEXT:    lis 7, 3855
 ; CHECK-NEXT:    or 3, 3, 4
-; CHECK-NEXT:    oris 12, 5, 52428
-; CHECK-NEXT:    oris 9, 6, 13107
+; CHECK-NEXT:    oris 9, 5, 52428
+; CHECK-NEXT:    oris 10, 6, 13107
 ; CHECK-NEXT:    lis 6, -3856
 ; CHECK-NEXT:    ori 7, 7, 3855
 ; CHECK-NEXT:    sldi 8, 3, 2
-; CHECK-NEXT:    ori 4, 12, 52428
+; CHECK-NEXT:    ori 4, 9, 52428
 ; CHECK-NEXT:    rldicl 3, 3, 62, 2
-; CHECK-NEXT:    ori 5, 9, 13107
+; CHECK-NEXT:    ori 5, 10, 13107
 ; CHECK-NEXT:    ori 6, 6, 61680
 ; CHECK-NEXT:    and 3, 3, 5
 ; CHECK-NEXT:    sldi 5, 6, 32
 ; CHECK-NEXT:    and 4, 8, 4
 ; CHECK-NEXT:    sldi 6, 7, 32
 ; CHECK-NEXT:    or 3, 3, 4
-; CHECK-NEXT:    oris 10, 5, 61680
-; CHECK-NEXT:    oris 11, 6, 3855
+; CHECK-NEXT:    oris 11, 5, 61680
+; CHECK-NEXT:    oris 12, 6, 3855
 ; CHECK-NEXT:    sldi 6, 3, 4
-; CHECK-NEXT:    ori 4, 10, 61680
+; CHECK-NEXT:    ori 4, 11, 61680
 ; CHECK-NEXT:    rldicl 3, 3, 60, 4
-; CHECK-NEXT:    ori 5, 11, 3855
+; CHECK-NEXT:    ori 5, 12, 3855
 ; CHECK-NEXT:    and 4, 6, 4
 ; CHECK-NEXT:    and 3, 3, 5
 ; CHECK-NEXT:    or 3, 3, 4
+; CHECK-NEXT:    rlwinm 5, 3, 24, 0, 31
 ; CHECK-NEXT:    rldicl 4, 3, 32, 32
-; CHECK-NEXT:    rlwinm 6, 3, 24, 0, 31
-; CHECK-NEXT:    rlwinm 5, 4, 24, 0, 31
-; CHECK-NEXT:    rlwimi 6, 3, 8, 8, 15
-; CHECK-NEXT:    rlwimi 5, 4, 8, 8, 15
-; CHECK-NEXT:    rlwimi 6, 3, 8, 24, 31
-; CHECK-NEXT:    rlwimi 5, 4, 8, 24, 31
-; CHECK-NEXT:    sldi 12, 5, 32
-; CHECK-NEXT:    or 3, 12, 6
+; CHECK-NEXT:    rlwinm 6, 4, 24, 0, 31
+; CHECK-NEXT:    rlwimi 5, 3, 8, 8, 15
+; CHECK-NEXT:    rlwimi 6, 4, 8, 8, 15
+; CHECK-NEXT:    rlwimi 5, 3, 8, 24, 31
+; CHECK-NEXT:    rlwimi 6, 4, 8, 24, 31
+; CHECK-NEXT:    sldi 3, 5, 32
+; CHECK-NEXT:    or 3, 3, 6
 ; CHECK-NEXT:    blr
 entry:
   %shr = lshr i64 %n, 1
   %and = and i64 %shr, 6148914691236517205
   %and1 = shl i64 %n, 1
   %shl = and i64 %and1, -6148914691236517206
   %or = or i64 %and, %shl
   %shr2 = lshr i64 %or, 2

llvm/trunk/test/CodeGen/PowerPC/testBitReverse.ll

 ; CHECK-NEXT:    ori 4, 4, 43690
 ; CHECK-NEXT:    ori 5, 5, 21845
 ; CHECK-NEXT:    and 3, 3, 5
 ; CHECK-NEXT:    sldi 5, 6, 32
 ; CHECK-NEXT:    sldi 6, 7, 32
 ; CHECK-NEXT:    and 4, 8, 4
 ; CHECK-NEXT:    lis 7, 3855
 ; CHECK-NEXT:    or 3, 3, 4
-; CHECK-NEXT:    oris 12, 5, 52428
-; CHECK-NEXT:    oris 9, 6, 13107
+; CHECK-NEXT:    oris 9, 5, 52428
+; CHECK-NEXT:    oris 10, 6, 13107
 ; CHECK-NEXT:    lis 6, -3856
 ; CHECK-NEXT:    ori 7, 7, 3855
 ; CHECK-NEXT:    sldi 8, 3, 2
-; CHECK-NEXT:    ori 4, 12, 52428
+; CHECK-NEXT:    ori 4, 9, 52428
 ; CHECK-NEXT:    rldicl 3, 3, 62, 2
-; CHECK-NEXT:    ori 5, 9, 13107
+; CHECK-NEXT:    ori 5, 10, 13107
 ; CHECK-NEXT:    ori 6, 6, 61680
 ; CHECK-NEXT:    and 3, 3, 5
 ; CHECK-NEXT:    sldi 5, 6, 32
 ; CHECK-NEXT:    and 4, 8, 4
 ; CHECK-NEXT:    sldi 6, 7, 32
 ; CHECK-NEXT:    or 3, 3, 4
-; CHECK-NEXT:    oris 10, 5, 61680
-; CHECK-NEXT:    oris 11, 6, 3855
+; CHECK-NEXT:    oris 11, 5, 61680
+; CHECK-NEXT:    oris 12, 6, 3855
 ; CHECK-NEXT:    sldi 6, 3, 4
-; CHECK-NEXT:    ori 4, 10, 61680
+; CHECK-NEXT:    ori 4, 11, 61680
 ; CHECK-NEXT:    rldicl 3, 3, 60, 4
-; CHECK-NEXT:    ori 5, 11, 3855
+; CHECK-NEXT:    ori 5, 12, 3855
 ; CHECK-NEXT:    and 4, 6, 4
 ; CHECK-NEXT:    and 3, 3, 5
 ; CHECK-NEXT:    or 3, 3, 4
+; CHECK-NEXT:    rlwinm 5, 3, 24, 0, 31
 ; CHECK-NEXT:    rldicl 4, 3, 32, 32
-; CHECK-NEXT:    rlwinm 6, 3, 24, 0, 31
-; CHECK-NEXT:    rlwinm 5, 4, 24, 0, 31
-; CHECK-NEXT:    rlwimi 6, 3, 8, 8, 15
-; CHECK-NEXT:    rlwimi 5, 4, 8, 8, 15
-; CHECK-NEXT:    rlwimi 6, 3, 8, 24, 31
-; CHECK-NEXT:    rlwimi 5, 4, 8, 24, 31
-; CHECK-NEXT:    sldi 12, 5, 32
-; CHECK-NEXT:    or 3, 12, 6
+; CHECK-NEXT:    rlwinm 6, 4, 24, 0, 31
+; CHECK-NEXT:    rlwimi 5, 3, 8, 8, 15
+; CHECK-NEXT:    rlwimi 6, 4, 8, 8, 15
+; CHECK-NEXT:    rlwimi 5, 3, 8, 24, 31
+; CHECK-NEXT:    rlwimi 6, 4, 8, 24, 31
+; CHECK-NEXT:    sldi 3, 5, 32
+; CHECK-NEXT:    or 3, 3, 6
 ; CHECK-NEXT:    blr
   %res = call i64 @llvm.bitreverse.i64(i64 %arg)
   ret i64 %res
 }