C++ Template Instantiation Issues

Introduction

If you don't know what C++ template instantiation is, then this page is not for you. If you are experiencing linker diagnostics like this one ...

 undefined                                                          first referenced
  symbol                                                                in file
 ---------                                                          ----------------
 Stack<T1, N2>::Stack<char, (int)100>() [with T1=char, N2=(int)100] mylib.lib<lib1.obj>
 T1 Stack<T1, N2>::pop() [with T1=char, N2=(int)100]                mylib.lib<lib1.obj>
 void Stack<T1, N2>::push(T1) [with T1=char, N2=(int)100]           mylib.lib<lib1.obj>

error: unresolved symbols remain
error: errors encountered during linking; "test.out" not built

>> Compilation failure

then this page is for you.

Typical Template Source Code Organization

TI C++ compilers do not support the export keyword. This means an appropriate template definition must be visible at the point of instantiation, i.e. the spot where the actual template-related class object or function is defined. In practical terms, this means the entire template definition must be placed in header file that is included by all the files that refer to the template. All the examples in this article are organized this way. Organizing template definitions in this manner is not a violation of the one-definition rule. See The C++ Programming Language, 3rd Ed., the last part of section 9.2.3.

Compiler Version

All the examples in this article were built with C6000 Code Generation Tools Version 6.1.0.

Basic Example

Let's start by explaining how a simple example works, then make changes to it that demonstrate the issues.

<syntaxhighlight lang=cpp> // stack.hpp template<typename T, int size> class Stack { private:

  T stack_[size];
  int top_;

public:

  Stack();
  void push(T);
  T pop();

};

template<typename T, int size> Stack<T, size>::Stack() {

  top_ = 0;

}

template<typename T, int size> void Stack<T, size>::push(T item) {

  if (top_ == size)
     { /* overflow */ }
  stack_[top_++] = item;

}

template<typename T, int size> T Stack<T, size>::pop() {

  if (top_ == 0)
     { /* underflow */ }
  return stack_[--top_];

} </syntaxhighlight>

<syntaxhighlight lang=cpp> // main.cpp

1. include "stack.hpp"

Stack<int, 100> main_int_stack; int int_val;

void lib_fxn();

int main() {

  main_int_stack.push(100);
  int_val = main_int_stack.pop();
  lib_fxn();
  return 0;

} </syntaxhighlight>

<syntaxhighlight lang=cpp> // lib1.cpp

1. include "stack.hpp"

Stack<char, 100> lib_char_stack; char char_val;

void lib_fxn() {

  lib_char_stack.push('c');
  char_val = lib_char_stack.pop();

} </syntaxhighlight>

Do not adopt that stack template code in your system. Use the <stack> implementation that comes with the compiler RTS.

Perform a simple build of these two .cpp files.

% del *.obj
% cl6x -as main.cpp lib1.cpp
[main.cpp]
[lib1.cpp]

The option -as is used so that static symbols (which show up later) can be seen. This technique is described in the article Find Static Functions and Variables. Removing the object files is explained later.

So which, if any, of those stack template functions were instantiated? Here is how to tell:

% nm6x main.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
00000060 T ___sti___8_main_cpp_916bf417
00000000 T _main

The answer is "none" for main.cpp. What about lib1.cpp?

% nm6x lib1.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
0000004c T ___sti___8_lib1_cpp_1155a7bd
00000000 T lib_fxn()

Also, "none".

What does that command line do? The nm6x name utility dumps out all the symbols defined in the object file. The dem6x utility demangles the C++ function names. The find command is a DOS utility similar to Unix grep. Used with /i " t ", it filters through lines with an isolated " t " or " T ". In nm6x output, symbols marked with T are global functions, and symbols marked with t are static functions. (The T stands for ".text", the section in which code symbols are normally defined.) When find is used with /v "$", it filters out the lines about the local branch destinations. Compiler generated branch destination labels always have "$" in the name. The name utility is documented in the Assembly Language Tools User's Guide, and the demangler is documented in the Compiler User's Guide. Ignore the ".text" symbol. That marks the start of the code section. Also ignore the ___sti symbols. Explaining those is beyond the scope of this article, and not related to templates.

Now, link it.

% cl6x -z -c main.obj lib1.obj -z -o test.out
<Linking>

When linking code that involves templates, you must invoke the linker through the shell utility cl6x. Invoking the linker directly doesn't work.

Now, which stack template functions are instantiated?

