Don't write order-only deps reachable through direct deps
The size of the generated ninja files is quadratic: NinjaCBinaryTargetWriter writes an order-only dep for every non-linkable
dep of a target. `source_set("a")` depending on `source_set("b")`
depending on `source_set("c")` produced:
build phony/c.linkdeps: phony c.o
build phony/b.linkdeps: phony b.o || phony/c.linkdeps
build phony/a.linkdeps: phony a.o || phony/b.linkdeps phony/c.linkdeps
a.linkdeps listing c.linkdeps is not needed.
Instead, only write order-only deps for:
1. Direct deps (looking through groups, which have no build statement).
2. Libraries inherited through direct deps whose build statement doesn't
list them (e.g. Rust libraries, or final targets that forward shared
libraries).
3. Frameworks (create_bundle targets). ClassifyDependency() doesn't
treat them as non-linkable deps of non-final targets.
https://issues.chromium.org/issues/40278737#comment7 compares ninja
files before and after this patch and checks that they are equivalent.
Results for a Chromium build (mac, arm64, is_debug=false):
before after
size of all loaded .ninja files 2634 MB 1009 MB
.linkdeps phony edges 1442 MB 15 MB
`||` on alink edges 181 MB 5 MB
`||` on link edges 21 MB 0.3 MB
gn gen (hyperfine, 6 runs) 2.917s ± .047 2.160s ± .052
user / sys 18.5s / 7.2s 12.3s / 4.7s
Chromium no-op builds of base_unittests (target already built, hyperfine,
M-series Mac), for siso and various ninja versions:
before after
siso v1.6.0 (autoninja), -offline 1.058s ± .031 735.5 ms ± 13.7
user / sys 7.0s / 2.0s 3.7s / 1.9s
depot_tools ninja (1.12.1) 10.09s ± .10 4.37s ± .02
ninja v1.13.2 6.388s ± .049 2.755s ± .009
ninja with some local changes to tweak perf 950.9 ms ± 5.1 535.8 ms ± 2.7
(`siso -n` and `ninja -n` are within 2% of the no-op times.)
No intended behavior change.
Bug: chromium:40278737
Change-Id: I517db1c641001e404d3e02ab0e653c1133076d7f
Reviewed-on: https://gn-review.googlesource.com/c/gn/+/26740
Commit-Queue: Nico Weber <thakis@chromium.org>
Reviewed-by: Takuto Ikuta <tikuta@google.com>
Reviewed-by: Nico Weber <thakis@google.com>
diff --git a/src/gn/ninja_binary_target_writer.cc b/src/gn/ninja_binary_target_writer.cc
index 8c8d2a0..6461102 100644
--- a/src/gn/ninja_binary_target_writer.cc
+++ b/src/gn/ninja_binary_target_writer.cc
@@ -544,11 +544,72 @@
}
}
+// Returns true if the build statement for |target|'s dependency output is
+// written by NinjaCBinaryTargetWriter and lists the order-only deps of all
+// non-linkable deps of |target|, which include (almost, see below) all of
+// |target|'s inherited libraries: Source sets list them on their .linkdeps
+// phony target, static libraries on their link step.
+static bool ListsOrderOnlyDepsOfInheritedLibs(const Target* target) {
+ return (target->output_type() == Target::SOURCE_SET ||
+ target->output_type() == Target::STATIC_LIBRARY) &&
+ !target->IsFinal() && !target->source_types_used().RustSourceUsed() &&
+ target->has_dependency_output();
+}
+
std::vector<OutputFile>
NinjaBinaryTargetWriter::GetOrderOnlyDepsFromNonLinkableDeps(
const UniqueVector<const Target*>& non_linkable_deps) const {
+ // |non_linkable_deps| contains the transitive closure of all inherited
+ // libraries. Listing all of them is redundant: If this target depends on a
+ // source set or static library D, then every library inherited through D is
+ // a non-linkable dep of D, and D's build statement (which this target
+ // depends on) already has an order-only dep on it. So only list:
+ // 1. direct deps, looking through groups
+ // 2. libraries inherited through direct deps whose build statement doesn't
+ // list them (see ListsOrderOnlyDepsOfInheritedLibs())
+ // 3. frameworks, since ClassifyDependency() doesn't treat them as
+ // non-linkable deps for non-final targets.
+ TargetSet direct_deps;
+ TargetSet inherited_through_other_deps;
+ bool can_omit_deps = false;
+ // The Rust writer lists some deps differently; keep it simple there.
+ if (!target_->source_types_used().RustSourceUsed()) {
+ const auto& target_deps = resolved().GetTargetDeps(target_);
+ std::vector<const Target*> worklist(target_deps.linked_deps().begin(),
+ target_deps.linked_deps().end());
+ while (!worklist.empty()) {
+ const Target* dep = worklist.back();
+ worklist.pop_back();
+ if (!direct_deps.add(dep))
+ continue;
+ if (dep->output_type() == Target::GROUP) {
+ const auto& group_deps = resolved().GetTargetDeps(dep);
+ worklist.insert(worklist.end(), group_deps.linked_deps().begin(),
+ group_deps.linked_deps().end());
+ continue;
+ }
+ if (ListsOrderOnlyDepsOfInheritedLibs(dep)) {
+ can_omit_deps = true;
+ continue;
+ }
+ // Final targets only forward (some) final targets, see
+ // ResolvedTargetData::ComputeInheritedLibsFor().
+ for (const auto& pair : resolved().GetInheritedLibraries(dep)) {
+ if (!dep->IsFinal() || pair.target()->IsFinal())
+ inherited_through_other_deps.add(pair.target());
+ }
+ }
+ for (const Target* data_dep : target_deps.data_deps())
+ direct_deps.add(data_dep);
+ }
+
UniqueVector<OutputFile> outputs_to_write;
for (const Target* dep : non_linkable_deps) {
+ if (can_omit_deps && !direct_deps.contains(dep) &&
+ !inherited_through_other_deps.contains(dep) &&
+ dep->output_type() != Target::CREATE_BUNDLE) {
+ continue;
+ }
outputs_to_write.Append(resolved().GetOrderOnlyDeps(dep));
}
return outputs_to_write.release();
diff --git a/src/gn/ninja_c_binary_target_writer_unittest.cc b/src/gn/ninja_c_binary_target_writer_unittest.cc
index 2f4977d..746aa59 100644
--- a/src/gn/ninja_c_binary_target_writer_unittest.cc
+++ b/src/gn/ninja_c_binary_target_writer_unittest.cc
@@ -493,7 +493,7 @@
"defines = -DBOOL_DEF -DINT_DEF=123 -DSTR_DEF=\\\"ABCD-1\\\"";
#endif
std::string out_str = out.str();
- EXPECT_TRUE(out_str.find(expectedSubstr) != std::string::npos);
+ EXPECT_TRUE(out_str.contains(expectedSubstr));
}
TEST_F(NinjaCBinaryTargetWriterTest, StaticLibrary) {
@@ -2038,9 +2038,7 @@
"obj/staticlib/libstaticlib.a "
"obj/dylib/libdylib.so | "
"obj/pub_in_staticlib/libpub_in_staticlib.rlib "
- "obj/priv_in_staticlib/libpriv_in_staticlib.rlib || "
- "phony/pub_sset_in_staticlib/pub_sset_in_staticlib.linkdeps "
- "phony/priv_sset_in_staticlib/priv_sset_in_staticlib.linkdeps\n"
+ "obj/priv_in_staticlib/libpriv_in_staticlib.rlib\n"
" ldflags =\n"
" libs =\n"
" frameworks =\n"
@@ -3141,7 +3139,7 @@
source_file_part = c.modulemap
source_name_part = c
-build obj/things/libc.a: alink || obj/stuff/libb.a obj/blah/liba.a
+build obj/things/libc.a: alink || obj/stuff/libb.a
arflags =
output_extension =
output_dir =
@@ -3677,3 +3675,130 @@
EXPECT_EQ(expected, out.str());
}
}
+
+// Order-only deps on inherited libraries are only written if they aren't
+// already reachable through the build statement of a direct dependency.
+TEST_F(NinjaCBinaryTargetWriterTest, OrderOnlyDepsOmitTransitiveDeps) {
+ Err err;
+ TestWithScope setup;
+
+ auto make_source_set = [&](Target* target) {
+ target->set_output_type(Target::SOURCE_SET);
+ target->visibility().SetPublic();
+ target->sources().push_back(
+ SourceFile("//foo/" + target->label().name() + ".cc"));
+ target->source_types_used().Set(SourceFile::SOURCE_CPP);
+ target->SetToolchain(setup.toolchain());
+ };
+
+ // a -> b -> c: a doesn't need to list c because b's .linkdeps already does.
+ Target c(setup.settings(), Label(SourceDir("//foo/"), "c"));
+ make_source_set(&c);
+ ASSERT_TRUE(c.OnResolved(&err));
+ Target b(setup.settings(), Label(SourceDir("//foo/"), "b"));
+ make_source_set(&b);
+ b.public_deps().push_back(LabelTargetPair(&c));
+ ASSERT_TRUE(b.OnResolved(&err));
+
+ // a -> group -> d -> e: a needs to list d (groups are looked through and
+ // have no build statement that could list d), but not e.
+ Target e(setup.settings(), Label(SourceDir("//foo/"), "e"));
+ make_source_set(&e);
+ ASSERT_TRUE(e.OnResolved(&err));
+ Target d(setup.settings(), Label(SourceDir("//foo/"), "d"));
+ make_source_set(&d);
+ d.private_deps().push_back(LabelTargetPair(&e));
+ ASSERT_TRUE(d.OnResolved(&err));
+ Target group(setup.settings(), Label(SourceDir("//foo/"), "group"));
+ group.set_output_type(Target::GROUP);
+ group.visibility().SetPublic();
+ group.public_deps().push_back(LabelTargetPair(&d));
+ group.SetToolchain(setup.toolchain());
+ ASSERT_TRUE(group.OnResolved(&err));
+
+ // a -> rlib -> f: Rust libraries forward inherited libraries but their
+ // build statements aren't known to list them, so a needs to list f.
+ Target f(setup.settings(), Label(SourceDir("//foo/"), "f"));
+ make_source_set(&f);
+ ASSERT_TRUE(f.OnResolved(&err));
+ Target rlib(setup.settings(), Label(SourceDir("//foo/"), "rlib"));
+ rlib.set_output_type(Target::RUST_LIBRARY);
+ rlib.visibility().SetPublic();
+ SourceFile rlib_root("//foo/lib.rs");
+ rlib.sources().push_back(rlib_root);
+ rlib.source_types_used().Set(SourceFile::SOURCE_RS);
+ rlib.rust_values().set_crate_root(rlib_root);
+ rlib.rust_values().crate_name() = "rlib";
+ rlib.private_deps().push_back(LabelTargetPair(&f));
+ rlib.SetToolchain(setup.toolchain());
+ ASSERT_TRUE(rlib.OnResolved(&err));
+
+ // a -> b2 -> c (again), and a -> e2 directly while also a -> d2 -> e2:
+ // direct deps are always listed.
+ Target e2(setup.settings(), Label(SourceDir("//foo/"), "e2"));
+ make_source_set(&e2);
+ ASSERT_TRUE(e2.OnResolved(&err));
+ Target d2(setup.settings(), Label(SourceDir("//foo/"), "d2"));
+ make_source_set(&d2);
+ d2.private_deps().push_back(LabelTargetPair(&e2));
+ ASSERT_TRUE(d2.OnResolved(&err));
+
+ Target a(setup.settings(), Label(SourceDir("//foo/"), "a"));
+ make_source_set(&a);
+ a.private_deps().push_back(LabelTargetPair(&b));
+ a.private_deps().push_back(LabelTargetPair(&group));
+ a.private_deps().push_back(LabelTargetPair(&rlib));
+ a.private_deps().push_back(LabelTargetPair(&d2));
+ a.private_deps().push_back(LabelTargetPair(&e2));
+ ASSERT_TRUE(a.OnResolved(&err));
+
+ // Source set: deps are on the .linkdeps phony.
+ {
+ std::ostringstream out;
+ NinjaCBinaryTargetWriter writer(&a, out);
+ writer.Run();
+ const char expected[] =
+ "build phony/foo/a.linkdeps: phony obj/foo/a.a.o || "
+ "phony/foo/b.linkdeps phony/foo/d.linkdeps obj/foo/librlib.rlib "
+ "phony/foo/d2.linkdeps phony/foo/e2.linkdeps phony/foo/f.linkdeps\n";
+ EXPECT_TRUE(out.str().contains(expected)) << out.str();
+ }
+
+ // Static library: deps are on the alink step.
+ {
+ Target lib(setup.settings(), Label(SourceDir("//foo/"), "lib"));
+ lib.set_output_type(Target::STATIC_LIBRARY);
+ lib.visibility().SetPublic();
+ lib.sources().push_back(SourceFile("//foo/lib.cc"));
+ lib.source_types_used().Set(SourceFile::SOURCE_CPP);
+ lib.private_deps().push_back(LabelTargetPair(&a));
+ lib.SetToolchain(setup.toolchain());
+ ASSERT_TRUE(lib.OnResolved(&err));
+
+ std::ostringstream out;
+ NinjaCBinaryTargetWriter writer(&lib, out);
+ writer.Run();
+ const char expected[] =
+ "build obj/foo/lib.a: alink obj/foo/lib.lib.o || "
+ "phony/foo/a.linkdeps\n";
+ EXPECT_TRUE(out.str().contains(expected)) << out.str();
+
+ // An executable depending on the static library links all the source
+ // sets' object files, but gets their order-only deps through the library.
+ Target exe(setup.settings(), Label(SourceDir("//foo/"), "exe"));
+ exe.set_output_type(Target::EXECUTABLE);
+ exe.visibility().SetPublic();
+ exe.sources().push_back(SourceFile("//foo/exe.cc"));
+ exe.source_types_used().Set(SourceFile::SOURCE_CPP);
+ exe.private_deps().push_back(LabelTargetPair(&lib));
+ exe.SetToolchain(setup.toolchain());
+ ASSERT_TRUE(exe.OnResolved(&err));
+
+ std::ostringstream exe_out;
+ NinjaCBinaryTargetWriter exe_writer(&exe, exe_out);
+ exe_writer.Run();
+ EXPECT_TRUE(exe_out.str().contains(" obj/foo/c.c.o ")) << exe_out.str();
+ EXPECT_TRUE(exe_out.str().contains(" obj/foo/lib.a ")) << exe_out.str();
+ EXPECT_FALSE(exe_out.str().contains(".linkdeps")) << exe_out.str();
+ }
+}
