US-12619409-B2 - Systems and methods for eager software build

US12619409B2US 12619409 B2US12619409 B2US 12619409B2US-12619409-B2

Abstract

A method and apparatus of a device that builds a target using a plurality of processing units is described. In an exemplary embodiment, the device receives a build file for the target, where the build file identifies a plurality of dependencies and the first target is depended on a second target. In addition, the device generates a directed acyclic graph for the first target from the plurality of dependencies. Furthermore, the device transforms the directed acyclic graph by transforming the first set of dependencies to a second set of dependencies and the second set of dependency includes the first dependency that is from a first node in the first target to a second node of a second target. The device additionally identifies a plurality of independent executable tasks, where each of the plurality of independent executable tasks is executable without an unresolved dependency and at least one of the plurality of executable tasks is associated with the second set of dependencies of the transformed directed acyclic graph. The device further schedules the plurality of independent executable tasks on the plurality of processing units. In addition, the device concurrently executes the plurality of independent executable tasks.

Inventors

Richard Ballard
Daniel Dunbar
Matthew Moriarity

Assignees

APPLE INC.

Dates

Publication Date: 20260505
Application Date: 20190405

Claims (18)

1 . A non-transitory machine-readable medium having executable instructions to cause one or more processing units to perform a method to build a first target using a plurality of processing units, the method comprising: receiving a build file for the first target, wherein the build file identifies a first set of task dependencies and the first target is dependent on a second target; generating a directed acyclic graph for the first target from the first set of task dependencies; transforming the directed acyclic graph by identifying an immediate task in the first target, wherein the immediate task is a task represented in an untransformed directed acyclic graph with a task dependency but is run without the task dependency being completed, and transforming the first set of task dependencies to a second set of task dependencies and the second set of task dependencies includes a first task dependency that is from a first node representing the immediate task in the first target to a second node of the second target; identifying a plurality of independent executable tasks using at least the transformed directed acyclic graph, wherein each of the plurality of independent executable tasks is executable without an unresolved task dependency, at least one of the plurality of independent executable tasks is associated with the second set of task dependencies of the transformed directed acyclic graph, the transformed directed acyclic graph has a greater number of concurrently executable paths that each include one or more of the independent executable tasks than the untransformed directed acyclic graph, and the second set of task dependencies of the transformed directed acyclic graph has a reduced number of task dependencies than in the first set of task dependencies; scheduling the plurality of independent executable tasks on the plurality of processing units; and executing the plurality of independent executable tasks.
2 . The non-transitory machine readable medium of claim 1 , wherein a task is selected from the group consisting of compilation, linking, copying headers, copying frameworks, generating debugging information, and code signing.
3 . The non-transitory machine readable medium of claim 1 , wherein the directed acyclic graph includes nodes and edges, wherein each node is one of a task node, and a gate node, and each edge couples a task node with a gate node.
4 . The non-transitory machine readable medium of claim 1 , wherein a task node represents a set of one or more tasks.
5 . The non-transitory machine readable medium of claim 4 , wherein the first target is selected from the group consisting of an application, framework, plurality of applications, library, and an operating system.
6 . The non-transitory machine readable medium of claim 1 , wherein the transforming of the first set of task dependencies comprises: removing a second task dependency in the directed acyclic graph.
7 . The non-transitory machine readable medium of claim 1 , wherein the transforming of the first set of task dependencies comprises: identifying a compilation task in the first target; identifying a copy task in the second target; creating the first task dependency between the compilation task and the copy task; and removing the second task dependency between the compilation task and another task in the first target.
8 . The non-transitory machine readable medium of claim 1 , wherein the transforming of the first set of task dependencies comprises: adding a second task dependency in the directed acyclic graph.
9 . The non-transitory machine readable medium of claim 1 , wherein the immediate task is selected from the group consisting of creating a framework directory structure, creating an application directory structure, writing header maps, copying a standard library, copying a stub binary for a certain application programming interface kit, and writing a module maps.
10 . A method to build a first target using a plurality of processing units, the method comprising: receiving a build file for the first target, wherein the build file identifies a first set of task dependencies and the first target is dependent on a second target; generating a directed acyclic graph for the first target from the first set of task dependencies; transforming the directed acyclic graph by identifying an immediate task in the first target, wherein the immediate task is a task represented in an untransformed directed acyclic graph with a task dependency but is run without the task dependency being completed, and transforming the first set of task dependencies to a second set of task dependencies and the second set of task dependencies includes a first task dependency that is from a first node representing the immediate task in the first target to a second node of the second target; identifying a plurality of independent executable tasks using at least the transformed directed acyclic graph, wherein each of the plurality of independent executable tasks is executable without an unresolved task dependency, at least one of the plurality of independent executable tasks is associated with the second set of task dependencies of the transformed directed acyclic graph, the transformed directed acyclic graph has a greater number of concurrently executable paths that each include one or more of the independent executable tasks than the untransformed directed acyclic graph, and the second set of task dependencies of the transformed directed acyclic graph has a reduced number of task dependencies than in the first set of task dependencies; scheduling the plurality of independent executable tasks on the plurality of processing units; and executing the plurality of independent executable tasks.
11 . The method of claim 10 , wherein a task is selected from the group consisting of compilation, linking, copying headers, copying frameworks, generating debugging information, and code signing.
12 . The method of claim 10 , wherein the directed acyclic graph includes nodes and edges, wherein each node is one of a task node, and a gate node, and each edge couples a task node with a gate node.
13 . The method of claim 12 , wherein the first target is selected from the group consisting of an application, framework, plurality of applications, library, and an operating system.
14 . The method of claim 10 , wherein the transforming of the first set of task dependencies comprises: removing a second task dependency in the directed acyclic graph.
15 . The method of claim 14 , wherein the transforming of the first set of task dependencies comprises: identifying a compilation task in the first target; identifying a copy task in the second target; creating the task dependency between the compilation task and the copy task; and removing a task dependency between the compilation task and another task in the first target.
16 . The method of claim 10 , wherein the transforming of the first set of task dependencies comprises: adding a second task dependency in the directed acyclic graph.
17 . The method of claim 10 , wherein the immediate task is selected from the group consisting of creating a framework directory structure, creating an application directory structure, writing header maps, copying a standard library, copying a stub binary for a certain application programming interface kit, and writing a module maps.
18 . A device that builds a first target, the device comprising: at least one processor; a memory coupled to the at least one processor through a bus; and a process executed from memory by the processor that causes the processor to receive a build file for the first target, wherein the build file identifies a first set of task dependencies and the first target is dependent on a second target, generate a directed acyclic graph for the first target from the first set of task dependencies, transform the directed acyclic graph by identifying an immediate task in the first target, wherein the immediate task is a task represented in an untransformed directed acyclic graph with a task dependency but is run without the task dependency being completed and transform the first set of task dependencies to a second set of task dependencies and the second set of task dependencies includes an additional task dependency that is from a first node representing the immediate task in the first target to a second node of the second target, identify a plurality of independent executable tasks using at least the transformed directed acyclic graph, wherein each of the plurality of independent executable tasks is executable without an unresolved task dependency and at least one of the plurality of independent executable tasks is associated with the second set of task dependencies of the transformed directed acyclic graph, the transformed directed acyclic graph has a greater number of concurrently executable paths that each include one or more of the independent executable tasks than the untransformed directed acyclic graph, and the second set of task dependencies of the transformed directed acyclic graph has a reduced number of dependencies than in the first set of dependencies, and schedule the plurality of independent executable tasks on the plurality of processors, and execute the plurality of independent executable tasks.

