Topologically sort the link options generated for modules based on
module-import dependencies, so we'll get the link order correct for
those silly linkers that need it.


git-svn-id: https://llvm.org/svn/llvm-project/cfe/trunk@172459 91177308-0d34-0410-b5e6-96231b3b80d8
diff --git a/lib/CodeGen/CodeGenModule.cpp b/lib/CodeGen/CodeGenModule.cpp
index 4b662e0..01bc66b 100644
--- a/lib/CodeGen/CodeGenModule.cpp
+++ b/lib/CodeGen/CodeGenModule.cpp
@@ -173,6 +173,7 @@
   EmitCtorList(GlobalDtors, "llvm.global_dtors");
   EmitGlobalAnnotations();
   EmitLLVMUsed();
+  EmitModuleLinkOptions();
 
   SimplifyPersonality();
 
@@ -715,6 +716,116 @@
   GV->setSection("llvm.metadata");
 }
 
+/// \brief Add link options implied by the given module, including modules
+/// it depends on, using a postorder walk.
+static void addLinkOptionsPostorder(llvm::LLVMContext &Context,
+                                    Module *Mod,
+                                    SmallVectorImpl<llvm::MDNode *> &Metadata,
+                                    llvm::SmallPtrSet<Module *, 16> &Visited) {
+  // Import this module's parent.
+  if (Mod->Parent && Visited.insert(Mod->Parent)) {
+    addLinkOptionsPostorder(Context, Mod->Parent, Metadata, Visited);
+  }
+
+  // Import this module's dependencies.
+  for (unsigned I = Mod->Imports.size(); I > 0; --I) {
+    if (Visited.insert(Mod->Imports[I-1]))
+      addLinkOptionsPostorder(Context, Mod->Imports[I-1], Metadata, Visited);
+  }
+
+  // Add linker options to link against the libraries/frameworks
+  // described by this module.
+  for (unsigned I = Mod->LinkLibraries.size(); I > 0; --I) {
+    // FIXME: -lfoo is Unix-centric and -framework Foo is Darwin-centric.
+    // We need to know more about the linker to know how to encode these
+    // options propertly.
+
+    // Link against a framework.
+    if (Mod->LinkLibraries[I-1].IsFramework) {
+      llvm::Value *Args[2] = {
+        llvm::MDString::get(Context, "-framework"),
+        llvm::MDString::get(Context, Mod->LinkLibraries[I-1].Library)
+      };
+
+      Metadata.push_back(llvm::MDNode::get(Context, Args));
+      continue;
+    }
+
+    // Link against a library.
+    llvm::Value *OptString
+    = llvm::MDString::get(Context,
+                          "-l" + Mod->LinkLibraries[I-1].Library);
+    Metadata.push_back(llvm::MDNode::get(Context, OptString));
+  }
+}
+
+void CodeGenModule::EmitModuleLinkOptions() {
+  // Collect the set of all of the modules we want to visit to emit link
+  // options, which is essentially the imported modules and all of their
+  // non-explicit child modules.
+  llvm::SetVector<clang::Module *> LinkModules;
+  llvm::SmallPtrSet<clang::Module *, 16> Visited;
+  SmallVector<clang::Module *, 16> Stack;
+
+  // Seed the stack with imported modules.
+  for (llvm::SetVector<clang::Module *>::iterator M = ImportedModules.begin(),
+                                               MEnd = ImportedModules.end();
+       M != MEnd; ++M) {
+    if (Visited.insert(*M))
+      Stack.push_back(*M);
+  }
+
+  // Find all of the modules to import, making a little effort to prune
+  // non-leaf modules.
+  while (!Stack.empty()) {
+    clang::Module *Mod = Stack.back();
+    Stack.pop_back();
+
+    bool AnyChildren = false;
+
+    // Visit the submodules of this module.
+    for (clang::Module::submodule_iterator Sub = Mod->submodule_begin(),
+                                        SubEnd = Mod->submodule_end();
+         Sub != SubEnd; ++Sub) {
+      // Skip explicit children; they need to be explicitly imported to be
+      // linked against.
+      if ((*Sub)->IsExplicit)
+        continue;
+
+      if (Visited.insert(*Sub)) {
+        Stack.push_back(*Sub);
+        AnyChildren = true;
+      }
+    }
+
+    // We didn't find any children, so add this module to the list of
+    // modules to link against.
+    if (!AnyChildren) {
+      LinkModules.insert(Mod);
+    }
+  }
+
+  // Add link options for all of the imported modules in reverse topological
+  // order.
+  SmallVector<llvm::MDNode *, 16> MetadataArgs;
+  Visited.clear();
+  for (llvm::SetVector<clang::Module *>::iterator M = LinkModules.begin(),
+                                               MEnd = LinkModules.end();
+       M != MEnd; ++M) {
+    if (Visited.insert(*M))
+      addLinkOptionsPostorder(getLLVMContext(), *M, MetadataArgs, Visited);
+  }
+
+  // Get/create metadata for the link options.
+  llvm::NamedMDNode *Metadata
+    = getModule().getOrInsertNamedMetadata("llvm.module.linkoptions");
+
+  // Add link options in topological order.
+  for (unsigned I = MetadataArgs.size(); I > 0; --I) {
+    Metadata->addOperand(MetadataArgs[I-1]);
+  }
+}
+
 void CodeGenModule::EmitDeferred() {
   // Emit code for any potentially referenced deferred decls.  Since a
   // previously unused static decl may become used during the generation of code
@@ -2772,73 +2883,7 @@
         break;
     }
 
