[RISCV] Lower the tail pseudoinstruction

[mgrang]

Summary

This patch lowers the tail pseudoinstruction. This has been modeled after ARM's tail call opt.

[mgrang]

lib/Target/RISCV/RISCVISelLowering.cpp

961

TODO: I couldn't write a test case to simulate this.

@asb What calling convention could result in a difference between caller and callee saved regs?

[mgrang]

lib/Target/RISCV/RISCVRegisterInfo.td

134

Can we also use x28-x31 (Caller temporaries) here?

[asb]

lib/Target/RISCV/RISCVISelLowering.cpp

961

Right now, the calling convention is always the same so this isn't testable. It's helpful to be future-proof though.

[HsiangKai]

I think it should be a typo.

lib/Target/RISCV/RISCVISelLowering.cpp

1326

Should it be MemOpChains.push_back(DAG.getStore(... ?

[HsiangKai]

Two questions.

lib/Target/RISCV/RISCVISelLowering.cpp

936

Why? In ARM tailcall opt, it could not exceed the number of arguments due to it has no available registers for indirect call under thumb1 instructions. In RISCV, we still have temporary registers to use when the number of arguments exceeds 8.

lib/Target/RISCV/RISCVRegisterInfo.td

134

Could we also use x10-x17 (Argument registers)?

I think we could let RA use any registers except callee-saved registers and x0-x4.

We could not use callee-saved registers, because these registers will be restored before tailcall and the address register will be clobbered.
We could not use x0-x4, because these registers have special meaning in RISCV architecture.

[asb]

It looks like this must be applied on top of D44885. Could you please rebase on to the latest version of that patch? It would also be useful to use 'Edit Related Revisions...' to indicate the in-flight patch(es) that this depends on.

[mgrang]

In D45395#1076818, @asb wrote:

It looks like this must be applied on top of D44885. Could you please rebase on to the latest version of that patch? It would also be useful to use 'Edit Related Revisions...' to indicate the in-flight patch(es) that this depends on.

Rebasing on top of D44885 seems to have broken tail call opt. I am debugging right now. Will push the updated patch once I have the fix.

[mgrang]

Rebased patch on top of D44885.

[asb]

Could you please separate the MC layer change into a separate patch?

It looks like there are cases where the stack is used for parameter passing and isEligibleForTailCallOptimization returns true, but there is no test coverage for these cases. Do you intend to enable tailcall optimisation for these cases? Might it be worth starting off by just enabling it for calls that make no use of the stack for parameter passing, thus simplifying the patch and the testing story?

lib/Target/RISCV/RISCVISelLowering.cpp

1097–1101

Handling ABI lowering for RV32D is rather fiddly, and the code that handles this breaks the assumption that one entry in Outs == one register (we use an approach similar to Mips, introducing buildpairf64 and splitf64 nodes to help workaround the fact that legalising and splitting and f64 to two i32 at ABI lowering time is _really_ fiddly when i64 isn't a legal type).

I think the safest way of checking eligibility is to pass a CCState to this function. If CCInfo.getNextStackOffset() == 0 then we know the stack isn't used.

Even without the RV32D case, you might have large values (e.g. i128 on RV32) that are passed via the stack. I'm assuming the intention is to not to tailcall if the stack is used at all, in which case getNextStackoffset is the better test.

1106–1107

The "interrupt" attribute isn't currently defined by RISC-V. At a minimum, it would be worth adding a note that this should be expanded as new function attributes are introduced.

I assume it would be too restrictive to have a whitelist of allowable attributes rather than a blacklist of attributes that disable tailcalling?

1111

Very minor, but it seems inconsistent that IsCalleeStructRet is calculate in the LowerCall but other properties such as CallerF.hasStructRetAttr or the presence of byval attributes are calculated here. I'd get rid of the IsCalleeStructRet argument.

1199

Also see my query in isEligibleForTailOptimization. If the intent is that tail calls aren't used when the stack is used, NumBytes should always be zero.

lib/Target/RISCV/RISCVInstrInfo.td

663–672

The correct name for this pseudoinstruction is "tail" (as used by gas and described in the ISA manual).

665

PseudoTAIL would make sense, and matches then naming convention for PseudoCALL/PseudoCALLIndirect.

669–671

This is going to have problems as currently defined. It assumes that you can specify tail $reg and have it work. As we have to always interpret an argument to tail as a symbol, this is going to lead to either incorrectly linked code or an error about an undefined symbol. Defining PseudoTAILIndirect with no AsmString might be a viable option?

[mgrang]

Addressed comments and split the MC part into a separate patch.

[mgrang]

Here's the MC layer patch which lower tail pseudo to auipc and jalr: https://reviews.llvm.org/D46221

[asb]

Thanks Mandeep. I'll re-review properly once this is rebased against D46221.

lib/Target/RISCV/RISCVISelLowering.cpp

1321–1326

Isn't this code dead now that tail calls are never used when parameters are passed on the stack?

lib/Target/RISCV/RISCVRegisterInfo.td

134

I agree with @HsiangKai, it seems as though any register that isn't callee-saved (or otherwise has a special meaning) should be safe to use. Or at least, all such registers will avoid the problem described in the comment.

[mgrang]

Thanks Alex for the explanation on indirect parameter passing. I have updated the condition in my patch and added a unit test.

test/CodeGen/RISCV/tail-calls.ll

1

Note: I have limited this test only to riscv32. With riscv64 I get the following error for fp128 parameter:
LLVM ERROR: Cannot select: t17: i64 = Constant<4611404543450677248>

I guess I can restrict only the failing test to riscv32 but I felt it was cleaner this way. We could enable this for riscv64 once the support for fp128 in riscv64 is more mature.

@asb What do you suggest?

[asb]

Hi Mandeep, I've added a number of inline comments and queries. I think we're getting pretty close now.

There's no test coverage for the patterns:

def : Pat<(Tail (iPTR texternalsym:$dst)),
          (PseudoTAIL texternalsym:$dst)>;
def : Pat<(Tail GPRTC:$dst),               
          (PseudoTAILIndirect GPRTC:$dst)>;

lib/Target/RISCV/RISCVISelLowering.cpp

1191–1192

Could you please add a test case for this, demonstrating that we get an error rather than silently miscompiling or ignoring musttail. A musttail function with structret or similar should do the trick.

1313

We know that IsTailCall should never be true here. I'd get rid of this conditional and add an assert at line 1308. It seems better than introducing a control flow path we can't test and we know should never execute.

1331–1339

Is this comment and logic actually relevant for the RISC-V implementation? In this patch, tail call optimisation is disabled for byval parameters and any case where the stack is used for parameter passing.

lib/Target/RISCV/RISCVInstrInfo.td

672

Is Uses = [X2] required here?

test/CodeGen/RISCV/disable-tail-calls.ll

1–2

The test is currently just testing whether -disable-tail-calls=false overrides a disable-tail-calls=true attribute. It should also test whether -disable-tail-calls=true overrides an explicit disable-tail-calls=false attribute.

The overriding behaviour seems a little surprising to me, but I see ARM is testing the same thing.

test/CodeGen/RISCV/tail-calls.ll

1

MC layer tests should check rv64 whenever relevant. Proper RV64 codegen isn't yet upstreamed (primarily as I need to sit down and flesh out the tests). Just testing RV32 for now is the right thing to do

[mgrang]

Thanks for the comments Alex. I had a couple of observations:

1. For PseudoTAILIndirect if I do not specify an AsmString then I don't see any instruction in the generated assembly. Is this because PseudoTAILIndirect is lowered in the RISCVMCCodeEmitter.cpp and may be too late for the assembly generation? What do you suggest to counter this?

2. I am not sure if we need the pattern for texternalsym:

def : Pat<(Tail (iPTR texternalsym:$dst)),
          (PseudoTAIL texternalsym:$dst)>;

An extern function, for example, always matches the tglobaladdr pattern:

def : Pat<(Tail (iPTR tglobaladdr:$dst)),
          (PseudoTAIL texternalsym:$dst)>;

And nothing ever seems to match the texternalsym pattern. I expected the following to match texternalsym since callee is an extern, but it matches tglobaladdr:

declare void @callee()
define void @CALLER2() {
  tail call void @callee()
  ret void
}

I have addressed the rest of your comments and will push an updated version soon. Thanks.

[mgrang]

Addressed comments.

[apazos]

I think those tail instructions that do not have a pseudo instruction in assembly code to represent them should not be lowered so late at MC layer as we are doing with the other call instructions.

[asb]

I'm definitely seeing failures with this due to PseudoTAILIndirect.

Sorry for being cryptic regarding handling of PseudoTAILIndirect. I meant it should have no asmstring because it should never reach the asm printer. It perhaps would be nice if there was an assert if an isCodeGenOnly instruction makes it through to the asm printer.

PseudoTAILIndirect is purely a codegen construct, and won't produce the tail pseudoinstruction. My first instinct would be to handle it very similarly to PseudoCALLIndirect and use PseudoInstExpansion:

def PseudoTAILIndirect : Pseudo<(outs), (ins GPRTC:$rs1), [(Tail GPRTC:$rs1)]>,
                         PseudoInstExpansion<(JALR X0, GPR:$rs1, 0)>;

But I see there's some sort of issue there and haven't had a chance yet to dig deep into what's going on. Setting let usesCustomInserter and handling in EmitInstrWithCustomerInserter is an alternative approach that comes to mind, though it would be good to better understand the PseudoInstExpansion issue first.

Test-wise, we definitely need coverage of PseudoInstExpansion. Beyond that, this seems like a nice optimisation to have. You mentioned it made not much difference in the workloads you threw at it, but it seems to trigger quite frequently in the sort of small test programs you find in a compiler test suite. If nothing else, it helps reduce the amount of code to look through when debugging those sort of inputs :)

lib/Target/RISCV/MCTargetDesc/RISCVMCCodeEmitter.cpp

88

Should expand doc comment to explain it also expands PseudoTAIL and that it returns the number of instructions that are produced.

That said, I expect we're going to drop the PseudoTAILIndirect expansion from here and so there's less need to return the number of instructions inserted.

[mgrang]

In D45395#1102983, @asb wrote:

I'm definitely seeing failures with this due to PseudoTAILIndirect.

Sorry for being cryptic regarding handling of PseudoTAILIndirect. I meant it should have no asmstring because it should never reach the asm printer. It perhaps would be nice if there was an assert if an isCodeGenOnly instruction makes it through to the asm printer.

PseudoTAILIndirect is purely a codegen construct, and won't produce the tail pseudoinstruction. My first instinct would be to handle it very similarly to PseudoCALLIndirect and use PseudoInstExpansion:

def PseudoTAILIndirect : Pseudo<(outs), (ins GPRTC:$rs1), [(Tail GPRTC:$rs1)]>,
                         PseudoInstExpansion<(JALR X0, GPR:$rs1, 0)>;

But I see there's some sort of issue there and haven't had a chance yet to dig deep into what's going on. Setting let usesCustomInserter and handling in EmitInstrWithCustomerInserter is an alternative approach that comes to mind, though it would be good to better understand the PseudoInstExpansion issue first.

Test-wise, we definitely need coverage of PseudoInstExpansion. Beyond that, this seems like a nice optimisation to have. You mentioned it made not much difference in the workloads you threw at it, but it seems to trigger quite frequently in the sort of small test programs you find in a compiler test suite. If nothing else, it helps reduce the amount of code to look through when debugging those sort of inputs :)

Thanks @asb for the suggestions.
I marked PseudoTAILIndirect as usesCustomInserter and custom lowered it in EmitInstrWithCustomInserter: https://reviews.llvm.org/differential/diff/147624

However, I see that the stack is not restored before the tail call. The call parameters are also not setup correctly without writing code to carry over the implicit regs info from the Pseudo to the JALR. As a result, I see failures on some of the spec benchmarks (gap, gcc, hmmer, mesa). I tried to play around to see how we can setup the call but could not find a clean way.

On the other hand, I looked at how AArch64 lowers the TCRETURNri. They custom lower it in the AArch64AsmPrinter after the auto-generated pseudos are lowered.
I tried the same for RISCV and it seemed to work very well: https://reviews.llvm.org/differential/diff/147623

I see the tail call being setup correctly and the spec benchmarks are all passing. This way we also don't need any explicit asmstring in the td for the Pseudo. I think we should follow this route for lowering the PseudoTAILIndirect.
What do you think Alex ?

[mgrang]

1. Lowered PseudoTAILIndirect in AsmPrinter (similar to AArch64 TCRETURNri pseudo).
2. Added test cases for tail call on external symbols and indirect tail call.
3. Addressed other comments.

[asb]

I'm not sure what I did wrong when first trying PseudoInstExpansion with PseudoTailIndirect, but I'm not seeing any problems now. Replace the current PseudoTAILIndirect definition with the following and drop the RISCVAsmPrinter changes:

def PseudoTAILIndirect : Pseudo<(outs), (ins GPRTC:$rs1), [(Tail GPRTC:$rs1)]>,
                         PseudoInstExpansion<(JALR X0, GPR:$rs1, 0)>;

This generates the following in RISCVGenMCPseudoLowering.inc:

case RISCV::PseudoTAILIndirect: {
  MCInst TmpInst;
  MCOperand MCOp;
  TmpInst.setOpcode(RISCV::JALR);
  // Operand: rd
  TmpInst.addOperand(MCOperand::createReg(RISCV::X0));
  // Operand: rs1
  lowerOperand(MI->getOperand(0), MCOp);
  TmpInst.addOperand(MCOp);
  // Operand: imm12
  TmpInst.addOperand(MCOperand::createImm(0));
  EmitToStreamer(OutStreamer, TmpInst);
  break;
}

With that change, this looks good to me.

[mgrang]

Added a PseudoInstExpansion rule for PseudoTAILIndirect as per Alex's suggestion.

[mgrang]

Thanks for the pointer Alex. I guess what I was doing incorrect was specifying GPRTC as the reg class in the PseudoInstExpansion which made the tablegen trip.

def PseudoTAILIndirect : Pseudo<(outs), (ins GPRTC:$rs1), [(Tail GPRTC:$rs1)]>,
                         PseudoInstExpansion<(JALR X0, GPRTC:$rs1, 0)>;

With your suggestion, PseudoTAILIndirect is now an almost exact replica of PseudoCALLIndirect. Thanks again!

[asb]

Fantastic, looks good to me (though see my comment for a tiny RISCVInstrInfo.td change to make prior to commit). Thanks!

lib/Target/RISCV/RISCVInstrInfo.td

680–681

This pattern isn't needed as it's already present in the PseudoTAILIndirect definition.

[mgrang]

This is merged in rL333137.

lib/Target/RISCV/MCTargetDesc/RISCVMCCodeEmitter.cpp

RISCVMCCodeEmitter(MCContext &ctx, MCInstrInfo const &MCII)
       : Ctx(ctx), MCII(MCII) {}
 
   ~RISCVMCCodeEmitter() override {}
 
   void encodeInstruction(const MCInst &MI, raw_ostream &OS,
                          SmallVectorImpl<MCFixup> &Fixups,
                          const MCSubtargetInfo &STI) const override;
 
-  void expandFunctionCall(const MCInst &MI, raw_ostream &OS,
+  unsigned expandFunctionCall(const MCInst &MI, raw_ostream &OS,
                               SmallVectorImpl<MCFixup> &Fixups,
                               const MCSubtargetInfo &STI) const;
 
   /// TableGen'erated function for getting the binary encoding for an
   /// instruction.
   uint64_t getBinaryCodeForInstr(const MCInst &MI,
                                  SmallVectorImpl<MCFixup> &Fixups,
                                  const MCSubtargetInfo &STI) const;
 
   /// Return binary encoding of operand. If the machine operand requires

 } // end anonymous namespace
 
 MCCodeEmitter *llvm::createRISCVMCCodeEmitter(const MCInstrInfo &MCII,
                                               const MCRegisterInfo &MRI,
                                               MCContext &Ctx) {
   return new RISCVMCCodeEmitter(Ctx, MCII);
 }
 
 // Expand PseudoCALL to AUIPC and JALR with relocation types.
 // We expand PseudoCALL while encoding, meaning AUIPC and JALR won't go through
 // RISCV MC to MC compressed instruction transformation. This is acceptable
 // because AUIPC has no 16-bit form and C_JALR have no immediate operand field.
 // We let linker relaxation deal with it. When linker relaxation enabled,
 // AUIPC and JALR have chance relax to JAL. If C extension is enabled,
 // JAL has chance relax to C_JAL.
-void RISCVMCCodeEmitter::expandFunctionCall(const MCInst &MI, raw_ostream &OS,
-                                            SmallVectorImpl<MCFixup> &Fixups,
-                                            const MCSubtargetInfo &STI) const {
+unsigned
+RISCVMCCodeEmitter::expandFunctionCall(const MCInst &MI, raw_ostream &OS,
   MCInst TmpInst;
   MCOperand Func = MI.getOperand(0);
-  unsigned Ra = (MI.getOpcode() == RISCV::PseudoTAIL) ? RISCV::X6 : RISCV::X1;
   uint32_t Binary;
 
+  // For an indirect tail call, emit JALR X0, 0(Reg).
+  // TODO: We had to custom lower this here since for tail calls we cannot
+  // allow JALR with any GPR; we need to restrict the register class to only
+  // caller-saved regs [x5-x7]. Hence we had to create a new regclass GPRTC
+  // which is a subclass of GPR. However, currently tablegen does not support
+  // the use of the registers of a subclass of the allowed regclass for an
+  // instruction. Once this is supported, we can replace the custom lowering
+  // here with a PseudoInstExpansion rule in RISCVInstrInfo.td.
+  if (MI.getOpcode() == RISCV::PseudoTAILIndirect) {
+    TmpInst = MCInstBuilder(RISCV::JALR)
+                .addReg(RISCV::X0)
+                .addReg(Func.getReg())
+                .addImm(0);
+    Binary = getBinaryCodeForInstr(TmpInst, Fixups, STI);
+    support::endian::Writer<support::little>(OS).write(Binary);
+    return 1 /* MCNumEmitted */;
+  }
+
+  unsigned Ra = (MI.getOpcode() == RISCV::PseudoTAIL) ? RISCV::X6 : RISCV::X1;
+
   assert(Func.isExpr() && "Expected expression");
 
   const MCExpr *Expr = Func.getExpr();
 
   // Create function call expression CallExpr for AUIPC.
   const MCExpr *CallExpr =
       RISCVMCExpr::create(Expr, RISCVMCExpr::VK_RISCV_CALL, Ctx);
 
   // Emit AUIPC Ra, Func with R_RISCV_CALL relocation type.
   TmpInst = MCInstBuilder(RISCV::AUIPC)
                 .addReg(Ra)
                 .addOperand(MCOperand::createExpr(CallExpr));
   Binary = getBinaryCodeForInstr(TmpInst, Fixups, STI);
   support::endian::Writer<support::little>(OS).write(Binary);
 
   // Emit JALR Ra, Ra, 0
   TmpInst = MCInstBuilder(RISCV::JALR).addReg(Ra).addReg(Ra).addImm(0);
   Binary = getBinaryCodeForInstr(TmpInst, Fixups, STI);
   support::endian::Writer<support::little>(OS).write(Binary);
+  return 2 /* MCNumEmitted */;
 }
 
 void RISCVMCCodeEmitter::encodeInstruction(const MCInst &MI, raw_ostream &OS,
                                            SmallVectorImpl<MCFixup> &Fixups,
                                            const MCSubtargetInfo &STI) const {
   const MCInstrDesc &Desc = MCII.get(MI.getOpcode());
   // Get byte count of instruction.
   unsigned Size = Desc.getSize();
 
   if (MI.getOpcode() == RISCV::PseudoCALL ||
-      MI.getOpcode() == RISCV::PseudoTAIL) {
-    expandFunctionCall(MI, OS, Fixups, STI);
-    MCNumEmitted += 2;
+      MI.getOpcode() == RISCV::PseudoTAIL ||
+      MI.getOpcode() == RISCV::PseudoTAILIndirect) {
+    MCNumEmitted += expandFunctionCall(MI, OS, Fixups, STI);
     return;
   }
 
   switch (Size) {
   default:
     llvm_unreachable("Unhandled encodeInstruction length!");
   case 2: {
     uint16_t Bits = getBinaryCodeForInstr(MI, Fixups, STI);

lib/Target/RISCV/RISCVISelLowering.h

private:
   SDValue lowerGlobalAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerBlockAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerConstantPool(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerExternalSymbol(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerSELECT(SDValue Op, SelectionDAG &DAG) const;
   SDValue lowerVASTART(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
+
+  bool IsEligibleForTailCallOptimization(CCState &CCInfo,
+    CallLoweringInfo &CLI, MachineFunction &MF,
+    const SmallVector<CCValAssign, 16> &ArgLocs) const;
 };
 }
 
 #endif

lib/Target/RISCV/RISCVISelLowering.cpp

 //===----------------------------------------------------------------------===//
 
 #include "RISCVISelLowering.h"
 #include "RISCV.h"
 #include "RISCVMachineFunctionInfo.h"
 #include "RISCVRegisterInfo.h"
 #include "RISCVSubtarget.h"
 #include "RISCVTargetMachine.h"
+#include "llvm/ADT/Statistic.h"
 #include "llvm/CodeGen/CallingConvLower.h"
 #include "llvm/CodeGen/MachineFrameInfo.h"
 #include "llvm/CodeGen/MachineFunction.h"
 #include "llvm/CodeGen/MachineInstrBuilder.h"
 #include "llvm/CodeGen/MachineRegisterInfo.h"
 #include "llvm/CodeGen/SelectionDAGISel.h"
 #include "llvm/CodeGen/TargetLoweringObjectFileImpl.h"
 #include "llvm/CodeGen/ValueTypes.h"
 #include "llvm/IR/DiagnosticInfo.h"
 #include "llvm/IR/DiagnosticPrinter.h"
 #include "llvm/Support/Debug.h"
 #include "llvm/Support/ErrorHandling.h"
 #include "llvm/Support/raw_ostream.h"
 
 using namespace llvm;
 
 #define DEBUG_TYPE "riscv-lower"
 
+STATISTIC(NumTailCalls, "Number of tail calls");
+
 RISCVTargetLowering::RISCVTargetLowering(const TargetMachine &TM,
                                          const RISCVSubtarget &STI)
     : TargetLowering(TM), Subtarget(STI) {
 
   MVT XLenVT = Subtarget.getXLenVT();
 
   // Set up the register classes.
   addRegisterClass(XLenVT, &RISCV::GPRRegClass);
static SDValue unpackF64OnRV32DSoftABI(SelectionDAG &DAG, SDValue Chain,
 
   assert(VA.isRegLoc() && "Expected register VA assignment");
 
   unsigned LoVReg = RegInfo.createVirtualRegister(&RISCV::GPRRegClass);
   RegInfo.addLiveIn(VA.getLocReg(), LoVReg);
   SDValue Lo = DAG.getCopyFromReg(Chain, DL, LoVReg, MVT::i32);
   SDValue Hi;
   if (VA.getLocReg() == RISCV::X17) {
     // Second half of f64 is passed on the stack.
     int FI = MFI.CreateFixedObject(4, 0, /*Immutable=*/true);
     SDValue FIN = DAG.getFrameIndex(FI, MVT::i32);
     Hi = DAG.getLoad(MVT::i32, DL, Chain, FIN,
                      MachinePointerInfo::getFixedStack(MF, FI));
   } else {
     // Second half of f64 is passed in another GPR.
     unsigned HiVReg = RegInfo.createVirtualRegister(&RISCV::GPRRegClass);
     RegInfo.addLiveIn(VA.getLocReg() + 1, HiVReg);
     Hi = DAG.getCopyFromReg(Chain, DL, HiVReg, MVT::i32);
   }
   return DAG.getNode(RISCVISD::BuildPairF64, DL, MVT::f64, Lo, Hi);
 }
 
 // Transform physical registers into virtual registers.
 SDValue RISCVTargetLowering::LowerFormalArguments(
     SDValue Chain, CallingConv::ID CallConv, bool IsVarArg,
     const SmallVectorImpl<ISD::InputArg> &Ins, const SDLoc &DL,
     SelectionDAG &DAG, SmallVectorImpl<SDValue> &InVals) const {
 
   switch (CallConv) {
   default:
     report_fatal_error("Unsupported calling convention");
   case CallingConv::C:
   case CallingConv::Fast:
     break;
   }
 
   MachineFunction &MF = DAG.getMachineFunction();
   EVT PtrVT = getPointerTy(DAG.getDataLayout());
   MVT XLenVT = Subtarget.getXLenVT();
   unsigned XLenInBytes = Subtarget.getXLen() / 8;
   // Used with vargs to acumulate store chains.
   std::vector<SDValue> OutChains;
SDValue RISCVTargetLowering::LowerFormalArguments(
   if (!OutChains.empty()) {
     OutChains.push_back(Chain);
     Chain = DAG.getNode(ISD::TokenFactor, DL, MVT::Other, OutChains);
   }
 
   return Chain;
 }
 
+/// IsEligibleForTailCallOptimization - Check whether the call is eligible
+/// for tail call optimization.
+/// Note: This is modelled after ARM's IsEligibleForTailCallOptimization.
+bool RISCVTargetLowering::IsEligibleForTailCallOptimization(
+  CCState &CCInfo, CallLoweringInfo &CLI, MachineFunction &MF,
+  const SmallVector<CCValAssign, 16> &ArgLocs) const {
+
+  auto &Callee = CLI.Callee;
+  auto CalleeCC = CLI.CallConv;
+  auto IsVarArg = CLI.IsVarArg;
+  auto &Outs = CLI.Outs;
+  auto &Caller = MF.getFunction();
+  auto CallerCC = Caller.getCallingConv();
+
+  // Do not tail call opt functions with "disable-tail-calls" attribute.
+  if (Caller.getFnAttribute("disable-tail-calls").getValueAsString() == "true")
+    return false;
+
+  // Exception-handling functions need a special set of instructions to
+  // indicate a return to the hardware. Tail-calling another function would
+  // probably break this.
+  // TODO: The "interrupt" attribute isn't currently defined by RISC-V. This
+  // should be expanded as new function attributes are introduced.
+  if (Caller.hasFnAttribute("interrupt"))
+    return false;
+
+  // Do not tail call opt functions with varargs.
+  if (IsVarArg)
+    return false;
+
+  // Do not tail call opt if the stack is used to pass parameters.
+  if (CCInfo.getNextStackOffset() != 0)
+    return false;
+
+  // Do not tail call opt if any parameters need to be passed indirectly.
+  // Since long doubles (fp128) and i128 are larger than 2*XLEN, they are
+  // passed indirectly. So the address of the value will be passed in a
+  // register, or if not available, then the address is put on the stack. In
+  // order to pass indirectly, space on the stack often needs to be allocated
+  // in order to store the value. In this case the CCInfo.getNextStackOffset()
+  // != 0 check is not enough and we need to check if any CCValAssign ArgsLocs
+  // are passed CCValAssign::Indirect.
+  for (auto &VA : ArgLocs)
+    if (VA.getLocInfo() == CCValAssign::Indirect)
+      return false;
+
+  // Do not tail call opt if either caller or callee uses struct return
+  // semantics.
+  auto IsCallerStructRet = Caller.hasStructRetAttr();
+  auto IsCalleeStructRet = Outs.empty() ? false : Outs[0].Flags.isSRet();
+  if (IsCallerStructRet || IsCalleeStructRet)
+    return false;
+
+  // Externally-defined functions with weak linkage should not be
+  // tail-called. The behaviour of branch instructions in this situation (as
+  // used for tail calls) is implementation-defined, so we cannot rely on the
+  // linker replacing the tail call with a return.
+  if (GlobalAddressSDNode *G = dyn_cast<GlobalAddressSDNode>(Callee)) {
+    const GlobalValue *GV = G->getGlobal();
+    if (GV->hasExternalWeakLinkage())
+      return false;
+  }
+
+  // The callee has to preserve all registers the caller needs to preserve.
+  const RISCVRegisterInfo *TRI = Subtarget.getRegisterInfo();
+  const uint32_t *CallerPreserved = TRI->getCallPreservedMask(MF, CallerCC);
+  if (CalleeCC != CallerCC) {
+    const uint32_t *CalleePreserved = TRI->getCallPreservedMask(MF, CalleeCC);
+    if (!TRI->regmaskSubsetEqual(CallerPreserved, CalleePreserved))
+      return false;
+  }
+
+  // Byval parameters hand the function a pointer directly into the stack area
+  // we want to reuse during a tail call. Working around this *is* possible
+  // but less efficient and uglier in LowerCall.
+  for (auto &Arg : Outs)
+    if (Arg.Flags.isByVal())
+      return false;
+
+  return true;
+}
+
 // Lower a call to a callseq_start + CALL + callseq_end chain, and add input
 // and output parameter nodes.
 SDValue RISCVTargetLowering::LowerCall(CallLoweringInfo &CLI,
                                        SmallVectorImpl<SDValue> &InVals) const {
   SelectionDAG &DAG = CLI.DAG;
   SDLoc &DL = CLI.DL;
   SmallVectorImpl<ISD::OutputArg> &Outs = CLI.Outs;
   SmallVectorImpl<SDValue> &OutVals = CLI.OutVals;
   SmallVectorImpl<ISD::InputArg> &Ins = CLI.Ins;
   SDValue Chain = CLI.Chain;
   SDValue Callee = CLI.Callee;
-  CLI.IsTailCall = false;
+  bool &IsTailCall = CLI.IsTailCall;
   CallingConv::ID CallConv = CLI.CallConv;
   bool IsVarArg = CLI.IsVarArg;
   EVT PtrVT = getPointerTy(DAG.getDataLayout());
   MVT XLenVT = Subtarget.getXLenVT();
 
   MachineFunction &MF = DAG.getMachineFunction();
 
   // Analyze the operands of the call, assigning locations to each operand.
   SmallVector<CCValAssign, 16> ArgLocs;
   CCState ArgCCInfo(CallConv, IsVarArg, MF, ArgLocs, *DAG.getContext());
   analyzeOutputArgs(MF, ArgCCInfo, Outs, /*IsRet=*/false, &CLI);
 
+  // Check if it's really possible to do a tail call.
+  if (IsTailCall)
+    IsTailCall = IsEligibleForTailCallOptimization(ArgCCInfo, CLI, MF,
+                                                   ArgLocs);
+
+  if (IsTailCall)
+    ++NumTailCalls;
+  else if (CLI.CS && CLI.CS.isMustTailCall())
+    report_fatal_error("failed to perform tail call elimination on a call "
+                       "site marked musttail");
+
   // Get a count of how many bytes are to be pushed on the stack.
   unsigned NumBytes = ArgCCInfo.getNextStackOffset();
 
   // Create local copies for byval args
   SmallVector<SDValue, 8> ByValArgs;
   for (unsigned i = 0, e = Outs.size(); i != e; ++i) {
     ISD::ArgFlagsTy Flags = Outs[i].Flags;
     if (!Flags.isByVal())
       continue;
 
     SDValue Arg = OutVals[i];
     unsigned Size = Flags.getByValSize();
     unsigned Align = Flags.getByValAlign();
 
     int FI = MF.getFrameInfo().CreateStackObject(Size, Align, /*isSS=*/false);
     SDValue FIPtr = DAG.getFrameIndex(FI, getPointerTy(DAG.getDataLayout()));
     SDValue SizeNode = DAG.getConstant(Size, DL, XLenVT);
 
     Chain = DAG.getMemcpy(Chain, DL, FIPtr, Arg, SizeNode, Align,
                           /*IsVolatile=*/false,
                           /*AlwaysInline=*/false,
-                          /*isTailCall=*/false, MachinePointerInfo(),
+                          IsTailCall, MachinePointerInfo(),
                           MachinePointerInfo());
     ByValArgs.push_back(FIPtr);
   }
 
+  if (!IsTailCall)
     Chain = DAG.getCALLSEQ_START(Chain, NumBytes, 0, CLI.DL);
 
   // Copy argument values to their designated locations.
   SmallVector<std::pair<unsigned, SDValue>, 8> RegsToPass;
   SmallVector<SDValue, 8> MemOpChains;
   SDValue StackPtr;
   for (unsigned i = 0, j = 0, e = ArgLocs.size(); i != e; ++i) {
     CCValAssign &VA = ArgLocs[i];
     SDValue ArgValue = OutVals[i];
if (VA.isRegLoc()) {
       // Queue up the argument copies and emit them at the end.
       RegsToPass.push_back(std::make_pair(VA.getLocReg(), ArgValue));
     } else {
       assert(VA.isMemLoc() && "Argument not register or memory");
 
       // Work out the address of the stack slot.
       if (!StackPtr.getNode())
         StackPtr = DAG.getCopyFromReg(Chain, DL, RISCV::X2, PtrVT);
+
+      if (!IsTailCall) {
         SDValue Address =
             DAG.getNode(ISD::ADD, DL, PtrVT, StackPtr,
                         DAG.getIntPtrConstant(VA.getLocMemOffset(), DL));
 
         // Emit the store.
         MemOpChains.push_back(
             DAG.getStore(Chain, DL, ArgValue, Address, MachinePointerInfo()));
       }
     }
+  }
 
   // Join the stores, which are independent of one another.
   if (!MemOpChains.empty())
     Chain = DAG.getNode(ISD::TokenFactor, DL, MVT::Other, MemOpChains);
 
   SDValue Glue;
 
+  // Tail call byval lowering might overwrite argument registers so in case of
+  // tail call optimization the copies to registers are lowered to 'real' stack
+  // slot.
+  // Force all the incoming stack arguments to be loaded from the stack
+  // before any new outgoing arguments are stored to the stack, because the
+  // outgoing stack slots may alias the incoming argument stack slots, and
+  // the alias isn't otherwise explicit. This is slightly more conservative
+  // than necessary, because it means that each store effectively depends
+  // on every argument instead of just those arguments it would clobber.
+  if (IsTailCall)
+    Glue = SDValue();
+
   // Build a sequence of copy-to-reg nodes, chained and glued together.
   for (auto &Reg : RegsToPass) {
     Chain = DAG.getCopyToReg(Chain, DL, Reg.first, Reg.second, Glue);
     Glue = Chain.getValue(1);
   }
 
+  if (IsTailCall)
+    Glue = SDValue();
+
   // If the callee is a GlobalAddress/ExternalSymbol node, turn it into a
   // TargetGlobalAddress/TargetExternalSymbol node so that legalize won't
   // split it and then direct call can be matched by PseudoCALL.
   if (GlobalAddressSDNode *S = dyn_cast<GlobalAddressSDNode>(Callee)) {
     Callee = DAG.getTargetGlobalAddress(S->getGlobal(), DL, PtrVT, 0, 0);
   } else if (ExternalSymbolSDNode *S = dyn_cast<ExternalSymbolSDNode>(Callee)) {
     Callee = DAG.getTargetExternalSymbol(S->getSymbol(), PtrVT, 0);
   }
 
   // The first call operand is the chain and the second is the target address.
   SmallVector<SDValue, 8> Ops;
   Ops.push_back(Chain);
   Ops.push_back(Callee);
 
   // Add argument registers to the end of the list so that they are
   // known live into the call.
   for (auto &Reg : RegsToPass)
     Ops.push_back(DAG.getRegister(Reg.first, Reg.second.getValueType()));
 
+  if (!IsTailCall) {
     // Add a register mask operand representing the call-preserved registers.
     const TargetRegisterInfo *TRI = Subtarget.getRegisterInfo();
     const uint32_t *Mask = TRI->getCallPreservedMask(MF, CallConv);
     assert(Mask && "Missing call preserved mask for calling convention");
     Ops.push_back(DAG.getRegisterMask(Mask));
+  }
 
   // Glue the call to the argument copies, if any.
   if (Glue.getNode())
     Ops.push_back(Glue);
 
   // Emit the call.
   SDVTList NodeTys = DAG.getVTList(MVT::Other, MVT::Glue);
+
+  if (IsTailCall) {
+    MF.getFrameInfo().setHasTailCall();
+    return DAG.getNode(RISCVISD::TAIL, DL, NodeTys, Ops);
+  }
+
   Chain = DAG.getNode(RISCVISD::CALL, DL, NodeTys, Ops);
   Glue = Chain.getValue(1);
 
   // Mark the end of the call, which is glued to the call itself.
   Chain = DAG.getCALLSEQ_END(Chain,
                              DAG.getConstant(NumBytes, DL, PtrVT, true),
                              DAG.getConstant(0, DL, PtrVT, true),
                              Glue, DL);

lib/Target/RISCV/RISCVInstrInfo.cpp

unsigned RISCVInstrInfo::getInstSizeInBytes(const MachineInstr &MI) const {
 
   switch (Opcode) {
   default: { return get(Opcode).getSize(); }
   case TargetOpcode::EH_LABEL:
   case TargetOpcode::IMPLICIT_DEF:
   case TargetOpcode::KILL:
   case TargetOpcode::DBG_VALUE:
     return 0;
+  case RISCV::PseudoTAILIndirect:
+    return 4;
   case RISCV::PseudoCALL:
+  case RISCV::PseudoTAIL:
     return 8;
   case TargetOpcode::INLINEASM: {
     const MachineFunction &MF = *MI.getParent()->getParent();
     const auto &TM = static_cast<const RISCVTargetMachine &>(MF.getTarget());
     return getInlineAsmLength(MI.getOperand(0).getSymbolName(),
                               *TM.getMCAsmInfo());
   }
   }
 }

lib/Target/RISCV/RISCVInstrInfo.td

 let isCall = 1, Defs = [X1] in
 def PseudoCALLIndirect : Pseudo<(outs), (ins GPR:$rs1), [(Call GPR:$rs1)]>,
                          PseudoInstExpansion<(JALR X1, GPR:$rs1, 0)>;
 
 let isBarrier = 1, isReturn = 1, isTerminator = 1 in
 def PseudoRET : Pseudo<(outs), (ins), [(RetFlag)]>,
                 PseudoInstExpansion<(JALR X0, X1, 0)>;
 
 // PseudoTAIL is a pseudo instruction similar to PseudoCALL and will eventually
 // expand to auipc and jalr while encoding.
 // Define AsmString to print "tail" when compile with -S flag.
 let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1, Uses = [X2],
     isCodeGenOnly = 0 in
 def PseudoTAIL : Pseudo<(outs), (ins bare_symbol:$dst), []> {
   let AsmString = "tail\t$dst";
 }
 
+let isCall = 1, isTerminator = 1, isReturn = 1, isBarrier = 1, Uses = [X2] in
+def PseudoTAILIndirect : Pseudo<(outs), (ins GPRTC:$dst), []>;
+
 def : Pat<(Tail (iPTR tglobaladdr:$dst)),
           (PseudoTAIL texternalsym:$dst)>;
 def : Pat<(Tail (iPTR texternalsym:$dst)),
           (PseudoTAIL texternalsym:$dst)>;
+def : Pat<(Tail GPRTC:$dst),
+          (PseudoTAILIndirect GPRTC:$dst)>;
 
 /// Loads
 
 multiclass LdPat<PatFrag LoadOp, RVInst Inst> {
   def : Pat<(LoadOp GPR:$rs1), (Inst GPR:$rs1, 0)>;
   def : Pat<(LoadOp AddrFI:$rs1), (Inst AddrFI:$rs1, 0)>;
   def : Pat<(LoadOp (add GPR:$rs1, simm12:$imm12)),
             (Inst GPR:$rs1, simm12:$imm12)>;
   def : Pat<(LoadOp (add AddrFI:$rs1, simm12:$imm12)),

lib/Target/RISCV/RISCVRegisterInfo.td

def GPRC : RegisterClass<"RISCV", [XLenVT], 32, (add
     (sequence "X%u", 10, 15),
     (sequence "X%u", 8, 9)
   )> {
   let RegInfos = RegInfoByHwMode<
       [RV32,              RV64,              DefaultMode],
       [RegInfo<32,32,32>, RegInfo<64,64,64>, RegInfo<32,32,32>]>;
 }
 
+// For tail calls, we can't use callee-saved registers, as they are restored to
+// the saved value before the tail call, which would clobber a call address.
+def GPRTC : RegisterClass<"RISCV", [XLenVT], 32, (add
+    (sequence "X%u", 5, 7),
+    (sequence "X%u", 10, 17),
+    (sequence "X%u", 28, 31)
+  )> {
+  let RegInfos = RegInfoByHwMode<
+      [RV32,              RV64,              DefaultMode],
+      [RegInfo<32,32,32>, RegInfo<64,64,64>, RegInfo<32,32,32>]>;
+}
+
 def SP : RegisterClass<"RISCV", [XLenVT], 32, (add X2)> {
   let RegInfos = RegInfoByHwMode<
       [RV32,              RV64,              DefaultMode],
       [RegInfo<32,32,32>, RegInfo<64,64,64>, RegInfo<32,32,32>]>;
 }
 
 // Floating point registers
 let RegAltNameIndices = [ABIRegAltName] in {

test/CodeGen/RISCV/disable-tail-calls.ll

+; Check that command line option "-disable-tail-calls" overrides function
+; attribute "disable-tail-calls".
+
+; RUN: llc < %s -mtriple=riscv32-unknown-elf \
+; RUN: | FileCheck %s --check-prefixes=CALLER1,NOTAIL
+; RUN: llc < %s -mtriple=riscv32-unknown-elf -disable-tail-calls \
+; RUN: | FileCheck %s --check-prefixes=CALLER1,NOTAIL
+; RUN: llc < %s -mtriple=riscv32-unknown-elf -disable-tail-calls=false \
+; RUN: | FileCheck %s --check-prefixes=CALLER1,TAIL
+
+; RUN: llc < %s -mtriple=riscv32-unknown-elf \
+; RUN: | FileCheck %s --check-prefixes=CALLER2,TAIL
+; RUN: llc < %s -mtriple=riscv32-unknown-elf -disable-tail-calls \
+; RUN: | FileCheck %s --check-prefixes=CALLER2,NOTAIL
+; RUN: llc < %s -mtriple=riscv32-unknown-elf -disable-tail-calls=false \
+; RUN: | FileCheck %s --check-prefixes=CALLER2,TAIL
+
+; CALLER1-LABEL: {{\_?}}caller1
+; CALLER2-LABEL: {{\_?}}caller2
+; NOTAIL-NOT: tail callee
+; NOTAIL: call callee
+; TAIL: tail callee
+; TAIL-NOT: call callee
+
+; Function with attribute #0 = { "disable-tail-calls"="true" }
+define i32 @caller1(i32 %a) #0 {
+entry:
+  %call = tail call i32 @callee(i32 %a)
+  ret i32 %call
+}
+
+define i32 @caller2(i32 %a) {
+entry:
+  %call = tail call i32 @callee(i32 %a)
+  ret i32 %call
+}
+
+declare i32 @callee(i32)
+
+attributes #0 = { "disable-tail-calls"="true" }

test/CodeGen/RISCV/tail-calls.ll

+; RUN: llc -mtriple riscv32-unknown-linux-gnu -o - %s | FileCheck %s
+; RUN: llc -mtriple riscv32-unknown-elf       -o - %s | FileCheck %s
+
+; Perform tail call optimization.
+declare i32 @callee(i32 %i)
+define i32 @caller(i32 %i) {
+; CHECK-LABEL: caller
+; CHECK: tail callee
+entry:
+  %r = tail call i32 @callee(i32 %i)
+  ret i32 %r
+}
+
+; Do not tail call optimize functions with varargs.
+declare i32 @callee_varargs(i32, ...)
+define void @caller_varargs(i32 %a, i32 %b) {
+; CHECK-LABEL: caller_varargs
+; CHECK-NOT: tail callee_varargs
+; CHECK: call callee_varargs
+entry:
+  %call = tail call i32 (i32, ...) @callee_varargs(i32 %a, i32 %b, i32 %b, i32 %a)
+  ret void
+}
+
+; Do not tail call optimize if stack is used to pass parameters.
+declare i32 @callee_args(i32 %a, i32 %b, i32 %c, i32 %dd, i32 %e, i32 %ff, i32 %g, i32 %h, i32 %i, i32 %j, i32 %k, i32 %l, i32 %m, i32 %n)
+define i32 @caller_args(i32 %a, i32 %b, i32 %c, i32 %dd, i32 %e, i32 %ff, i32 %g, i32 %h, i32 %i, i32 %j, i32 %k, i32 %l, i32 %m, i32 %n) {
+; CHECK-LABEL: caller_args
+; CHECK-NOT: tail callee_args
+; CHECK: call callee_args
+entry:
+  %r = tail call i32 @callee_args(i32 %a, i32 %b, i32 %c, i32 %dd, i32 %e, i32 %ff, i32 %g, i32 %h, i32 %i, i32 %j, i32 %k, i32 %l, i32 %m, i32 %n)
+  ret i32 %r
+}
+
+; Do not tail call optimize if parameters need to be passed indirectly.
+declare i32 @callee_indirect(fp128 %a)
+define void @caller_indirect() {
+; CHECK-LABEL: caller_indirect
+; CHECK-NOT: tail callee_indirect
+; CHECK: call callee_indirect
+entry:
+  %call = tail call i32 @callee_indirect(fp128 0xL00000000000000003FFF000000000000)
+  ret void
+}
+
+; Externally-defined functions with weak linkage should not be tail-called.
+; The behaviour of branch instructions in this situation (as used for tail
+; calls) is implementation-defined, so we cannot rely on the linker replacing
+; the tail call with a return.
+declare extern_weak void @callee_weak()
+define void @caller_weak() {
+; CHECK-LABEL: caller_weak
+; CHECK-NOT: tail callee_weak
+; CHECK: call callee_weak
+entry:
+  tail call void @callee_weak()
+  ret void
+}
+
+; Exception-handling functions need a special set of instructions to indicate a
+; return to the hardware. Tail-calling another function would probably break
+; this.
+declare void @callee_irq()
+define void @caller_irq() #0 {
+; CHECK-LABEL: caller_irq
+; CHECK-NOT: tail callee_irq
+; CHECK: call callee_irq
+entry:
+  tail call void @callee_irq()
+  ret void
+}
+attributes #0 = { "interrupt" }
+
+; Byval parameters hand the function a pointer directly into the stack area
+; we want to reuse during a tail call. Do not tail call optimize functions with
+; byval parameters.
+declare i32 @callee_byval(i32** byval %a)
+define i32 @caller_byval() {
+; CHECK-LABEL: caller_byval
+; CHECK-NOT: tail callee_byval
+; CHECK: call callee_byval
+entry:
+  %a = alloca i32*
+  %r = tail call i32 @callee_byval(i32** byval %a)
+  ret i32 %r
+}