Description

FIELD OF INVENTION This invention relates generally to compilation technology and more particularly to identifying and executing build tasks. BACKGROUND OF THE INVENTION In software development, a developer can use a build automation tool to build executable programs and libraries. Each of the executable programs and/or libraries can be dependent on other entities, such as source files, object files, other libraries, etc. For example, the tasks that make up building a target (e.g., an application, framework, or library) can be grouped into a target. Furthermore, one target can be dependent on another target. If target A depends on target B, the build system must wait for every task that goes into building target B to finish before any tasks for target A can begin. This makes for a simple model, but it limits opportunities for parallelism in the build. Certainly not every task in target A requires B to be completely built, linked, and post-processed. SUMMARY OF THE DESCRIPTION A method and apparatus of a device that builds a target using a plurality of processing units is described. In an exemplary embodiment, the device receives a build file for the first target, where the build file identifies a plurality of dependencies and the first target is depended on a second target. In addition, the device generates a directed acyclic graph for the first target from the plurality of dependencies. Furthermore, the device transforms the directed acyclic graph by transforming the first set of dependencies to a second set of dependencies and the second set of dependency includes a first dependency that is from a first node in the first target to a second node of a second target. The device additionally identifies a plurality of independent executable tasks, where each of the plurality of independent executable tasks is executable without an unresolved dependency and at least one of the plurality of executable tasks is associated with the second set of dependencies of the transformed directed acyclic graph. The device further schedules the plurality of independent executable tasks on the plurality of processing units. In addition, the device executes the plurality of independent executable tasks. In a further embodiment, a task is selected from the group consisting of compilation, linking, copying headers, copying frameworks, generating debugging information, and code signing. In addition, a directed acyclic graph includes nodes and edges, wherein each node is one of a task node, and gate node, and each edge couples a task node with a gate node. Furthermore, the task node represents a set of one or more tasks. Additionally, a target is selected from the group consisting of an application, framework, plurality of applications, library, and an operating system. In another embodiment, the device removes and/or adds a second dependency in the directed acyclic graph. The device further identifies a compilation task in the first target and a copy task in the second target. The device additionally creates the first dependency between the compilation task and the copy task. In addition, the device removes the third dependency between the compilation task and another task in the first target. Furthermore, the plurality of independent executable tasks includes an immediate task, wherein the immediate task is a task represented in the untransformed directed acyclic graph with a dependency but can be run without this dependency being completed. The immediate task can be one of creating a framework directory structure, creating an application directory structure, writing header maps, copying a standard library, copying a stub binary for certain an application programming interface kit, and writing a module maps. In one embodiment, a machine-readable medium having executable instructions to cause one or more processing units to perform a method to build a target using a plurality of processing units is described. In an exemplary embodiment, the machine-readable medium method receives a build file for the first target, where the build file identifies a first set of dependencies and the first target is depended on a second target. In addition, the machine-readable medium method generates a directed acyclic graph for the first target from the first set of dependencies. Furthermore, the machine-readable medium method transforms the directed acyclic graph by transforming the first set of dependencies to a second set of dependencies and the second set of dependency includes a first dependency is from a first node in the first target to a second node of a second target. The machine-readable medium method additionally identifies a plurality of independent executable tasks, where each of the plurality of independent executable tasks is executable without an unresolved dependency and at least one of the plurality of executable tasks is associated with the second set of dependencies of the transformed directed acyclic graph. The machine-readable