diff --git a/bolt/lib/Passes/RetpolineInsertion.cpp b/bolt/lib/Passes/RetpolineInsertion.cpp
--- a/bolt/lib/Passes/RetpolineInsertion.cpp
+++ b/bolt/lib/Passes/RetpolineInsertion.cpp
@@ -22,6 +22,7 @@
 //===----------------------------------------------------------------------===//
 
 #include "bolt/Passes/RetpolineInsertion.h"
+#include "llvm/MC/MCInstPrinter.h"
 #include "llvm/Support/raw_ostream.h"
 
 #define DEBUG_TYPE "bolt-retpoline"
@@ -173,39 +174,45 @@
 std::string createRetpolineFunctionTag(BinaryContext &BC,
                                        const IndirectBranchInfo &BrInfo,
                                        bool R11Available) {
-  if (BrInfo.isReg())
-    return "__retpoline_r" + to_string(BrInfo.BranchReg) + "_";
+  std::string Tag;
+  llvm::raw_string_ostream TagOS(Tag);
+  TagOS << "__retpoline_";
+
+  if (BrInfo.isReg()) {
+    BC.InstPrinter->printRegName(TagOS, BrInfo.BranchReg);
+    TagOS << "_";
+    TagOS.flush();
+    return Tag;
+  }
 
   // Memory Branch
   if (R11Available)
     return "__retpoline_r11";
 
-  std::string Tag = "__retpoline_mem_";
-
   const IndirectBranchInfo::MemOpInfo &MemRef = BrInfo.Memory;
 
-  std::string DispExprStr;
-  if (MemRef.DispExpr) {
-    llvm::raw_string_ostream Ostream(DispExprStr);
-    MemRef.DispExpr->print(Ostream, BC.AsmInfo.get());
-    Ostream.flush();
-  }
+  TagOS << "mem_";
 
-  Tag += MemRef.BaseRegNum != BC.MIB->getNoRegister()
-             ? "r" + to_string(MemRef.BaseRegNum)
-             : "";
+  if (MemRef.BaseRegNum != BC.MIB->getNoRegister())
+    BC.InstPrinter->printRegName(TagOS, MemRef.BaseRegNum);
 
-  Tag += MemRef.DispExpr ? "+" + DispExprStr : "+" + to_string(MemRef.DispImm);
+  TagOS << "+";
+  if (MemRef.DispExpr)
+    MemRef.DispExpr->print(TagOS, BC.AsmInfo.get());
+  else
+    TagOS << MemRef.DispImm;
 
-  Tag += MemRef.IndexRegNum != BC.MIB->getNoRegister()
-             ? "+" + to_string(MemRef.ScaleImm) + "*" +
-                   to_string(MemRef.IndexRegNum)
-             : "";
+  if (MemRef.IndexRegNum != BC.MIB->getNoRegister()) {
+    TagOS << "+" << MemRef.ScaleImm << "*";
+    BC.InstPrinter->printRegName(TagOS, MemRef.IndexRegNum);
+  }
 
-  Tag += MemRef.SegRegNum != BC.MIB->getNoRegister()
-             ? "_seg_" + to_string(MemRef.SegRegNum)
-             : "";
+  if (MemRef.SegRegNum != BC.MIB->getNoRegister()) {
+    TagOS << "_seg_";
+    BC.InstPrinter->printRegName(TagOS, MemRef.SegRegNum);
+  }
 
+  TagOS.flush();
   return Tag;
 }
 
diff --git a/bolt/test/CMakeLists.txt b/bolt/test/CMakeLists.txt
--- a/bolt/test/CMakeLists.txt
+++ b/bolt/test/CMakeLists.txt
@@ -47,6 +47,7 @@
   llvm-objdump
   llvm-readelf
   llvm-readobj
+  llvm-strings
   llvm-strip
   llvm-objcopy
   merge-fdata
diff --git a/bolt/test/lit.cfg.py b/bolt/test/lit.cfg.py
--- a/bolt/test/lit.cfg.py
+++ b/bolt/test/lit.cfg.py
@@ -87,6 +87,7 @@
     ToolSubst('llvm-nm', unresolved='fatal'),
     ToolSubst('llvm-objdump', unresolved='fatal'),
     ToolSubst('llvm-objcopy', unresolved='fatal'),
+    ToolSubst('llvm-strings', unresolved='fatal'),
     ToolSubst('llvm-strip', unresolved='fatal'),
     ToolSubst('llvm-readelf', unresolved='fatal'),
     ToolSubst('link_fdata', command=sys.executable, unresolved='fatal', extra_args=[link_fdata_cmd]),
diff --git a/bolt/test/runtime/X86/retpoline-synthetic.test b/bolt/test/runtime/X86/retpoline-synthetic.test
--- a/bolt/test/runtime/X86/retpoline-synthetic.test
+++ b/bolt/test/runtime/X86/retpoline-synthetic.test
@@ -20,5 +20,12 @@
 RUN: llvm-objdump -d -j ".text" %t | FileCheck %s -check-prefix=CHECK-JUMP
 CHECK-JUMP-NOT: jmpq   *
 
+# Check generated retpoline stub names
+RUN: llvm-strings %t | FileCheck %s -check-prefix=CHECK-STRINGS
+CHECK-STRINGS-DAG: __retpoline_%rax_
+CHECK-STRINGS-DAG: __retpoline_mem_%rip+DATAat0x[[#]]
+CHECK-STRINGS-DAG: __retpoline_mem_%rax+0
+CHECK-STRINGS-DAG: __retpoline_mem_%r[[#]]+0+8*%rbx
+
 RUN: %t 1000 3 | FileCheck %s
 CHECK: 30000000