From a05ddaa95a8f7f65fe01e2c1613a354876e69839 Mon Sep 17 00:00:00 2001 From: Boris Kolpackov Date: Thu, 10 Mar 2022 10:17:48 +0200 Subject: Add reverse_execute_prerequisites() variant --- libbuild2/algorithm.cxx | 109 ++++++++++++++++++++++++++++++++++++++++++--- libbuild2/algorithm.hxx | 16 ++++++- libbuild2/algorithm.ixx | 14 ++++++ libbuild2/cc/link-rule.cxx | 29 +++++++++--- 4 files changed, 154 insertions(+), 14 deletions(-) diff --git a/libbuild2/algorithm.cxx b/libbuild2/algorithm.cxx index 64d4689..217e7af 100644 --- a/libbuild2/algorithm.cxx +++ b/libbuild2/algorithm.cxx @@ -2404,9 +2404,9 @@ namespace build2 const timestamp& mt, const execute_filter& ef, size_t n) { - context& ctx (t.ctx); + assert (a == perform_update_id); - assert (ctx.current_mode == execution_mode::first); + context& ctx (t.ctx); size_t busy (ctx.count_busy ()); size_t exec (ctx.count_executed ()); @@ -2441,7 +2441,7 @@ namespace build2 wg.wait (); bool e (mt == timestamp_nonexistent); - const target* rt (tt != nullptr ? nullptr : &t); + const target* rt (nullptr); for (size_t i (0); i != n; ++i) { @@ -2479,18 +2479,113 @@ namespace build2 if (p.adhoc ()) p.target = nullptr; // Blank out. - else + else if (tt != nullptr) { if (rt == nullptr && pt.is_a (*tt)) rt = &pt; } } - assert (rt != nullptr); + assert (tt == nullptr || rt != nullptr); + + return pair, const target*> ( + e ? optional () : rs, rt); + } + + pair, const target*> + reverse_execute_prerequisites (const target_type* tt, + action a, const target& t, + const timestamp& mt, const execute_filter& ef, + size_t n) + { + assert (a == perform_update_id); + + context& ctx (t.ctx); + + size_t busy (ctx.count_busy ()); + size_t exec (ctx.count_executed ()); + + auto& pts (t.prerequisite_targets[a]); + + if (n == 0) + n = pts.size (); + + // Pretty much as reverse_execute_members() but hairier. + // + target_state rs (target_state::unchanged); + + wait_guard wg (ctx, busy, t[a].task_count); + + for (size_t i (n); i != 0; ) + { + const target*& pt (pts[--i]); + + if (pt == nullptr) // Skipped. + continue; + + target_state s (execute_async (a, *pt, busy, t[a].task_count)); + + if (s == target_state::postponed) + { + rs |= s; + pt = nullptr; + } + } + + wg.wait (); + + bool e (mt == timestamp_nonexistent); + const target* rt (nullptr); + + for (size_t i (n); i != 0; ) + { + prerequisite_target& p (pts[--i]); + + if (p == nullptr) + continue; + + const target& pt (*p.target); + + ctx.sched.wait (exec, pt[a].task_count, scheduler::work_none); + + target_state s (pt.executed_state (a)); + rs |= s; + + // Should we compare the timestamp to this target's? + // + if (!e && (p.adhoc () || !ef || ef (pt, i))) + { + // If this is an mtime-based target, then compare timestamps. + // + if (const mtime_target* mpt = pt.is_a ()) + { + if (mpt->newer (mt, s)) + e = true; + } + else + { + // Otherwise we assume the prerequisite is newer if it was changed. + // + if (s == target_state::changed) + e = true; + } + } + + if (p.adhoc ()) + p.target = nullptr; // Blank out. + else if (tt != nullptr) + { + // Note that here we need last. + // + if (pt.is_a (*tt)) + rt = &pt; + } + } + + assert (tt == nullptr || rt != nullptr); return pair, const target*> ( - e ? optional () : rs, - tt != nullptr ? rt : nullptr); + e ? optional () : rs, rt); } target_state diff --git a/libbuild2/algorithm.hxx b/libbuild2/algorithm.hxx index b472603..00d4fdd 100644 --- a/libbuild2/algorithm.hxx +++ b/libbuild2/algorithm.hxx @@ -678,8 +678,8 @@ namespace build2 // case if they are up to something tricky (like recursively linking liba{} // prerequisites). // - // Note that because we use mtime, this function should normally only be - // used in the perform_update action (which is straight). + // Note that because we use mtime, this function can only be used for the + // perform_update action. // using execute_filter = function; @@ -689,6 +689,18 @@ namespace build2 const execute_filter& = nullptr, size_t count = 0); + // As above, but execute prerequisites in reverse. + // + // Sometime it may be advantageous to execute prerequisites in reverse, for + // example, to have more immediate incremental compilation or more accurate + // progress. See cc::link_rule for background. + // + optional + reverse_execute_prerequisites (action, const target&, + const timestamp&, + const execute_filter& = nullptr, + size_t count = 0); + // Another version of the above that does two extra things for the caller: // it determines whether the action needs to be executed on the target based // on the passed timestamp and finds a prerequisite of the specified type diff --git a/libbuild2/algorithm.ixx b/libbuild2/algorithm.ixx index c57e117..1b3a5cd 100644 --- a/libbuild2/algorithm.ixx +++ b/libbuild2/algorithm.ixx @@ -834,6 +834,12 @@ namespace build2 const timestamp&, const execute_filter&, size_t); + LIBBUILD2_SYMEXPORT pair, const target*> + reverse_execute_prerequisites (const target_type*, + action, const target&, + const timestamp&, const execute_filter&, + size_t); + inline optional execute_prerequisites (action a, const target& t, const timestamp& mt, const execute_filter& ef, @@ -842,6 +848,14 @@ namespace build2 return execute_prerequisites (nullptr, a, t, mt, ef, n).first; } + inline optional + reverse_execute_prerequisites (action a, const target& t, + const timestamp& mt, const execute_filter& ef, + size_t n) + { + return reverse_execute_prerequisites (nullptr, a, t, mt, ef, n).first; + } + template inline pair, const T&> execute_prerequisites (action a, const target& t, diff --git a/libbuild2/cc/link-rule.cxx b/libbuild2/cc/link-rule.cxx index 50c56a4..2e644cc 100644 --- a/libbuild2/cc/link-rule.cxx +++ b/libbuild2/cc/link-rule.cxx @@ -2470,14 +2470,33 @@ namespace build2 // Note that execute_prerequisites() blanks out all the ad hoc // prerequisites so we don't need to worry about them from now on. // + // There is an interesting trade-off between the straight and reverse + // execution. With straight we may end up with inaccurate progress if + // most of our library prerequisites (typically specified last) are + // already up to date. In this case, the progress will first increase + // slowly as we compile this target's source files and then jump + // straight to 100% as we "realize" that all the libraries (and all + // their prerequisites) are already up to date. + // + // Switching to reverse fixes this but messes up incremental building: + // now instead of starting to compile source files right away, we will + // first spend some time making sure all the libraries are up to date + // (which, in case of an error in the source code, will be a complete + // waste). + // + // There doesn't seem to be an easy way to distinguish between + // incremental and from-scratch builds and on balance fast incremental + // builds feel more important. + // target_state ts; - if (optional s = - execute_prerequisites (a, - t, - mt, - [] (const target&, size_t) {return false;})) + if (optional s = execute_prerequisites ( + a, t, + mt, + [] (const target&, size_t) {return false;})) + { ts = *s; + } else { // An ad hoc prerequisite renders us out-of-date. Let's update from -- cgit v1.1