[WebAssembly] Implement __builtin_return_address for emscripten

[quantum]

Summary

In this patch, ISD::RETURNADDR is lowered on the emscripten target
to the new Emscripten runtime function emscripten_return_address, which
implements the functionality.

[tlively]

llvm/test/CodeGen/WebAssembly/return-address.ll

6 ↗

(On Diff #200541)

Can you add a comment to this test saying what it is for? Also, it would be good to add a test to check for an error on wasm32-unknown-unknown.

11 ↗

(On Diff #200541)

how about naming this test_returnaddress to call attention to what's being tested.

[quantum]

• Renamed test function in LLVM IR to test_returnaddress.
• Created test for wasm32-unknown-unknown and expect it to fail.

[sunfish]

Would it make sense to take this opportunity to rename the library function, from emscripten_return_address to something more general, like __wasm_return_address or __wasm_callsite_identifier or something, so that non-Emscripten environments could implement it too if they wished?

[tlively]

llvm/test/CodeGen/WebAssembly/return-address-emscripten.ll

6 ↗

(On Diff #200575)

Please add a newline after the explanatory comment to visually separate it from the CHECK lines.

llvm/test/CodeGen/WebAssembly/return-address-unknown.ll

2 ↗

(On Diff #200575)

It would be better to pipe the error message to FileCheck and Check for the exact message you are expecting, rather than to just expect the test as a whole to fail.

[quantum]

• Check the error message on wasm32-unknown-unknown
• Added new lines to visually separate test description from checks

[tlively]

In D62210#1510838, @sunfish wrote:

Would it make sense to take this opportunity to rename the library function, from emscripten_return_address to something more general, like __wasm_return_address or __wasm_callsite_identifier or something, so that non-Emscripten environments could implement it too if they wished?

I would image that WASI would want its own WASI-namespaced version of this. Are other system functions going to be general over all wasm OSes?

[quantum]

In D62210#1510838, @sunfish wrote:

Would it make sense to take this opportunity to rename the library function, from emscripten_return_address to something more general, like __wasm_return_address or __wasm_callsite_identifier or something, so that non-Emscripten environments could implement it too if they wished?

I think we can always check the subtarget before calling setLibcallName to accommodate alternative names for this function, if other targets decide to implement return address with a library call.

It is not yet clear how non-Emscripten environments will implement __builtin_return_address at all. It would be premature to declare a function for them to implement.

[tlively]

llvm/test/CodeGen/WebAssembly/return-address-unknown.ll

2 ↗

(On Diff #200576)

I don't think this XFAIL should be necessary any more, right?

[quantum]

llvm/test/CodeGen/WebAssembly/return-address-unknown.ll

2 ↗

(On Diff #200576)

It is necessary. Without the XFAIL it gets count as an unexpected failure.

[sunfish]

A function like this might be implemented in compiler_rt/libgcc or libc, which might in make future WASI system calls or future wasm language features underneath. An interface like __wasm_return_address doesn't commit to a particular implementation. I'm not suggesting enabling it for other targets now, just asking if it makes sense to pick a name which isn't tied to Emscripten.

If Emscripten wishes to support the WASI ABI in the future, it may have to support whatever name WASI ends up picking in addition to the Emscripten-specific name. However, it isn't a show stopper if Emscripten ends up having to support multiple names, so I don't have a strong opinion here.

[aheejin]

Nice!

• Please run clang-format before you submit patches
• When you did what the review suggested, please click 'Done' checkbox, so that the reviewer will know which one was taken care of and which one was not.

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

994 ↗

(On Diff #200576)

Does this mean we ignore the whole node if the argument is not a constant? How about signaling a failure?

llvm/lib/Target/WebAssembly/WebAssemblyRuntimeLibcallSignatures.cpp

468 ↗

(On Diff #200576)

How about moving this up, before all undefined ones?

496 ↗

(On Diff #200576)

This looks irrelevant to the comment about floats above. Maybe add a newline and comment for this?

[quantum]

Performed requested changes.

[quantum]

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

994 ↗

(On Diff #200576)

verifyReturnAddressArgumentIsConstant takes care of generating the error. This code is copied from what other targets are doing.

[quantum]

Used clang-format.

[sbc100]

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

277 ↗

(On Diff #200589)

I kind of agree with Dan re: the naming of this.

If anything we should we at least put "__" at the start so that its clear this is not a normal user function.

What is this called on other plaforms? Why not just call it "__builtin_return_address"?

992 ↗

(On Diff #200589)

Should we just lower this anyway? And thereby turn this from compile error into a link error if you happen to have not implemented it?

[quantum]

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

277 ↗

(On Diff #200589)

The function already exists in emscripten under that name. In emscripten, these functions don't have the __ prefix, for example, emscripten_get_callstack.

On other platforms, __builtin_return_address is lowered to code that reads LR or pulls it out of the stack, instead of a helper function.

992 ↗

(On Diff #200589)

I don't think so. We aren't sure what this can be lowered to on other WASM targets. Emscripten is the first target to use a library function to compute return addresses, and I would hesitate to extend this to other targets.

[tlively]

llvm/test/CodeGen/WebAssembly/return-address-unknown.ll

2 ↗

(On Diff #200576)

Oh, because llc is still "failing", even though the test now passes. Try adding a not to the run line, like ; RUN: not llc..

[quantum]

Use not instead of XFAIL

[tlively]

If a cross-platform version of this function emerges, we can always update the name here and in emscripten later. I think this is fine to merge now because it is consistent in the context of things that exist today and can easily be extended. I also think it is good to leave this as a compiler error; there's not much of a difference between this and any other runtime function that wasm does not support but that an individual user might want to supply. Maybe a separate PR should make all runtime functions linker errors instead of compile errors?

[tlively]

I'll wait for a second LGTM and take care of committing this tomorrow.

[sbc100]

llvm/include/llvm/IR/RuntimeLibcalls.def

543 ↗

(On Diff #200619)

This seems a little strange given that its in generic code and also its that only actual LIBCALL with nullptr as the second arg here. Can you explain why this is needed? I would imagine it should have a comment since its different from all the others.

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

277 ↗

(On Diff #200589)

OK, fair enough.

Can you add a TODO() here to replace this with a more generic thing (wither from tool-conventions, or from wasi I guess) in the future?

llvm/lib/Target/WebAssembly/WebAssemblyRuntimeLibcallSignatures.cpp

497 ↗

(On Diff #200619)

Does this need to be protected by an if (is_emscripten()) check too?

[sbc100]

Actually what happens right now if you *don't* land this? Will it result in link error: undefined symbol __builtin_return_address?

Is so, why not just make __builtin_return_address and alias for emscripten_return_address in emscripten and avoid this change completely?

[quantum]

In D62210#1511588, @sbc100 wrote:

Actually what happens right now if you *don't* land this? Will it result in link error: undefined symbol __builtin_return_address?

Is so, why not just make __builtin_return_address and alias for emscripten_return_address in emscripten and avoid this change completely?

What happens right now is llc just fails to build with the error message

WebAssembly hasn't implemented __builtin_return_address

This message was removed in this diff and replaced with a concrete implementation for Emscripten.

__builtin_return_address actually a compiler intrinsic and not a real function. I would have just implemented it in emscripten if it was a function.

llvm/include/llvm/IR/RuntimeLibcalls.def

543 ↗

(On Diff #200619)

This is in generic code because it appears that all library calls must be defined here. There is some common mechanism for TargetLowering to lower things to library calls that handles declaring external symbols and other stuff.

As for nullptr, this is not the first one to use it. This appears to be the name used for functions that don't have a standardized name to use as default, and putting the emscripten name would not have made sense here.

llvm/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

277 ↗

(On Diff #200589)

Sure I'll add a note here.

llvm/lib/Target/WebAssembly/WebAssemblyRuntimeLibcallSignatures.cpp

497 ↗

(On Diff #200619)

I don't think this is necessary. It won't be trying to look up the emscripten name in the map if we aren't on emscripten, so it doesn't hurt to have it in the map. The other direction is governed by a separate map.

[quantum]

Add a TODO about future action regarding emscripten_return_address libcall, depending on what other WASM backends end up doing.

llvm/trunk/include/llvm/IR/RuntimeLibcalls.def

 HANDLE_LIBCALL(ATOMIC_FETCH_NAND_16, "__atomic_fetch_nand_16")
 
 // Stack Protector Fail
 HANDLE_LIBCALL(STACKPROTECTOR_CHECK_FAIL, "__stack_chk_fail")
 
 // Deoptimization
 HANDLE_LIBCALL(DEOPTIMIZE, "__llvm_deoptimize")
 
+// Return address
+HANDLE_LIBCALL(RETURN_ADDRESS, nullptr)
+
 HANDLE_LIBCALL(UNKNOWN_LIBCALL, nullptr)
 
 #undef HANDLE_LIBCALL

llvm/trunk/lib/Target/WebAssembly/WebAssemblyISelLowering.h

SDValue LowerFormalArguments(SDValue Chain, CallingConv::ID CallConv,
                                bool IsVarArg,
                                const SmallVectorImpl<ISD::InputArg> &Ins,
                                const SDLoc &DL, SelectionDAG &DAG,
                                SmallVectorImpl<SDValue> &InVals) const override;
 
   // Custom lowering hooks.
   SDValue LowerOperation(SDValue Op, SelectionDAG &DAG) const override;
   SDValue LowerFrameIndex(SDValue Op, SelectionDAG &DAG) const;
+  SDValue LowerRETURNADDR(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerFRAMEADDR(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerGlobalAddress(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerExternalSymbol(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerBR_JT(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerJumpTable(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerVASTART(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerCopyToReg(SDValue Op, SelectionDAG &DAG) const;
   SDValue LowerIntrinsic(SDValue Op, SelectionDAG &DAG) const;

llvm/trunk/lib/Target/WebAssembly/WebAssemblyISelLowering.cpp

if (Subtarget->hasBulkMemory()) {
     MaxStoresPerMemsetOptSize = 1;
   }
 
   // Override the __gnu_f2h_ieee/__gnu_h2f_ieee names so that the f32 name is
   // consistent with the f64 and f128 names.
   setLibcallName(RTLIB::FPEXT_F16_F32, "__extendhfsf2");
   setLibcallName(RTLIB::FPROUND_F32_F16, "__truncsfhf2");
 
+  // Define the emscripten name for return address helper.
+  // TODO: when implementing other WASM backends, make this generic or only do
+  // this on emscripten depending on what they end up doing.
+  setLibcallName(RTLIB::RETURN_ADDRESS, "emscripten_return_address");
+
   // Always convert switches to br_tables unless there is only one case, which
   // is equivalent to a simple branch. This reduces code size for wasm, and we
   // defer possible jump table optimizations to the VM.
   setMinimumJumpTableEntries(2);
 }
 
 TargetLowering::AtomicExpansionKind
 WebAssemblyTargetLowering::shouldExpandAtomicRMWInIR(AtomicRMWInst *AI) const {
SDValue WebAssemblyTargetLowering::LowerOperation(SDValue Op,
   case ISD::BR_JT:
     return LowerBR_JT(Op, DAG);
   case ISD::VASTART:
     return LowerVASTART(Op, DAG);
   case ISD::BlockAddress:
   case ISD::BRIND:
     fail(DL, DAG, "WebAssembly hasn't implemented computed gotos");
     return SDValue();
-  case ISD::RETURNADDR: // Probably nothing meaningful can be returned here.
-    fail(DL, DAG, "WebAssembly hasn't implemented __builtin_return_address");
-    return SDValue();
+  case ISD::RETURNADDR:
+    return LowerRETURNADDR(Op, DAG);
   case ISD::FRAMEADDR:
     return LowerFRAMEADDR(Op, DAG);
   case ISD::CopyToReg:
     return LowerCopyToReg(Op, DAG);
   case ISD::EXTRACT_VECTOR_ELT:
   case ISD::INSERT_VECTOR_ELT:
     return LowerAccessVectorElement(Op, DAG);
   case ISD::INTRINSIC_VOID:

 }
 
 SDValue WebAssemblyTargetLowering::LowerFrameIndex(SDValue Op,
                                                    SelectionDAG &DAG) const {
   int FI = cast<FrameIndexSDNode>(Op)->getIndex();
   return DAG.getTargetFrameIndex(FI, Op.getValueType());
 }
 
+SDValue WebAssemblyTargetLowering::LowerRETURNADDR(SDValue Op,
+                                                   SelectionDAG &DAG) const {
+  SDLoc DL(Op);
+
+  if (!Subtarget->getTargetTriple().isOSEmscripten()) {
+    fail(DL, DAG,
+         "Non-Emscripten WebAssembly hasn't implemented "
+         "__builtin_return_address");
+    return SDValue();
+  }
+
+  if (verifyReturnAddressArgumentIsConstant(Op, DAG))
+    return SDValue();
+
+  unsigned Depth = cast<ConstantSDNode>(Op.getOperand(0))->getZExtValue();
+  return makeLibCall(DAG, RTLIB::RETURN_ADDRESS, Op.getValueType(),
+                     {DAG.getConstant(Depth, DL, MVT::i32)}, false, DL)
+      .first;
+}
+
 SDValue WebAssemblyTargetLowering::LowerFRAMEADDR(SDValue Op,
                                                   SelectionDAG &DAG) const {
   // Non-zero depths are not supported by WebAssembly currently. Use the
   // legalizer's default expansion, which is to return 0 (what this function is
   // documented to do).
   if (Op.getConstantOperandVal(0) > 0)
     return SDValue();
 

llvm/trunk/lib/Target/WebAssembly/WebAssemblyRuntimeLibcallSignatures.cpp

RuntimeLibcallSignatureTable() : Table(RTLIB::UNKNOWN_LIBCALL, unsupported) {
     // Memory
     Table[RTLIB::MEMCPY] = iPTR_func_iPTR_iPTR_iPTR;
     Table[RTLIB::MEMSET] = iPTR_func_iPTR_i32_iPTR;
     Table[RTLIB::MEMMOVE] = iPTR_func_iPTR_iPTR_iPTR;
 
     // __stack_chk_fail
     Table[RTLIB::STACKPROTECTOR_CHECK_FAIL] = func;
 
+    // Return address handling
+    Table[RTLIB::RETURN_ADDRESS] = i32_func_i32;
+
     // Element-wise Atomic memory
     // TODO: Fix these when we implement atomic support
     Table[RTLIB::MEMCPY_ELEMENT_UNORDERED_ATOMIC_1] = unsupported;
     Table[RTLIB::MEMCPY_ELEMENT_UNORDERED_ATOMIC_2] = unsupported;
     Table[RTLIB::MEMCPY_ELEMENT_UNORDERED_ATOMIC_4] = unsupported;
     Table[RTLIB::MEMCPY_ELEMENT_UNORDERED_ATOMIC_8] = unsupported;
     Table[RTLIB::MEMCPY_ELEMENT_UNORDERED_ATOMIC_16] = unsupported;
     Table[RTLIB::MEMMOVE_ELEMENT_UNORDERED_ATOMIC_1] = unsupported;
for (const auto &NameLibcall : NameLibcalls) {
                "duplicate libcall names in name map");
         Map[NameLibcall.first] = NameLibcall.second;
       }
     }
     // Override the __gnu_f2h_ieee/__gnu_h2f_ieee names so that the f32 name is
     // consistent with the f64 and f128 names.
     Map["__extendhfsf2"] = RTLIB::FPEXT_F16_F32;
     Map["__truncsfhf2"] = RTLIB::FPROUND_F32_F16;
+
+    Map["emscripten_return_address"] = RTLIB::RETURN_ADDRESS;
   }
 };
 
 } // end anonymous namespace
 
 void llvm::getLibcallSignature(const WebAssemblySubtarget &Subtarget,
                                RTLIB::Libcall LC,
                                SmallVectorImpl<wasm::ValType> &Rets,

llvm/trunk/test/CodeGen/WebAssembly/return-address-emscripten.ll

+; RUN: llc < %s -asm-verbose=false | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-emscripten"
+
+; This tests the implementation of __builtin_return_address on emscripten
+
+; CHECK-LABEL: test_returnaddress:
+; CHECK-NEXT: .functype test_returnaddress () -> (i32){{$}}
+; CHECK-NEXT: {{^}} i32.const 0{{$}}
+; CHECK-NEXT: {{^}} i32.call emscripten_return_address{{$}}
+; CHECK-NEXT: {{^}} end_function{{$}}
+define i8* @test_returnaddress() {
+  %r = call i8* @llvm.returnaddress(i32 0)
+  ret i8* %r
+}
+
+; LLVM represents __builtin_return_address as call to this function in IR.
+declare i8* @llvm.returnaddress(i32 immarg)

llvm/trunk/test/CodeGen/WebAssembly/return-address-unknown.ll

+; RUN: not llc < %s -asm-verbose=false 2>&1 | FileCheck %s
+
+target datalayout = "e-m:e-p:32:32-i64:64-n32:64-S128"
+target triple = "wasm32-unknown-unknown"
+
+; This tests the implementation of __builtin_return_address on the unknown OS.
+; Since this is not implemented, it should fail.
+
+; CHECK: Non-Emscripten WebAssembly hasn't implemented __builtin_return_address
+define i8* @test_returnaddress() {
+  %r = call i8* @llvm.returnaddress(i32 0)
+  ret i8* %r
+}
+
+; LLVM represents __builtin_return_address as call to this function in IR.
+declare i8* @llvm.returnaddress(i32 immarg)