From b01aaa16e5adaa0cc064490535f8756b2ef8d421 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Thu, 12 Aug 2021 13:05:54 +0200 Subject: Add ${c,cxx}.deduplicate_export_libs() function This function deduplicates interface library dependencies by removing libraries that are also interface dependencies of the specified libraries. This can result in significantly better build performance for heavily interface-interdependent library families (for example, like Boost). Typical usage: import intf_libs = ... import intf_libs += ... ... import intf_libs += ... intf_libs = $cxx.deduplicate_export_libs($intf_libs) --- libbuild2/cc/common.cxx | 2 ++ libbuild2/cc/functions.cxx | 59 +++++++++++++++++++++++++++++++ libbuild2/cc/link-rule.cxx | 86 ++++++++++++++++++++++++++++++++++++++++++++++ libbuild2/cc/link-rule.hxx | 7 ++++ 4 files changed, 154 insertions(+) (limited to 'libbuild2') diff --git a/libbuild2/cc/common.cxx b/libbuild2/cc/common.cxx index 934ea38..b3a5724 100644 --- a/libbuild2/cc/common.cxx +++ b/libbuild2/cc/common.cxx @@ -165,6 +165,8 @@ namespace build2 // these variables are not overridable) and pass the base scope we // have already resolved. // + // See also deduplicate_export_libs() if changing anything here. + // // @@ PERF: do target_only (helps a bit in non-installed case)? // { diff --git a/libbuild2/cc/functions.cxx b/libbuild2/cc/functions.cxx index 7f9a6c2..6d54c49 100644 --- a/libbuild2/cc/functions.cxx +++ b/libbuild2/cc/functions.cxx @@ -399,6 +399,65 @@ namespace build2 fail << t << " is not an object file target"; }}); + // $.deduplicate_export_libs() + // + // Deduplicate interface library dependencies by removing libraries that + // are also interface dependencies of the specified libraries. This can + // result in significantly better build performance for heavily + // interface-interdependent library families (for example, like Boost). + // Typical usage: + // + // import intf_libs = ... + // import intf_libs += ... + // ... + // import intf_libs += ... + // intf_libs = $cxx.deduplicate_export_libs($intf_libs) + // + // Notes: + // + // 1. We only consider unqualified absolute/normalized target names (the + // idea is that the installed case will already be deduplicated). + // + // 2. We assume all the libraries listed are of the module type and only + // look for cc.export.libs and .export.libs. + // + // 3. No member/group selection/linkup: we resolve *.export.libs on + // whatever is listed. + // + // Note that this function is not pure. + // + f.insert (".deduplicate_export_libs", false). + insert ( + [] (const scope* bs, + vector_view vs, + const function_overload& f) -> value + { + const char* x (*reinterpret_cast (&f.data)); + + if (bs == nullptr) + fail << f.name << " called out of scope"; + + const scope* rs (bs->root_scope ()); + + if (rs == nullptr) + fail << f.name << " called out of project"; + + const module* m (rs->find_module (x)); + + if (m == nullptr) + fail << f.name << " called without " << x << " module loaded"; + + // We can assume the argument is present due to function's types + // signature. + // + names& r (vs[0].as ()); + m->deduplicate_export_libs (*bs, + vector (r.begin (), r.end ()), + r); + return value (move (r)); + }, + x); + // $.find_system_library() // // Return the library path if the specified library exists in one of the diff --git a/libbuild2/cc/link-rule.cxx b/libbuild2/cc/link-rule.cxx index 4497382..76d8418 100644 --- a/libbuild2/cc/link-rule.cxx +++ b/libbuild2/cc/link-rule.cxx @@ -34,6 +34,92 @@ namespace build2 using namespace bin; using build2::to_string; + bool link_rule:: + deduplicate_export_libs (const scope& bs, + const vector& ns, + names& r, + vector>* seen) const + { + bool top (seen == nullptr); + + vector> seen_storage; + if (top) + seen = &seen_storage; + + // The plan is as follows: resolve the target names in ns into targets + // and then traverse their interface dependencies recursively removing + // duplicates from the list r. + // + for (auto i (ns.begin ()), e (ns.end ()); i != e; ++i) + { + if (i->pair) + { + ++i; + continue; + } + + const name& n (*i); + + if (n.qualified () || + !(n.dir.absolute () && n.dir.normalized ()) || + !(n.type == "lib" || n.type == "liba" || n.type != "libs")) + continue; + + if (!top) + { + // Check if we have already seen this library among interface + // dependencies of our interface dependencies. + // + if (find (seen->begin (), seen->end (), n) != seen->end ()) + continue; + + // Remove duplicates. Because we only consider absolute/normalized + // target names, we can just compare their names. + // + for (auto i (r.begin ()); i != r.end (); ) + { + if (i->pair) + i += 2; + else if (*i == n) + i = r.erase (i); + else + ++i; + } + + // @@ TODO: we could optimize this further by returning false if + // there are no viable candidates (e.g., only pairs/qualified/etc + // left). + // + if (r.empty ()) + return false; + } + + if (const target* t = search_existing (n, bs, dir_path () /* out */)) + { + // The same logic as in process_libraries(). + // + const scope& bs (t->base_scope ()); + + if (lookup l = t->lookup_original (c_export_libs, false, &bs).first) + { + if (!deduplicate_export_libs (bs, cast> (l), r, seen)) + return false; + } + + if (lookup l = t->lookup_original (x_export_libs, false, &bs).first) + { + if (!deduplicate_export_libs (bs, cast> (l), r, seen)) + return false; + } + } + + if (!top) + seen->push_back (n); + } + + return true; + } + optional link_rule:: find_system_library (const strings& l) const { diff --git a/libbuild2/cc/link-rule.hxx b/libbuild2/cc/link-rule.hxx index 3d801d6..0fc1790 100644 --- a/libbuild2/cc/link-rule.hxx +++ b/libbuild2/cc/link-rule.hxx @@ -214,6 +214,13 @@ namespace build2 append_binless_modules (strings&, sha256*, const scope&, action, const file&) const; + bool + deduplicate_export_libs ( + const scope&, + const vector&, + names&, + vector>* = nullptr) const; + optional find_system_library (const strings&) const; -- cgit v1.1