Missing backedges and poor precompilation result

[timholy]

While analyzing a surprisingly-poor result from adding a precompile workload for Trixi (https://github.com/trixi-framework/TrixiStartup.jl), it became clear that the source of the trouble was missing backedge(s). I don't have a MWE, but installing VectorizedStatistics@v0.5.4 and making the following diff to PrecompileTools@1.0.2 (current main branch):

diff --git a/src/PrecompileTools.jl b/src/PrecompileTools.jl
index d5599ec..0f514ab 100644
--- a/src/PrecompileTools.jl
+++ b/src/PrecompileTools.jl
@@ -17,12 +17,22 @@ function workload_enabled(mod::Module)
     end
 end

+function check_edges(node)
+    parentmi = node.mi_info.mi
+    for child in node.children
+        childmi = child.mi_info.mi
+        (isdefined(childmi, :backedges) && parentmi ∈ childmi.backedges) || error("missing backedge from\n  $childmi\nto  $parentmi")
+        check_edges(child)
+    end
+end
+
 function precompile_roots(roots)
     @assert have_inference_tracking
     for child in roots
         mi = child.mi_info.mi
         precompile(mi.specTypes) # TODO: Julia should allow one to pass `mi` directly (would handle `invoke` properly)
         verbose[] && println(mi)
+        check_edges(child)
     end
 end

I get

julia> using VectorizedStatistics
Precompiling VectorizedStatistics
  ✗ VectorizedStatistics
  0 dependencies successfully precompiled in 14 seconds. 32 already precompiled.

ERROR: The following 1 direct dependency failed to precompile:

VectorizedStatistics [3b853605-1c98-4422-8364-4bd93ee0529e]

Failed to precompile VectorizedStatistics [3b853605-1c98-4422-8364-4bd93ee0529e] to "/tmp/pkgs/compiled/v1.10/VectorizedStatistics/jl_eE3FiL".
ERROR: LoadError: missing backedge from
  MethodInstance for (::Base.var"#48#49")(::Type{Float64})
to  MethodInstance for Base._any(::Base.var"#48#49", ::Tuple{DataType, DataType}, ::Colon)
Stacktrace:
  [1] error(s::String)
    @ Base ./error.jl:35
  [2] check_edges(node::Core.Compiler.Timings.Timing)
    @ PrecompileTools /tmp/pkgs/dev/PrecompileTools/src/PrecompileTools.jl:24
  [3] check_edges(node::Core.Compiler.Timings.Timing) (repeats 7 times)
    @ PrecompileTools /tmp/pkgs/dev/PrecompileTools/src/PrecompileTools.jl:25
  [4] precompile_roots(roots::Vector{Core.Compiler.Timings.Timing})
    @ PrecompileTools /tmp/pkgs/dev/PrecompileTools/src/PrecompileTools.jl:35
  [5] macro expansion
    @ /tmp/pkgs/dev/PrecompileTools/src/PrecompileTools.jl:97 [inlined]
  [6] macro expansion
    @ /tmp/pkgs/packages/VectorizedStatistics/K7wEX/src/precompile.jl:4 [inlined]
⋮

This is on Julia master but I get a similar result on Julia 1.9.0-rc3.

A bit of explanation about how this works: PrecompileTools turns on "inference snooping" which constructs a tree of the inference spawned by each runtime-dispatched call (the "roots" in PrecompileTools parlance). As you navigate each one of these trees, the children should have a backedge to each parent. The diff above just checks whether that's true.

This ends up affecting Trixi precompilation because we rely on tracing the backedges to find package-owned or explicitly "tagged" (by PrecompileTools) MethodInstances. In this case, an expensive-to-compile Trixi MethodInstance has no backedges to any "root" and thus gets omitted from the cache.

[timholy]

The practical consequences for PrecompileTools-managed precompilation will be fixed by JuliaLang/PrecompileTools.jl#15. @vtjnash has suggested that there may be backedges that aren't required for proper invalidation, and that pruning them might be a good thing; if this is one such case, then this issue should be closed. The only real question is whether that's not true, in which case missing backedges open us up to #265 violations.

[vtjnash]

Hopefully fixed since then, so I don't think there is an easy way to check for these