% nm6x main.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
00000060 T Stack<T1, N2>::Stack<int, (int)100>() [with T1=int, N2=(int)100]
0000015c T ___sti___8_main_cpp_916bf417
00000000 T _main
00000124 T T1 Stack<T1, N2>::pop() [with T1=int, N2=(int)100]
000000e8 T void Stack<T1, N2>::push(T1) [with T1=int, N2=(int)100]

% nm6x lib1.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
0000004c T Stack<T1, N2>::Stack<char, (int)100>() [with T1=char, N2=(int)100]
00000154 T ___sti___8_lib1_cpp_1155a7bd
00000000 T lib_fxn()
00000120 T T1 Stack<T1, N2>::pop() [with T1=char, N2=(int)100]
000000e8 T void Stack<T1, N2>::push(T1) [with T1=char, N2=(int)100]

Hey! What happened?

Late Template Instantiation

When the linker discovers an entity (data object or function) needs to be instantiated, it invokes the compiler to re-compile the appropriate source file(s), using extra undocumented options that indicate which template entities to instantiate with what types. In this case, main.cpp is recompiled to instantiate the Stack functions with type "int", and lib1.cpp is recompiled to instantiate the Stack functions with type "char". This "late template instantiation" method avoids two problems. Templates are not instantiated until it is known they are needed, thus saving compile time. And, it avoids the problem of duplicate entities that would arise should the same template be instantiated with the same type in multiple files.

This linker driven re-compile is not all of the behind the scenes action. Recall the directions in the first build to delete all the .obj files. When the compiler is first compiling a file and comes across a potential template instantiation, it looks to see if the object file already exists. It if does, it opens it to determine which templates actually were instantiated the last time the file was built, and during the current compile, instantiates those templates again. In most cases in practice, this scheme reduces the linker driven re-compiles down to almost zero. If you rebuild those .cpp files again, without deleting the post-link .obj files, then those template function will be instantiated on the first compile, and thus the linker doesn't need to re-compile anything.

Normally, you don't need to worry about any of this. It just works. Unfortunately, there are a few issues.

Cannot Instantiate Templates for Library Members

To set this issue up, rebuild the source files down to the initial object file state where nothing is instantiated.

% del *.obj
% cl6x -as main.cpp lib1.cpp
[main.cpp]
[lib1.cpp]
% nm6x main.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
00000060 T ___sti___8_main_cpp_916bf417
00000000 T _main
% nm6x lib1.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
0000004c T ___sti___8_lib1_cpp_1155a7bd
00000000 T lib_fxn()

Now, put lib1.obj in a library, then link.

% ar6x -r mylib.lib lib1.obj
  ==>  new archive 'mylib.lib'
  ==>  building archive 'mylib.lib'
% cl6x -z -c main.obj -o test.out mylib.lib
<Linking>

 undefined                                                          first referenced
  symbol                                                                in file
 ---------                                                          ----------------
 Stack<T1, N2>::Stack<char, (int)100>() [with T1=char, N2=(int)100] mylib.lib<lib1.obj>
 T1 Stack<T1, N2>::pop() [with T1=char, N2=(int)100]                mylib.lib<lib1.obj>
 void Stack<T1, N2>::push(T1) [with T1=char, N2=(int)100]           mylib.lib<lib1.obj>

error: unresolved symbols remain
error: errors encountered during linking; "test.out" not built

>> Compilation failure

What happened? The linker needs to re-compile lib1.cpp to instantiate the Stack template functions with type "char". But lib1.obj is not an ordinary object file, but a member of a library. And there is no general mechanism by which the linker can find the source code of a library member. In many cases of libraries purchased from vendors, the library source code is not available. Thus, the link fails.

First Workaround: Inline the Function Definitions

One workaround is to write the stack template functions as inline.

<syntaxhighlight lang="cpp"> // stack.hpp - inline version template<typename T, int size> class Stack { private:

  T stack_[size];
  int top_;

public:

  Stack()
  {
     top_ = 0;
  }

  void push(T item)
  {
     if (top_ == size)
        { /* overflow */ }
     stack_[top_++] = item;
  }

  T pop()
  {
     if (top_ == 0)
        { /* underflow */ }
     return stack_[--top_];
  }

}; </syntaxhighlight>

This second Stack example is much more typical of how template classes are written in practice. The initial stack.hpp example, while useful here, is less typical in form.

So, what does this do?

