diff --git a/llvm/lib/Target/AVR/AVRISelDAGToDAG.cpp b/llvm/lib/Target/AVR/AVRISelDAGToDAG.cpp
--- a/llvm/lib/Target/AVR/AVRISelDAGToDAG.cpp
+++ b/llvm/lib/Target/AVR/AVRISelDAGToDAG.cpp
@@ -467,8 +467,9 @@
   Ops.push_back(Chain);
   Ops.push_back(Chain.getValue(1));
 
-  SDNode *ResNode =
-      CurDAG->getMachineNode(AVR::ICALL, DL, MVT::Other, MVT::Glue, Ops);
+  SDNode *ResNode = CurDAG->getMachineNode(
+      Subtarget->hasEIJMPCALL() ? AVR::EICALL : AVR::ICALL, DL, MVT::Other,
+      MVT::Glue, Ops);
 
   ReplaceUses(SDValue(N, 0), SDValue(ResNode, 0));
   ReplaceUses(SDValue(N, 1), SDValue(ResNode, 1));
diff --git a/llvm/lib/Target/AVR/AVRMCInstLower.h b/llvm/lib/Target/AVR/AVRMCInstLower.h
--- a/llvm/lib/Target/AVR/AVRMCInstLower.h
+++ b/llvm/lib/Target/AVR/AVRMCInstLower.h
@@ -9,6 +9,7 @@
 #ifndef LLVM_AVR_MCINST_LOWER_H
 #define LLVM_AVR_MCINST_LOWER_H
 
