[BPF] Implement mod operation

[Jim]

Summary

Implement BPF_MOD instruction to fix lack of assembly parser support mentioned in https://github.com/llvm/llvm-project/issues/55192.

[yonghong-song]

The current 'summary' or commit message is too simple. Could you clarify some motivation why you need to add this instruction?
The change itself looks good to me. The kernel selftest test_verifier does test BPF_MOD instruction and I checked verifier code, BPF_MOD is handled similar to BPF_DIV which should be okay in most cases, so I didn't see a major issue here.

[ast]

lgtm as well.

[yonghong-song]

@Jim Thanks for the updated commit message. Please go ahead to merge to llvm-project main branch if you have write permission. Otherwise, please provide me with peoper git author signature "<name> <email address>" and I can help push the patch for you.

[Jim]

In D125207#3505163, @yonghong-song wrote:

@Jim Thanks for the updated commit message. Please go ahead to merge to llvm-project main branch if you have write permission. Otherwise, please provide me with peoper git author signature "<name> <email address>" and I can help push the patch for you.

Thanks @yonghong-song . I have commit right.

llvm/lib/Target/BPF/BPFISelLowering.cpp

BPFTargetLowering::BPFTargetLowering(const TargetMachine &TM,
 
   for (auto VT : { MVT::i32, MVT::i64 }) {
     if (VT == MVT::i32 && !STI.getHasAlu32())
       continue;
 
     setOperationAction(ISD::SDIVREM, VT, Expand);
     setOperationAction(ISD::UDIVREM, VT, Expand);
     setOperationAction(ISD::SREM, VT, Expand);
-    setOperationAction(ISD::UREM, VT, Expand);
     setOperationAction(ISD::MULHU, VT, Expand);
     setOperationAction(ISD::MULHS, VT, Expand);
     setOperationAction(ISD::UMUL_LOHI, VT, Expand);
     setOperationAction(ISD::SMUL_LOHI, VT, Expand);
     setOperationAction(ISD::ROTR, VT, Expand);
     setOperationAction(ISD::ROTL, VT, Expand);
     setOperationAction(ISD::SHL_PARTS, VT, Expand);
     setOperationAction(ISD::SRL_PARTS, VT, Expand);

llvm/lib/Target/BPF/BPFInstrFormats.td

 def BPF_SUB  : BPFArithOp<0x1>;
 def BPF_MUL  : BPFArithOp<0x2>;
 def BPF_DIV  : BPFArithOp<0x3>;
 def BPF_OR   : BPFArithOp<0x4>;
 def BPF_AND  : BPFArithOp<0x5>;
 def BPF_LSH  : BPFArithOp<0x6>;
 def BPF_RSH  : BPFArithOp<0x7>;
 def BPF_NEG  : BPFArithOp<0x8>;
+def BPF_MOD  : BPFArithOp<0x9>;
 def BPF_XOR  : BPFArithOp<0xa>;
 def BPF_MOV  : BPFArithOp<0xb>;
 def BPF_ARSH : BPFArithOp<0xc>;
 def BPF_END  : BPFArithOp<0xd>;
 
 def BPF_XCHG    : BPFArithOp<0xe>;
 def BPF_CMPXCHG : BPFArithOp<0xf>;
 

llvm/lib/Target/BPF/BPFInstrInfo.td

let isAsCheapAsAMove = 1 in {
   defm AND : ALU<BPF_AND, "&=", and>;
   defm SLL : ALU<BPF_LSH, "<<=", shl>;
   defm SRL : ALU<BPF_RSH, ">>=", srl>;
   defm XOR : ALU<BPF_XOR, "^=", xor>;
   defm SRA : ALU<BPF_ARSH, "s>>=", sra>;
 }
   defm MUL : ALU<BPF_MUL, "*=", mul>;
   defm DIV : ALU<BPF_DIV, "/=", udiv>;
+  defm MOD : ALU<BPF_MOD, "%=", urem>;
 }
 
 class NEG_RR<BPFOpClass Class, BPFArithOp Opc,
              dag outs, dag ins, string asmstr, list<dag> pattern>
     : TYPE_ALU_JMP<Opc.Value, 0, outs, ins, asmstr, pattern> {
   bits<4> dst;
 
   let Inst{51-48} = dst;

llvm/test/CodeGen/BPF/32-bit-subreg-alu.ll

 ;   return a / b;
 ; }
 ;
 ; unsigned div_i(unsigned a)
 ; {
 ;   return a / 0xf;
 ; }
 ;
+; unsigned rem(unsigned a, unsigned b)
+; {
+;   return a % b;
+; }
+;
+; unsigned rem_i(unsigned a)
+; {
+;   return a % 0xf;
+; }
+;
 ; int or(int a, int b)
 ; {
 ;   return a | b;
 ; }
 ;
 ; int or_i(int a)
 ; {
 ;   return a | 0xff;

 define dso_local i32 @div_i(i32 %a) local_unnamed_addr #0 {
 entry:
   %div = udiv i32 %a, 15
 ; CHECK: w{{[0-9]+}} /= 15
   ret i32 %div
 }
 
 ; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @rem(i32 %a, i32 %b) local_unnamed_addr #0 {
+entry:
+  %rem = urem i32 %a, %b
+; CHECK: w{{[0-9]+}} %= w{{[0-9]+}}
+  ret i32 %rem
+}
+
+; Function Attrs: norecurse nounwind readnone
+define dso_local i32 @rem_i(i32 %a) local_unnamed_addr #0 {
+entry:
+  %rem = urem i32 %a, 15
+; CHECK: w{{[0-9]+}} %= 15
+  ret i32 %rem
+}
+
+; Function Attrs: norecurse nounwind readnone
 define dso_local i32 @or(i32 %a, i32 %b) local_unnamed_addr #0 {
 entry:
   %or = or i32 %b, %a
 ; CHECK: w{{[0-9]+}} |= w{{[0-9]+}}
   ret i32 %or
 }
 
 ; Function Attrs: norecurse nounwind readnone