% del *.obj
% cl6x -as lib1.cpp
% nm6x lib1.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
00000000 t Stack<T1, N2>::Stack<char, (int)100>() [with T1=char, N2=(int)100]
00000134 T ___sti___8_lib1_cpp_1155a7bd
000000f4 T lib_fxn()
000000c0 t T1 Stack<T1, N2>::pop() [with T1=char, N2=(int)100]
00000088 t void Stack<T1, N2>::push(T1) [with T1=char, N2=(int)100]

Notice two things that are different about this pre-link build of lib1.obj. One, the Stack functions have been instantiated. Two, those instantiations are static. Notice the "t" next to the Stack function names. Recall the "t" means static. Compare against the post-link build of lib1.obj above, where the same functions are marked with "T" for global.

Why are the Stack functions static? When the first phase of compilation, called the parser, sees an inline function in a template, it instantiates any entities that use the template. This is done to allow later phases of compilation, i.e. the optimizer, to see the inline function and thus actually perform the inlining. In this particular case, the optimizer phase is not run, the inline functions are not actually inlined, and the only correct thing left to do is create a static copy of the function.

For this example, if optimization is used, the functions actually are inlined. Here is one way to see that.

% del *.obj
% cl6x -as -o lib1.cpp
% nm6x lib1.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
00000048 T ___sti___8_lib1_cpp_1155a7bd
00000000 T lib_fxn()
% ar6x -r mylib.lib lib1.obj
  ==>  new archive 'mylib.lib'
  ==>  building archive 'mylib.lib'
% cl6x -as -o main.cpp
% nm6x main.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
0000006c T ___sti___8_main_cpp_916bf417
00000000 T _main
% cl6x -z -c main.obj -o test.out mylib.lib
<Linking>
% nm6x main.obj | dem6x -q | find /i " t " | find /v "$"
00000000 t .text
0000006c T ___sti___8_main_cpp_916bf417
00000000 T _main

The library and main.obj are built as before, except with -o to enable optimization. Then it links successfully. Inspection of the object files for template instantiation is carried out at various points. As can be seen by their absence, no template functions are ever instantiated.

Well, that settles everything for this simple example. But some questions remain:

• What if inlining every member function is not practical?
• What happens when a function fails to inline?
• Can other things go wrong?

To address these issues we need a more in-depth example.

Recast The Example

<syntaxhighlight lang=cpp> // main2.cpp

void lib_fxn(); int main() { lib_fxn(); return 0; } </syntaxhighlight>

<syntaxhighlight lang=cpp> // lib2.cpp

1. include <string>

std::string l1, l2;

void lib_fxn() {

  l1 = "lib string";
  l1 = l2;

} </syntaxhighlight>

The main code merely calls the library function. The library code includes the standard header <string> and does some standard things with strings. Does this build?

% del *.obj
% cl6x -as lib2.cpp
% ar6x -r mylib.lib lib2.obj
  ==>  new archive 'mylib.lib'
  ==>  building archive 'mylib.lib'
% cl6x -as main2.cpp
% cl6x -z -c main2.obj -o test.out mylib.lib
<Linking>

 undefined                                                                                              first referenced
  symbol                                                                                                    in file
 ---------                                                                                              ----------------
 std::basic_string<T1, T2, T3>::npos [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>] mylib.lib<lib2.obj>

error: unresolved symbols remain
error: errors encountered during linking; "test.out" not built

>> Compilation failure

Surprisingly, no. What just happened?

Well, for starters, if you are going to use <string>, you need to get used to seeing "std::basic_string<T1, T2, T3>::something [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>]" in your diagnostics. All that stuff is the fully expanded representation of the string type. Think of it as "std::string::something".

So, what is "npos"? So far, we only know it is a undefined symbol. An undefined symbol for what? There is no way to figure it out from what we have here. Build a simple, self-contained, example of code that uses <string>. That's a nice exercise for the reader. Then run nm6x on the final .out file:

% nm6x test.out | dem6x -q | find "npos"
00000008 B std::basic_string<T1, T2, T3>::npos [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>]

Notice this symbol is marked with "B". This means it is a global variable from an uninitialized data section such as .bss. Recall that function symbols are marked with "T" or "t". So, this is a data symbol, not a function symbol. It is also a member of the string class. Thus, this has to be static data member. (Never heard of that? See The C++ Programming Language, 3rd Ed., section 10.2.4.)