+#include "AVRSubtarget.h"
 #include "llvm/Support/Compiler.h"
 
 namespace llvm {
@@ -29,7 +30,8 @@
 
   /// Lowers a `MachineInstr` into a `MCInst`.
   void lowerInstruction(const MachineInstr &MI, MCInst &OutMI) const;
-  MCOperand lowerSymbolOperand(const MachineOperand &MO, MCSymbol *Sym) const;
+  MCOperand lowerSymbolOperand(const MachineOperand &MO, MCSymbol *Sym,
+                               const AVRSubtarget &Subtarget) const;
 
 private:
   MCContext &Ctx;
diff --git a/llvm/lib/Target/AVR/AVRMCInstLower.cpp b/llvm/lib/Target/AVR/AVRMCInstLower.cpp
--- a/llvm/lib/Target/AVR/AVRMCInstLower.cpp
+++ b/llvm/lib/Target/AVR/AVRMCInstLower.cpp
@@ -12,7 +12,6 @@
 //===----------------------------------------------------------------------===//
 
 #include "AVRMCInstLower.h"
-
 #include "AVRInstrInfo.h"
 #include "MCTargetDesc/AVRMCExpr.h"
 
@@ -23,8 +22,9 @@
 
 namespace llvm {
 
-MCOperand AVRMCInstLower::lowerSymbolOperand(const MachineOperand &MO,
-                                             MCSymbol *Sym) const {
+MCOperand
+AVRMCInstLower::lowerSymbolOperand(const MachineOperand &MO, MCSymbol *Sym,
+                                   const AVRSubtarget &Subtarget) const {
   unsigned char TF = MO.getTargetFlags();
   const MCExpr *Expr = MCSymbolRefExpr::create(Sym, Ctx);
 
@@ -42,15 +42,19 @@
 
   if (TF & AVRII::MO_LO) {
     if (IsFunction) {
-      // N.B. Should we use _GS fixups here to cope with >128k progmem?
-      Expr = AVRMCExpr::create(AVRMCExpr::VK_AVR_PM_LO8, Expr, IsNegated, Ctx);
+      Expr =
+          AVRMCExpr::create(Subtarget.hasEIJMPCALL() ? AVRMCExpr::VK_AVR_LO8_GS
+                                                     : AVRMCExpr::VK_AVR_PM_LO8,
+                            Expr, IsNegated, Ctx);
     } else {
       Expr = AVRMCExpr::create(AVRMCExpr::VK_AVR_LO8, Expr, IsNegated, Ctx);
     }
   } else if (TF & AVRII::MO_HI) {
     if (IsFunction) {
-      // N.B. Should we use _GS fixups here to cope with >128k progmem?
-      Expr = AVRMCExpr::create(AVRMCExpr::VK_AVR_PM_HI8, Expr, IsNegated, Ctx);
+      Expr =
+          AVRMCExpr::create(Subtarget.hasEIJMPCALL() ? AVRMCExpr::VK_AVR_HI8_GS
+                                                     : AVRMCExpr::VK_AVR_PM_HI8,
+                            Expr, IsNegated, Ctx);
     } else {
       Expr = AVRMCExpr::create(AVRMCExpr::VK_AVR_HI8, Expr, IsNegated, Ctx);
     }
@@ -63,6 +67,7 @@
 
 void AVRMCInstLower::lowerInstruction(const MachineInstr &MI,
                                       MCInst &OutMI) const {
+  auto &Subtarget = MI.getParent()->getParent()->getSubtarget<AVRSubtarget>();
   OutMI.setOpcode(MI.getOpcode());
 
   for (MachineOperand const &MO : MI.operands()) {
@@ -82,11 +87,12 @@
       MCOp = MCOperand::createImm(MO.getImm());
       break;
     case MachineOperand::MO_GlobalAddress:
-      MCOp = lowerSymbolOperand(MO, Printer.getSymbol(MO.getGlobal()));
+      MCOp =
+          lowerSymbolOperand(MO, Printer.getSymbol(MO.getGlobal()), Subtarget);
       break;
     case MachineOperand::MO_ExternalSymbol:
       MCOp = lowerSymbolOperand(
-          MO, Printer.GetExternalSymbolSymbol(MO.getSymbolName()));
+          MO, Printer.GetExternalSymbolSymbol(MO.getSymbolName()), Subtarget);
       break;
     case MachineOperand::MO_MachineBasicBlock:
       MCOp = MCOperand::createExpr(
@@ -96,13 +102,15 @@
       continue;
     case MachineOperand::MO_BlockAddress:
       MCOp = lowerSymbolOperand(
-          MO, Printer.GetBlockAddressSymbol(MO.getBlockAddress()));
+          MO, Printer.GetBlockAddressSymbol(MO.getBlockAddress()), Subtarget);
       break;
     case MachineOperand::MO_JumpTableIndex:
-      MCOp = lowerSymbolOperand(MO, Printer.GetJTISymbol(MO.getIndex()));
+      MCOp = lowerSymbolOperand(MO, Printer.GetJTISymbol(MO.getIndex()),
+                                Subtarget);
       break;
     case MachineOperand::MO_ConstantPoolIndex:
-      MCOp = lowerSymbolOperand(MO, Printer.GetCPISymbol(MO.getIndex()));
+      MCOp = lowerSymbolOperand(MO, Printer.GetCPISymbol(MO.getIndex()),
+                                Subtarget);
       break;
     }
 
diff --git a/llvm/test/CodeGen/AVR/issue-58856-eicall.ll b/llvm/test/CodeGen/AVR/issue-58856-eicall.ll
new file mode 100644
--- /dev/null
+++ b/llvm/test/CodeGen/AVR/issue-58856-eicall.ll
@@ -0,0 +1,30 @@
+; NOTE: Assertions have been autogenerated by utils/update_llc_test_checks.py
+; RUN: llc < %s -mtriple=avr -mattr=-eijmpcall | FileCheck %s --check-prefix=ICALL
+; RUN: llc < %s -mtriple=avr -mattr=+eijmpcall | FileCheck %s --check-prefix=EICALL
+
+; This test verifies the bug https://github.com/llvm/llvm-project/issues/58856
+
+declare dso_local i16 @func()
+
+define i16 @foo() {
+; ICALL-LABEL: foo:
+; ICALL:       ; %bb.0:
+; ICALL-NEXT:    ldi r30, pm_lo8(func)
+; ICALL-NEXT:    ldi r31, pm_hi8(func)
+; ICALL-NEXT:    ;APP
+; ICALL-NEXT:    ;NO_APP
+; ICALL-NEXT:    icall
+; ICALL-NEXT:    ret
+;
+; EICALL-LABEL: foo:
+; EICALL:       ; %bb.0:
+; EICALL-NEXT:    ldi r30, lo8_gs(func)
+; EICALL-NEXT:    ldi r31, hi8_gs(func)
+; EICALL-NEXT:    ;APP
+; EICALL-NEXT:    ;NO_APP
+; EICALL-NEXT:    eicall
+; EICALL-NEXT:    ret
+  %1 = tail call addrspace(0) ptr addrspace(1) asm "", "=r,0"(ptr addrspace(1) @func)
+  %2 = tail call i16 %1()
+  ret i16 %2
+}