llvm/test/MC/BPF/insn-unit.s

 // CHECK-64: c3 92 10 00 00 00 00 00  lock *(u32 *)(r2 + 16) += r9
 // CHECK-32: c3 92 10 00 00 00 00 00  lock *(u32 *)(r2 + 16) += w9
 // CHECK: db a3 e2 ff 00 00 00 00   lock *(u64 *)(r3 - 30) += r10
 
 // ======== BPF_JMP Class ========
   goto Llabel0               // BPF_JA
   call 1                     // BPF_CALL
   exit                       // BPF_EXIT
-// CHECK: 05 00 1a 00 00 00 00 00   goto +26
+// CHECK: 05 00 1b 00 00 00 00 00   goto +27
 // CHECK: 85 00 00 00 01 00 00 00   call 1
 // CHECK: 95 00 00 00 00 00 00 00   exit
 
   if r0 == r1 goto Llabel0   // BPF_JEQ  | BPF_X
   if r3 != r4 goto Llabel0   // BPF_JNE  | BPF_X
-// CHECK: 1d 10 17 00 00 00 00 00   if r0 == r1 goto +23
-// CHECK: 5d 43 16 00 00 00 00 00   if r3 != r4 goto +22
+// CHECK: 1d 10 18 00 00 00 00 00   if r0 == r1 goto +24
+// CHECK: 5d 43 17 00 00 00 00 00   if r3 != r4 goto +23
 
   if r1 > r2 goto Llabel0    // BPF_JGT  | BPF_X
   if r2 >= r3 goto Llabel0   // BPF_JGE  | BPF_X
   if r4 s> r5 goto Llabel0   // BPF_JSGT | BPF_X
   if r5 s>= r6 goto Llabel0  // BPF_JSGE | BPF_X
-// CHECK: 2d 21 15 00 00 00 00 00   if r1 > r2 goto +21
-// CHECK: 3d 32 14 00 00 00 00 00   if r2 >= r3 goto +20
-// CHECK: 6d 54 13 00 00 00 00 00   if r4 s> r5 goto +19
-// CHECK: 7d 65 12 00 00 00 00 00   if r5 s>= r6 goto +18
+// CHECK: 2d 21 16 00 00 00 00 00   if r1 > r2 goto +22
+// CHECK: 3d 32 15 00 00 00 00 00   if r2 >= r3 goto +21
+// CHECK: 6d 54 14 00 00 00 00 00   if r4 s> r5 goto +20
+// CHECK: 7d 65 13 00 00 00 00 00   if r5 s>= r6 goto +19
 
   if r6 < r7 goto Llabel0    // BPF_JLT  | BPF_X
   if r7 <= r8 goto Llabel0   // BPF_JLE  | BPF_X
   if r8 s< r9 goto Llabel0   // BPF_JSLT | BPF_X
   if r9 s<= r10 goto Llabel0 // BPF_JSLE | BPF_X
-// CHECK: ad 76 11 00 00 00 00 00   if r6 < r7 goto +17
-// CHECK: bd 87 10 00 00 00 00 00   if r7 <= r8 goto +16
-// CHECK: cd 98 0f 00 00 00 00 00   if r8 s< r9 goto +15
-// CHECK: dd a9 0e 00 00 00 00 00   if r9 s<= r10 goto +14
+// CHECK: ad 76 12 00 00 00 00 00   if r6 < r7 goto +18
+// CHECK: bd 87 11 00 00 00 00 00   if r7 <= r8 goto +17
+// CHECK: cd 98 10 00 00 00 00 00   if r8 s< r9 goto +16
+// CHECK: dd a9 0f 00 00 00 00 00   if r9 s<= r10 goto +15
 
   if r0 == 0 goto Llabel0           // BPF_JEQ  | BPF_K
   if r3 != -1 goto Llabel0          // BPF_JNE  | BPF_K