So, this problem is similar to the one in the simpler example in that something needs to be instantiated by rebuilding lib2.obj, but because lib2.obj comes from a library, the linker cannot re-compile it. In the simpler example, an instantiation of the Stack<char> member functions is needed. In this example, it is more subtle. The instantiation of the basic_string<char> member functions comes on the first compile due to inlining. But the instantiation of the static data member npos is also needed, and inlining doesn't provide it.

Second Workaround: Include Template Definition Headers in User Code

One workaround is to include <string> in the user code, in this case, in main2.cpp.

<syntaxhighlight lang=cpp> // main2.cpp

1. include <string> // addition

void lib_fxn(); int main() { lib_fxn(); return 0; } </syntaxhighlight>

Here is the build, including two looks at what is being instantiated in main2.obj.

% del *.obj *.lib
% cl6x -as lib2.cpp
% ar6x -r mylib.lib lib2.obj
  ==>  new archive 'mylib.lib'
  ==>  building archive 'mylib.lib'
% cl6x -as main2.cpp
% nm6x main2.obj | dem6x -q | perl -ne "print if (m/ [tb] [^\$]*$/i);"
00000000 b .bss
00000000 t .text
00000000 T _main
% cl6x -z -c main2.obj -o test.out mylib.lib
<Linking>
% nm6x main2.obj | dem6x -q | perl -ne "print if (m/ [tb] [^\$]*$/i);"
00000000 b .bss
00000000 t .text
00000000 T _main
00000000 B std::basic_string<T1, T2, T3>::npos [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>]

It is interesting that including <string> in a file that does not itself use the string type fixes the problem. What is going on? The first time main2.cpp is compiled, nothing gets instantiated. But, because main2.cpp includes <string> and other non-template classes declared in <string> use the string template class, the compiler builds up the information that tells the linker, in effect, main2.cpp could instantiate the string template on a rebuild. And, indeed, the linker does exactly that, rebuilding main2.cpp to instantiate npos.

Why does the nm6x command line now use Perl instead of find? The find command, which can only search for fixed strings and not regular expressions, cannot perform the task needed. That Perl command passes through all the symbols which are marked with t or b, regardless of case, and the symbol name does not contain a $.

Third Workaround: Use a Template in a Non-Template Class Declaration

Sometimes the second workaround fails. This section explains why, and shows one way to address it. To focus on the issues at hand requires another example.

<syntaxhighlight lang="cpp"> // simple.hpp

template<typename T> class Simple { public:

  static T s_mem_;                  // declare static data member

};

template<typename T> T Simple<T>::s_mem_; // define it </syntaxhighlight>

<syntaxhighlight lang="cpp"> // main3.cpp

void lib_fxn(); int main() { lib_fxn(); return 0; } </syntaxhighlight>

<syntaxhighlight lang="cpp"> // lib3.cpp

1. include "simple.hpp"

Simple<int> int_simple; // need instantiation here

void lib_fxn() {

  Simple<int>::s_mem_ = 10;    // use static member

} </syntaxhighlight>

This example shows a simple template class that only contains a static data member. Recall that npos is a static data member of the string template class. Building this example ...

% del *.obj
% cl6x -as lib3.cpp
% ar6x -r mylib.lib lib3.obj
  ==>  new archive 'mylib.lib'
  ==>  building archive 'mylib.lib'
% cl6x -as main3.cpp
% cl6x -z -c main3.obj -o test.out mylib.lib
<Linking>

 undefined                        first referenced
  symbol                              in file
 ---------                        ----------------
 Simple<T1>::s_mem_ [with T1=int] mylib.lib<lib3.obj>

error: unresolved symbols remain
error: errors encountered during linking; "test.out" not built

>> Compilation failure

... fails as expected. So, using the second workaround will fix it, right? Let's see. Add the header to main3.cpp and build again ...

<syntaxhighlight lang="cpp"> // main3.cpp

1. include "simple.hpp" // addition

void lib_fxn(); int main() { lib_fxn(); return 0; } </syntaxhighlight>

% del *.obj
% cl6x -as lib3.cpp
% ar6x -r mylib.lib lib3.obj
  ==>  new archive 'mylib.lib'
  ==>  building archive 'mylib.lib'
% cl6x -as main3.cpp
% cl6x -z -c main3.obj -o test.out mylib.lib
<Linking>

 undefined                        first referenced
  symbol                              in file
 ---------                        ----------------
 Simple<T1>::s_mem_ [with T1=int] mylib.lib<lib3.obj>

error: unresolved symbols remain
error: errors encountered during linking; "test.out" not built

