[ARC] Add codegen for count trailing zeros intrinsic for the ARC backend

[thomasjohns]

Summary

This makes the __builtin_ctz(x) intrinsic generate ffs.f %r, %r (find first set) and mov.eq %r, 32 (conditional move) ARC instructions. This change also added the ffs instruction to tablegen with a disassembly test.

[marksl]

Looks good

[thomasjohns]

Attempt to fix clang-tidy lints in ARCExpandPseudos.cpp.

[marksl]

Thanks for fixing the clang-tidy issue

llvm/lib/Target/ARC/ARCExpandPseudos.cpp

public:
   static char ID;
   ARCExpandPseudos() : MachineFunctionPass(ID) {}
 
   bool runOnMachineFunction(MachineFunction &Fn) override;
 
   StringRef getPassName() const override { return "ARC Expand Pseudos"; }
 
 private:
-  void ExpandStore(MachineFunction &, MachineBasicBlock::iterator);
-  void ExpandCTLZ(MachineFunction &, MachineBasicBlock::iterator);
+  void expandStore(MachineFunction &, MachineBasicBlock::iterator);
+  void expandCTLZ(MachineFunction &, MachineBasicBlock::iterator);
+  void expandCTTZ(MachineFunction &, MachineBasicBlock::iterator);
 
   const ARCInstrInfo *TII;
 };
 
 char ARCExpandPseudos::ID = 0;
 
 } // end anonymous namespace
 
 static unsigned getMappedOp(unsigned PseudoOp) {
   switch (PseudoOp) {
   case ARC::ST_FAR:
     return ARC::ST_rs9;
   case ARC::STH_FAR:
     return ARC::STH_rs9;
   case ARC::STB_FAR:
     return ARC::STB_rs9;
   default:
     llvm_unreachable("Unhandled pseudo op.");
   }
 }
 
-void ARCExpandPseudos::ExpandStore(MachineFunction &MF,
+void ARCExpandPseudos::expandStore(MachineFunction &MF,
                                    MachineBasicBlock::iterator SII) {
   MachineInstr &SI = *SII;
   Register AddrReg = MF.getRegInfo().createVirtualRegister(&ARC::GPR32RegClass);
   Register AddOpc =
       isUInt<6>(SI.getOperand(2).getImm()) ? ARC::ADD_rru6 : ARC::ADD_rrlimm;
   BuildMI(*SI.getParent(), SI, SI.getDebugLoc(), TII->get(AddOpc), AddrReg)
       .addReg(SI.getOperand(1).getReg())
       .addImm(SI.getOperand(2).getImm());
   BuildMI(*SI.getParent(), SI, SI.getDebugLoc(),
           TII->get(getMappedOp(SI.getOpcode())))
       .addReg(SI.getOperand(0).getReg())
       .addReg(AddrReg)
       .addImm(0);
   SI.eraseFromParent();
 }
 
-void ARCExpandPseudos::ExpandCTLZ(MachineFunction &MF,
+void ARCExpandPseudos::expandCTLZ(MachineFunction &MF,
                                   MachineBasicBlock::iterator MII) {
   // Expand:
   //  %R2<def> = CTLZ %R0, %STATUS<imp-def>
   // To:
   //  %R2<def> = FLS_f_rr %R0, %STATUS<imp-def>
   //  %R2<def,tied1> = MOV_cc_ru6 %R2<tied0>, 32, pred:1, %STATUS<imp-use>
   //  %R2<def,tied1> = RSUB_cc_rru6 %R2<tied0>, 31, pred:2, %STATUS<imp-use>
   MachineInstr &MI = *MII;
BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), TII->get(ARC::RSUB_cc_rru6))
       .add(Dest)
       .addImm(31)
       .addImm(ARCCC::NE)
       .addReg(Rb);
 
   MI.eraseFromParent();
 }
 
