[cmake] Unbreak LLVM-Config.cmake / llvm_expand_dependencies

[whitequark]

Summary

The algorithm for sorting libraries in topological order, as
previously implemented, had a few issues:

• It didn't make any sense.
• It didn't actually sort libraries in topological order.
• It hung on some inputs, e.g. "LLVMipo".

This commit replaces the old algorithm with a straightforward port
from llvm-config.cpp.

[whitequark]

The new implementation was tested in the CMake buildsystem of the OCaml bindings, which I will post a bit later. It links a lot of libraries in different combinations, which, with BUILD_SHARED_LIBS=OFF, exposed both the incorrect ordering and the hangups in the old implementation. The new one works perfectly well.

[rnk]

cmake/modules/LLVM-Config.cmake

155

Can you add a comment before the function describing what it does, and perhaps reference the llvm-config code? It's doing a post-order traversal, which is apparently not what the linker expects.

Would a pre-order traversal save the list reversal? It's not immediately clear to me that it would.

183

I guess the linker actually expects roots first and leaves last.

[whitequark]

cmake/modules/LLVM-Config.cmake

155

It just duplicates the algorithm in the llvm-config binary to keep things simple. Also IIRC I started with a pre-order traversal and it looked really ugly when implemented in cmake.

183

What do you mean? llvm_expand_dependencies currently uses the correct ordering; it won't build without this REVERSE.

[whitequark]

@rnk, I've added the documentation.

[rnk]

lgtm

Thanks!

[whitequark]

Committed in rL224554

cmake/modules/LLVM-Config.cmake

else( NOT idx LESS 0 )
         list(APPEND expanded_components ${canonical_lib})
       endif( lib_idx LESS 0 )
     endif( NOT idx LESS 0 )
   endforeach(c)
 
   set(${out_libs} ${expanded_components} PARENT_SCOPE)
 endfunction()
 
+# Perform a post-order traversal of the dependency graph.
+# This duplicates the algorithm used by llvm-config, originally
+# in tools/llvm-config/llvm-config.cpp, function ComputeLibsForComponents.
+function(expand_topologically name required_libs visited_libs)
+  list(FIND visited_libs ${name} found)
+  if( found LESS 0 )
+    list(APPEND visited_libs ${name})
+    set(visited_libs ${visited_libs} PARENT_SCOPE)
+
+    get_property(lib_deps GLOBAL PROPERTY LLVMBUILD_LIB_DEPS_${name})
+    foreach( lib_dep ${lib_deps} )
+      expand_topologically(${lib_dep} "${required_libs}" "${visited_libs}")
+      set(required_libs ${required_libs} PARENT_SCOPE)
+      set(visited_libs ${visited_libs} PARENT_SCOPE)
+    endforeach()
+
+    list(APPEND required_libs ${name})
+    set(required_libs ${required_libs} PARENT_SCOPE)
+  endif()
+endfunction()
+
 # Expand dependencies while topologically sorting the list of libraries:
 function(llvm_expand_dependencies out_libs)
   set(expanded_components ${ARGN})
-  list(LENGTH expanded_components lst_size)
-  set(cursor 0)
-  set(processed)
-  while( cursor LESS lst_size )
-    list(GET expanded_components ${cursor} lib)
-    get_property(lib_deps GLOBAL PROPERTY LLVMBUILD_LIB_DEPS_${lib})
-    list(APPEND expanded_components ${lib_deps})
-    # Remove duplicates at the front:
-    list(REVERSE expanded_components)
-    list(REMOVE_DUPLICATES expanded_components)
-    list(REVERSE expanded_components)
-    list(APPEND processed ${lib})
-    # Find the maximum index that doesn't have to be re-processed:
-    while(NOT "${expanded_components}" MATCHES "^${processed}.*" )
-      list(REMOVE_AT processed -1)
-    endwhile()
-    list(LENGTH processed cursor)
-    list(LENGTH expanded_components lst_size)
-  endwhile( cursor LESS lst_size )
-  set(${out_libs} ${expanded_components} PARENT_SCOPE)
+
+  set(required_libs)
+  set(visited_libs)
+  foreach( lib ${expanded_components} )
+    expand_topologically(${lib} "${required_libs}" "${visited_libs}")
+  endforeach()
+
+  list(REVERSE required_libs)
+  set(${out_libs} ${required_libs} PARENT_SCOPE)
 endfunction()
 
 function(explicit_map_components_to_libraries out_libs)
   llvm_map_components_to_libnames(link_libs ${ARGN})
   llvm_expand_dependencies(expanded_components ${link_libs})
   # Return just the libraries included in this build:
   set(result)
   foreach(c ${expanded_components})
     if( TARGET ${c} )
       set(result ${result} ${c})
     endif()
   endforeach(c)
   set(${out_libs} ${result} PARENT_SCOPE)
 endfunction(explicit_map_components_to_libraries)