-    // Walk from this module up to its top-level module; we'll import all of
-    // these modules and their non-explicit child modules.
-    llvm::SmallVector<clang::Module *, 2> Stack;
-    for (clang::Module *Mod = Import->getImportedModule(); Mod;
-         Mod = Mod->Parent) {
-      if (!ImportedModules.insert(Mod))
-        break;
-      
-      Stack.push_back(Mod);
-    }
-
-    if (Stack.empty())
-      break;
-
-    // Get/create metadata for the link options.
-    llvm::NamedMDNode *Metadata
-      = getModule().getOrInsertNamedMetadata("llvm.module.linkoptions");
-
-    // Find all of the non-explicit submodules of the modules we've imported and
-    // import them.
-    while (!Stack.empty()) {
-      clang::Module *Mod = Stack.back();
-      Stack.pop_back();
-
-      // Add linker options to link against the libraries/frameworks
-      // described by this module.
-      for (unsigned I = 0, N = Mod->LinkLibraries.size(); I != N; ++I) {
-        // FIXME: -lfoo is Unix-centric and -framework Foo is Darwin-centric.
-        // We need to know more about the linker to know how to encode these
-        // options propertly.
-
-        // Link against a framework.
-        if (Mod->LinkLibraries[I].IsFramework) {
-          llvm::Value *Args[2] = {
-            llvm::MDString::get(getLLVMContext(), "-framework"),
-            llvm::MDString::get(getLLVMContext(),
-                                Mod->LinkLibraries[I].Library)
-          };
-          
-          Metadata->addOperand(llvm::MDNode::get(getLLVMContext(), Args));
-          continue;
-        }
-
-        // Link against a library.
-        llvm::Value *OptString
-          = llvm::MDString::get(getLLVMContext(),
-                                "-l" + Mod->LinkLibraries[I].Library);
-        Metadata->addOperand(llvm::MDNode::get(getLLVMContext(), OptString));
-      }
-
-      // Import this module's (non-explicit) submodules.
-      for (clang::Module::submodule_iterator Sub = Mod->submodule_begin(),
-                                          SubEnd = Mod->submodule_end();
-           Sub != SubEnd; ++Sub) {
-        if ((*Sub)->IsExplicit)
-          continue;
-
-        if (ImportedModules.insert(*Sub))
-          Stack.push_back(*Sub);
-      }
-
-      // Import this module's dependencies.
-      for (unsigned I = 0, N = Mod->Imports.size(); I != N; ++I) {
-        if (ImportedModules.insert(Mod->Imports[I]))
-          Stack.push_back(Mod->Imports[I]);
-      }
-    }
+    ImportedModules.insert(Import->getImportedModule());
     break;
  }
 
diff --git a/lib/CodeGen/CodeGenModule.h b/lib/CodeGen/CodeGenModule.h
index 4088cac..00a98a6 100644
--- a/lib/CodeGen/CodeGenModule.h
+++ b/lib/CodeGen/CodeGenModule.h
@@ -995,6 +995,9 @@
   /// references to global which may otherwise be optimized out.
   void EmitLLVMUsed();
 
+  /// \brief Emit the link options introduced by imported modules.
+  void EmitModuleLinkOptions();
+
   void EmitDeclMetadata();
 
   /// EmitCoverageFile - Emit the llvm.gcov metadata used to tell LLVM where
diff --git a/test/Modules/autolink.m b/test/Modules/autolink.m
index 9da6d32..e1a240b 100644
--- a/test/Modules/autolink.m
+++ b/test/Modules/autolink.m
@@ -13,8 +13,13 @@
   return autolink;
 }
 
+@import Module.SubFramework;
+const char *get_module_subframework() {
+  return module_subframework;
+}
+
 @import DependsOnModule.SubFramework;
-float *get_module_subframework() {
+float *get_module_subframework_dep() {
   return sub_framework;
 }
 
@@ -23,9 +28,9 @@
   return no_umbrella_A;
 }
 
-// CHECK: !llvm.module.linkoptions = !{![[AUTOLINK:[0-9]+]], ![[AUTOLINK_FRAMEWORK:[0-9]+]], ![[DEPENDSONMODULE:[0-9]+]], ![[MODULE:[0-9]+]], ![[NOUMBRELLA:[0-9]+]]}
-// CHECK: ![[AUTOLINK]] = metadata !{metadata !"-lautolink"}
+// CHECK: !llvm.module.linkoptions = !{![[AUTOLINK_FRAMEWORK:[0-9]+]], ![[AUTOLINK:[0-9]+]], ![[DEPENDSONMODULE:[0-9]+]], ![[MODULE:[0-9]+]], ![[NOUMBRELLA:[0-9]+]]}
 // CHECK: ![[AUTOLINK_FRAMEWORK]] = metadata !{metadata !"-framework", metadata !"autolink_framework"}
+// CHECK: ![[AUTOLINK]] = metadata !{metadata !"-lautolink"}
 // CHECK: ![[DEPENDSONMODULE]] = metadata !{metadata !"-framework", metadata !"DependsOnModule"}
 // CHECK: ![[MODULE]] = metadata !{metadata !"-framework", metadata !"Module"}
 // CHECK: ![[NOUMBRELLA]] = metadata !{metadata !"-framework", metadata !"NoUmbrella"}