+void ARCExpandPseudos::expandCTTZ(MachineFunction &MF,
+                                  MachineBasicBlock::iterator MII) {
+  // Expand:
+  //  %R0<def> = CTTZ %R0<kill>, %STATUS<imp-def>
+  // To:
+  //  %R0<def> = FFS_f_rr %R0<kill>, %STATUS<imp-def>
+  //  %R0<def,tied1> = MOVcc_ru6 %R0<tied0>, 32, pred:1, %STATUS<imp-use>
+  MachineInstr &MI = *MII;
+  const MachineOperand &Dest = MI.getOperand(0);
+  const MachineOperand &Src = MI.getOperand(1);
+  Register R = MF.getRegInfo().createVirtualRegister(&ARC::GPR32RegClass);
+
+  BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), TII->get(ARC::FFS_f_rr), R)
+      .add(Src);
+  BuildMI(*MI.getParent(), MI, MI.getDebugLoc(), TII->get(ARC::MOV_cc_ru6))
+      .add(Dest)
+      .addImm(32)
+      .addImm(ARCCC::EQ)
+      .addReg(R);
+
+  MI.eraseFromParent();
+}
+
 bool ARCExpandPseudos::runOnMachineFunction(MachineFunction &MF) {
   const ARCSubtarget *STI = &MF.getSubtarget<ARCSubtarget>();
   TII = STI->getInstrInfo();
   bool Expanded = false;
   for (auto &MBB : MF) {
     MachineBasicBlock::iterator MBBI = MBB.begin(), E = MBB.end();
     while (MBBI != E) {
       MachineBasicBlock::iterator NMBBI = std::next(MBBI);
       switch (MBBI->getOpcode()) {
       case ARC::ST_FAR:
       case ARC::STH_FAR:
       case ARC::STB_FAR:
-        ExpandStore(MF, MBBI);
+        expandStore(MF, MBBI);
         Expanded = true;
         break;
       case ARC::CTLZ:
-        ExpandCTLZ(MF, MBBI);
+        expandCTLZ(MF, MBBI);
+        Expanded = true;
+        break;
+      case ARC::CTTZ:
+        expandCTTZ(MF, MBBI);
         Expanded = true;
         break;
       default:
         break;
       }
       MBBI = NMBBI;
     }
   }
   return Expanded;
 }
 
 FunctionPass *llvm::createARCExpandPseudosPass() {
   return new ARCExpandPseudos();
 }

llvm/lib/Target/ARC/ARCISelLowering.cpp

