diff --git a/src/IceCfg.cpp b/src/IceCfg.cpp
index d8e3b24..0bd6b36 100644
--- a/src/IceCfg.cpp
+++ b/src/IceCfg.cpp
@@ -44,9 +44,9 @@
   Ctx->getStrDump() << "ICE translation error: " << ErrorMessage << "\n";
 }
 
-CfgNode *Cfg::makeNode(const IceString &Name) {
+CfgNode *Cfg::makeNode() {
   SizeT LabelIndex = Nodes.size();
-  CfgNode *Node = CfgNode::create(this, LabelIndex, Name);
+  CfgNode *Node = CfgNode::create(this, LabelIndex);
   Nodes.push_back(Node);
   return Node;
 }
diff --git a/src/IceCfg.h b/src/IceCfg.h
index 970b838..c313a89 100644
--- a/src/IceCfg.h
+++ b/src/IceCfg.h
@@ -59,9 +59,17 @@
   void setEntryNode(CfgNode *EntryNode) { Entry = EntryNode; }
   CfgNode *getEntryNode() const { return Entry; }
   // Create a node and append it to the end of the linearized list.
-  CfgNode *makeNode(const IceString &Name = "");
+  CfgNode *makeNode();
   SizeT getNumNodes() const { return Nodes.size(); }
   const NodeList &getNodes() const { return Nodes; }
+  // Adds a name to the list and returns its index, suitable for the
+  // argument to getNodeName().  No checking for duplicates is done.
+  int32_t addNodeName(const IceString &Name) {
+    int32_t Index = NodeNames.size();
+    NodeNames.push_back(Name);
+    return Index;
+  }
+  const IceString &getNodeName(int32_t Index) const { return NodeNames[Index]; }
 
   // Manage instruction numbering.
   InstNumberT newInstNumber() { return NextInstNumber++; }
@@ -175,6 +183,7 @@
   IceString ErrorMessage;
   CfgNode *Entry; // entry basic block
   NodeList Nodes; // linearized node list; Entry should be first
+  std::vector<IceString> NodeNames;
   InstNumberT NextInstNumber;
   VarList Variables;
   VarList Args; // subset of Variables, in argument order
diff --git a/src/IceCfgNode.cpp b/src/IceCfgNode.cpp
index 59035f8..920f373 100644
--- a/src/IceCfgNode.cpp
+++ b/src/IceCfgNode.cpp
@@ -22,15 +22,15 @@
 
 namespace Ice {
 
-CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber, IceString Name)
-    : Func(Func), Number(LabelNumber), Name(Name), HasReturn(false),
+CfgNode::CfgNode(Cfg *Func, SizeT LabelNumber)
+    : Func(Func), Number(LabelNumber), NameIndex(-1), HasReturn(false),
       NeedsPlacement(false), InstCountEstimate(0) {}
 
 // Returns the name the node was created with.  If no name was given,
 // it synthesizes a (hopefully) unique name.
 IceString CfgNode::getName() const {
-  if (!Name.empty())
-    return Name;
+  if (NameIndex >= 0)
+    return Func->getNodeName(NameIndex);
   return "__" + std::to_string(getIndex());
 }
 
@@ -219,8 +219,9 @@
 // out-edge list, this node's in-edge list, and the Phi instruction's
 // operand list.
 CfgNode *CfgNode::splitIncomingEdge(CfgNode *Pred, SizeT EdgeIndex) {
-  CfgNode *NewNode =
-      Func->makeNode("split_" + Pred->getName() + "_" + getName() + "_" +
+  CfgNode *NewNode = Func->makeNode();
+  if (ALLOW_DUMP)
+    NewNode->setName("split_" + Pred->getName() + "_" + getName() + "_" +
                      std::to_string(EdgeIndex));
   // The new node is added to the end of the node list, and will later
   // need to be sorted into a reasonable topological order.
diff --git a/src/IceCfgNode.h b/src/IceCfgNode.h
index 279b07f..d60b0f0 100644
--- a/src/IceCfgNode.h
+++ b/src/IceCfgNode.h
@@ -26,17 +26,18 @@
   CfgNode &operator=(const CfgNode &) = delete;
 
 public:
-  static CfgNode *create(Cfg *Func, SizeT LabelIndex, IceString Name = "") {
-    return new (Func->allocate<CfgNode>()) CfgNode(Func, LabelIndex, Name);
+  static CfgNode *create(Cfg *Func, SizeT LabelIndex) {
+    return new (Func->allocate<CfgNode>()) CfgNode(Func, LabelIndex);
   }
 
   // Access the label number and name for this node.
   SizeT getIndex() const { return Number; }
   IceString getName() const;
-  void setName(IceString &NewName) {
+  void setName(const IceString &NewName) {
     // Make sure that the name can only be set once.
-    assert(Name.empty());
-    Name = NewName;
+    assert(NameIndex < 0);
+    if (!NewName.empty())
+      NameIndex = Func->addNodeName(NewName);
   }
   IceString getAsmName() const {
     return ".L" + Func->getFunctionName() + "$" + getName();
@@ -87,10 +88,10 @@
   void dump(Cfg *Func) const;
 
 private:
-  CfgNode(Cfg *Func, SizeT LabelIndex, IceString Name);
+  CfgNode(Cfg *Func, SizeT LabelIndex);
   Cfg *const Func;
   const SizeT Number; // label index
-  IceString Name;     // for dumping only
+  int32_t NameIndex;  // index into Cfg::NodeNames table
   bool HasReturn;     // does this block need an epilog?
   bool NeedsPlacement;
   InstNumberT InstCountEstimate; // rough instruction count estimate
diff --git a/src/IceConverter.cpp b/src/IceConverter.cpp
index e06e290..a8148f9 100644
--- a/src/IceConverter.cpp
+++ b/src/IceConverter.cpp
@@ -156,7 +156,9 @@
 
   Ice::CfgNode *mapBasicBlockToNode(const BasicBlock *BB) {
     if (NodeMap.find(BB) == NodeMap.end()) {
-      NodeMap[BB] = Func->makeNode(BB->getName());
+      NodeMap[BB] = Func->makeNode();
+      if (ALLOW_DUMP)
+        NodeMap[BB]->setName(BB->getName());
     }
     return NodeMap[BB];
   }
diff --git a/src/PNaClTranslator.cpp b/src/PNaClTranslator.cpp
index 124ed89..8f1f99d 100644
--- a/src/PNaClTranslator.cpp
+++ b/src/PNaClTranslator.cpp
@@ -2678,7 +2678,8 @@
     return;
   }
   std::string Nm(Name.data(), Name.size());
-  getFunctionParser()->getFunc()->getNodes()[Index]->setName(Nm);
+  if (ALLOW_DUMP)
+    getFunctionParser()->getFunc()->getNodes()[Index]->setName(Nm);
 }
 
 bool FunctionParser::ParseBlock(unsigned BlockID) {