>> Compilation failure

No luck. What's going on? Merely defining a template, as is done in simple.hpp, does not cause the compiler to record that it can, on a later re-compile, instantiate that template. It turns out using the template, with non-template types, causes the compiler to record that it can instantiate the template later. One of the easiest things to do is declare an instance of the template class object in a non-template class that is never used.

<syntaxhighlight lang="cpp"> // main3.cpp

1. include "simple.hpp" // addition

class never_used { // non-template class that is never used

  Simple<int> m_;

};

void lib_fxn(); int main() { lib_fxn(); return 0; } </syntaxhighlight>

% del *.obj
% cl6x -as lib3.cpp
% ar6x -r mylib.lib lib3.obj
  ==>  new archive 'mylib.lib'
  ==>  building archive 'mylib.lib'
% cl6x -as main3.cpp
% cl6x -z -c main3.obj -o test.out mylib.lib
<Linking>

Success! How do you know what to declare in the never used class? Look again at the error message issued by the linker. It tells you exactly which template class and type (int) to use.

The string example works because, within the scope of <string>, the following things (conceptually speaking) occur:

<syntaxhighlight lang="cpp"> // define the string template

class you_never_use { // not a template!

  std::string some_member;          // defines a string

}; </syntaxhighlight>

Fourth Workaround: Explicit Instantiation

If you are a library vendor, and your library has a template instantiation problem similar to the one in mylib.lib, there is something you can do to avoid it. You can, in effect, tell the compiler to instantiate a template with a given type on the first compile.

The mechanism is called explicit instantiation, and it is described in The C++ Programming Language, 3rd Ed., section C.13.10.

<syntaxhighlight lang=cpp> // lib2.cpp

1. include <string>

template class std::basic_string<char>; // addition

std::string l1, l2;

void lib_fxn() {

  l1 = "lib string";
  l1 = l2;

} </syntaxhighlight>

Unfortunately, you do have to know that "std::string" is a typedef for "std::basic_string<char>". The explicit instantiation line must refer to the actual template, and not the typedef. An explicit instantiation means the compiler must instantiate everything in the template. What does that look like?

% del *.obj
% cl6x -as lib2.cpp
% nm6x lib2.obj | dem6x -q | perl -ne "print if (m/ [tb] [^\$]*$/i);"
00000000 b .bss
00000000 b .far
00000000 t .text
00000df4 t T1 *std::_Allocate<T1>(unsigned int, T1 *) [with T1=char]
00000878 t void std::basic_string<T1, T2, T3>::_Copy(std::_String_val<T1, T3>::_Alty::size_type, std::_String_val<T1, T3>::_Alty::size_type) [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>]
00000a44 t void std::basic_string<T1, T2, T3>::_Eos(std::_String_val<T1, T3>::_Alty::size_type) [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>]
00000a9c t bool std::basic_string<T1, T2, T3>::_Grow(std::_String_val<T1, T3>::_Alty::size_type, bool) [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>]
00000bec t bool std::basic_string<T1, T2, T3>::_Inside(const T1 *) [with T1=char, T2=std::char_traits<char>, T3=std::allocator<char>]

... snip! ...

Many static functions get instantiated. The best way to handle that is to build with optimization (-o) and the switch for putting each function in its own subsection (-mo for C6000, -ms for ARM). Those build options reduce the number of functions instantiated in the first place, and, on the final link, give the same result as the second workaround.

One valid concern with this workaround is the possiblity of multiple definition errors. What if multiple libraries contain the same explicit instantiation? The answer is to place each explicit instantiation in a file of its own. The linker brings in a member (AKA a file) from a library only when it is needed to satisfy a reference from elsewhere. If two libraries contain the same explicit instantiation, and they both contain that explicit instantiation in a file of its own, only one of those library members is brought in. No multiple definition error occurs.

About Inlining

Templates involve lots of inlining. And there are some issues with inlining. But it is important to understand that template induced inlining does not introduce extra issues over those associated with inlining in the first place. Therefore, C++ Inlining Issues are addressed in a separate article.

Early Template Instantiation

There is a long term solution to all of this. TI compilers for ARM, MSP430, and C6000 devices all support EABI. Template instantiation methods are part of the ABI, and EABI requires a different method called early template instantiation. The details are not worth considering here. The main point is all these template instantiation issues go away. It just works. The same is true of the inlining issues.

As of this writing, TI compilers for C2000, C5500, and C5400 do not support EABI.