ARCTargetLowering::ARCTargetLowering(const TargetMachine &TM,
 
   // Other expansions
   setOperationAction(ISD::STACKSAVE, MVT::Other, Expand);
   setOperationAction(ISD::STACKRESTORE, MVT::Other, Expand);
 
   // Sign extend inreg
   setOperationAction(ISD::SIGN_EXTEND_INREG, MVT::i1, Custom);
 
-  // TODO: Predicate with `options.hasBitScan() ? Legal : Expand` when
-  //       the HasBitScan predicate is available.
+  // TODO: Predicate these with `options.hasBitScan() ? Legal : Expand`
+  //       when the HasBitScan predicate is available.
   setOperationAction(ISD::CTLZ, MVT::i32, Legal);
+  setOperationAction(ISD::CTTZ, MVT::i32, Legal);
 }
 
 const char *ARCTargetLowering::getTargetNodeName(unsigned Opcode) const {
   switch (Opcode) {
   case ARCISD::BL:
     return "ARCISD::BL";
   case ARCISD::CMOV:
     return "ARCISD::CMOV";

llvm/lib/Target/ARC/ARCInstrInfo.td

 def STH_FAR : PseudoInstARC<(outs), (ins GPR32:$dst, MEMrlimm:$addr),
                              "STH_FAR $dst, $addr",
                              [(truncstorei16 GPR32:$dst, AddrModeFar:$addr)]>;
 
 def STB_FAR : PseudoInstARC<(outs), (ins GPR32:$dst, MEMrlimm:$addr),
                              "STB_FAR $dst, $addr",
                              [(truncstorei8 GPR32:$dst, AddrModeFar:$addr)]>;
 
-// TODO: Add `Requires<[HasBitScan]>` predicate when available.
+// TODO: Add `Requires<[HasBitScan]>` predicate to these when available.
+let Defs = [STATUS32] in {
   def CTLZ : PseudoInstARC<(outs GPR32:$A),
                            (ins GPR32:$B),
                            "error.fls $A, $B",
-                         [(set GPR32:$A, (ctlz i32:$B))]> {
-  let Defs = [STATUS32];
+                           [(set GPR32:$A, (ctlz i32:$B))]>;
+
+  def CTTZ : PseudoInstARC<(outs GPR32:$A),
+                           (ins GPR32:$B),
+                           "error.ffs $A, $B",
+                           [(set GPR32:$A, (cttz i32:$B))]>;
 }
 
 //===----------------------------------------------------------------------===//
 // Instruction Generation multiclasses.
 // Generate many variants of a single instruction with a single defining
 // multiclass.  These classes do not contain Selection DAG patterns.
 //===----------------------------------------------------------------------===//
 

 // ---------------------------------------------------------------------------
 // Unary Instruction definitions.
 // ---------------------------------------------------------------------------
 // General unary instruction definitions.
 defm SEXB : ArcUnaryGEN4Inst<0b000101, "sexb">;
 defm SEXH : ArcUnaryGEN4Inst<0b000110, "sexh">;
 
 // Extension unary instruction definitions.
+defm FFS : ArcUnaryEXT5Inst<0b010010, "ffs">;
 defm FLS : ArcUnaryEXT5Inst<0b010011, "fls">;
 
 let Predicates=[HasNorm] in {
   defm NORM  : ArcUnaryEXT5Inst<0b000001,"norm">;
   defm NORMH : ArcUnaryEXT5Inst<0b001000,"normh">;
 }
 
 // General Unary Instruction fragments.

llvm/test/CodeGen/ARC/ctlz.ll

-; RUN: llc -march=arc < %s | FileCheck %s
-
-target triple = "arc"
-
-declare i32 @llvm.ctlz.i32(i32, i1)
-
-; CHECK-LABEL: clz32:
-; CHECK:       fls.f   %r0, %r0
-; CHECK-NEXT:  mov.eq  %r0, 32
-; CHECK-NEXT:  rsub.ne %r0, %r0, 31
-define i32 @clz32(i32 %x) {
-  %a = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
-  ret i32 %a
-}

llvm/test/CodeGen/ARC/intrinsics.ll

+; RUN: llc -march=arc < %s | FileCheck %s
+
+target triple = "arc"
+
+declare i32 @llvm.ctlz.i32(i32, i1)
+declare i32 @llvm.cttz.i32(i32, i1)
+
+; CHECK-LABEL: clz32:
+; CHECK:       fls.f   %r0, %r0
+; CHECK-NEXT:  mov.eq  %r0, 32
+; CHECK-NEXT:  rsub.ne %r0, %r0, 31
+define i32 @clz32(i32 %x) {
+  %a = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
+  ret i32 %a
+}
+
+; CHECK-LABEL: ctz32:
+; CHECK:       ffs.f   %r0, %r0
+; CHECK-NEXT:  mov.eq  %r0, 32
+define i32 @ctz32(i32 %x) {
+  %a = call i32 @llvm.cttz.i32(i32 %x, i1 false)
+  ret i32 %a
+}

llvm/test/MC/Disassembler/ARC/misc.txt

 0xb8 0x23 0xff 0x3f 
 
 # CHECK: fls %r0, %r0
 0x2f 0x28 0x13 0x00
 
 # CHECK: fls.f %r0, %r0
 0x2f 0x28 0x13 0x80
 
+# CHECK: ffs %r0, %r0
+0x2f 0x28 0x12 0x00
+
+# CHECK: ffs.f %r0, %r0
+0x2f 0x28 0x12 0x80
+
+# CHECK: ffs %r15, %r15
+0x2f 0x2f 0xd2 0x13
+
+# CHECK: ffs.f %r15, %r15
+0x2f 0x2f 0xd2 0x93
+
 # CHECK: norm %r22, %blink
 0x2f 0x2e 0xc1 0x27
 
 # CHECK: normh %r7, %r18
 0x2f 0x2f 0x88 0x04