-// CHECK: 15 00 0d 00 00 00 00 00   if r0 == 0 goto +13
-// CHECK: 55 03 0c 00 ff ff ff ff   if r3 != -1 goto +12
+// CHECK: 15 00 0e 00 00 00 00 00   if r0 == 0 goto +14
+// CHECK: 55 03 0d 00 ff ff ff ff   if r3 != -1 goto +13
 
   if r1 > 64 goto Llabel0           // BPF_JGT  | BPF_K
   if r2 >= 0xffffffff goto Llabel0  // BPF_JGE  | BPF_K
   if r4 s> 0xffffffff goto Llabel0  // BPF_JSGT | BPF_K
   if r5 s>= 0x7fffffff goto Llabel0 // BPF_JSGE | BPF_K
-// CHECK: 25 01 0b 00 40 00 00 00   if r1 > 64 goto +11
-// CHECK: 35 02 0a 00 ff ff ff ff   if r2 >= -1 goto +10
-// CHECK: 65 04 09 00 ff ff ff ff   if r4 s> -1 goto +9
-// CHECK: 75 05 08 00 ff ff ff 7f   if r5 s>= 2147483647 goto +8
+// CHECK: 25 01 0c 00 40 00 00 00   if r1 > 64 goto +12
+// CHECK: 35 02 0b 00 ff ff ff ff   if r2 >= -1 goto +11
+// CHECK: 65 04 0a 00 ff ff ff ff   if r4 s> -1 goto +10
+// CHECK: 75 05 09 00 ff ff ff 7f   if r5 s>= 2147483647 goto +9
 
   if r6 < 0xff goto Llabel0         // BPF_JLT  | BPF_K
   if r7 <= 0xffff goto Llabel0      // BPF_JLE  | BPF_K
   if r8 s< 0 goto Llabel0           // BPF_JSLT | BPF_K
   if r9 s<= -1 goto Llabel0         // BPF_JSLE | BPF_K
-// CHECK: a5 06 07 00 ff 00 00 00   if r6 < 255 goto +7
-// CHECK: b5 07 06 00 ff ff 00 00   if r7 <= 65535 goto +6
-// CHECK: c5 08 05 00 00 00 00 00   if r8 s< 0 goto +5
-// CHECK: d5 09 04 00 ff ff ff ff   if r9 s<= -1 goto +4
+// CHECK: a5 06 08 00 ff 00 00 00   if r6 < 255 goto +8
+// CHECK: b5 07 07 00 ff ff 00 00   if r7 <= 65535 goto +7
+// CHECK: c5 08 06 00 00 00 00 00   if r8 s< 0 goto +6
+// CHECK: d5 09 05 00 ff ff ff ff   if r9 s<= -1 goto +5
 
 // ======== BPF_ALU64 Class ========
   r0 += r1    // BPF_ADD  | BPF_X
   r1 -= r2    // BPF_SUB  | BPF_X
   r2 *= r3    // BPF_MUL  | BPF_X
   r3 /= r4    // BPF_DIV  | BPF_X
+  r4 %= r5    // BPF_MOD  | BPF_X
 // CHECK: 0f 10 00 00 00 00 00 00   r0 += r1
 // CHECK: 1f 21 00 00 00 00 00 00   r1 -= r2
 // CHECK: 2f 32 00 00 00 00 00 00   r2 *= r3
 // CHECK: 3f 43 00 00 00 00 00 00   r3 /= r4
+// CHECK: 9f 54 00 00 00 00 00 00   r4 %= r5
 
 Llabel0 :
   r2 = -r2    // BPF_NEG
   r4 |= r5    // BPF_OR   | BPF_X
   r5 &= r6    // BPF_AND  | BPF_X
   r6 <<= r7   // BPF_LSH  | BPF_X
   r7 >>= r8   // BPF_RSH  | BPF_X
   r8 ^= r9    // BPF_XOR  | BPF_X

 // CHECK: dc 01 00 00 10 00 00 00   r1 = be16 r1
 // CHECK: dc 02 00 00 20 00 00 00   r2 = be32 r2
 // CHECK: dc 03 00 00 40 00 00 00   r3 = be64 r3
 
   r0 += 1           // BPF_ADD  | BPF_K
   r1 -= 0x1         // BPF_SUB  | BPF_K
   r2 *= -4          // BPF_MUL  | BPF_K
   r3 /= 5           // BPF_DIV  | BPF_K
+  r4 %= 5           // BPF_MOD  | BPF_K
 // CHECK: 07 00 00 00 01 00 00 00   r0 += 1
 // CHECK: 17 01 00 00 01 00 00 00   r1 -= 1
 // CHECK: 27 02 00 00 fc ff ff ff   r2 *= -4
 // CHECK: 37 03 00 00 05 00 00 00   r3 /= 5
+// CHECK: 97 04 00 00 05 00 00 00   r4 %= 5
 
   r4 |= 0xff        // BPF_OR   | BPF_K
   r5 &= 0xFF        // BPF_AND  | BPF_K
   r6 <<= 63         // BPF_LSH  | BPF_K
   r7 >>= 32         // BPF_RSH  | BPF_K
   r8 ^= 0           // BPF_XOR  | BPF_K
   r9 = 1            // BPF_MOV  | BPF_K
   r9 = 0xffffffff   // BPF_MOV  | BPF_K