Location>code7788 >text

AOT Rambling Topic (Part 7): Talking about Node Dependency Graphs for C#

Popularity:15 ℃/2024-10-24 10:46:55

I: Background

1. Storytelling

Previous articleWe Talked.AOT ProgrammingThe three main issues that you may encounter in the AOT, which in turn, test your knowledge of the AOT in theknot diagramThe understanding that it is the origin of everything, I will draw a few diagrams to interpret it from a personal point of view, not necessarily right.

II: Understanding Node Dependency Graphs

1. Understanding of nodes

According to the official word, constructing dependent nodes is the same as the GC's labeling algorithm, which uses depth-first, with each node being a type, for example:

  1. MethodCodeNode Indicates a method node
  2. EETypeNode Indicates a MethodTable type node.

At the same time the nodes have deeper hierarchical relationships, such as a link like this thatMethodCodeNode -> ObjectNode -> SortableDependencyNode -> DependencyNodeCore<DependencyContextType> -> DependencyNode -> IDependencyNode

By the way, the most central node dependency graph algorithm comes from the method(), simplified as follows:


    public override void ComputeMarkedNodes()
    {
        do
        {
            // Run mark stack algorithm as much as possible
            using (())
            {
                ProcessMarkStack();
            }

            // Compute all dependencies which were not ready during the ProcessMarkStack step
            _deferredStaticDependencies.TryGetValue(_currentDependencyPhase, out var deferredDependenciesInCurrentPhase);

            if (deferredDependenciesInCurrentPhase != null)
            {
                ComputeDependencies(deferredDependenciesInCurrentPhase);
                foreach (DependencyNodeCore<DependencyContextType> node in deferredDependenciesInCurrentPhase)
                {
                    ();
                    GetStaticDependenciesImpl(node);
                }

                ();
            }

            if (_markStack.Count == 0)
            {
                // Time to move to next deferred dependency phase.

                // 1. Remove old deferred dependency list(if it exists)
                if (deferredDependenciesInCurrentPhase != null)
                {
                    _deferredStaticDependencies.Remove(_currentDependencyPhase);
                }

                // 2. Increment current dependency phase
                _currentDependencyPhase++;

                // 3. Notify that new dependency phase has been entered
                ComputingDependencyPhaseChange?.Invoke(_currentDependencyPhase);
            }
        } while ((_markStack.Count != 0) || (_deferredStaticDependencies.Count != 0));

    }

During traversal, it is first traversed with theProcessMarkStack() Processes all static nodes, and after that processes those new nodes that were generated in the previous stage or those that were not ready in the previous stage, called heredelay nodeThis is a bit confusing, but let's take an example: A is a mandatory node, and C only goes in when B enters the dependency graph, otherwise it doesn't, so it's called a conditional dependency. Finally, I will match a diagram, you can view:

I can't make it up any further, so let's write a small example to visualize it.

2. A small example

The code is very simple, so you can see what a dependency graph constructed from this code might look like.


    internal class Program
    {
        static int Main(string[] args)
        {
            Animal animal = new Bird();
            ();
            return animal is Dog ? 1 : 0;
        }
    }

    public abstract class Animal
    {
        public virtual void Fly() { }

        public abstract void Sound();
    }

    public class Bird : Animal
    {
        public override void Sound() { }

        public override void Fly() { }
    }

    public class Dog : Animal
    {
        public override void Sound() { }
    }

Without hanging everyone up, the final dependency chart probably looks like this.

The picture above explains it a little:

  • Rectangle: Method Body
  • Ellipse: Class
  • Dashed Rectangle: Dummy Method
  • Dotted ellipse: unconstructed class
  • Dashed edge: Conditional dependencies

As you can see from the graph, the starting point is at theProgram::Main function, with the slight caveat that this is the logical managed entry, the real entry at the ilc level is the unmanaged function{[Example_21_1]<Module>.StartupCodeMain(int32,native int)} On top of that, everyone can be interested in theDependencyAnalyzerBase<DependencyContextType>.AddRoot The next breakpoint is sufficient, the screenshot is below:

Sharp-eyed friends may have a question about this() It makes sense that it was removed in the dependency chart, but is there any evidence for me to see for myself?

3. How to observe that a node has been removed

aot has put a lot of effort into debugging support, for example with IlcGenerateMapFile you can see the node type of each dependency graph, configured on csproj as follows:


<Project Sdk="">
	<PropertyGroup>
		<OutputType>Exe</OutputType>
		<TargetFramework>net8.0</TargetFramework>
		<ImplicitUsings>enable</ImplicitUsings>
		<Nullable>enable</Nullable>
		<PublishAot>true</PublishAot>
		<InvariantGlobalization>true</InvariantGlobalization>
		<IlcGenerateMapFile>true</IlcGenerateMapFile>
	</PropertyGroup>
</Project>

Next, open the generatedobj\Debug\net8.0\win-x64\native\Example_21_1. file, search for the correspondingBird__Sound cap (a poem)Bird__Fly Methods.

By the way, I'll explain the MethodCode node above a little bit, complete as follows:


  <MethodCode Name="Example_21_1_Example_21_1_Bird__Sound" Length="16" Hash="5e2f1c14edcffc6459b012c27e0e8410215a90cfa5dda68376042264d59e6252" />

I just said that.MethodCode is a method node, Name goes without saying, Length is the assembly code length of the method, and Hash is the hash representation of the bytecode, which is in the source code of the The answer can be found on.

4. Unconstructed type interpretation

This refers to the abovereturn animal is Dog ? 1 : 0; That being said, I personally don't think the AOT team did a good job with this one, why? Because.Animal is Dog The underlying call to the method, which at bottom only needs to save the The information will be fine, the screenshot is below:

But it's a shame that AOT actually putExample_21_1.() also appended to the dependency graph, which would be completely unnecessary.

If you want to generate it, then generate it, but it's disgusting that you don't give it a chance to be generated.Dog::Dog constructor, which results in the Dog not being able to be instantiated, causing it to become an island function.<IlcGenerateMapFile>true</IlcGenerateMapFile> Nodes can be observed more intuitively.

III: Summary

The generation of node dependency graphs is a more complex process, and the current AOT Compiler in .NET8 still has a lot of room for optimization, for example:

  1. Context-based dependency speculation.
  2. Unconstructed type speculation.
  3. Some unknowns not yet known...

NET9, .NET10 will be even better.
图片名称