[ARC] Add codegen for llvm.ctlz intrinsic for the ARC backend

[thomasjohns]

Summary

Add a CTLZ pseudo instruction to tablegen and the ability to expand this pseudo instruction instruction to ARC assembly code.

[thomasjohns]

llvm/lib/Target/ARC/ARCInstrInfo.td

314

I just realized I made a bad merge here and dropped the }. Fixing it now.

[thomasjohns]

llvm/lib/Target/ARC/ARCInstrInfo.td

314

I'll also move this pseudo instruction to be next to the other pseudo instructions

[thomasjohns]

Fix missing } after bad merge. Move CTLZ next to other pseudo instructions.

[thomasjohns]

llvm clang-tidy rule: prefer Register over unsinged int.

[marksl]

llvm/lib/Target/ARC/ARCExpandPseudos.cpp

86

I know you're following ExpandStore above in using "SI" here, but let's switch to "MI" as that is the most common practice. I think he used "SI" because it was a store instruction. All your readers will recognize MI as a MachineInstr, but they will have no such association to SI.

93

This is not right. The final instruction of the sequence must write to DestReg.

[thomasjohns]

Thanks for the feedback, Mark.

This change prefers MI over SI naming, updates instruction writing, and makes the test case more precise (the generated code was improved and no longer had an unneeded mov %r1, %r0.

[marksl]

Looks good

clang/lib/Basic/Targets/ARC.h

public:
   }
 
   bool validateAsmConstraint(const char *&Name,
                              TargetInfo::ConstraintInfo &Info) const override {
     return false;
   }
 
   bool hasExtIntType() const override { return true; }
+
+  bool isCLZForZeroUndef() const override { return false; }
 };
 
 } // namespace targets
 } // namespace clang
 
 #endif // LLVM_CLANG_LIB_BASIC_TARGETS_ARC_H

llvm/lib/Target/ARC/ARCExpandPseudos.cpp

 //===- ARCExpandPseudosPass - ARC expand pseudo loads -----------*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // This pass expands stores with large offsets into an appropriate sequence.
 //===----------------------------------------------------------------------===//
 
 #include "ARC.h"
 #include "ARCInstrInfo.h"
 #include "ARCRegisterInfo.h"
 #include "ARCSubtarget.h"
+#include "MCTargetDesc/ARCInfo.h"
 #include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/MachineFunctionPass.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "arc-expand-pseudos"
 
 namespace {
 
 class ARCExpandPseudos : public MachineFunctionPass {
 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);
 
   const ARCInstrInfo *TII;
 };
 
 char ARCExpandPseudos::ID = 0;
 
 } // end anonymous namespace
 
void ARCExpandPseudos::ExpandStore(MachineFunction &MF,
   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,
+                                  MachineBasicBlock::iterator SII) {
+  // 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 &SI = *SII;
+  const MachineOperand &Dest = SI.getOperand(0);
+  assert(Dest.isReg());
+  const MachineOperand &Src = SI.getOperand(1);
+  assert(Src.isReg());
+  unsigned DestReg = Dest.getReg();
+
+  BuildMI(*SI.getParent(), SI, SI.getDebugLoc(), TII->get(ARC::FLS_f_rr),
+          DestReg)
+      .add(Src)
+      .addReg(ARC::STATUS32, RegState::ImplicitDefine);
+
+  unsigned Ra = MF.getRegInfo().createVirtualRegister(&ARC::GPR32RegClass);
+  unsigned Rb = MF.getRegInfo().createVirtualRegister(&ARC::GPR32RegClass);
+  BuildMI(*SI.getParent(), SI, SI.getDebugLoc(), TII->get(ARC::MOV_cc_ru6), Ra)
+      .addImm(32)
+      .addImm(ARCCC::EQ)
+      .addReg(DestReg);
+  BuildMI(*SI.getParent(), SI, SI.getDebugLoc(), TII->get(ARC::RSUB_cc_rru6),
+          Rb)
+      .addImm(31)
+      .addImm(ARCCC::NE)
+      .addReg(Ra);
+
+  SI.eraseFromParent();
+}
+
 bool ARCExpandPseudos::runOnMachineFunction(MachineFunction &MF) {
   const ARCSubtarget *STI = &MF.getSubtarget<ARCSubtarget>();
   TII = STI->getInstrInfo();
-  bool ExpandedStore = false;
+  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);
-        ExpandedStore = true;
+        Expanded = true;
+        break;
+      case ARC::CTLZ:
+        ExpandCTLZ(MF, MBBI);
+        Expanded = true;
         break;
       default:
         break;
       }
       MBBI = NMBBI;
     }
   }
-  return ExpandedStore;
+  return Expanded;
 }
 
 FunctionPass *llvm::createARCExpandPseudosPass() {
   return new ARCExpandPseudos();
 }

llvm/lib/Target/ARC/ARCISelLowering.cpp

ARCTargetLowering::ARCTargetLowering(const TargetMachine &TM,
   setOperationAction(ISD::VACOPY, MVT::Other, Expand);
 
   // 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.
+  setOperationAction(ISD::CTLZ, 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

 defm SEXH : ArcUnaryGEN4Inst<0b000110, "sexh">;
 
 // Extension unary instruction definitions.
 defm FLS : ArcUnaryEXT5Inst<0b010011, "fls">;
 
 let Predicates=[HasNorm] in {
   defm NORM  : ArcUnaryEXT5Inst<0b000001,"norm">;
   defm NORMH : ArcUnaryEXT5Inst<0b001000,"normh">;
+
+// TODO: Add `Requires<[HasBitScan]>` predicate when available.
+def CTLZ : PseudoInstARC<(outs GPR32:$A),
+                         (ins GPR32:$B),
+                         "error.fls $A, $B",
+                         [(set GPR32:$A, (ctlz i32:$B))]> {
+  let Defs = [STATUS32];
 }
 
 // General Unary Instruction fragments.
 def : Pat<(sext_inreg i32:$a, i8), (SEXB_rr i32:$a)>;
 def : Pat<(sext_inreg i32:$a, i16), (SEXH_rr i32:$a)>;
 
 // Comparison instruction definition
 let isCompare = 1, Defs = [STATUS32] in {

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: mov.eq  [[R:%r[01]]], 32
+; CHECK: rsub.ne [[R]], [[R]], 31
+define i32 @clz32(i32 %x) {
+  %a = call i32 @llvm.ctlz.i32(i32 %x, i1 false)
+  ret i32 %a
+}