[extract_symbols.py] Better handling of templates

[john.brawn]

Summary

Since commit 846b676 SmallVectorBase<uint32_t> has been explicitly instantiated, which means that clang.exe must export it for a plugin to be able to link against it, but the constructor is not exported as currently no template constructors or destructors are exported.

We can't just export all constructors and destructors, as that puts us over the symbol limit on Windows, so instead rewrite how we decide which templates need to be exported to be more precise. Currently we assume that templates instantiated many times have no explicit instantiations, but this isn't necessarily true and results also in exporting implicit template instantiations that we don't need to. Instead check for references to template members, as this indicates that the template must be explicitly instantiated (as if it weren't the template would just be implicitly instantiated on use).

Doing this reduces the number of symbols exported from clang from 66011 to 53993 (in the build configuration that I've been testing). It also lets us get rid of the special-case handling of Type::getAs, as its explicit instantiations are now being detected as such.

[glandium]

Could you add before/after figures of the numbers of symbols in, say, clang.symbols in the summary?

Overall, this LGTM, but I'm not a reviewer.

llvm/utils/extract_symbols.py

183

would it be worth changing this to use parse_microsoft_mangling?

334

you probably want to pass the re.ASCII flag to these match invocations.

346

You can probably drop the \ before the first @.

[john.brawn]

In D142989#4095488, @glandium wrote:

Could you add before/after figures of the numbers of symbols in, say, clang.symbols in the summary?

Will do.

llvm/utils/extract_symbols.py

183

The important thing here is detecting that we have a function type mangling, which parse_microsoft_mangling doesn't do.

334

Names in symbols aren't necessarily ASCII, e.g.

int あ() { return 0; }

results in the symbol ?あ@@YAHXZ. Though we probably don't use non-ASCII identifiers in LLVM, so it doesn't really matter.

[john.brawn]

Adjusted summary, removed superfluous \.

[simon_tatham]

LGTM, with a small commenting nit.

llvm/utils/extract_symbols.py

523–526

Grammar/clarity nit: this comment is now incoherent. Previously its overall structure was a single sentence saying "Print symbols which both [do this] and [are not that]", which made it clear how the two individual conditions combined into the overall decision. But now the "[are not that]" bullet point is replaced with a sentence rather than a predicate.

Suggest rewording to clarify how the revised two conditions are combined.

Reading the code, I _think_ it's "Print symbols which both: [appear in exactly one input] and [are not an unreferenced template]".

[Jake-Egan]

Hi, this caused some failures on AIX, could you take a look?

Could not load library '/scratch/powerllvm/powerllvm_env/aix-ppc64/clang-ppc64-aix/build/unittests/Analysis/InlineAdvisorPlugin.so': rtld: 0712-001 Symbol _ZN4llvm15SmallVectorBaseIjE13mallocForGrowEPvmmRm was referenced
      from module /scratch/powerllvm/powerllvm_env/aix-ppc64/clang-ppc64-aix/build/unittests/Analysis/InlineAdvisorPlugin.so(), but a runtime definition
	    of the symbol was not found.
rtld: 0712-001 Symbol _ZN4llvm13AllAnalysesOnINS_6ModuleEE6SetKeyE was referenced
      from module /scratch/powerllvm/powerllvm_env/aix-ppc64/clang-ppc64-aix/build/unittests/Analysis/InlineAdvisorPlugin.so(), but a runtime definition
	    of the symbol was not found.

LLVM-Unit :: Passes/./PluginsTests/1/2
LLVM-Unit :: Passes/./PluginsTests/0/2
LLVM-Unit :: Analysis/./AnalysisTests/42/81

https://lab.llvm.org/buildbot/#/builders/214/builds/5764

[john.brawn]

In D142989#4115843, @Jake-Egan wrote:

Hi, this caused some failures on AIX, could you take a look?

I'll try, though I don't know anything about AIX so I may not have much success.

[Jake-Egan]

Thank you - it seems only AIX uses -Wl,-brtl flags with these tests.

[john.brawn]

I could reproduce the failure in PluginInlineAdvisorTest.PluginLoad to find _ZN4llvm13AllAnalysesOnINS_6ModuleEE6SetKeyE on Linux as well, when using a suitable build configuration. Fixed in
https://reviews.llvm.org/rG78f13ea093afdebcaa3b5c5690530b9217bbdfac on Linux, and hopefully also on AIX. I don't expect it to fix the failure to find _ZN4llvm15SmallVectorBaseIjE13mallocForGrowEPvmmRm though, so I'll try to figure out what's going on there also.

[Jake-Egan]

Thank you for looking into this. Unfortunately I think 78f13ea093afdebcaa3b5c5690530b9217bbdfac removed another symbol _ZN4llvm4PassD2Ev and _ZN4llvm13AllAnalysesOnINS_6ModuleEE6SetKeyE is still missing as well. https://lab.llvm.org/buildbot/#/builders/214/builds/5781 (EDIT: Or maybe I spoke too soon and a clean build will resolve it: https://lab.llvm.org/buildbot/#/builders/214/builds/5782)

It's possible you don't see the _ZN4llvm15SmallVectorBaseIjE13mallocForGrowEPvmmRm issue on Linux because the symbol isn't called during the test. But on AIX, it is checked for at load time, regardless of a call or not.

[john.brawn]

I noticed that llvm-nm has slightly different output for undefined symbols to GNU nm: GNU nm doesn't list value and size, llvm-nm list value and size zero. I've pushed a fix for that in https://reviews.llvm.org/rGe5d914672233, which may possibly also fix the AIX failure if AIX nm behaves in a similar way to llvm-nm.

[Jake-Egan]

That did the trick! I'm going to go ahead and revert 78f13ea093afdebcaa3b5c5690530b9217bbdfac because it's causing some other failures and your most recent commit fixes things.

llvm/utils/extract_symbols.py

 from __future__ import print_function
 import sys
 import re
 import os
 import subprocess
 import multiprocessing
 import argparse
 
-# Define functions which extract a list of symbols from a library using several
-# different tools. We use subprocess.Popen and yield a symbol at a time instead
-# of using subprocess.check_output and returning a list as, especially on
-# Windows, waiting for the entire output to be ready can take a significant
-# amount of time.
+# Define functions which extract a list of pairs of (symbols, is_def) from a
+# library using several different tools. We use subprocess.Popen and yield a
+# symbol at a time instead of using subprocess.check_output and returning a list
+# as, especially on Windows, waiting for the entire output to be ready can take
+# a significant amount of time.
 
 def dumpbin_get_symbols(lib):
     process = subprocess.Popen(['dumpbin','/symbols',lib], bufsize=1,
                                stdout=subprocess.PIPE, stdin=subprocess.PIPE,
                                universal_newlines=True)
     process.stdin.close()
     for line in process.stdout:
-        # Look for external symbols that are defined in some section
-        match = re.match("^.+SECT.+External\s+\|\s+(\S+).*$", line)
+        # Look for external symbols
+        match = re.match("^.+(SECT|UNDEF).+External\s+\|\s+(\S+).*$", line)
         if match:
-            yield match.group(1)
+            yield (match.group(2), match.group(1) != "UNDEF")
     process.wait()
 
 def nm_get_symbols(lib):
     if sys.platform.startswith('aix'):
         process = subprocess.Popen(['nm','-P','-Xany','-C','-p',lib], bufsize=1,
                                    stdout=subprocess.PIPE, stdin=subprocess.PIPE,
                                    universal_newlines=True)
     else:
         process = subprocess.Popen(['nm','-P',lib], bufsize=1,
                                    stdout=subprocess.PIPE, stdin=subprocess.PIPE,
                                    universal_newlines=True)
     process.stdin.close()
     for line in process.stdout:
         # Look for external symbols that are defined in some section
         # The POSIX format is:
         #   name   type   value   size
         # The -P flag displays the size field for symbols only when applicable,
         # so the last field is optional. There's no space after the value field,
         # but \s+ match newline also, so \s+\S* will match the optional size field.
         match = re.match("^(\S+)\s+[BDGRSTVW]\s+\S+\s+\S*$", line)
         if match:
-            yield match.group(1)
+            yield (match.group(1), True)
+        # Look for undefined symbols, which have only name and type (which is U).
+        match = re.match("^(\S+)\s+U\s+$", line)
+        if match:
+            yield (match.group(1), False)
     process.wait()
 
 def readobj_get_symbols(lib):
     process = subprocess.Popen(['llvm-readobj','--symbols',lib], bufsize=1,
                                stdout=subprocess.PIPE, stdin=subprocess.PIPE,
                                universal_newlines=True)
     process.stdin.close()
     for line in process.stdout:
         # When looking through the output of llvm-readobj we expect to see Name,
         # Section, then StorageClass, so record Name and Section when we see
-        # them and decide if this is a defined external symbol when we see
+        # them and decide if this is an external symbol when we see
         # StorageClass.
         match = re.search('Name: (\S+)', line)
         if match:
             name = match.group(1)
         match = re.search('Section: (\S+)', line)
         if match:
             section = match.group(1)
         match = re.search('StorageClass: (\S+)', line)
         if match:
             storageclass = match.group(1)
             if section != 'IMAGE_SYM_ABSOLUTE' and \
-               section != 'IMAGE_SYM_UNDEFINED' and \
                storageclass == 'External':
-                yield name
+                yield (name, section != 'IMAGE_SYM_UNDEFINED')
     process.wait()
 
 # Define functions which determine if the target is 32-bit Windows (as that's
 # where calling convention name decoration happens).
 
 def dumpbin_is_32bit_windows(lib):
     # dumpbin /headers can output a huge amount of data (>100MB in a debug
     # build) so we read only up to the 'machine' line then close the output.
if not '?' in symbol:
             # Remove calling convention decoration from names
             match = re.match('[_@]([^@]+)', symbol)
             if match:
                 symbol = match.group(1)
         # Discard floating point/SIMD constants.
         if symbol.startswith(("__xmm@", "__ymm@", "__real@")):
             return None
         return symbol
-    # Function template instantiations start with ?$; keep the instantiations of
-    # clang::Type::getAs, as some of them are explipict specializations that are
-    # defined in clang's lib/AST/Type.cpp; discard the rest as it's assumed that
-    # the definition is public
-    elif re.match('\?\?\$getAs@.+@Type@clang@@', symbol):
-        return symbol
-    elif symbol.startswith('??$'):
-        return None
     # Deleting destructors start with ?_G or ?_E and can be discarded because
     # link.exe gives you a warning telling you they can't be exported if you
     # don't
     elif symbol.startswith('??_G') or symbol.startswith('??_E'):
         return None
-    # Constructors (?0) and destructors (?1) of templates (?$) are assumed to be
-    # defined in headers and not required to be kept
-    elif symbol.startswith('??0?$') or symbol.startswith('??1?$'):
-        return None
     # An anonymous namespace is mangled as ?A(maybe hex number)@. Any symbol
     # that mentions an anonymous namespace can be discarded, as the anonymous
     # namespace doesn't exist outside of that translation unit.
     elif re.search('\?A(0x\w+)?@', symbol):
         return None
     # Skip X86GenMnemonicTables functions, they are not exposed from llvm/include/.
     elif re.match('\?is[A-Z0-9]*@X86@llvm', symbol):
         return None
def should_keep_microsoft_symbol(symbol, calling_convention_decoration):
     # <function-class> ::= [A-Z]
     # <this-cvr-qualifiers> ::= [A-Z0-9_]*
     # <calling-convention> ::= [A-JQ]
     # <return-type> ::= .+
     # <argument-list> ::= X   (void)
     #                 ::= .+@ (list of types)
     #                 ::= .*Z (list of types, varargs)
     # <throw-spec> ::= exceptions are not allowed
     elif re.search('(llvm|clang)@@[A-Z][A-Z0-9_]*[A-JQ].+(X|.+@|.*Z)$', symbol):
         return symbol
     return None
 
 # Itanium manglings are of the form _Z<identifier_mangling><type_mangling>. We
 # demangle the identifier mangling to identify symbols that can be safely
 # discarded.
 def should_keep_itanium_symbol(symbol, calling_convention_decoration):
     # Start by removing any calling convention decoration (which we expect to
def should_keep_itanium_symbol(symbol, calling_convention_decoration):
     # Demangle the name. If the name is too complex then we don't need to keep
     # it, but it the demangling fails then keep the symbol just in case.
     try:
         names, _ = parse_itanium_nested_name(match.group(2))
     except TooComplexName:
         return None
     if not names:
         return symbol
-    # Constructors and destructors of templates classes are assumed to be
-    # defined in headers and not required to be kept
-    if re.match('[CD][123]', names[-1][0]) and names[-2][1]:
-        return None
-    # Keep the instantiations of clang::Type::getAs, as some of them are
-    # explipict specializations that are defined in clang's lib/AST/Type.cpp;
-    # discard any other function template instantiations as it's assumed that
-    # the definition is public
-    elif symbol.startswith('_ZNK5clang4Type5getAs'):
-        return symbol
-    elif names[-1][1]:
-        return None
     # Keep llvm:: and clang:: names
     elif names[0][0] == '4llvm' or names[0][0] == '5clang':
         return symbol
     # Discard everything else
     else:
         return None
 
 # Certain kinds of complex manglings we assume cannot be part of a public
while tmp:
             tmp = skip_itanium_template(tmp)
             is_template = True
         # Add the name to the list
         ret.append((name_part, is_template))
 
     # If we get here then something went wrong
     return None, None
 
+# Parse a microsoft mangled symbol and return a list of pairs of
+# (name, is_template). This is very rudimentary and does just enough
+# in order to determine if the first or second component is a template.
+def parse_microsoft_mangling(arg):
+    # If the name doesn't start with ? this isn't a mangled name
+    if not arg.startswith('?'):
+        return [(arg, False)]
+    arg = arg[1:]
+    components = []
+    while len(arg) > 0:
+        # If we see an empty component we've reached the end
+        if arg.startswith('@'):
+            return components
+        # Check for a simple name
+        match = re.match('(\w+)@(.+)', arg)
+        if match:
+            components.append((match.group(1), False))
+            arg = match.group(2)
+            continue
+        # Check for a special function name
+        match = re.match('(\?_?\w)(.+)', arg)
+        if match:
+            components.append((match.group(1), False))
+            arg = match.group(2)
+            continue
+        # Check for a template name
+        match = re.match('\?\$(\w+)@[^@]+@(.+)', arg)
+        if match:
+            components.append((match.group(1), True))
+            arg = match.group(2)
+            continue
+        # Some other kind of name that we can't handle
+        components.append((arg, False))
+        return components
+    return components
+
 def extract_symbols(arg):
     get_symbols, should_keep_symbol, calling_convention_decoration, lib = arg
-    symbols = dict()
-    for symbol in get_symbols(lib):
+    symbol_defs = dict()
+    symbol_refs = set()
+    for (symbol, is_def) in get_symbols(lib):
         symbol = should_keep_symbol(symbol, calling_convention_decoration)
         if symbol:
-            symbols[symbol] = 1 + symbols.setdefault(symbol,0)
-    return symbols
+            if is_def:
+                symbol_defs[symbol] = 1 + symbol_defs.setdefault(symbol,0)
+            else:
+                symbol_refs.add(symbol)
+    return (symbol_defs, symbol_refs)
+
+def get_template_name(sym, mangling):
+    # Parse the mangling into a list of (name, is_template)
+    try:
+        if mangling == 'microsoft':
+            names = parse_microsoft_mangling(sym)
+        else:
+            match = re.match('_Z(T[VTIS])?(N.+)', sym)
+            if match:
+                names, _ = parse_itanium_nested_name(match.group(2))
+            else:
+                names = None
+    except TooComplexName:
+        return None
+
+    if not names:
+        return None
+
+    # If any component is a template then return it
+    for name, is_template in names:
+        if is_template:
+            return name
+
+    # Not a template
+    return None
 
 if __name__ == '__main__':
     tool_exes = ['dumpbin','nm','objdump','llvm-readobj']
     parser = argparse.ArgumentParser(
         description='Extract symbols to export from libraries')
     parser.add_argument('--mangling', choices=['itanium','microsoft'],
                         required=True, help='expected symbol mangling scheme')
     parser.add_argument('--tools', choices=tool_exes, nargs='*',
try:
         libs_symbols = result.get(3600)
     except KeyboardInterrupt:
         # On Ctrl-C terminate everything and exit
         pool.terminate()
         pool.join()
         exit(1)
 
     # Merge everything into a single dict
-    symbols = dict()
-    for this_lib_symbols in libs_symbols:
-        for k,v in list(this_lib_symbols.items()):
-            symbols[k] = v + symbols.setdefault(k,0)
-
-    # Count instances of member functions of template classes, and map the
-    # symbol name to the function+class. We do this under the assumption that if
-    # a member function of a template class is instantiated many times it's
-    # probably declared in a public header file.
-    template_function_count = dict()
-    template_function_mapping = dict()
-    template_function_count[""] = 0
-    for k in symbols:
-        name = None
-        if args.mangling == 'microsoft':
-            # Member functions of templates start with
-            # ?<fn_name>@?$<class_name>@, so we map to <fn_name>@?$<class_name>.
-            # As manglings go from the innermost scope to the outermost scope
-            # this means:
-            #  * When we have a function member of a subclass of a template
-            #    class then <fn_name> will actually contain the mangling of
-            #    both the subclass and the function member. This is fine.
-            #  * When we have a function member of a template subclass of a
-            #    (possibly template) class then it's the innermost template
-            #    subclass that becomes <class_name>. This should be OK so long
-            #    as we don't have multiple classes with a template subclass of
-            #    the same name.
-            match = re.search("^\?(\??\w+\@\?\$\w+)\@", k)
-            if match:
-                name = match.group(1)
-        else:
-            # Find member functions of templates by demangling the name and
-            # checking if the second-to-last name in the list is a template.
-            match = re.match('_Z(T[VTIS])?(N.+)', k)
-            if match:
-                try:
-                    names, _ = parse_itanium_nested_name(match.group(2))
-                    if names and names[-2][1]:
-                        name = ''.join([x for x,_ in names])
-                except TooComplexName:
-                    # Manglings that are too complex should already have been
-                    # filtered out, but if we happen to somehow see one here
-                    # just leave it as-is.
-                    pass
-        if name:
-            old_count = template_function_count.setdefault(name,0)
-            template_function_count[name] = old_count + 1
-            template_function_mapping[k] = name
-        else:
-            template_function_mapping[k] = ""
+    symbol_defs = dict()
+    symbol_refs = set()
+    for (this_lib_defs, this_lib_refs) in libs_symbols:
+        for k,v in list(this_lib_defs.items()):
+            symbol_defs[k] = v + symbol_defs.setdefault(k,0)
+        for sym in list(this_lib_refs):
+            symbol_refs.add(sym)
+
+    # Find which template instantiations are referenced at least once.
+    template_instantiation_refs = set()
+    for sym in list(symbol_refs):
+        template = get_template_name(sym, args.mangling)
+        if template:
+            template_instantiation_refs.add(template)
 
     # Print symbols which both:
     #  * Appear in exactly one input, as symbols defined in multiple
     #    objects/libraries are assumed to have public definitions.
-    #  * Aren't instances of member functions of templates which have been
-    #    instantiated 100 times or more, which are assumed to have public
-    #    definitions. (100 is an arbitrary guess here.)
+    #  * Are not a template instantiation that isn't referenced anywhere. This
+    #    is because we need to export any explicitly instantiated templates,
+    #    and we expect those to be referenced in some object.
     if args.o:
         outfile = open(args.o,'w')
     else:
         outfile = sys.stdout
-    for k,v in list(symbols.items()):
-        template_count = template_function_count[template_function_mapping[k]]
-        if v == 1 and template_count < 100:
+    for k,v in list(symbol_defs.items()):
+        template = get_template_name(k, args.mangling)
+        if v == 1 and (not template or template in template_instantiation_refs):
             print(k, file=outfile)